include/AD/automata/treemat.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 regular_tree_matcher_h
  26 #define regular_tree_matcher_h
  27
  28 //////////////////////////////////////////////////////////////////////////
  29 //
  30 // Class |TreeMatcher| represents a tree automaton with compressed
  31 // lookup tables.  See class |TreeGen| for the generator.
  32 //
  33 //////////////////////////////////////////////////////////////////////////
  34
  35 #include <AD/automata/treetab.h>  // tree automata tables
  36
  37 class TreeMatcher : public TreeTables {
  38
  39    TreeMatcher(const TreeMatcher&);       // no copy constructor
  40    void operator = (const TreeMatcher&);  // no assignment
  41
  42 public:
  43
  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;
  53
  54 protected:
  55
  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
  62
  63 public:
  64
  65    ///////////////////////////////////////////////////////////////////////
  66    //  Constructor
  67    ///////////////////////////////////////////////////////////////////////
  68    TreeMatcher( const Arity  arity_table[],
  69                 const Offset base_table [],
  70                 const State  index_table[]
  71               )
  72       : arity(arity_table), base(base_table), index(index_table) {}
  73
  74    ///////////////////////////////////////////////////////////////////////
  75    //  Selectors
  76    ///////////////////////////////////////////////////////////////////////
  77    inline int rank(Functor f) const { return arity[f]; }
  78
  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    //////////////////////////////////////////////////////////////////////////
  85
  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];
  95       }
  96 };
  97
  98 #endif