#include <IndexedListWithBlocks.h>

Collaboration diagram for DGtal::IndexedListWithBlocks< TValue, N, M >:

Data Structures
struct	AnyBlock
union	BlockPointer
class	ConstIterator
struct	FirstBlock
class	Iterator
union	ValueOrBlockPointer
	Used in blocks to finish it or to point to the next block. More...

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
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

Public Member Functions
	IndexedListWithBlocks ()
	IndexedListWithBlocks (const IndexedListWithBlocks &other)
IndexedListWithBlocks &	operator= (const IndexedListWithBlocks &other)
	~IndexedListWithBlocks ()
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
void	selfDisplay (std::ostream &out) const
bool	isValid () const

Private Member Functions
	BOOST_STATIC_ASSERT (N >=1)
	BOOST_STATIC_ASSERT (M >=2)

Private Attributes
FirstBlock	myFirstBlock

Detailed Description

template<typename TValue, unsigned int N, unsigned int M>
class DGtal::IndexedListWithBlocks< TValue, N, M >

Aim: Represents a mixed list/array structure which is useful in some context. It is essentially a list of blocks.

 Description of template class 'IndexedListWithBlocks' <p>@verbatim

if less than 3 values and N = 2 +------+------+------+------+------+ | size | V[0] | V[1] | ... | 0 | +------+------+------+------+------+

if only 3 values and N = 2 +------+------+------+------+------+ | size | V[0] | V[1] | V[2] | V[3] | +------+------+------+------+------+

if more than 3 values and N = 2, M = 4 +------+------+------+------+------+ +------+------+------+------+------+ | size | V[0] | V[1] | V[2] | ptr --------> | V[3] | V[4] | V[5] | V[6] | ptr --------> ... +------+------+------+------+------+ +------+------+------+------+------+

 Such a structure is useful when:
 - the user knows at which position/index lies its value.
 - the expected size of this container is small, but may sometimes increase.
 - the user wishes sometimes to insert a new value or erase another value. Note that in this case the user knows that further indices have changed.
 - the user wishes to have a random access to the values that is as fast as possible.
 - one wishes to limit as possible the memory usage.
 - generally this structure is embedded as the value of a big array.

 @tparam TValue the type for the values stored in the list.
 @tparam N the number of value stored in the first block.
 @tparam M the number of value stored in the further blocks.

 NB: In the following, we use the notations
 - n is the size of the container
 - b is the number of blocks ( b = 1 + (size()-N) / M ).

Definition at line 94 of file IndexedListWithBlocks.h.

Member Typedef Documentation

template<typename TValue, unsigned int N, unsigned int M>

typedef ConstIterator DGtal::IndexedListWithBlocks< TValue, N, M >::const_iterator

Definition at line 120 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef ConstPointer DGtal::IndexedListWithBlocks< TValue, N, M >::const_pointer

Definition at line 117 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef ConstReference DGtal::IndexedListWithBlocks< TValue, N, M >::const_reference

Definition at line 116 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef const Value* DGtal::IndexedListWithBlocks< TValue, N, M >::ConstPointer

Definition at line 106 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef const Value& DGtal::IndexedListWithBlocks< TValue, N, M >::ConstReference

Definition at line 105 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef DifferenceType DGtal::IndexedListWithBlocks< TValue, N, M >::difference_type

Definition at line 113 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef std::ptrdiff_t DGtal::IndexedListWithBlocks< TValue, N, M >::DifferenceType

Definition at line 101 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::iterator

Definition at line 119 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Value* DGtal::IndexedListWithBlocks< TValue, N, M >::Pointer

Definition at line 104 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Pointer DGtal::IndexedListWithBlocks< TValue, N, M >::pointer

Definition at line 115 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Value& DGtal::IndexedListWithBlocks< TValue, N, M >::Reference

Definition at line 103 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Reference DGtal::IndexedListWithBlocks< TValue, N, M >::reference

Definition at line 114 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::size_type

Definition at line 118 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef std::size_t DGtal::IndexedListWithBlocks< TValue, N, M >::SizeType

Definition at line 102 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef TValue DGtal::IndexedListWithBlocks< TValue, N, M >::Value

Definition at line 100 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>

typedef Value DGtal::IndexedListWithBlocks< TValue, N, M >::value_type

Definition at line 109 of file IndexedListWithBlocks.h.

Constructor & Destructor Documentation

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::IndexedListWithBlocks ( )

inline

Constructor.

Definition at line 416 of file IndexedListWithBlocks.ih.

{ // default constructor of myFirstBlock is automatically called.

}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::IndexedListWithBlocks ( const IndexedListWithBlocks< TValue, N, M > & other )

inline

Copy constructor.

Parameters:

other the object to clone.

Definition at line 431 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::FirstBlock::data, DGtal::IndexedListWithBlocks< TValue, N, M >::myFirstBlock, DGtal::IndexedListWithBlocks< TValue, N, M >::ValueOrBlockPointer::nextBlock, and DGtal::IndexedListWithBlocks< TValue, N, M >::FirstBlock::size.

  : myFirstBlock( other.myFirstBlock )
{
  unsigned int s = N + 1; // there is one more stored value in the last block.
  const AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
  AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
  while ( s < myFirstBlock.size  )
    {
      *currentPointer = new AnyBlock( *nextBlock );
      s += M;
      currentPointer = & ( currentPointer->data.nextBlock );
    }
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::~IndexedListWithBlocks ( )

inline

Destructor.

Definition at line 423 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::clear().

{
  clear();
}

Member Function Documentation

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::begin ( )

inline

Returns:: an iterator pointing on the first element in the container.

Definition at line 594 of file IndexedListWithBlocks.ih.

{
  return Iterator( myFirstBlock, 0 );
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::ConstIterator DGtal::IndexedListWithBlocks< TValue, N, M >::begin ( ) const

inline

Returns:: an iterator pointing on the first element in the container.

Definition at line 612 of file IndexedListWithBlocks.ih.

{
  return ConstIterator( myFirstBlock, 0 );
}

template<typename TValue, unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::BOOST_STATIC_ASSERT ( N >= 1 )

private

template<typename TValue, unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::BOOST_STATIC_ASSERT ( M >= 2 )

private

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::capacity ( ) const

inline

The number of values currently allocated in the structure.

Definition at line 517 of file IndexedListWithBlocks.ih.

{
  return ( size() <= (N+1) )
    ? N+1
    : ( 1 + ( size() - 1 - N ) / M ) * M + N;
}

template<typename TValue , unsigned int N, unsigned int M>

void DGtal::IndexedListWithBlocks< TValue, N, M >::clear ( )

inline

Removes all the values stored in the structure. O(b) complexity.

Definition at line 473 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::AnyBlock::next.

Referenced by DGtal::IndexedListWithBlocks< TValue, N, M >::~IndexedListWithBlocks().

{
  AnyBlock* nextBlock = myFirstBlock.data.nextBlock;
  while ( nextBlock != 0 )
    {
      AnyBlock* ptr = nextBlock;
      nextBlock = nextBlock->next;
      delete ptr;
    }
  myFirstBlock.size = 0;
  myFirstBlock.data.nextBlock = 0;
}

template<typename TValue , unsigned int N, unsigned int M>

bool DGtal::IndexedListWithBlocks< TValue, N, M >::empty ( ) const

inline

Returns:: 'true' if and only if the container is empty. O(1)

Definition at line 499 of file IndexedListWithBlocks.ih.

{
  return size() == 0;
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::end ( )

inline

Returns:: an iterator pointing after the last element in the container.

Definition at line 603 of file IndexedListWithBlocks.ih.

{
  return Iterator( myFirstBlock, size() );
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::ConstIterator DGtal::IndexedListWithBlocks< TValue, N, M >::end ( ) const

inline

Returns:: an iterator pointing after the last element in the container.

Definition at line 621 of file IndexedListWithBlocks.ih.

{
  return ConstIterator( myFirstBlock, size() );
}

template<typename TValue , unsigned int N, unsigned int M>

void DGtal::IndexedListWithBlocks< TValue, N, M >::erase ( unsigned int idx )

inline

Removal of a value at a given position. Following values are shifted.

Parameters:

idx	the index of the value in the container.

Precondition:: idx < size() NB: O( n ), E = O( n - idx )

Definition at line 582 of file IndexedListWithBlocks.ih.

{
  ASSERT( idx < size() ); // end is not ok.
  myFirstBlock.erase( idx );
}

template<typename TValue , unsigned int N, unsigned int M>

void DGtal::IndexedListWithBlocks< TValue, N, M >::insert	(	unsigned int	idx,
		const Value &	value
	)

inline

Insertion of a new value at given position. The former value at this position and the next ones are shifted.

Parameters:

idx	the index of the value in the container.

Precondition:: idx <= size() (if size(), inserts at the end.

Parameters:

value the value to insert. NB: O( n ), E = O( n - idx )

Definition at line 572 of file IndexedListWithBlocks.ih.

{
  ASSERT( idx <= size() ); // end is ok.
  myFirstBlock.insert( idx, value );
}

template<typename TValue , unsigned int N, unsigned int M>

bool DGtal::IndexedListWithBlocks< TValue, N, M >::isValid ( ) const

inline

Checks the validity/consistency of the object.

Returns:: 'true' if the object is valid, 'false' otherwise.

Definition at line 665 of file IndexedListWithBlocks.ih.

{
    return true;
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::max_size ( ) const

inline

The maximum number of values storable in the structure.

Definition at line 508 of file IndexedListWithBlocks.ih.

{
  return SizeType( -1 ) / (2*sizeof( Value ));
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M > & DGtal::IndexedListWithBlocks< TValue, N, M >::operator= ( const IndexedListWithBlocks< TValue, N, M > & other )

inline

Assignment.

Parameters:

other the object to copy.

Returns:: a reference on 'this'.

Definition at line 449 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::FirstBlock::data, DGtal::IndexedListWithBlocks< TValue, N, M >::myFirstBlock, and DGtal::IndexedListWithBlocks< TValue, N, M >::ValueOrBlockPointer::nextBlock.

{
  if ( this != &other )
    {
      clear();
      myFirstBlock = other.myFirstBlock;
      // there is one more stored value in the last block.
      unsigned int s = N + 1; 
      const AnyBlock* nextBlock = other.myFirstBlock.data.nextBlock;
      AnyBlock** currentPointer = & myFirstBlock.data.nextBlock;
      while ( s < myFirstBlock.size  )
        {
          *currentPointer = new AnyBlock( *nextBlock );
          s += M;
          currentPointer = & ( (*currentPointer)->next );
        }
    }
  return *this;
}

template<typename TValue , unsigned int N, unsigned int M>

DGtal::IndexedListWithBlocks< TValue, N, M >::Value & DGtal::IndexedListWithBlocks< TValue, N, M >::operator[] ( unsigned int idx )

inline

Random unprotected read-write access to value at position idx

Parameters:

idx	the index of the value in the container.

Returns:: a reference on the value.

Precondition:: idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )

Definition at line 550 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::AnyBlock::next, and DGtal::IndexedListWithBlocks< TValue, N, M >::AnyBlock::values.

{
  ASSERT( idx < size() );
  if ( idx < N )
    return myFirstBlock.values[ idx ];
  else if ( ( idx == N ) && ( size() == N+1 ) )
    return myFirstBlock.data.lastValue;
  AnyBlock* ptr = myFirstBlock.data.nextBlock;
  idx -= N;
  while ( idx >= M )
    {
      idx -= M;
      ptr = ptr->next;
    }
  ASSERT( ptr != 0 );
  return ptr->values[ idx ];
}

template<typename TValue , unsigned int N, unsigned int M>

const DGtal::IndexedListWithBlocks< TValue, N, M >::Value & DGtal::IndexedListWithBlocks< TValue, N, M >::operator[] ( unsigned int idx ) const

inline

Random unprotected read access to value at position idx

Parameters:

idx	the index of the value in the container.

Returns:: a const reference on the value.

Precondition:: idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )

Definition at line 528 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::AnyBlock::next, and DGtal::IndexedListWithBlocks< TValue, N, M >::AnyBlock::values.

{
  ASSERT( idx < size() );
  if ( idx < N )
    return myFirstBlock.values[ idx ];
  else if ( ( idx == N ) && ( size() == N+1 ) )
    return myFirstBlock.data.lastValue;
  const AnyBlock* ptr = myFirstBlock.data.nextBlock;
  idx -= N;
  while ( idx >= M )
    {
      idx -= M;
      ptr = ptr->next;
    }
  ASSERT( ptr != 0 );
  return ptr->values[ idx ];
}

template<typename TValue , unsigned int N, unsigned int M>

void DGtal::IndexedListWithBlocks< TValue, N, M >::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 637 of file IndexedListWithBlocks.ih.

References DGtal::IndexedListWithBlocks< TValue, N, M >::ConstIterator::myValues.

{
  if ( size() == 0 ) out << "()";
  else
    {
      ConstIterator it = begin();
      ConstIterator it_end = end();
      ConstIterator it_last = it;
      out << "(";
      out << *it;
      ++it;
      for ( ; it != it_end; ++it )
        {
          out << ( ( it_last.myValues == it.myValues ) ? ',' : ';' );
          out << *it;
          it_last = it;
        }
      out << ")";
    }
}