deque.h

Go to the documentation of this file.

#ifndef CPPTL_DEQUE_H_INCLUDED
# define CPPTL_DEQUE_H_INCLUDED

# include "_stlimpl.h"

namespace CppTL {

struct YesType 
{
   char dummy[256];
};

struct NoType
{
};

template<class T>
struct IsInteger
{
   typedef NoType value_type;
};

#define CPPTL_DECLARE_INTEGER_TYPE( type ) \
   template<> struct IsInteger<type> {     \
      typedef YesType value_type;          \
   }

CPPTL_DECLARE_INTEGER_TYPE( bool );
CPPTL_DECLARE_INTEGER_TYPE( char );
CPPTL_DECLARE_INTEGER_TYPE( signed char );
CPPTL_DECLARE_INTEGER_TYPE( unsigned char );
CPPTL_DECLARE_INTEGER_TYPE( signed int );
CPPTL_DECLARE_INTEGER_TYPE( unsigned int );
CPPTL_DECLARE_INTEGER_TYPE( signed short);
CPPTL_DECLARE_INTEGER_TYPE( unsigned short );
CPPTL_DECLARE_INTEGER_TYPE( signed long );
CPPTL_DECLARE_INTEGER_TYPE( unsigned long );


class DequeBase
{
public:
   typedef unsigned int size_t;
   enum { elementPerPage = 32 };

protected:
   DequeBase();
   ~DequeBase();

   void swap( DequeBase &other );
   void prependPage( void *newPage );
   void appendPage( void *newPage );

   void growPageMap( size_t pagesToPrepend, size_t pagesToAppend );

protected:
   // array with list of page map.
   // the array is allocated bigger then required and the map is
   // initialy placed in its middle to allow growth from the begin or the end.
   void **pageMapBuffer_;
   void **pageMap_;
   size_t pageMapBufferSize_;
   size_t usedPages_;

   // only the first and last page may be partially filled. All other pages
   // are fully filled.
   size_t firstPageStartIndex_;
   size_t lastPageEndIndex_;

private:
   void initialize();
};


class DequeIteratorCommonBase
{
public:
   typedef DequeBase::size_t size_t;
   typedef int difference_type;
   enum { elementPerPage = DequeBase::elementPerPage };

   size_t index() const;

protected:
   DequeIteratorCommonBase();

   DequeIteratorCommonBase( void **pageMapBegin,
                            void **pageMapEnd,
                            void **pageMapCurrent,
                            size_t indexInCurrentPage,
                            size_t firstPageStartIndex,
                            size_t lastPageStartIndex );

   void increment();

   void decrement();

   void advance( difference_type n );

   difference_type computeDistance( const DequeIteratorCommonBase &other ) const;

   inline bool isEqual( const DequeIteratorCommonBase &other ) const
   {
      return indexInCurrentPage_ == other.indexInCurrentPage_  &&
             pageMapCurrent_ == other.pageMapCurrent_;
   }

   inline bool isLess( const DequeIteratorCommonBase &other ) const
   {
      return pageMapCurrent_ < other.pageMapCurrent_
             || (pageMapCurrent_ == other.pageMapCurrent_  && 
                 indexInCurrentPage_ < other.indexInCurrentPage_ );
   }

protected:
   void **pageMapBegin_;
   void **pageMapEnd_;
   void **pageMapCurrent_;
   size_t indexInCurrentPage_;
   size_t firstPageStartIndex_;
   size_t lastPageStartIndex_;
};


template<class T>
class DequeIteratorBase : public DequeIteratorCommonBase
{
public:
   typedef DequeBase::size_t size_t;
   typedef int difference_type;
   enum { elementPerPage = DequeBase::elementPerPage };

   inline T **currentPage() const
   {
      return pageMapCurrent_;
   }

   inline size_t indexInCurrentPage() const
   {
      return indexInCurrentPage_;
   }

   bool operator ==( const DequeIteratorBase &other ) const
   {
      return isEqual( other );
   }

   bool operator !=( const DequeIteratorBase &other ) const
   {
      return !isEqual( other );
   }

   bool operator <( const DequeIteratorBase &other ) const
   {
      return isLess( other );
   }

   bool operator <=( const DequeIteratorBase &other ) const
   {
      return !other.isLess( *this );
   }

   bool operator >=( const DequeIteratorBase &other ) const
   {
      return !isLess( other );
   }

