/*
 * 5799-WZQ (C) COPYRIGHT IBM CORPORATION 1986
 * LICENSED MATERIALS - PROPERTY OF IBM
 * REFER TO COPYRIGHT INSTRUCTIONS FORM NUMBER G120-2083
 */
/* $Header:trie.h 12.0$ */
/* $ACIS:trie.h 12.0$ */
/* $Source: /ibm/acis/usr/src/ibm/lib/tools/RCS/trie.h,v $ */

#if !defined(lint) && !defined(LOCORE)  && defined(RCS_HDRS)
static char *rcsidtrie = "$Header:trie.h 12.0$";
#endif

  /*\
  |*   PROVIDES --
  |*
  |*   trie *
  |*   tr_New()             -- Returns a pointer to a newly created,
  |*                           initialized, trie.
  |*   char *
  |*   tr_Add(tr,str,flag)  --  Adds the string 'str' to 'tr' so that
  |*   trie    *tr;		calls to tr_Find(tr,str) will return
  |*   char    *str,*flag;      'flag'. Returns the string (structure)
  |*                            formerly associated with 'str' in 'tr'.
  |*   char *
  |*   tr_Find(tr,str)      --  Retrieves the string (structure) that
  |*   trie   *tr;              is associated with 'str' in 'tr'.
  |*   char   *str;             Returns NULL if no association.
  |*
  |*   int
  |*   tr_Ok(tr,str)        --  Returns TR_OK if 'str' is a prefix for
  |*   trie  *tr;               any of the strings stored in 'tr',
  |*   char  *str;              bitwise OR'ed with TR_VALID if it is a
  |*                            valid string by itself.  Returns
  |*   TR_ILLEGAL if 'str' is not a valid prefix for 'tr'
  |*
  |*   char *
  |*   tr_Expand(tr,str,flg)--  Returns the longest legal prefix for a
  |*   trie  *tr;               string in 'tr' that is also a prefix of
  |*   char  *str;              'str', or, if 'str' is a legal prefix
  |*   int   *flg;              itself, it returns the longest unique
  |*                            trie prefix which contains 'str' as
  |*   prefix.  In other words, this this performs EMACS/TOPS-20 like
  |*   dictionary expansion. The integer pointed to by 'flg' is set
  |*   to contain status information regarding the expansion.  Returned
  |*   values are:  TR_EXPANDED if 'str' is expanded to form a prefix,
  |*   TR_SHRUNK if 'str'is shrunk, TR_OK if 'str' is already a valid
  |*   prefix. In addition, if the returned string is one of the strings
  |*   stored in 'tr', (*flg) is bitwise OR'ed with TR_VALID.
  |*
  |*   Trie contains:  fool, food, foolish, foolishness
  |*
  |*     STR CONTAINS		RETURNED STRING    VALUE OF FLG
  |*     ------------           ---------------    ------------
  |*     "a"                    NULL               TR_SHRUNK
  |*     "f"                    "foo"              TR_EXPANDED
  |*     "foo"			"foo"              TR_OK
  |*     "fool"                 "fool"             TR_OK|TR_VALID
  |*     "fooli"                "foolish"          TR_EXPANDED|TR_VALID
  |*     "foolishn"             "foolishness"      TR_EXPANDED|TR_VALID
  |*     "foolishnessh"         "foolishness"      TR_SHRUNK|TR_VALID
  |*     "fowl"                 "fo"               TR_SHRUNK
  |*
  |*  int
  |*  tr_Dump(fil,tr)   --       Dumps 'tr' to fil
  |*
  |*  trie *
  |*  tr_Load(fil) --       Loads a trie from fil and returns a pointer
  |*
  |*  NOTE:	This code is not very extensively tested (or documented)
  |*            I expect to polish this when I get a chance.
  |*            Right now this is VERY space inefficient, I hope to
  |*            clean it up in the near future.
  |*            Drop me a note if you encounter (and/or fix) any bugs,
  |*            or extend this in any way. (or if you are interested
  |* 		receiving any future versions).
  |*
  |*                       copyright (c)  IBM 1986
  |*
  \*/

#define TR_SHRUNK    0x01
#define TR_OK        0x02
#define TR_EXPANDED  0x04
#define TR_VALID     0x0100
#define TR_ILLEGAL   0x8

int tr_debug;

typedef struct TR {
		     char  *tr_root;  /* actually (trie_node *) */
                  } trie;

extern trie    *tr_New();
extern char    *tr_Add();
extern char    *tr_Find();
extern int      tr_Ok();
extern char    *tr_Expand();
extern int	tr_Dump();
extern trie    *tr_Load();
