trie/trie_manipulators/CandGenInfreqRemoveNopruneMerge.hpp

Go to the documentation of this file.

#ifndef CandGenInfreqRemoveNopruneMerge_HPP
#define CandGenInfreqRemoveNopruneMerge_HPP


#include "common.hpp"
#include "common/Edge.hpp"
#include "common/log.h"
#include "apriori/bodon/trie/trie_manipulators/CandidateGeneratorNoprune.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace trie
{
   template <class DF_D, class TRIE, bool NEE>
   class CandGenInfreqRemoveNopruneMerge : 
         public CandidateGeneratorNoprune<DF_D, TRIE, NEE>
   {
      protected:
         unsigned int nr_of_deleted;
         unsigned int total_nr_of_deleted;
         typedef CandidateGeneratorNoprune<DF_D, TRIE, NEE> PARENT;
      public:
         CandGenInfreqRemoveNopruneMerge( TRIE& main_trie, DF_D& df_decoder ) : 
            PARENT(main_trie, df_decoder), 
            total_nr_of_deleted(0){}


         void generateCandidate(unsigned int candidate_size);
      
         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 );



      public:
         // No public members
   };


   template <class DF_D, class TRIE, bool NEE>
   void CandGenInfreqRemoveNopruneMerge<DF_D, TRIE, NEE>::
   generateCandidate(const unsigned int candidate_size)
   {
      if(candidate_size == 3)
      {
         PARENT::nr_of_new_candidates = 0;
         if(NEE > NEE_Off)
         {
            std::vector<item_t> NEEsum;
            generateCandidateFindParentNEE( &this->main_trie, NEEsum,
                                            candidate_size -2 );
         }
         else
            generateCandidateFindParent( &this->main_trie, 
                                         candidate_size -2 );
         log_dbg(0,"Number of newly generated candidates: %d", PARENT::nr_of_new_candidates);
#if DEBUG_LEVEL >= LEVEL_DBG
            nr_of_all_candidates += nr_of_new_candidates;
#endif
      }
      else
         log_dbg(0,"This algorithm does not generate any candidate in this phase.");

   }

   template <class DF_D, class TRIE, bool NEE>
   void CandGenInfreqRemoveNopruneMerge<DF_D, TRIE, NEE>::
   deleteInfrequent( const counter_t min_supp, unsigned int candidate_size )
   {
      assert(candidate_size > 1);
      nr_of_deleted = 0;
      PARENT::nr_of_new_candidates = 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);
      log_dbg(0,"Number of newly generated candidates (in del. phase!): %d", 
              PARENT::nr_of_new_candidates);
#if DEBUG_LEVEL >= LEVEL_DBG
      nr_of_all_candidates += nr_of_new_candidates;
      total_nr_of_deleted += nr_of_deleted;
#endif
   }

   template <class DF_D, class TRIE, bool NEE>
   void CandGenInfreqRemoveNopruneMerge<DF_D, TRIE, NEE>::
   afterWorkDel()
   {
      log_dbg(0,"The total number of generated candidates (in del. p.): %d", 
              PARENT::nr_of_all_candidates);
      log_dbg(0,"The total number of infrequent candidates: %d", 
              total_nr_of_deleted);
   }

   template <class DF_D, class TRIE, bool NEE>
   void CandGenInfreqRemoveNopruneMerge<DF_D, TRIE, NEE>::
   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() )
         {
            PARENT::df_decoder.pushItem( (*itEdge).first );
            delete_infrequent_subtrie( static_cast<TRIE*>((*itEdge).second), min_supp,
                                       step_to_cand_par);
            PARENT::df_decoder.popItem();
            if( 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<TRIE*>((*itEdge).second)->getCounter() < min_supp )
            {
#if DEBUG_LEVEL >= LEVEL_DBG
                  ++nr_of_deleted;
#endif
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else
               ++itEdge;
         }
         generateCandidateAtParent(subtrie);
#if DEBUG_LEVEL >= LEVEL_DBG
         for( typename TRIE::iterator it( subtrie->edgelist.begin() );
              it != subtrie->edgelist.end(); ++it)
            nr_of_new_candidates += 
               static_cast<TRIE*>((*it).second)->edgelist.size();
#endif
      }
   }
   template <class DF_D, class TRIE, bool NEE>
   void CandGenInfreqRemoveNopruneMerge<DF_D, TRIE, NEE>::
   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( 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() );
               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 ++itEdge;
            PARENT::df_decoder.popItem();
         }
         NEEsum.resize( NEEsum.size() - subtrie->neelist.size() );
      }
      else
      {
         while( itEdge != subtrie->edgelist.end() )
         {
            if( static_cast<TRIE*>((*itEdge).second)->getCounter() < min_supp )
            {
#if DEBUG_LEVEL >= LEVEL_DBG
               ++nr_of_deleted;
#endif
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else if(static_cast<TRIE*>((*itEdge).second)->getCounter() == 
                    subtrie->getCounter())
            {
               subtrie->neelist.push_back((*itEdge).first);
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = subtrie->edgelist.erase(itEdge);
            }
            else
               ++itEdge;
         }
         generateCandidateAtParentNEE(subtrie, NEEsum);
#if DEBUG_LEVEL >= LEVEL_DBG
         for( typename TRIE::iterator it( subtrie->edgelist.begin() );
              it != subtrie->edgelist.end(); ++it)
            nr_of_new_candidates += 
               static_cast<TRIE*>((*it).second)->edgelist.size();
#endif
      }
   }
}
}
#endif

---