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

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

#include <DGtal/base/IndexedListWithBlocks.h>

Data Structures

struct  AnyBlock
 
union  BlockPointer
 Forward declaration. More...
 
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 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

◆ const_iterator

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.

◆ const_pointer

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.

◆ const_reference

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.

◆ ConstPointer

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.

◆ ConstReference

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.

◆ difference_type

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.

◆ DifferenceType

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.

◆ iterator

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.

◆ Pointer

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.

◆ pointer

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.

◆ Reference

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.

◆ reference

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.

◆ size_type

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.

◆ SizeType

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.

◆ Value

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.

◆ value_type

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

Definition at line 111 of file IndexedListWithBlocks.h.

Constructor & Destructor Documentation

◆ IndexedListWithBlocks() [1/2]

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

Constructor.

◆ IndexedListWithBlocks() [2/2]

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.

◆ ~IndexedListWithBlocks()

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

Destructor.

Member Function Documentation

◆ begin() [1/2]

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.

◆ begin() [2/2]

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.

◆ BOOST_STATIC_ASSERT() [1/2]

template<typename TValue , unsigned int N, unsigned int M>
DGtal::IndexedListWithBlocks< TValue, N, M >::BOOST_STATIC_ASSERT ( M >=  2)
private

◆ BOOST_STATIC_ASSERT() [2/2]

template<typename TValue , unsigned int N, unsigned int M>
DGtal::IndexedListWithBlocks< TValue, N, M >::BOOST_STATIC_ASSERT ( N >=  1)
private

◆ capacity()

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.

◆ clear()

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.

◆ empty()

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)

◆ end() [1/2]

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.

◆ end() [2/2]

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.

◆ erase()

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 )

◆ insert()

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 )

◆ isValid()

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.

◆ max_size()

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.

◆ operator=()

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

◆ operator[]() [1/2]

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

◆ operator[]() [2/2]

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

◆ selfDisplay()

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.

◆ size()

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

◆ myFirstBlock

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: