DGtal  0.9.3beta
Data Structures | Public Types | Public Member Functions | Private Member Functions | Private Attributes
DGtal::IndexedListWithBlocks< TValue, N, M > Class Template Reference

#include <DGtal/base/IndexedListWithBlocks.h>

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

Data Structures

struct  AnyBlock
 
union  BlockPointer
 
class  ConstIterator
 
struct  FirstBlock
 
class  Iterator
 
union  ValueOrBlockPointer
 

Public Types

typedef TValue Value
 
typedef std::ptrdiff_t DifferenceType
 
typedef std::size_t SizeType
 
typedef ValueReference
 
typedef ValuePointer
 
typedef const ValueConstReference
 
typedef const ValueConstPointer
 
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)
 
IndexedListWithBlocksoperator= (const IndexedListWithBlocks &other)
 
 ~IndexedListWithBlocks ()
 
SizeType size () const
 
bool empty () const
 
SizeType max_size () const
 
SizeType capacity () const
 
void clear ()
 
Valueoperator[] (unsigned int idx)
 
const Valueoperator[] (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'

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:

Template Parameters
TValuethe type for the values stored in the list.
Nthe number of value stored in the first block.
Mthe number of value stored in the further blocks.

NB: In the following, we use the notations

Definition at line 93 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 119 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 116 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 115 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 105 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 104 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 112 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 100 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>
typedef Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::iterator

Definition at line 118 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>
typedef Value* DGtal::IndexedListWithBlocks< TValue, N, M >::Pointer

Definition at line 103 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>
typedef Pointer DGtal::IndexedListWithBlocks< TValue, N, M >::pointer

Definition at line 114 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>
typedef Value& DGtal::IndexedListWithBlocks< TValue, N, M >::Reference

Definition at line 102 of file IndexedListWithBlocks.h.

template<typename TValue, unsigned int N, unsigned int M>
typedef Reference DGtal::IndexedListWithBlocks< TValue, N, M >::reference

Definition at line 113 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 117 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 101 of file IndexedListWithBlocks.h.

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

Definition at line 99 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 108 of file IndexedListWithBlocks.h.

Constructor & Destructor Documentation

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

Constructor.

template<typename TValue, unsigned int N, unsigned int M>
DGtal::IndexedListWithBlocks< TValue, N, M >::IndexedListWithBlocks ( const IndexedListWithBlocks< TValue, N, M > &  other)

Copy constructor.

Parameters
otherthe object to clone.
template<typename TValue, unsigned int N, unsigned int M>
DGtal::IndexedListWithBlocks< TValue, N, M >::~IndexedListWithBlocks ( )

Destructor.

Member Function Documentation

template<typename TValue, unsigned int N, unsigned int M>
Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::begin ( )
Returns
an iterator pointing on the first element in the container.
template<typename TValue, unsigned int N, unsigned int M>
ConstIterator DGtal::IndexedListWithBlocks< TValue, N, M >::begin ( ) const
Returns
an iterator pointing on the first element in the container.
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>
SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::capacity ( ) const

The number of values currently allocated in the structure.

template<typename TValue, unsigned int N, unsigned int M>
void DGtal::IndexedListWithBlocks< TValue, N, M >::clear ( )

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

template<typename TValue, unsigned int N, unsigned int M>
bool DGtal::IndexedListWithBlocks< TValue, N, M >::empty ( ) const
Returns
'true' if and only if the container is empty. O(1)
template<typename TValue, unsigned int N, unsigned int M>
Iterator DGtal::IndexedListWithBlocks< TValue, N, M >::end ( )
Returns
an iterator pointing after the last element in the container.
template<typename TValue, unsigned int N, unsigned int M>
ConstIterator DGtal::IndexedListWithBlocks< TValue, N, M >::end ( ) const
Returns
an iterator pointing after the last element in the container.
template<typename TValue, unsigned int N, unsigned int M>
void DGtal::IndexedListWithBlocks< TValue, N, M >::erase ( unsigned int  idx)

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

Parameters
idxthe index of the value in the container.
Precondition
idx < size() NB: O( n ), E = O( n - idx )
template<typename TValue, unsigned int N, unsigned int M>
void DGtal::IndexedListWithBlocks< TValue, N, M >::insert ( unsigned int  idx,
const Value value 
)

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

Parameters
idxthe index of the value in the container.
Precondition
idx <= size() (if size(), inserts at the end.
Parameters
valuethe value to insert. NB: O( n ), E = O( n - idx )
template<typename TValue, unsigned int N, unsigned int M>
bool DGtal::IndexedListWithBlocks< TValue, N, M >::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
template<typename TValue, unsigned int N, unsigned int M>
SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::max_size ( ) const

The maximum number of values storable in the structure.

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

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'.
template<typename TValue, unsigned int N, unsigned int M>
Value& DGtal::IndexedListWithBlocks< TValue, N, M >::operator[] ( unsigned int  idx)

Random unprotected read-write access to value at position idx

Parameters
idxthe 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 ) )
template<typename TValue, unsigned int N, unsigned int M>
const Value& DGtal::IndexedListWithBlocks< TValue, N, M >::operator[] ( unsigned int  idx) const

Random unprotected read access to value at position idx

Parameters
idxthe 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 ) )
template<typename TValue, unsigned int N, unsigned int M>
void DGtal::IndexedListWithBlocks< TValue, N, M >::selfDisplay ( std::ostream &  out) const

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.
template<typename TValue, unsigned int N, unsigned int M>
SizeType DGtal::IndexedListWithBlocks< TValue, N, M >::size ( ) const

The number of values stored in the structure. O(1) complexity.

Field Documentation

template<typename TValue, unsigned int N, unsigned int M>
FirstBlock DGtal::IndexedListWithBlocks< TValue, N, M >::myFirstBlock
private

Stores the first block of values.

Definition at line 700 of file IndexedListWithBlocks.h.


The documentation for this class was generated from the following file: