#include <rangemap.h>
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.
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.
K | Type of keys. This must be an integral type. |
V | Type of values. |
MAP | A 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, Tuple< K, V > > |
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 > |
Static Public Member Functions | |
static Result< void > | DescribeIO (const DataSerializeInterface &stream) |
Private Member Functions | |
MAXON_DISALLOW_COPY_AND_ASSIGN (RangeMap) | |
Private Attributes | |
MapType | _map |
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> |
RangeMap | ( | ) |
MAXON_OPERATOR_MOVE_ASSIGNMENT | ( | RangeMap< K, V, MAP > | ) |
Makes this map a copy of src.
[in] | src | Source from which the entries are taken. |
void Flush | ( | ) |
Flushes the map. This removes all entries. Depending on the underlying map, memory may still be held for later re-use.
void Reset | ( | ) |
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.
Int GetCount | ( | ) | 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.
Bool IsEmpty | ( | ) | const |
Checks if the RangeMap is empty. This is the same as GetCount() == 0
Bool IsPopulated | ( | ) | const |
Checks if the RangeMap is populated. This is the same as GetCount() != 0
Int GetMemorySize | ( | ) | const |
Calculates the memory usage for this map. Keys and Values must have a public member GetMemorySize that return the element size.
ResultMem Insert | ( | K | rMinValue, |
K | 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.
[in] | rMinValue | Lower boundary of the range. |
[in] | rMaxValue | Upper boundary of the range. |
[in] | value | Value to which the range shall be mapped. |
ResultMem Insert | ( | K | 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.
[in] | key | A single key which shall be mapped. |
[in] | value | Value to which the range shall be mapped. |
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.
[in] | range | Range which shall be mapped. |
[in] | value | Value to which the range shall be mapped. |
const V* FindValue | ( | K | 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.
[in] | key | Key to search for. |
const V* FindRange | ( | K | 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.
[in] | key | Key to search for. |
[out] | rangeOut | If a mapping is found, rangeOut is set to its range. |
ResultMem Erase | ( | K | rMinValue, |
K | rMaxValue | ||
) |
Removes any mappings of values within the range rMinValue
... rMaxValue
. Existing overlapping mappings are truncated, split or removed as necessary.
[in] | rMinValue | Lower boundary of the range. |
[in] | rMaxValue | Upper boundary of the range. |
ResultMem Erase | ( | K | key | ) |
Removes a mapping for the given key
, if any. Existing overlapping mappings are truncated, split or removed as necessary.
[in] | key | Key which shall be unmapped. |
Removes any mappings of values within the given range
. Existing overlapping mappings are truncated, split or removed as necessary.
[in] | range | Range for which all mappings shall be removed. |
SFINAEHelper<String, K>::type ToString | ( | const FormatStatement * | fmt = nullptr | ) | const |
Iterator Begin | ( | ) |
Returns an iterator pointing to the first entry of this map. The iteration order corresponds to the order of the ranges.
Iterator End | ( | ) |
Returns an iterator pointing just behind the last entry of this map. The iteration order corresponds to the order of the ranges.
ConstIterator Begin | ( | ) | const |
Returns an iterator pointing to the first entry of this map. The iteration order corresponds to the order of the ranges.
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.
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.
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.
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.
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.
const MapType& GetMap | ( | ) | const |
HashInt GetHashCode | ( | ) | const |
UniqueHash GetUniqueHashCode | ( | ) | const |
const MapType& GetUnderlyingMap | ( | ) | const |
|
static |
|
private |
|
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.