#ifndef RDF_INDEX_H_
#define RDF_INDEX_H_
#include "rdf_rule_core.h"
#include "rdf_rule_cback.h"
namespace rdf {
/////////////////////////////////////////////////////////////////////////////////////////
// class index_triple
//
/////////////////////////////////////////////////////////////////////////////////////////
class index_triple {
public:
inline index_triple():
m_subject(0),
m_predicate(0),
m_object(0) {};
inline index_triple(index_type s, index_type p,index_type o):
m_subject(s),
m_predicate(p),
m_object(o) {};
inline index_triple(index_type const* t3):
m_subject(t3[0]),
m_predicate(t3[1]),
m_object(t3[2]) {};
inline index_triple(index_triple const& rhs):
m_subject(rhs.m_subject),
m_predicate(rhs.m_predicate),
m_object(rhs.m_object) {};
inline index_triple& operator=(index_triple const& rhs)
{
m_subject = rhs.m_subject;
m_predicate = rhs.m_predicate;
m_object = rhs.m_object;
return *this;
};
inline index_type get_subject() const{return m_subject;};
inline index_type get_predicate() const{return m_predicate;};
inline index_type get_object() const{return m_object;};
inline index_type * as_array(index_type * t3)const{
t3[0] = m_subject;
t3[1] = m_predicate;
t3[2] = m_object;
return t3;
};
private:
friend std::ostream& operator<<(std::ostream& out, index_triple const& t);
friend struct eq_index_triple;
friend struct hash_index_triple;
index_type m_subject;
index_type m_predicate;
index_type m_object;
};
inline std::ostream& operator<<(std::ostream& out, index_triple const& t)
{
out << "(" << to_string(t.m_subject) << ", "
<< to_string(t.m_predicate) << ", "
<< to_string(t.m_object) << ")";
return out;
};
struct eq_index_triple
{
inline bool operator()(index_triple const& lhs, index_triple const& rhs)const
{
return lhs.m_subject==rhs.m_subject && lhs.m_predicate==rhs.m_predicate && lhs.m_object==rhs.m_object;
};
inline bool operator()(index_type * lhs, index_type * rhs)const
{
return lhs[0]==rhs[0] && lhs[1]==rhs[1] && lhs[2]==rhs[2];
};
};
struct hash_index_triple
{
inline std::size_t operator()(index_triple const& triple)const
{
return std::size_t(triple.m_subject) + std::size_t(triple.m_predicate) + std::size_t(triple.m_object);
};
inline std::size_t operator()(index_type * t3)const
{
return std::size_t(t3[0]) + std::size_t(t3[1]) + std::size_t(t3[2]);
};
};
namespace internal {
/////////////////////////////////////////////////////////////////////////////////////////
// class wc_type
//
/////////////////////////////////////////////////////////////////////////////////////////
class wc_type {
public:
wc_type(index_type w_index, unsigned int const count=1):
m_index(w_index),
m_ref_count(count)
{};
index_type
get_index()const
{
return m_index;
};
unsigned int
get_ref_count()const
{
return m_ref_count;
};
unsigned int
add_ref_count(unsigned int count=1)const
{
m_ref_count+=count; return m_ref_count;
};
unsigned int
del_ref_count(unsigned int count=1) const
{
// //*
// if(0 == m_ref_count) std::cout << "+++++++ ERROR +++++++ SUBSTRACTING FROM 0!! in del_ref_count\n";
m_ref_count -= count;
return m_ref_count;
};
unsigned int
reset_ref_count(unsigned int count=1)const
{
m_ref_count=count; return m_ref_count;
};
private:
friend struct hash_wc;
friend struct eq_wc;
index_type m_index;
mutable unsigned int m_ref_count;
};
struct hash_wc
{
inline std::size_t operator()(wc_type const& wc)const{return std::size_t(wc.m_index);};
};
struct eq_wc
{
inline bool operator()(wc_type const& lhs, wc_type const& rhs)const{return lhs.m_index == rhs.m_index;};
};
typedef std::tr1::unordered_set<wc_type, hash_wc, eq_wc> w_set_type;
typedef std::tr1::unordered_map<index_type , w_set_type> v_map_type;
typedef std::tr1::unordered_map<index_type , v_map_type> u_map_type;
/////////////////////////////////////////////////////////////////////////////////////////
// class w_itor_set
//
/////////////////////////////////////////////////////////////////////////////////////////
class w_itor_set {
public:
inline w_itor_set():
m_itor(),
m_end()
{};
inline w_itor_set(w_set_type::const_iterator const& itor_, w_set_type::const_iterator const& end_):
m_itor(itor_),
m_end(end_)
{};
inline w_itor_set(const w_itor_set& rhs):
m_itor(rhs.m_itor),
m_end(rhs.m_end)
{};
inline w_itor_set&
operator=(const w_itor_set& rhs)
{
m_itor = rhs.m_itor; m_end = rhs.m_end;
return *this;
};
inline void
set_itor(w_set_type::const_iterator const& itor, w_set_type::const_iterator const& end)
{
m_itor=itor;
m_end=end;
};
inline index_type
get_index()const
{
return m_itor->get_index();
};
inline bool
is_end()const
{
return m_itor == m_end;
};
inline bool
next()
{
++m_itor;
return !is_end();
};
private:
w_set_type::const_iterator m_itor;
w_set_type::const_iterator m_end;
};
/////////////////////////////////////////////////////////////////////////////////////////
// class itor_map
//
/////////////////////////////////////////////////////////////////////////////////////////
template<class RItor> // RItor is either v_map_type or u_map_type
class itor_map {
public:
inline itor_map():
m_v(0),
m_itor(),
m_end(),
m_is_end(true)
{};
inline itor_map(index_type v_, typename RItor::const_iterator const& itor_, typename RItor::const_iterator const& end_):
m_v(v_),
m_itor(itor_),
m_end(end_),
m_is_end(false)
{
if(m_itor!=m_end) m_v = m_itor->first; else if(m_v==0) m_is_end = true;
};
inline itor_map(const itor_map& rhs):
m_v(rhs.m_v),
m_itor(rhs.m_itor),
m_end(rhs.m_end),
m_is_end(rhs.m_is_end){};
inline itor_map&
operator=(const itor_map& rhs)
{
m_v = rhs.m_v; m_itor = rhs.m_itor; m_end = rhs.m_end; m_is_end = rhs.m_is_end;
return *this;
};
inline void
set_itor(typename RItor::const_iterator const& itor, typename RItor::const_iterator const& end)
{
m_itor=itor; m_end=end;
};
inline index_type
get_index()const
{
return m_v;
};
inline bool
is_end()const
{
return m_is_end;
};
template<class W> // W is either itor_map<v_map_type> or w_itor_set
inline bool next(W& w_itor)
{
if(m_itor != m_end) ++m_itor;
if(m_itor == m_end) {
m_is_end = true;
m_v = 0;
return false;
}
this->set_itor_position(w_itor);
return true;
};
template<class W> // W is either itor_map<v_map_type> or w_itor_set
inline void set_itor_position(W& w_itor)
{
if(m_itor != m_end) {
m_is_end = false;
m_v = m_itor->first;
w_itor.set_itor(m_itor->second.begin(), m_itor->second.end());
}
};
private:
index_type m_v;
typename RItor::const_iterator m_itor;
typename RItor::const_iterator m_end;
bool m_is_end;
};
/////////////////////////////////////////////////////////////////////////////////////////
// class index_graph_iterator
//
/////////////////////////////////////////////////////////////////////////////////////////
class index_graph_iterator {
public:
typedef index_triple value_type;
inline index_graph_iterator(itor_map<u_map_type> const& u_itor_, itor_map<v_map_type> const& v_itor_, w_itor_set const& w_itor_):
m_u_itor(u_itor_),
m_v_itor(v_itor_),
m_w_itor(w_itor_)
{};
inline index_graph_iterator():
m_u_itor(),
m_v_itor(),
m_w_itor()
{};
inline index_graph_iterator(index_graph_iterator const& rhs):
m_u_itor(rhs.m_u_itor),
m_v_itor(rhs.m_v_itor),
m_w_itor(rhs.m_w_itor)
{};
inline index_graph_iterator&
operator=(index_graph_iterator const& rhs)
{
m_u_itor = rhs.m_u_itor; m_v_itor = rhs.m_v_itor; m_w_itor = rhs.m_w_itor;
return *this;
};
inline bool
is_end()const
{
return m_u_itor.is_end() and m_v_itor.is_end() and m_w_itor.is_end();
};
inline bool
next() {
if(is_end()) return false;
if(!m_w_itor.next()) {
if(!m_v_itor.next(m_w_itor)) {
if(m_u_itor.next(m_v_itor)) {
m_v_itor.set_itor_position(m_w_itor);
}
}
}
return !is_end();
};
// function member not used by rdf_graph since lookup_spo must be called
// to unwind the indexes.
inline value_type
get_triple()const
{
return value_type(m_u_itor.get_index(), m_v_itor.get_index(), m_w_itor.get_index());
};
private:
friend void lookup_spo(char const m_lookup, index_type &s, index_type &p, index_type &o, index_graph_iterator const& m_index_itor);
itor_map<u_map_type> m_u_itor;
itor_map<v_map_type> m_v_itor;
w_itor_set m_w_itor;
};
/////////////////////////////////////////////////////////////////////////////////////////
// lookup_spo
//
/////////////////////////////////////////////////////////////////////////////////////////
inline void lookup_spo(char const m_lookup, index_type &s, index_type &p, index_type &o, index_graph_iterator const& m_index_itor)
{
if(m_lookup == 's') { // case 'spo' <==> "uvw'
s = m_index_itor.m_u_itor.get_index();
p = m_index_itor.m_v_itor.get_index();
o = m_index_itor.m_w_itor.get_index();
} else if(m_lookup == 'p') { // case 'pos' <==> "uvw'
s = m_index_itor.m_w_itor.get_index();
p = m_index_itor.m_u_itor.get_index();
o = m_index_itor.m_v_itor.get_index();
} else { // case 'osp' <==> "uvw'
s = m_index_itor.m_v_itor.get_index();
p = m_index_itor.m_w_itor.get_index();
o = m_index_itor.m_u_itor.get_index();
}
};
/////////////////////////////////////////////////////////////////////////////////////////
// class index_graph
//
/////////////////////////////////////////////////////////////////////////////////////////
class index_graph {
public:
typedef index_graph_iterator iterator;
typedef w_set_type::iterator w_itor_type;
typedef v_map_type::iterator v_itor_type;
typedef u_map_type::iterator u_itor_type;
typedef w_set_type::const_iterator w_const_itor_type;
typedef v_map_type::const_iterator v_const_itor_type;
typedef u_map_type::const_iterator u_const_itor_type;
inline index_graph(unsigned int size=20):
m_initial_size(size),
m_index(m_initial_size),
m_v_end(),
m_w_end(),
m_session_p(NULL),
m_index_triple_cback_mgr_p(NULL) {};
inline void set_initial_size(unsigned int size) {m_initial_size = size;};
/*
* return true if (u, v, w) exist, false otherwise.
*/
inline bool
contains(index_type u, index_type v, index_type w) const
{
u_const_itor_type utor = m_index.find(u);
if(utor == m_index.end()) return false;
v_const_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) return false;
w_set_type::const_iterator wtor = vtor->second.find(wc_type(w));
if(wtor == vtor->second.end()) return false;
return true;
};
/*
* return true if (u, v, *) exist, false otherwise.
*/
inline bool
contains(index_type u, index_type v) const
{
u_const_itor_type utor = m_index.find(u);
if(utor == m_index.end()) return false;
v_const_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) return false;
return true;
};
iterator
find() const;
inline iterator
find_all()const
{
return find();
};
iterator
find(index_type u) const;
iterator
find(index_type u, index_type v) const;
// returns the reference count in the inferred graph.
// used by rule_term to determine if an inferred triple will
// be removed as result of retract call.
inline unsigned int
get_ref_count(index_type u, index_type v, index_type w)const
{
u_const_itor_type utor = m_index.find(u);
if(utor == m_index.end()) return 0;
v_const_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) return 0;
w_set_type::const_iterator wtor = vtor->second.find(wc_type(w));
if(wtor == vtor->second.end()) return 0;
return wtor->get_ref_count();
};
// increase the reference count if type wc_type
inline bool insert(index_type u, index_type v, index_type w, bool notify_listners=true)
{
u_itor_type utor = m_index.find(u);
if(utor == m_index.end()) {
utor = m_index.insert(u_map_type::value_type(u, v_map_type(m_initial_size))).first;
}
v_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) {
vtor = utor->second.insert(v_map_type::value_type(v, w_set_type(m_initial_size))).first;
}
std::pair<w_set_type::iterator, bool> pair = vtor->second.insert(wc_type(w));
if(!pair.second) pair.first->add_ref_count();
// apply the call back functors
if(notify_listners and m_index_triple_cback_mgr_p and pair.second) m_index_triple_cback_mgr_p->triple_inserted(m_session_p, u, v, w);
return pair.second;
};
// delete the triple regardless if reference count is in use
inline unsigned int erase (index_type u, index_type v, index_type w)
{
u_itor_type utor = m_index.find(u);
if(utor == m_index.end()) return 0;
v_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) return 0;
unsigned int count = vtor->second.erase(wc_type(w));
if(vtor->second.empty()) {
utor->second.erase(v);
if(utor->second.empty()) {
m_index.erase(u);
}
}
// apply the call back functors
if(m_index_triple_cback_mgr_p and count>0) m_index_triple_cback_mgr_p->triple_deleted(m_session_p, u, v, w);
return count;
};
// reduce reference count, if in use, delete if ref count is zero
inline unsigned int retract(index_type u, index_type v, index_type w)
{
u_itor_type utor = m_index.find(u);
if(utor == m_index.end()) return 0;
v_itor_type vtor = utor->second.find(v);
if(vtor == utor->second.end()) return 0;
unsigned int count = 0;
w_set_type::iterator wtor = vtor->second.find(wc_type(w));
if(wtor == vtor->second.end()) return 0;
if(wtor->del_ref_count() == 0) {
vtor->second.erase(wtor);
if(vtor->second.empty()) {
utor->second.erase(v);
if(utor->second.empty()) {
m_index.erase(u);
}
}
count = 1;
}
// apply the call back functors
if(m_index_triple_cback_mgr_p and count>0) m_index_triple_cback_mgr_p->triple_deleted(m_session_p, u, v, w);
return count;
};
inline void register_call_back_manager(rule::rule_session * session_p, index_triple_cback_mgr const* callback_mgr_p)
{
m_session_p = session_p;
m_index_triple_cback_mgr_p = callback_mgr_p;
};
inline void unregister_call_back_manager()
{
m_session_p = NULL;
m_index_triple_cback_mgr_p = NULL;
};
private:
unsigned int m_initial_size;
u_map_type m_index;
// have empty iterators
v_const_itor_type m_v_end;
w_const_itor_type m_w_end;
// callback functors manager
rule::rule_session * m_session_p;
index_triple_cback_mgr const* m_index_triple_cback_mgr_p;
};
}; /*namespace internal */
}; /*namespace rdf */
#endif /*RDF_INDEX_H_*/
