simple.cc - generated code example
[prop.git] / include / AD / automata / treemat.h
blob169f7577b6c0755a3ca341c5cfd81b14c7ef9954
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.
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
16 // code.
18 // This software is still under development and we welcome any suggestions
19 // and help from the users.
21 // Allen Leung
22 // 1994
23 //////////////////////////////////////////////////////////////////////////////
25 #ifndef regular_tree_matcher_h
26 #define regular_tree_matcher_h
28 //////////////////////////////////////////////////////////////////////////
30 // Class |TreeMatcher| represents a tree automaton with compressed
31 // lookup tables. See class |TreeGen| for the generator.
33 //////////////////////////////////////////////////////////////////////////
35 #include <AD/automata/treetab.h> // tree automata tables
37 class TreeMatcher : public TreeTables {
39 TreeMatcher(const TreeMatcher&); // no copy constructor
40 void operator = (const TreeMatcher&); // no assignment
42 public:
44 ///////////////////////////////////////////////////////////////////////
45 // Inport some types
46 ///////////////////////////////////////////////////////////////////////
47 typedef TreeTables Super;
48 typedef Super::Functor Functor;
49 typedef Super::Arity Arity;
50 typedef Super::State State;
51 typedef Super::Offset Offset;
52 typedef Super::Rule Rule;
54 protected:
56 ///////////////////////////////////////////////////////////////////////
57 // Compressed tables
58 ///////////////////////////////////////////////////////////////////////
59 const Arity * const arity; // Mapping from functors to arities
60 const Offset * const base; // Mapping from functors to base offset
61 const State * const index; // Tables mu and theta in linearized form
63 public:
65 ///////////////////////////////////////////////////////////////////////
66 // Constructor
67 ///////////////////////////////////////////////////////////////////////
68 TreeMatcher( const Arity arity_table[],
69 const Offset base_table [],
70 const State index_table[]
72 : arity(arity_table), base(base_table), index(index_table) {}
74 ///////////////////////////////////////////////////////////////////////
75 // Selectors
76 ///////////////////////////////////////////////////////////////////////
77 inline int rank(Functor f) const { return arity[f]; }
79 //////////////////////////////////////////////////////////////////////////
80 // Advance one state within the tree automaton.
81 // The first go() function is an optimized form for a unit functor--
82 // i.e. a functor with 0 arity. The second go() function is the general
83 // form which looks up all three tables.
84 //////////////////////////////////////////////////////////////////////////
86 inline State go(Functor f) const { return (State) base[f]; }
87 inline State go(Functor f, const State * inputs) const
88 { register Offset offset; // current offset
89 register const State * indices; // indices;
90 register int i;
91 for (i = arity[f], offset = base[f], indices = index + offset + 1;
92 i > 0; i--, indices += indices[-1])
93 offset += indices[ *inputs++ ];
94 return index[offset];
98 #endif