inhomogeneous_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/inhomogeneous_trie/trie_manipulators/ManipulatorBase.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
namespace inhomogeneous_trie
{
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   class SimplePruner : public 
   Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
   {
      private:
         typedef Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
      protected:
         std::vector<Edge> extenders;
         std::vector<Edge> replace_list;

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


      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, class LEAF, class LEAF_ALLOCATOR> inline int 
   SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::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 = PARENT::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 = PARENT::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, class LEAF, class LEAF_ALLOCATOR> inline void 
   SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   generateCandidateAtParent(TRIE* trie, std::vector<item_t>& maybe_candidate)
   {
      typename TRIE::iterator itEdge2;
      LEAF* toExtendAsLeaf;
      TRIE* toExtend;
      replace_list.clear();
      for( typename TRIE::iterator itEdge( trie->edgelist.begin() ); 
           itEdge != trie->edgelist.end(); ++itEdge )
      {
         toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
         PARENT::df_decoder.pushItemWithWrite( (*itEdge).first, toExtendAsLeaf->getCounter() );
         PARENT::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, PARENT::s_alloc.allocate()));
               static_cast<LEAF*>(extenders.back().second)->setCounter(0);
            }
         }
         maybe_candidate.pop_back();
         if(extenders.empty())
         {
            toExtendAsLeaf->setCounter(0);
            replace_list.push_back(Edge((*itEdge).first, toExtendAsLeaf));
         }
         else
         {
            toExtend = new TRIE(toExtendAsLeaf->getCounter());
            PARENT::s_alloc.free(toExtendAsLeaf);
            replace_list.push_back(Edge((*itEdge).first, toExtend));
            toExtend->edgelist.insert(extenders);
         }
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }
}
}
}
#endif

---