8#ifndef Sawyer_IntervalMap_H
9#define Sawyer_IntervalMap_H
11#include <boost/cstdint.hpp>
12#include <Sawyer/Assert.h>
13#include <Sawyer/Map.h>
14#include <Sawyer/Optional.h>
15#include <Sawyer/Sawyer.h>
21template<
class IntervalMap>
28template<
class IntervalMap>
39template<
typename I,
typename T>
45#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
47 friend class boost::serialization::access;
50 void serialize(S&,
const unsigned ) {
55#ifdef SAWYER_HAVE_CEREAL
57 friend class cereal::access;
59 template<
class Archive>
60 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive&) {
70 bool merge(
const Interval &leftInterval, Value &leftValue,
const Interval &rightInterval, Value &rightValue) {
71 SAWYER_ARGUSED(leftInterval);
72 SAWYER_ARGUSED(rightInterval);
73 return leftValue == rightValue;
83 SAWYER_ARGUSED(interval);
84 SAWYER_ARGUSED(splitPoint);
93 SAWYER_ARGUSED(interval);
94 SAWYER_ARGUSED(value);
95 SAWYER_ARGUSED(splitPoint);
179template<
typename I,
typename T,
class Policy = MergePolicy<I, T> >
189 struct IntervalCompare {
191 return a.greatest() < b.greatest();
195 typedef std::pair<Interval, Interval> IntervalPair;
238#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
240 friend class boost::serialization::access;
243 void serialize(S &s,
const unsigned ) {
244 s & BOOST_SERIALIZATION_NVP(map_);
245 s & BOOST_SERIALIZATION_NVP(policy_);
246 s & BOOST_SERIALIZATION_NVP(size_);
250#ifdef SAWYER_HAVE_CEREAL
252 friend class cereal::access;
254 template<
class Archive>
255 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive &archive) {
256 archive(CEREAL_NVP(map_));
257 archive(CEREAL_NVP(policy_));
258 archive(CEREAL_NVP(size_));
275 template<
class Interval2,
class T2,
class Policy2>
278 for (OtherIterator otherIter=other.
nodes().begin(); other!=other.
nodes().end(); ++other)
286 template<
class Interval2,
class T2,
class Policy2>
290 for (OtherIterator otherIter=other.
nodes().begin(); other!=other.
nodes().end(); ++other)
306 boost::iterator_range<NodeIterator>
nodes() {
return map_.
nodes(); }
307 boost::iterator_range<ConstNodeIterator>
nodes()
const {
return map_.
nodes(); }
314 boost::iterator_range<ConstIntervalIterator>
intervals()
const {
return map_.
keys(); }
322 boost::iterator_range<ValueIterator>
values() {
return map_.
values(); }
323 boost::iterator_range<ConstValueIterator>
values()
const {
return map_.
values(); }
346 while (ub!=map_.
nodes().end() && ub->
key().least() <= scalar)
352 while (ub!=map_.
nodes().end() && ub->
key().least() <= scalar)
375 return imap.nodes().end();
376 Iter lb = imap.lowerBound(scalar);
377 if (lb!=imap.nodes().end() && lb->key().least() <= scalar)
379 if (lb==imap.nodes().begin())
380 return imap.nodes().end();
401 Iter found = imap.lowerBound(scalar);
402 if (found==imap.nodes().end() || scalar < found->key().
least())
403 return imap.nodes().end();
421 static boost::iterator_range<typename IntervalMapTraits<IMap>::NodeIterator>
424 if (interval.isEmpty())
425 return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
426 Iter begin = imap.lowerBound(interval.least());
427 if (begin==imap.nodes().end() || begin->key().least() > interval.greatest())
428 return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
429 return boost::iterator_range<Iter>(begin, imap.upperBound(interval.greatest()));
449 if (interval.isEmpty())
450 return imap.nodes().end();
451 Iter lb = imap.lowerBound(interval.least());
452 return lb!=imap.nodes().end() && interval.overlaps(lb->key()) ? lb : imap.nodes().end();
465 template<
typename T2,
class Policy2>
466 std::pair<NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
471 template<
typename T2,
class Policy2>
472 std::pair<ConstNodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
478 template<
class IMap,
typename T2,
class Policy2>
479 static std::pair<typename IntervalMapTraits<IMap>::NodeIterator,
485 while (thisIter!=imap.nodes().end() && otherIter!=other.
nodes().end()) {
486 if (thisIter->
key().overlaps(otherIter->
key()))
487 return std::make_pair(thisIter, otherIter);
488 if (thisIter->
key().greatest() < otherIter->
key().greatest()) {
494 return std::make_pair(imap.nodes().end(), other.
nodes().end());
520 for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
521 if (isLarge(iter->key(),
size))
524 return imap.nodes().end();
552 Iter best = imap.nodes().end();
553 for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
554 if (iter->key().size()==
size &&
size!=0)
556 if (iter->key().size() >
size && (best==imap.nodes().end() || iter->key().size() < best->key().size()))
572 if (minAddr < iter->key().least())
574 if (iter->key().greatest() == all.greatest())
576 minAddr = iter->key().
greatest() + 1;
590 if (maxAddr > iter->key().greatest())
592 if (iter->key().least() == all.least())
594 maxAddr = iter->key().
least() - 1;
622 if (found==
nodes().end())
623 throw std::domain_error(
"key lookup failure; key is not in map domain");
624 return found->
value();
629 if (found==
nodes().end())
630 throw std::domain_error(
"key lookup failure; key is not in map domain");
631 return found->
value();
662 return found ==
nodes().end() ? dflt : found->
value();
666 return found ==
nodes().end() ? dflt : found->
value();
675 static const Value dflt;
677 return found==
nodes().end() ? dflt : found->
value();
711 return map_.
keys().begin()->least();
718 return last->greatest();
727 if (found==
nodes().end())
729 return std::max(lowerLimit, found->
key().least());
738 if (found==
nodes().end())
740 return std::min(upperLimit, found->
key().greatest());
749 if (lowerLimit < iter->key().least())
751 lowerLimit = iter->key().greatest() + 1;
752 if (lowerLimit <= iter->key().least())
764 if (upperLimit > iter->key().greatest())
766 upperLimit = iter->key().least() - 1;
767 if (upperLimit >= iter->key().greatest())
769 if (iter==
nodes().begin())
794 if (erasure.isEmpty())
802 for (iter=
lowerBound(erasure.least()); iter!=
nodes().end() && !erasure.isLeftOf(iter->
key()); ++iter) {
805 if (erasure.contains(foundInterval)) {
807 if (eraseBegin==
nodes().end())
809 size_ -= foundInterval.size();
810 }
else if (erasure.least()>foundInterval.least() && erasure.greatest()<foundInterval.greatest()) {
812 ASSERT_require(eraseBegin==
nodes().end());
814 IntervalPair rt = splitInterval(foundInterval, erasure.greatest()+1);
815 Value rightValue = policy_.split(foundInterval, v , rt.second.least());
816 insertions.
insert(rt.second, rightValue);
817 IntervalPair lt = splitInterval(rt.first, erasure.least());
818 policy_.truncate(rt.first, v , erasure.least());
819 insertions.
insert(lt.first, v);
820 size_ -= erasure.
size();
821 }
else if (erasure.least() > foundInterval.least()) {
823 ASSERT_require(eraseBegin==
nodes().end());
825 IntervalPair halves = splitInterval(foundInterval, erasure.least());
826 policy_.truncate(foundInterval, v , erasure.least());
827 insertions.
insert(halves.first, v);
828 size_ -= halves.second.
size();
829 }
else if (erasure.greatest() < foundInterval.greatest()) {
831 if (eraseBegin==
nodes().end())
833 IntervalPair halves = splitInterval(foundInterval, erasure.greatest()+1);
834 Value rightValue = policy_.split(foundInterval, v , halves.second.least());
835 insertions.
insert(halves.second, rightValue);
836 size_ -= halves.first.
size();
841 if (eraseBegin!=
nodes().end())
849 template<
typename T2,
class Policy2>
851 ASSERT_forbid2((
const void*)&other == (
const void*)
this,
"use clear() instead");
853 for (OtherIter oi=other.
nodes().begin(); oi!=other.
nodes().end(); ++oi)
868 if (found!=
nodes().end() && key.overlaps(found->
key()))
873 if (key.least() - 1 < key.least()) {
875 if (left!=
nodes().end() &&
876 left->
key().greatest()+1==key.least() &&
877 policy_.merge(left->
key(), left->
value(), key, value)) {
879 std::swap(value, left->
value());
880 size_ -= left->
key().size();
886 if (key.greatest() + 1 > key.greatest()) {
888 if (right!=
nodes().end() &&
889 key.greatest()+1==right->
key().least() &&
890 policy_.merge(key, value, right->
key(), right->
value())) {
892 size_ -= right->
key().size();
905 template<
typename T2,
class Policy2>
907 ASSERT_forbid2((
const void*)&other == (
const void*)
this,
"cannot insert a container into itself");
909 for (OtherIter oi=other.
nodes().begin(); oi!=other.
nodes().end(); ++oi)
923 bool overlaps(
const Interval &interval)
const {
926 bool isOverlapping(
const Interval &interval)
const {
927 return overlaps(interval);
930 template<
typename T2,
class Policy2>
931 bool overlaps(
const IntervalMap<Interval, T2, Policy2> &other)
const {
934 template<
typename T2,
class Policy2>
935 bool isOverlapping(
const IntervalMap<Interval, T2, Policy2> &other)
const {
936 return overlaps(other);
939 bool isDistinct(
const Interval &interval)
const {
940 return !overlaps(interval);
943 template<
typename T2,
class Policy2>
944 bool isDistinct(
const IntervalMap<Interval, T2, Policy2> &other)
const {
945 return !overlaps(other);
953 if (found==
nodes().end())
955 if (key.least() < found->key().least())
957 ASSERT_require(key.overlaps(found->key()));
958 if (key.greatest() <= found->key().greatest())
960 key = splitInterval(key, found->key().greatest()+1).second;
965 template<
typename T2,
class Policy2>
966 bool contains(
const IntervalMap<Interval, T2, Policy2> &other)
const {
967 for (
ConstNodeIterator iter=other.nodes().begin(); iter!=other.nodes().end(); ++iter) {
968 if (!contains(iter->key()))
980 ASSERT_forbid(interval.isEmpty());
981 ASSERT_require(splitPoint > interval.least() && splitPoint <= interval.greatest());
985 return IntervalPair(left, right);
989 static bool isLarge(
const Interval &interval, boost::uint64_t
size) {
990 return !interval.isEmpty() && (interval.size()==0 || interval.size() >=
size);
An associative container whose keys are non-overlapping intervals.
size_t nIntervals() const
Number of nodes in the container.
Map::ConstValueIterator ConstValueIterator
Value iterator.
const Value & getOrElse(const typename Interval::Value &scalar, const Value &dflt) const
Lookup and return a value or something else.
IntervalMap()
Default constructor.
const Value & get(const typename Interval::Value &scalar) const
Returns a reference to an existing value.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
ConstNodeIterator upperBound(const typename Interval::Value &scalar) const
Find the first node whose interval begins above the specified scalar key.
Interval firstUnmapped(typename Interval::Value minAddr) const
Find the first unmapped region.
static IntervalMapTraits< IMap >::NodeIterator findPriorImpl(IMap &imap, const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
void clear()
Empties the container.
static IntervalMapTraits< IMap >::NodeIterator bestFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits< IMap >::NodeIterator start)
Find the best fit node at or after a starting point.
ConstNodeIterator firstFit(const typename Interval::Value &size, ConstNodeIterator start) const
Find the first fit node at or after a starting point.
Interval::Value greatest() const
Returns the maximum scalar key.
void eraseMultiple(const IntervalMap< Interval, T2, Policy2 > &other)
Erase intervals specified in another IntervalMap.
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for traversing nodes.
Optional< typename Interval::Value > least(typename Interval::Value lowerLimit) const
Returns the limited-minimum scalar key.
Interval hull() const
Returns the range of values in this map.
ConstNodeIterator findFirstOverlap(const Interval &interval) const
Find first interval that overlaps with the specified interval.
ConstNodeIterator lowerBound(const typename Interval::Value &scalar) const
Find the first node whose interval ends at or above the specified scalar key.
Interval lastUnmapped(typename Interval::Value maxAddr) const
Find the last unmapped region.
static IntervalMapTraits< IMap >::NodeIterator findFirstOverlapImpl(IMap &imap, const Interval &interval)
Find first interval that overlaps with the specified interval.
NodeIterator upperBound(const typename Interval::Value &scalar)
Find the first node whose interval begins above the specified scalar key.
IntervalMap(const IntervalMap< Interval2, T2, Policy2 > &other)
Copy constructor.
Optional< typename Interval::Value > greatest(typename Interval::Value upperLimit) const
Returns the limited-maximum scalar key.
Map::NodeIterator NodeIterator
Node iterator.
ConstNodeIterator find(const typename Interval::Value &scalar) const
Find the node containing the specified scalar key.
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Interval::Value least() const
Returns the minimum scalar key.
NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start)
Find the first fit node at or after a starting point.
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
std::pair< NodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator > findFirstOverlap(typename IntervalMap::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter)
Find first interval that overlaps with any in another container.
ConstNodeIterator bestFit(const typename Interval::Value &size, ConstNodeIterator start) const
Find the best fit node at or after a starting point.
void erase(const Interval &erasure)
Erase the specified interval.
static std::pair< typename IntervalMapTraits< IMap >::NodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator > findFirstOverlapImpl(IMap &imap, typename IntervalMapTraits< IMap >::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter)
Find first interval that overlaps with any in another container.
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
bool exists(const typename Interval::Value &size) const
Returns true if element exists.
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIterator > findAllImpl(IMap &imap, const Interval &interval)
Finds all nodes overlapping the specified interval.
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterators for traversing keys.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
NodeIterator findPrior(const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
ConstNodeIterator findPrior(const typename Interval::Value &scalar) const
Find the last node whose interval starts at or below the specified scalar key.
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Optional< typename Interval::Value > greatestUnmapped(typename Interval::Value upperLimit) const
Returns the limited-maximum unmapped scalar key.
std::pair< ConstNodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator > findFirstOverlap(typename IntervalMap::ConstNodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter) const
Find first interval that overlaps with any in another container.
bool isEmpty() const
Determine if the container is empty.
static IntervalMapTraits< IMap >::NodeIterator findImpl(IMap &imap, const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
boost::iterator_range< ConstValueIterator > values() const
Iterators for traversing values.
Optional< Value > getOptional(const typename Interval::Value &scalar) const
Lookup and return a value or nothing.
Map::ConstNodeIterator ConstNodeIterator
Node iterator.
Map::Node Node
Storage node.
const Value & operator[](const typename Interval::Value &scalar) const
Returns a reference to an existing value.
const Value & getOrDefault(const typename Interval::Value &scalar) const
Lookup and return a value or a default.
Interval::Value size() const
Returns the number of values represented by this container.
boost::iterator_range< ConstNodeIterator > findAll(const Interval &interval) const
Finds all nodes overlapping the specified interval.
Container::Map< Interval, Value, IntervalCompare > Map
Type of the underlying map.
Map::ValueIterator ValueIterator
Value iterator.
Map::ConstKeyIterator ConstIntervalIterator
Interval iterator.
static IntervalMapTraits< IMap >::NodeIterator firstFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits< IMap >::NodeIterator start)
Find the first fit node at or after a starting point.
void insertMultiple(const IntervalMap< Interval, T2, Policy2 > &other, bool makeHole=true)
Insert values from another container.
IntervalMap & operator=(const IntervalMap< Interval2, T2, Policy2 > &other)
Assignment operator.
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start)
Find the best fit node at or after a starting point.
Value & getOrElse(const typename Interval::Value &scalar, Value &dflt)
Lookup and return a value or something else.
Range of values delimited by endpoints.
T greatest() const
Returns upper limit.
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
T least() const
Returns lower limit.
T Value
Types of values in the interval.
static Interval whole()
Construct an interval that covers the entire domain.
Bidirectional iterator over keys.
Bidirectional iterator over key/value nodes.
Bidirectional iterator over values.
Bidirectional iterator over key/value nodes.
const Key & key() const
Key part of key/value node.
Value & value()
Value part of key/value node.
Bidirectional iterator over values.
Container associating values with keys.
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
boost::iterator_range< ValueIterator > values()
Iterators for container values.
size_t size() const
Number of nodes, keys, or values in this container.
bool isEmpty() const
Determines whether this container is empty.
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Map & clear()
Remove all nodes.
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Policy indicating how values are merged and split.
Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Split one value into two values.
bool merge(const Interval &leftInterval, Value &leftValue, const Interval &rightInterval, Value &rightValue)
Merge two values if possible.
void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Discard the right part of a value.
Holds a value or nothing.
IntervalMap::ValueIterator ValueIterator
Value iterator.
IntervalMap::NodeIterator NodeIterator
Node iterator.
IntervalMap::Value & ValueReference
Reference to value.