#ifndef RULE_GRAPH_H_
#define RULE_GRAPH_H_
#include "rdf_rule_core.h"
#include "rdf_graph.h"
namespace rule {
class rule_session;
namespace internal {
class rule_term_base;
using rdf::index_type;
using rdf::var;
inline std::string to_string(index_type i){return rdf::to_string(i);};
inline std::string to_string(std::string const& v){return v;};
/////////////////////////////////////////////////////////////////////////////////////////
// class relation_row_map
//
// Complies to property_map concept
/////////////////////////////////////////////////////////////////////////////////////////
class relation_row_map
{
typedef std::vector<index_type> data_type;
public:
typedef data_type::value_type value_type;
typedef data_type::size_type size_type;
typedef data_type::iterator iterator;
typedef data_type::const_iterator const_iterator;
typedef data_type::reference reference;
typedef data_type::const_reference const_reference;
typedef boost::lvalue_property_map_tag category;
///////////////////////////////////////////////////////////////////
// status for the relation_row:
//
// inserted: row added and must apply consequent terms
// deleted: row removed and must retract inferred triples
// processed: either triples processed or action cancelled by
// a combination of insert/delete and vice versa
///////////////////////////////////////////////////////////////////
enum row_status_type {inserted, deleted, processed};
inline relation_row_map():
m_data(),
m_hash(0),
m_row_status(processed)
{};
inline relation_row_map(data_type::size_type size):
m_data(size),
m_hash(0),
m_row_status(processed)
{};
inline reference operator[](size_type const key)
{
if(key >= m_data.size()) throw rdf::rdf_exception(0, "reference operator[] Ah-ha m_data is not properly initialize");
return m_data[key];
};
inline const_reference operator[](size_type const key)const
{
if(key >= m_data.size()) throw rdf::rdf_exception(0, "const_reference operator[] Ah-ha m_data is not properly initialize");
return m_data[key];
};
inline void put(size_type const key, value_type const& value)
{
if(key >= m_data.size()) throw rdf::rdf_exception(0, "put: Ah-ha m_data is not properly initialize");
m_data[key] = value;
};
inline value_type get(size_type const key)const
{
if(key >= m_data.size()) throw rdf::rdf_exception(0, "get: Ah-ha m_data is not properly initialize");
return m_data[key];
};
inline iterator begin(){return m_data.begin();};
inline iterator end() {return m_data.end();};
inline const_iterator begin()const{return m_data.begin();};
inline const_iterator end() const{return m_data.end();};
inline size_type size(){return m_data.size();};
std::string to_string()const;
std::string to_string(rule_term_base const&)const;
inline std::size_t get_hash()const{return m_hash;};
inline void set_hash(std::size_t hash){ m_hash = hash;};
inline row_status_type get_row_status()const{return m_row_status;};
inline void set_row_status(row_status_type status){m_row_status = status;};
inline char const* get_row_status_str()const
{
switch(m_row_status) {
case inserted: return "inserted";
case deleted: return "deleted";
case processed: return "processed";
default: return "unknown (ERROR)";
};
};
inline bool is_inserted() const{return inserted == m_row_status;};
inline bool is_deleted() const{return deleted == m_row_status;};
inline bool is_processed() const{return processed == m_row_status;};
inline void set_inserted() {m_row_status = inserted;};
inline void set_deleted() {m_row_status = deleted;};
inline void set_processed() {m_row_status = processed;};
private:
data_type m_data;
std::size_t m_hash;
row_status_type m_row_status;
};
inline void put(relation_row_map &row_map, relation_row_map::size_type key, relation_row_map::value_type const& value) {row_map.put(key, value);};
inline relation_row_map::value_type get(relation_row_map const& row_map, relation_row_map::size_type key) {return row_map.get(key);};
class beta_relation_const_iterator_type;
typedef std::tr1::shared_ptr<relation_row_map> relation_row_ptr_type;
struct eq_row
{
inline bool operator()(relation_row_ptr_type const& lhs, relation_row_ptr_type const& rhs)const
{
if(lhs->size() < rhs->size()) return true;
if(lhs->size() > rhs->size()) return false;
relation_row_map::iterator lhs_itor = lhs->begin();
relation_row_map::iterator rhs_itor = rhs->begin();
relation_row_map::iterator lhs_end = lhs->end();
while(lhs_itor != lhs_end) {
if(*lhs_itor < *rhs_itor) {return false;};
if(*lhs_itor > *rhs_itor) {return false;};
++lhs_itor;
++rhs_itor;
};
return true;
};
};
struct hash_row
{
inline std::size_t operator()(relation_row_ptr_type const& row_p)const
{
return row_p->get_hash();
};
};
/////////////////////////////////////////////////////////////////////////////////////////
// class beta_relation
//
// Container of joint rows at each rule term, known as beta-nodes in rete network.
//
// Hold a set of all active rows in the relation table (m_unique_row_set)
//
// Hold a slist of rows that are queued for processing - inserted and deleted rows.
//
// - non-consequent terms (in rule_term and rule_propagation) will iterate through the
// slist using unified iterator (i.e., unified with unique_row_set) since they may need
// to iterate through all rows not only the queued items.
//
// Hold an index as a multi-map to index rows on a specific index_type.
//
// The unique row contains all rows being processed (deleted and inserted) and inserted processed rows.
// Deleted rows are removed onced processed.
// Iterator may not be safe if rows are added while iterating.
// The lists are slist to minimize space and ensure that insertions does not invalidate iterator - used a queux
/////////////////////////////////////////////////////////////////////////////////////////
class beta_relation
{
typedef relation_row_ptr_type row_p_t;
typedef std::tr1::unordered_set<row_p_t, hash_row, eq_row> row_set_type;
typedef __gnu_cxx::slist<row_p_t> row_list_type;
typedef std::tr1::unordered_multimap<index_type, row_p_t> lookup_map_type;
public:
static const unsigned int NO_LOOKUP_INDEX;
typedef row_list_type::size_type size_type;
typedef row_list_type::const_iterator list_const_iterator_t;
typedef row_set_type::const_iterator set_const_iterator_t;
typedef lookup_map_type::const_iterator map_const_iterator_t;
typedef beta_relation_const_iterator_type const_iterator;
typedef relation_row_map::const_iterator relation_row_const_iterator;
typedef std::pair<relation_row_const_iterator, relation_row_const_iterator> relation_row_pair_const_iterator;
inline beta_relation(unsigned int index_map_size, unsigned int p, rule_vertex v, unsigned int lookup_map_size=10, unsigned int unique_row_set_size=50):
m_index_map_size(index_map_size),
m_is_consequent_term(false),
m_unique_row_set(unique_row_set_size),
m_propagation_qx_rows(),
m_lookup_index(NO_LOOKUP_INDEX),
m_lookup_map(lookup_map_size),
m_has_fired(false),
m_priority(p),
m_rule_vertex(v)
{};
// used by rule_propagator only
inline bool
has_fired()const
{
return m_has_fired;
};
inline void
set_has_fired(bool b)
{
m_has_fired = b;
};
inline void
set_lookup_index(unsigned int index_)
{
m_lookup_index = index_;
};
inline bool
is_consequent_term()const
{
return m_is_consequent_term;
};
inline void
set_is_consequent_term(bool b)
{
m_is_consequent_term = b;
};
// used for query_rules to reset the state between query execution within same rule_session.
inline void
clear()
{
m_unique_row_set.clear();
m_propagation_qx_rows.clear();
m_has_fired = false;
};
inline bool
empty()const
{
return m_unique_row_set.empty();
};
inline unsigned int
get_row_count()const
{
return m_unique_row_set.size();
};
///////////////////////////////////////////////////////
// queue management methods for body terms used by rule_propagation
//
// Method used percolating down in the rete network for body terms.
///////////////////////////////////////////////////////////
inline void
reset_propagation_qx()
{
m_propagation_qx_rows.clear();
};
inline bool
is_propagation_qx_empty()const
{
return m_propagation_qx_rows.empty();
};
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////
// row management methods for body and consequent terms
//
// method used when adding rows in beta_relation:
//
// Body terms: used when percolating down in the rete-network by
// rule_terms. Inserted and deleted queux are not accessed when
// a beta_relation when rows are added/deleted.
// Used by rule_term.
//
// Consequent term: also used when percolating down the rete-network,
// however, rule_session may be poping the queux while processing
// consequent terms and a call back is notified which initiate the
// propagation through the rete-network and add a row here.
///////////////////////////////////////////////////////////
inline relation_row_ptr_type create_relation_row()const
{
return relation_row_ptr_type(new relation_row_map(m_index_map_size));
};
inline void
insert_lookup_index(relation_row_ptr_type const& row_p)
{
if(m_lookup_index < NO_LOOKUP_INDEX) {
index_type key = (*row_p)[m_lookup_index];
m_lookup_map.insert(lookup_map_type::value_type(key, row_p));
}
};
inline void
remove_lookup_index(relation_row_ptr_type const& row_p)
{
// update lookup index
if(m_lookup_index < NO_LOOKUP_INDEX) {
eq_row eq_op;
lookup_map_type::iterator map_itor;
lookup_map_type::iterator map_end;
index_type key = (*row_p)[m_lookup_index];
boost::tie(map_itor, map_end) = m_lookup_map.equal_range(key);
while(map_itor!=map_end) {
if(eq_op(row_p, map_itor->second)) {
m_lookup_map.erase(map_itor);
map_itor = map_end;
} else ++map_itor;
}
}
};
///////////////////////////////////////////////////////
// beta_relation::insert_row
//
// defined in rule_session.h due to dependency on rule_session and to ensure inlining.
///////////////////////////////////////////////////////////
unsigned int
insert_row(rule_session * rule_session_p, relation_row_ptr_type const& row_p, std::size_t hash_code);
inline void
erase_deleted_row(relation_row_ptr_type const& row_p)
{
m_unique_row_set.erase(row_p);
};
///////////////////////////////////////////////////////
// beta_relation::delete_row
//
// defined in rule_session.h due to dependency on rule_session and to ensure inlining.
///////////////////////////////////////////////////////////
unsigned int
delete_row(rule_session * rule_session_p, relation_row_ptr_type const& row_p, std::size_t hash_code);
///////////////////////////////////////////////////////////
// iterator on relation_row
inline relation_row_pair_const_iterator
get_relation_row_const_iterator(relation_row_map const& row)const
{
return relation_row_pair_const_iterator(row.begin(), row.end());
};
inline const_iterator
propagation_qx_rows_iterator(bool all_rows)const;
inline const_iterator
beta_relation_iterator_all()const;
inline const_iterator
beta_relation_iterator (
relation_row_map::size_type idx0,
relation_row_map::size_type idx1,
relation_row_map::size_type idx2,
index_type const* t3)const;
private:
friend class beta_relation_const_iterator_type;
inline set_const_iterator_t all_rows_begin()const{return m_unique_row_set.begin();};
inline set_const_iterator_t all_rows_end() const{return m_unique_row_set.end();};
inline list_const_iterator_t propagation_qx_begin()const{return m_propagation_qx_rows.begin();};
inline list_const_iterator_t propagation_qx_end() const{return m_propagation_qx_rows.end();};
unsigned int m_index_map_size;
bool m_is_consequent_term;
row_set_type m_unique_row_set;
row_list_type m_propagation_qx_rows;
unsigned int m_lookup_index;
lookup_map_type m_lookup_map;
bool m_has_fired; // this is to indicate if the rule term has consumed asserted triples
unsigned int m_priority;
rule_vertex m_rule_vertex;
};
/////////////////////////////////////////////////////////////////////////////////////////
// class beta_relation_const_iterator_type
//
// single pass iterator, visit element nelm in reverse
/////////////////////////////////////////////////////////////////////////////////////////
class beta_relation_const_iterator_type {
typedef beta_relation::set_const_iterator_t set_const_iterator_t;
typedef beta_relation::list_const_iterator_t list_const_iterator_t;
typedef beta_relation::map_const_iterator_t map_const_iterator_t;
enum mode {list_mode, multimap_mode, set_mode};
public:
inline beta_relation_const_iterator_type(
beta_relation const& beta_relation,
list_const_iterator_t const& itor_,
list_const_iterator_t const& end_
):
m_mode(list_mode),
m_beta_relation(beta_relation),
m_list_itor(itor_),
m_list_end(end_),
m_map_itor(),
m_map_end(),
m_set_itor(),
m_set_end()
{};
inline beta_relation_const_iterator_type(
beta_relation const& beta_relation,
map_const_iterator_t const& itor_,
map_const_iterator_t const& end_
):
m_mode(multimap_mode),
m_beta_relation(beta_relation),
m_list_itor(),
m_list_end(),
m_map_itor(itor_),
m_map_end(end_),
m_set_itor(),
m_set_end()
{};
inline beta_relation_const_iterator_type(
beta_relation const& beta_relation,
set_const_iterator_t const& itor_,
set_const_iterator_t const& end_
):
m_mode(set_mode),
m_beta_relation(beta_relation),
m_list_itor(),
m_list_end(),
m_map_itor(),
m_map_end(),
m_set_itor(itor_),
m_set_end(end_)
{
// position the itor to the first non deleted item
while(m_set_itor!=m_set_end and (*m_set_itor)->is_deleted()) ++m_set_itor;
};
inline bool is_end()const
{
switch(m_mode) {
case list_mode: return m_list_itor == m_list_end;
case multimap_mode: return m_map_itor == m_map_end;
case set_mode: return m_set_itor == m_set_end;
default: return true;
};
};
inline bool next()
{
switch(m_mode) {
case list_mode: ++m_list_itor; break;
case multimap_mode: ++m_map_itor; break;
case set_mode:
++m_set_itor;
while(m_set_itor!=m_set_end and (*m_set_itor)->is_deleted()) ++m_set_itor;
break;
};
return is_end();
};
inline relation_row_ptr_type const& get_relation_row_ptr()const
{
switch(m_mode) {
case list_mode: return *m_list_itor;
case multimap_mode: return m_map_itor->second;
case set_mode: return *m_set_itor;
default: throw rdf::rdf_exception(rdf::unexpected_logic_error, "beta_relation_const_iterator_type::get_relation_row: invalid iterator mode!");
};
};
inline relation_row_map const& get_relation_row()const{return *get_relation_row_ptr();};
inline beta_relation::relation_row_pair_const_iterator get_relation_row_const_iterator()const
{
return m_beta_relation.get_relation_row_const_iterator(get_relation_row());
};
private:
mode m_mode;
beta_relation const& m_beta_relation;
list_const_iterator_t m_list_itor;
list_const_iterator_t m_list_end;
map_const_iterator_t m_map_itor;
map_const_iterator_t m_map_end;
set_const_iterator_t m_set_itor;
set_const_iterator_t m_set_end;
};
/////////////////////////////////////////////////////////////////////////////////////////
// beta_relation::propagation_qx_rows_iterator
//
/////////////////////////////////////////////////////////////////////////////////////////
inline beta_relation::const_iterator
beta_relation::propagation_qx_rows_iterator(bool all_rows)const
{
if(all_rows) return beta_relation_iterator_all();
return beta_relation_const_iterator_type(*this, propagation_qx_begin(), propagation_qx_end());
};
/////////////////////////////////////////////////////////////////////////////////////////
// beta_relation::beta_relation_iterator_all
//
/////////////////////////////////////////////////////////////////////////////////////////
inline beta_relation::const_iterator
beta_relation::beta_relation_iterator_all()const
{
return beta_relation_const_iterator_type(*this, all_rows_begin(), all_rows_end());
};
/////////////////////////////////////////////////////////////////////////////////////////
// beta_relation::beta_relation_iterator
//
/////////////////////////////////////////////////////////////////////////////////////////
inline beta_relation::const_iterator
beta_relation::beta_relation_iterator (
relation_row_map::size_type idx0,
relation_row_map::size_type idx1,
relation_row_map::size_type idx2,
index_type const*triple)const
{
if(m_lookup_index == NO_LOOKUP_INDEX) return beta_relation_const_iterator_type(*this, all_rows_begin(), all_rows_end());
beta_relation::lookup_map_type::const_iterator itor;
beta_relation::lookup_map_type::const_iterator end;
if(idx0 == m_lookup_index) {
boost::tie(itor, end) = m_lookup_map.equal_range(triple[0]);
return beta_relation_const_iterator_type(*this, itor, end);
}
if(idx1 == m_lookup_index) {
boost::tie(itor, end) = m_lookup_map.equal_range(triple[1]);
return beta_relation_const_iterator_type(*this, itor, end);
}
if(idx2 == m_lookup_index) {
boost::tie(itor, end) = m_lookup_map.equal_range(triple[2]);
return beta_relation_const_iterator_type(*this, itor, end);
}
return beta_relation_const_iterator_type(*this, all_rows_begin(), all_rows_end());
};
struct F_expression;
struct F_join;
struct F_var;
inline std::string to_string(F_expression const& f);
/////////////////////////////////////////////////////////////////////////////////////////
// class F_cst
//
// Funtors for Fu, Fv, and Fw for parameter of template Term class
// case for a constant, such as the subject in triple: (s, ?p, ?o)
/////////////////////////////////////////////////////////////////////////////////////////
struct F_cst {
F_cst(index_type index_) :
m_index(index_){};
F_cst(rdf::resource const& r) :
m_index(r.get_index()){};
F_cst() :
m_index(0){};
F_cst(F_cst const& rhs) :
m_index(rhs.m_index){};
inline void set(index_type index_){m_index = index_;};
inline index_type get_cback_index()const{return m_index;};
inline index_type operator()(relation_row_map const& row)const{return m_index;};
// used in compute_inferred_triple
inline index_type operator()(rule_session *, relation_row_map const& row)const{return m_index;};
// used to determine if row produced u in rule_engine::expain_why.
// used by rule_term::merge_row to see if there is a match to newly added u.
inline bool operator()(rule_session *, relation_row_map const& row, index_type const u)const{return u == m_index;};
// used for explain_why - return true if F can match m_index of triple
inline bool is_match_possible(index_type const u)const{return u == m_index;};
inline bool check_for_match(rdf::index_type const u)const{return u == m_index;};
inline bool check_for_match(std::string const& s)const{return true;};
inline bool check_for_match(F_expression const& x)const{return rdf::internal::to_resource_base(m_index).is_literal();};
inline index_type get_match_item()const{return m_index;};
inline relation_row_map::size_type
get_lookup_index()const
{
return beta_relation::NO_LOOKUP_INDEX;
};
bool has_label(std::string const& label)const{return false;};
std::string get_label()const{return rdf::internal::to_resource_base(m_index).get_name();};
inline bool is_same_as(F_cst const& x)const{return m_index == x.m_index;};
inline bool is_same_as(F_join const& x)const{return false;};
inline bool is_same_as(F_var const& x)const{return false;};
inline bool is_same_as(F_expression const& x)const{return false;};
private:
index_type m_index;
};
inline std::string to_string(F_cst const& f){return f.get_label();};
/////////////////////////////////////////////////////////////////////////////////////////
// class F_join
//
// Funtors for Fu, Fv, and Fw for parameter of template Term class
// case for a joined value, such as the object in triples: (s, ?p2, ?o)(s, ?p, ?o)
/////////////////////////////////////////////////////////////////////////////////////////
struct F_join {
F_join(relation_row_map::size_type index_) :
m_index(index_){};
F_join() :
m_index(0){};
F_join(F_join const& rhs) :
m_index(rhs.m_index){};
void set(relation_row_map::size_type index_){m_index = index_;};
inline var get_cback_index()const{return var();};
inline index_type operator()(relation_row_map const& row)const{return row[m_index];};
// used in compute_inferred_triple
inline index_type operator()(rule_session *, relation_row_map const& row)const{return row[m_index];};
// used to determine if row produced u in rule_engine::expain_why.
// used by rule_term::merge_row to see if there is a match to newly added u.
inline bool operator()(rule_session *, relation_row_map const& row, index_type const u)const{return u == row[m_index];};
// used for explain_why - will match depending on row
inline bool is_match_possible(index_type const)const{return true;};
inline bool check_for_match(rdf::index_type const u)const{return true;};
inline bool check_for_match(std::string const& s)const{return true;};
inline bool check_for_match(F_expression const& x)const{return true;};
inline std::string get_match_item()const{return "join";};
inline relation_row_map::size_type get_lookup_index()const{return m_index;};
bool has_label(std::string const& label)const{return false;};
std::string get_label()const{return "join_"+boost::lexical_cast<std::string>(m_index);};
inline bool is_same_as(F_cst const& x)const{return false;};
inline bool is_same_as(F_join const& x)const{return m_index == x.m_index;};
inline bool is_same_as(F_var const& x)const{return false;};
inline bool is_same_as(F_expression const& x)const{return false;};
private:
relation_row_map::size_type m_index;
};
inline std::string to_string(F_join const& f){return f.get_label();};
/////////////////////////////////////////////////////////////////////////////////////////
// class F_var
//
// Funtors for Fu, Fv, and Fw for parameter of template Term class
// case for a variable, such as the object in triples: (s, ?p, ?o)
/////////////////////////////////////////////////////////////////////////////////////////
struct F_var {
F_var(char const* label):
m_label(label){};
F_var(std::string const& label):
m_label(label){};
F_var(F_var const& rhs):
m_label(rhs.m_label){};
inline var get_cback_index()const{return var();};
inline var operator()(relation_row_map const& row)const{return var();};
inline var operator()(rule_session *, relation_row_map const& row)const{return var();};
// used to determine if row produced u in rule_engine::expain_why.
// used by rule_term::merge_row to see if there is a match to newly added u.
inline bool operator()(rule_session *, relation_row_map const& row, index_type const u)const{return true;};
inline bool check_for_match(rdf::index_type const u)const{return true;};
inline bool check_for_match(std::string const& s)const{return true;};
inline bool check_for_match(F_expression const& x)const{return true;};
inline std::string get_match_item()const{return m_label;};
inline relation_row_map::size_type get_lookup_index()const{return beta_relation::NO_LOOKUP_INDEX;};
bool has_label(std::string const& label)const{return label == m_label;};
std::string const& get_label()const{return m_label;};
inline bool is_same_as(F_cst const& x)const{return false;};
inline bool is_same_as(F_join const& x)const{return false;};
inline bool is_same_as(F_var const& x)const{return m_label == x.m_label;};
inline bool is_same_as(F_expression const& x)const{return false;};
private:
std::string m_label;
};
inline std::string to_string(F_var const& f){return f.get_label();};
}; /* internal namespace */
}; /* rule namespace */
#endif /*RULE_GRAPH_H_*/
