include/AD/tries/comptrie.h

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef compressed_trie_h
  26 #define compressed_trie_h
  27
  28 //
  29 // Compressed trie (well, actually a dfa).
  30 //
  31
  32 #include <AD/generic/generic.h>
  33
  34 class CompressedTrie {
  35
  36    CompressedTrie(const CompressedTrie&);      // no copy constructor
  37    void operator = (const CompressedTrie&);    // no assignment
  38
  39 public:
  40
  41    typedef short Symbol;
  42    typedef int Node;
  43
  44 protected:
  45
  46    Node   * next;       //  Transition function indexed by node
  47    Node   * base;       //  base pointer
  48    Node   * check;      //  back pointer
  49    Symbol * symbol;     //  Symbol at node
  50    int      size;       //  length of these arrays
  51
  52    Symbol   min_symbol; //  minimal value of symbol
  53    Symbol   max_symbol; //  maximal value of symbol
  54
  55    Node     start;      //  root of the trie
  56
  57 public:
  58
  59    CompressedTrie();
  60    CompressedTrie(Symbol min_symbol, Symbol max_symbol, int size);
  61   ~CompressedTrie();
  62
  63    Node root() const { return start; }
  64
  65    Node lookup(Node node, Symbol c) const
  66       {  register Node offset = base[node] + c;
  67          if (check[offset] == node) return next[offset];
  68          else return -1;
  69       }
  70 };
  71
  72 #endif