ROSE 0.11.145.147
IntervalMap.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_IntervalMap_H
9#define Sawyer_IntervalMap_H
10
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>
16
17namespace Sawyer {
18namespace Container {
19
21template<class IntervalMap>
27
28template<class IntervalMap>
34
39template<typename I, typename T>
41public:
42 typedef I Interval;
43 typedef T Value;
44
45#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
46private:
47 friend class boost::serialization::access;
48
49 template<class S>
50 void serialize(S&, const unsigned /*version*/) {
51 // nothing to serialize in this class
52 }
53#endif
54
55#ifdef SAWYER_HAVE_CEREAL
56private:
57 friend class cereal::access;
58
59 template<class Archive>
60 void CEREAL_SERIALIZE_FUNCTION_NAME(Archive&) {
61 // nothing to serialize in this class
62 }
63#endif
64
65public:
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;
74 }
75
82 Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
83 SAWYER_ARGUSED(interval);
84 SAWYER_ARGUSED(splitPoint);
85 return value;
86 }
87
92 void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
93 SAWYER_ARGUSED(interval);
94 SAWYER_ARGUSED(value);
95 SAWYER_ARGUSED(splitPoint);
96 }
97};
98
179template<typename I, typename T, class Policy = MergePolicy<I, T> >
181public:
182 typedef I Interval;
183 typedef T Value;
185private:
186 // Nodes of the underlying map are sorted by their last value so that we can use that map's lowerBound method to find the
187 // range to which a scalar key might belong. Since the intervals in the map are non-overlapping, sorting by greatest values
188 // has the same effect as sorting by least values.
189 struct IntervalCompare {
190 bool operator()(const Interval &a, const Interval &b) const {
191 return a.greatest() < b.greatest();
192 }
193 };
194
195 typedef std::pair<Interval, Interval> IntervalPair;
196
197public:
200
205 typedef typename Map::Node Node;
206
212
233private:
234 Map map_;
235 Policy policy_;
236 typename Interval::Value size_; // number of values (map_.size is number of intervals)
237
238#ifdef SAWYER_HAVE_BOOST_SERIALIZATION
239private:
240 friend class boost::serialization::access;
241
242 template<class S>
243 void serialize(S &s, const unsigned /*version*/) {
244 s & BOOST_SERIALIZATION_NVP(map_);
245 s & BOOST_SERIALIZATION_NVP(policy_);
246 s & BOOST_SERIALIZATION_NVP(size_);
247 }
248#endif
249
250#ifdef SAWYER_HAVE_CEREAL
251private:
252 friend class cereal::access;
253
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_));
259 }
260#endif
261
263 // Constructors
265public:
269 IntervalMap(): size_(0) {}
270
275 template<class Interval2, class T2, class Policy2>
277 typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
278 for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
279 insert(Interval(otherIter->key()), Value(otherIter->value()));
280 }
281
286 template<class Interval2, class T2, class Policy2>
288 clear();
289 typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
290 for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
291 insert(Interval(otherIter->key()), Value(otherIter->value()));
292 return *this;
293 }
294
296 // Searching
298public:
299
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(); }
315
322 boost::iterator_range<ValueIterator> values() { return map_.values(); }
323 boost::iterator_range<ConstValueIterator> values() const { return map_.values(); }
331 NodeIterator lowerBound(const typename Interval::Value &scalar) {
332 return map_.lowerBound(Interval(scalar));
333 }
334 ConstNodeIterator lowerBound(const typename Interval::Value &scalar) const {
335 return map_.lowerBound(Interval(scalar));
336 }
344 NodeIterator upperBound(const typename Interval::Value &scalar) {
345 NodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
346 while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
347 ++ub;
348 return ub;
349 }
350 ConstNodeIterator upperBound(const typename Interval::Value &scalar) const {
351 ConstNodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
352 while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
353 ++ub;
354 return ub;
355 }
363 NodeIterator findPrior(const typename Interval::Value &scalar) {
364 return findPriorImpl(*this, scalar);
365 }
366 ConstNodeIterator findPrior(const typename Interval::Value &scalar) const {
367 return findPriorImpl(*this, scalar);
368 }
369
370 template<class IMap>
372 findPriorImpl(IMap &imap, const typename Interval::Value &scalar) {
373 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
374 if (imap.isEmpty())
375 return imap.nodes().end();
376 Iter lb = imap.lowerBound(scalar);
377 if (lb!=imap.nodes().end() && lb->key().least() <= scalar)
378 return lb;
379 if (lb==imap.nodes().begin())
380 return imap.nodes().end();
381 return --lb;
382 }
390 NodeIterator find(const typename Interval::Value &scalar) {
391 return findImpl(*this, scalar);
392 }
393 ConstNodeIterator find(const typename Interval::Value &scalar) const {
394 return findImpl(*this, scalar);
395 }
396
397 template<class IMap>
399 findImpl(IMap &imap, const typename Interval::Value &scalar) {
400 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
401 Iter found = imap.lowerBound(scalar);
402 if (found==imap.nodes().end() || scalar < found->key().least())
403 return imap.nodes().end();
404 return found;
405 }
413 boost::iterator_range<NodeIterator> findAll(const Interval &interval) {
414 return findAllImpl(*this, interval);
415 }
416 boost::iterator_range<ConstNodeIterator> findAll(const Interval &interval) const {
417 return findAllImpl(*this, interval);
418 }
419
420 template<class IMap>
421 static boost::iterator_range<typename IntervalMapTraits<IMap>::NodeIterator>
422 findAllImpl(IMap &imap, const Interval &interval) {
423 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
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()));
430 }
439 return findFirstOverlapImpl(*this, interval);
440 }
442 return findFirstOverlapImpl(*this, interval);
443 }
444
445 template<class IMap>
447 findFirstOverlapImpl(IMap &imap, const Interval &interval) {
448 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
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();
453 }
465 template<typename T2, class Policy2>
466 std::pair<NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
469 return findFirstOverlapImpl(*this, thisIter, other, otherIter);
470 }
471 template<typename T2, class Policy2>
472 std::pair<ConstNodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
475 return findFirstOverlapImpl(*this, thisIter, other, otherIter);
476 }
477
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()) {
489 ++thisIter;
490 } else {
491 ++otherIter;
492 }
493 }
494 return std::make_pair(imap.nodes().end(), other.nodes().end());
495 }
510 return firstFitImpl(*this, size, start);
511 }
513 return firstFitImpl(*this, size, start);
514 }
515
516 template<class IMap>
518 firstFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
519 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
520 for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
521 if (isLarge(iter->key(), size))
522 return iter;
523 }
524 return imap.nodes().end();
525 }
526
542 return bestFitImpl(*this, size, start);
543 }
545 return bestFitImpl(*this, size, start);
546 }
547
548 template<class IMap>
550 bestFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
551 typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
552 Iter best = imap.nodes().end();
553 for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
554 if (iter->key().size()==size && size!=0)
555 return iter;
556 if (iter->key().size() > size && (best==imap.nodes().end() || iter->key().size() < best->key().size()))
557 best = iter;
558 }
559 return best;
560 }
569 Interval firstUnmapped(typename Interval::Value minAddr) const {
571 for (ConstNodeIterator iter=lowerBound(minAddr); iter!=nodes().end(); ++iter) {
572 if (minAddr < iter->key().least()) // minAddr is not mapped
573 return Interval::hull(minAddr, iter->key().least()-1);
574 if (iter->key().greatest() == all.greatest())
575 return Interval(); // no unmapped addresses, prevent potential overflow in next statement
576 minAddr = iter->key().greatest() + 1;
577 }
578 return Interval::hull(minAddr, all.greatest());
579 }
580
587 Interval lastUnmapped(typename Interval::Value maxAddr) const {
589 for (ConstNodeIterator iter=findPrior(maxAddr); iter!=nodes().begin(); --iter) {
590 if (maxAddr > iter->key().greatest()) // maxAddr is not mapped
591 return Interval::hull(iter->key().greatest()+1, maxAddr);
592 if (iter->key().least() == all.least())
593 return Interval(); // no unmapped address, prevent potential overflow in next statement
594 maxAddr = iter->key().least() - 1;
595 }
596 return Interval::hull(all.least(), maxAddr);
597 }
598
602 bool exists(const typename Interval::Value &size) const {
603 return find(size)!=nodes().end();
604 }
605
607 // Accessors
609public:
620 const Value& operator[](const typename Interval::Value &scalar) const {
621 ConstNodeIterator found = find(scalar);
622 if (found==nodes().end())
623 throw std::domain_error("key lookup failure; key is not in map domain");
624 return found->value();
625 }
626
627 const Value& get(const typename Interval::Value &scalar) const {
628 ConstNodeIterator found = find(scalar);
629 if (found==nodes().end())
630 throw std::domain_error("key lookup failure; key is not in map domain");
631 return found->value();
632 }
648 Optional<Value> getOptional(const typename Interval::Value &scalar) const {
649 ConstNodeIterator found = find(scalar);
650 return found == nodes().end() ? Optional<Value>() : Optional<Value>(found->value());
651 }
652
660 Value& getOrElse(const typename Interval::Value &scalar, Value &dflt) {
661 NodeIterator found = find(scalar);
662 return found == nodes().end() ? dflt : found->value();
663 }
664 const Value& getOrElse(const typename Interval::Value &scalar, const Value &dflt) const {
665 ConstNodeIterator found = find(scalar);
666 return found == nodes().end() ? dflt : found->value();
667 }
674 const Value& getOrDefault(const typename Interval::Value &scalar) const {
675 static const Value dflt;
676 ConstNodeIterator found = find(scalar);
677 return found==nodes().end() ? dflt : found->value();
678 }
679
681 // Capacity
683public:
684
688 bool isEmpty() const {
689 return map_.isEmpty();
690 }
691
696 size_t nIntervals() const {
697 return map_.size();
698 }
699
704 typename Interval::Value size() const {
705 return size_;
706 }
707
709 typename Interval::Value least() const {
710 ASSERT_forbid(isEmpty());
711 return map_.keys().begin()->least();
712 }
713
715 typename Interval::Value greatest() const {
716 ASSERT_forbid(isEmpty());
717 ConstIntervalIterator last = map_.keys().end(); --last;
718 return last->greatest();
719 }
720
726 ConstNodeIterator found = lowerBound(lowerLimit); // first node ending at or after lowerLimit
727 if (found==nodes().end())
728 return Nothing();
729 return std::max(lowerLimit, found->key().least());
730 }
731
737 ConstNodeIterator found = findPrior(upperLimit); // last node beginning at or before upperLimit
738 if (found==nodes().end())
739 return Nothing();
740 return std::min(upperLimit, found->key().greatest());
741 }
742
748 for (ConstNodeIterator iter = lowerBound(lowerLimit); iter!=nodes().end(); ++iter) {
749 if (lowerLimit < iter->key().least())
750 return lowerLimit;
751 lowerLimit = iter->key().greatest() + 1;
752 if (lowerLimit <= iter->key().least()) // sensitive to GCC optimization
753 return Nothing(); // overflow
754 }
755 return lowerLimit;
756 }
757
763 for (ConstNodeIterator iter = findPrior(upperLimit); iter!=nodes().end(); --iter) {
764 if (upperLimit > iter->key().greatest())
765 return upperLimit;
766 upperLimit = iter->key().least() - 1;
767 if (upperLimit >= iter->key().greatest()) // sensitive to GCC optimization
768 return Nothing(); // overflow
769 if (iter==nodes().begin())
770 break;
771 }
772 return upperLimit;
773 }
774
776 Interval hull() const {
777 return isEmpty() ? Interval() : Interval::hull(least(), greatest());
778 }
779
780
782 // Mutators
784public:
785
787 void clear() {
788 map_.clear();
789 size_ = 0;
790 }
791
793 void erase(const Interval &erasure) {
794 if (erasure.isEmpty())
795 return;
796
797 // Find what needs to be removed, and create a list of things to insert, but delay actual removing until after
798 // the loop since Map::erase doesn't return a next iterator.
799 Map insertions; // what needs to be inserted back in
800 NodeIterator eraseBegin = nodes().end();
801 NodeIterator iter;
802 for (iter=lowerBound(erasure.least()); iter!=nodes().end() && !erasure.isLeftOf(iter->key()); ++iter) {
803 Interval foundInterval = iter->key();
804 Value &v = iter->value();
805 if (erasure.contains(foundInterval)) {
806 // erase entire found interval
807 if (eraseBegin==nodes().end())
808 eraseBegin = iter;
809 size_ -= foundInterval.size();
810 } else if (erasure.least()>foundInterval.least() && erasure.greatest()<foundInterval.greatest()) {
811 // erase the middle of the node, leaving a left and a right portion
812 ASSERT_require(eraseBegin==nodes().end());
813 eraseBegin = iter;
814 IntervalPair rt = splitInterval(foundInterval, erasure.greatest()+1);
815 Value rightValue = policy_.split(foundInterval, v /*in,out*/, rt.second.least());
816 insertions.insert(rt.second, rightValue);
817 IntervalPair lt = splitInterval(rt.first, erasure.least());
818 policy_.truncate(rt.first, v /*in,out*/, erasure.least());
819 insertions.insert(lt.first, v);
820 size_ -= erasure.size();
821 } else if (erasure.least() > foundInterval.least()) {
822 // erase the right part of the node
823 ASSERT_require(eraseBegin==nodes().end());
824 eraseBegin = iter;
825 IntervalPair halves = splitInterval(foundInterval, erasure.least());
826 policy_.truncate(foundInterval, v /*in,out*/, erasure.least());
827 insertions.insert(halves.first, v);
828 size_ -= halves.second.size();
829 } else if (erasure.greatest() < foundInterval.greatest()) {
830 // erase the left part of the node
831 if (eraseBegin==nodes().end())
832 eraseBegin = iter;
833 IntervalPair halves = splitInterval(foundInterval, erasure.greatest()+1);
834 Value rightValue = policy_.split(foundInterval, v /*in,out*/, halves.second.least());
835 insertions.insert(halves.second, rightValue);
836 size_ -= halves.first.size();
837 }
838 }
839
840 // Do the actual erasing and insert the new stuff, which is easy now because we know it doesn't overlap with anything.
841 if (eraseBegin!=nodes().end())
842 map_.eraseAtMultiple(eraseBegin, iter);
843 map_.insertMultiple(insertions.nodes());
844 }
845
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)
854 erase(oi->key());
855 }
856
861 void insert(Interval key, Value value, bool makeHole=true) {
862 if (key.isEmpty())
863 return;
864 if (makeHole) {
865 erase(key);
866 } else {
867 NodeIterator found = lowerBound(key.least());
868 if (found!=nodes().end() && key.overlaps(found->key()))
869 return;
870 }
871
872 // Attempt to merge with a left-adjoining node
873 if (key.least() - 1 < key.least()) {
874 NodeIterator left = find(key.least() - 1);
875 if (left!=nodes().end() &&
876 left->key().greatest()+1==key.least() &&
877 policy_.merge(left->key(), left->value(), key, value)) {
878 key = Interval::hull(left->key().least(), key.greatest());
879 std::swap(value, left->value());
880 size_ -= left->key().size();
881 map_.eraseAt(left);
882 }
883 }
884
885 // Attempt to merge with a right-adjoining node
886 if (key.greatest() + 1 > key.greatest()) {
887 NodeIterator right = find(key.greatest() + 1);
888 if (right!=nodes().end() &&
889 key.greatest()+1==right->key().least() &&
890 policy_.merge(key, value, right->key(), right->value())) {
891 key = Interval::hull(key.least(), right->key().greatest());
892 size_ -= right->key().size();
893 map_.eraseAt(right);
894 }
895 }
896
897 map_.insert(key, value);
898 size_ += key.size();
899 }
900
905 template<typename T2, class Policy2>
906 void insertMultiple(const IntervalMap<Interval, T2, Policy2> &other, bool makeHole=true) {
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)
910 insert(oi->key(), Value(oi->value()), makeHole);
911 }
912
913// FIXME[Robb Matzke 2014-04-13]
914// // Intersection
915// void intersect(const Interval&);
916
917
918
920 // Predicates
922public:
923 bool overlaps(const Interval &interval) const {
924 return findFirstOverlap(interval) != nodes().end();
925 }
926 bool isOverlapping(const Interval &interval) const {
927 return overlaps(interval);
928 }
929
930 template<typename T2, class Policy2>
931 bool overlaps(const IntervalMap<Interval, T2, Policy2> &other) const {
932 return findFirstOverlap(nodes().begin(), other, other.nodes().begin()).first != nodes().end();
933 }
934 template<typename T2, class Policy2>
935 bool isOverlapping(const IntervalMap<Interval, T2, Policy2> &other) const {
936 return overlaps(other);
937 }
938
939 bool isDistinct(const Interval &interval) const {
940 return !overlaps(interval);
941 }
942
943 template<typename T2, class Policy2>
944 bool isDistinct(const IntervalMap<Interval, T2, Policy2> &other) const {
945 return !overlaps(other);
946 }
947
948 bool contains(Interval key) const {
949 if (key.isEmpty())
950 return true;
951 ConstNodeIterator found = find(key.least());
952 while (1) {
953 if (found==nodes().end())
954 return false;
955 if (key.least() < found->key().least())
956 return false;
957 ASSERT_require(key.overlaps(found->key()));
958 if (key.greatest() <= found->key().greatest())
959 return true;
960 key = splitInterval(key, found->key().greatest()+1).second;
961 ++found;
962 }
963 }
964
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()))
969 return false;
970 }
971 return true;
972 }
973
974
976 // Private support methods
978private:
979 static IntervalPair splitInterval(const Interval &interval, const typename Interval::Value &splitPoint) {
980 ASSERT_forbid(interval.isEmpty());
981 ASSERT_require(splitPoint > interval.least() && splitPoint <= interval.greatest());
982
983 Interval left = Interval::hull(interval.least(), splitPoint-1);
984 Interval right = Interval::hull(splitPoint, interval.greatest());
985 return IntervalPair(left, right);
986 }
987
988 // a more convenient way to check whether interval contains at least size items and still handle overflow
989 static bool isLarge(const Interval &interval, boost::uint64_t size) {
990 return !interval.isEmpty() && (interval.size()==0 || interval.size() >= size);
991 }
992};
993
994} // namespace
995} // namespace
996
997#endif
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.
Definition Interval.h:31
T greatest() const
Returns upper limit.
Definition Interval.h:224
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition Interval.h:162
T least() const
Returns lower limit.
Definition Interval.h:218
T Value
Types of values in the interval.
Definition Interval.h:34
static Interval whole()
Construct an interval that covers the entire domain.
Definition Interval.h:191
Bidirectional iterator over keys.
Definition Sawyer/Map.h:243
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:213
Bidirectional iterator over values.
Definition Sawyer/Map.h:296
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:187
Type for stored nodes.
Definition Sawyer/Map.h:107
const Key & key() const
Key part of key/value node.
Definition Sawyer/Map.h:116
Value & value()
Value part of key/value node.
Definition Sawyer/Map.h:123
Bidirectional iterator over values.
Definition Sawyer/Map.h:271
Container associating values with keys.
Definition Sawyer/Map.h:72
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition Sawyer/Map.h:523
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition Sawyer/Map.h:771
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition Sawyer/Map.h:414
size_t size() const
Number of nodes, keys, or values in this container.
Definition Sawyer/Map.h:438
bool isEmpty() const
Determines whether this container is empty.
Definition Sawyer/Map.h:431
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition Sawyer/Map.h:506
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition Sawyer/Map.h:387
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition Sawyer/Map.h:797
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition Sawyer/Map.h:400
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition Sawyer/Map.h:646
Map & clear()
Remove all nodes.
Definition Sawyer/Map.h:732
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition Sawyer/Map.h:682
Policy indicating how values are merged and split.
Definition IntervalMap.h:40
Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Split one value into two values.
Definition IntervalMap.h:82
bool merge(const Interval &leftInterval, Value &leftValue, const Interval &rightInterval, Value &rightValue)
Merge two values if possible.
Definition IntervalMap.h:70
void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Discard the right part of a value.
Definition IntervalMap.h:92
Represents no value.
Definition Optional.h:36
Holds a value or nothing.
Definition Optional.h:56
Sawyer support library.
IntervalMap::ValueIterator ValueIterator
Value iterator.
Definition IntervalMap.h:24
IntervalMap::NodeIterator NodeIterator
Node iterator.
Definition IntervalMap.h:23
IntervalMap::Value & ValueReference
Reference to value.
Definition IntervalMap.h:25