   bool operator >( const DequeIteratorBase &other ) const
   {
      return other.isLess( *this );
   }

protected:
   DequeIteratorBase()
   {
   }

   DequeIteratorBase( void **pageMapBegin,
                      void **pageMapEnd,
                      void **pageMapCurrent,
                      size_t indexInCurrentPage,
                      size_t firstPageStartIndex,
                      size_t lastPageStartIndex )
      : DequeIteratorCommonBase( pageMapBegin, pageMapEnd, 
                                 pageMapCurrent, indexInCurrentPage, 
                                 firstPageStartIndex, lastPageStartIndex )
   {
   }


   T &deref() const
   {
      CPPTL_ASSERT_MESSAGE( pageMapCurrent_ != pageMapEnd_  
                            ||  indexInCurrentPage_ != lastPageStartIndex_,
                            "DequeIterator: dereferencing invalid iterator" );
      return (*pageMapCurrent_)[indexInCurrentPage];
   }
};


template<class T, class Traits>
class DequeIterator : public DequeIteratorBase<T>
{
public:
   typedef DequeBase::size_t size_t;
   typedef int difference_type;
   typedef T value_type;
   typedef CPPTL_TYPENAME Traits::reference reference;
   typedef CPPTL_TYPENAME Traits::pointer pointer;

   typedef DequeIterator<T,Traits> SelfType;
   typedef DequeIteratorBase<T> SuperClass;
   typedef DequeIterator< T, ::CppTL::Impl::ConstIteratorTraits<T> > ConstDequeIterator;
   typedef DequeIterator< T, ::CppTL::Impl::NonConstIteratorTraits<T> > NonConstDequeIterator;

   DequeIterator()
   {
   }

   // This constructor ensure that it is possible to construct a
   // const iterator from a non const iterator.
   DequeIterator( const NonConstDequeIterator &other )
      : DequeIteratorBase<T>( other )
   {
   }

   DequeIterator( void **pageMapBegin,
                  void **pageMapEnd,
                  void **pageMapCurrent,
                  size_t indexInCurrentPage,
                  size_t firstPageStartIndex,
                  size_t lastPageStartIndex )
      : SuperClass( pageMapBegin, pageMapEnd, 
                    pageMapCurrent, indexInCurrentPage, 
                    firstPageStartIndex, lastPageStartIndex )
   {
   }

   SelfType &operator++()
   {
      increment();
      return *this;
   }

   SelfType &operator++( int )
   {
      SelfType temp( *this );
      ++*this;
      return temp;
   }

   SelfType &operator--()
   {
      decrement();
      return *this;
   }

   SelfType &operator--( int )
   {
      SelfType temp( *this );
      --*this;
      return temp;
   }

   SelfType &operator +=( difference_type n )
   {
      advance( n );
      return *this;
   }

   SelfType operator +( difference_type n ) const
   {
      SelfType temp( *this );
      return temp += n;
   }

   SelfType &operator -=( difference_type n )
   {
      advance( -n );
      return *this;
   }

   SelfType operator -( difference_type n ) const
   {
      SelfType temp( *this );
      return temp -= n;
   }

   reference operator[]( difference_type n ) const
   {
      return *( *this + n );
   }

   reference operator *() const
   {
      return deref();
   }

   reference operator->() const
   {
      return deref();
   }

   difference_type operator -( const SelfType &other ) const
   {
      return computeDistance( other );
   }
};


template<class T>
class Deque : public DequeBase
{
public:
   typedef T value_type;
   typedef T *pointer;
   typedef const T *const_pointer;
   typedef T &reference;
   typedef const T &const_reference;
   typedef unsigned int size_t;
   typedef DequeIterator< T, ::CppTL::Impl::NonConstIteratorTraits<T> > iterator;
   typedef DequeIterator< T, ::CppTL::Impl::ConstIteratorTraits<T> > const_iterator;
   typedef Deque<T> SelfType;

   Deque()
   {
   }

   Deque( size_t count )
   {
      insert( begin(), count, T() );
   }

   Deque( size_t count, const T &value )
   {
      insert( begin(), count, value );
   }

   Deque( const_iterator first, const_iterator last )
   {
      insert( begin(), first, last );
   }

