SupportCounterIterArray.hpp

Go to the documentation of this file.

#ifndef SupportCounterIterArray_HPP
#define SupportCounterIterArray_HPP

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




namespace Bodon
{
namespace sequence
{
   template <class TRIE>
   class SupportCounterIterArray
   {
      public:
         SupportCounterIterArray( ){}

      public:
         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 );
      private:
         typedef std::vector<std::vector<item_t>::const_iterator> iter_vector_t;
         typedef std::vector< iter_vector_t > iter_array_t;
         
         void findCandidatesAssist( 
            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,
            std::vector< iter_vector_t::const_iterator >& first_occurences, 
            const std::vector< iter_vector_t::const_iterator >& iter_ends );

   };

   template <class TRIE> void 
   SupportCounterIterArray<TRIE>::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 )
   {
      iter_array_t iter_array;
      for( std::vector<item_t>::const_iterator it_basket2 = it_basket; 
           it_basket2 != it_basket_upper_bound + step_to_candidate -1; 
           ++it_basket2)
      {
         if(*it_basket2 >= iter_array.size())
            iter_array.resize(*it_basket2 + 1);
         iter_array[*it_basket2].push_back(it_basket2);        
      }
      std::vector< iter_vector_t::const_iterator > first_occurences, iter_ends;
      first_occurences.reserve(iter_array.size());
      iter_ends.reserve(iter_array.size());
      for(iter_array_t::const_iterator it_first_occ = iter_array.begin(); 
         it_first_occ != iter_array.end(); ++it_first_occ)
      {
         first_occurences.push_back((*it_first_occ).begin());
         iter_ends.push_back((*it_first_occ).end());
      }
      findCandidatesAssist( subtrie, it_basket_upper_bound, it_basket, 
                            step_to_candidate, counter_incr, 
                            first_occurences, iter_ends );
   }

   template <class TRIE> void 
   SupportCounterIterArray<TRIE>::findCandidatesAssist( 
      TRIE* subtrie, std::vector<item_t>::const_iterator it_basket_upper_bound,
      const std::vector<item_t>::const_iterator it_basket, 
      item_t step_to_candidate, const counter_t counter_incr,
      std::vector< iter_vector_t::const_iterator >& first_occurences, 
      const std::vector< iter_vector_t::const_iterator >& iter_ends )
   {
      --step_to_candidate;
      iter_vector_t::const_iterator first_occurenc_origin;
      std::vector<item_t>::const_iterator it_basket_next;
      for( typename TRIE::iterator it_edge(subtrie->edgelist.begin()); 
           it_edge != subtrie->edgelist.end(); ++it_edge)
      {
         if( (*it_edge).first < first_occurences.size() && 
             first_occurences[(*it_edge).first] != iter_ends[(*it_edge).first])
         {
            first_occurenc_origin = first_occurences[(*it_edge).first];
            while(*(first_occurences[(*it_edge).first]) < it_basket)
            {
               ++first_occurences[(*it_edge).first];
               if( first_occurences[(*it_edge).first] == iter_ends[(*it_edge).first] )
                  break;
            }

            if(first_occurences[(*it_edge).first] != iter_ends[(*it_edge).first] &&
               *(first_occurences[(*it_edge).first]) < it_basket_upper_bound)
            {
               it_basket_next = *(first_occurences[(*it_edge).first]) + 1;
               ++first_occurences[(*it_edge).first];
               if( step_to_candidate ) 
                  findCandidatesAssist( 
                     static_cast<TRIE*>((*it_edge).second), it_basket_upper_bound + 1, 
                     it_basket_next, step_to_candidate, counter_incr, 
                     first_occurences, iter_ends );
               else
                  static_cast<Leaf*>((*it_edge).second)->increaseCounter(counter_incr);
            }
            first_occurences[(*it_edge).first] = first_occurenc_origin;
         }
      }
   }
}
}
#endif

---