core.cpp

Go to the documentation of this file.

#include "common.hpp"

#include <stack>
#include <vector>

#include "common/log.h"
#include "common/maxvector.cpp"

namespace bracz {

  template<class STRUCTURE, class OUTPUT>
  class FPGrowthBase {
  protected:
  
    typedef TYPENAME STRUCTURE::fptree_t fptree_t;

    typedef struct {
      item_t nextitem;
      item_t lastitem;
      fptree_t *fptree;
      item_t singlepdepth;
    } tdrecurse_t;

  public:
    void findFrequentItems(const counter_t minsupp, STRUCTURE &str, OUTPUT &out, item_t maxitem) {}

  };


  template<class STRUCTURE, class OUTPUT, bool SINGLEPATH, NEELevel NEE, FirstLevel FIRSTLEVEL> class FPGrowthBaseNoNEE : public FPGrowthBase<STRUCTURE,OUTPUT> {
  protected:
    typedef TYPENAME FPGrowthBase<STRUCTURE,OUTPUT>::tdrecurse_t tdrecurse_t;
  public:
#define VECTOR bracz::maxvector

    FPGrowthBaseNoNEE(){}

    //global variables for the core recursion
    VECTOR<item_t> curritemset;
    VECTOR<item_t> neelist;
    VECTOR<counter_t> neecounts;
    //    VECTOR<TYPENAME STRUCTURE::SinglePathIterator> itst;

    //num freq itemset
    size_t numfreq;
    //count of freqitems in main recursion
    size_t numfreqrec;
    //statistics for single path optimization
    size_t singleheader;
    size_t singlepart;
    size_t singlebody;

    counter_t minsupp;

    item_t maxitem;


    OUTPUT *out;

    STRUCTURE *str;

    TYPENAME STRUCTURE::fptree_t *singleptree;
    counter_t cfreq;

  private:
    inline void DINLINE outputPush(item_t item) {
      if (OUTPUT::isDFO()) {
        out->pushItem(item);
      } else {
        curritemset.push_back(item);
      }
    }

    inline void DINLINE outputPop() {
      if (OUTPUT::isDFO()) {
        out->popItem();
      } else {
        curritemset.pop_back();
      }
    }

    inline void DINLINE outputWriteLow(counter_t supp) {
      numfreq++;
      if (OUTPUT::isDFO()) {
        out->write(supp);
      } else {
        out->writeItemsetAndCounter(curritemset.begin(),curritemset.end(),supp);
      }
    }

    counter_t neesupp;

    void neeRecurse(size_t neeidx) {
      //choose the first element to insert
      while(neeidx<neelist.size()) {
        if (OUTPUT::isDFO()) {
          numfreq++;
          out->pushItemWithPrevSupport(neelist[neeidx]);
        } else {
          outputPush(neelist[neeidx]);
          outputWriteLow(neesupp);
        }
        neeRecurse(++neeidx);
        outputPop();
      }
    }


    inline void DINLINE outputWrite(counter_t supp) {
      outputWriteLow(supp);
      if (NEE==NEE_Full) {
        neesupp=supp;
#ifdef STATS_NEECOUNT
        neecounts[neelist.size()]++;
#endif
        neeRecurse(0);
      }
    }


    inline void DINLINE outputPushAndWrite(item_t item, counter_t supp) {
      outputPush(item);
      outputWrite(supp);
    }

  public:

    void singlePRecurse(TYPENAME STRUCTURE::SinglePathIterator itop) {
      while(itop.increment(singleptree),!itop.atEnd(singleptree)) {
        outputPushAndWrite(itop.getCurrItem(singleptree),cfreq);
        // ****
        singlebody++;
        singlePRecurse(itop);
      }
      outputPop();
    }

    void freqRecurse(tdrecurse_t stop) {
      counter_t rootfreq=stop.fptree->getRootFrequency();
      if (NEE==NEE_Full) {
        for (item_t curritem=stop.lastitem;curritem>(SINGLEPATH?stop.singlepdepth:0);) {
          --curritem;
          if (stop.fptree->getFrequency(curritem)==rootfreq) {
            //fprintf(stderr,"\nnee item %d singlepdepth %d lastitem %d | ",curritem,stop.singlepdepth,stop.lastitem);
            neelist.push_back(curritem);
          } //if conditionally closed item
        }//for available items
      }//if NEE
      outputWrite(rootfreq);
      for (item_t curritem=0;curritem<stop.lastitem;++curritem) {
        if (stop.lastitem==maxitem) {
          fprintf(stderr,"%d ",curritem);
        }
        counter_t cfreq=stop.fptree->getFrequency(curritem);
        if (cfreq < minsupp) {
          continue;
        } else if (SINGLEPATH && curritem < stop.singlepdepth) {
          singlepart++;
          outputPushAndWrite(curritem,cfreq);
          //out->pushItem(maxitem-1);//outputPushAndWrite(0,cfreq);
          this->cfreq=cfreq;
          this->singleptree=stop.fptree;
          singlePRecurse(str->getSinglePathIterator(stop.fptree,curritem));
          //out->popItem();
          continue;
        } else if ((NEE==NEE_Full) && (cfreq==rootfreq)) {
          //          fprintf(stderr,"\nnee popback %d singlepdepth %d cfreq %d root freq %d |",curritem,stop.singlepdepth,cfreq,rootfreq);
          neelist.pop_back();
          continue;
        }
        numfreqrec++;
        outputPush(curritem);
        tdrecurse_t nr;
        nr.nextitem=0;
        nr.lastitem=curritem;
        if ((NEE==NEE_Level1) && (cfreq==rootfreq)) {
          nr.fptree=stop.fptree;
          nr.singlepdepth=stop.singlepdepth;
          freqRecurse(nr);
        } else {
          nr.fptree=str->projectTree(stop.fptree,curritem);
          // **** remove this sanity check
          if (cfreq!=nr.fptree->getRootFrequency()) {
            log_err(0,"Inconsistency: cfreq %u cond tree freq %u",cfreq,nr.fptree->getRootFrequency());
          }
          nr.singlepdepth=str->checkSinglePath(nr.fptree,curritem,stop.singlepdepth);
          freqRecurse(nr);
          str->deallocTree(nr.fptree, stop.fptree, curritem);
        }
        outputPop();
      }
    }

    void NOINLINE findFrequentItems(const counter_t minsupp, STRUCTURE &str, OUTPUT &out, item_t maxitem) {
      curritemset.reserve(maxitem);
      neelist.reserve(maxitem);
#ifdef STATS_NEECOUNT
      neecounts.reserve(maxitem);
      for (item_t i=0;i<maxitem;++i)
        neecounts[i]=0;
#endif
      this->minsupp=minsupp;
      this->out=&out;
      this->str=&str;
      //num freq itemset
      numfreq=0;
      numfreqrec=0;
      //statistics for single path optimization
      singleheader=0;
      singlepart=0;
      singlebody=0;
      this->maxitem=maxitem;
      tdrecurse_t globtree;

      if (FIRSTLEVEL!=FLBuildSingleTree) {
        out.write(str.getTransactionCount());
        for (item_t curritem=0;curritem<maxitem;++curritem) {
          fprintf(stderr,"%d ",curritem);
          globtree.nextitem=0;
          globtree.singlepdepth=0;
          globtree.lastitem=curritem;
          globtree.fptree=str.getProjTree(curritem);
          outputPush(curritem);
          freqRecurse(globtree);
          outputPop();
        }
      } else {
        globtree.nextitem=0;
        globtree.singlepdepth=0;
        globtree.lastitem=maxitem;
        globtree.fptree=str.getFullTree();
        freqRecurse(globtree);
      }
      fprintf(stderr,"\n");
      log_info(0,"core recursion ended. numfreq rec=%zu, single header=%zu, part=%zu, body=%zu",numfreqrec,singleheader,singlepart,singlebody);
      log_info(0,"Total frequent itemsets returned: %zu",numfreq);
    }
    
    ~FPGrowthBaseNoNEE() {
#ifdef STATS_NEECOUNT
      for (item_t i=0;i<maxitem;++i) {
        fprintf(stderr,"length %d, count %u\n",i,neecounts[i]);
      }
#endif
    }

  };//class FPGrowthBaseNoNEE

/*

  stack: last item, structure, counter,
  for next item=last item -1 downto 0 do
    project
    recurse (next item, new structure, new counter)
    cleanup
  end for


  stack: last item, next item, structure, counter
  while(!stack.empty) do
    if (stack.top.nextitem == stack.top.lastitem) then
      pop stack
      stack.top.nextitem++;
    else
      if stack.top.nextitem is not frequent then continue
      itemset.push_back(nextitem)
      output the (single) new itemset:
      project onto stack.top.nextitem
      check-singlepath
      get-conditional-frequencies
      check-and-extend conditional closed item list
      push projection onto stack with nextitem=0
    endif

  
*/


     
} //namespace bracz                                                                                                

---