/* 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. =============================================================*/