00001 #ifndef CandidateGeneratorPrune_HPP
00002 #define CandidateGeneratorPrune_HPP
00003
00004
00005 #include "common.hpp"
00006 #include "common/Edge.hpp"
00007 #include "common/allocators.hpp"
00008 #include <vector>
00009
00010
00011
00012
00013
00014
00015 namespace Bodon
00016 {
00017 template <class P, class DF_D, class TRIE,
00018 class TRIE_ALLOCATOR = NewWrapperAlloc<TRIE>, NEELevel NEE = NEE_Full>
00019 class CandidateGeneratorPrune : public P
00020 {
00021 protected:
00022 unsigned int nr_of_new_candidates;
00023 unsigned int nr_of_all_candidates;
00024 public:
00025 CandidateGeneratorPrune( TRIE& main_trie, DF_D& df_decoder,
00026 TRIE_ALLOCATOR& s_alloc ) :
00027 P(main_trie, df_decoder, s_alloc),
00028 nr_of_all_candidates(0){}
00029
00030
00036 void generateCandidate(unsigned int candidate_size);
00037
00038 void afterWorkCandGen();
00039 protected:
00040
00042 void generateCandidateFindParent(
00043 TRIE* trie, std::vector<item_t>& maybe_candidate,
00044 unsigned int step_to_freq_par);
00045 void generateCandidateFindParentNEE(
00046 TRIE* trie, std::vector<item_t>& maybe_candidate,
00047 std::vector<item_t>& NEEsum,
00048 unsigned int step_to_freq_par);
00049 };
00050
00051
00052 template <class P, class DF_D, class TRIE, class TRIE_ALLOCATOR, NEELevel NEE>
00053 void CandidateGeneratorPrune<P, DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
00054 generateCandidate(unsigned int candidate_size)
00055 {
00056 assert(candidate_size > 1);
00057 nr_of_new_candidates = 0;
00058 std::vector<item_t> maybe_candidate;
00059 if(NEE > NEE_Off)
00060 {
00061 std::vector<item_t> NEEsum;
00062 generateCandidateFindParentNEE( &this->main_trie, maybe_candidate,
00063 NEEsum, candidate_size -2 );
00064 }
00065 else
00066 generateCandidateFindParent( &this->main_trie, maybe_candidate,
00067 candidate_size -2 );
00068 log_dbg(0,"Number of newly generated candidates: %d",
00069 nr_of_new_candidates);
00070
00071 #if DEBUG_LEVEL >= LEVEL_DBG
00072 nr_of_all_candidates += nr_of_new_candidates;
00073 #endif
00074 }
00075 template <class P, class DF_D, class TRIE, class TRIE_ALLOCATOR, NEELevel NEE>
00076 void CandidateGeneratorPrune<P, DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
00077 afterWorkCandGen()
00078 {
00079 log_dbg(0,"The total number of generated candidates (in del. p.): %d",
00080 nr_of_all_candidates);
00081 }
00082
00083 template <class P, class DF_D, class TRIE, class TRIE_ALLOCATOR, NEELevel NEE>
00084 void CandidateGeneratorPrune<P, DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
00085 generateCandidateFindParent( TRIE* trie,
00086 std::vector<item_t>& maybe_candidate,
00087 unsigned int step_to_freq_par)
00088 {
00089 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00090 if(step_to_freq_par)
00091 {
00092 --step_to_freq_par;
00093 while( itEdge != trie->edgelist.end() )
00094 {
00095 maybe_candidate.push_back((*itEdge).first);
00096 P::df_decoder.pushItem( (*itEdge).first );
00097 generateCandidateFindParent( static_cast<TRIE*>((*itEdge).second),
00098 maybe_candidate,
00099 step_to_freq_par);
00100 if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
00101 {
00102 P::s_alloc.free(static_cast<TRIE*>((*itEdge).second));
00103 itEdge = trie->edgelist.erase(itEdge);
00104 }
00105 else ++itEdge;
00106 P::df_decoder.popItem();
00107 maybe_candidate.pop_back();
00108 }
00109 }
00110 else
00111 {
00112 generateCandidateAtParent(trie, maybe_candidate);
00113 #if DEBUG_LEVEL >= LEVEL_DBG
00114 for( typename TRIE::iterator it( trie->edgelist.begin() );
00115 it != trie->edgelist.end(); ++it)
00116 nr_of_new_candidates +=
00117 static_cast<TRIE*>((*it).second)->edgelist.size();
00118 #endif
00119 }
00120 }
00121
00122 template <class P, class DF_D, class TRIE, class TRIE_ALLOCATOR, NEELevel NEE>
00123 void CandidateGeneratorPrune<P, DF_D, TRIE, TRIE_ALLOCATOR, NEE>::
00124 generateCandidateFindParentNEE( TRIE* trie,
00125 std::vector<item_t>& maybe_candidate,
00126 std::vector<item_t>& NEEsum,
00127 unsigned int step_to_freq_par)
00128 {
00129 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00130 if(step_to_freq_par)
00131 {
00132 NEEsum.insert( NEEsum.end(),
00133 trie->neelist.begin(), trie->neelist.end() );
00134 --step_to_freq_par;
00135 while( itEdge != trie->edgelist.end() )
00136 {
00137 maybe_candidate.push_back((*itEdge).first);
00138 P::df_decoder.pushItem( (*itEdge).first );
00139 generateCandidateFindParentNEE( static_cast<TRIE*>((*itEdge).second),
00140 maybe_candidate, NEEsum,
00141 step_to_freq_par);
00142 if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
00143 {
00144 NEEsum.insert( NEEsum.end(),
00145 static_cast<TRIE*>((*itEdge).second)->neelist.begin(),
00146 static_cast<TRIE*>((*itEdge).second)->neelist.end() );
00147 if( NEEsum.size() < step_to_freq_par + 2 )
00148 {
00149 P::df_decoder.writeNEE( static_cast<TRIE*>((*itEdge).second)->getCounter(),
00150 NEEsum);
00151 NEEsum.resize( NEEsum.size() -
00152 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
00153 P::s_alloc.free(static_cast<TRIE*>((*itEdge).second));
00154 itEdge = trie->edgelist.erase(itEdge);
00155 }
00156 else
00157 {
00158 NEEsum.resize( NEEsum.size() -
00159 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
00160 ++itEdge;
00161 }
00162 }
00163 else ++itEdge;
00164 P::df_decoder.popItem();
00165 maybe_candidate.pop_back();
00166 }
00167 NEEsum.resize( NEEsum.size() - trie->neelist.size() );
00168 }
00169 else
00170 {
00171 generateCandidateAtParentNEE(trie, maybe_candidate, NEEsum);
00172 #if DEBUG_LEVEL >= LEVEL_DBG
00173 for( typename TRIE::iterator it( trie->edgelist.begin() );
00174 it != trie->edgelist.end(); ++it)
00175 nr_of_new_candidates +=
00176 static_cast<TRIE*>((*it).second)->edgelist.size();
00177 #endif
00178
00179 }
00180 }
00181 }
00182 #endif
