inhomogeneous_trie/trie_manipulators/sequence/CandidateGeneratorPrune.hpp

Go to the documentation of this file.

#ifndef CandidateGeneratorPrune_HPP
#define CandidateGeneratorPrune_HPP

#include "common.hpp"
#include "common/Edge.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
namespace inhomogeneous_trie
{
   template <class P, class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   class CandidateGeneratorPrune : public P
   {
      protected:
         unsigned int nr_of_new_candidates;
         unsigned int nr_of_all_candidates;
      public:
         CandidateGeneratorPrune( TRIE& main_trie, DF_D& df_decoder,
                                  LEAF_ALLOCATOR& s_alloc ) :
            P(main_trie, df_decoder, s_alloc), 
            nr_of_all_candidates(0){}


         void generateCandidate(unsigned int candidate_size);
      
         void afterWorkCandGen();
      protected:

         void generateCandidateFindParent( 
            TRIE* trie, std::vector<item_t>& maybe_candidate,
            unsigned int step_to_freq_par);
         void removeNonCandPaths( TRIE* trie, unsigned int step_to_freq);
   };


   template <class P, class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   generateCandidate(unsigned int candidate_size)
   {
      assert(candidate_size > 1);
      nr_of_new_candidates = 0;
      std::vector<item_t> maybe_candidate;
      generateCandidateFindParent( &this->main_trie, maybe_candidate,
                                   candidate_size -2 );
      removeNonCandPaths(&this->main_trie, candidate_size - 2);
      log_dbg(0,"Number of newly generated candidates: %d", 
              nr_of_new_candidates);

#if DEBUG_LEVEL >= LEVEL_DBG
      nr_of_all_candidates += nr_of_new_candidates;
#endif
   }
   template <class P, class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   afterWorkCandGen()
   {
      log_dbg(0,"The total number of generated candidates (in del. p.): %d", 
              nr_of_all_candidates);
   }

   template <class P, class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   generateCandidateFindParent( TRIE* trie, 
                                std::vector<item_t>& maybe_candidate,
                                unsigned int step_to_freq_par)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() );
      if(step_to_freq_par)
      {
         --step_to_freq_par;
         while( itEdge != trie->edgelist.end() )
         {
            maybe_candidate.push_back((*itEdge).first);
            P::df_decoder.pushItem( (*itEdge).first );
            generateCandidateFindParent( static_cast<TRIE*>((*itEdge).second), 
                                         maybe_candidate,
                                         step_to_freq_par);
            P::df_decoder.popItem();
            maybe_candidate.pop_back();
            ++itEdge;
         }
      }
      else
      {
         generateCandidateAtParent(trie, maybe_candidate);
#if DEBUG_LEVEL >= LEVEL_DBG
         for( typename TRIE::iterator it( trie->edgelist.begin() );
              it != trie->edgelist.end(); ++it)
            nr_of_new_candidates += 
               static_cast<TRIE*>((*it).second)->edgelist.size();
#endif
      }
   }

   template <class P, class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   removeNonCandPaths( TRIE* trie, unsigned int step_to_freq_par)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() );
      if(step_to_freq_par)
      {
         while( itEdge != trie->edgelist.end() )
         {
            removeNonCandPaths( static_cast<TRIE*>((*itEdge).second), 
                                step_to_freq_par-1);
            if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
            {
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = trie->edgelist.erase(itEdge);
            }
            else ++itEdge;
         }
      }
      else
      {
         while( itEdge != trie->edgelist.end() )
         {
            if( static_cast<LEAF*>((*itEdge).second)->getCounter() == 0)
            {
               P::s_alloc.free(static_cast<LEAF*>((*itEdge).second));
               itEdge = trie->edgelist.erase(itEdge);          
            }
            else ++itEdge;
         }
      }
   }
}
}
}
#endif

---