trie/trie_manipulators/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
{
   template <class DF_D, class TRIE, bool NEE>
   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;
         typedef ManipulatorBase<DF_D, TRIE> PARENT;

      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 intersectNEE( const TRIE* subset_trie ) const;

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

         void filterNonExtendersNEE( 
            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);
         void generateCandidateAtParentNEE(
            TRIE* trie, std::vector<item_t>& maybe_candidate,
            std::vector<item_t>& NEEsum);


   };

   template <class DF_D, class TRIE, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   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, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   intersectNEE( const TRIE* subset_trie ) const
   {
      typename TRIE::const_iterator it_e( subset_trie->edgelist.begin() );
      std::vector<item_t>::const_iterator it_nee( subset_trie->neelist.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)
         {
            while(it_nee != subset_trie->neelist.end() && *it_nee < *it_i)
               ++it_nee;
            if(it_nee != subset_trie->neelist.end() && *it_nee == *it_i)
               ext_nee.push_back(*it_i);
            it_i = ext_items.erase(it_i);
         }
         else
         {
            ++it_e;
            ++it_i;
         }
      }
      if(it_i != ext_items.end())
      {
         std::vector<item_t>::iterator it_2(it_i);
         do
         {
            while(it_nee != subset_trie->neelist.end() && *it_nee < *it_i)
               ++it_nee;
            if(it_nee != subset_trie->neelist.end() && *it_nee == *it_i)
               ext_nee.push_back(*it_i);
            ++it_i;
         }
         while(it_i != ext_items.end());
         ext_items.erase(it_2, ext_items.end());
      }
   }

   template <class DF_D, class TRIE, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   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, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   filterNonExtendersNEE( const std::vector<const TRIE*>& subset_tries,
                          const item_t leaf_item ) const
   {
      std::vector<typename TRIE::const_iterator> subset_child_iters; 
      std::vector<vector<item_t>::const_iterator> subset_nee_iters;
      subset_child_iters.reserve(subset_tries.size());
      subset_nee_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());
         subset_nee_iters.push_back((*it)->neelist.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)
            intersectNEE(static_cast<const TRIE*>((*(subset_child_iters[index])).second));
         else
         {
            while( subset_nee_iters[index] !=  subset_tries[index]->neelist.end() &&
                *subset_nee_iters[index] < leaf_item)
               ++subset_nee_iters[index];
            if( subset_nee_iters[index] != subset_tries[index]->neelist.end() &&
                *subset_nee_iters[index] == leaf_item)
               intersectNEE( subset_tries[index] );
            else
            {
               ext_items.clear();
               break;
            }
         }
      }
   }
   template <class DF_D, class TRIE, bool NEE> inline bool
   IntersectProPruner<DF_D, TRIE, NEE>::
   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, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   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);
         PARENT::df_decoder.pushItemWithWrite( (*itEdge).first, toExtend->getCounter() );
         PARENT::df_decoder.popItem();
         if(all_subset_included)
         {
            itEdge2 = itEdge;
            ++itEdge2;
            ext_items.clear();
            for( ; 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)));
            if(extenders.empty())
            {
               delete toExtend;
               itEdge = trie->edgelist.erase(itEdge);
            }
            else 
            {
               toExtend->edgelist.insert(extenders);
               ++itEdge;
            }
         }
         else
         {
            delete toExtend;
            itEdge = trie->edgelist.erase(itEdge);
         }
      }
   }
   template <class DF_D, class TRIE, bool NEE> inline void 
   IntersectProPruner<DF_D, TRIE, NEE>::
   generateCandidateAtParentNEE(TRIE* trie, std::vector<item_t>& maybe_candidate,
                                std::vector<item_t>& NEEsum)
   {
      std::vector<const TRIE*> subset_tries;
      NEEsum.insert( NEEsum.end(), 
                     trie->neelist.begin(), trie->neelist.end() );

      if( 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);
            itEdge2 = itEdge;
            ++itEdge2;
            ext_items.clear();
            ext_nee.clear();
            for( ; itEdge2 != trie->edgelist.end(); ++itEdge2 )
               ext_items.push_back((*itEdge2).first);
            filterNonExtendersNEE( 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)));
            if(extenders.empty() && ext_nee.empty() && NEEsum.size() < 1)
            {
               PARENT::df_decoder.pushItemWithWrite( 
                  (*itEdge).first,
                  static_cast<TRIE*>(toExtend)->getCounter() );
               PARENT::df_decoder.popItem();
               delete toExtend;
               itEdge = trie->edgelist.erase(itEdge);
            }
            else
            {
               toExtend->edgelist.insert(extenders);
               toExtend->neelist.reserve(ext_nee.size());
               toExtend->neelist.insert( toExtend->neelist.end(), 
                                         ext_nee.begin(), ext_nee.end() );
               ++itEdge;
            }
         }
      }
      else if(NEEsum.size() < 1)
      {
         typename TRIE::iterator itEdge( trie->edgelist.begin() );
         while( itEdge != trie->edgelist.end() )
         {
            PARENT::df_decoder.pushItemWithWrite( 
               (*itEdge).first,
               static_cast<TRIE*>((*itEdge).second)->getCounter() );
            PARENT::df_decoder.popItem();
            delete static_cast<TRIE*>((*itEdge).second);
            itEdge = trie->edgelist.erase(itEdge);
         }
      }
      NEEsum.resize( NEEsum.size() - trie->neelist.size() );
   }
}
#endif

---