SupportCounterFilter.hpp

Go to the documentation of this file.

#ifndef SupportCounterFilter_HPP
#define SupportCounterFilter_HPP

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




namespace Bodon
{
namespace dynamic_trie
{
   template <class TRIE_OEL, class TRIE_OI>
   class SupportCounterFilter
   {
      private:
         typedef Bodon::Leaf LEAF;
      public:
         SupportCounterFilter( ){}

         void updateCounters(
            TRIE_OEL& main_trie, const std::vector<item_t>& transaction,
            item_t candidate_size, const counter_t counter_incr,
            std::vector<unsigned int>& filter)
         {
            if( candidate_size <= transaction.size() )
               findCandidates( 
                  &main_trie, transaction.end()-candidate_size+1, 
                  transaction.begin(), candidate_size,
                  counter_incr, filter );
         }
      protected:
         unsigned int findCandidates( TRIE_OEL* 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,
            std::vector<unsigned int>& filter );

         unsigned int findCandidates( TRIE_OI* 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,
            std::vector<unsigned int>& filter );
   };

   template <class TRIE_OEL, class TRIE_OI> unsigned int
   SupportCounterFilter<TRIE_OEL, TRIE_OI>::findCandidates( 
      TRIE_OEL* 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,
      std::vector<unsigned int>& filter )
   {
      --step_to_candidate;
      typename TRIE_OEL::iterator it_edge(subtrie->edgelist.begin());
      unsigned int return_value = 0;
      if( step_to_candidate ) 
      {
         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;
               unsigned int local_return_value;
               if(static_cast<LEAF*>((*it_edge).second)->getCounter() & TWO_POW31)
                  local_return_value = 
                     findCandidates( static_cast<TRIE_OEL*>((*it_edge).second),
                                     it_basket_upper_bound + 1, it_basket, 
                                     step_to_candidate, counter_incr, filter);
               else
                  local_return_value = 
                     findCandidates( static_cast<TRIE_OI*>((*it_edge).second),
                                     it_basket_upper_bound + 1, it_basket, 
                                     step_to_candidate, counter_incr, filter);
               return_value += local_return_value;
               filter[(*it_edge).first] += local_return_value;
               ++it_edge;
            }
         }
      }
      else
      {
         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;
               static_cast<LEAF*>((*it_edge).second)
                  ->increaseCounter( counter_incr);
               ++filter[(*it_edge).first];
               ++return_value;
               ++it_edge;
            }
         }
      }
      return return_value;
   }

   template <class TRIE_OEL, class TRIE_OI> unsigned int 
   SupportCounterFilter<TRIE_OEL, TRIE_OI>::findCandidates( 
      TRIE_OI* 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,
      std::vector<unsigned int>& filter )
   {
      --step_to_candidate;
      void* subsubtrie;
      item_t largest_label = subtrie->edgelist.largestEdgelabel();
      unsigned int return_value = 0;
      if( step_to_candidate ) 
      {
         while( it_basket != it_basket_upper_bound && *it_basket <= largest_label)
         {
            subtrie->edgelist.lookupNoUppercheck(*it_basket, subsubtrie);
            if(subsubtrie)
            {
               unsigned int local_return_value;
               if(static_cast<LEAF*>(subsubtrie)->getCounter() & TWO_POW31)
                  local_return_value = 
                     findCandidates( static_cast<TRIE_OEL*>(subsubtrie),
                                     it_basket_upper_bound + 1, it_basket + 1, 
                                     step_to_candidate, counter_incr, filter );
               else
                  local_return_value = 
                     findCandidates( static_cast<TRIE_OI*>(subsubtrie),
                                     it_basket_upper_bound + 1, it_basket + 1, 
                                     step_to_candidate, counter_incr, filter );
               return_value += local_return_value;
               filter[*it_basket] += local_return_value;               
            }
            ++it_basket;

         }
      }
      else
      {
         while( it_basket != it_basket_upper_bound && *it_basket <= largest_label)
         {
            subtrie->edgelist.lookupNoUppercheck(*it_basket, subsubtrie);
            if(subsubtrie)
            {
               static_cast<LEAF*>(subsubtrie)
                  ->increaseCounter(counter_incr);
               ++return_value;
               ++filter[*it_basket];
            }
            ++it_basket;
         }
      }
      return return_value;
   }
}
}
#endif

---