include/AD/rete/gen_rete.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 generalized_rete_network_h
  26 #define generalized_rete_network_h
  27
  28 #include <AD/rete/fact.h>   // database facts
  29 #include <AD/memory/mem.h>  // memory manager
  30
  31 //////////////////////////////////////////////////////////////////////////////
  32 //
  33 //  Class ReteInterp is an interpreter for a generalized Rete network.
  34 //
  35 //////////////////////////////////////////////////////////////////////////////
  36 class ReteInterp {
  37
  38    ReteInterp      (const ReteInterp&);     // no copy constructor
  39    void operator = (const ReteInterp&);     // no assignment
  40
  41 public:
  42
  43    ///////////////////////////////////////////////////////////////////////////
  44    //  Import types
  45    ///////////////////////////////////////////////////////////////////////////
  46    typedef Fact::Age    Age;       // timestamp
  47    typedef Fact::RuleId RuleId;    // rule id
  48    typedef int          NodeId;    // node number;
  49    typedef int          JoinId;    // join id
  50
  51    ///////////////////////////////////////////////////////////////////////////
  52    //  Definition of the network nodes.
  53    ///////////////////////////////////////////////////////////////////////////
  54    struct Node {
  55       enum Kind {
  56          ENTRY,      // network entry node
  57          HASH_ENTRY, // network entry node for hashed key entry
  58          SORT_ENTRY, // network entry node for sorted key entry
  59          FORK,       // fork node
  60          JOIN,       // linear join node
  61          HASH_JOIN,  // hashed join node
  62          SORT_JOIN,  // sorted key join node
  63          NOT,        // negation node
  64          HASH_NOT,   // hashed negation node
  65          SORT_NOT,   // sorted key negation node
  66          BOT         // bottom node
  67       } kind;
  68       NodeId left_input;   // left input node
  69       NodeId right_input;  // right input node
  70       NodeId child;        // child node
  71       JoinId join;         // join number(if any)
  72       short  left_arity;   // left arity
  73       short  arity;        // arity of token
  74    };
  75
  76 protected:
  77
  78    ///////////////////////////////////////////////////////////////////////////
  79    //  Internal members.
  80    ///////////////////////////////////////////////////////////////////////////
  81    Mem&             mem;              // internal memory manager.
  82    class AlphaMem * alpha_mem;        // alpha memory indexed by node number.
  83    class BetaMem  * beta_mem;         // beta memory indexed by node number.
  84    const Node *     network;          // the rete network in table format.
  85    const NodeId *   chain_table;      // tables of chains
  86    int              number_of_nodes;  // number of nodes in the network.
  87    int              number_of_facts;  // number of facts in the database.
  88    int              max_token_arity;  // maximum arity of tokens.
  89
  90    ///////////////////////////////////////////////////////////////////////////
  91    //  Methods for propagating tokens within the node.
  92    ///////////////////////////////////////////////////////////////////////////
  93    void insert_right (NodeId, Fact *);
  94    void insert_left  (NodeId, Fact **);
  95    void remove_right (NodeId, Fact *);
  96    void remove_left  (NodeId, Fact **);
  97
  98 public:
  99
 100    ///////////////////////////////////////////////////////////////////////////
 101    //  Constructor and destructor
 102    ///////////////////////////////////////////////////////////////////////////
 103             ReteInterp(int N, const Node net[], const NodeId chain[]);
 104    virtual ~ReteInterp();
 105
 106    ///////////////////////////////////////////////////////////////////////////
 107    //  Method to return the name of the rete network class.
 108    ///////////////////////////////////////////////////////////////////////////
 109    virtual const char * name_of() const;
 110
 111    ///////////////////////////////////////////////////////////////////////////
 112    //  Methods to enter/remove tokens from the conflict set.
 113    ///////////////////////////////////////////////////////////////////////////
 114    virtual void activate   (RuleId, int, Fact * []);
 115    virtual void deactivate (RuleId, int, Fact * []);
 116
 117    ///////////////////////////////////////////////////////////////////////////
 118    //  Methods to assert and retract facts from the network.
 119    ///////////////////////////////////////////////////////////////////////////
 120    virtual void clear        ();
 121    virtual void assert_fact  (Fact *);
 122    virtual void retract_fact (Fact *);
 123    inline ReteInterp& operator << (Fact * f) { assert_fact(f); return *this; }
 124    inline ReteInterp& operator =  (Fact * f) { assert_fact(f); return *this; }
 125    inline ReteInterp& operator ,  (Fact * f) { assert_fact(f); return *this; }
 126
 127    ///////////////////////////////////////////////////////////////////////////
 128    //  Methods for driving the inference.
 129    ///////////////////////////////////////////////////////////////////////////
 130    virtual Bool is_stable() = 0; // is the conflict set empty?
 131    virtual void fire     ();     // fire one rule
 132    virtual void infer    ();     // fire all rules
 133
 134    ///////////////////////////////////////////////////////////////////////////
 135    //  The following methods can be (re)defined by the clients.
 136    ///////////////////////////////////////////////////////////////////////////
 137 protected:
 138    virtual void alpha_test        ( Fact * ) = 0;
 139    virtual int  beta_test         ( JoinId, Fact * [] ) = 0;
 140    virtual void action            ( RuleId, Fact * [] ) = 0;
 141    virtual void initialise_axioms () = 0;
 142 };
 143
 144 #endif