00001
00002 #ifndef CandidateGeneratorNoprune_HPP
00003 #define CandidateGeneratorNoprune_HPP
00004
00005 #include "common.hpp"
00006 #include "common/Edge.hpp"
00007 #include "common/log.h"
00008 #include "apriori/bodon/inhomogeneous_trie/trie_manipulators/ManipulatorBase.hpp"
00009 #include <vector>
00010
00011
00012
00013
00014 namespace Bodon
00015 {
00016
00017 namespace dynamic_trie
00018 {
00019
00020 template <class DF_D, class TRIE_OEL, class TRIE_OI, class LEAF,
00021 class LEAF_ALLOCATOR, NEELevel NEE>
00022 class CandidateGeneratorNoprune : public Bodon::inhomogeneous_trie::
00023 ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR>
00024 {
00025 private:
00026 typedef Bodon::inhomogeneous_trie::
00027 ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR> PARENT;
00028 protected:
00029 std::vector<Edge> extenders;
00030 std::vector<Edge> replace_list;
00031
00032 unsigned int nr_of_new_candidates;
00033
00034
00035 public:
00036 CandidateGeneratorNoprune( TRIE_OEL& main_trie, DF_D& df_decoder,
00037 LEAF_ALLOCATOR& s_alloc ) :
00038 PARENT(main_trie, df_decoder, s_alloc){}
00039
00040
00046 void generateCandidate(unsigned int candidate_size);
00047
00048 void afterWorkCandGen();
00049 protected:
00050
00051 template <class TRIE> void generateCandidateAtParent( TRIE* trie );
00052 template <class TRIE> void generateCandidateAtParentNEE(
00053 TRIE* trie);
00054
00056 template <class TRIE> void generateCandidateFindParent(
00057 TRIE* trie, unsigned int step_to_freq_par);
00058 template <class TRIE> void generateCandidateFindParentNEE(
00059 TRIE* trie, unsigned int step_to_freq_par);
00060
00061 public:
00062
00063 };
00064
00065
00066 template <class DF_D, class TRIE_OEL, class TRIE_OI,
00067 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00068 inline void CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI, LEAF,
00069 LEAF_ALLOCATOR, NEE>::
00070 generateCandidate(unsigned int candidate_size)
00071 {
00072 assert(candidate_size > 1);
00073 if(NEE > NEE_Off)
00074 {
00075 PARENT::df_decoder.pushEquisupportItemSet(
00076 PARENT::main_trie.neelist);
00077 generateCandidateFindParentNEE<TRIE_OEL>(
00078 &PARENT::main_trie, candidate_size -2 );
00079 }
00080 else
00081 generateCandidateFindParent<TRIE_OEL>(
00082 &PARENT::main_trie, candidate_size -2 );
00083
00084 }
00085 template <class DF_D, class TRIE_OEL, class TRIE_OI, class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00086 void CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI, LEAF, LEAF_ALLOCATOR, NEE>::
00087 afterWorkCandGen()
00088 {
00089 }
00090
00091
00092 template <class DF_D, class TRIE_OEL, class TRIE_OI,
00093 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00094 template <class TRIE> inline void
00095 CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI, LEAF,
00096 LEAF_ALLOCATOR, NEE>::
00097 generateCandidateAtParent(TRIE* trie)
00098 {
00099 typename TRIE::iterator itEdge2;
00100 LEAF* toExtendAsLeaf;
00101 replace_list.clear();
00102 for( typename TRIE::iterator itEdge( trie->edgelist.begin() );
00103 itEdge != trie->edgelist.end(); ++itEdge )
00104 {
00105 toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
00106 PARENT::df_decoder.pushItemWithWrite( (*itEdge).first,
00107 toExtendAsLeaf->getCounter() );
00108 PARENT::df_decoder.popItem();
00109 itEdge2 = itEdge;
00110 ++itEdge2;
00111 extenders.clear();
00112 for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
00113 {
00114 extenders.push_back(Edge((*itEdge2).first, PARENT::s_alloc.allocate()));
00115 static_cast<LEAF*>(extenders.back().second)->setCounter(0);
00116
00117 }
00118 if(!extenders.empty())
00119 {
00120 if( 2 * extenders.size() < extenders.back().first - extenders.front().first + 3 )
00121 {
00122 TRIE_OEL* toExtend = new TRIE_OEL(toExtendAsLeaf->getCounter() | TWO_POW31 );
00123 replace_list.push_back(Edge((*itEdge).first, toExtend));
00124 toExtend->edgelist.insert(extenders);
00125 }
00126 else
00127 {
00128 TRIE_OI* toExtend = new TRIE_OI(toExtendAsLeaf->getCounter());
00129 replace_list.push_back(Edge((*itEdge).first, toExtend));
00130 toExtend->edgelist.insert(extenders);
00131 }
00132 #if DEBUG_LEVEL >= LEVEL_INFO
00133 nr_of_new_candidates +=extenders.size();
00134 #endif
00135 }
00136 PARENT::s_alloc.free(toExtendAsLeaf);
00137 }
00138 trie->edgelist.clear();
00139 trie->edgelist.insert(replace_list);
00140 }
00141
00142 template <class DF_D, class TRIE_OEL, class TRIE_OI,
00143 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00144 template <class TRIE> inline void
00145 CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI, LEAF,
00146 LEAF_ALLOCATOR, NEE>::
00147 generateCandidateAtParentNEE( TRIE* trie )
00148 {
00149 typename TRIE::iterator itEdge2;
00150 LEAF* toExtendAsLeaf;
00151 replace_list.clear();
00152 for( typename TRIE::iterator itEdge( trie->edgelist.begin() );
00153 itEdge != trie->edgelist.end(); ++itEdge )
00154 {
00155 toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
00156 itEdge2 = itEdge;
00157 ++itEdge2;
00158 extenders.clear();
00159 for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
00160 {
00161 extenders.push_back(Edge((*itEdge2).first, PARENT::s_alloc.allocate()));
00162 static_cast<LEAF*>(extenders.back().second)->setCounter(0);
00163 }
00164 if(extenders.empty())
00165 {
00166 PARENT::df_decoder.pushItem( (*itEdge).first );
00167 PARENT::df_decoder.write( toExtendAsLeaf->getCounter());
00168 PARENT::df_decoder.popItem();
00169 }
00170 else
00171 {
00172 if( 2 * extenders.size() < extenders.back().first - extenders.front().first + 3 )
00173 {
00174 TRIE_OEL* toExtend = new TRIE_OEL(toExtendAsLeaf->getCounter() | TWO_POW31 );
00175 replace_list.push_back(Edge((*itEdge).first, toExtend));
00176 toExtend->edgelist.insert(extenders);
00177 }
00178 else
00179 {
00180 TRIE_OI* toExtend = new TRIE_OI(toExtendAsLeaf->getCounter());
00181 replace_list.push_back(Edge((*itEdge).first, toExtend));
00182 toExtend->edgelist.insert(extenders);
00183 }
00184 #if DEBUG_LEVEL >= LEVEL_PERF
00185 nr_of_new_candidates +=extenders.size();
00186 #endif
00187 }
00188 PARENT::s_alloc.free(toExtendAsLeaf);
00189 }
00190 trie->edgelist.clear();
00191 trie->edgelist.insert(replace_list);
00192 }
00193
00194
00195 template <class DF_D, class TRIE_OEL, class TRIE_OI,
00196 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00197 template <class TRIE> void
00198 CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI,
00199 LEAF, LEAF_ALLOCATOR, NEE>::
00200 generateCandidateFindParent( TRIE* trie,
00201 unsigned int step_to_freq_par)
00202 {
00203 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00204 if(step_to_freq_par)
00205 {
00206 --step_to_freq_par;
00207 while( itEdge != trie->edgelist.end() )
00208 {
00209 PARENT::df_decoder.pushItem( (*itEdge).first );
00210 if( static_cast<LEAF*>((*itEdge).second)->getCounter() & TWO_POW31 )
00211 {
00212 generateCandidateFindParent<TRIE_OEL>(
00213 static_cast<TRIE_OEL*>((*itEdge).second), step_to_freq_par);
00214 if(static_cast<TRIE_OEL*>((*itEdge).second)->edgelist.empty())
00215 {
00216 delete static_cast<TRIE_OEL*>((*itEdge).second);
00217 itEdge = trie->edgelist.erase(itEdge);
00218 }
00219 else ++itEdge;
00220 }
00221 else
00222 {
00223 generateCandidateFindParent<TRIE_OI>(
00224 static_cast<TRIE_OI*>((*itEdge).second), step_to_freq_par);
00225 if(static_cast<TRIE_OI*>((*itEdge).second)->edgelist.empty())
00226 {
00227 delete static_cast<TRIE_OI*>((*itEdge).second);
00228 itEdge = trie->edgelist.erase(itEdge);
00229 }
00230 else ++itEdge;
00231 }
00232 PARENT::df_decoder.popItem();
00233 }
00234 }
00235 else
00236 generateCandidateAtParent(trie);
00237 }
00238 template <class DF_D, class TRIE_OEL, class TRIE_OI,
00239 class LEAF, class LEAF_ALLOCATOR, NEELevel NEE>
00240 template <class TRIE> void
00241 CandidateGeneratorNoprune<DF_D, TRIE_OEL, TRIE_OI, LEAF,
00242 LEAF_ALLOCATOR, NEE>::
00243 generateCandidateFindParentNEE( TRIE* trie,
00244 unsigned int step_to_freq_par)
00245 {
00246 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00247 if(step_to_freq_par)
00248 {
00249 --step_to_freq_par;
00250 while( itEdge != trie->edgelist.end() )
00251 {
00252 PARENT::df_decoder.pushItem( (*itEdge).first );
00253 if( static_cast<LEAF*>((*itEdge).second)->getCounter() & TWO_POW31 )
00254 {
00255 PARENT::df_decoder.pushEquisupportItemSet(
00256 static_cast<TRIE_OEL*>((*itEdge).second)->neelist);
00257 generateCandidateFindParentNEE<TRIE_OEL>(
00258 static_cast<TRIE_OEL*>((*itEdge).second), step_to_freq_par);
00259 if(static_cast<TRIE_OEL*>((*itEdge).second)->edgelist.empty())
00260 {
00261 PARENT::df_decoder.write( static_cast<TRIE_OEL*>((*itEdge).second)->getCounter() & TWO_POW31_1);
00262 delete static_cast<TRIE_OEL*>((*itEdge).second);
00263 itEdge = trie->edgelist.erase(itEdge);
00264 }
00265 else ++itEdge;
00266 }
00267 else
00268 {
00269 PARENT::df_decoder.pushEquisupportItemSet(static_cast<TRIE_OI*>((*itEdge).second)->neelist);
00270 generateCandidateFindParentNEE<TRIE_OI>(
00271 static_cast<TRIE_OI*>((*itEdge).second), step_to_freq_par);
00272 if(static_cast<TRIE_OI*>((*itEdge).second)->edgelist.empty())
00273 {
00274 PARENT::df_decoder.write( static_cast<TRIE_OI*>((*itEdge).second)->getCounter());
00275 delete static_cast<TRIE_OI*>((*itEdge).second);
00276 itEdge = trie->edgelist.erase(itEdge);
00277 }
00278 else ++itEdge;
00279 }
00280 PARENT::df_decoder.popItem();
00281 }
00282 }
00283 else
00284 generateCandidateAtParentNEE(trie);
00285 }
00286 }
00287 }
00288 #endif
