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
00017 namespace dynamic_trie
00018 {
00019
00020 template <class P, class DF_D, class TRIE_OEL, class TRIE_OI,
00021 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00022 class CandidateGeneratorPrune : public P
00023 {
00024 protected:
00025 unsigned int total_nr_of_candidates;
00026 unsigned int total_nr_of_nonprefix_equiitem;
00027
00028 public:
00029 CandidateGeneratorPrune( TRIE_OEL& main_trie, DF_D& df_decoder,
00030 LEAF_ALLOCATOR& s_alloc) :
00031 P(main_trie, df_decoder, s_alloc),
00032 total_nr_of_candidates(0), total_nr_of_nonprefix_equiitem(0){}
00033
00034
00040 void generateCandidate(unsigned int candidate_size);
00041
00042 void afterWorkCandGen();
00043 protected:
00044
00046 template <class TRIE> void generateCandidateFindParent(
00047 TRIE* trie, std::vector<item_t>& maybe_candidate,
00048 unsigned int step_to_freq_par);
00049 template <class TRIE> void generateCandidateFindParentNEE(
00050 TRIE* trie, std::vector<item_t>& maybe_candidate,
00051 unsigned int step_to_freq_par);
00052 };
00053
00054
00055 template <class P, class DF_D, class TRIE_OEL, class TRIE_OI,
00056 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00057 void CandidateGeneratorPrune<P, DF_D, TRIE_OEL, TRIE_OI, LEAF,
00058 LEAF_ALLOCATOR, NEE>::
00059 generateCandidate(unsigned int candidate_size)
00060 {
00061 assert(candidate_size > 1);
00062 P::nr_of_new_candidates = 0;
00063 std::vector<item_t> maybe_candidate;
00064 if(NEE > NEE_Off)
00065 {
00066 P::nr_of_nonprefix_equiitem = 0;
00067 P::df_decoder.pushEquisupportItemSet(
00068 P::main_trie.neelist);
00069 generateCandidateFindParentNEE( &this->main_trie, maybe_candidate,
00070 candidate_size -2 );
00071 log_info_det(0,"Number of nonprefix equisupport items: %d", P::nr_of_nonprefix_equiitem);
00072 #if DEBUG_LEVEL >= LEVEL_INFO
00073 total_nr_of_nonprefix_equiitem += nr_of_nonprefix_equiitem;
00074 #endif
00075
00076 }
00077 else
00078 generateCandidateFindParent( &this->main_trie, maybe_candidate,
00079 candidate_size -2 );
00080 log_info_det(0,"Number of newly generated candidates: %d",
00081 P::nr_of_new_candidates);
00082 #if DEBUG_LEVEL >= LEVEL_INFO
00083 total_nr_of_candidates += nr_of_new_candidates;
00084 #endif
00085 }
00086
00087 template <class P, class DF_D, class TRIE_OEL, class TRIE_OI,
00088 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00089 void CandidateGeneratorPrune<P, DF_D, TRIE_OEL, TRIE_OI, LEAF,
00090 LEAF_ALLOCATOR, NEE>::
00091 afterWorkCandGen()
00092 {
00093 log_info(0,"The total number of generated candidates: %d",
00094 total_nr_of_candidates);
00095 if(NEE > NEE_Off)
00096 log_info(0,"The total number of nonprefix equisupport item: %d",
00097 total_nr_of_nonprefix_equiitem);
00098 }
00099
00100 template <class P, class DF_D, class TRIE_OEL, class TRIE_OI,
00101 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00102 template <class TRIE>
00103 void CandidateGeneratorPrune<P, DF_D, TRIE_OEL, TRIE_OI,
00104 LEAF, LEAF_ALLOCATOR, NEE>::
00105 generateCandidateFindParent( TRIE* trie,
00106 std::vector<item_t>& maybe_candidate,
00107 unsigned int step_to_freq_par)
00108 {
00109 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00110 if(step_to_freq_par)
00111 {
00112 --step_to_freq_par;
00113 while( itEdge != trie->edgelist.end() )
00114 {
00115 maybe_candidate.push_back((*itEdge).first);
00116 P::df_decoder.pushItem( (*itEdge).first );
00117 if( static_cast<LEAF*>((*itEdge).second)->getCounter() & TWO_POW31 )
00118 {
00119 generateCandidateFindParent( static_cast<TRIE_OEL*>((*itEdge).second),
00120 maybe_candidate,
00121 step_to_freq_par);
00122 if( static_cast<TRIE_OEL*>((*itEdge).second)->edgelist.empty() )
00123 {
00124 delete static_cast<TRIE_OEL*>((*itEdge).second);
00125 itEdge = trie->edgelist.erase(itEdge);
00126 }
00127 else ++itEdge;
00128 }
00129 else
00130 {
00131 generateCandidateFindParent( static_cast<TRIE_OI*>((*itEdge).second),
00132 maybe_candidate,
00133 step_to_freq_par);
00134 if( static_cast<TRIE_OI*>((*itEdge).second)->edgelist.empty() )
00135 {
00136 delete static_cast<TRIE_OI*>((*itEdge).second);
00137 itEdge = trie->edgelist.erase(itEdge);
00138 }
00139 else ++itEdge;
00140 }
00141 P::df_decoder.popItem();
00142 maybe_candidate.pop_back();
00143 }
00144 }
00145 else
00146 {
00147 generateCandidateAtParent(trie, maybe_candidate);
00148 }
00149 }
00150
00151 template <class P, class DF_D, class TRIE_OEL, class TRIE_OI,
00152 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00153 template <class TRIE>
00154 void CandidateGeneratorPrune<P, DF_D, TRIE_OEL, TRIE_OI,
00155 LEAF, LEAF_ALLOCATOR, NEE>::
00156 generateCandidateFindParentNEE( TRIE* trie,
00157 std::vector<item_t>& maybe_candidate,
00158 unsigned int step_to_freq_par)
00159 {
00160 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00161 if(step_to_freq_par)
00162 {
00163 --step_to_freq_par;
00164 while( itEdge != trie->edgelist.end() )
00165 {
00166 maybe_candidate.push_back((*itEdge).first);
00167 P::df_decoder.pushItem( (*itEdge).first );
00168 if( static_cast<LEAF*>((*itEdge).second)->getCounter() & TWO_POW31 )
00169 {
00170 P::df_decoder.pushEquisupportItemSet(
00171 static_cast<TRIE_OEL*>((*itEdge).second)->neelist);
00172 generateCandidateFindParentNEE( static_cast<TRIE_OEL*>((*itEdge).second),
00173 maybe_candidate, step_to_freq_par);
00174 if( static_cast<TRIE_OEL*>((*itEdge).second)->edgelist.empty() &&
00175 ( NEE == NEE_Full ||
00176 NEE == NEE_Level1 && P::df_decoder.nrOfEEItems() < step_to_freq_par + 2 ))
00177 {
00178 P::df_decoder.write( static_cast<TRIE_OEL*>((*itEdge).second)->getCounter()
00179 & TWO_POW31_1);
00180 delete static_cast<TRIE_OEL*>((*itEdge).second);
00181 itEdge = trie->edgelist.erase(itEdge);
00182 }
00183 else
00184 ++itEdge;
00185 }
00186 else
00187 {
00188 P::df_decoder.pushEquisupportItemSet(static_cast<TRIE_OI*>((*itEdge).second)->neelist);
00189 generateCandidateFindParentNEE( static_cast<TRIE_OI*>((*itEdge).second),
00190 maybe_candidate, step_to_freq_par);
00191 if( static_cast<TRIE_OI*>((*itEdge).second)->edgelist.empty() &&
00192 ( NEE == NEE_Full ||
00193 NEE != NEE_Level1 && P::df_decoder.nrOfEEItems() < step_to_freq_par + 2 ) )
00194 {
00195 P::df_decoder.write( static_cast<TRIE_OI*>((*itEdge).second)->getCounter() );
00196 delete static_cast<TRIE_OI*>((*itEdge).second);
00197 itEdge = trie->edgelist.erase(itEdge);
00198 }
00199 else
00200 ++itEdge;
00201 }
00202 P::df_decoder.popItem();
00203 maybe_candidate.pop_back();
00204 }
00205 }
00206 else
00207 generateCandidateAtParentNEE(trie, maybe_candidate);
00208
00209 }
00210 }
00211 }
00212 #endif
