RangeMap< K, V, MAP > Class Template Reference

#include <rangemap.h>

Detailed Description

template<typename K, typename V, typename MAP = BurstTrieMapSelector<>>
class maxon::RangeMap< K, V, MAP >

Unlike a normal map, a RangeMap maps whole ranges (of integral values) to values. For each contiguous range having the same value, only a single entry is needed, so a RangeMap will perform much better than a normal map if it is likely that consecutive keys are mapped to the same value.

RangeMap<UInt, String> map;
if (!map.Insert(Range<UInt>(10, 40), "Alice"_s))
return false;
if (!map.Insert(Range<UInt>(30, 50), "Carol"_s))
return false;
if (!map.Erase(Range<UInt>(15, 25)))
return false;

The above example results in a map with three entries: The range 10 ... 14 is mapped to "Alice" as well as the range 26 ... 29, while the range 30 ... 50 is mapped to "Carol".

RangeMap ensures that its ranges don't overlap, and that directly adjacent ranges (with no gap between them) which are mapped to the same value are merged to a single range.

RangeMap supports the usual iterators. They iterate through the map per range.

Template Parameters
KType of keys. This must be an integral type.
VType of values.
MAPA map selector template to choose the underlying map implementation to use. This has to be an ordered map. Note that the default is the BurstTrieMap which only allows unsigned integral types.

Classes

class  EntryIteratorBase
 
class  KeyIteratorBase
 
class  ValueIteratorBase
 

Public Types

using MapType = typename MAP::template Type< K, typename std::conditional< std::is_same< V, UnitType >::value, RangeSetPair< K >, Pair< K, V > >::type >
 
using Range = maxon::Range< K >
 
using ValueType = typename MapType::ValueType
 
using MapValue = typename MapType::ValueType
 
using Iterator = typename MapType::template IteratorTemplate< false, EntryIteratorBase >
 
using ConstIterator = typename MapType::template IteratorTemplate< true, EntryIteratorBase >
 
using KeyIterator = typename MapType::template IteratorTemplate< false, KeyIteratorBase >
 
using ConstKeyIterator = typename MapType::template IteratorTemplate< true, KeyIteratorBase >
 
using ValueIterator = typename MapType::template IteratorTemplate< false, ValueIteratorBase >
 
using ConstValueIterator = typename MapType::template IteratorTemplate< true, ValueIteratorBase >
 

Public Member Functions

 RangeMap ()
 
 RangeMap (RangeMap &&src)
 
 MAXON_OPERATOR_MOVE_ASSIGNMENT (RangeMap)
 
Result< void > CopyFrom (const RangeMap &src)
 
void Flush ()
 
void Reset ()
 
Int GetCount () const
 
Bool IsEmpty () const
 
Bool IsPopulated () const
 
Int GetMemorySize () const
 
ResultMem Insert (K rMinValue, K rMaxValue, const V &value)
 
ResultMem Insert (K key, const V &value)
 
ResultMem Insert (const Range &range, const V &value)
 
const V * FindValue (K key) const
 
const V * FindRange (K key, Range &rangeOut) const
 
ResultMem Erase (K rMinValue, K rMaxValue)
 
ResultMem Erase (K key)
 
ResultMem Erase (const Range &range)
 
SFINAEHelper< String, K >::type ToString (const FormatStatement *fmt) const
 
Iterator Begin ()
 
Iterator End ()
 
ConstIterator Begin () const
 
ConstIterator End () const
 
KeyIterator GetKeys ()
 
ConstKeyIterator GetKeys () const
 
ValueIterator GetValues ()
 
ConstValueIterator GetValues () const
 
const MapTypeGetMap () const
 
UInt GetHashCode () const
 
Bool operator== (const RangeMap &other) const
 
Bool operator!= (const RangeMap &other) const
 
const MapTypeGetUnderlyingMap () const
 

Static Public Member Functions

static Result< void > DescribeIO (const DataSerializeInterface &stream)
 

Private Member Functions

 MAXON_DISALLOW_COPY_AND_ASSIGN (RangeMap)
 

Private Attributes

MapType _map
 

Member Typedef Documentation

◆ MapType

using MapType = typename MAP::template Type<K, typename std::conditional<std::is_same<V, UnitType>::value, RangeSetPair<K>, Pair<K, V> >::type>

