SupportCounterLookupTransLinBin.hpp

Go to the documentation of this file.

#ifndef SupportCounterLookupTransLinBin_HPP
#define SupportCounterLookupTransLinBin_HPP

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




namespace Bodon
{
   template <class TRIE, unsigned int THRESHOLD=100>
   class SupportCounterLookupTransLinBin
   {
      public:
         SupportCounterLookupTransLinBin( ){}

         void updateCounters(
            TRIE& main_trie, const std::vector<item_t>& transaction,
            item_t candidate_size, const counter_t counter_incr)
         {
            if( candidate_size <= transaction.size() )
               findCandidates( 
                  &main_trie, transaction.end()-candidate_size+1, 
                  transaction.begin(), candidate_size,
                  counter_incr );
         }

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

         void findCandidatesSpecMerge( TRIE* subtrie,
            std::vector<item_t>::const_iterator it_basket_upper_bound,
            std::vector<item_t>::const_iterator it_basket, 
            item_t step_to_candidate,
            const counter_t counter_incr,
            typename TRIE::iterator it_edge );

         void findCandidatesMerge( TRIE* subtrie,
            std::vector<item_t>::const_iterator it_basket_upper_bound,
            std::vector<item_t>::const_iterator it_basket, 
            item_t step_to_candidate,
            const counter_t counter_incr );
   };

   template <class TRIE, unsigned int THRESHOLD> void 
   SupportCounterLookupTransLinBin<TRIE, THRESHOLD>::findCandidates( 
      TRIE* subtrie, std::vector<item_t>::const_iterator it_basket_upper_bound,
      std::vector<item_t>::const_iterator it_basket, 
      item_t step_to_candidate, const counter_t counter_incr )
   {
      --step_to_candidate;
      for( typename TRIE::iterator it_edge(subtrie->edgelist.begin());
           it_edge != subtrie->edgelist.end(); ++it_edge)
      {
         if( static_cast<unsigned int>(it_basket_upper_bound - it_basket) 
             < THRESHOLD )
         {
            findCandidatesSpecMerge( 
               subtrie, it_basket_upper_bound,
               it_basket, step_to_candidate, counter_incr, it_edge );
            break;
         }
         else
            it_basket = std::lower_bound( it_basket, it_basket_upper_bound, 
                                          (*it_edge).first);
         if(it_basket == it_basket_upper_bound)
            break;
         else
         { 
            if(*it_basket == (*it_edge).first)
            {
               if( step_to_candidate ) 
                  findCandidates( static_cast<TRIE*>((*it_edge).second),
                                  it_basket_upper_bound + 1, it_basket, 
                                  step_to_candidate, counter_incr);
               else
                  static_cast<Leaf*>((*it_edge).second)
                     ->increaseCounter( counter_incr);
               ++it_basket;
            }
         }
      }
   }
   template <class TRIE, unsigned int THRESHOLD> void 
   SupportCounterLookupTransLinBin<TRIE, THRESHOLD>::findCandidatesSpecMerge( 
      TRIE* subtrie, std::vector<item_t>::const_iterator it_basket_upper_bound,
      std::vector<item_t>::const_iterator it_basket, 
      item_t step_to_candidate, const counter_t counter_incr,
      typename TRIE::iterator it_edge )
   {
      while( it_edge != subtrie->edgelist.end() && 
             it_basket != it_basket_upper_bound )
      {
         if( (*it_edge).first < *it_basket) ++it_edge;
         else if( (*it_edge).first > *it_basket) ++it_basket;
         else
         {
            ++it_basket;
            if( step_to_candidate ) 
               findCandidatesMerge( static_cast<TRIE*>((*it_edge).second),
                                    it_basket_upper_bound + 1, it_basket, 
                                    step_to_candidate, counter_incr);
            else
               static_cast<Leaf*>((*it_edge).second)
                  ->increaseCounter( counter_incr);
            ++it_edge;
         }
      }
   }
   template <class TRIE, unsigned int THRESHOLD> void 
   SupportCounterLookupTransLinBin<TRIE, THRESHOLD>::findCandidatesMerge( 
      TRIE* subtrie, std::vector<item_t>::const_iterator it_basket_upper_bound,
      std::vector<item_t>::const_iterator it_basket, 
      item_t step_to_candidate, const counter_t counter_incr )
   {
      --step_to_candidate;
      typename TRIE::iterator it_edge(subtrie->edgelist.begin());
      while( it_edge != subtrie->edgelist.end() && 
             it_basket != it_basket_upper_bound )
      {
         if( (*it_edge).first < *it_basket) ++it_edge;
         else if( (*it_edge).first > *it_basket) ++it_basket;
         else
         {
            ++it_basket;
            if( step_to_candidate ) 
               findCandidatesMerge( static_cast<TRIE*>((*it_edge).second),
                                    it_basket_upper_bound + 1, it_basket, 
                                    step_to_candidate, counter_incr);
            else
               static_cast<Leaf*>((*it_edge).second)
                  ->increaseCounter( counter_incr);
            ++it_edge;
         }
      }
   }
}
#endif

---