home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / GCC / GERLIB_DEV08B.LHA / gerlib / libg++ / etc / ADT-examples / Patricia.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-12-12  |  2.1 KB  |  68 lines
  1. /* Implements the PATRICIA Trie ADT.  PATRICIA stands for ``Practical
  2.    Algorithm to Retrieve Information Coded in Alphanumeric.''  PATRICIA
  3.    was developed by D.R. Morrison.  The current implementation is
  4.    based upon Robert Sedgewick's description in his Algorithms book.
  5.    
  6.    Includes operations for
  7.  * Initialization
  8.  * Insertion
  9.  * Retrieval */
  10.  
  11. /* This could change, depending on what client wants */
  12. typedef void *CONTENTS; 
  13.  
  14. /* Record structure that *must* be visible to clients. */ 
  15.  
  16. class Trie_Record
  17. {
  18. private:
  19.   char    *key;           /* Only works safely and easily for char *'s */
  20.   CONTENTS contents;      /* Pointer to record Contents referenced by Key */
  21.  
  22. public:
  23.   char    *get_key (void) { return key; }
  24.   CONTENTS get_contents (void) { return contents; }
  25.   void     set_key (char *k) { key = k; }
  26.   void     set_contents (CONTENTS c) { contents = c; }
  27. };
  28.  
  29. /* We globalized the class because this is done by g++ 1.40 anyway and with 
  30.  * 1.9? this does not work at all (one has to prefix all members of the nested
  31.  * class with the name of the enclosing class.H.S.
  32.  */
  33.   /* Nested class definition, should be invisible to clients with new C++ 
  34.      scoping rules... */
  35.  
  36.   struct Trie_Node 
  37.     {                      
  38.       Trie_Record trie_rec;      /* Stores data in the Trie */
  39.       int         branch_bit;    /* Stores index of next Bit to compare */
  40.       Trie_Node  *left;          /* Pointer to left child. */
  41.       Trie_Node  *right;         /* Pointer to right child. */
  42.       
  43.       Trie_Node (char *k = "", int len = 0, CONTENTS new_contents = 0, int b = 0);
  44.     };
  45.  
  46. class Patricia_Trie 
  47. {
  48. private:
  49.  
  50.   /* Root for the entire Patricia tree, (actually a dummy header!). */
  51.   Trie_Node *root;
  52.   
  53.   /* Recursively free tree memory via modified post-order traversal. */
  54.   void dispose_trie (Trie_Node *root);
  55.  
  56.   /* Returns 1 if bit is set. */
  57.   inline int is_bit_set (int block, int shift) { return (block & (1 << shift)) != 0; }
  58.  
  59.   /* Return the ith power of 2. */
  60.   inline int POW2 (int i) { return 1 << i; }
  61.   
  62. public:
  63.   Patricia_Trie (void);
  64.  ~Patricia_Trie (void);
  65.   Trie_Record *find (char *key);
  66.   void insert (char *key, CONTENTS contents, int key_len = 0);
  67. };
  68.