trie/trie_manipulators/sequence/SimplePruner.hpp

Go to the documentation of this file.

#ifndef SimplePruner_HPP
#define SimplePruner_HPP

#include "common.hpp"
#include "common/Edge.hpp"
#include "apriori/bodon/trie/trie_manipulators/ManipulatorBase.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
   template <class DF_D, class TRIE>
   class SimplePruner : public ManipulatorBase<DF_D, TRIE>
   {
      protected:
         std::vector<Edge> extenders;

      public:
         SimplePruner( TRIE& main_trie, DF_D& df_decoder ) : 
            ManipulatorBase<DF_D, TRIE>(main_trie, df_decoder){}


      protected:
         int isAllSubsetFrequent( std::vector<item_t>& maybe_candidate, 
                                  const item_t new_item ) const;


         void generateCandidateAtParent( 
            TRIE* trie, std::vector<item_t>& maybe_candidate );
   };


   template <class DF_D, class TRIE> inline int 
   SimplePruner<DF_D, TRIE>::isAllSubsetFrequent( 
      std::vector<item_t>& generator, const item_t new_item ) const
   {
      assert(generator.size() > 1);
      std::vector<item_t>::iterator item_it = generator.end()-2;
      register item_t deleted_item = *item_it, temp_item;
      const TRIE* temp_trie;

      generator.erase( item_it );
      temp_trie = main_trie.isIncluded( generator, generator.begin() );
      if( temp_trie)
      { 
         if( !temp_trie->edgelist.find(new_item) )
         {
            generator.insert( item_it, deleted_item );
            return 0;
         }
      }
      else
      {
         generator.insert( item_it, deleted_item );
         return 0;
      }
      while(item_it != generator.begin())
      {
         --item_it;
         temp_item = *item_it;
         *item_it = deleted_item;
         deleted_item = temp_item;
         temp_trie = main_trie.isIncluded( generator, generator.begin() );      
         if( temp_trie)
         { 
            if( !temp_trie->edgelist.find(new_item) )
            {
               generator.insert( item_it, deleted_item );
               return 0;
            }
         }
         else
         {
            generator.insert( item_it, deleted_item );
            return 0;
         }
      }
      generator.insert( item_it, deleted_item );
      return 1;
   }


   template <class DF_D, class TRIE> inline void 
   SimplePruner<DF_D, TRIE>::
   generateCandidateAtParent(TRIE* trie, std::vector<item_t>& maybe_candidate)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() ), itEdge2;
      TRIE* toExtend;
      while( itEdge != trie->edgelist.end() )
      {
         toExtend = static_cast<TRIE*>((*itEdge).second);
         df_decoder.pushItemWithWrite( (*itEdge).first, toExtend->getCounter() );
         df_decoder.popItem();
         maybe_candidate.push_back((*itEdge).first);
         extenders.clear();
         for( itEdge2 = trie->edgelist.begin(); itEdge2 != trie->edgelist.end(); ++itEdge2 )
         {
            if( isAllSubsetFrequent( maybe_candidate, (*itEdge2).first ) == 1 )
               extenders.push_back(Edge((*itEdge2).first, new TRIE(0)));
         }
         maybe_candidate.pop_back();
         toExtend->edgelist.insert(extenders);
         ++itEdge;
      }
   }
}
}
#endif

---