include/AD/rewrite/b_items.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 welcomed 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(read crave for)
  19 // any suggestions and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #ifndef BURS_item_set_h
  26 #define BURS_item_set_h
  27
  28 #include <iostream.h>
  29 #include <new.h>
  30 #include <AD/rewrite/b_item.h>  // Item set
  31 #include <AD/memory/mem.h>      // Memory manager
  32 #include <AD/contain/bitset.h>  // Bit sets
  33
  34 //////////////////////////////////////////////////////////////////////////////
  35 //  A state in the BURS tree automata is represented as a set of items.
  36 //  We represent an item set simply as a vector of BURS_item's indexed
  37 //  by the non-terminal.
  38 //////////////////////////////////////////////////////////////////////////////
  39 class BURS_ItemSet {
  40 public:
  41
  42    ///////////////////////////////////////////////////////////////////////////
  43    //  Import some types
  44    ///////////////////////////////////////////////////////////////////////////
  45    typedef BURS_Item::State       State;
  46    typedef BURS_Item::Functor     Functor;
  47    typedef BURS_Item::NonTerminal NonTerminal;
  48    typedef BURS_Item::Arity       Arity;
  49    typedef BURS_Item::Cost        Cost;
  50    typedef BURS_Item::Rule        Rule;
  51
  52    ///////////////////////////////////////////////////////////////////////////
  53    //   We'll implement a set of non-terminals as a bitset.
  54    //   The bitset iterator is given more readable alias.
  55    ///////////////////////////////////////////////////////////////////////////
  56    typedef BitSet NonTerminalSet;
  57 #  define foreach_nonterminal(n,set) foreach_bit(n,set)
  58
  59    ///////////////////////////////////////////////////////////////////////////
  60    //  Import some constants
  61    ///////////////////////////////////////////////////////////////////////////
  62    enum BURS_ItemSet_constants
  63    {  infinite_cost = TreeGrammar::infinite_cost,
  64       zero_cost     = TreeGrammar::zero_cost
  65    };
  66
  67 private:
  68
  69    int          n;         // number of non-terminals
  70    BURS_Item    items[1];  // a vector of items, indexed by non-terminal.
  71
  72 public:
  73
  74    ///////////////////////////////////////////////////////////////////////////
  75    //  Memory management routines.
  76    //  We'll redefine `new' and `delete' since item sets are to be allocated
  77    //  using our own memory pools for efficiency.
  78    ///////////////////////////////////////////////////////////////////////////
  79    inline void * operator new    (size_t, Mem& mem, int k);
  80    inline void   operator delete (void *) {}
  81
  82    ///////////////////////////////////////////////////////////////////////////
  83    //  Some selectors.
  84    ///////////////////////////////////////////////////////////////////////////
  85    inline int              size()                      const { return n; }
  86    inline const BURS_Item& operator [] (NonTerminal A) const { return items[A]; }
  87    inline       BURS_Item& operator [] (NonTerminal A)       { return items[A]; }
  88
  89    ///////////////////////////////////////////////////////////////////////////
  90    //  Operations on an item set.
  91    ///////////////////////////////////////////////////////////////////////////
  92    inline void clear           ();
  93    inline void normalise_costs ();
  94
  95    ///////////////////////////////////////////////////////////////////////////
  96    //  Hashing and equality
  97    ///////////////////////////////////////////////////////////////////////////
  98    inline friend unsigned int hash  (const BURS_ItemSet *);
  99    inline friend Bool         equal (const BURS_ItemSet *, const BURS_ItemSet *);
 100
 101    ///////////////////////////////////////////////////////////////////////////
 102    //  Printing method
 103    ///////////////////////////////////////////////////////////////////////////
 104    friend ostream& operator << (ostream&, const BURS_Item&);
 105 };
 106
 107 //////////////////////////////////////////////////////////////////////////////
 108 //  Clears out an item set
 109 //////////////////////////////////////////////////////////////////////////////
 110 inline void BURS_ItemSet::clear()
 111 {  for (register int i = n - 1; i > 0; i--) {
 112       items[i].cost = infinite_cost;
 113       items[i].rule = 0;
 114    }
 115    items[0].cost = 0;
 116    items[0].rule = 0;
 117 }
 118
 119 //////////////////////////////////////////////////////////////////////////////
 120 //  Inlined member functions
 121 //////////////////////////////////////////////////////////////////////////////
 122 inline void * BURS_ItemSet::operator new(size_t, Mem& mem, int k)
 123 {  BURS_ItemSet * set =
 124       (BURS_ItemSet*)mem.m_alloc
 125           (sizeof(BURS_ItemSet) + (k-1)* sizeof(BURS_Item));
 126    set->n        = k;
 127    set->clear();
 128    return set;
 129 }
 130
 131 //////////////////////////////////////////////////////////////////////////////
 132 //  Hashing function for an item set.
 133 //////////////////////////////////////////////////////////////////////////////
 134 inline unsigned int hash(register const BURS_ItemSet * set)
 135 {  register unsigned int h = 23;
 136    for (register int i = set->n - 1; i > 0; i--)
 137       h += h * 16 + set->items[i].cost;
 138    return h;
 139 }
 140
 141 //////////////////////////////////////////////////////////////////////////////
 142 //  Equality between two item sets.
 143 //////////////////////////////////////////////////////////////////////////////
 144 inline Bool equal(register const BURS_ItemSet * a,
 145                   register const BURS_ItemSet * b)
 146 {  for (register int i = 1; i < a->n; i++)
 147       if (a->items[i].cost != b->items[i].cost)
 148          return false;
 149    return true;
 150         //|| a->items[i].rule != b->items[i].rule)
 151 }
 152
 153 //////////////////////////////////////////////////////////////////////////////
 154 //  Method to normalise the cost of a state.
 155 //////////////////////////////////////////////////////////////////////////////
 156 inline void BURS_ItemSet::normalise_costs()
 157 {
 158    ///////////////////////////////////////////////////////////////////////////
 159    // Find the minimal cost of the item set
 160    ///////////////////////////////////////////////////////////////////////////
 161    Cost min_cost = infinite_cost;
 162    for (int i = n - 1; i > 0; i--)
 163       if (items[i].cost < min_cost) min_cost = items[i].cost;
 164
 165    ///////////////////////////////////////////////////////////////////////////
 166    // Subtract the minimal cost from the rest
 167    ///////////////////////////////////////////////////////////////////////////
 168    for (int j = n - 1; j > 0; j--)
 169       if (items[j].cost != infinite_cost)
 170          items[j].cost -= min_cost;
 171 }
 172
 173 #endif