◆ Range

using Range = maxon::Range<K>

◆ ValueType

using ValueType = typename MapType::ValueType

◆ MapValue

using MapValue = typename MapType::ValueType

◆ Iterator

using Iterator = typename MapType::template IteratorTemplate<false, EntryIteratorBase>

◆ ConstIterator

using ConstIterator = typename MapType::template IteratorTemplate<true, EntryIteratorBase>

◆ KeyIterator

using KeyIterator = typename MapType::template IteratorTemplate<false, KeyIteratorBase>

◆ ConstKeyIterator

using ConstKeyIterator = typename MapType::template IteratorTemplate<true, KeyIteratorBase>

◆ ValueIterator

using ValueIterator = typename MapType::template IteratorTemplate<false, ValueIteratorBase>

◆ ConstValueIterator

using ConstValueIterator = typename MapType::template IteratorTemplate<true, ValueIteratorBase>

Constructor & Destructor Documentation

◆ RangeMap() [1/2]

RangeMap ( )

◆ RangeMap() [2/2]

RangeMap ( RangeMap< K, V, MAP > &&  src)

Member Function Documentation

◆ MAXON_OPERATOR_MOVE_ASSIGNMENT()

MAXON_OPERATOR_MOVE_ASSIGNMENT ( RangeMap< K, V, MAP )

◆ CopyFrom()

Result<void> CopyFrom ( const RangeMap< K, V, MAP > &  src)

Makes this map a copy of src.

Parameters
[in]srcSource from which the entries are taken.
Returns
True if copying succeeded.

◆ Flush()

void Flush ( void  )

Flushes the map. This removes all entries. Depending on the underlying map, memory may still be held for later re-use.

See also
Reset()

◆ Reset()

void Reset ( void  )

Resets the map. This removes all entries and frees any memory held by the map, so the map will be in a state as if it had been newly constructed.

See also
Flush()

◆ GetCount()

Int GetCount ( void  ) const

Returns the number of entries in this map. Each contiguous key range where the keys are mapped to the same value requires a single entry.

Returns
Number of entries.

◆ IsEmpty()

Bool IsEmpty ( ) const

Checks if the RangeMap is empty. This is the same as GetCount() == 0

Returns
True if this RangeMap does not contain any elements.

◆ IsPopulated()

Bool IsPopulated ( void  ) const

Checks if the RangeMap is populated. This is the same as GetCount() != 0

Returns
True if this RangeMap contains any elements.

◆ GetMemorySize()

Int GetMemorySize ( void  ) const

Calculates the memory usage for this map. Keys and Values must have a public member GetMemorySize that return the element size.

Returns
Memory size in bytes.

◆ Insert() [1/3]

ResultMem Insert ( rMinValue,
rMaxValue,
const V &  value 
)

Maps the range rMinValue ... rMaxValue to value. Existing overlapping mappings are truncated, split or removed as necessary, or they are merged with the new mapping if their values are equal. If the range is empty (rMaxValue is less than rMinValue), nothing happens.

Parameters
[in]rMinValueLower boundary of the range.
[in]rMaxValueUpper boundary of the range.
[in]valueValue to which the range shall be mapped.
Returns
False if a memory allocation failed.

◆ Insert() [2/3]

ResultMem Insert ( key,
const V &  value 
)

Maps the single value key (i.e., the range key ... key consisting of a single element) to value. Existing mappings which overlap key are truncated, split or removed as necessary, or they may be extended to include key if their values are equal.

Parameters
[in]keyA single key which shall be mapped.
[in]valueValue to which the range shall be mapped.
Returns
False if a memory allocation failed.

◆ Insert() [3/3]

ResultMem Insert ( const Range range,
const V &  value 
)

Maps the given range to value. Existing overlapping mappings are truncated, split or removed as necessary, or they are merged with the new mapping if their values are equal. If the range is empty, nothing happens.

Parameters
[in]rangeRange which shall be mapped.
[in]valueValue to which the range shall be mapped.
Returns
False if a memory allocation failed.

◆ FindValue()

const V* FindValue ( key) const

Finds the value associated with the given key in this map. If there is a mapping for a range which contains key, the value of this mapping is returned, otherwise nullptr.

