classicrebuildfp.cpp

Go to the documentation of this file.

#include "common.hpp"
#include "common/log.h"
#include "io/input/transaction_reader/TransactionReader.hpp"
#include "fpgrowth/buildfptree.hpp"


namespace bracz {

  typedef struct bnode_t { 
    bnode_t *parent;
    item_t item;
    counter_t counter;
    bnode_t *headerlink;
    bnode_t *firstchild;
    bnode_t *nextsibling;
  } bnode_t;


  template<class INPUT, FirstLevel FIRSTLEVEL, bool SINGLE> class ClassicRebuildFPStructure {
  private:

  public:
    typedef struct fptree_t {
      counter_t *freqs;
      bnode_t **headertable;
      bnode_t *root;
      counter_t DINLINE getFrequency(item_t i) {
        return freqs[i];
      }

      counter_t DINLINE getRootFrequency() {
        return root->counter;
      }
    } fptree_t;


    counter_t getTransactionCount() {
      return transaction_count;
    }

  private:

    INPUT *inp;
    
  protected:

    counter_t minsupp;
    fptree_t fulltree;

    std::vector<fptree_t> l1trees;

    // used when per-item trees are built
    counter_t transaction_count;

    singleualloc<bnode_t, 10*1024> nodeallocator;
    singlesalloc<fptree_t,100> treealloc;


    typedef blockstack<stackmultiblock<bnode_t*,false,stacksingleblock<counter_t,false> > > treecontentalloc_t;
    //these will be unused if operating TD mode
    treecontentalloc_t treecontentalloc;


    template<class ARR> void addTransToTree(const ARR &trans, size_t len, fptree_t *tree, counter_t count) {
      bnode_t *bnode=tree->root;
      bnode->counter+=count;
      for(size_t i=0;i<len;++i) {
        register item_t curritem=trans[i];
        bnode_t** rnode=&(bnode->firstchild);
        bnode_t * nnode=*rnode;
        tree->freqs[curritem]+=count;
        while (nnode && nnode->item<curritem) {
          rnode=&(nnode->nextsibling);
          nnode=nnode->nextsibling;
        }
        if (!nnode || (nnode->item>curritem)) {
          //we need to allocate a new node
          nnode=nodeallocator.allocate();
          nnode->parent=i?bnode:NULL;
          nnode->item=curritem;
          nnode->counter=count;
          nnode->headerlink=tree->headertable[curritem];
          tree->headertable[curritem]=nnode;

          nnode->nextsibling=*rnode;
          *rnode=nnode;
          nnode->firstchild=NULL;
          
        } else {//nnode->item==curritem
          nnode->counter+=count;
        }
        //traverse to next node
        bnode=nnode;
      }
    }

    void DINLINE inittree(fptree_t &fulltree) {
      fulltree.root=nodeallocator.allocate();
      fulltree.root->item=-1;
      fulltree.root->parent=NULL;
      fulltree.root->firstchild=NULL;
      fulltree.root->counter=0;
      fulltree.root->headerlink=NULL;
      fulltree.root->nextsibling=NULL;
    }

    void DINLINE allocatetree(fptree_t &fulltree, item_t maxitem) {
      alignalloc::allocz(fulltree.freqs,maxitem);
      alignalloc::allocz(fulltree.headertable,maxitem);
      inittree(fulltree);
    }

    void buildTree(item_t maxitem) {
      log_status(0,"Building unconditional FP tree.");
      //build the trie
      std::vector<item_t> trans;
      inp->rewind();
      //    size_t singlec=0;
      transaction_count=0;
      allocatetree(fulltree,maxitem);
      while (counter_t count=inp->nextTransactionBIS(trans)) {
        transaction_count+=count;
        addTransToTree(trans,trans.size(),&fulltree,count);
      }
    }


    void buildAllL1Trees(item_t maxitem) {
      log_status(0,"Initializing FP tree.");
      l1trees.resize(maxitem);
      for(item_t i=0;i<maxitem;++i) {
        allocatetree(l1trees[i],i);
      }
      log_status(0,"Building 1st conditional FP trees.");
      //build the trie
      std::vector<item_t> trans;
      inp->rewind();
      //    size_t singlec=0;
      transaction_count=0;
      while (counter_t count=inp->nextTransactionBIS(trans)) {
        transaction_count+=count;
        for (size_t itemidx=0;itemidx<trans.size();++itemidx) {
          addTransToTree(trans,itemidx,&l1trees[trans[itemidx]],count);
        }
      }
    }

  public:
    class SinglePathIterator {
    private:
      bnode_t *c;
    public:
      void DINLINE increment(fptree_t *) {
        c=c->parent;
      }
      bool DINLINE atEnd(fptree_t *) {
        return !c;
      }
      item_t DINLINE getCurrItem(fptree_t *) {
        return c->item;
      }
      SinglePathIterator(bnode_t *_c): c(_c){}
    };//class SinglePathIterator

    SinglePathIterator getSinglePathIterator(fptree_t *t,item_t curritem) {
      return SinglePathIterator(t->headertable[curritem]);
    }

    ClassicRebuildFPStructure(INPUT *_inp, item_t maxitem, counter_t _minsupp):inp(_inp),minsupp(_minsupp) {
      temptransaction=new item_t[maxitem];
      switch(FIRSTLEVEL) {
      case FLBuildSingleTree: {
        buildTree(maxitem);
        break;
      }
      case FLBuildAllL1Trees: {
        buildAllL1Trees(maxitem);
        break;
      }
      case FLSimultProject: {
        log_err(0,"Simultaneous projection is not implemented in ClassicFpTree yet.");
        exit(1);
        break;
      }
      }
    }
    
    ~ClassicRebuildFPStructure() {
      delete [] temptransaction;
    }

    fptree_t * getFullTree() {
      if (FIRSTLEVEL != FLBuildSingleTree) {
        log_err(0,"Requested full tree when per-item trees are calculated!");
        return NULL;
      } else 
        return &fulltree;
    }

    fptree_t * getProjTree(item_t item) {
      if (FIRSTLEVEL == FLBuildSingleTree) {
        log_err(0,"Requested per-item tree when only unconditional tree is calculated!");
        return NULL;
      } else 
        return &(l1trees[item]);
    }


    item_t DINLINE checkSinglePath(fptree_t *t, item_t curritem, item_t spdepth) {
      if (!SINGLE) {
        return 0;
      } else {
        while ((spdepth<curritem) && ((!t->headertable[spdepth]) || (!t->headertable[spdepth]->headerlink)))
          spdepth++;
        return spdepth;
      }
    }

    template <class O_M> void DINLINE handleSinglePath(fptree_t *t, item_t curritem, O_M *out) {
    
    }

    void DINLINE zeroDataDense(fptree_t *intr, item_t curritem) {
      //partial erase on the `data' part of the tree
      alignalloc::zerola(intr->freqs,curritem);
      //zero the counters above the current item
      for (item_t i=0;i<curritem;++i) {
        for(bnode_t *cnode=intr->headertable[i];cnode;cnode=cnode->headerlink) {
          cnode->counter=0;
        }
      }
    }

    /*    void DINLINE aggregateDense(fptree_t *intr, item_t curritem) {
      for (bnode_t *cnode=intr->headertable[curritem];cnode;cnode=cnode->headerlink) {
        counter_t c=cnode->counter;
        intr->rootfreq+=c;
        bnode_t *nnode=cnode->parent;
        while (nnode) {
          nnode->counter+=c;
          intr->freqs[nnode->item]+=c;
          nnode=nnode->parent;
        }
      }
      
      }*/

    item_t* temptransaction;

    fptree_t * DINLINE projectTree(fptree_t *intr,item_t curritem) {
      /*if (TD) {
        zeroDataDense(intr,curritem);
        aggregateDense(intr,curritem);
        return intr;
        } else {*/
      fptree_t *nftree = treealloc.allocate();
      pair<bnode_t**, counter_t*> als;
      treecontentalloc.pushAndGetBlock(curritem,als);
      nftree->freqs=als.second;
      alignalloc::zero(nftree->freqs,curritem);
      nftree->headertable=als.first;
      alignalloc::zero(nftree->headertable,curritem);
      inittree(*nftree);
      
      for (bnode_t *cnode=intr->headertable[curritem];cnode;cnode=cnode->headerlink) {
        counter_t c=cnode->counter;
        bnode_t *nnode=cnode->parent;
        item_t *ptr=temptransaction+curritem;
        while (nnode) {
          if (intr->freqs[nnode->item]>=minsupp) {
            --ptr;
            *ptr=nnode->item;
          }
          nnode=nnode->parent;
        }
        addTransToTree(ptr,temptransaction+curritem-ptr,nftree,c);
      }

      return nftree;
    }
  

    void DINLINE deallocTree(fptree_t *t, fptree_t *parent, item_t projitem) {
      for (item_t i=0;i<projitem;++i) {
        for(bnode_t *cnode=t->headertable[i];cnode;cnode=cnode->headerlink) {
          nodeallocator.free(cnode);
        }
      }
      nodeallocator.free(t->root);
      treecontentalloc.freeBlock();
      treealloc.free(t);
    }

  }; //class ClassicRebuildFPStructure


}//namespace bracz

---