00001 #ifndef CandidateGeneratorNoprune_HPP
00002 #define CandidateGeneratorNoprune_HPP
00003
00004 #include "common.hpp"
00005 #include "common/Edge.hpp"
00006 #include "common/log.h"
00007 #include "apriori/bodon/inhomogeneous_trie/trie_manipulators/ManipulatorBase.hpp"
00008 #include <vector>
00009
00010
00011
00012
00013
00014
00015 namespace Bodon
00016 {
00017 namespace sequence
00018 {
00019 namespace inhomogeneous_trie
00020 {
00021 template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
00022 class CandidateGeneratorNoprune : public
00023 Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
00024 {
00025 private:
00026 typedef Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
00027 protected:
00028 std::vector<Edge> extenders;
00029 unsigned int nr_of_new_candidates;
00030 unsigned int nr_of_all_candidates;
00031 std::vector<Edge> replace_list;
00032
00033 public:
00034 CandidateGeneratorNoprune( TRIE& main_trie, DF_D& df_decoder,
00035 LEAF_ALLOCATOR& s_alloc ) :
00036 Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>(
00037 main_trie, df_decoder, s_alloc),
00038 nr_of_all_candidates(0){}
00039
00040
00046 void generateCandidate(unsigned int candidate_size);
00047
00048 void afterWorkCandGen();
00049 protected:
00050
00051 void generateCandidateAtParent( TRIE* trie );
00053 void generateCandidateFindParent(
00054 TRIE* trie, unsigned int step_to_freq_par);
00055
00056 public:
00057
00058 };
00059
00060
00061 template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
00062 void CandidateGeneratorNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
00063 generateCandidate(unsigned int candidate_size)
00064 {
00065 assert(candidate_size > 1);
00066 nr_of_new_candidates = 0;
00067 generateCandidateFindParent( &this->main_trie,
00068 candidate_size -2 );
00069 log_dbg(0, "Number of newly generated candidates: %d", nr_of_new_candidates);
00070 #if DEBUG_LEVEL >= LEVEL_DBG
00071 nr_of_all_candidates += nr_of_new_candidates;
00072 #endif
00073 }
00074 template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
00075 void CandidateGeneratorNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
00076 afterWorkCandGen()
00077 {
00078 log_dbg(0, "The total number of generated candidates: %d", nr_of_all_candidates);
00079 }
00080
00081
00082 template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> inline void
00083 CandidateGeneratorNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
00084 generateCandidateAtParent(TRIE* trie)
00085 {
00086 typename TRIE::iterator itEdge2;
00087 LEAF* toExtendAsLeaf;
00088 TRIE* toExtend;
00089 replace_list.clear();
00090 for( typename TRIE::iterator itEdge( trie->edgelist.begin() );
00091 itEdge != trie->edgelist.end(); ++itEdge)
00092 {
00093 toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
00094 PARENT::df_decoder.pushItemWithWrite( (*itEdge).first,
00095 toExtendAsLeaf->getCounter() );
00096 PARENT::df_decoder.popItem();
00097 extenders.clear();
00098 for( itEdge2 = trie->edgelist.begin();
00099 itEdge2 != trie->edgelist.end(); ++itEdge2 )
00100 {
00101 extenders.push_back(Edge((*itEdge2).first, PARENT::s_alloc.allocate()));
00102 static_cast<LEAF*>(extenders.back().second)->setCounter(0);
00103 }
00104 if(!extenders.empty())
00105 {
00106 toExtend = new TRIE(toExtendAsLeaf->getCounter());
00107 toExtend->edgelist.insert(extenders);
00108 replace_list.push_back(Edge((*itEdge).first, toExtend));
00109 }
00110 PARENT::s_alloc.free(toExtendAsLeaf);
00111 }
00112 trie->edgelist.clear();
00113 trie->edgelist.insert(replace_list);
00114 }
00115
00116
00117 template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> void
00118 CandidateGeneratorNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
00119 generateCandidateFindParent( TRIE* trie,
00120 unsigned int step_to_freq_par)
00121 {
00122 typename TRIE::iterator itEdge( trie->edgelist.begin() );
00123 if(step_to_freq_par)
00124 {
00125 --step_to_freq_par;
00126 while( itEdge != trie->edgelist.end() )
00127 {
00128 PARENT::df_decoder.pushItem( (*itEdge).first );
00129 generateCandidateFindParent(
00130 static_cast<TRIE*>((*itEdge).second), step_to_freq_par);
00131 if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
00132 {
00133 delete static_cast<TRIE*>((*itEdge).second);
00134 itEdge = trie->edgelist.erase(itEdge);
00135 }
00136 else ++itEdge;
00137 PARENT::df_decoder.popItem();
00138 }
00139 }
00140 else
00141 {
00142 generateCandidateAtParent(trie);
00143 #if DEBUG_LEVEL >= LEVEL_DBG
00144 for( typename TRIE::iterator it( trie->edgelist.begin() );
00145 it != trie->edgelist.end(); ++it)
00146 nr_of_new_candidates +=
00147 static_cast<TRIE*>((*it).second)->edgelist.size();
00148 #endif
00149 }
00150 }
00151 }
00152 }
00153 }
00154 #endif