inhomogeneous_trie/trie_manipulators/InfreqRemover.hpp

Go to the documentation of this file.

#ifndef InfreqRemover_HPP
#define InfreqRemover_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 InfreqRemover : public ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
   {
      private:
         typedef ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
      protected:
         std::vector<Edge> extenders;
         unsigned int nr_of_deleted;
         unsigned int total_nr_of_deleted;

      public:
         InfreqRemover( TRIE& main_trie, DF_D& df_decoder,
                        LEAF_ALLOCATOR& s_alloc ) : 
            ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>(main_trie, df_decoder, s_alloc), 
            total_nr_of_deleted(0){}

         void deleteInfrequent( const counter_t min_supp,
                                unsigned int candidate_size );
         void afterWorkDel();
      protected:

         void delete_infrequent_subtrie( 
            TRIE* subtrie, const counter_t min_supp,
            unsigned int step_to_cand_par );
         void delete_infrequent_subtrieNEE( 
            TRIE* subtrie, const counter_t min_supp,
            std::vector<item_t>& NEEsum, unsigned int step_to_cand_par);

         void destroy(TRIE* subtrie);
         void destroyAndWriteNEE(TRIE* subtrie, std::vector<item_t>& NEEsum);
   };

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   deleteInfrequent( const counter_t min_supp,
                     unsigned int candidate_size )
   {
      assert(candidate_size > 2);
      nr_of_deleted = 0;
      if(NEE > NEE_Off)
      {
         std::vector<item_t> NEEsum;
         delete_infrequent_subtrieNEE( &this->main_trie, min_supp, 
                                       NEEsum, candidate_size - 1 );
         
      }
      else
         delete_infrequent_subtrie( &this->main_trie, min_supp, 
                                    candidate_size - 1 );
      log_dbg(0,"Number of infrequent candidates: %d", nr_of_deleted);
#if DEBUG_LEVEL >= LEVEL_DBG
      total_nr_of_deleted += nr_of_deleted;
#endif
   }

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   afterWorkDel()
   {
      log_dbg(0,"The total number of infrequent candidates: %d", 
              total_nr_of_deleted);
      if(!DEADENDPRUNE)
         if(NEE > NEE_Off)
         {
            std::vector<item_t> NEEsum;
            destroyAndWriteNEE(&this->main_trie, NEEsum);
         }
         else
            destroy(&this->main_trie);
   }

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   delete_infrequent_subtrie( TRIE* subtrie, const counter_t min_supp,
                              unsigned int step_to_cand_par)
   {
      typename TRIE::iterator itEdge( subtrie->edgelist.begin() );
      if(step_to_cand_par)
      {
         --step_to_cand_par;
         while( itEdge != subtrie->edgelist.end() )
         {
            delete_infrequent_subtrie( static_cast<TRIE*>((*itEdge).second), min_supp,
                                       step_to_cand_par);
            if( DEADENDPRUNE && 
                static_cast<TRIE*>((*itEdge).second)->edgelist.empty() )
            {
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else ++itEdge;
         }
      }
      else
      {
         while( itEdge != subtrie->edgelist.end() )
         {
            if( static_cast<LEAF*>((*itEdge).second)->getCounter() < min_supp )
            {
#if DEBUG_LEVEL >= LEVEL_DBG
               ++nr_of_deleted;
#endif
               PARENT::s_alloc.free(static_cast<LEAF*>((*itEdge).second));
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else
               ++itEdge;
         }
      }
   }
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   delete_infrequent_subtrieNEE( TRIE* subtrie, const counter_t min_supp,
                                 std::vector<item_t>& NEEsum,
                                 unsigned int step_to_cand_par)
   {
      typename TRIE::iterator itEdge( subtrie->edgelist.begin() );
      if(step_to_cand_par)
      {
         --step_to_cand_par;
         NEEsum.insert( NEEsum.end(), 
               subtrie->neelist.begin(), subtrie->neelist.end() );
         while( itEdge != subtrie->edgelist.end() )
         {
            PARENT::df_decoder.pushItem((*itEdge).first);
            delete_infrequent_subtrieNEE( static_cast<TRIE*>((*itEdge).second), min_supp,
                                          NEEsum, step_to_cand_par);
            if( DEADENDPRUNE && 
                static_cast<TRIE*>((*itEdge).second)->edgelist.empty() )
            {
               NEEsum.insert( NEEsum.end(), 
                              static_cast<TRIE*>((*itEdge).second)->neelist.begin(), 
                              static_cast<TRIE*>((*itEdge).second)->neelist.end() );
               if( NEEsum.size() < step_to_cand_par + 1)
               {

                  PARENT::df_decoder.writeNEE(
                     static_cast<TRIE*>((*itEdge).second)->getCounter(), NEEsum);
                  NEEsum.resize( NEEsum.size() - 
                                 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
                  delete static_cast<TRIE*>((*itEdge).second);
                  itEdge = subtrie->edgelist.erase(itEdge);
               }
               else
               {
                  NEEsum.resize( NEEsum.size() - 
                                 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
                  ++itEdge;
               }           
            }
            else ++itEdge;
            PARENT::df_decoder.popItem();
         }
         NEEsum.resize( NEEsum.size() - subtrie->neelist.size() );
      }
      else
      {
         while( itEdge != subtrie->edgelist.end() )
         {
            if( static_cast<LEAF*>((*itEdge).second)->getCounter() < min_supp )
            {
#if DEBUG_LEVEL >= LEVEL_DBG
               ++nr_of_deleted;
#endif
               PARENT::s_alloc.free(static_cast<LEAF*>((*itEdge).second));
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else if(static_cast<LEAF*>((*itEdge).second)->getCounter() == 
                    subtrie->getCounter())
            {
               subtrie->neelist.push_back((*itEdge).first);
               PARENT::s_alloc.free(static_cast<LEAF*>((*itEdge).second));
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else
               ++itEdge;
         }
      }
   }
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   destroy(TRIE* trie)
   {
      for(typename TRIE::iterator itEdge( trie->edgelist.begin()); 
          itEdge != trie->edgelist.end(); ++itEdge )
      {
         destroy( static_cast<TRIE*>((*itEdge).second) );
         delete static_cast<TRIE*>((*itEdge).second);
      }
      trie->edgelist.clear();
   }
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, 
             NEELevel NEE, bool DEADENDPRUNE>
   void InfreqRemover<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE, DEADENDPRUNE>::
   destroyAndWriteNEE(TRIE* trie, std::vector<item_t>& NEEsum)
   {
      NEEsum.insert( NEEsum.end(), 
                     trie->neelist.begin(), trie->neelist.end() );
      PARENT::df_decoder.writeNEE( trie->getCounter(), NEEsum);
      for(typename TRIE::iterator itEdge( trie->edgelist.begin()); 
          itEdge != trie->edgelist.end(); ++itEdge )
      {
         PARENT::df_decoder.pushItem((*itEdge).first);
         destroyAndWriteNEE( static_cast<TRIE*>((*itEdge).second), NEEsum );
         delete static_cast<TRIE*>((*itEdge).second);
         PARENT::df_decoder.popItem();
      }
      trie->edgelist.clear();
      NEEsum.resize( NEEsum.size() - trie->neelist.size() );
   }
}
}
#endif

---