SupportCounterMerge2.hpp

Go to the documentation of this file.

#ifndef SupportCounterMerge2_HPP
#define SupportCounterMerge2_HPP

#include <algorithm>
#include "common.hpp"
#include <vector>
#include "apriori/bodon/Leaf.hpp"
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
   template <class TRIE>
   class SupportCounterMerge2
   {
      private:
         typedef std::pair<item_t, std::vector<item_t>::const_iterator> SeqFirstOcc;

      public:
         SupportCounterMerge2( ){}

         void findCandidates( TRIE* subtrie,
            std::vector<item_t>::const_iterator it_transaction_upper_bound,
            std::vector<item_t>::const_iterator it_transaction, 
            item_t step_to_candidate,
            const counter_t counter_incr );


   };

   template <class TRIE> void 
   SupportCounterMerge2<TRIE>::findCandidates( 
      TRIE* subtrie, std::vector<item_t>::const_iterator it_transaction_upper_bound,
      std::vector<item_t>::const_iterator it_transaction, 
      item_t step_to_candidate, const counter_t counter_incr )
   {
      --step_to_candidate;
      vector<bool>::size_type largestEdgelabel = 
         subtrie->edgelist.largestEdgelabel();
      vector<bool>::size_type smallestEdgelabel = 
         subtrie->edgelist.smallestEdgelabel();
      vector<bool> pattern(largestEdgelabel + 1 - smallestEdgelabel, true);
      typename std::vector<SupportCounterMerge2<TRIE>::SeqFirstOcc> 
         first_occ;
      first_occ.reserve(it_transaction_upper_bound - it_transaction);
      while(it_transaction != it_transaction_upper_bound)
         if(*it_transaction <= largestEdgelabel && 
            *it_transaction >= smallestEdgelabel && 
            pattern[*it_transaction - smallestEdgelabel])
         {
            pattern[*it_transaction - smallestEdgelabel] = false;              
            first_occ.push_back(SupportCounterMerge2<TRIE>::SeqFirstOcc(
                                   *it_transaction, ++it_transaction));
         }
         else
            ++it_transaction;
      std::sort(first_occ.begin(), first_occ.end() );

      typename TRIE::iterator it_edge(subtrie->edgelist.begin());
      typename std::vector<SupportCounterMerge2<TRIE>::SeqFirstOcc>::const_iterator 
         it_transaction2(first_occ.begin());
      while( it_edge != subtrie->edgelist.end() && 
             it_transaction2 != first_occ.end() )
      {
         if( (*it_edge).first < (*it_transaction2).first ) ++it_edge;
         else if( (*it_edge).first > (*it_transaction2).first ) ++it_transaction2;
         else
         {
            if( step_to_candidate ) 
               findCandidates( static_cast<TRIE*>((*it_edge).second),
                               it_transaction_upper_bound + 1, (*it_transaction2).second, 
                               step_to_candidate, counter_incr);
            else
               static_cast<Leaf*>((*it_edge).second)->increaseCounter( counter_incr);
            ++it_transaction2;
            ++it_edge;
         }
      }
   }
}
}
#endif

---