trie/trie_manipulators/FrequentPairInserterNoprune.hpp

Go to the documentation of this file.

#ifndef FrequentPairInserterNoprune_HPP
#define FrequentPairInserterNoprune_HPP

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

namespace Bodon
{
template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, bool NEE>
class FrequentPairInserterNoprune : public 
inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
{
   private:
      typedef inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
   protected:
      std::vector<Edge> extenders;

   public:
      FrequentPairInserterNoprune( TRIE& trie, DF_D& df_decoder,
                                   LEAF_ALLOCATOR& s_alloc) : 
         PARENT(trie, df_decoder, s_alloc){}


      void insertFrequentPairs(
         const std::vector< std::pair< counter_t, 
         std::pair<item_t, item_t> > >& freq_pairs_with_counters )
      {
         if(NEE > NEE_Off)
            insertFrequentPairsNEE(freq_pairs_with_counters);
         else
            insertFrequentPairsNONEE(freq_pairs_with_counters);
      }

   protected:
      void insertFrequentPairsNONEE(
         const std::vector< std::pair< counter_t, 
         std::pair<item_t, item_t> > >& freq_pairs_with_counters );
      void insertFrequentPairsNEE(
         const std::vector< std::pair< counter_t, 
         std::pair<item_t, item_t> > >& freq_pairs_with_counters );
};

   
template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, bool NEE> void 
FrequentPairInserterNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE>::insertFrequentPairsNONEE(
   const std::vector< std::pair< counter_t, std::pair<item_t, item_t> > >& 
   freq_pairs_with_counters )
{
   if( freq_pairs_with_counters.empty() )
      PARENT::main_trie.edgelist.clear();
   else
   {
      std::vector< std::pair< counter_t, std::pair<item_t, item_t> > >::
         const_iterator it = freq_pairs_with_counters.begin();
      typename TRIE::iterator mt_iter = PARENT::main_trie.edgelist.begin(); 
      while( mt_iter != PARENT::main_trie.edgelist.end())
      {
         while (it != freq_pairs_with_counters.end() && 
                (*it).second.first < (*mt_iter).first)
            ++it;
         extenders.clear();
         while( it != freq_pairs_with_counters.end() &&  
                (*it).second.first == (*mt_iter).first)
         {
            extenders.push_back(Edge((*it).second.second, PARENT::s_alloc.allocate()));
            static_cast<LEAF*>(extenders.back().second)->setCounter((*it).first);
            ++it;
         }
         if(extenders.size() > 1)
         {
            static_cast<TRIE*>((*mt_iter).second)->edgelist.insert(extenders);
            ++mt_iter;
         }
         else
         {
            if(extenders.size() == 1)
            {
               PARENT::df_decoder.pushItem((*mt_iter).first);
               PARENT::df_decoder.pushItemWithWrite(
                  extenders.front().first, static_cast<LEAF*>(extenders.front().second)->getCounter());
               PARENT::s_alloc.free(static_cast<LEAF*>(extenders.front().second));
               PARENT::df_decoder.popItem();
               PARENT::df_decoder.popItem();
            }
            delete static_cast<TRIE*>((*mt_iter).second);
            mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
         }
      }
      while( mt_iter != PARENT::main_trie.edgelist.end() )
      {
         delete static_cast<TRIE*>((*mt_iter).second);
         mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
      }
   }
}

template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR, bool NEE> void 
FrequentPairInserterNoprune<DF_D, TRIE, LEAF, LEAF_ALLOCATOR, NEE>::insertFrequentPairsNEE(
   const std::vector< std::pair< counter_t, std::pair<item_t, item_t> > >& 
   freq_pairs_with_counters )
{
   PARENT::df_decoder.pushEquisupportItemSet(PARENT::main_trie.neelist);
   PARENT::df_decoder.write( PARENT::main_trie.getCounter() );
   if( freq_pairs_with_counters.empty() )
      PARENT::main_trie.edgelist.clear();
   else
   {
      unsigned int nr_of_prefix_equiitem=0;
      std::vector< std::pair< counter_t, std::pair<item_t, item_t> > >::
         const_iterator it = freq_pairs_with_counters.begin();
      vector<item_t> neelist;
      for( typename TRIE::iterator mt_iter = PARENT::main_trie.edgelist.begin(); 
           mt_iter != PARENT::main_trie.edgelist.end(); ++mt_iter )
      {
         while (it != freq_pairs_with_counters.end() && 
                (*it).second.first < (*mt_iter).first)
            ++it;
         extenders.clear();
         neelist.clear();
         while( it != freq_pairs_with_counters.end() && 
                (*it).second.first == (*mt_iter).first )
            if( !PARENT::main_trie.neeFind((*it).second.second) )
         {
            if( (*it).first == 
                static_cast<LEAF*>((*mt_iter).second)->getCounter() )
            {
               neelist.push_back((*it).second.second);
#if DEBUG_LEVEL >= LEVEL_PERF
               ++nr_of_prefix_equiitem;
#endif
            }
            else
            {
               extenders.push_back(Edge((*it).second.second, 
                                        PARENT::s_alloc.allocate()));
               static_cast<LEAF*>(extenders.back().second)->setCounter((*it).first);
            }
            ++it;
         }
         if(extenders.size() > 1)
         {
            static_cast<TRIE*>((*mt_iter).second)->edgelist.insert(extenders);
            static_cast<TRIE*>((*mt_iter).second)->neePushBackSorted(neelist);
            ++mt_iter;
         }
         else
         {
            PARENT::df_decoder.pushItem((*mt_iter).first);
            PARENT::df_decoder.pushEquisupportItemSet(neelist);
            if(extenders.size() == 1)
            {
               PARENT::df_decoder.pushItem( extenders.front().first );
               PARENT::df_decoder.write(
                  static_cast<LEAF*>(extenders.front().second)->getCounter());
               PARENT::s_alloc.free(static_cast<LEAF*>(extenders.front().second));
               PARENT::df_decoder.popItem();
            }
            PARENT::df_decoder.write( 
               static_cast<LEAF*>((*mt_iter).second)->getCounter() );
            PARENT::df_decoder.popItem();
            delete static_cast<LEAF*>((*mt_iter).second);
            mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
         }
      }
//      log_perf(0,"Number of prefix equisupport items: %d", nr_of_prefix_equiitem); 
   }
}

}

#endif

---