buildfptree.hpp

Go to the documentation of this file.

#ifndef BUILDFPTREE_HPP_050413
#define BUILDFPTREE_HPP_050413

#include "common/linmap.cpp"
#include "common/allocators.hpp"

  // we must define it this way because of template circular references. :(
#define NONORDFP_CHILDMAP linmap


namespace bracz {
  
  class nullTreeAnn {
  public:
    inline void DINLINE initTree(item_t maxitem) {
    }
    
    inline void DINLINE onNewTreeNode(item_t curritem,counter_t /*count*/) {
    }

    nullTreeAnn() {
    }
  }; //class nullTreeAnn



/*
  Shows the interface which a build fp tree must comply to
*/
class AbstractBuildTree {
public:
  class nodeiter_t;
  class nodeptr_t;
  class node_t;

  class nodeptr_t {
  public:
    node_t * operator->();
    node_t & operator*();
  };

  class nodeiter_t {
  public:
    const std::pair<item_t,nodeptr_t> & operator*();
    const std::pair<item_t,nodeptr_t> * operator->();
    void operator++();
    bool operator==(const nodeiter_t &o);
    bool operator!=(const nodeiter_t &o);
  };


  class node_t {
  public:
    counter_t getCounter();
    void setCounter(counter_t c);
    nodeiter_t childrenBegin();
    nodeiter_t childrenEnd();
  };

  typedef node_t root_t;

  /* 
     example within:
     allocator
     root node
  */
  class buildtree_t {
  public:
    nodeptr_t getRoot();
  };

  /*root_t *&root,U& nodesperitem, BUILDTREEALLOC &allocator,*/
   void initBuildTree(buildtree_t &tree, item_t maxitem);
  
