1 //////////////////////////////////////////////////////////////////////////////
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
11 // Although you are under no obligation to do so, we strongly recommend that
12 // you give away all software developed using our tools.
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
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef compressed_trie_h
26 #define compressed_trie_h
29 // Compressed trie (well, actually a dfa).
32 #include <AD/generic/generic.h>
34 class CompressedTrie
{
36 CompressedTrie(const CompressedTrie
&); // no copy constructor
37 void operator = (const CompressedTrie
&); // no assignment
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
52 Symbol min_symbol
; // minimal value of symbol
53 Symbol max_symbol
; // maximal value of symbol
55 Node start
; // root of the trie
60 CompressedTrie(Symbol min_symbol
, Symbol max_symbol
, int size
);
63 Node
root() const { return start
; }
65 Node
lookup(Node node
, Symbol c
) const
66 { register Node offset
= base
[node
] + c
;
67 if (check
[offset
] == node
) return next
[offset
];