OrderedEdgelist.hpp

Go to the documentation of this file.

#ifndef OrderedEdgelist_HPP
#define OrderedEdgelist_HPP

#include "common.hpp"
#include "common/Edge.hpp"
#include "datastructures/trie/edgelist/Edgelist.hpp"
#include <vector>
//#include <iterator>   //for test


namespace Bodon
{

   template < class VECTOR = std::vector<Edge> >         
   class OrderedEdgelist : public Edgelist<VECTOR>
   {
      public:
         OrderedEdgelist() : Edgelist<VECTOR>(){}
         void* find(item_t item) const;
         void findForward( item_t label, 
                           typename VECTOR::iterator& hint) const;

         void findForwardNoBoundaryCheck( 
            item_t label, typename VECTOR::iterator& hint) const;

         void findBackward( item_t label, 
                            typename VECTOR::iterator& hint) const;
         void findBackwardNoBoundaryCheck( 
            item_t label, typename VECTOR::iterator& hint) const;


         void*& findOrCreate(item_t label);
         bool lookup(item_t label, void*& subtrie) const;
         void lookupNocheck(item_t label, void*& subtrie) const;
         void lookupNoUppercheck(item_t label, void*& subtrie) const
         {
            lookupNocheck(label, subtrie);
         }
         void lower_bound(typename VECTOR::iterator& it, item_t label)
         {
            it = std::lower_bound(it, VECTOR::end(), label);
         }
         item_t largestEdgelabel() const
         {
            return VECTOR::back().first;
         }
         item_t smallestEdgelabel() const
         {
            return VECTOR::front().first;
         }
   };
   template <class VECTOR>
   inline void* OrderedEdgelist<VECTOR>::find(
      item_t label) const
   {
      typename VECTOR::const_iterator it = VECTOR::begin(); 
      while(it != VECTOR::end() && (*it).first < label)
         ++it;
      if(it != VECTOR::end() && (*it).first == label)
         return  (*it).second;
      else
         return NULL;
   }
   template <class VECTOR>
   inline void OrderedEdgelist<VECTOR>::findForward(
      item_t label, typename VECTOR::iterator& hint) const
   {
      while(hint != VECTOR::end() && (*hint).first < label)
         ++hint;
   }
   template <class VECTOR>
   inline void OrderedEdgelist<VECTOR>::findForwardNoBoundaryCheck(
      item_t label, typename VECTOR::iterator& hint) const
   {
      while((*hint).first < label)
         ++hint;
   }

   template <class VECTOR>
   inline void OrderedEdgelist<VECTOR>::findBackward(
      item_t label, typename VECTOR::iterator& hint) const
   {
      while(hint != VECTOR::begin() && (*hint).first > label)
         --hint;
   }

   template <class VECTOR>
   inline void OrderedEdgelist<VECTOR>::findBackwardNoBoundaryCheck(
      item_t label, typename VECTOR::iterator& hint) const
   {
      while((*hint).first > label)
         --hint;
   }

   template <class VECTOR>
   inline void*& OrderedEdgelist<VECTOR>::findOrCreate(
      item_t label)
   {
      typename VECTOR::iterator it = std::lower_bound( VECTOR::begin(), VECTOR::end(), label );
      if( it == VECTOR::end() || (*it).first != label )
         it = std::vector<Edge>::insert(it, Edge(label, NULL));
      return (*it).second;
   }

   template <class VECTOR>
   inline bool OrderedEdgelist<VECTOR>::lookup(
      item_t label, void*& subtrie) const
   {
      if(VECTOR::back() < label)
         return false;
      else
      {
         typename VECTOR::const_iterator it = 
            std::lower_bound( VECTOR::begin(), VECTOR::end(), 
                              label );
         if( (*it).first == label )
            subtrie = (*it).second;
         else 
            subtrie = NULL;
         return true;
      }
   }
   
   template <class VECTOR>
   inline void OrderedEdgelist<VECTOR>::lookupNocheck(
      item_t label, void*& subtrie) const
   {
        typename VECTOR::const_iterator it = 
            std::lower_bound( VECTOR::begin(), 
                              VECTOR::end(), label );
         if( (*it).first == label )
            subtrie = (*it).second;
         else 
            subtrie = NULL;
   }
}

#endif

---