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/trie/trie_manipulators/ManipulatorBase.hpp"
#include <vector>
//#include <cstdio>
//#include <iterator>   //for test




namespace Bodon
{
namespace sequence
{
   template <class DF_D, class TRIE>
   class IntersectProPruner : public ManipulatorBase<DF_D, TRIE>
   {
      protected:
         std::vector<Edge> extenders;
         mutable std::vector<item_t> ext_items;
         mutable std::vector<item_t> ext_nee;

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

      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> inline void 
   IntersectProPruner<DF_D, TRIE>::
   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> inline void 
   IntersectProPruner<DF_D, TRIE>::
   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> inline bool
   IntersectProPruner<DF_D, TRIE>::
   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 = 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 = 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> inline void 
   IntersectProPruner<DF_D, TRIE>::
   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 itEdge( trie->edgelist.begin() ), itEdge2;
      TRIE* toExtend;
      while( itEdge != trie->edgelist.end() )
      {
         toExtend = static_cast<TRIE*>((*itEdge).second);
         df_decoder.pushItemWithWrite( (*itEdge).first, toExtend->getCounter() );
         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 );
            extenders.clear();
            for(std::vector<item_t>::iterator it = ext_items.begin();
                it != ext_items.end(); ++it)
               extenders.push_back(Edge(*it, new TRIE(0)));
            toExtend->edgelist.insert(extenders);
         }
         ++itEdge;
      }
   }
}
}
#endif

---