inhomogeneous_trie/trie_manipulators/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 inhomogeneous_trie
{
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE = true>
   class SimplePruner : public ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
   {
      protected:
         typedef ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
         std::vector<Edge> extenders;
         vector<item_t> leaf_neelist;
         std::vector<Edge> replace_list;

         bool is_there_any_new_candidate;

      public:
         SimplePruner( TRIE& main_trie, DF_D& df_decoder, 
                       LEAF_ALLOCATOR& s_alloc ) : 
            PARENT(main_trie, df_decoder, s_alloc){}


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


         void generateCandidateAtParent( 
            TRIE* trie, std::vector<item_t>& maybe_candidate );
         void generateCandidateAtParentNEE( 
            TRIE* trie, std::vector<item_t>& maybe_candidate,
            std::vector<item_t>& NEEsum );
         void generateCandidateAtParentNEENoDeadend( 
            TRIE* trie, std::vector<item_t>& maybe_candidate );
   };
   
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE> 
   inline int SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   helper_func( const TRIE* temp_trie, const item_t new_item) const 
   {           
      if(NEE > NEE_Off && temp_trie->neeFind(new_item))
      {
         if(NEE == NEE_Level1)
            return 1;
         else
         {
//          std::cout<<"nonprefix: "<<new_item<<std::endl;
            return 2;          
         }
      }
      else 
         return 0;             
   }


   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE> 
   inline int SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   isAllSubsetFrequent( std::vector<item_t>& generator, const item_t new_item ) const
   {
      assert(itemset.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 = this->main_trie.isIncluded( generator, generator.begin() );
      if( temp_trie)
      { 
         if( !temp_trie->edgelist.find(new_item) )
         {
            generator.insert( item_it, deleted_item );
            return helper_func(temp_trie, new_item);
         }
      }
      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 = this->main_trie.isIncluded( generator, generator.begin() );      
         if( temp_trie)
         { 
            if( !temp_trie->edgelist.find(new_item) )
            {
               generator.insert( item_it, deleted_item );
               return helper_func(temp_trie, new_item);
            }
         }
         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, 
          NEELevel NEE, bool DEADENDPRUNE> inline void 
   SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   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);
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         for( ; 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())
         {
            toExtend = new TRIE(toExtendAsLeaf->getCounter());
            replace_list.push_back(Edge((*itEdge).first, toExtend));
            toExtend->edgelist.insert(extenders);
            if( !DEADENDPRUNE)
               is_there_any_new_candidate = true;

         }
         PARENT::s_alloc.free(toExtendAsLeaf);
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE> inline void 
   SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   generateCandidateAtParentNEE( TRIE* trie, std::vector<item_t>& maybe_candidate,
                                 std::vector<item_t>& NEEsum )
   {
      typename TRIE::iterator itEdge2;
      LEAF* toExtendAsLeaf;
      TRIE* toExtend;
      replace_list.clear();
      for( typename TRIE::iterator itEdge( trie->edgelist.begin() ); 
           itEdge != trie->edgelist.end(); ++itEdge )
      {
         maybe_candidate.push_back((*itEdge).first);
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         leaf_neelist.clear();
         toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
         for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
         {
            switch (isAllSubsetFrequent( maybe_candidate, (*itEdge2).first ))
            {
               case 1:
                  extenders.push_back(Edge((*itEdge2).first, PARENT::s_alloc.allocate()));
                  static_cast<LEAF*>(extenders.back().second)->setCounter(0);
                  break;
               case 2: 
                  leaf_neelist.push_back((*itEdge2).first);
                  break;
            }                            
         }
         maybe_candidate.pop_back();
         if(extenders.empty() && leaf_neelist.empty() && 
            ( NEE == NEE_Full  || 
              NEE == NEE_Level1 && PARENT::df_decoder.EEListEmpty()) )

         {
            PARENT::df_decoder.pushItemWithWrite( 
               (*itEdge).first, toExtendAsLeaf->getCounter() );
            PARENT::df_decoder.popItem();
         }
         else 
         {
            toExtend = new TRIE(toExtendAsLeaf->getCounter());
            toExtend->edgelist.insert(extenders);
            toExtend->neePushBackSorted( leaf_neelist );
            replace_list.push_back(Edge((*itEdge).first, toExtend));

         }
         PARENT::s_alloc.free(toExtendAsLeaf);
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE> inline void 
   SimplePruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   generateCandidateAtParentNEENoDeadend( 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 )
      {
         maybe_candidate.push_back((*itEdge).first);
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         leaf_neelist.clear();
         toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
         for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
         {
            switch (isAllSubsetFrequent( maybe_candidate, (*itEdge2).first ))
            {
               case 1:
                  extenders.push_back(Edge((*itEdge2).first, PARENT::s_alloc.allocate()));
                  static_cast<LEAF*>(extenders.back().second)->setCounter(0);
                  break;
               case 2: 
                  leaf_neelist.push_back((*itEdge2).first);
                  break;
            }                            
         }
         maybe_candidate.pop_back();
         toExtend = new TRIE(toExtendAsLeaf->getCounter());
         toExtend->edgelist.insert(extenders);
         toExtend->neePushBackSorted( leaf_neelist );
         replace_list.push_back(Edge((*itEdge).first, toExtend));
         is_there_any_new_candidate = true;
         PARENT::s_alloc.free(toExtendAsLeaf);
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }
}
}
#endif

---