classicfp.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 node_t {
    node_t *parent;
    item_t item;
    counter_t counter;
    node_t *headerlink;
  } node_t;


  template<class INPUT,class BUILDTREE, FirstLevel FIRSTLEVEL, bool TD, bool SINGLE> class ClassicFPStructure {
  private:

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

      counter_t DINLINE getRootFrequency() {
        return rootfreq;
      }
    } fptree_t;


    counter_t getTransactionCount() {
      return transaction_count;
    }

  private:

    INPUT *inp;
    
  protected:

    fptree_t fulltree;

    std::vector<fptree_t> l1trees;

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

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

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


    void reccopytree(fptree_t *target,TYPENAME BUILDTREE::nodeptr_t node, node_t *parent) {
      //target->counters[nodeidx]=node->getCounter();
      for(TYPENAME BUILDTREE::nodeiter_t i=node->childrenBegin();
          i!=node->childrenEnd();
          ++i) {
        //item_t (*i).first
        //
        node_t *newnode=nodeallocator.allocate();
        newnode->parent=parent;
        newnode->item=(*i).first;
        newnode->counter=(*i).second->getCounter();
        newnode->headerlink=target->headertable[(*i).first];
        target->headertable[(*i).first]=newnode;
        target->freqs[(*i).first]+=(*i).second->getCounter();

        reccopytree(target,TYPENAME BUILDTREE::nodeptr_t((*i).second),newnode);
      }
    }

    void copyBuildTreeToFinalTree(TYPENAME BUILDTREE::buildtree_t &buildtree,fptree_t &fulltree,item_t maxitem) {
      alignalloc::allocz(fulltree.freqs,maxitem);
      alignalloc::allocz(fulltree.headertable,maxitem);
      fulltree.rootfreq=buildtree.getRoot()->getCounter();
      reccopytree(&fulltree,(buildtree.getRoot()),NULL);
    }

    void buildTree(item_t maxitem) {
      bracz::nullTreeAnn treeann;
      BUILDTREE btr;
      typename BUILDTREE::buildtree_t buildtree;
      btr.initBuildTree(buildtree,maxitem,treeann);

      log_status(0,"Building temporary FP tree.");
      //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;
        btr.addTransToTree(trans,trans.size(),buildtree,count,treeann);
      }
      copyBuildTreeToFinalTree(buildtree,fulltree,maxitem);
    }


    void buildAllL1Trees(item_t maxitem) {
      BUILDTREE btr;
      // holds the number of nodes for each item id
      bracz::nullTreeAnn treeann;
      std::vector<typename BUILDTREE::buildtree_t> trees;
      trees.resize(maxitem);
      log_status(0,"Initializing FP tree.");
      for(item_t i=0;i<maxitem;++i) {
        btr.initBuildTree(trees[i],i,treeann);
      }
      log_status(0,"Building temporary 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) {
          btr.addTransToTree(trans,itemidx,trees[trans[itemidx]],count,treeann);
        }
      }
      l1trees.resize(maxitem);
      for(item_t i=0;i<maxitem;++i) {
        copyBuildTreeToFinalTree(trees[i],l1trees[i],i);
      }
    }

  public:
    class SinglePathIterator {
    private:
      node_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(node_t *_c): c(_c){}
    };//class SinglePathIterator

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

    ClassicFPStructure(INPUT *_inp, item_t maxitem) {
      inp=_inp;
      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;
      }
      }
    }

    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(node_t *cnode=intr->headertable[i];cnode;cnode=cnode->headerlink) {
          cnode->counter=0;
        }
        }*/
      intr->rootfreq=0;
    }

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

    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();
        nftree->parents=intr->parents;
        nftree->itemstarts=intr->itemstarts;
        nftree->counters=NULL;
        nodealloc.pushAndGetBlock(nftree->itemstarts[curritem],nftree->counters);
        nftree->freqs=NULL;
        headeralloc.pushAndGetBlock(curritem,nftree->freqs);
        zeroDataADense(nftree,curritem);
        aggregateDense(nftree->itemstarts,nftree->parents,nftree->freqs,intr->counters,nftree->counters,curritem);
        if (PROJECT) {
          compactTree(nftree,curritem);
        }
        return nftree;*/
      }
    }

    void DINLINE deallocTree(fptree_t *t, fptree_t *parent, item_t projitem) {
      //in case of TD de clean up the nonzer counters in the tree
      if (TD) {
        for (node_t *cnode=t->headertable[projitem];cnode;cnode=cnode->headerlink) {
          node_t *pnode=cnode;
          while (pnode && pnode->counter) {
            pnode->counter=0;
            pnode=pnode->parent;
          }
        }
      }
    }

  }; //class ClassicFPStructure

}//namespace bracz

---