#include "discrim.h"

This page has information from files discrim.h and discrim.c.

Public Routines
Public Definitions
Introduction

Public Routines in File discrim.c

Index

destroy_discrim_tree	discrim_init	free_discrim_pos	p_discrim_mem
discrim_dealloc	fprint_discrim_mem	get_discrim
discrim_empty	free_discrim	get_discrim_pos

Details

void destroy_discrim_tree(Discrim d);

This routine frees all the memory associated with a discrimination index. It can be used with either wild or tame trees.

void discrim_dealloc(Discrim d);

This routine frees an empty discrimination index (wild or tame).

BOOL discrim_empty(Discrim d);

This Boolean function checks if a discrimination index is empty. It can be used with either wild or tame trees.

Discrim discrim_init(void);

This routine allocates and returns an empty discrimination index. It can be used for either wild or tame indexing.

void fprint_discrim_mem(FILE *fp, BOOL heading);

This routine prints (to FILE *fp) memory usage statistics for data types associated with the discrim package. The Boolean argument heading tells whether to print a heading on the table.

void free_discrim(Discrim p);

void free_discrim_pos(Discrim_pos p);

Discrim get_discrim(void);

Discrim_pos get_discrim_pos(void);

The structure is not initialized.

void p_discrim_mem(void);

This routine prints (to stdout) memory usage statistics for data types associated with the discrim package.

Public Definitions in File discrim.h

typedef struct discrim * Discrim;

struct discrim {       /* node in a discrimination tree */
  Discrim   next;      /* sibling */
  union {
    Discrim kids;      /* for internal nodes */
    Plist data;        /* for leaves */
  } u;
  short symbol;        /* variable number or symbol number */
  char type;           /* term type and for ac indexing type */
};

typedef struct discrim_pos * Discrim_pos;

struct discrim_pos {  /* to save position in set of answers */
  void    *query;
  Context subst;        /* substitution */
  Plist   data;         /* identical terms from leaf of discrim tree */
  void    *backtrack;   /* data for backtracking */
};

/* type of discrimination tree node */

enum { DVARIABLE, DRIGID, AC_ARG_TYPE, AC_NV_ARG_TYPE };

#define DVAR(d)  ((d)->type == DVARIABLE)

Introduction

This package implements two kinds of discrimination indexing for first-order terms. Both kinds support GENERALIZATION retrieval only (e.g., for forward demodulation and forward subsumption).

The "wild" kind is an imperfect filter, and it does not bind variables. The caller must also call a routine, say match(), to check if the answers are really more general than the query term and to construct the substitution. Wild indexing supports associative-commutative (AC) and commutative (C) symbols. Indexing terms with AC symbols works by considering the number of arguments and the number of nonvariable arguments of AC terms that do not occur in other AC terms. (The term "wild" is used because all variables in the discrimination tree are treated as the the wildcard symbol *).

With the "bind" kind, every answer is more general than the query term, and the matching substitution is constructed during the retrieval. Wild indexing supports commutative (C) symbols, but it does not support associative-commutative (AC) symbols. Retrieval with C symbols can produce duplicate answers.