trie/trie_manipulators/FrequentPairInserter.hpp

Go to the documentation of this file.

#ifndef FrequentPairInserter_HPP
#define FrequentPairInserter_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 FrequentPairInserter : 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:
      FrequentPairInserter( 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)
            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 FrequentPairInserter<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.empty())
         {
            delete static_cast<TRIE*>((*mt_iter).second);
            mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
         }
         else
         {
            static_cast<TRIE*>((*mt_iter).second)->edgelist.insert(extenders);
            ++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 
FrequentPairInserter<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 )
{
   std::vector<item_t> NEEsum(PARENT::main_trie.neelist);
   PARENT::df_decoder.writeNEE( PARENT::main_trie.getCounter(), NEEsum );
   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();
      vector<item_t> neelist;
      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();
         neelist.clear();
         while( it != freq_pairs_with_counters.end() && 
                (*it).second.first == (*mt_iter).first &&
                !PARENT::main_trie.neeFind((*it).second.second) )
         {
            if( (*it).first == 
                static_cast<TRIE*>((*mt_iter).second)->getCounter() )
               neelist.push_back((*it).second.second);
            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())
            {
               static_cast<TRIE*>((*mt_iter).second)->neeAddSorted(neelist);
               ++mt_iter;
            }
            else
            {
               PARENT::df_decoder.pushItemWithWrite( 
                  (*mt_iter).first, 
                  static_cast<TRIE*>((*mt_iter).second)->getCounter() );
               PARENT::df_decoder.popItem();
               delete static_cast<TRIE*>((*mt_iter).second);
               mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
            }    
         }
         else
         {
            static_cast<TRIE*>((*mt_iter).second)->edgelist.insert(extenders);
            static_cast<TRIE*>((*mt_iter).second)->neeAddSorted(neelist);
            ++mt_iter;
         }
      }
      while( mt_iter != PARENT::main_trie.edgelist.end() )
      {
         PARENT::df_decoder.pushItemWithWrite( 
            (*mt_iter).first, 
            static_cast<TRIE*>((*mt_iter).second)->getCounter() );
         PARENT::df_decoder.popItem();
         delete static_cast<TRIE*>((*mt_iter).second);
         mt_iter = PARENT::main_trie.edgelist.erase(mt_iter);
      }
   }
}

}   
   
#endif

---