Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members

dynamic_trie/trie_manipulators/CandidateGeneratorPrune.hpp

Go to the documentation of this file.
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 //#include <cstdio>
00009 //#include <iterator>   //for test
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

Generated on Sun Sep 17 17:50:38 2006 for FIM environment by  doxygen 1.4.4