  /*
    CALLBACK has the following functions:
    void onNewTreeNode(item_t item, counter_t count);
    //void onIncraseCounter(item_t item, counter_t oldcount, counter_t count)
  */
  template<class T, class CALLBACK>  void addTransToTree(T &trans,size_t length,buildtree_t &tree, counter_t count, CALLBACK & cb);
}; //class abstractbuildtree


template <bool ENDONLY = false> class TrieBuildTree {
public:

  class node_t;

      typedef NONORDFP_CHILDMAP<item_t,node_t*> childmap_t;
      typedef typename childmap_t::iterator nodeiter_t;



  class node_t {
    counter_t counter;
    NONORDFP_CHILDMAP<item_t,node_t*> children;
    friend class TrieBuildTree;
  public:

    inline counter_t DINLINE getCounter() {
      return counter;
    } 
    inline void DINLINE setCounter(counter_t c) {
      counter=c;
    }
    inline nodeiter_t DINLINE childrenBegin() {
      return children.begin();
    }
    inline nodeiter_t DINLINE childrenEnd() {
      return children.end();
    }

    childmap_t* getChildren() {
      return &children;
    }
  };//class node_t 


  class nodeptr_t {
  private:
    node_t *data;
  public:
    inline node_t & operator*() {
      return *data;
    }
    inline node_t * operator->() {
      return data;
    }
    inline bool operator==(const nodeptr_t &o) {
      return data==o.data;
    }
    inline bool operator!=(const nodeptr_t &o) {
      return data!=o.data;
    }
    nodeptr_t(node_t *d): data(d){}
  }; //class nodeptr_t

  class buildtree_t {
    node_t *root;
    friend class TrieBuildTree;
  public:
    inline nodeptr_t DINLINE getRoot() {
      return nodeptr_t(root);
    }
  };

protected:
  typedef bracz::blockalloc<node_t,10000> nodealloc_t;

  nodealloc_t allocator;

public:

  /*root_t *&root,U& nodesperitem, BUILDTREEALLOC &allocator,*/
  template <class CALLBACK> void initBuildTree(buildtree_t &tree, item_t maxitem, CALLBACK &cb) {
    tree.root = allocator.allocate();
    tree.root->counter=0;
    cb.initTree(maxitem);
  }

  template<class T, class CALLBACK>  void addTransToTree(T &trans,size_t length,buildtree_t &tree, counter_t count, CALLBACK & cb) {
    node_t *bnode=tree.root;
    if (!ENDONLY) {
      bnode->counter+=count;
    }
    for(size_t i=0;i<length;++i) {
      register item_t curritem=trans[i];
      node_t*& nnode=bnode->children[curritem];
      if (!nnode) {
        //we need to allocate a new node
        nnode=allocator.allocate();
        if (!ENDONLY)
          nnode->counter=count;
        else
          nnode->counter=0;
        //nodesperitem[curritem]++;
        cb.onNewTreeNode(curritem,count);
      } else {
        // **** remove this in production code
        /*if(nnode->counter==1)
          singlec++;*/
        // ****
        if (!ENDONLY)
          nnode->counter+=count;
      }
      //traverse to next node
      bnode=nnode;
    }
    if (ENDONLY) {
      bnode->counter+=count;
    }
  }
  
  

}; //class TrieBuildTree ===================================================


template <bool ENDONLY=false> class EndPatriciaBuildTree {
protected:
  static const counter_t leafbit=1<<30;

  inline static bool DINLINE isLeaf(counter_t cnt){
    return (cnt & leafbit);
  }
  inline static counter_t DINLINE  origCounter(counter_t cnt) {
    return cnt & (~leafbit);
  }

  inline static counter_t DINLINE  counterToLeaf(counter_t cnt) {
    return cnt | (leafbit);
  }

  inline static counter_t DINLINE  counterToNode(counter_t cnt) {
    return cnt;
  }


  typedef NONORDFP_CHILDMAP<item_t,void*> childmap_t;

  static const int internal_node_allocsize = (sizeof(childmap_t)+sizeof(counter_t) + sizeof(uint32_t)-1 )/sizeof(uint32_t);
  
  inline static int DINLINE leafAllocSize(int itemcnt) {
    //assumes sizeof(item_t)==sizeof(uint32_t)
    if (sizeof(item_t)==sizeof(uint32_t)) {
      //faster calculation
      return ((sizeof(counter_t)+sizeof(uint32_t)-1)/sizeof(uint32_t))+1+itemcnt;
    }else {
      return ((sizeof(counter_t)+itemcnt*sizeof(item_t) + sizeof(uint32_t)-1)/sizeof(uint32_t))+1;
    }
  }

  class internalnode_t {
  public:
    counter_t counter;
    childmap_t children;
    void clear() {
      children.clear();
      counter=0;
    }
  }; //class internalnode_t

  class endnode_t {
  public:
    counter_t counter;
    uint32_t leafsize;
    item_t leafs;
  }; //class endnode_t

  //allocator for internal nodes
  blockalloc<internalnode_t,10*1024> nodeallocator;
  //allocator for leafs
  blockalloc<uint32_t,100*1024> rawallocator;

public:


  class storenode_t {
  protected:
    void * data;
    friend class EndPatriciaBuildTree;
  protected:
    inline bool DINLINE isLeaf() const {
      return EndPatriciaBuildTree::isLeaf(getRawCounter());
    }
    inline counter_t DINLINE getRawCounter() const {
      return *reinterpret_cast<counter_t*>(data);
    }
    inline counter_t & DINLINE getRawCounter() {
      return *reinterpret_cast<counter_t*>(data);
    }
    inline const item_t* DINLINE getLeafsPtr() const {
      return &(reinterpret_cast<endnode_t*>(data)->leafs);
    }
    inline item_t* DINLINE getLeafsPtr() {
      return &(reinterpret_cast<endnode_t*>(data)->leafs);
    }
    inline uint32_t& DINLINE getLeafsSize() {
      return reinterpret_cast<endnode_t*>(data)->leafsize;
    }

    inline uint32_t DINLINE getLeafsSize() const {
      return reinterpret_cast<endnode_t*>(data)->leafsize;
    }

    inline childmap_t& DINLINE getChildMap() const {
      return reinterpret_cast<internalnode_t*>(data)->children;
    }




  public:
    inline counter_t DINLINE getCounter() {
      return origCounter(getRawCounter());
    }

    inline childmap_t * getChildren() {
      if (isLeaf()) {
        return NULL;
      } else {
        return &(getChildMap());
      }
    }

    explicit storenode_t(void* d): data(d){}
  };//class storenode_t 

  class nodeiter_t;

  class node_t: public storenode_t {
  protected:
    uint32_t idx;
  public:
    static const uint32_t npos= (uint32_t)(-1);
    
    inline counter_t DINLINE getCounter() {
      if (!ENDONLY) {
        return origCounter(this->getRawCounter());
      } else {
        if (this->isLeaf()) {
          if (idx>=this->getLeafsSize()) {
            return origCounter(this->getRawCounter());
          } else {
            return 0;
          }
        } else {
          return origCounter(this->getRawCounter());          
        }
      }
    }

    inline void DINLINE setCounter(counter_t c) {
      if (this->isLeaf()) {
        this->getRawCounter()=EndPatriciaBuildTree::counterToLeaf(c); 
      } else {
        this->getRawCounter()=EndPatriciaBuildTree::counterToNode(c); 
      }
    }


    inline nodeiter_t DINLINE childrenBegin() {
      if (this->isLeaf()) {
        if (idx<this->getLeafsSize())
          return nodeiter_t(this->data,idx);
        else
          return nodeiter_t(this->data,npos);
      } else {
        return nodeiter_t(this->getChildMap().begin());
      }
    }
    inline const nodeiter_t DINLINE childrenEnd() const {
      if (this->isLeaf()) {
        return nodeiter_t(this->data,npos);
      } else {
        return nodeiter_t(this->getChildMap().end());
      }
    }
    explicit node_t(void*d):storenode_t(d),idx(0) {}
    explicit node_t(void*d,uint32_t i):storenode_t(d),idx(i) {}
    //static const int internal_node_allocsize = (siz
  }; //class ndoe_t

  class nodeptr_t: public node_t {
  public:
    inline node_t & DINLINE operator*() {
      return *this;
    }
    inline node_t * DINLINE operator->() {
      return this;
    }
    explicit nodeptr_t(void *d):node_t(d) {}
    explicit nodeptr_t(void *d,uint32_t i):node_t(d,i) {}
    nodeptr_t(const node_t & n): node_t(n) {}
  }; //class nodeptr_t
  

  class nodeiter_t: protected nodeptr_t {
  protected:
    using node_t::npos;
    using node_t::idx;
    using storenode_t::data;
    childmap_t::iterator mapiter;
    inline bool isMapIter() const {
      return (!this->data);
    }
    inline bool isEndIter() const {
      return (this->idx==npos);
    }
  public:
    inline nodeiter_t& DINLINE operator++() {
      if (isMapIter()) {
        ++mapiter;
        return *this;
      } else {
        this->idx=npos;//set to enditer
        return *this;
      }
    }
    inline std::pair<item_t,nodeptr_t> DINLINE operator*() const {
      if (isMapIter()) {
        return std::make_pair(mapiter->first,nodeptr_t(mapiter->second));
      } else {
        return std::make_pair(this->getLeafsPtr()[idx],nodeptr_t(this->data,this->idx+1));
      }
    }
    inline bool DINLINE operator==(const nodeiter_t &o) {
      if (isMapIter()&&o.isMapIter()) {
        return mapiter==o.mapiter;
      } else {
        return (this->idx==o.idx) && (this->data==o.data);
      }
    }
    inline bool DINLINE operator!=(const nodeiter_t &o) {
      if (isMapIter()&&o.isMapIter()) {
        return mapiter!=o.mapiter;
      } else {
        return (idx!=o.idx) || (data!=o.data);
      }
    }
    nodeiter_t(void* d,uint32_t i):nodeptr_t(d,i){}
    nodeiter_t(const childmap_t::iterator & it): nodeptr_t(NULL,npos),mapiter(it){}
  }; 



  class buildtree_t {
    node_t root;
    friend class EndPatriciaBuildTree;
  public:
    inline nodeptr_t DINLINE getRoot() {
      return nodeptr_t(root);
    }
    buildtree_t():root(NULL) {
    }
  };

protected:

  void* allocateInternalNode(counter_t cnt) {
    internalnode_t *nn=nodeallocator.allocate();
    nn->clear();
    nn->counter=counterToNode(cnt);
    return nn;
  }

  storenode_t allocateLeafNode(counter_t cnt,uint32_t len) {
    storenode_t nn(rawallocator.allocate(leafAllocSize(len)));
    nn.getRawCounter()=counterToLeaf(cnt);
    nn.getLeafsSize()=len;
    return nn;
  }

public:

  template <class CALLBACK> void initBuildTree(buildtree_t &tree, item_t maxitem, CALLBACK &cb) {
    tree.root = node_t(allocateInternalNode(0));
    cb.initTree(maxitem);
  }

  template<class T, class CALLBACK>  void addTransToTree(T &trans,size_t length,buildtree_t &tree, counter_t count, CALLBACK & cb) {
    storenode_t bnode=tree.root;
    size_t i=0;
    void **nnode=NULL;//save the previous pointer
    //the root may not be a leaf node
    while ((i<length) && (!bnode.isLeaf())) {
      if (!ENDONLY)
        bnode.getRawCounter()+=count;
      register item_t curritem=trans[i];
      nnode=&(bnode.getChildMap()[curritem]);
      if (!*nnode) {
        //we need to add a new (leaf) node
        bnode=allocateLeafNode(count,length-i-1);
        *nnode=bnode.data;
        //nnode->counter=count;
        //nodesperitem[curritem]++;
        cb.onNewTreeNode(trans[i],count);
        //if (trans[i]==5) {
        //  log_dbg(0,"5|a|%d|%d",i,length);
        //}
        ++i;
        item_t *lptr=bnode.getLeafsPtr();
        while(i<length) {
          *lptr=trans[i];
          lptr++;
          cb.onNewTreeNode(trans[i],count);

          //if (trans[i]==5) {
          //  log_dbg(0,"5|b|%d|%d",i,length);
          //}
          i++;
        }
        return;
      } 
      //traverse to next node
      bnode=storenode_t(*nnode);
      ++i;
    }//while internal nodes
    if ((i==length)&&((!bnode.isLeaf())||(bnode.getLeafsSize()==0))) {
      //if (!bnode.isLeaf()) {
      //increase last counter
      bnode.getRawCounter()+=count;
    } else {
      //now: either i<length && bnode.isleaf
      // or: bnode.isleaf && bnode.leafsize>0
      //in both cases we have to split the current leaf node
      internalnode_t *newnode = nodeallocator.allocate();
      newnode->clear();
      counter_t nodectr;
      if (ENDONLY)
        nodectr=counterToNode(0);
      else
        nodectr=counterToNode(bnode.getCounter()+count);
      newnode->counter=nodectr;
      *nnode = newnode;
      //create common elements
      uint32_t lc=0;//index in the existing leaf
      while ((i<length)&&(lc<bnode.getLeafsSize())&&(trans[i]==bnode.getLeafsPtr()[lc])) {
        newnode=(internalnode_t*)((newnode->children[trans[i]])=nodeallocator.allocate());
        newnode->clear();
        newnode->counter=nodectr;
        ++lc;
        ++i;
      }
      //we did the common path. now create the distinct path
      if (lc<bnode.getLeafsSize()) {
        uint32_t ls=bnode.getLeafsSize()-lc-1;
        item_t li=bnode.getLeafsPtr()[lc];
        //shorten and attach the original leaf
        endnode_t *newleaf = reinterpret_cast<endnode_t*>((item_t*)bnode.data + lc+1);
        newleaf->counter=bnode.getRawCounter();
        newleaf->leafsize=ls;
        newnode->children[li]=newleaf;
      } else if (ENDONLY) {
        newnode->counter+=bnode.getCounter();
      }
      if (i<length) {
        uint32_t ls=length-i-1;
        item_t li=trans[i];
        storenode_t newleaf=allocateLeafNode(count,ls);
        newnode->children[li]=newleaf.data;
        //if (trans[i]==5) {
        // log_dbg(0,"5|c|%d|%d",i,length);
        //}
        ++i;
        cb.onNewTreeNode(li,count);
        uint32_t ofs=0;
        while(ofs<ls) {
          newleaf.getLeafsPtr()[ofs]=trans[i+ofs];
          cb.onNewTreeNode(trans[i+ofs],count);
          //if (trans[i+ofs]==5) {
          //  log_dbg(0,"5|d|%d|%d",i+ofs,length);
          //}
          ofs++;
        }
      } else if (ENDONLY) {
        newnode->counter+=count;
      }        //add new leaf node
    }//finish splitting
  }//addTransToTree
  

}; //class EndPatriciaBuildTree


}//namespace bracz


#endif

---