sequence/support_counter/SupportCounterMerge.hpp

Go to the documentation of this file.

#ifndef SupportCounterMerge_HPP
#define SupportCounterMerge_HPP

#include "common.hpp"
#include <vector>
#include "apriori/bodon/Leaf.hpp"
#include <algorithm>

//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
   template <class TRIE>
   class SupportCounterMerge
   {
      private:
         class SeqFirstOcc : public std::pair<item_t, std::vector<item_t>::const_iterator>
         {
            public:
               SeqFirstOcc(item_t item, std::vector<item_t>::const_iterator it) :
                  std::pair<item_t, std::vector<item_t>::const_iterator>(item, it){}
 
/*             bool operator<(const SeqFirstOcc& x) const
               {
                  return first < x.first;
                  }*/
               bool operator==(const SeqFirstOcc& x) const
               {
                  return first == x.first;
               }
         };

      public:
         SupportCounterMerge( ){}

         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 
   SupportCounterMerge<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();

      typename std::vector<SupportCounterMerge<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 )
            first_occ.push_back(SupportCounterMerge<TRIE>::SeqFirstOcc(
                                   *it_transaction, ++it_transaction));
         else
            ++it_transaction;
//       std::stable_sort(first_occ.begin(), first_occ.end() );
      std::sort(first_occ.begin(), first_occ.end() );
      first_occ.erase( std::unique(first_occ.begin(), first_occ.end() ), 
                       first_occ.end() );
         
      typename TRIE::iterator it_edge(subtrie->edgelist.begin());
      typename std::vector<SupportCounterMerge<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

---