OffsetIndexVector.hpp

Go to the documentation of this file.

#ifndef OffsetIndexVector_HPP
#define OffsetIndexVector_HPP

#include "common.hpp"
#include "common/Edge.hpp"
#include <vector>
#include <iterator>     //for test


namespace Bodon
{
   template < class VECTOR = std::vector<void*> >
   class OffsetIndexVector : private VECTOR
   {
      private:
         item_t offset;

      public:

         class iterator
         {
               friend class OffsetIndexVector;
            private:
               OffsetIndexVector* oiv;
               typename VECTOR::iterator it;
            public:            
               iterator(){}

               iterator( OffsetIndexVector* oiv, 
                         const typename VECTOR::iterator& it) : 
                  oiv(oiv), it(it){}

               Edge operator*() const
               {
                  return Edge( oiv->offset + 
                               it - static_cast<VECTOR*>(oiv)->begin(),
                               *it );
               }
               iterator& operator++()
               {
                  do ++it;
                  while( it != static_cast<VECTOR*>(oiv)->end() && 
                         *it == NULL );
                  return *this;
               }
               
               iterator& operator=(const iterator& an_it)
               {
                  if( this != &an_it )
                  {
                     oiv = an_it.oiv;
                     it = an_it.it;
                  }
                  return *this;
               }
               bool operator==(const iterator& an_it) const
               {
                  return it == an_it.it;
               }

               bool operator!=(const iterator& an_it) const
               {
                  return it != an_it.it;
               }
         };

         class const_iterator
         {
               friend class OffsetIndexVector;
            private:
               const OffsetIndexVector* oiv;
               typename VECTOR::const_iterator it;
            public:            
               const_iterator(){}

               const_iterator( const OffsetIndexVector* oiv, 
                               const typename VECTOR::const_iterator& it) : 
                  oiv(oiv), it(it){}

                Edge operator*() const
               {
                  return Edge( oiv->offset + 
                               it - static_cast<const VECTOR*>(oiv)->begin(),
                               *it );
               }
               const_iterator& operator++()
               {
                  do ++it;
                  while( it != static_cast<const VECTOR*>(oiv)->end() && 
                         *it == NULL );
                  return *this;
               }
               
               const_iterator& operator=(const iterator& an_it)
               {
                  if( this != &an_it )
                  {
                     oiv = an_it.oiv;
                     it = an_it.it;
                  }
                  return *this;
               }
               bool operator==(const iterator& an_it) const
               {
                  return it == an_it.it;
               }

               bool operator!=(const const_iterator& an_it) const
               {
                  return it != an_it.it;
               }
         };
      public:
         OffsetIndexVector():VECTOR(){}
         iterator begin()
         {
            return iterator(this, VECTOR::begin());
         }

         const_iterator begin() const 
         {
            return const_iterator(this, VECTOR::begin());
         }

         iterator end()
         {
            return iterator(this, VECTOR::end());
         }
         const_iterator end() const
         {
            return const_iterator(this, VECTOR::end());
         }
         void clear()
         {
            VECTOR::erase( VECTOR::begin(), 
                           VECTOR::end() );
         }
         bool empty() const
         {
            return VECTOR::begin() == VECTOR::end();
         }
         void*& getSubtrie(item_t label)
         {
            return VECTOR::operator[](label - offset);
         }
         void quickErase(item_t pos);
         iterator erase(iterator pos);
        

         void* find(const item_t label) const 
         {
            if( label  >= offset + VECTOR::size() || label < offset)
               return NULL;
            else 
               return VECTOR::operator[](label - offset);
         }

         void*& findOrCreate(item_t label);
         bool lookup(item_t label, void*& subtrie)
         {
            if( label  >= offset + VECTOR::size() )
               return false;
            else
            {
               if( label < offset)
                  subtrie = NULL;
               else subtrie = VECTOR::operator[](label - offset);
               return true;
            }
         }
         void lookupNocheck(item_t label, void*& subtrie) const
         {
            if( label < offset || label  >= offset + VECTOR::size())
               subtrie = NULL;
            else subtrie = VECTOR::operator[](label - offset);
         }
         void lookupNoUppercheck(item_t label, void*& subtrie) const
         {
            if( label < offset )
               subtrie = NULL;
            else subtrie = VECTOR::operator[](label - offset);
         }

         void insert(const std::vector<Edge>& new_edges);

         item_t largestEdgelabel() const
         {
                return VECTOR::size() + offset - 1;
         }
         item_t smallestEdgelabel() const
         {
                return offset;
         }
   };
   template <class VECTOR>
   inline void OffsetIndexVector<VECTOR>::
   insert(const std::vector<Edge>& new_edges)
   {
      if(!new_edges.empty())
      {
         offset = new_edges.front().first;
         VECTOR::reserve(new_edges.back().first - offset +1 );
         VECTOR::resize(new_edges.back().first - offset +1, NULL);
         for(std::vector<Edge>::const_iterator it = new_edges.begin();
            it != new_edges.end(); ++it)
            VECTOR::operator[]((*it).first - offset) = (*it).second;
      }
   }
   template <class VECTOR>
   inline void OffsetIndexVector<VECTOR>::
   quickErase(item_t pos)
   {
      pos -= offset;
      if( pos == 0 )
      {
         do
         {
            VECTOR::erase(VECTOR::begin());
            ++offset;
         }
         while(!VECTOR::empty() && VECTOR::front() == NULL);
      }
      else if( pos == VECTOR::size() - 1 )
      {
         do
         {
            VECTOR::pop_back();
         }
         while( VECTOR::back() == NULL );
      }
      else
         VECTOR::operator[](pos) = NULL;
   }

   template <class VECTOR>
   inline typename OffsetIndexVector<VECTOR>::iterator 
   OffsetIndexVector<VECTOR>::erase( 
      typename OffsetIndexVector<VECTOR>::iterator pos)
   {
      if( pos.it == VECTOR::begin() )
      {
         do
         {
            VECTOR::erase(VECTOR::begin());
            ++offset;
         }
         while(!VECTOR::empty() && VECTOR::front() == NULL);
         return begin();
      }
      else if(pos.it == VECTOR::end()-1)
      {
         do
         {
            VECTOR::pop_back();
         }
         while( VECTOR::back() == NULL );
         return end();
      }
      else
      {
         *(pos.it) = NULL;
         return ++pos;
      }
   }
   template <class VECTOR>
   inline void*& OffsetIndexVector<VECTOR>::findOrCreate(item_t label)
   {
      if(VECTOR::empty())
      {
         offset = label;
         VECTOR::push_back(NULL);
      }
      else if( label >= offset + VECTOR::size())
      {
         VECTOR::resize(label - offset + 1, NULL);
      }
      else if(label < offset)
      {
         VECTOR::insert(VECTOR::begin(), offset - label, NULL);
         offset = label;
      }
      return VECTOR::operator[](label - offset);
   }
   
}

#endif

---