Interval library for C++
Interval Library by Ross Smith
#include "rs-interval/interval-map.hpp"
namespace RS::Interval;
This header defines a class representing a map from a set of disjoint intervals to values of some other type.
template <IntervalCompatible K, std::regular T> class IntervalMap;
A map from a set of intervals over K to values of T. The IntervalMap
object also contains a default value of T that will be returned when a key
is not a member of any of the intervals in the map.
This is an ordered map analogous to std::map. The intervals in the map are
automatically updated when intervals are inserted or erased: an inserted
interval will erase any parts of existing intervals that it covers, or will
be merged with them if they have the same mapped value; an interval will be
removed, reduced in size, or split into two if part of it is erased.
using IntervalMap::key_type = K;
using IntervalMap::interval_type = Interval<K>;
using IntervalMap::mapped_type = T;
using IntervalMap::value_type = std::pair<const Interval<K>, T>;
Type aliases.
class IntervalMap::iterator;
A bidirectional const iterator over the intervals that make up the set,
dereferencing to an Interval<T>.
static constexpr Category IntervalMap::category = interval_category<K>;
The underlying key type’s interval category.
IntervalMap::IntervalMap();
explicit IntervalMap::IntervalMap(const T& defval);
IntervalMap::IntervalMap(std::initializer_list<value_type> list);
IntervalMap::IntervalMap(const IntervalMap& map);
IntervalMap::IntervalMap(IntervalMap&& map) noexcept;
IntervalMap::~IntervalMap() noexcept;
IntervalMap& IntervalMap::operator=(const IntervalMap& map);
IntervalMap& IntervalMap::operator=(IntervalMap&& map) noexcept;
An optional default value can be provided; if none is provided, a default
constructed value of T is used. When a map is constructed from a list of
(interval,value) pairs, the intervals are ordered lexicographically, and
adjacent intervals are merged when they touch or overlap and have the same
mapped value. When two intervals overlap but do not have the same mapped
value, later entries in the initializer list will overwrite earlier ones.
std::strong_ordering
operator<=>(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator==(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator!=(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator<(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator>(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator<=(const IntervalMap& a, const IntervalMap& b) noexcept;
bool operator>=(const IntervalMap& a, const IntervalMap& b) noexcept;
Lexicographical comparison operators. These call T’s comparison operators.
The default value does not participate in comparisons.
const T& IntervalMap::operator[](const K& key) const;
Returns the mapped value corresponding to the interval containing the given key, or the default value if no interval contains the key.
IntervalMap::iterator IntervalMap::begin() const noexcept;
IntervalMap::iterator IntervalMap::end() const noexcept;
Iterators over the map’s list of (interval,value) pairs.
IntervalMap::iterator IntervalMap::find(const K& key) const;
Returns an iterator pointing to the interval containing the given key, or
end() if no such interval exists.
IntervalMap::iterator IntervalMap::lower_bound(const K& key) const;
IntervalMap::iterator IntervalMap::upper_bound(const K& key) const;
If the key is contained in one of the intervals in the map, lower_bound()
returns an iterator pointing to that interval, and upper_bound() returns the
next iterator. If not, both functions return the iterator pointing to the
first interval after the given key, or end() if no such interval exists.
bool IntervalMap::contains(const K& key) const;
True if one of the intervals in the map contains the key.
const T& IntervalMap::default_value() const noexcept;
Returns the default value.
bool IntervalMap::empty() const noexcept;
True if the map is empty.
std::size_t IntervalMap::size() const noexcept;
Returns the number of intervals in the map.
std::size_t IntervalMap::hash() const noexcept;
struct std::hash<IntervalMap>;
Hash function for an interval map.
void IntervalMap::default_value(const T& defval);
Changes the default value.
void IntervalMap::clear() noexcept;
void IntervalMap::reset(const T& defval = T());
These clear all (interval,value) pairs from the map. The clear() function
does not change the default value, while reset() also changes it.
void IntervalMap::insert(const Interval<K>& in, const T& t);
void IntervalMap::insert(const value_type& v);
Adds a new (interval,value) pair to the map. Intervals in the map that
overlap this interval will be modified or removed as necessary.
void IntervalMap::erase(const Interval<K>& in);
Removes an interval from the map. This does not have to exactly match an interval already in the set. Intervals in the map that overlap this interval will be modified or removed as necessary. This will have no effect if this interval does not overlap any existing interval in the map.
void IntervalMap::swap(IntervalMap& map) noexcept;
void swap(IntervalMap& a, IntervalMap& b) noexcept;
Swap two interval maps.
template <IntervalCompatible K, std::regular T>
requires (std::formattable<K, char> && std::formattable<T, char>)
struct std::formatter<IntervalMap<K, T>>;
Standard formatter for interval maps. This does not implement any format
specifiers; it will always use the default format for the key and value
types. The format is "{A:X,B:Y,C:Z,...}", where A, B, C, etc are
intervals or values of K, and X, Y, Z, etc are values of T.