/* Copyright (C) 1995 Bjoern Beutel. */

/* Description. =============================================================*/

/* This module implements a static trie structure. */

/* Types. ===================================================================*/

typedef struct  /* A "trie_entry_t" associates KEY with CONTENT. */
{ 
  string_t key; /* The key of a trie entry is considered case insensitive. */
  int_t content;
} trie_entry_t;

/* Functions. ===============================================================*/

/* A trie is a vector of ints. When constructed, it is returned as a pool
 * together with the index of the root node. */

extern void new_trie( int_t n, 
                      trie_entry_t *entries, 
                      pool_t *trie_pool, 
                      int_t *root_node_index );
/* Take N ENTRIES and build a trie of them.
 * Return the trie in *TRIE_POOL 
 * and the index of its root node in *ROOT_NODE_INDEX.
 * The keys in *ENTRIES must be non-empty, unique, and sorted. */

extern bool_t lookup_trie( int_t *trie, 
                           int_t *node_index, 
                           string_t *input, 
                           int_t *content );
/* Test if a prefix of *INPUT matches the node at *NODE_INDEX in TRIE.
 * If it does, return TRUE (else return FALSE) and:
 *   *CONTENT contains the associated content,
 *   *NODE contains the subnode for the matched input, and
 *   *INPUT points to the first char behind the prefix. */

/* End of file. =============================================================*/