SupportCounterLookupTransOffsetIndex.hpp

Go to the documentation of this file.

#ifndef SupportCounterLookupTransOffsetIndex_HPP
#define SupportCounterLookupTransOffsetIndex_HPP

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




namespace Bodon
{
   template <class TRIE>
   class SupportCounterLookupTransOffsetIndex
   {
      public:
         SupportCounterLookupTransOffsetIndex( ){}
         
         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() )
            {
            const item_t offset = transaction.front();
            std::vector<size_t> trans_vector(transaction.back() - offset + 1, 0);

            for(std::vector<item_t>::const_iterator it_basket = transaction.begin();
                it_basket != transaction.end(); ++it_basket)
               trans_vector[*it_basket - offset] = it_basket - transaction.begin() +1;

// We have to find the first label of the root that is greater than the offset.
// As soon as such label is found, we know that all other labels that 
// will be tested in the recursion are greater than the offset.
            std::vector<item_t>::const_iterator 
               it_basket_upper_bound = transaction.end()-candidate_size+1;
            size_t index_upper_bound = transaction.size()-candidate_size+3;
            --candidate_size;
            typename TRIE::iterator it_edge(main_trie.edgelist.begin());
            while( it_edge != main_trie.edgelist.end() && (*it_edge).first < offset )
               ++it_edge;
            while( it_edge != main_trie.edgelist.end() && 
                   (*it_edge).first < *it_basket_upper_bound )
            {
               if( trans_vector[(*it_edge).first - offset] )
                  if( candidate_size ) 
                     findCandidatesAssist( static_cast<TRIE*>((*it_edge).second),
                                           offset, trans_vector, index_upper_bound,
                                           candidate_size, counter_incr);
                  else
                     static_cast<Leaf*>((*it_edge).second)
                        ->increaseCounter( counter_incr);
               ++it_edge;
            }
            }
         }

      protected:
         void findCandidatesAssist( 
            TRIE* subtrie, const item_t offset,
            const std::vector<size_t>& trans_vector, size_t index_upper_bound,
            item_t step_to_candidate, const counter_t counter_incr );
         
   };

   template <class TRIE> void 
   SupportCounterLookupTransOffsetIndex<TRIE>::findCandidatesAssist( 
      TRIE* subtrie, const item_t offset, const std::vector<size_t>& trans_vector,
      const size_t index_upper_bound, item_t step_to_candidate, 
      const counter_t counter_incr )
   {
      --step_to_candidate;
      typename TRIE::iterator it_edge(subtrie->edgelist.begin());
      if( step_to_candidate ) 
      {
         while( it_edge != subtrie->edgelist.end() && 
                (*it_edge).first < trans_vector.size() + offset)
         {
            if( trans_vector[(*it_edge).first - offset] )
               if( trans_vector[(*it_edge).first - offset] < index_upper_bound)
                  findCandidatesAssist( static_cast<TRIE*>((*it_edge).second),
                                        offset, trans_vector, index_upper_bound+1,
                                        step_to_candidate, counter_incr);
               else
                  break;
            ++it_edge;
         }
      }
      else
      {
         while( it_edge != subtrie->edgelist.end() && 
                (*it_edge).first < trans_vector.size() + offset)
         {
            if( trans_vector[(*it_edge).first - offset] )
               if( trans_vector[(*it_edge).first - offset] < index_upper_bound)
                  static_cast<Leaf*>((*it_edge).second)
                     ->increaseCounter( counter_incr);
               else
                  break;
            ++it_edge;
         }
      }
   }
}
#endif

---