SupportCounterMergeTries.hpp

Go to the documentation of this file.

#ifndef SupportCounterMergeTries_HPP
#define SupportCounterMergeTries_HPP

#include "common.hpp"
#include <vector>
#include "apriori/bodon/Leaf.hpp"
//#include <cstdio>
//#include <iterator>   //for test



namespace Bodon
{
namespace dynamic_trie
{
   template <class TRIE_OEL, class TRIE_OI, 
             class PATRICIA>
   class SupportCounterMergeTries
   {
      protected:
         TRIE_OEL& cand_trie;
         PATRICIA& patricia;
         typedef Bodon::Leaf LEAF;

      public:
         SupportCounterMergeTries( TRIE_OEL& cand_trie,
                                   PATRICIA& patricia ) :
            cand_trie(cand_trie), 
            patricia(patricia){}
         
         void countSupport(const unsigned int candidate_size )
         {
//          kiir(patricia.getRoot());
            mergeTries(&this->cand_trie, patricia.getRoot(), 
                       candidate_size-1, this->cand_trie.edgelist.begin());
         }
         void kiir(typename PATRICIA::nodeptr_t subpatricia)
         {
            std::cout<<"Counter: "<<subpatricia->getCounter()<<std::endl;
            std::cout<<"Labels: "<<std::endl;
            for( typename PATRICIA::nodeiter_t patr_iter = subpatricia.childrenBegin();
                 patr_iter != subpatricia.childrenEnd(); ++patr_iter)
            {
               std::cout<<"label: "<<(*patr_iter).first<<std::endl;
            }
            for( typename PATRICIA::nodeiter_t patr_iter = subpatricia.childrenBegin();
                 patr_iter != subpatricia.childrenEnd(); ++patr_iter)
            {
               kiir((*patr_iter).second);
            }
         }
         
      private:
         template <class TRIE> void mergeTries(
            TRIE* subtrie, typename PATRICIA::nodeptr_t subpatricia, 
            unsigned int step_to_leaf_par,
            typename TRIE::iterator first_larger_edge);

         template <class TRIE> bool mergeTriesRemoveInfreqP(
            TRIE* subtrie, typename PATRICIA::nodeptr_t subpatricia, 
            unsigned int step_to_leaf_par,
            typename TRIE::iterator first_larger_edge);

   };

   template <class TRIE_OEL, class TRIE_OI, 
             class PATRICIA> 
   template <class TRIE> inline void
   SupportCounterMergeTries<TRIE_OEL, TRIE_OI, 
                            PATRICIA>::
   mergeTries( TRIE* subtrie, typename PATRICIA::nodeptr_t subpatricia, 
               unsigned int step_to_leaf_par, 
               typename TRIE::iterator first_larger_edge)
   {      
      for( typename PATRICIA::nodeiter_t patr_iter = subpatricia.childrenBegin();
           patr_iter != subpatricia.childrenEnd(); ++patr_iter)
      {
         while( first_larger_edge != subtrie->edgelist.end() &&
                (*first_larger_edge).first < (*patr_iter).first  )
            ++first_larger_edge;
         if( first_larger_edge != subtrie->edgelist.end() &&
             (*first_larger_edge).first >= (*patr_iter).first  )
         {
            mergeTries( subtrie, (*patr_iter).second, 
                        step_to_leaf_par, first_larger_edge );
            if( (*patr_iter).first == (*first_larger_edge).first )
            {
               if(step_to_leaf_par > 0)
               {
                  if(static_cast<LEAF*>((*first_larger_edge).second)->getCounter() & TWO_POW31)
                     mergeTries( 
                        static_cast<TRIE_OEL*>((*first_larger_edge).second), 
                        (*patr_iter).second, step_to_leaf_par - 1,
                        static_cast<TRIE_OEL*>((*first_larger_edge).second)->edgelist.begin());
                  else
                     mergeTries( 
                        static_cast<TRIE_OI*>((*first_larger_edge).second), 
                        (*patr_iter).second, step_to_leaf_par - 1,
                        static_cast<TRIE_OI*>((*first_larger_edge).second)->edgelist.begin());
               }
               else
               {
                  static_cast<LEAF*>((*first_larger_edge).second)
                     ->increaseCounter((*patr_iter).second->getCounter());
               }
               ++first_larger_edge;
            }
         }
         else break;
      }
   }
}
}
#endif

---