dynamic_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 dynamic_trie
{
   template <class DF_D, class TRIE_OEL, class TRIE_OI, class LEAF, 
             class LEAF_ALLOCATOR, NEELevel NEE>
   class SimplePruner : public Bodon::inhomogeneous_trie::
         ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR>
   {
      protected:
         std::vector<Edge> extenders;
         std::vector<item_t> leaf_neelist;
         std::vector<Edge> replace_list;
         unsigned int nr_of_new_candidates;
         unsigned int nr_of_nonprefix_equiitem;
         typedef Bodon::inhomogeneous_trie::
         ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR> PARENT;

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


      protected:
         template <class TRIE> const void* isIncluded( 
            const TRIE* trie, const std::vector<item_t>& an_itemset, 
            std::vector<item_t>::const_iterator item_it ) const;

         template <class TRIE> 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;


         template <class TRIE> void generateCandidateAtParent( 
            TRIE* trie, std::vector<item_t>& maybe_candidate );
         template <class TRIE> void generateCandidateAtParentNEE( 
            TRIE* trie, std::vector<item_t>& maybe_candidate );
   };
   template <class DF_D, class TRIE_OEL, class TRIE_OI, 
             class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> 
   template <class TRIE> const void* 
   SimplePruner<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_ALLOCATOR, NEE>::
   isIncluded( const TRIE* trie, const std::vector<item_t>& an_itemset, 
               std::vector<item_t>::const_iterator item_it ) const
   {
      if( item_it == an_itemset.end() )
         return static_cast<const void*>(trie);
      else
      {
         void* subtrie;
         subtrie = trie->edgelist.find(*item_it);
         if(subtrie)
         {
            if( static_cast<LEAF*>(subtrie)->getCounter() & TWO_POW31 )
               return isIncluded(static_cast<TRIE_OEL*>(subtrie), an_itemset, ++item_it);
            else
               return isIncluded(static_cast<TRIE_OI*>(subtrie), an_itemset, ++item_it);          
         }
         else 
            if(NEE == NEE_Level1 && trie->neeFind(*item_it) )
               return isIncluded(trie, an_itemset, ++item_it);    
            else
               return NULL;
      }
   }

   template <class DF_D, class TRIE_OEL, class TRIE_OI, 
             class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> 
   template <class TRIE> inline int 
   SimplePruner<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_ALLOCATOR, NEE>::
   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_OEL, class TRIE_OI, 
             class LEAF, class LEAF_ALLOCATOR, NEELevel NEE > 
   inline int SimplePruner<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_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 void* temp_trie;

      generator.erase( item_it );
      temp_trie = isIncluded( &this->main_trie, generator, generator.begin() );
      if( temp_trie)
      { 
         if( static_cast<const LEAF*>(temp_trie)->getCounter() & TWO_POW31 )
         {
            if( !static_cast<const TRIE_OEL*>(temp_trie)->edgelist.find(new_item) )
            {
               generator.insert( item_it, deleted_item );
               return helper_func(static_cast<const TRIE_OEL*>(temp_trie), new_item);
            }
         }
         else
         {
            if( !static_cast<const TRIE_OI*>(temp_trie)->edgelist.find(new_item) )
            {
               generator.insert( item_it, deleted_item );
               return helper_func(static_cast<const TRIE_OI*>(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 = isIncluded( &this->main_trie, generator, generator.begin() );      
         if( temp_trie)
         { 
            if( static_cast<const LEAF*>(temp_trie)->getCounter() & TWO_POW31 )
            {
               if( !static_cast<const TRIE_OEL*>(temp_trie)->edgelist.find(new_item) )
               {
                  generator.insert( item_it, deleted_item );
                  return helper_func(static_cast<const TRIE_OEL*>(temp_trie), new_item);
               }
            }
            else
            {
               if( !static_cast<const TRIE_OI*>(temp_trie)->edgelist.find(new_item) )
               {
                  generator.insert( item_it, deleted_item );
                  return helper_func(static_cast<const TRIE_OI*>(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_OEL, class TRIE_OI, 
             class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> 
   template <class TRIE> inline void 
   SimplePruner<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_ALLOCATOR, NEE>::
   generateCandidateAtParent(TRIE* trie, std::vector<item_t>& maybe_candidate)
   {
      typename TRIE::iterator itEdge2;
      LEAF* toExtendAsLeaf;
      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())
         {
            if( 2 * extenders.size() < extenders.back().first - extenders.front().first + 3 )
            {
               TRIE_OEL* toExtend = new TRIE_OEL(toExtendAsLeaf->getCounter() | TWO_POW31);
               replace_list.push_back(Edge((*itEdge).first, toExtend));
               toExtend->edgelist.insert(extenders);
            }
            else
            {
               TRIE_OI* toExtend = new TRIE_OI(toExtendAsLeaf->getCounter() );
               replace_list.push_back(Edge((*itEdge).first, toExtend));
               toExtend->edgelist.insert(extenders);
            }
#if DEBUG_LEVEL >= LEVEL_INFO
               nr_of_new_candidates +=extenders.size();
#endif
         }
         PARENT::s_alloc.free(toExtendAsLeaf);
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }

   template <class DF_D, class TRIE_OEL, class TRIE_OI, 
             class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> 
   template <class TRIE> inline void 
   SimplePruner<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_ALLOCATOR, NEE>::
   generateCandidateAtParentNEE( TRIE* trie, std::vector<item_t>& maybe_candidate )
   {
      typename TRIE::iterator itEdge2;
      LEAF* toExtendAsLeaf;
      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 
         {
            if( extenders.empty() || 
                2 * extenders.size() < extenders.back().first - extenders.front().first + 3 )
            {
               TRIE_OEL* toExtend = new TRIE_OEL(toExtendAsLeaf->getCounter() | TWO_POW31);
               toExtend->edgelist.insert(extenders);
               toExtend->neePushBackSorted( leaf_neelist );
               replace_list.push_back(Edge((*itEdge).first, toExtend));
            }
            else
            {
               TRIE_OI* toExtend = new TRIE_OI(toExtendAsLeaf->getCounter());
               toExtend->edgelist.insert(extenders);
               toExtend->neePushBackSorted( leaf_neelist );
               replace_list.push_back(Edge((*itEdge).first, toExtend));
            }
#if DEBUG_LEVEL >= LEVEL_INFO
               nr_of_new_candidates +=extenders.size();
               nr_of_nonprefix_equiitem += leaf_neelist.size();
#endif

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

---