IndexedListWithBlocks.h

 
#pragma once
 
#if defined(IndexedListWithBlocks_RECURSES)
#error Recursive header files inclusion detected in IndexedListWithBlocks.h
#else // defined(IndexedListWithBlocks_RECURSES)
#define IndexedListWithBlocks_RECURSES
 
#if !defined IndexedListWithBlocks_h
#define IndexedListWithBlocks_h
 
// Inclusions
#include <cstring>
#include <iostream>
#include "DGtal/base/Common.h"
 
namespace DGtal
{
 
  // template class IndexedListWithBlocks
  template <typename TValue, unsigned int N, unsigned int M>
  class IndexedListWithBlocks
  {
    BOOST_STATIC_ASSERT( N >= 1 );
    BOOST_STATIC_ASSERT( M >= 2 );
  public:
    // ----------------------- Public types ------------------------------
    typedef TValue Value;
    typedef std::ptrdiff_t DifferenceType;
    typedef std::size_t SizeType;
    typedef Value& Reference;
    typedef Value* Pointer;
    typedef const Value& ConstReference;
    typedef const Value* ConstPointer;
 
    class Iterator;
    class ConstIterator;
 
    // ----------------------- Standard types ------------------------------
    typedef Value value_type;
    typedef DifferenceType difference_type;
    typedef Reference reference;
    typedef Pointer pointer;
    typedef ConstReference const_reference;
    typedef ConstPointer const_pointer;
    typedef SizeType size_type;
    typedef Iterator iterator;
    typedef ConstIterator const_iterator;
    
    struct FirstBlock; 
    struct AnyBlock; 
 
    union BlockPointer {
      FirstBlock* first;
      AnyBlock* any;
    };
 
    union ValueOrBlockPointer {
      Value lastValue; // used when at the end of the list
      AnyBlock* nextBlock;  // used otherwise
    };
 
    struct FirstBlock {
      inline
      FirstBlock() : size( 0 )
      { data.nextBlock = 0; }
 
      inline
      void insert( unsigned int idx, const Value & v )
      {
        if ( size <= N )
          {
            ASSERT( idx <= size );
            // works also in the case we use 'data' to store a N+1-th value.
            std::copy_backward( values + idx, values + size, values + size + 1 );
            values[ idx ] = v;
          }
        else if ( size == (N+1) )
          {
            ASSERT( idx <= size );
            // This cannot be tested.
            // ASSERT( data.nextBlock == 0 );
            AnyBlock* next = new AnyBlock;
            if ( idx < N )
              {
                next->values[ 0 ] = values[ N - 1 ];
                next->values[ 1 ] = data.lastValue;
                std::copy_backward( values + idx, values + N - 1, values + N );
                values[ idx ] = v;
              }
            else if ( idx == N )
              {
                next->values[ 0 ] = v;
                next->values[ 1 ] = data.lastValue;
              }
            else if ( idx > N )
              {
                next->values[ 0 ] = data.lastValue;
                next->values[ 1 ] = v;
              }
            data.nextBlock = next;
          }
        else // size > N + 1
          {
            if ( idx < N )
              {
                Value v1 = values[ N - 1 ];
                std::copy_backward( values + idx, values + N - 1, values + N );
                data.nextBlock->insert( 0, size - N, v1 );
                values[ idx ] = v;
              }
            else
              data.nextBlock->insert( idx - N, size - N, v );
          }
        ++size;
      }
 
      inline 
      void erase( unsigned int idx )
      {
        // std::cerr << "FirstBlock::erase(" << idx << ")"
        //        << " this=" << this
        //        << " next=" << data.nextBlock
        //        << std::endl;
        ASSERT( idx < size );
        if ( size <= ( N + 1 ) )
          {
            // works also in the case we use 'data' to store a N+1-th value.
            std::copy( values + idx + 1, values + size, values + idx );
            data.nextBlock = 0;
          }
        else if ( size == N + 2 )
          { 
            if ( idx < N )
              {
                std::copy( values + idx + 1, values + N, values + idx );
                values[ N - 1 ] = data.nextBlock->values[ 0 ];
                Value tmp = data.nextBlock->values[ 1 ];
                delete data.nextBlock;
                data.lastValue = tmp;
              }
            else if ( idx == N )
              {
                Value tmp = data.nextBlock->values[ 1 ];
                delete data.nextBlock;
                data.lastValue = tmp;
              }
            else // idx == N + 1
              {
                Value tmp = data.nextBlock->values[ 0 ];
                delete data.nextBlock;
                data.lastValue = tmp;
              }
          }
        else // size > N + 2
          {
            if ( idx < N )
              {
                std::copy( values + idx + 1, values + N, values + idx );
                values[ N - 1 ] = data.nextBlock->values[ 0 ];
                data.nextBlock = data.nextBlock->erase( 0, size - N );
              }
            else
              data.nextBlock = data.nextBlock->erase( idx - N, size - N );
          }
        --size;
      }
 
      unsigned int size;
      Value values[ N ];
      ValueOrBlockPointer data;
    };
 
    struct AnyBlock {
      inline AnyBlock() : next( 0 ) {}
 
      inline
      void insert( unsigned int idx, unsigned int size, const Value & v )
      {
        ASSERT( idx <= size );
        if ( idx >= M ) 
          {
            if ( next == 0 )
              {
                ASSERT( idx == M );
                next = new AnyBlock;
                next->values[ 0 ] = v;
              }
            else
              next->insert( idx - M, size - M, v );
          }
        else 
          { // idx < M
            if ( size < ( M - 1) )
              {
                std::copy_backward( values + idx, values + size, 
                                    values + size + 1 );
                values[ idx ] = v;
              }
            else
              {
                Value v1 = values[ M - 1 ];
                std::copy_backward( values + idx, values + M - 1, values + M );
                values[ idx ] = v;
                if ( size >= M )
                  {
                    if ( next == 0 )
                      {
                        ASSERT( size == M );
                        next = new AnyBlock;
                        next->values[ 0 ] = v1;
                      }
                    else
                      next->insert( 0, size - M, v1 );
                  }
              }
          }
      }
 
