trie/trie_manipulators/CandidateGeneratorNoprune.hpp

Go to the documentation of this file.

#ifndef CandidateGeneratorNoprune_HPP
#define CandidateGeneratorNoprune_HPP


#include "common.hpp"
#include "common/Edge.hpp"
#include "common/log.h"
#include "apriori/bodon/trie/trie_manipulators/ManipulatorBase.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace trie
{
   template <class DF_D, class TRIE, bool NEE>
   class CandidateGeneratorNoprune : public ManipulatorBase<DF_D, TRIE>
   {
      protected:
         std::vector<Edge> extenders;
         unsigned int nr_of_new_candidates;
         unsigned int nr_of_all_candidates;
         typedef ManipulatorBase<DF_D, TRIE> PARENT;

      public:
         CandidateGeneratorNoprune( TRIE& main_trie, DF_D& df_decoder ) : 
            ManipulatorBase<DF_D, TRIE>(main_trie, df_decoder),
            nr_of_all_candidates(0){}


         void generateCandidate(unsigned int candidate_size);
         
         void afterWorkCandGen();
      protected:

         void generateCandidateAtParent( TRIE* trie );
         void generateCandidateAtParentNEE( TRIE* trie,
                                         std::vector<item_t>& NEEsum );

         void generateCandidateFindParent( 
            TRIE* trie, unsigned int step_to_freq_par);
         void generateCandidateFindParentNEE( 
            TRIE* trie, std::vector<item_t>& NEEsum,
            unsigned int step_to_freq_par);




      public:
         // No public members
   };


   template <class DF_D, class TRIE, bool NEE> 
   void CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   generateCandidate(unsigned int candidate_size)
   {
      assert(candidate_size > 1);
      nr_of_new_candidates = 0;
      if(NEE > NEE_Off)
      {
         std::vector<item_t> NEEsum;
         generateCandidateFindParentNEE( &PARENT::main_trie, NEEsum,
                                         candidate_size -2 );
      }
      else generateCandidateFindParent( &PARENT::main_trie,
                                        candidate_size -2 );
      log_dbg(0, "Number of newly generated candidates: %d", nr_of_new_candidates);
#if DEBUG_LEVEL >= LEVEL_DBG
      nr_of_all_candidates += nr_of_new_candidates;
#endif
   }
   template <class DF_D, class TRIE, bool NEE> 
   void CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   afterWorkCandGen()
   {
      log_dbg(0, "The total number of generated candidates: %d", nr_of_all_candidates);
   }


   template <class DF_D, class TRIE, bool NEE> inline void 
   CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   generateCandidateAtParent(TRIE* trie)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() ), itEdge2;
      TRIE* toExtend;
      while( itEdge != trie->edgelist.end() )
      {
         toExtend = static_cast<TRIE*>((*itEdge).second);
         PARENT::df_decoder.pushItemWithWrite( (*itEdge).first, 
                                       toExtend->getCounter() );
         PARENT::df_decoder.popItem();
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
               extenders.push_back(Edge((*itEdge2).first, new TRIE(0)));
         if(extenders.empty())
         {
            delete toExtend;
            itEdge = trie->edgelist.erase(itEdge);
         }
         else 
         {
            toExtend->edgelist.insert(extenders);
            ++itEdge;
         }
      }
   }

   template <class DF_D, class TRIE, bool NEE> inline void 
   CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   generateCandidateAtParentNEE( TRIE* trie,
                                 std::vector<item_t>& NEEsum )
   {
      NEEsum.insert( NEEsum.end(), 
                     trie->neelist.begin(), trie->neelist.end() );
      typename TRIE::iterator itEdge( trie->edgelist.begin() ), itEdge2;
      TRIE* toExtend;
      while( itEdge != trie->edgelist.end() )
      {
         itEdge2 = itEdge;
         ++itEdge2;
         extenders.clear();
         for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
               extenders.push_back(Edge((*itEdge2).first, new TRIE(0)));
         toExtend = static_cast<TRIE*>((*itEdge).second);
         if(extenders.empty())
         {
            PARENT::df_decoder.pushItem( (*itEdge).first );
            PARENT::df_decoder.writeNEE( static_cast<TRIE*>(toExtend)->getCounter(), NEEsum);
            PARENT::df_decoder.popItem();
            delete toExtend;
            itEdge = trie->edgelist.erase(itEdge);
         }
         else 
         {
            toExtend->edgelist.insert(extenders);
            ++itEdge;
         }
      }
      NEEsum.resize( NEEsum.size() - trie->neelist.size() );
   }


   template <class DF_D, class TRIE, bool NEE> void
   CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   generateCandidateFindParent( TRIE* trie, 
                                unsigned int step_to_freq_par)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() );
      if(step_to_freq_par)
      {
         --step_to_freq_par;
         while( itEdge != trie->edgelist.end() )
         {
            PARENT::df_decoder.pushItem( (*itEdge).first );
            generateCandidateFindParent( 
               static_cast<TRIE*>((*itEdge).second), step_to_freq_par);
            if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
            {
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = trie->edgelist.erase(itEdge);
            }
            else ++itEdge;
            PARENT::df_decoder.popItem();
         }
      }
      else
      {
         generateCandidateAtParent(trie);
#if DEBUG_LEVEL >= LEVEL_DBG
         for( typename TRIE::iterator it( trie->edgelist.begin() );
              it != trie->edgelist.end(); ++it)
            nr_of_new_candidates += 
               static_cast<TRIE*>((*it).second)->edgelist.size();
#endif
      }
   }
   template <class DF_D, class TRIE, bool NEE> void
   CandidateGeneratorNoprune<DF_D, TRIE, NEE>::
   generateCandidateFindParentNEE( TRIE* trie, 
                                std::vector<item_t>& NEEsum,
                                unsigned int step_to_freq_par)
   {
      typename TRIE::iterator itEdge( trie->edgelist.begin() );
      if(step_to_freq_par)
      {
         NEEsum.insert( NEEsum.end(), 
                        trie->neelist.begin(), trie->neelist.end() );
         --step_to_freq_par;
         while( itEdge != trie->edgelist.end() )
         {
            PARENT::df_decoder.pushItem( (*itEdge).first );
            generateCandidateFindParentNEE( 
               static_cast<TRIE*>((*itEdge).second), NEEsum, step_to_freq_par);
            if(static_cast<TRIE*>((*itEdge).second)->edgelist.empty())
            {
               NEEsum.insert( NEEsum.end(), 
                              static_cast<TRIE*>((*itEdge).second)->neelist.begin(), 
                              static_cast<TRIE*>((*itEdge).second)->neelist.end() );
               PARENT::df_decoder.writeNEE( static_cast<TRIE*>((*itEdge).second)->getCounter(), 
                                       NEEsum);
               NEEsum.resize( NEEsum.size() - 
                              static_cast<TRIE*>((*itEdge).second)->neelist.size() );
               delete static_cast<TRIE*>((*itEdge).second);
               itEdge = trie->edgelist.erase(itEdge);
            }
            else ++itEdge;
            PARENT::df_decoder.popItem();
         }
         NEEsum.resize( NEEsum.size() - trie->neelist.size() );
      }
      else
      {
         generateCandidateAtParentNEE(trie, NEEsum);
#if DEBUG_LEVEL >= LEVEL_DBG
         for( typename TRIE::iterator it( trie->edgelist.begin() );
              it != trie->edgelist.end(); ++it)
            nr_of_new_candidates += 
               static_cast<TRIE*>((*it).second)->edgelist.size();
#endif
      }
   }
}
}
#endif

---