template<typename TData, unsigned int L, typename TWord, unsigned int N, unsigned int M>
class DGtal::LabelledMap< TData, L, TWord, N, M >
Aim: Represents a map label -> data, where the label is an integer between 0 and a constant L-1. It is based on a binary coding of labels and a mixed list/array structure. The assumption is that the number of used labels is much less than L. The objective is to minimize the memory usage.
Description of template class 'LabelledMap' <p> Model of boost::AssociativeContainer,
boost::PairAssociativeContainer,
boost::UniqueAssociativeContainer. As such, it is refinement of
boost::ForwardContainer and boost::Container. It is also a model
of boost::Assignable, boost::CopyConstructible.
V[ 0 ] is the data of the first set label.
V[ 1 ] is the data of the second set label.
...
if less than 3 datas and N = 2
+------+------+------+------+------+
|labels| V[0] | V[1] | ... | 0 |
+------+------+------+------+------+
if only 3 datas and N = 2
+------+------+------+------+------+
|labels| V[0] | V[1] | V[2] | V[3] |
+------+------+------+------+------+
if more than 3 datas and N = 2, M = 4
+------+------+------+------+------+ +------+------+------+------+------+
|labels| V[0] | V[1] | V[2] | ptr --------> | V[3] | V[4] | V[5] | V[6] | ptr --------> ...
+------+------+------+------+------+ +------+------+------+------+------+
This structure is related to the IndexedListWithBlocks, except
that it stores the mapping label -> index. The (maximum) number
of possible labels is fixed at instantiation for optimisation
purposes.
Such a structure is useful when:
- the expected size of this container is small, but may sometimes increase.
- the user wishes sometimes to insert a new data or erase another data.
- the user wishes to have an access to the datas that is as fast as possible given a valid label.
- one wishes to limit as possible the memory usage.
- generally this structure is embedded as the data of a big array.
Model of boost::PairAssociativeContainer and
boost::SimpleAssociativeContainer.
@tparam TData the type for the datas stored in the list.
@tparam L the maximum number of labels.
@tparam TWord the integer used to store the labels (if L >= log_2( digits( TWord ) ) then several consecutive words are stored.), e.g. DGtal::uint8_t.
@tparam N the number of data stored in the first block.
@tparam M the number of data 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 119 of file LabelledMap.h.
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Copy constructor.
- Parameters:
-
| other | the object to clone. |
Definition at line 554 of file LabelledMap.ih.
References DGtal::LabelledMap< TData, L, TWord, N, M >::__FirstBlock::data, DGtal::LabelledMap< TData, L, TWord, N, M >::myFirstBlock, DGtal::LabelledMap< TData, L, TWord, N, M >::myLabels, DGtal::LabelledMap< TData, L, TWord, N, M >::DataOrBlockPointer::nextBlock, and DGtal::LabelledMap< TData, L, TWord, N, M >::size().
{
unsigned int s = N + 1;
{
*currentPointer = new __AnyBlock( *nextBlock );
s += M;
currentPointer = & ( currentPointer->data.nextBlock );
}
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Random unprotected read-write access to data at position idx
- Parameters:
-
| idx | the index of the data in the container. |
- Returns:
- a reference on the data.
- Precondition:
- idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )
Definition at line 747 of file LabelledMap.ih.
References DGtal::LabelledMap< TData, L, TWord, N, M >::__AnyBlock::datas, and DGtal::LabelledMap< TData, L, TWord, N, M >::__AnyBlock::next.
{
if ( idx < N )
else if ( ( idx == N ) && (
size() == N+1 ) )
idx -= N;
while ( idx >= M )
{
idx -= M;
}
ASSERT( ptr != 0 );
return ptr->datas[ idx ];
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Random unprotected read access to data at position idx
- Parameters:
-
| idx | the index of the data in the container. |
- Returns:
- a const reference on the data.
- Precondition:
- idx < size() NB: O( b ), E = O( 1 + ceil( ( idx - N ) / M ) )
Definition at line 725 of file LabelledMap.ih.
References DGtal::LabelledMap< TData, L, TWord, N, M >::__AnyBlock::datas, and DGtal::LabelledMap< TData, L, TWord, N, M >::__AnyBlock::next.
{
if ( idx < N )
else if ( ( idx == N ) && (
size() == N+1 ) )
idx -= N;
while ( idx >= M )
{
idx -= M;
}
ASSERT( ptr != 0 );
return ptr->datas[ idx ];
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
| std::pair< typename DGtal::LabelledMap< TData, L, TWord, N, M >::Iterator, typename DGtal::LabelledMap< TData, L, TWord, N, M >::Iterator > DGtal::LabelledMap< TData, L, TWord, N, M >::equal_range |
( |
const Key & |
x | ) |
|
|
inline |
Get range of equal elements.
Returns the bounds of a range that includes all the elements in the container with a key that compares equal to x. Here, the range will include one element at most.
If x does not match any key in the container, the range returned has a length of zero, with both iterators pointing to the element with nearest key greater than x, if any, or to map::end if x is greater than all the elements in the container.
- Parameters:
-
- Returns:
- a pair, where its member pair::first is an iterator to the lower bound of the range with the same value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the range with the same value as the one that would be returned by upper_bound(x).
Definition at line 935 of file LabelledMap.ih.
{
for ( ; it != it_end; ++it )
{
if ( (*it).first == x )
{
it_end = it; ++it_end;
return std::make_pair( it, it_end );
}
else if ( (*it).first > x ) return std::make_pair( it, it );
}
return std::make_pair( it_end, it_end );
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
| std::pair< typename DGtal::LabelledMap< TData, L, TWord, N, M >::ConstIterator, typename DGtal::LabelledMap< TData, L, TWord, N, M >::ConstIterator > DGtal::LabelledMap< TData, L, TWord, N, M >::equal_range |
( |
const Key & |
x | ) |
const |
|
inline |
Get range of equal elements.
Returns the bounds of a range that includes all the elements in the container with a key that compares equal to x. Here, the range will include one element at most.
If x does not match any key in the container, the range returned has a length of zero, with both iterators pointing to the element with nearest key greater than x, if any, or to map::end if x is greater than all the elements in the container.
- Parameters:
-
- Returns:
- a pair, where its member pair::first is an iterator to the lower bound of the range with the same value as the one that would be returned by lower_bound(x), and pair::second is an iterator to the upper bound of the range with the same value as the one that would be returned by upper_bound(x).
Definition at line 957 of file LabelledMap.ih.
{
ConstIterator it =
begin(), it_end =
end();
for ( ; it != it_end; ++it )
{
if ( (*it).first == x ) return std::make_pair( it, ++it );
else if ( (*it).first > x ) return std::make_pair( it, it );
}
return std::make_pair( it_end, it_end );
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Get iterator to element.
Searches the container for an element with x as key and returns an iterator to it if found, otherwise it returns an iterator to end() (the element past the end of the container).
NB: Another member function, count(), can be used to just check whether a particular key exists. 'count( x ) == 1' is faster than 'find( x ) != end()'.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- An iterator to the element, if the specified key value is found, end() if the specified key is not found in the container.
Definition at line 972 of file LabelledMap.ih.
{
for ( ; it != it_end; ++it )
{
if ( (*it).first == x ) return it;
else if ( (*it).first > x ) return it_end;
}
return it_end;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Get iterator to element.
Searches the container for an element with x as key and returns an iterator to it if found, otherwise it returns an iterator to end() (the element past the end of the container).
NB: Another member function, count(), can be used to just check whether a particular key exists. 'count( x ) == 1' is faster than 'find( x ) != end()'.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- An iterator to the element, if the specified key value is found, end() if the specified key is not found in the container.
Definition at line 987 of file LabelledMap.ih.
{
ConstIterator it =
begin(), it_end =
end();
for ( ; it != it_end; ++it )
{
if ( (*it).first == x ) return it;
else if ( (*it).first > x ) return it_end;
}
return it_end;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Insertion of a new data at given label. Follows std::insert return a pair<iterator,bool>). Note that the data is associated to key only if key was not present in the container.
- Parameters:
-
- Returns:
- a pair <iterator,bool> where iterator points on the pair (key,data) while the boolean is true if a new element was indeed created.
NB: This method is provided to follow the std::AssociativeContainer concept. You are discourage to use this functions since the correct iterator must be recomputed at each insert. Prefer operator[] or fastAt.
Definition at line 869 of file LabelledMap.ih.
{
ASSERT( val.first < L );
if ( ! exists )
{
unsigned int block_size =
size();
}
while ( (*position).first != val.first )
{
++position;
}
return std::make_pair( position, exists );
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Return iterator to lower bound.
Returns an iterator pointing to the first element in the container whose key does not compare less than x (using the container's comparison object), i.e. it is either equal or greater.
Unlike upper_bound(), this member function returns an iterator to the element also if it compares equal to x and not only if it compares greater.
Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- an iterator to the the first element in the container whose key does not compare less than x.
Definition at line 1002 of file LabelledMap.ih.
{
for ( ; it != it_end; ++it )
{
if ( (*it).first >= x ) return it;
}
return it_end;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Return iterator to lower bound.
Returns an iterator pointing to the first element in the container whose key does not compare less than x, i.e. it is either equal or greater.
Unlike upper_bound(), this member function returns an iterator to the element also if it compares equal to x and not only if it compares greater.
Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- an iterator to the the first element in the container whose key does not compare less than x.
Definition at line 1016 of file LabelledMap.ih.
{
ConstIterator it =
begin(), it_end =
end();
for ( ; it != it_end; ++it )
{
if ( (*it).first >= x ) return it;
}
return it_end;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
| DGtal::LabelledMap< TData, L, TWord, N, M > & DGtal::LabelledMap< TData, L, TWord, N, M >::operator= |
( |
const LabelledMap< TData, L, TWord, N, M > & |
other | ) |
|
|
inline |
Assignment.
- Parameters:
-
- Returns:
- a reference on 'this'.
Definition at line 586 of file LabelledMap.ih.
References DGtal::LabelledMap< TData, L, TWord, N, M >::__FirstBlock::data, DGtal::LabelledMap< TData, L, TWord, N, M >::myFirstBlock, DGtal::LabelledMap< TData, L, TWord, N, M >::myLabels, DGtal::LabelledMap< TData, L, TWord, N, M >::DataOrBlockPointer::nextBlock, and DGtal::LabelledMap< TData, L, TWord, N, M >::size().
{
if ( this != &other )
{
unsigned int theSize = other.size();
unsigned int s = N + 1;
while ( s < theSize )
{
*currentPointer = new __AnyBlock( *nextBlock );
s += M;
currentPointer = & ( (*currentPointer)->next );
}
}
return *this;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Swap content. Exchanges the content of the container with the content of mp, which is another map object containing elements of the same type. Sizes may differ.
After the call to this member function, the elements in this container are those which were in mp before the call, and the elements of mp are those which were in this.
NB: not exactly standard ! The iterators pointing on the first block change roles ! The other references and pointers remain valid for the swapped objects.
Definition at line 706 of file LabelledMap.ih.
References DGtal::LabelledMap< TData, L, TWord, N, M >::myFirstBlock, and DGtal::LabelledMap< TData, L, TWord, N, M >::myLabels.
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Return iterator to upper bound.
Returns an iterator pointing to the first element in the container whose key compares greater than x. (>x)
Unlike lower_bound(), this member function does not return an iterator to the element if its key compares equal to x, but only if it compares strictly greater.
Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- an iterator to the the first element in the container whose key compares greater than x.
Definition at line 1030 of file LabelledMap.ih.
{
for ( ; it != it_end; ++it )
{
if ( (*it).first > x ) return it;
}
return it_end;
}
template<typename TData , unsigned int L, typename TWord , unsigned int N, unsigned int M>
Return iterator to upper bound.
Returns an iterator pointing to the first element in the container whose key compares greater than x. (>x)
Unlike lower_bound(), this member function does not return an iterator to the element if its key compares equal to x, but only if it compares strictly greater.
Notice that, internally, all the elements in this container are always ordered by their keys, therefore all the elements that follow the one returned by this function will have a key that compares greater than x.
- Parameters:
-
| x | Key to be searched for (in 0..L-1) |
- Returns:
- an iterator to the the first element in the container whose key compares greater than x.
Definition at line 1044 of file LabelledMap.ih.
{
ConstIterator it =
begin(), it_end =
end();
for ( ; it != it_end; ++it )
{
if ( (*it).first > x ) return it;
}
return it_end;
}
1.8.1.1