      inline 
      AnyBlock* erase( unsigned int idx, unsigned int size )
      {
        // std::cerr << "AnyBlock::erase(" << idx << "," << size << ")" 
        //        << " this=" << this
        //        << " next=" << next
        //        << std::endl;
        if ( size == 1 )
          {
            ASSERT( idx == 0 );
            delete this;
            return 0;
          }
        if ( idx < M )
          {
            std::copy( values + idx + 1, values + M, values + idx );
            if ( next != 0 )
              {
                ASSERT( size > M );
                values[ M - 1 ] = next->values[ 0 ];
                next = next->erase( 0, size - M );
              }
          }
        else
          next = next->erase( idx - M, size - M );
        return this;
      }
 
 
      Value values[ M ];
      AnyBlock* next;
    };
 
    class Iterator {
    public:
      typedef Iterator Self;
      typedef TValue Value;
      typedef Value* Pointer;
      typedef Value& Reference;
      typedef std::ptrdiff_t DifferenceType; 
 
      // ----------------------- std types ----------------------------------
      typedef Value value_type;
      typedef std::size_t size_type;
      typedef DifferenceType difference_type;
      typedef Pointer pointer;
      typedef Reference reference;
      //typedef const Reference const_reference;
      typedef std::forward_iterator_tag iterator_category;
 
 
    protected:
      unsigned int myIdx;      
      unsigned int myNbValues; 
      Value* myValues;         
      AnyBlock* myNext;        
 
      friend class IndexedListWithBlocks;
 
    protected:
      Iterator( FirstBlock & block, unsigned int idx );
      
    public:
      ~Iterator();
 
      Iterator();
 
      Iterator( const Iterator & other );
 
      Self & operator= ( const Self & other );
      
      Reference operator*() const;
     
      Pointer operator->() const;
      
      Self& operator++();
      
      Self operator++( int );
 
      Self& operator+=( DifferenceType n );
 
      Reference operator[]( DifferenceType n ) const;
    
      bool operator==( const Self & other ) const;
      
      bool operator!=( const Self & other ) const;
      
      
    };
 
 
    class ConstIterator {
    public:
      typedef ConstIterator Self;
      typedef TValue Value;
      typedef const Value* Pointer;
      typedef const Value& Reference;
      typedef std::ptrdiff_t DifferenceType; 
 
      // ----------------------- std types ----------------------------------
      typedef Value value_type;
      typedef std::size_t size_type;
      typedef DifferenceType difference_type;
      typedef Pointer pointer;
      typedef Reference reference;
      // typedef Reference const_reference;
      typedef std::forward_iterator_tag iterator_category;
 
 
    protected:
      unsigned int myIdx;      
      unsigned int myNbValues; 
      const Value* myValues;   
      const AnyBlock* myNext;  
 
      friend class IndexedListWithBlocks;
 
    protected:
      ConstIterator( const FirstBlock & block, unsigned int idx );
      
    public:
      ~ConstIterator();
 
      ConstIterator();
 
      ConstIterator( const ConstIterator & other );
 
      Self & operator= ( const Self & other );
      
      Reference operator*() const;
     
      Pointer operator->() const;
      
      Self& operator++();
      
      Self operator++( int );
 
      Self& operator+=( DifferenceType n );
 
      Reference operator[]( DifferenceType n ) const;
    
      bool operator==( const Self & other ) const;
      
      bool operator!=( const Self & other ) const;
      
      
    };
 
 
    // ----------------------- Standard services ------------------------------
  public:
 
    IndexedListWithBlocks();
 
    IndexedListWithBlocks ( const IndexedListWithBlocks & other );
 
    IndexedListWithBlocks & operator= ( const IndexedListWithBlocks & other );
 
    ~IndexedListWithBlocks();
 
    // ----------------------- Container services -----------------------------
  public:
    
    SizeType size() const;
 
    bool empty() const;
 
    SizeType max_size() const;
 
    SizeType capacity() const;
 
    void clear();
 
    Value & operator[]( unsigned int idx );
 
    const Value & operator[]( unsigned int idx ) const;
 
    void insert( unsigned int idx, const Value & value );
 
    void erase( unsigned int idx );
 
    Iterator begin();
 
    Iterator end();
 
    ConstIterator begin() const;
 
    ConstIterator end() const;
 
    // ----------------------- Interface --------------------------------------
  public:
 
    void selfDisplay ( std::ostream & out ) const;
 
    bool isValid() const;
 
    // ------------------------- Protected Datas ------------------------------
  private:
    // ------------------------- Private Datas --------------------------------
  private:
 
    FirstBlock myFirstBlock;
 
    // ------------------------- Hidden services ------------------------------
  protected:
 
    // ------------------------- Internals ------------------------------------
  private:
 
  }; // end of class IndexedListWithBlocks
 
 
  template  <typename TValue, unsigned int N, unsigned int M>
  std::ostream&
  operator<< ( std::ostream & out, 
               const IndexedListWithBlocks<TValue, N, M> & object );
 
} // namespace DGtal
 
 
// Includes inline functions.
#include "DGtal/base/IndexedListWithBlocks.ih"
 
//                                                                           //
 
#endif // !defined IndexedListWithBlocks_h
 
#undef IndexedListWithBlocks_RECURSES
#endif // else defined(IndexedListWithBlocks_RECURSES)