00001 #ifndef CandidateGeneratorPrune_HPP
00002 #define CandidateGeneratorPrune_HPP
00003
00004 #include "common.hpp"
00005 #include "common/Edge.hpp"
00006 #include "common/allocators.hpp"
00007 #include <vector>
00008
00009
00010
00011
00012
00013
00014 namespace Bodon
00015 {
00016 namespace inhomogeneous_trie
00017 {
00018 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00019 NEELevel NEE, bool DEADENDPRUNE = true>
00020 class CandidateGeneratorPrune : public P
00021 {
00022 protected:
00023 unsigned int nr_of_new_candidates;
00024 unsigned int nr_of_all_candidates;
00025
00026 public:
00027 CandidateGeneratorPrune( TRIE& main_trie, DF_D& df_decoder,
00028 LEAF_ALLOCATOR& s_alloc) :
00029 P(main_trie, df_decoder, s_alloc),
00030 nr_of_all_candidates(0){}
00031
00032
00038 void generateCandidate(unsigned int candidate_size);
00039
00040 void afterWorkCandGen();
00041 bool isThereAnyCandidate() const
00042 {
00043 if(DEADENDPRUNE)
00044 return P::isThereAnyCandidate();
00045 else
00046 return P::is_there_any_new_candidate;
00047
00048 }
00049 protected:
00050
00052 void generateCandidateFindParent(
00053 TRIE* trie, std::vector<item_t>& maybe_candidate,
00054 unsigned int step_to_freq_par);
00055 void generateCandidateFindParentNEE(
00056 TRIE* trie, std::vector<item_t>& maybe_candidate,
00057 std::vector<item_t>& NEEsum,
00058 unsigned int step_to_freq_par);
00059 void generateCandidateFindParentNEENoDeadend(
00060 TRIE* trie, std::vector<item_t>& maybe_candidate,
00061 unsigned int step_to_freq_par);
00062 };
00063
00064
00065 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00066 NEELevel NEE, bool DEADENDPRUNE>
00067 void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF_ALLOCATOR,
00068 NEE, DEADENDPRUNE>::
00069 generateCandidate(unsigned int candidate_size)
00070 {
00071 assert(candidate_size > 1);
00072 nr_of_new_candidates = 0;
00073 P::is_there_any_new_candidate = false;
00074 std::vector<item_t> maybe_candidate;
00075 if(NEE > NEE_Off)
00076 {
00077 if(DEADENDPRUNE)
00078 {
00079 std::vector<item_t> NEEsum;
00080 generateCandidateFindParentNEE( &this->main_trie, maybe_candidate,
00081 NEEsum, candidate_size -2 );
00082 }
00083 else
00084 generateCandidateFindParentNEENoDeadend(
00085 &this->main_trie, maybe_candidate, candidate_size -2 );
00086 }
00087 else
00088 generateCandidateFindParent( &this->main_trie, maybe_candidate,
00089 candidate_size -2 );
00090 log_dbg(0,"Number of newly generated candidates: %d",
00091 nr_of_new_candidates);
00092
00093 #if DEBUG_LEVEL >= LEVEL_DBG
00094 nr_of_all_candidates += nr_of_new_candidates;
00095 #endif
00096 }
00097
00098 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00099 NEELevel NEE, bool DEADENDPRUNE>
00100 void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF_ALLOCATOR,
00101 NEE, DEADENDPRUNE>::
00102 afterWorkCandGen()
00103 {
00104 log_dbg(0,"The total number of generated candidates (in del. p.): %d",
00105 nr_of_all_candidates);
00106 }
00107
00108 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00109 NEELevel NEE, bool DEADENDPRUNE>
00110 void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF_ALLOCATOR,
00111 NEE, DEADENDPRUNE>::
00112 generateCandidateFindParent( TRIE* trie,
00113 std::vector<item_t>& maybe_candidate,
00114 unsigned int step_to_freq_par)
00115 {
00116 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00117 if(step_to_freq_par)
00118 {
00119 --step_to_freq_par;
00120 while( itEdge != trie->edgelist.end() )
00121 {
00122 maybe_candidate.push_back((*itEdge).first);
00123 P::df_decoder.pushItem( (*itEdge).first );
00124 generateCandidateFindParent( static_cast<TRIE*>((*itEdge).second),
00125 maybe_candidate,
00126 step_to_freq_par);
00127 if( DEADENDPRUNE &&
00128 static_cast<TRIE*>((*itEdge).second)->edgelist.empty() )
00129 {
00130 delete static_cast<TRIE*>((*itEdge).second);
00131 itEdge = trie->edgelist.erase(itEdge);
00132 }
00133 else ++itEdge;
00134 P::df_decoder.popItem();
00135 maybe_candidate.pop_back();
00136 }
00137 }
00138 else
00139 {
00140 generateCandidateAtParent(trie, maybe_candidate);
00141 #if DEBUG_LEVEL >= LEVEL_DBG
00142 for( typename TRIE::iterator it( trie->edgelist.begin() );
00143 it != trie->edgelist.end(); ++it)
00144 nr_of_new_candidates +=
00145 static_cast<TRIE*>((*it).second)->edgelist.size();
00146 #endif
00147 }
00148 }
00149
00150 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00151 NEELevel NEE, bool DEADENDPRUNE>
00152 void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF_ALLOCATOR,
00153 NEE, DEADENDPRUNE>::
00154 generateCandidateFindParentNEE( TRIE* trie,
00155 std::vector<item_t>& maybe_candidate,
00156 std::vector<item_t>& NEEsum,
00157 unsigned int step_to_freq_par)
00158 {
00159 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00160 if(step_to_freq_par)
00161 {
00162 NEEsum.insert( NEEsum.end(),
00163 trie->neelist.begin(), trie->neelist.end() );
00164 --step_to_freq_par;
00165 while( itEdge != trie->edgelist.end() )
00166 {
00167 maybe_candidate.push_back((*itEdge).first);
00168 P::df_decoder.pushItem( (*itEdge).first );
00169 generateCandidateFindParentNEE( static_cast<TRIE*>((*itEdge).second),
00170 maybe_candidate, NEEsum,
00171 step_to_freq_par);
00172 if( static_cast<TRIE*>((*itEdge).second)->edgelist.empty() )
00173 {
00174 NEEsum.insert( NEEsum.end(),
00175 static_cast<TRIE*>((*itEdge).second)->neelist.begin(),
00176 static_cast<TRIE*>((*itEdge).second)->neelist.end() );
00177 if( NEEsum.size() < step_to_freq_par + 2 )
00178 {
00179 P::df_decoder.writeNEE( static_cast<TRIE*>((*itEdge).second)->getCounter(),
00180 NEEsum);
00181 NEEsum.resize( NEEsum.size() -
00182 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
00183 delete static_cast<TRIE*>((*itEdge).second);
00184 itEdge = trie->edgelist.erase(itEdge);
00185 }
00186 else
00187 {
00188 NEEsum.resize( NEEsum.size() -
00189 static_cast<TRIE*>((*itEdge).second)->neelist.size() );
00190 ++itEdge;
00191 }
00192 }
00193 else ++itEdge;
00194 P::df_decoder.popItem();
00195 maybe_candidate.pop_back();
00196 }
00197 NEEsum.resize( NEEsum.size() - trie->neelist.size() );
00198 }
00199 else
00200 {
00201 generateCandidateAtParentNEE(trie, maybe_candidate, NEEsum);
00202 #if DEBUG_LEVEL >= LEVEL_DBG
00203 for( typename TRIE::iterator it( trie->edgelist.begin() );
00204 it != trie->edgelist.end(); ++it)
00205 nr_of_new_candidates +=
00206 static_cast<TRIE*>((*it).second)->edgelist.size();
00207 #endif
00208
00209 }
00210
00211 }
00212
00213 template <class P, class DF_D, class TRIE, class LEAF_ALLOCATOR,
00214 NEELevel NEE, bool DEADENDPRUNE>
00215 void CandidateGeneratorPrune<P, DF_D, TRIE, LEAF_ALLOCATOR,
00216 NEE, DEADENDPRUNE>::
00217 generateCandidateFindParentNEENoDeadend(
00218 TRIE* trie, std::vector<item_t>& maybe_candidate,
00219 unsigned int step_to_freq_par)
00220 {
00221 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00222 if(step_to_freq_par)
00223 {
00224 --step_to_freq_par;
00225 while( itEdge != trie->edgelist.end() )
00226 {
00227 maybe_candidate.push_back((*itEdge).first);
00228 generateCandidateFindParentNEENoDeadend( static_cast<TRIE*>((*itEdge).second),
00229 maybe_candidate, step_to_freq_par);
00230 ++itEdge;
00231 maybe_candidate.pop_back();
00232 }
00233 }
00234 else
00235 {
00236 generateCandidateAtParentNEENoDeadend(trie, maybe_candidate);
00237 #if DEBUG_LEVEL >= LEVEL_DBG
00238 for( typename TRIE::iterator it( trie->edgelist.begin() );
00239 it != trie->edgelist.end(); ++it)
00240 nr_of_new_candidates +=
00241 static_cast<TRIE*>((*it).second)->edgelist.size();
00242 #endif
00243
00244 }
00245
00246 }
00247 }
00248 }
00249 #endif
