#include <slang/util/IntervalMap.h>
template<typename TKey, typename TValue>
slang::IntervalMap class

A data structure that maps from intervals (closed ranges) to values.

The first N intervals will be stored inline with the object itself, so no allocations will occur until that space is exhausted. Once it is, the map switches to a B+ tree representation with very small overhead for small key and value objects.

Overlapping and duplicate intervals are allowed.

New branches of the B+ tree are allocated via a provided PoolAllocator instance. This allocator is not stored in the map itself, but instead provided on each insert call. This trades off convenience to save space in the map object.

The memory reserved by the map from the PoolAllocator is not returned in its destructor (IntervalMap has a trivial destructor). This is so it can be used in types that themselves require a trivial destructor. The tradeoff is that the reserved memory is not returnable to the pool once the map is destroyed, and you must dispose of the PoolAllocator itself to free up the memory.

Constructors, destructors, conversion operators

IntervalMap()
Default constructor.
~IntervalMap() defaulted
Destructor.
IntervalMap(const IntervalMap&) deleted
Not copyable.
IntervalMap(IntervalMap&& other) noexcept
Move constructor.

Public functions

auto operator=(const IntervalMap&) -> IntervalMap& deleted
Not copyable.
auto operator=(IntervalMap&& other) -> IntervalMap& noexcept
Move assignment operator.
auto empty() const -> bool
Indicates whether the map is empty.
void clear(allocator_type& alloc)
Clears the map and returns all allocated memory, if any, to the provided allocator.
void insert(TKey left, TKey right, const TValue& value, allocator_type& alloc)
Inserts a new interval and value pair into the map.
void insert(const std::pair<TKey, TKey>& key, const TValue& value, allocator_type& alloc)
Inserts a new interval and value pair into the map.
void unionWith(TKey left, TKey right, const TValue& value, allocator_type& alloc)
Inserts a new interval and value pair into the map, combining it with any intervals that already exist in the map that are adjacent to or overlap with the new one.
void unionWith(const std::pair<TKey, TKey>& key, const TValue& value, allocator_type& alloc)
Inserts a new interval and value pair into the map, combining it with any intervals that already exist in the map that are adjacent to or overlap with the new one and share the same value.
auto begin() -> iterator
Returns an iterator at the start of the map.
auto begin() const -> const_iterator
Returns an iterator at the start of the map.
auto end() -> iterator
Returns an iterator at the end of the map.
auto end() const -> const_iterator
Returns an iterator at the end of the map.
auto find(TKey left, TKey right) const -> overlap_iterator
Finds all intervals that overlap the given interval.
auto find(const std::pair<TKey, TKey>& key) const -> overlap_iterator
Finds all intervals that overlap the given interval.
auto getBounds() const -> std::pair<TKey, TKey>
Gets an interval encompassing the entire set of items in the map.
void verify() const
Verifies the internal state of the map, ASSERTing if it's not valid.

Function documentation

template<typename TKey, typename TValue>
void slang::IntervalMap<TKey, TValue>::insert(TKey left, TKey right, const TValue& value, allocator_type& alloc)

Inserts a new interval and value pair into the map.

Insertion complexity is O(log n)

template<typename TKey, typename TValue>
void slang::IntervalMap<TKey, TValue>::insert(const std::pair<TKey, TKey>& key, const TValue& value, allocator_type& alloc)

Inserts a new interval and value pair into the map.

Insertion complexity is O(log n)

template<typename TKey, typename TValue>
void slang::IntervalMap<TKey, TValue>::unionWith(TKey left, TKey right, const TValue& value, allocator_type& alloc)

Inserts a new interval and value pair into the map, combining it with any intervals that already exist in the map that are adjacent to or overlap with the new one.

Note that it in the case of combining intervals, the old value associated with the interval will be kept and the new one ignored. It is assumed that if you are using this method you don't care much about the values.

Complexity is O(log n + m) where n is the number of intervals in the map and m is the number of intervals found to union with.

template<typename TKey, typename TValue>
void slang::IntervalMap<TKey, TValue>::unionWith(const std::pair<TKey, TKey>& key, const TValue& value, allocator_type& alloc)

Inserts a new interval and value pair into the map, combining it with any intervals that already exist in the map that are adjacent to or overlap with the new one and share the same value.

Note that it in the case of combining intervals, the old value associated with the interval will be kept and the new one ignored. It is assumed that if you are using this method you don't care much about the values.

Complexity is O(log n + m) where n is the number of intervals in the map and m is the number of intervals found to union with.

template<typename TKey, typename TValue>
overlap_iterator slang::IntervalMap<TKey, TValue>::find(TKey left, TKey right) const

Finds all intervals that overlap the given interval.

The returned iterator can be used to traverse all of the overlapping intervals.

The complexity is O(log n + m) where n is the number of intervals in the map and m is the number of overlapping intervals found.

template<typename TKey, typename TValue>
overlap_iterator slang::IntervalMap<TKey, TValue>::find(const std::pair<TKey, TKey>& key) const

Finds all intervals that overlap the given interval.

The returned iterator can be used to traverse all of the overlapping intervals.

The complexity is O(log n + m) where n is the number of intervals in the map and m is the number of overlapping intervals found.

template<typename TKey, typename TValue>
void slang::IntervalMap<TKey, TValue>::verify() const

Verifies the internal state of the map, ASSERTing if it's not valid.

This is only intended for use with unit tests.