LabelledMap.h

#pragma once

#if defined(LabelledMap_RECURSES)
#error Recursive header files inclusion detected in LabelledMap.h
#else // defined(LabelledMap_RECURSES)

#define LabelledMap_RECURSES

#if !defined LabelledMap_h

#define LabelledMap_h

// Inclusions
#include <cstring>
#include <cmath>
#include <iostream>
#include "DGtal/base/Common.h"
#include "DGtal/base/Labels.h"
//#include "DGtal/base/FakeKeyValuePair.h"

namespace DGtal
{

  // template class LabelledMap
  template <typename TData, unsigned int L, typename TWord,
            unsigned int N, unsigned int M>
  class LabelledMap
  {
    BOOST_STATIC_ASSERT( L >= 1 );
    BOOST_STATIC_ASSERT( N >= 0 );
    BOOST_STATIC_ASSERT( M >= 2 );
  public:
    // ----------------------- Public types ------------------------------
    typedef LabelledMap<TData, L, TWord, N, M> Self;
    typedef TData Data;
    typedef TWord Word;
    typedef Labels<L, Word> LabelsType;
    typedef typename LabelsType::Label Label;
    typedef Label Key;
    typedef std::pair<const Key, Data> Value;
    //typedef FakeKeyValuePair<Key, Data> Value;

    typedef typename LabelsType::ConstIterator LabelsConstIterator;
    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;      //< Forward declaration
    class ConstIterator; //< Forward declaration
    class KeyCompare;    //< Forward declaration
    class ValueCompare;  //< Forward declaration
    // ----------------------- Standard types ------------------------------
    typedef Key key_type;
    typedef Value value_type;
    typedef Data data_type;
    typedef Data mapped_type;
    typedef DifferenceType difference_type;
    typedef Reference reference;
    typedef Pointer pointer;
    typedef ConstReference const_reference;
    typedef ConstPointer const_pointer;
    typedef SizeType size_type;
    typedef ConstIterator iterator;
    typedef ConstIterator const_iterator;
    typedef KeyCompare key_compare;
    typedef ValueCompare value_compare;

    struct __FirstBlock; //< Forward declaration
    struct __AnyBlock; //< Forward declaration

    union BlockPointer {
      __FirstBlock* first;
      __AnyBlock* any;
    };

    union DataOrBlockPointer {
      Data lastData; // used when at the end of the list
      __AnyBlock* nextBlock;  // used otherwise
    };

    struct __FirstBlock {
      inline
      __FirstBlock() 
      { data.nextBlock = 0; }

      inline
      Data & insert( unsigned int idx, unsigned int size, const Data & v )
      {
        ASSERT( idx <= size );
        if ( size < N )
          {
            std::copy_backward( datas + idx, datas + size, datas + size + 1 );
            return ( datas[ idx ] = v );
          }
        else if ( size == N )
          {
            if ( idx < N )
              {
                data.lastData = datas[ N - 1 ];
                std::copy_backward( datas + idx, datas + N - 1, datas + N );
                return ( datas[ idx ] = v );
              }
            else // idx == N
              {
                return ( data.lastData = v );
              }
          }
        else if ( size == (N+1) )
          {
            // This cannot be tested.
            // ASSERT( data.nextBlock == 0 );
            __AnyBlock* next = new __AnyBlock;
            if ( idx < N )
              {
                next->datas[ 0 ] = datas[ N - 1 ];
                next->datas[ 1 ] = data.lastData;
                std::copy_backward( datas + idx, datas + N - 1, datas + N );
                data.nextBlock = next;
                return ( datas[ idx ] = v );
              }
            else if ( idx == N )
              {
                next->datas[ 1 ] = data.lastData;
                data.nextBlock = next;
                return ( next->datas[ 0 ] = v );
              }
            else //if ( idx > N )
              {
                next->datas[ 0 ] = data.lastData;
                data.nextBlock = next;
                return ( next->datas[ 1 ] = v );
              }
          }
        else // size > N + 1
          {
            if ( idx < N )
              {
                Data v1 = datas[ N - 1 ];
                std::copy_backward( datas + idx, datas + N - 1, datas + N );
                data.nextBlock->insert( 0, size - N, v1 );
                return ( datas[ idx ] = v );
              }
            else
              return data.nextBlock->insert( idx - N, size - N, v );
          }
      }