Parameters
[in]keyKey to search for.
Returns
Pointer to value for the given key, or nullptr if no entry exists for the key.

◆ FindRange()

const V* FindRange ( key,
Range rangeOut 
) const

Finds the value associated with the given key in this map. If there is a mapping for a range which contains key, rangeOut is set to the range, and the value of the mapping is returned, otherwise nullptr.

Parameters
[in]keyKey to search for.
[out]rangeOutIf a mapping is found, rangeOut is set to its range.
Returns
Pointer to value for the given key, or nullptr if no entry exists for the key.

◆ Erase() [1/3]

ResultMem Erase ( rMinValue,
rMaxValue 
)

Removes any mappings of values within the range rMinValue ... rMaxValue. Existing overlapping mappings are truncated, split or removed as necessary.

Parameters
[in]rMinValueLower boundary of the range.
[in]rMaxValueUpper boundary of the range.
Returns
False if a memory allocation failed.

◆ Erase() [2/3]

ResultMem Erase ( key)

Removes a mapping for the given key, if any. Existing overlapping mappings are truncated, split or removed as necessary.

Parameters
[in]keyKey which shall be unmapped.
Returns
False if a memory allocation failed.

◆ Erase() [3/3]

ResultMem Erase ( const Range range)

Removes any mappings of values within the given range. Existing overlapping mappings are truncated, split or removed as necessary.

Parameters
[in]rangeRange for which all mappings shall be removed.
Returns
False if a memory allocation failed.

◆ ToString()

SFINAEHelper<String, K>::type ToString ( const FormatStatement fmt) const

◆ Begin() [1/2]

Iterator Begin ( )

Returns an iterator pointing to the first entry of this map. The iteration order corresponds to the order of the ranges.

Returns
Iterator for this map pointing to the first element.

◆ End() [1/2]

Iterator End ( )

Returns an iterator pointing just behind the last entry of this map. The iteration order corresponds to the order of the ranges.

Returns
Iterator for this map pointing behind the last element.

◆ Begin() [2/2]

ConstIterator Begin ( ) const

Returns an iterator pointing to the first entry of this map. The iteration order corresponds to the order of the ranges.

Returns
Iterator for this map pointing to the first element.

◆ End() [2/2]

ConstIterator End ( ) const

Returns an iterator pointing just behind the last entry of this map. The iteration order corresponds to the order of the ranges.

Returns
Iterator for this map pointing behind the last element.

◆ GetKeys() [1/2]

KeyIterator GetKeys ( )

Returns a foreach iterator to iterate over all keys (i.e., ranges) of this map. This will yield all ranges in ascending order.

Returns
Foreach iterator over all keys (i.e., ranges).

◆ GetKeys() [2/2]

ConstKeyIterator GetKeys ( ) const

Returns a foreach iterator to iterate over all keys (i.e., ranges) of this map. This will yield all ranges in ascending order.

Returns
Foreach iterator over all keys (i.e., ranges).

◆ GetValues() [1/2]

ValueIterator GetValues ( )

Returns a foreach iterator to iterate over all values of this map. This will yield all values in ascending order of the corresponding ranges.

Returns
Foreach iterator over all values.

◆ GetValues() [2/2]

ConstValueIterator GetValues ( ) const

Returns a foreach iterator to iterate over all values of this map. This will yield all values in ascending order of the corresponding ranges.

Returns
Foreach iterator over all values.

◆ GetMap()

const MapType& GetMap ( ) const

◆ GetHashCode()

UInt GetHashCode ( ) const

◆ operator==()

Bool operator== ( const RangeMap< K, V, MAP > &  other) const

◆ operator!=()

Bool operator!= ( const RangeMap< K, V, MAP > &  other) const

◆ GetUnderlyingMap()

const MapType& GetUnderlyingMap ( ) const

◆ DescribeIO()

static Result<void> DescribeIO ( const DataSerializeInterface stream)
static

◆ MAXON_DISALLOW_COPY_AND_ASSIGN()

MAXON_DISALLOW_COPY_AND_ASSIGN ( RangeMap< K, V, MAP )
private

Member Data Documentation

◆ _map

MapType _map
private

The underlying map which maps each start of a range to a pair consisting of the end of the range and the mapped value.