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




namespace Bodon
{
namespace trie
{
   template <class DF_D, class TRIE, 
             class TRIE_ALLOCATOR = NewWrapperAlloc<TRIE>, bool NEE= true>
   class SimplePruner : public Bodon::inhomogeneous_trie::ManipulatorBase<
      DF_D, TRIE, TRIE_ALLOCATOR>
   {
      private:
         typedef Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, TRIE_ALLOCATOR> PARENT;
      protected:
         std::vector<Edge> extenders;

      public:
         SimplePruner( TRIE& main_trie, DF_D& df_decoder,
                       TRIE_ALLOCATOR& s_alloc ) : 
            Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, TRIE_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 );
         void generateCandidateAtParentNEE( 
            TRIE* trie, std::vector<item_t>& maybe_candidate,
            std::vector<item_t>& NEEsum );
   };


   template <class DF_D, class TRIE, class TRIE_ALLOCATOR, bool NEE> inline int 
   SimplePruner<DF_D, TRIE, TRIE_ALLOCATOR, NEE>::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 = PARENT::main_trie.isIncluded( generator, generator.begin() );
      if( temp_trie)
      { 
         if( !temp_trie->edgelist.find(new_item) )
         {
            generator.insert( item_it, deleted_item );
            if(NEE)
            {
               if( temp_trie->neeFind(new_item) ) 
                  return 2;
               else 
                  return 0;            
            }
            else 
               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 );
               if(NEE)
               {
                  if( temp_trie->neeFind(new_item) ) 
                     return 2;
                  else 
                     return 0;         
               }
               else 
                  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 TRIE_ALLOCATOR, bool NEE> inline void 
   SimplePruner<DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
   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);
         PARENT::df_decoder.pushItemWithWrite( (*itEdge).first, toExtend->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<TRIE*>(extenders.back().second)->setCounter(0);
            }
         }
         maybe_candidate.pop_back();
         if(extenders.empty())
         {
            delete toExtend;
            itEdge = trie->edgelist.erase(itEdge);
         }
         else 
         {
            toExtend->edgelist.insert(extenders);
            ++itEdge;
         }
      }
   }

   template <class DF_D, class TRIE, class TRIE_ALLOCATOR, bool NEE> inline void 
   SimplePruner<DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
   generateCandidateAtParentNEE( TRIE* trie, std::vector<item_t>& maybe_candidate,
                                 std::vector<item_t>& NEEsum )
   {
      NEEsum.insert( NEEsum.end(), 
                     trie->neelist.begin(), trie->neelist.end() );
      typename TRIE::iterator itEdge( trie->edgelist.begin() ), itEdge2;
      TRIE* toExtend;
      while( itEdge != trie->edgelist.end() )
      {
         toExtend = static_cast<TRIE*>((*itEdge).second);
         maybe_candidate.push_back((*itEdge).first);
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         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<TRIE*>(extenders.back().second)->setCounter(0);
                  break;
               case 2: toExtend->neelist.push_back((*itEdge2).first);break;
            }                            
         }
         maybe_candidate.pop_back();
         if(extenders.empty() && NEEsum.size() < 1 && toExtend->neelist.empty() )
         {
            PARENT::df_decoder.pushItemWithWrite( (*itEdge).first,
                                          toExtend->getCounter() );
            PARENT::df_decoder.popItem();
            delete toExtend;
            itEdge = trie->edgelist.erase(itEdge);
         }
         else 
         {
            toExtend->edgelist.insert(extenders);
            ++itEdge;
         }
      }
      NEEsum.resize( NEEsum.size() - trie->neelist.size() );
   }
}
}
#endif

---