      inline 
      void erase( unsigned int idx, unsigned int size )
      {
        // 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 data.
            std::copy( datas + idx + 1, datas + size, datas + idx );
            data.nextBlock = 0;
          }
        else if ( size == N + 2 )
          { 
            if ( idx < N )
              {
                std::copy( datas + idx + 1, datas + N, datas + idx );
                datas[ N - 1 ] = data.nextBlock->datas[ 0 ];
                Data tmp = data.nextBlock->datas[ 1 ];
                delete data.nextBlock;
                data.lastData = tmp;
              }
            else if ( idx == N )
              {
                Data tmp = data.nextBlock->datas[ 1 ];
                delete data.nextBlock;
                data.lastData = tmp;
              }
            else // idx == N + 1
              {
                Data tmp = data.nextBlock->datas[ 0 ];
                delete data.nextBlock;
                data.lastData = tmp;
              }
          }
        else // size > N + 2
          {
            if ( idx < N )
              {
                std::copy( datas + idx + 1, datas + N, datas + idx );
                datas[ N - 1 ] = data.nextBlock->datas[ 0 ];
                data.nextBlock = data.nextBlock->erase( 0, size - N );
              }
            else
              data.nextBlock = data.nextBlock->erase( idx - N, size - N );
          }
      }

      Data datas[ N ];
      DataOrBlockPointer data;
    };

    struct __AnyBlock {
      inline __AnyBlock() : next( 0 ) {}

