dynamic_trie/trie_manipulators/FrequentPairInserter.hpp

Go to the documentation of this file.

#ifndef FrequentPairInserterDyn_HPP
#define FrequentPairInserterDyn_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
{
namespace dynamic_trie
{
template <class DF_D, class TRIE_OEL, class TRIE_OI, class LEAF, 
          class LEAF_ALLOCATOR, NEELevel NEE>
class FrequentPairInserter : public Bodon::inhomogeneous_trie::
         ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR>
{
   private:
      typedef Bodon::inhomogeneous_trie::
      ManipulatorBase<DF_D, TRIE_OEL, LEAF_ALLOCATOR> PARENT;
   protected:
      std::vector<Edge> extenders;
      std::vector<Edge> replace_list;

   public:
      FrequentPairInserter( TRIE_OEL& 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_OEL, class TRIE_OI, class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> void 
FrequentPairInserter<DF_D, TRIE_OEL, TRIE_OI, 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_OEL::iterator mt_iter;
      for( 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;
         if(it == freq_pairs_with_counters.end() )
         {
            break;
         }
         extenders.clear();
         while ((*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.empty())
            if( 2 * extenders.size() < extenders.back().first - extenders.front().first + 2 )
            {
               TRIE_OEL* toExtend = new TRIE_OEL(
                  static_cast<LEAF*>((*mt_iter).second)->getCounter() | TWO_POW31 );
               toExtend->edgelist.insert(extenders);
               replace_list.push_back(Edge((*mt_iter).first, toExtend));
            }
            else
            {
               TRIE_OI* toExtend = new TRIE_OI(
                  static_cast<LEAF*>((*mt_iter).second)->getCounter() );
               toExtend->edgelist.insert(extenders);
               replace_list.push_back(Edge((*mt_iter).first, toExtend));
            }
         delete static_cast<LEAF*>((*mt_iter).second);
      }
      while( mt_iter != PARENT::main_trie.edgelist.end() )
      {
         delete static_cast<LEAF*>((*mt_iter).second);
         ++mt_iter;
      }
      PARENT::main_trie.edgelist.clear();
      PARENT::main_trie.edgelist.insert(replace_list);
   }
}

template <class DF_D, class TRIE_OEL, class TRIE_OI, 
          class LEAF, class LEAF_ALLOCATOR, NEELevel NEE> void 
FrequentPairInserter<DF_D, TRIE_OEL, TRIE_OI, 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() & TWO_POW31_1);
   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;
      typename TRIE_OEL::iterator mt_iter;
      for( 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.empty())
         {
            if(PARENT::main_trie.neelist.empty() && neelist.empty())
            {
               PARENT::df_decoder.pushItemWithWrite( 
                  (*mt_iter).first, static_cast<LEAF*>((*mt_iter).second)->getCounter() );
               PARENT::df_decoder.popItem();
            }
            else
            {
               TRIE_OEL* toExtend = new TRIE_OEL(
                  static_cast<LEAF*>((*mt_iter).second)->getCounter() | TWO_POW31 );
               toExtend->neePushBackSorted(neelist);
               replace_list.push_back(Edge((*mt_iter).first, toExtend));
            }       
         }
         else
            if( 2 * extenders.size() < 
                extenders.back().first - extenders.front().first + 2 )
            {
               TRIE_OEL* toExtend = new TRIE_OEL(
                  static_cast<LEAF*>((*mt_iter).second)->getCounter() | TWO_POW31 );
               toExtend->edgelist.insert(extenders);
               toExtend->neePushBackSorted(neelist);
               replace_list.push_back(Edge((*mt_iter).first, toExtend));
            }
            else
            {
               TRIE_OI* toExtend = new TRIE_OI(
                  static_cast<LEAF*>((*mt_iter).second)->getCounter() );
               toExtend->edgelist.insert(extenders);
               toExtend->neePushBackSorted(neelist);
               replace_list.push_back(Edge((*mt_iter).first, toExtend));
            }
         delete static_cast<LEAF*>((*mt_iter).second);
      }
      PARENT::main_trie.edgelist.clear();
      PARENT::main_trie.edgelist.insert(replace_list);
//      log_perf(0,"Number of prefix equisupport items: %d", nr_of_prefix_equiitem); 
   }
}
}
}

#endif

---