   ~Deque()
   {
      if ( pageMap_  &&  usedPages_ > 0 )
      {
         ::CppTL::Impl::destruct_range( begin(), end() );
         void **pageMapEnd = pageMap_ + usedPages_;
         for ( void **pageMap = pageMap_; pageMap != pageMapEnd; ++pageMap )
            freePage( *pageMap );
      }
   }

   size_t size() const
   {
      return (usedPages_+1) * elementPerPage - firstPageStartIndex_ - lastPageEndIndex_;
   }

   bool empty() const
   {
      return usedPages_ == 0  
             ||  ( usedPages_ == 1  &&  firstPageStartIndex_ == lastPageEndIndex_ );
   }

   void push_front( const T &element )
   {
      // should we allocate a new page ?
      if ( usedPages_ == 0  ||  firstPageStartIndex_ == 0 )
      {
         T *newPage = allocatePage()
         CPPTL_TRY_BEGIN
         {
            prependPage( newPage ); // may throw
         }
         CPPTL_TRY_END_CLEANUP( releasePage( newPage ) )
         firstPageStartIndex_ = elementPerPage;
         if ( usedPages_ == 1 )
            lastPageEndIndex_ = elementPerPage;
      }
      T *newElement = page(0) + firstPageStartIndex_ - 1;
      // If the following copy constructor, then the deque is changed but in
      // a state equivalent to before the call to push_front().
      new (newElement)( element );     // may throw
      --firstPageStartIndex_;
   }

   void push_back( const T &element )
   {
      // should we allocate a new page ?
      if ( usedPages_ == 0  ||  lastPageEndIndex_ == elementPerPage )
      {
         T *newPage = allocatePage()
         CPPTL_TRY_BEGIN
         {
            appendPage( newPage ); // may throw
         }
         CPPTL_TRY_END_CLEANUP( releasePage( newPage ) )
         lastPageEndIndex_ = 0;
      }
      T *newElement = page(usedPages_-1) + lastPageEndIndex_;
      // If the following copy constructor, then the deque is changed but in
      // a state equivalent to before the call to push_back().
      new (newElement)( element );     // may throw
      ++lastPageEndIndex_;
   }

   void swap( SelfType &other )
   {
      DequeBase::swap( other );
   }

   void pop_front()
   {
      CPPTL_ASSERT_MESSAGE( !empty(), "Deque<T>::pop_front(): logic error, deque is empty" );
      normalizeFirstPageStartIndex();
      T *newElement = page(0) + firstPageStartIndex_;
      newElement->~T();
      ++firstPageStartIndex_;
   }

   void pop_back()
   {
      CPPTL_ASSERT_MESSAGE( !empty(), "Deque<T>::pop_back(): logic error, deque is empty" );
      normalizeLastPageEndIndex();
      T *newElement = page(usedPages_ - 1) + lastPageEndIndex_ - 1;
      newElement->~T();
      --lastPageEndIndex_;
   }

   void resize( size_t newSize )
   {
      size_t oldSize = size();
      if ( newSize < oldSize )
      {
         usedPages_ = 0;
         lastPageEndIndex_ = firstPageStartIndex_;
      }
      else if ( newSize > oldSize )
      {
         insert( end(), newSize-oldSize, T() );
      }
   }

   T &back()
   {
      CPPTL_ASSERT_MESSAGE( !empty(), "Deque<T>::back(): logic error, deque is empty" );
      normalizeLastPageEndIndex();
      return page(usedPages_)[lastPageEndIndex_];
   }

   T &front()
   {
      CPPTL_ASSERT_MESSAGE( !empty(), "Deque<T>::front(): logic error, deque is empty" );
      normalizeFirstPageStartIndex();
      return page(0)[firstPageStartIndex_];
   }

   T &at( size_t index )
   {
      CPPTL_ASSERT_MESSAGE( index < size(), "Deque<T>::at(): logic error, bad index" );
      index += firstPageStartIndex_;
      indexInPage = index % elementPerPage;
      return pageMap_[index/elementPerPage][indexInPage];
   }

   T &operator[]( size_t index )
   {
      return at( index );
   }

   const T &back() const
   {
      return const_cast<SelfType *>(this)->back();
   }

   const T &front() const
   {
      return const_cast<SelfType *>(this)->front();
   }

   const T &at( size_t index ) const
   {
      return const_cast<SelfType *>(this)->at(index);
   }