      inline
      Data & insert( unsigned int idx, unsigned int size, const Data & v )
      {
        ASSERT( idx <= size );
        if ( idx >= M ) 
          {
            if ( next == 0 )
              {
                ASSERT( size == M );
                ASSERT( idx == M );
                next = new __AnyBlock;
                return ( next->datas[ 0 ] = v );
              }
            else
              {
                ASSERT( size > M );
                return next->insert( idx - M, size - M, v );
              }
          }
        else 
          { // idx < M
            if ( size <= ( M - 1) ) // ( size < ( M - 1) )
              {
                ASSERT( next == 0 );
                std::copy_backward( datas + idx, datas + size, 
                                    datas + size + 1 );
                return ( datas[ idx ] = v );
              }
            else
              {
                Data v1 = datas[ M - 1 ];
                std::copy_backward( datas + idx, datas + M - 1, datas + M );
                // if ( size >= M )
                //   {
                if ( next == 0 )
                  {
                    ASSERT( size == M );
                    next = new __AnyBlock;
                    next->datas[ 0 ] = v1;
                  }
                else
                  {
                    ASSERT( size > M );
                    next->insert( 0, size - M, v1 );
                  }
                // }
                return ( datas[ idx ] = v );
              }
          }
      }

      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( datas + idx + 1, datas + M, datas + idx );
            if ( next != 0 )
              {
                ASSERT( size > M );
                datas[ M - 1 ] = next->datas[ 0 ];
                next = next->erase( 0, size - M );
              }
          }
        else
          next = next->erase( idx - M, size - M );
        return this;
      }


      Data datas[ M ];
      __AnyBlock* next;
    };

    class BlockIterator {
    public:
      typedef BlockIterator Self;
      typedef TData 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 myDatas of the iterator
      unsigned int myNbDatas; //< number of valid datas in array \a myDatas
      Data* myDatas;         //< array of \a myNbDatas datas.
      __AnyBlock* myNext;        //< pointer to next block or 0 if last block.

      friend class LabelledMap;

    protected:
      BlockIterator( __FirstBlock & block, unsigned int idx, unsigned int size );
      
    public:
      ~BlockIterator();

      BlockIterator();

      BlockIterator( const BlockIterator & 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 BlockConstIterator {
    public:
      typedef BlockConstIterator Self;
      typedef TData 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 myDatas of the iterator
      unsigned int myNbDatas; //< number of valid datas in array \a myDatas
      const Data* myDatas;   //< array of \a myNbDatas datas.
      const __AnyBlock* myNext;  //< pointer to next block or 0 if last block.

      friend class LabelledMap;

    protected:
      BlockConstIterator( const __FirstBlock & block, unsigned int idx, unsigned int size );
      
    public:
      ~BlockConstIterator();

      BlockConstIterator();

      BlockConstIterator( const BlockConstIterator & 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;
      
      
    };

    // ----------------------- Iterator services ------------------------------
  public:

    class ConstIterator {
    public:
      friend class LabelledMap;
      typedef ConstIterator Self;
      // The following line is removed so that gcc-4.2 and gcc-4.6 compiles. 
      //typedef typename LabelledMap<TData, L, TWord, N, M>::Value Value;
      typedef const 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 Reference const_reference;
      typedef std::forward_iterator_tag iterator_category;

    private:
      LabelsConstIterator myLabelsIt; 
      BlockConstIterator myBlockIt;

    protected:
      ConstIterator( LabelsConstIterator lIt, BlockConstIterator bIt );

    public:
      ~ConstIterator();

      ConstIterator();

      ConstIterator( const ConstIterator & other );

      Self & operator= ( const Self & other );
      
      Reference operator*() const;
     
      Pointer operator->() const;
      
      Self& operator++();
      
      Self operator++( int );

      bool operator==( const Self & other ) const;
      
      bool operator!=( const Self & other ) const;


      Data & _data() const;
      const Data & _const_data() const;
    };
    
    typedef ConstIterator Iterator;
    class KeyCompare {
    public:
      inline KeyCompare() {}
      inline bool operator()( Key k1, Key k2 ) const
      {
        return k1 < k2;
      }
    };
    class ValueCompare {
    public:
      inline ValueCompare() {}
      inline bool operator()( const Value & v1, const Value & v2 ) const
      {
        return v1.first < v2.first;
      }
    };

    
    // ----------------------- Standard services ------------------------------
  public:

    LabelledMap();

    LabelledMap ( const LabelledMap & other );

    template <typename InputIterator>
    LabelledMap( InputIterator first, InputIterator last );

    LabelledMap & operator= ( const LabelledMap & other );

    ~LabelledMap();

    // ----------------------- Container services -----------------------------
  public:

    const LabelsType & labels() const;

    SizeType size() const;

    bool empty() const;

    SizeType max_size() const;

    SizeType capacity() const;

    KeyCompare key_comp() const;

    ValueCompare value_comp() const;

    void swap( Self & other );

    void clear();

    SizeType count( const Key & key ) const;

    Data & operator[]( const Key & key );

    const Data & operator[]( const Key & key ) const;

    Data & fastAt( const Key & key );

    const Data & fastAt( const Key & key ) const;

    std::pair<Iterator, bool> insert( const Value & val );

    Iterator insert( Iterator position, const Value & val );

    template <typename InputIterator>
    void insert( InputIterator first, InputIterator last );

    void erase( Iterator position );

    SizeType erase( Key key );

    void erase( Iterator first, Iterator last );

    ConstIterator begin() const;

    ConstIterator end() const;

    Iterator begin();

    Iterator end();

    std::pair<Iterator, Iterator> equal_range( const Key & x );

    std::pair<ConstIterator, ConstIterator> equal_range( const Key & x ) const;

    Iterator find ( const Key & x );

    ConstIterator find ( const Key & x ) const;

    Iterator lower_bound( const Key & x );

    ConstIterator lower_bound ( const Key & x ) const;

    Iterator upper_bound ( const Key & x );

    ConstIterator upper_bound ( const Key & x ) const;


    void blockClear( unsigned int size );

    Data & blockAt( unsigned int idx );

    const Data & blockAt( unsigned int idx ) const;

    Data & blockInsert( unsigned int idx, unsigned int block_size, const Data & data );

    void blockErase( unsigned int idx );


    BlockIterator blockBegin();

    BlockIterator blockEnd();

    BlockConstIterator blockBegin() const;

    BlockConstIterator blockEnd() const;

    // ----------------------- Interface --------------------------------------
  public:

    void selfDisplay ( std::ostream & out ) const;

    bool isValid() const;

    // ------------------------- Protected Datas ------------------------------
  private:
    // ------------------------- Private Datas --------------------------------
  private:

    LabelsType myLabels;

    __FirstBlock myFirstBlock;

    // ------------------------- Hidden services ------------------------------
  protected:

    // ------------------------- Internals ------------------------------------
  private:

  }; // end of class LabelledMap


  template  <typename TData, unsigned int L, typename TWord,
             unsigned int N, unsigned int M>
  std::ostream&
  operator<< ( std::ostream & out, 
               const LabelledMap<TData, L, TWord, N, M> & object );

  namespace detail {

    struct LabelledMapMemFunctor 
    { 
      double _p; double _q;
      unsigned int _sL;
      unsigned int _sV;      
      unsigned int _sP;
      unsigned int _sA;
      LabelledMapMemFunctor( double p, double q,
                             unsigned int sL, unsigned int sV,
                             unsigned int sP, unsigned int sA )
        : _p( p ), _q( q ), _sL( sL ), _sV( sV ), _sP( sP ), _sA( sA )
      {}
      
      inline
      double fctNM( unsigned int N, unsigned int M ) const
      {
        double alpha0 = _sL + _sV * ( N+1 );
        double beta0 = _sV * M + _sA + _sP;
        return alpha0 
          + beta0 * _q * pow(1.0 - _p, (double)N+1) 
          * ( 1.0 + pow(1.0 - _p, (double)M-1 ) 
              / ( 1.0 - pow(1.0 - _p, (double)M ) ) );
      }
      inline
      double fctNMpq( unsigned int N, unsigned int M, double p, double q ) const
      {
        double alpha0 = _sL + _sV * ( N+1 );
        double beta0 = _sV * M + _sA + _sP;
        return alpha0 
          + beta0 * q * pow(1.0 - p, (double)N+1) 
          * ( 1.0 + pow(1.0 - p, (double)M-1 ) 
              / ( 1.0 - pow(1.0 - p, (double)M ) ) );
      }

    };

    template <typename TData>
    std::pair< unsigned int, unsigned int >
    argminLabelledMapMemoryUsageForGeometricDistribution
    ( unsigned int L, double prob_no_data, double prob_one_data );
  }

} // namespace DGtal


// Includes inline functions.
#include "DGtal/base/LabelledMap.ih"

//                                                                           //

#endif // !defined LabelledMap_h

#undef LabelledMap_RECURSES
#endif // else defined(LabelledMap_RECURSES)