inhomogeneous_trie/trie_manipulators/sequence/IntersectProPruner.hpp

Go to the documentation of this file.

#ifndef IntersectProPruner_HPP
#define IntersectProPruner_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 sequence
{
namespace inhomogeneous_trie
{
   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR>
   class IntersectProPruner : public 
   Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>
   {
      private:
         typedef Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR> PARENT;
      protected:
         std::vector<Edge> extenders;
         mutable std::vector<item_t> ext_items;
         mutable std::vector<item_t> ext_nee;
         std::vector<Edge> replace_list;

      public:
         IntersectProPruner( TRIE& main_trie, DF_D& df_decoder,
                             LEAF_ALLOCATOR& s_alloc ) :
            Bodon::inhomogeneous_trie::ManipulatorBase<DF_D, TRIE, LEAF_ALLOCATOR>(
               main_trie, df_decoder, s_alloc){}

      protected:
         
         void intersect( const TRIE* subset_trie ) const;

         void filterNonExtenders( 
            const std::vector<const TRIE*>& subset_tries,
            const item_t leaf_item ) const;

         bool findSubsetTries( 
            std::vector<item_t>& itemset, 
            std::vector<const TRIE*>& subset_trie) const;

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


   };

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> inline void 
   IntersectProPruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   intersect( const TRIE* subset_trie) const
   {
      typename TRIE::const_iterator it_e( subset_trie->edgelist.begin() );
      std::vector<item_t>::iterator it_i(ext_items.begin());
      while(it_e != subset_trie->edgelist.end() && it_i != ext_items.end())
      {
         if(*it_e < *it_i)
            ++it_e;
         else if(*it_e > *it_i)
            it_i = ext_items.erase(it_i);
         else
         {
            ++it_e;
            ++it_i;
         }
      }
      ext_items.erase(it_i, ext_items.end());      
   }


   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> inline void 
   IntersectProPruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   filterNonExtenders( const std::vector<const TRIE*>& subset_tries,  
                       const item_t leaf_item ) const
   {
      std::vector<typename TRIE::const_iterator> subset_child_iters;
      subset_child_iters.reserve(subset_tries.size());
      for(typename std::vector<const TRIE*>::const_iterator it = subset_tries.begin(); 
          it !=  subset_tries.end(); ++it)
         subset_child_iters.push_back((*it)->edgelist.begin());

      for(std::vector<item_t>::size_type index = 0; 
          index < subset_tries.size(); ++index)
      {
         while( subset_child_iters[index] !=  subset_tries[index]->edgelist.end() &&
                (*(subset_child_iters[index])).first < leaf_item)
            ++subset_child_iters[index];
         if( subset_child_iters[index] !=  subset_tries[index]->edgelist.end() &&
             (*(subset_child_iters[index])).first == leaf_item)
            intersect(static_cast<const TRIE*>((*(subset_child_iters[index])).second));
         else
         {
            ext_items.clear();
            break;
         }
      }
   }


   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> inline bool
   IntersectProPruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   findSubsetTries( std::vector<item_t>& itemset, 
                    std::vector<const TRIE*>& subset_tries ) const
   {
      assert(itemset.size() > 0);
      std::vector<item_t>::iterator item_it = itemset.end()-1;
      register item_t deleted_item = *item_it, temp_item;
      const TRIE* a_subset_trie;

      itemset.pop_back();
      a_subset_trie = PARENT::main_trie.isIncluded( itemset, itemset.begin() );
      if(a_subset_trie)
         subset_tries.push_back(a_subset_trie);
      else 
      {
         itemset.push_back(deleted_item);
         return false;
      }
      while(item_it != itemset.begin() )
      {
         --item_it;
         temp_item = *item_it;
         *item_it = deleted_item;
         deleted_item = temp_item;
         a_subset_trie = PARENT::main_trie.isIncluded( itemset, itemset.begin() );
         if(a_subset_trie)
            subset_tries.push_back(a_subset_trie);
         else
         {
            itemset.insert( item_it, deleted_item );
            return false;
         }
      }
      itemset.insert( item_it, deleted_item );
      return true;
   }

   template <class DF_D, class TRIE, class LEAF, class LEAF_ALLOCATOR> 
   inline void IntersectProPruner<DF_D, TRIE, LEAF, LEAF_ALLOCATOR>::
   generateCandidateAtParent(TRIE* trie, std::vector<item_t>& maybe_candidate)
   {
      std::vector<const TRIE*> subset_tries;
      const bool all_subset_included = findSubsetTries( 
         maybe_candidate, subset_tries);
      typename TRIE::iterator itEdge2;
      LEAF* toExtendAsLeaf;
      TRIE* toExtend;
      replace_list.clear();
      for( typename TRIE::iterator itEdge( trie->edgelist.begin() ); 
             itEdge != trie->edgelist.end(); ++itEdge )
      {
         toExtendAsLeaf = static_cast<LEAF*>((*itEdge).second);
         PARENT::df_decoder.pushItemWithWrite( (*itEdge).first, 
                                       toExtendAsLeaf->getCounter() );
         PARENT::df_decoder.popItem();
         if(all_subset_included)
         {
            ext_items.clear();
            for( itEdge2 = trie->edgelist.begin(); 
                 itEdge2 != trie->edgelist.end(); ++itEdge2 )
               ext_items.push_back((*itEdge2).first);
            filterNonExtenders( subset_tries, (*itEdge).first );
            if(ext_items.empty())
            {
               toExtendAsLeaf->setCounter(0);
               replace_list.push_back(Edge((*itEdge).first, toExtendAsLeaf));
            }
            else
            {
               extenders.clear();
               for(std::vector<item_t>::iterator it = ext_items.begin();
                   it != ext_items.end(); ++it)
               {
                  extenders.push_back(Edge(*it, PARENT::s_alloc.allocate()));
                  static_cast<LEAF*>(extenders.back().second)->setCounter(0);
               }
               toExtend = new TRIE(toExtendAsLeaf->getCounter());
               PARENT::s_alloc.free(toExtendAsLeaf);
               replace_list.push_back(Edge((*itEdge).first, toExtend));
               toExtend->edgelist.insert(extenders);
            }
         }
         else
         {
            toExtendAsLeaf->setCounter(0);
            replace_list.push_back(Edge((*itEdge).first, toExtendAsLeaf));
         }
      }
      trie->edgelist.clear();
      trie->edgelist.insert(replace_list);
   }
}
}
}
#endif

---