   const T &operator[]( size_t index ) const
   {
      return const_cast<SelfType *>(this)->at(index);
   }

   void clear()
   {
      Deque empty;
      swap( empty );
   }

   iterator begin()
   {
      return iterator( pageMap_, pageMap_ + usedPages_, 
                       pageMap_, firstPageStartIndex_,
                       firstPageStartIndex_, lastPageEndIndex_ );
   }

   iterator end()
   {
      T **lastPage = usedPages_ ? pageMap_ + usedPages_ - 1 : pageMap_;
      return iterator( pageMap_, pageMap_ + usedPages_, 
                       lastPage, lastPageEndIndex_,
                       firstPageStartIndex_, lastPageEndIndex_ );
   }

   const_iterator begin() const
   {
      return const_iterator( pageMap_, pageMap_ + usedPages_, 
                             pageMap_, firstPageStartIndex_,
                             firstPageStartIndex_, lastPageEndIndex_ );
   }

   const_iterator end() const
   {
      T **lastPage = usedPages_ ? pageMap_ + usedPages_ - 1 : pageMap_;
      return const_iterator( pageMap_, pageMap_ + usedPages_, 
                             lastPage, lastPageEndIndex_,
                             firstPageStartIndex_, lastPageEndIndex_ );
   }

   iterator erase( iterator where )
   {
      size_t index = where.index();
      size_t currentSize = size();
      CPPTL_ASSERT_MESSAGE( index < currentSize, "Deque<T>::erase(): invalid iterator" );
      if ( index < currentSize / 2 )
      {
         ::CppTL::Impl::copy_backwards( begin(), where-1, where );
         pop_front();
      }
      else
      {
         ::CppTL::Impl::cpptl_copy( where+1, end(), where );
         pop_back();
      }
   }

   iterator erase( iterator first, iterator last )
   {
      size_t indexFirst = first.index();
      size_t indexLast = last.index();
      size_t currentSize = size();
      size_t afterErasedRange = size - indexLast;
      CPPTL_ASSERT_MESSAGE( index < currentSize, "Deque<T>::erase(): invalid iterator" );
      if ( indexFirst < afterErasedRange )
      {
         iterator beginIt = begin();
         ::CppTL::Impl::copy_backwards( beginIt, first, last );
         ::CppTL::Impl::destruct_range( beginIt, last - indexFirst );
         usedPages_ -= lastErasedIt.currentPage() - beginIt.currentPage();
         lastPageEndIndex_ = lastErasedIt.indexInCurrentPage();
      }
      else
      {
         iterator endIt = end();
         ::CppTL::Impl::cpptl_copy( last, endIt, first );
         ::CppTL::Impl::destruct_range( first + afterErasedRange, endIt );
         usedPages_ -= endIt.currentPage() - beginErasedRange.currentPage();
         lastPageEndIndex_ = beginErasedRange.indexInCurrentPage();
      }
   }

   iterator insert( iterator where, const value_type &value )
   {
      size_t index = where.index();
      size_t currentSize = size();
      CPPTL_ASSERT_MESSAGE( index < currentSize, "Deque<T>::erase(): invalid iterator" );
      if ( index < currentSize / 2 )
      {
         reserveAtFront( 1 );
         iterator itBegin = begin();
         iterator itWhere = itBegin + index;
         ::CppTL::Impl::copy_and_destroy( itWhere, itWhere+1, itBegin );
         new (&*itWhere)( value );
      }
      else
      {
         reserveAtEnd( 1 );
         iterator itWhere = begin() + index;
         iterator itEnd = end();
         ::CppTL::Impl::copy_backwards_and_destroy( itWhere+1, itEnd-1, itEnd );
         new (&*itWhere)( value );
      }
   }

   iterator insert( iterator where, size_t count, const value_type &value )
   {
      size_t count = last - first;
      size_t currentSize = size();
      size_t whereIndex = where.index();
      size_t elementAfter = currentSize - whereIndex;
      if ( whereIndex < elementAfter )    // insert at beginning, less elements to move
      {
         reserveAtFront( count );      // may throw
         iterator itBegin = begin();
         ::CppTL::Impl::copy_and_destroy( itBegin + count, itBegin + (count+whereIndex), 
                                          itBegin );
         ::CppTL::Impl::copy_with_construct_value( itBegin + index, count, value );
      }
      else  // insert at end
      {
         reserveAtEnd( count );
         iterator itNewWhere = begin() + whereIndex;
         iterator itOldEnd = itNewWhere + ( currentSize - whereIndex );
         ::CppTL::Impl::copy_backwards_and_destroy( itNewWhere, itOldEnd, itEnd );
         ::CppTL::Impl::copy_with_construct_value( itNewWhere , count, value );
      }
      CPPTL_ASSERT_MESSAGE( size() == currentSize + count, "Deque<T>::insert: internal logic error." );
   }

