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

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.

Template Parameters

TValue	the type for the values stored in the list.
N	the number of value stored in the first block.
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 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

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

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

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 )

◆ 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

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

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

◆ 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

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

◆ 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

out	the 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:

IndexedListWithBlocks.h

Data Structures

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ const_pointer

◆ const_reference

◆ ConstPointer

◆ ConstReference

◆ difference_type

◆ DifferenceType

◆ iterator

◆ Pointer

◆ pointer

◆ Reference

◆ reference

◆ size_type

◆ SizeType

◆ Value

◆ value_type

Constructor & Destructor Documentation

◆ IndexedListWithBlocks() [1/2]

◆ IndexedListWithBlocks() [2/2]

◆ ~IndexedListWithBlocks()

Member Function Documentation

◆ begin() [1/2]

◆ begin() [2/2]

◆ BOOST_STATIC_ASSERT() [1/2]

◆ BOOST_STATIC_ASSERT() [2/2]

◆ capacity()

◆ clear()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ erase()

◆ insert()

◆ isValid()

◆ max_size()

◆ operator=()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ selfDisplay()

◆ size()

Field Documentation

◆ myFirstBlock