OrderedEdgelistDynLookup.hpp

Go to the documentation of this file.

#ifndef OrderedEdgelistDynLookup_HPP
#define OrderedEdgelistDynLookup_HPP

#include "datastructures/trie/edgelist/OrderedEdgelist.hpp"
#include <vector>
//#include <iterator>   //for test


namespace Bodon
{
   template <class VECTOR, unsigned int THRESHOLD>       
   class OrderedEdgelistDynLookup : public OrderedEdgelist<VECTOR>
   {
      protected:
         typedef OrderedEdgelist<VECTOR> PARENT;
      public:
         OrderedEdgelistDynLookup() : OrderedEdgelist<VECTOR>(){}

         void* find(item_t item) 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);
   };
   
   template <class VECTOR, unsigned int THRESHOLD>
   inline void* OrderedEdgelistDynLookup<VECTOR, THRESHOLD>::
   find(item_t label) const
   {
      typename VECTOR::const_iterator it;
      if(VECTOR::size() < THRESHOLD)
      {
         it = VECTOR::begin();
         while(it != VECTOR::end())
            if( (*it).first < label)
               ++it;
            else if( (*it).first == label)
               return (*it).second;
            else 
               return NULL;
         return NULL;
      }
      else
      {
         it = std::lower_bound( VECTOR::begin(), VECTOR::end(), label );
         if( it != VECTOR::end() && (*it).first == label)
            return  (*it).second;
         else 
            return NULL;
      }
         
   }   template <class VECTOR, unsigned int THRESHOLD>
   inline void*& OrderedEdgelistDynLookup<VECTOR, THRESHOLD>::findOrCreate(
      item_t label)
   {
      typename VECTOR::iterator it;
      if(VECTOR::size() < THRESHOLD)
      {
         for(it = VECTOR::begin(); it != VECTOR::end(); ++it)
            if(*it >= label)
               break;
      }
      else 
         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, unsigned int THRESHOLD>
   inline bool OrderedEdgelistDynLookup<VECTOR, THRESHOLD>::lookup(
      item_t label, void*& subtrie) const
   {
      if(VECTOR::back() < label)
         return false;
      else
      {
         subtrie = NULL;
         typename VECTOR::const_iterator it;
         if(VECTOR::size() < THRESHOLD)
         {
            for( it = VECTOR::begin(); it != VECTOR::end() && 
                    (*it).first <= label; ++it)
               if((*it).first == label)
               {
                  subtrie = (*it).second;
                  break;
               }
         }
         else 
         {
            it = std::lower_bound( VECTOR::begin(), VECTOR::end(), label );
            if( (*it).first == label )
               subtrie = (*it).second;
         }
         return true;
      }
   }
   
   template <class VECTOR, unsigned int THRESHOLD>
   inline void OrderedEdgelistDynLookup<VECTOR, THRESHOLD>::lookupNocheck(
      item_t label, void*& subtrie) const
   {
      subtrie = NULL;
      typename VECTOR::const_iterator it;
      if(VECTOR::size() < THRESHOLD)
      {
         for(it = VECTOR::begin(); it != VECTOR::end() && (*it).first <= label; ++it)
            if((*it).first == label)
            {
               subtrie = (*it).second;
               break;
            }
         }
         else 
         {
            it = std::lower_bound( VECTOR::begin(), VECTOR::end(), 
                         label );
            if( (*it).first == label )
               subtrie = (*it).second;
         }
   }
   template <class VECTOR, unsigned int THRESHOLD>
   inline void OrderedEdgelistDynLookup<VECTOR, THRESHOLD>::
   lower_bound(typename VECTOR::iterator& it, item_t label)
   {
      if( static_cast<unsigned int>(VECTOR::end() - it) < THRESHOLD)
         while(it != VECTOR::end() && (*it).first < label) ++it;
      else
         it = std::lower_bound(it, VECTOR::end(), label);
   }
}

#endif

---