   iterator insert( iterator where, const_iterator first, const_iterator last )
   {
      size_t count = last - first;
      size_t currentSize = size();
      size_t whereIndex = where.index();
      size_t elementAfter = currentSize - whereIndex;
      if ( whereIndex < elementAfter )    // insert at beginning, less elements to move
      {
         reserveAtFront( count );      // may throw
         iterator itBegin = begin();
         ::CppTL::Impl::copy_and_destroy( itBegin + count, itBegin + (count+whereIndex), 
                                          itBegin );
         ::CppTL::Impl::copy_with_construct( first, last, itBegin + index );
      }
      else  // insert at end
      {
         reserveAtEnd( count );
         iterator itNewWhere = begin() + whereIndex;
         iterator itOldEnd = itNewWhere + ( currentSize - whereIndex );
         ::CppTL::Impl::copy_backwards_and_destroy( itNewWhere, itOldEnd, itEnd );
         ::CppTL::Impl::copy_with_construct( first, last, itNewWhere );
      }
      CPPTL_ASSERT_MESSAGE( size() == currentSize + count, "Deque<T>::insert: internal logic error." );
   }

private:
   T **page( size_t index )
   {
      CPPTL_ASSERT_MESSAGE( index <= usedPages_, "Deque<T>::page(): invalid parameter" );
      return static_cast<T **>( pageMap_ + index );
   }

   void reserveAtFront( size_t count )
   {
      if ( count <= firstPageStartIndex_ )
      {
         firstPageStartIndex_ -= count;
      }
      else
      {
         size_t newPageCount = (count - firstPageStartIndex_ + elementPerPage - 1) / elementPerPage;
         firstPageStartIndex_ = (firstPageStartIndex_ - count) % elementPerPage + elementPerPage;
         while ( --newPageCount >= 0 )
         {
            T *newPage = allocatePage()
            CPPTL_TRY_BEGIN
            {
               prependPage( newPage ); // may throw
            }
            CPPTL_TRY_END_CLEANUP( releasePage( newPage ) )
         }
      }
   }

   void reserverAtEnd( size_t count )
   {
      size_t remainingInLastPage = elementPerPage - lastPageEndIndex_;
      if ( count <= remainingInLastPage )
      {
         lastPageEndIndex_ += count;
      }
      else
      {
         size_t newPageCount = (count - remainingInLastPage + elementPerPage - 1) / elementPerPage;
         lastPageEndIndex_ = (lastPageEndIndex_ - count ) % elementPerPage + elementPerPage;
         while ( --newPageCount >= 0 )
         {
            T *newPage = allocatePage()
            CPPTL_TRY_BEGIN
            {
               appendPage( newPage ); // may throw
            }
            CPPTL_TRY_END_CLEANUP( releasePage( newPage ) )
         }
      }
   }

   inline void normalizeFirstPageStartIndex()
   {
      if ( firstPageStartIndex_ == elementPerPage )
      {
         CPPTL_ASSERT_MESSAGE( usedPages_ > 0, "Deque<T>::normalizeFirstPageStartIndex(): internal logic error." );
         ++pageMap_;
         --usedPages_;
         firstPageStartIndex_ = 0;
      }
   }

   inline void normalizeLastPageEndIndex()
   {
      if ( lastPageEndIndex_ == 0 )
      {
         CPPTL_ASSERT_MESSAGE( usedPages_ > 0, "Deque<T>::normalizeLastPageEndIndex(): internal logic error." );
         --usedPages_;
         lastPageEndIndex_ = elementPerPage;
      }
   }

   T *allocatePage()
   {
      return static_cast<T *>( malloc( sizeof(T) * elementPerPage ) );
   }

   void freePage( T *page )
   {
      free( page );
   }
};



} // namespace CppTL

#endif // CPPTL_DEQUE_H_INCLUDED