nonordfp.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"

//#define PREFETCH
static const int PREFETCHDIST=64;

namespace bracz {




  template<class INPUT,class BUILDTREE, FirstLevel FIRSTLEVEL> class NonOrdFPStructure {
  public:
    typedef uint32_t index_t;

    typedef struct fptree_t {
      index_t *itemstarts;
      index_t *parents;

      counter_t *freqs;
      counter_t *counters;

      enum freeelement_t {
        free_none=0,
        free_data=1,
        free_structure=2
      };
      int freeelements;


      fptree_t() {
        itemstarts=NULL;
        counters=NULL;
        parents=NULL;
        freqs=NULL;
        freeelements=free_none;
      }

      counter_t DINLINE getFrequency(item_t i) {
        return freqs[i];
      }

      counter_t DINLINE getRootFrequency() {
        return counters[0];
      }
    } 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;


    class TreeCopy {
    public:

      std::vector<index_t> nextfreenode;

      fptree_t *target;

      void reccopytree(TYPENAME BUILDTREE::nodeptr_t node, index_t nodeidx) {
        target->counters[nodeidx]=node->getCounter();
        for(TYPENAME BUILDTREE::nodeiter_t i=node->childrenBegin();
            i!=node->childrenEnd();
            ++i) {
          register index_t newidx=nextfreenode[(*i).first]++;
          target->parents[newidx]=nodeidx;
          target->freqs[(*i).first]+=(*i).second->getCounter();
          reccopytree(TYPENAME BUILDTREE::nodeptr_t((*i).second),newidx);
        }
      }

    };//class TreeCopy

    class TreeAnnotation {
    protected:
      std::vector<counter_t> nodesperitem;

    public:
      inline void DINLINE initTree(item_t maxitem) {
        nodesperitem.resize(maxitem,0);
      }

      inline void DINLINE onNewTreeNode(item_t curritem,counter_t /*count*/) {
        nodesperitem[curritem]++;
      }
    

      template<class BUILDTREE_> inline void DINLINE buildTreeToFinalTree(BUILDTREE_ & btr, typename BUILDTREE_::buildtree_t &tree, fptree_t &fulltree, item_t maxitem) {
        //      log_dbg(0,"nodes per item:");
        //calculate and fill itemstarts array
        alignalloc::alloc(fulltree.itemstarts,maxitem+1);
        alignalloc::allocz(fulltree.freqs,maxitem);
        index_t last=1;//node 0 is the root
        for(size_t i=0;i<maxitem;++i) {
          fulltree.itemstarts[i]=last;
          //        fprintf(stderr,"(%d=%d) ",i,nodesperitem[i]);
          last+=nodesperitem[i];
        }
        //fprintf(stderr,"\n");
        fulltree.itemstarts[maxitem]=last;
        //    log_info(0,"Build FP-tree: nodes %d, multiples %d",last,singlec);
        //log_info(0,"Build FP-tree: nodes %d",last);
        //compact the trie, copy data to the final structure
        //log_status(0,"Creating unconditional compact FP tree.");
        alignalloc::alloc(fulltree.parents,last);
        alignalloc::alloc(fulltree.counters,last);
        TreeCopy tc;
        tc.nextfreenode.assign(fulltree.itemstarts, fulltree.itemstarts+maxitem);
        tc.target=&fulltree;
        tc.reccopytree((tree.getRoot()),0);
        fprintf(stderr,"[%d %d %d] ",maxitem,fulltree.counters[0],last);
        //log_status(0,"done root counter=%d",fulltree.counters[0]);
      }
    }; //class TreeAnnotation
    void buildTree(item_t maxitem) {
      TreeAnnotation 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);
      }
      treeann.buildTreeToFinalTree(btr,buildtree,fulltree,maxitem);
    }

    void buildAllL1Trees(item_t maxitem) {
      BUILDTREE btr;
      // holds the number of nodes for each item id
      std::vector<TreeAnnotation> treeannotations;
      std::vector<typename BUILDTREE::buildtree_t> trees;
      trees.resize(maxitem);
      treeannotations.resize(maxitem);
      log_status(0,"Initializing FP tree.");
      for(item_t i=0;i<maxitem;++i) {
        btr.initBuildTree(trees[i],i,treeannotations[i]);
      }
      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,treeannotations[trans[itemidx]]);
        }
      }
      l1trees.resize(maxitem);
      for(item_t i=0;i<maxitem;++i) {
        treeannotations[i].buildTreeToFinalTree(btr,trees[i],l1trees[i],i);
      }
      fprintf(stderr,"\n");
    }
          


    class SimultProject {

      typedef struct simultprojnode_t {
        item_t parentitem; //NOTE this holds 'item+1', item 0 is reserved for the root
        index_t parentoffset;
        counter_t counter;
        simultprojnode_t *next;
      } simultprojnode_t __attribute__ ((aligned (16)));;

      bracz::blockalloc<simultprojnode_t,100000> tempnodealloc;
          

      typedef struct temptrie_t {
      public:
        bracz::maxvector<simultprojnode_t*> nodes;
      } temptrie_t; //struct temptrie_t

      //the current path in the recursion
      std::vector<item_t> curritemset;

      //this holds the unassembled temporary nonord fp trees
      bracz::maxvector<temptrie_t> temptrees;

      //parent
      NonOrdFPStructure *parent;
        
      class counterAddCombine {
      public:
        inline static void DINLINE combine (counter_t &dest, const counter_t &src) {
          dest+=src;
        }
      };

      template <typename T, class CombineFn> class itemlist_t {
      private:
        std::vector<item_t> itemlist;
        T* elements;
        uint32_t maxitem;

      public:
        itemlist_t(): elements(NULL){}
        
        inline void DINLINE init(uint32_t _maxitem){
          maxitem=_maxitem;
          itemlist.reserve(maxitem);
          alignalloc::allocz(elements,maxitem);
        }

        ~itemlist_t() {
          alignalloc::freeifnonnull(elements);
        }

        inline T& DINLINE getItem(item_t i) {
          return elements[i];
        }

        inline void DINLINE setItem(item_t i,T element) {
          if (!getItem(i)) {
            itemlist.push_back(i);
          }
          CombineFn::combine(elements[i],element);
        }

        inline void DINLINE combine(const itemlist_t &o) {
          for(index_t idx=0;idx<o.itemlist.size();++idx) {
            item_t i=o.itemlist[idx];
            setItem(i,o.elements[i]);
          }
        }

        inline void DINLINE clear() {
          // **** may clear with memory zero routine
          if (true) {
            for(index_t idx=0;idx<itemlist.size();++idx) {
              item_t i=itemlist[idx];
              elements[i]=T();
            }
          } else {
            alignalloc::zero(elements,maxitem);
          }
          itemlist.clear();
        }

        class iterator {
        private:
          itemlist_t *parent;
          uint32_t idx;
        public:
          iterator(itemlist_t *p,uint32_t i):parent(p),idx(i){
          }
          iterator(const iterator &o):parent(o.parent),idx(o.idx) {
          }
          inline bool DINLINE operator==(const iterator&o) const {
            return (idx==o.idx)&&(parent==o.parent);
          }
          inline bool DINLINE operator!=(const iterator&o) const {
            return (idx!=o.idx)||(parent!=o.parent);
          }
          inline iterator& operator++() {
            ++idx;
            return *this;
          }
          inline std::pair<item_t, T> operator*() const {
            item_t i=parent->itemlist[idx];
            return std::make_pair(i,parent->elements[i]);
          }

        }; //class iterator
        friend class iterator;
        iterator begin() {
          return iterator(this,0);
        }
        iterator end() {
          return iterator(this,itemlist.size());
        }
      }; //class itemlist_t

      typedef itemlist_t<counter_t,counterAddCombine> myitemlist_t;  

      bracz::maxvector<myitemlist_t> itemlists;
      //a 2-dim array of node pointers for the current node ptr along the recursion. It is indexed with item ids
      bracz::maxvector<simultprojnode_t**> recursenodes;  

      item_t maxitem;

      size_t totnodecount;

      void simultRecurse(TYPENAME BUILDTREE::nodeptr_t node) {
        index_t idx=curritemset.size()-1;
        itemlists[idx].clear();
                                                       // **** might be better to post-zero the existing nodes
        //union children's list into my list
        for(TYPENAME BUILDTREE::nodeiter_t i=node->childrenBegin();
            i!=node->childrenEnd();
            ++i) {
          item_t childitem = (*i).first;
          TYPENAME BUILDTREE::nodeptr_t childp((*i).second);
          //fprintf(stderr,"child %d, counter %d (",childitem,(*childp).getCounter());
          curritemset.push_back(childitem+1);

          //insert the child's item into the itemlists of all its parent nodes
          //first look how much we need to go upwards
          index_t pidx=idx;
          while (!recursenodes[pidx][childitem])//watch: recursenodes[0] is initialized with the root node of each tree
            --pidx;
          ++pidx;//the terminating node needs not to be created
          while(pidx<=idx) {
            //insert node
            simultprojnode_t *newnode = tempnodealloc.allocate();
            totnodecount++;
            //newnode->counter=0;
            newnode->parentitem=curritemset[pidx-1];//this is already 1-indexed
            //the parent is the last node inserted with that item id in this tree.
            newnode->parentoffset=parent->l1trees[childitem].itemstarts[curritemset[pidx-1]]-1; //already indexed from 1
            //add the new node to the counter
            parent->l1trees[childitem].itemstarts[curritemset[pidx]]++;
            //add the new node to the linked list
            //fprintf(stderr,"ins pidx %d into temptrees[%d].nodes[%d]",pidx,childitem,curritemset[pidx]);
            newnode->next=temptrees[childitem].nodes[curritemset[pidx]];
            temptrees[childitem].nodes[curritemset[pidx]]=newnode;
            //add the new node to the recursion node table
            recursenodes[pidx][childitem]=newnode;
            pidx++;
          }


          //alignalloc::zero(recursenodes[idx+1],maxitem); // **** would be enough to zero FROM current item till maxitem
          simultRecurse(childp);

          itemlists[idx].combine(itemlists[idx+1]);
          itemlists[idx].setItem(childitem,(*childp).getCounter());
          //fprintf(stderr,")");
          curritemset.pop_back();
        }
        //insert my node into all trees that are in mylist
        //fprintf(stderr,"\"");
        for (typename myitemlist_t::iterator i=itemlists[idx].begin();
             i!=itemlists[idx].end();
             ++i) {
          //the parent pointers, next, etc. are already filled by the descendant who has first inserted i->first into my itemlist
          recursenodes[idx][(*i).first]->counter=(*i).second;
          recursenodes[idx][(*i).first]=NULL;
          //fprintf(stderr,"{%d %d}",(*i).first,(*i).second);
        }
        //fprintf(stderr,"\"");
      }//function simultrecurse

    public:
      void doSimultProject(NonOrdFPStructure *par,item_t maxitem, uint32_t maxdepth, BUILDTREE &btr,typename BUILDTREE::buildtree_t  &tree) {
        log_status(0,"Preparing simultaneous projection");
        parent=par;
        totnodecount=0;
        parent->l1trees.resize(maxitem);
        this->maxitem=maxitem;
        curritemset.reserve(maxdepth+1);
        curritemset.resize(0);
        curritemset.push_back(0);//watch
        temptrees.resize(maxitem);
        itemlists.resize(maxdepth+1);
        recursenodes.resize(maxdepth+1);
        for(uint32_t i=0;i<=maxdepth;++i) {
          itemlists[i].init(maxitem);
          alignalloc::allocz(recursenodes[i],maxitem);
        }
        for (item_t i=0;i<maxitem;++i) {
          temptrees[i].nodes.resize(i+1,NULL);
          //this will hold the count of nodes for each item
          //this is indexed with 'item+1'
          alignalloc::allocz(parent->l1trees[i].itemstarts,i+1);
          parent->l1trees[i].itemstarts[0]=1;//we do have a node for item id -1, the root.
          recursenodes[0][i]=tempnodealloc.allocate();
          totnodecount++;
          recursenodes[0][i]->parentitem=0;//**** may cause problems
          recursenodes[0][i]->parentoffset=0;
          recursenodes[0][i]->next=NULL;
          recursenodes[0][i]->counter=0;
          temptrees[i].nodes[0]=recursenodes[0][i];
        }
        log_status(0,"Doing simultaneous projection");
        simultRecurse(tree.getRoot());
        //fprintf(stderr,"\n");
        log_info(0,"total node count %u",totnodecount);
        log_status(0,"Copying temporary tries into the final containers.");
        for(uint32_t i=0;i<=maxdepth;++i) {
          alignalloc::free(recursenodes[i]);
        }
        bracz::maxvector<index_t> nodeoffsets;
        nodeoffsets.reserve(maxitem+2);
        bracz::maxvector<index_t> nextnode;
        nextnode.reserve(maxitem+1);
        for (item_t curritem=0;curritem<maxitem;++curritem) {
          //fprintf(stderr,"%d ",curritem);
          fptree_t &t=parent->l1trees[curritem];
          nodeoffsets.resize(curritem+2);
          nextnode.resize(curritem+1);
          nodeoffsets[0]=0;
          for(item_t i=1;i<=curritem+1;++i) {
            nodeoffsets[i]=nodeoffsets[i-1]+t.itemstarts[i-1];
            nextnode[i-1]=t.itemstarts[i-1]=nodeoffsets[i];
          }
          //nextnode=nodeoffsets;
          size_t nodecount=t.itemstarts[curritem];
          alignalloc::alloc(t.parents,nodecount);
          alignalloc::alloc(t.counters,nodecount);
          alignalloc::alloc(t.freqs,curritem);
          for(item_t i=0;i<=curritem;++i) {
            counter_t allc=0;
            for (simultprojnode_t *cnode=temptrees[curritem].nodes[i];cnode;cnode=cnode->next) {
              __builtin_prefetch(cnode->next);
              index_t idx=--nextnode[i];
              //fprintf(stderr,"node %d, counter %d; ",idx,cnode->counter);
              t.parents[idx]=nodeoffsets[cnode->parentitem]+cnode->parentoffset;
              allc+=(t.counters[idx]=cnode->counter);
            }
            if (i) {
              t.freqs[i-1]=allc;
              //fprintf(stderr,"f[%d %d] ",i,allc);
            } else {
              //fprintf(stderr,"root(%d %d) ",allc,t.counters[0]);
            }
          }//for levels to copy
        }//for temp tree to copy
        log_status(0,"Finished. Starting main recursion.");
      }//doSimultProject

    };

    friend class SimultProject;

    void simultProject(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;
      uint32_t maxdepth = 0;
      while (counter_t count=inp->nextTransactionBIS(trans)) {
        transaction_count+=count;
        if (trans.size()>maxdepth) 
          maxdepth=trans.size();
        btr.addTransToTree(trans,trans.size(),buildtree,count,treeann);
      }
      SimultProject projctr;
      projctr.doSimultProject(this,maxitem,maxdepth,btr,buildtree);
    }

  public:

    NonOrdFPStructure(INPUT *_inp, item_t maxitem) {
      inp=_inp;
      switch(FIRSTLEVEL) {
      case FLBuildSingleTree: {
        buildTree(maxitem);
        break;
      }
      case FLBuildAllL1Trees: {
        buildAllL1Trees(maxitem);
        break;
      }
      case FLSimultProject: {
        simultProject(maxitem);
        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]);
    }


    ~NonOrdFPStructure() {
      alignalloc::freeifnonnull(fulltree.parents);
      alignalloc::freeifnonnull(fulltree.itemstarts);
      alignalloc::freeifnonnull(fulltree.counters);
      alignalloc::freeifnonnull(fulltree.freqs);
    }
  
    bool DINLINE checkSinglePath(fptree_t *t, item_t curritem) {
      return false;
    }

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

  }; //class nonordfpstructure

  template<class INPUT,class BUILDTREEALLOC, bool SINGLE, bool TD,
  bool PROJECT, bool PROJECTDELETECLOSED, bool PROJMERGENODES,
  FirstLevel FIRSTLEVEL, bool SPARSEAGGR> class TDNonOrdFPStructure : public NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL> {
  public:
    typedef TYPENAME NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>::fptree_t fptree_t;
    typedef TYPENAME NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>::index_t index_t;

  private:
    counter_t minsupp;

    //these will be unused if single path optimization is turned off
    counter_t *multiples;
    index_t *last;
    //these will be unused if projections are turned off
    index_t *projmap;
    index_t *projlastidx;
    //these will be used only in sparse aggregation
    index_t *sparsenodes;
    index_t **nextfreesparsenode;

    //these will be unused if operating TD mode
    blockstack<stacksingleblock<counter_t,true> > nodealloc;
    blockstack<stacksingleblock<counter_t,false> > headeralloc;
    blockstack<stacksingleblock<index_t,false> > projheaderalloc;
    blockstack<stacksingleblock<index_t,false> > projnodealloc;
    singlesalloc<fptree_t,100> treealloc;

    using NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>::l1trees;

  public:


    TDNonOrdFPStructure(INPUT *_inp, item_t maxitem, counter_t _minsupp) :      NonOrdFPStructure<INPUT,BUILDTREEALLOC,FIRSTLEVEL>(_inp,maxitem),minsupp(_minsupp) {
      if (SINGLE) {
        alignalloc::alloc(multiples,maxitem);
        alignalloc::alloc(last,maxitem);
      }
      index_t maxtreesize=0;
      if (PROJECT||SPARSEAGGR) {
        if (FIRSTLEVEL!=FLBuildSingleTree) {
          for (item_t i=0;i<maxitem;++i) { 
            if (l1trees[i].itemstarts[i]>maxtreesize) {
              maxtreesize=l1trees[i].itemstarts[i];
            }
          }
        } else {
          maxtreesize=this->fulltree.itemstarts[maxitem];
        }
      }
      if (PROJECT) {
        alignalloc::alloc(projmap,maxtreesize);
        alignalloc::alloc(projlastidx,maxtreesize);
      }
      if (SPARSEAGGR) {
        alignalloc::allocz(sparsenodes,maxtreesize);
        alignalloc::alloc(nextfreesparsenode,maxitem);
      }
    }

    ~TDNonOrdFPStructure() {
      if (SINGLE) {
        alignalloc::free(multiples);
        alignalloc::free(last);
      }
    }

    class SinglePathIterator {
    private:
      index_t nodeidx;
      item_t curritem;
    public:
      SinglePathIterator () {}
      SinglePathIterator(index_t _n, item_t _i):
        nodeidx(_n), curritem(_i) {}

      void DINLINE increment (fptree_t *tree) {
        nodeidx=tree->parents[nodeidx];
        while (nodeidx && (tree->itemstarts[curritem]>nodeidx))
          curritem--;
      }

      bool DINLINE atEnd(fptree_t *tree) {
        return (!nodeidx);
      }

      item_t DINLINE getCurrItem(fptree_t *tree) {
        return curritem;
      }

    };


    item_t DINLINE checkSinglePath(fptree_t *t, item_t curritem, item_t spdepth) {
      if (!SINGLE) {
        return 0;
      } else {
        while ((spdepth<curritem) && (multiples[spdepth]<=1))
          spdepth++;
        return spdepth;
      }
    }

    SinglePathIterator DINLINE getSinglePathIterator(fptree_t *tree, item_t curritem) {
      if (!SINGLE) {
        log_err(0,"Error: requested SinglePathIterator when singlepath optimization is not enabled");
      }
      return SinglePathIterator(last[curritem],curritem);
    }


    void DINLINE zeroDataDense(fptree_t *intr, item_t curritem) {
      //partial erase on the `data' part of the tree
      alignalloc::zerola(intr->counters,intr->itemstarts[curritem]);
      alignalloc::zerola(intr->freqs,curritem);
      if (SINGLE)
        alignalloc::zero(multiples,curritem+1);
    }
    
    void DINLINE zeroDataADense(fptree_t *intr, item_t curritem) {
      //aligned erase on the `data' part of the tree
      if (!SPARSEAGGR) 
        alignalloc::zero(intr->counters,intr->itemstarts[curritem]);
      alignalloc::zero(intr->freqs,curritem);
      if (SINGLE)
        alignalloc::zero(multiples,curritem+1);
    }

    void DINLINE aggregateSparse(index_t* itemstarts,index_t *parents, counter_t *freqs, counter_t *ocounters, counter_t *ncounters, item_t curritem) {
      for (item_t i=0;i<curritem;++i) {
        nextfreesparsenode[i]=sparsenodes+itemstarts[i];
      }
      item_t paritem=curritem;
      for(index_t nodeidx=itemstarts[curritem];nodeidx<itemstarts[curritem+1];++nodeidx) {
        if (ocounters[nodeidx]) {
          register index_t par=parents[nodeidx];
          if (par && !ncounters[parents[nodeidx]]) {
            if (itemstarts[paritem]>par) {
              do {
                --paritem;
              } while (itemstarts[paritem]>par);
            } else {
              while (itemstarts[paritem+1]<=par) ++paritem;
            }
            *(nextfreesparsenode[paritem]++)=par;
          }
          ncounters[parents[nodeidx]]+=ocounters[nodeidx];
        }
      }
      for (item_t nextitem=curritem;nextitem>0;) {
        --nextitem;//pre-decrement: workaround of unsigned int item_t and underflow
        if (SINGLE) {
          multiples[nextitem]=nextfreesparsenode[nextitem]-(sparsenodes+itemstarts[nextitem]);
          last[nextitem]=*(nextfreesparsenode[nextitem]-1);
        }
        for(index_t *pnodeidx=sparsenodes+itemstarts[nextitem];pnodeidx!=nextfreesparsenode[nextitem];++pnodeidx) {
          index_t nodeidx=*pnodeidx;
          counter_t cnt=ncounters[nodeidx];
          index_t par=parents[nodeidx];
          freqs[nextitem]+=cnt;
          if (par && !ncounters[par]) {
            if (itemstarts[paritem]>par) {
              do {
                --paritem;
              } while (itemstarts[paritem]>par);
            } else {
              while (itemstarts[paritem+1]<=par) ++paritem;
            }
            *(nextfreesparsenode[paritem]++)=par;
          }
          ncounters[par]+=cnt;
        }//for nodes of current item
      }//for next item
    } //aggregateSparse
    
    void DINLINE aggregateDense(index_t* itemstarts,index_t *parents, counter_t *freqs, counter_t *ocounters, counter_t *ncounters, item_t curritem) {
#ifdef PREFETCH      
      for(index_t nodeidx=itemstarts[curritem+1];nodeidx>itemstarts[curritem];) {
        --nodeidx;
        if (nodeidx>PREFETCHDIST)
          __builtin_prefetch(ncounters+parents[nodeidx-PREFETCHDIST]);
        ncounters[parents[nodeidx]]+=ocounters[nodeidx];  
      }
#else
      for(index_t nodeidx=itemstarts[curritem];nodeidx<itemstarts[curritem+1];++nodeidx) {
        ncounters[parents[nodeidx]]+=ocounters[nodeidx];  
      }
#endif
      for (item_t nextitem=curritem;nextitem>0;) {
        --nextitem;//pre-decrement: workaround of unsigned int item_t and underflow
#ifdef PREFETCH
        for(index_t nodeidx=itemstarts[nextitem+1]-1;nodeidx>=itemstarts[nextitem];--nodeidx) {
          if (nodeidx>PREFETCHDIST)
            __builtin_prefetch(ncounters+parents[nodeidx-PREFETCHDIST]); 
#else
        for(index_t nodeidx=itemstarts[nextitem];nodeidx<itemstarts[nextitem+1];++nodeidx) {
#endif
          register counter_t cnt=ncounters[nodeidx];
          if (cnt) {
            {
              register int par=parents[nodeidx];
              ncounters[par]+=cnt;
            }
            freqs[nextitem]+=cnt;
            if (SINGLE) {
              multiples[nextitem]++;
              last[nextitem]=nodeidx;
            }
          }//if current node nonzero
        }//for nodes of current item
      }//for next item
    } //aggregateDense

    fptree_t * DINLINE projectTree(fptree_t *intr,item_t curritem) {
      if (TD) {
        zeroDataDense(intr,curritem);
        aggregateDense(intr->itemstarts,intr->parents,intr->freqs,intr->counters,intr->counters,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);
        if (SPARSEAGGR) {
          aggregateSparse(nftree->itemstarts,nftree->parents,nftree->freqs,intr->counters,nftree->counters,curritem);

        } else {
          aggregateDense(nftree->itemstarts,nftree->parents,nftree->freqs,intr->counters,nftree->counters,curritem);
        }
        if (PROJECT) {
         if (SPARSEAGGR) 
         compactTreeSparse(nftree,curritem);
         else
         compactTree(nftree,curritem);

        }
        return nftree;
      }
    }

    inline bool DINLINE dropNode(fptree_t *t, item_t curritem, index_t nodeidx) {
      return (t->counters[nodeidx]==0) || (t->freqs[curritem]<minsupp) || (PROJECTDELETECLOSED&&(t->freqs[curritem]==t->getRootFrequency()));
    }

    //do not call this routine in TD mode -- it (destructively) modifies the fptree_t *t.
    inline void DINLINE compactTree(fptree_t *t, item_t projitem) {
      index_t nn=1; //next free node index
      index_t *newparents;
      index_t *newitemstarts;
      projheaderalloc.pushAndGetBlock(projitem+1,newitemstarts);
      projnodealloc.pushAndGetBlock(t->itemstarts[projitem],newparents);
      projmap[0]=0;
      newparents[0]=0;
      projlastidx[0]=0;
      for (item_t curritem=0; curritem<projitem; ++curritem) {
        newitemstarts[curritem]=nn;
        for (index_t nodeidx=t->itemstarts[curritem];nodeidx<t->itemstarts[curritem+1];++nodeidx) {
          if (dropNode(t,curritem,nodeidx)) {
            projmap[nodeidx]=projmap[t->parents[nodeidx]];
          } else {
            index_t newidx;
            if (PROJMERGENODES && 
                ((newidx=projlastidx[projmap[t->parents[nodeidx]]])
                 >=newitemstarts[curritem])) {
              //if there is a child of my (new) parent on this level (=with this item as the merge
              t->counters[newidx]+=t->counters[nodeidx];
            } else {
              //allocate a new node
              newidx=nn++;
              t->counters[newidx]=t->counters[nodeidx]; //newidx<=nodeidx, we won't overwrite any position we'd want to use later
              newparents[newidx]=projmap[t->parents[nodeidx]];
              projlastidx[newparents[newidx]]=newidx;
              projlastidx[newidx]=0;
            }
            projmap[nodeidx]=newidx;
          }//if drop-or-keep node
        }//for nodes at the current level
        if (SINGLE) {
          multiples[curritem]=nn-newitemstarts[curritem];
          last[curritem]=newitemstarts[curritem];
        }
      }//for items
      newitemstarts[projitem]=nn;
      t->parents=newparents;
      t->itemstarts=newitemstarts;
      t->freeelements|=fptree_t::free_structure;
    }//compactTree


    inline void DINLINE compactTreeSparse(fptree_t *t, item_t projitem) {
      index_t nn=1; //next free node index
      index_t *newparents;
      index_t *newitemstarts;
      projheaderalloc.pushAndGetBlock(projitem+1,newitemstarts);
      projnodealloc.pushAndGetBlock(t->itemstarts[projitem],newparents);
      counter_t *newcounters;
      projnodealloc.pushAndGetBlock(t->itemstarts[projitem],newcounters);
      projmap[0]=0;
      newparents[0]=0;
      projlastidx[0]=0;
      newcounters[0]=t->counters[0];
      for (item_t curritem=0; curritem<projitem; ++curritem) {
        newitemstarts[curritem]=nn;
        for(index_t *pnodeidx=sparsenodes+t->itemstarts[curritem];pnodeidx!=nextfreesparsenode[curritem];++pnodeidx) {
          index_t nodeidx=*pnodeidx;
          //        for (index_t nodeidx=t->itemstarts[curritem];nodeidx<t->itemstarts[curritem+1];++nodeidx) {
          if (dropNode(t,curritem,nodeidx)) {
            projmap[nodeidx]=projmap[t->parents[nodeidx]];
          } else {
            index_t newidx;
            if (PROJMERGENODES && 
                ((newidx=projlastidx[projmap[t->parents[nodeidx]]])
                 >=newitemstarts[curritem])) {
              //if there is a child of my (new) parent on this level (=with this item as the merge
              newcounters[newidx]+=t->counters[nodeidx];
            } else {
              //allocate a new node
              newidx=nn++;
              newcounters[newidx]=t->counters[nodeidx]; //newidx<=nodeidx, we won't overwrite any position we'd want to use later
              newparents[newidx]=projmap[t->parents[nodeidx]];
              projlastidx[newparents[newidx]]=newidx;
              projlastidx[newidx]=0;
            }
            projmap[nodeidx]=newidx;
          }//if drop-or-keep node
          t->counters[nodeidx]=0;
        }//for nodes at the current level
        if (SINGLE) {
          multiples[curritem]=nn-newitemstarts[curritem];
          last[curritem]=newitemstarts[curritem];
        }
      }//for items
      newitemstarts[projitem]=nn;
      t->parents=newparents;
      t->itemstarts=newitemstarts;
      t->freeelements|=fptree_t::free_structure;
      t->counters[0]=0;
      t->counters=newcounters;
      nodealloc.freeBlock();
    }//compactTree

    void DINLINE deallocTree(fptree_t *t, fptree_t *parent, item_t projitem) {
      //in case of TD nothing to do as there is only one tree which is global
      if (!TD) {
        if (PROJECT) {
          projheaderalloc.freeBlock();
          projnodealloc.freeBlock();
          if (SPARSEAGGR) {//allocated two blocks on projnodealloc
            projnodealloc.freeBlock();
          }
        }
        if (!PROJECT || !SPARSEAGGR) {
          nodealloc.freeBlock();
        }
        headeralloc.freeBlock();
        treealloc.free(t);
      }
    }
  }; //class TDNonOrdFPStructure


} //namespace bracz

---