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; //< Forward declaration
    struct AnyBlock; //< Forward declaration

    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; //< only positive offsets allowed.

      // ----------------------- 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;      //< current index in \a myValues of the iterator
      unsigned int myNbValues; //< number of valid values in array \a myValues
      Value* myValues;         //< array of \a myNbValues values.
      AnyBlock* myNext;        //< pointer to next block or 0 if last block.

      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; //< only positive offsets allowed.

      // ----------------------- 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;      //< current index in \a myValues of the iterator
      unsigned int myNbValues; //< number of valid values in array \a myValues
      const Value* myValues;   //< array of \a myNbValues values.
      const AnyBlock* myNext;  //< pointer to next block or 0 if last block.

      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)