TrieBase.hpp

Go to the documentation of this file.

#ifndef TrieBase_HPP
#define TrieBase_HPP

#include "common.hpp"
#include <stack>

template <class EDGELIST, typename DATA = counter_t >
class TrieBase
{
   protected:
      DATA data;
      EDGELIST edgelist;

   public:
      class iterator
      {
         private:
            typedef std::pair< typename EDGELIST::iterator, 
                               TrieBase<EDGELIST, DATA>* > itpair_t;
            std::stack<itpair_t> node_stack;
            std::vector<item_t> itemset;
         public:
            iterator(){}
            iterator(typename EDGELIST::iterator it, TrieBase* trie)
            {
               node_stack.push(itpair_t(it, trie));
            }

//          iterator& operator++()
            void operator++()
            {
               while( (node_stack.top().first == node_stack.top().
                       second->edgelist.end()) )
               {
                  node_stack.pop();
                  itemset.pop_back();
                  if(!node_stack.empty())
                     ++node_stack.top().first;
                  else 
                     break;
               }
               if(!node_stack.empty())
               {
                  itemset.push_back( (*node_stack.top().first).first );
                  node_stack.push(
                     itpair_t( static_cast<TrieBase<EDGELIST, DATA>*>
                               ((*node_stack.top().first).second)->edgelist.begin(),
                               static_cast<TrieBase<EDGELIST, DATA>*>
                               ((*node_stack.top().first).second) ));
               }
//             return *this;
            }
/*          iterator iterator::operator++(int)
            {
               iterator ans(*this);
               operator++();
               return ans;
               }*/

            std::pair<std::vector<item_t>, DATA> operator*() const
            {
               return std::pair<std::vector<item_t>, DATA>(
                  itemset, node_stack.top().second->data );
            }

            iterator& operator=(const iterator& an_it)
            {
               if( this != &an_it )
               {
                  node_stack = an_it.node_stack;
                  itemset = an_it.itemset;
               }
               return *this;
            }
            bool operator==(const iterator& an_it) const
            {
               return node_stack == an_it.node_stack;
            }

            bool operator!=(const iterator& an_it) const
            {
               return node_stack != an_it.node_stack;
            }
      };
      static DATA def_data;
      TrieBase(){data = def_data;}
      TrieBase(DATA data) : data(data){}
      iterator begin(){return iterator(edgelist.begin(), this);}
      iterator end(){return iterator();}

      void setData(DATA data)
      {this->data = data;}

      DATA& getData()
      {return data;}


      void addLeaf( const item_t label)
      {
         edgelist.addEdge(label, new TrieBase(def_data));
      }


      bool isLeaf() const
      {
         return !edgelist.empty();
      }
      template <class CONT> bool isIncluded( 
         const CONT& itemset, 
         typename CONT::const_iterator it ) const;

      template <class CONT> TrieBase& addItemset(
         const CONT& itemset, 
         typename CONT::const_iterator it);
};

template <class EDGELIST, typename DATA> template <class CONT> inline 
bool TrieBase<EDGELIST, DATA>::
isIncluded( const CONT& itemset, typename CONT::const_iterator it ) const
{
   if( it == itemset.end() ) return true;
   else
   {
      TrieBase* subtrie;
      edgelist.lookupNocheck(*it, subtrie);
      if(subtrie)
         return static_cast<TrieBase*>(static_cast<TrieBase*>(subtrie))->
            isIncluded<CONT>( itemset, ++it );
      else 
         return false;
   }
}

template <class EDGELIST, typename DATA> template <class CONT> inline 
TrieBase<EDGELIST, DATA>& TrieBase<EDGELIST, DATA>::addItemset(
   const CONT& itemset, typename CONT::const_iterator it)
{
   if( it == itemset.end() ) 
      return *this;
   else
   {
      TrieBase** subtrie = reinterpret_cast<TrieBase**>(&edgelist.findOrCreate(*it));
      if(*subtrie == NULL)
         *subtrie = new TrieBase();
      return (*subtrie)->addItemset( itemset, ++it );
   }

}

#endif

---