ROSE  0.9.9.109
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://github.com/matzke1/sawyer.
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 
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 
20 namespace Sawyer {
21 namespace Container {
22 
24 template<class IntervalMap>
28  typedef typename IntervalMap::Value &ValueReference;
29 };
30 
31 template<class IntervalMap>
35  typedef typename IntervalMap::Value const &ValueReference;
36 };
37 
42 template<typename I, typename T>
43 class MergePolicy {
44 public:
45  typedef I Interval;
46  typedef T Value;
47 
48 private:
49  friend class boost::serialization::access;
50 
51  template<class S>
52  void serialize(S&, const unsigned /*version*/) {
53  // nothing to serialize in this class
54  }
55 
56 public:
61  bool merge(const Interval &leftInterval, Value &leftValue, const Interval &rightInterval, Value &rightValue) {
62  SAWYER_ARGUSED(leftInterval);
63  SAWYER_ARGUSED(rightInterval);
64  return leftValue == rightValue;
65  }
66 
73  Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
74  SAWYER_ARGUSED(interval);
75  SAWYER_ARGUSED(splitPoint);
76  return value;
77  }
78 
83  void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint) {
84  SAWYER_ARGUSED(interval);
85  SAWYER_ARGUSED(value);
86  SAWYER_ARGUSED(splitPoint);
87  }
88 };
89 
170 template<typename I, typename T, class Policy = MergePolicy<I, T> >
171 class IntervalMap {
172 public:
173  typedef I Interval;
174  typedef T Value;
176 private:
177  // Nodes of the underlying map are sorted by their last value so that we can use that map's lowerBound method to find the
178  // range to which a scalar key might belong. Since the intervals in the map are non-overlapping, sorting by greatest values
179  // has the same effect as sorting by least values.
180  struct IntervalCompare {
181  bool operator()(const Interval &a, const Interval &b) const {
182  return a.greatest() < b.greatest();
183  }
184  };
185 
186  typedef std::pair<Interval, Interval> IntervalPair;
187 
188 public:
191 
196  typedef typename Map::Node Node;
197 
203 
220  typedef typename Map::NodeIterator NodeIterator;
224 private:
225  Map map_;
226  Policy policy_;
227  typename Interval::Value size_; // number of values (map_.size is number of intervals)
228 
229 private:
230  friend class boost::serialization::access;
231 
232  template<class S>
233  void serialize(S &s, const unsigned /*version*/) {
234  s & BOOST_SERIALIZATION_NVP(map_);
235  s & BOOST_SERIALIZATION_NVP(policy_);
236  s & BOOST_SERIALIZATION_NVP(size_);
237  }
238 
240  // Constructors
242 public:
246  IntervalMap(): size_(0) {}
247 
252  template<class Interval2, class T2, class Policy2>
254  typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
255  for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
256  insert(Interval(otherIter->key()), Value(otherIter->value()));
257  }
258 
263  template<class Interval2, class T2, class Policy2>
265  clear();
266  typedef typename IntervalMap<Interval2, T2, Policy2>::ConstNodeIterator OtherIterator;
267  for (OtherIterator otherIter=other.nodes().begin(); other!=other.nodes().end(); ++other)
268  insert(Interval(otherIter->key()), Value(otherIter->value()));
269  return *this;
270  }
271 
273  // Searching
275 public:
276 
283  boost::iterator_range<NodeIterator> nodes() { return map_.nodes(); }
284  boost::iterator_range<ConstNodeIterator> nodes() const { return map_.nodes(); }
291  boost::iterator_range<ConstIntervalIterator> intervals() const { return map_.keys(); }
292 
299  boost::iterator_range<ValueIterator> values() { return map_.values(); }
300  boost::iterator_range<ConstValueIterator> values() const { return map_.values(); }
308  NodeIterator lowerBound(const typename Interval::Value &scalar) {
309  return map_.lowerBound(Interval(scalar));
310  }
311  ConstNodeIterator lowerBound(const typename Interval::Value &scalar) const {
312  return map_.lowerBound(Interval(scalar));
313  }
321  NodeIterator upperBound(const typename Interval::Value &scalar) {
322  NodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
323  while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
324  ++ub;
325  return ub;
326  }
327  ConstNodeIterator upperBound(const typename Interval::Value &scalar) const {
328  ConstNodeIterator ub = map_.upperBound(Interval(scalar)); // first node that ENDS after scalar
329  while (ub!=map_.nodes().end() && ub->key().least() <= scalar)
330  ++ub;
331  return ub;
332  }
340  NodeIterator findPrior(const typename Interval::Value &scalar) {
341  return findPriorImpl(*this, scalar);
342  }
343  ConstNodeIterator findPrior(const typename Interval::Value &scalar) const {
344  return findPriorImpl(*this, scalar);
345  }
346 
347  template<class IMap>
349  findPriorImpl(IMap &imap, const typename Interval::Value &scalar) {
350  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
351  if (imap.isEmpty())
352  return imap.nodes().end();
353  Iter lb = imap.lowerBound(scalar);
354  if (lb!=imap.nodes().end() && lb->key().least() <= scalar)
355  return lb;
356  if (lb==imap.nodes().begin())
357  return imap.nodes().end();
358  return --lb;
359  }
367  NodeIterator find(const typename Interval::Value &scalar) {
368  return findImpl(*this, scalar);
369  }
370  ConstNodeIterator find(const typename Interval::Value &scalar) const {
371  return findImpl(*this, scalar);
372  }
373 
374  template<class IMap>
376  findImpl(IMap &imap, const typename Interval::Value &scalar) {
377  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
378  Iter found = imap.lowerBound(scalar);
379  if (found==imap.nodes().end() || scalar < found->key().least())
380  return imap.nodes().end();
381  return found;
382  }
390  boost::iterator_range<NodeIterator> findAll(const Interval &interval) {
391  return findAllImpl(*this, interval);
392  }
393  boost::iterator_range<ConstNodeIterator> findAll(const Interval &interval) const {
394  return findAllImpl(*this, interval);
395  }
396 
397  template<class IMap>
398  static boost::iterator_range<typename IntervalMapTraits<IMap>::NodeIterator>
399  findAllImpl(IMap &imap, const Interval &interval) {
400  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
401  if (interval.isEmpty())
402  return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
403  Iter begin = imap.lowerBound(interval.least());
404  if (begin==imap.nodes().end() || begin->key().least() > interval.greatest())
405  return boost::iterator_range<Iter>(imap.nodes().end(), imap.nodes().end());
406  return boost::iterator_range<Iter>(begin, imap.upperBound(interval.greatest()));
407  }
415  NodeIterator findFirstOverlap(const Interval &interval) {
416  return findFirstOverlapImpl(*this, interval);
417  }
418  ConstNodeIterator findFirstOverlap(const Interval &interval) const {
419  return findFirstOverlapImpl(*this, interval);
420  }
421 
422  template<class IMap>
424  findFirstOverlapImpl(IMap &imap, const Interval &interval) {
425  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
426  if (interval.isEmpty())
427  return imap.nodes().end();
428  Iter lb = imap.lowerBound(interval.least());
429  return lb!=imap.nodes().end() && interval.isOverlapping(lb->key()) ? lb : imap.nodes().end();
430  }
442  template<typename T2, class Policy2>
443  std::pair<NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
446  return findFirstOverlapImpl(*this, thisIter, other, otherIter);
447  }
448  template<typename T2, class Policy2>
449  std::pair<ConstNodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator>
452  return findFirstOverlapImpl(*this, thisIter, other, otherIter);
453  }
454 
455  template<class IMap, typename T2, class Policy2>
456  static std::pair<typename IntervalMapTraits<IMap>::NodeIterator,
459  typename IntervalMapTraits<IMap>::NodeIterator thisIter,
462  while (thisIter!=imap.nodes().end() && otherIter!=other.nodes().end()) {
463  if (thisIter->key().isOverlapping(otherIter->key()))
464  return std::make_pair(thisIter, otherIter);
465  if (thisIter->key().greatest() < otherIter->key().greatest()) {
466  ++thisIter;
467  } else {
468  ++otherIter;
469  }
470  }
471  return std::make_pair(imap.nodes().end(), other.nodes().end());
472  }
486  NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start) {
487  return firstFitImpl(*this, size, start);
488  }
489  ConstNodeIterator firstFit(const typename Interval::Value &size, ConstNodeIterator start) const {
490  return firstFitImpl(*this, size, start);
491  }
492 
493  template<class IMap>
495  firstFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
496  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
497  for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
498  if (isLarge(iter->key(), size))
499  return iter;
500  }
501  return imap.nodes().end();
502  }
503 
518  NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start) {
519  return bestFitImpl(*this, size, start);
520  }
521  ConstNodeIterator bestFit(const typename Interval::Value &size, ConstNodeIterator start) const {
522  return bestFitImpl(*this, size, start);
523  }
524 
525  template<class IMap>
527  bestFitImpl(IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits<IMap>::NodeIterator start) {
528  typedef typename IntervalMapTraits<IMap>::NodeIterator Iter;
529  Iter best = imap.nodes().end();
530  for (Iter iter=start; iter!=imap.nodes().end(); ++iter) {
531  if (iter->key().size()==size && size!=0)
532  return iter;
533  if (iter->key().size() > size && (best==imap.nodes().end() || iter->key().size() < best->key().size()))
534  best = iter;
535  }
536  return best;
537  }
546  Interval firstUnmapped(typename Interval::Value minAddr) const {
547  Interval all = Interval::whole();
548  for (ConstNodeIterator iter=lowerBound(minAddr); iter!=nodes().end(); ++iter) {
549  if (minAddr < iter->key().least()) // minAddr is not mapped
550  return Interval::hull(minAddr, iter->key().least()-1);
551  if (iter->key().greatest() == all.greatest())
552  return Interval(); // no unmapped addresses, prevent potential overflow in next statement
553  minAddr = iter->key().greatest() + 1;
554  }
555  return Interval::hull(minAddr, all.greatest());
556  }
557 
564  Interval lastUnmapped(typename Interval::Value maxAddr) const {
565  Interval all = Interval::whole();
566  for (ConstNodeIterator iter=findPrior(maxAddr); iter!=nodes().begin(); --iter) {
567  if (maxAddr > iter->key().greatest()) // maxAddr is not mapped
568  return Interval::hull(iter->key().greatest()+1, maxAddr);
569  if (iter->key().least() == all.least())
570  return Interval(); // no unmapped address, prevent potential overflow in next statement
571  maxAddr = iter->key().least() - 1;
572  }
573  return Interval::hull(all.least(), maxAddr);
574  }
575 
579  bool exists(const typename Interval::Value &size) const {
580  return find(size)!=nodes().end();
581  }
582 
584  // Accessors
586 public:
597  const Value& operator[](const typename Interval::Value &scalar) const {
598  ConstNodeIterator found = find(scalar);
599  if (found==nodes().end())
600  throw std::domain_error("key lookup failure; key is not in map domain");
601  return found->value();
602  }
603 
604  const Value& get(const typename Interval::Value &scalar) const {
605  ConstNodeIterator found = find(scalar);
606  if (found==nodes().end())
607  throw std::domain_error("key lookup failure; key is not in map domain");
608  return found->value();
609  }
625  Optional<Value> getOptional(const typename Interval::Value &scalar) const {
626  ConstNodeIterator found = find(scalar);
627  return found == nodes().end() ? Optional<Value>() : Optional<Value>(found->value());
628  }
629 
637  Value& getOrElse(const typename Interval::Value &scalar, Value &dflt) {
638  NodeIterator found = find(scalar);
639  return found == nodes().end() ? dflt : found->value();
640  }
641  const Value& getOrElse(const typename Interval::Value &scalar, const Value &dflt) const {
642  ConstNodeIterator found = find(scalar);
643  return found == nodes().end() ? dflt : found->value();
644  }
651  const Value& getOrDefault(const typename Interval::Value &scalar) const {
652  static const Value dflt;
653  ConstNodeIterator found = find(scalar);
654  return found==nodes().end() ? dflt : found->value();
655  }
656 
658  // Capacity
660 public:
661 
665  bool isEmpty() const {
666  return map_.isEmpty();
667  }
668 
673  size_t nIntervals() const {
674  return map_.size();
675  }
676 
681  typename Interval::Value size() const {
682  return size_;
683  }
684 
686  typename Interval::Value least() const {
687  ASSERT_forbid(isEmpty());
688  return map_.keys().begin()->least();
689  }
690 
692  typename Interval::Value greatest() const {
693  ASSERT_forbid(isEmpty());
694  ConstIntervalIterator last = map_.keys().end(); --last;
695  return last->greatest();
696  }
697 
702  Optional<typename Interval::Value> least(typename Interval::Value lowerLimit) const {
703  ConstNodeIterator found = lowerBound(lowerLimit); // first node ending at or after lowerLimit
704  if (found==nodes().end())
705  return Nothing();
706  return std::max(lowerLimit, found->key().least());
707  }
708 
713  Optional<typename Interval::Value> greatest(typename Interval::Value upperLimit) const {
714  ConstNodeIterator found = findPrior(upperLimit); // last node beginning at or before upperLimit
715  if (found==nodes().end())
716  return Nothing();
717  return std::min(upperLimit, found->key().greatest());
718  }
719 
724  Optional<typename Interval::Value> leastUnmapped(typename Interval::Value lowerLimit) const {
725  for (ConstNodeIterator iter = lowerBound(lowerLimit); iter!=nodes().end(); ++iter) {
726  if (lowerLimit < iter->key().least())
727  return lowerLimit;
728  lowerLimit = iter->key().greatest() + 1;
729  if (lowerLimit <= iter->key().least()) // sensitive to GCC optimization
730  return Nothing(); // overflow
731  }
732  return lowerLimit;
733  }
734 
739  Optional<typename Interval::Value> greatestUnmapped(typename Interval::Value upperLimit) const {
740  for (ConstNodeIterator iter = findPrior(upperLimit); iter!=nodes().end(); --iter) {
741  if (upperLimit > iter->key().greatest())
742  return upperLimit;
743  upperLimit = iter->key().least() - 1;
744  if (upperLimit >= iter->key().greatest()) // sensitive to GCC optimization
745  return Nothing(); // overflow
746  if (iter==nodes().begin())
747  break;
748  }
749  return upperLimit;
750  }
751 
753  Interval hull() const {
754  return isEmpty() ? Interval() : Interval::hull(least(), greatest());
755  }
756 
757 
759  // Mutators
761 public:
762 
764  void clear() {
765  map_.clear();
766  size_ = 0;
767  }
768 
770  void erase(const Interval &erasure) {
771  if (erasure.isEmpty())
772  return;
773 
774  // Find what needs to be removed, and create a list of things to insert, but delay actual removing until after
775  // the loop since Map::erase doesn't return a next iterator.
776  Map insertions; // what needs to be inserted back in
777  NodeIterator eraseBegin = nodes().end();
778  NodeIterator iter;
779  for (iter=lowerBound(erasure.least()); iter!=nodes().end() && !erasure.isLeftOf(iter->key()); ++iter) {
780  Interval foundInterval = iter->key();
781  Value &v = iter->value();
782  if (erasure.isContaining(foundInterval)) {
783  // erase entire found interval
784  if (eraseBegin==nodes().end())
785  eraseBegin = iter;
786  size_ -= foundInterval.size();
787  } else if (erasure.least()>foundInterval.least() && erasure.greatest()<foundInterval.greatest()) {
788  // erase the middle of the node, leaving a left and a right portion
789  ASSERT_require(eraseBegin==nodes().end());
790  eraseBegin = iter;
791  IntervalPair rt = splitInterval(foundInterval, erasure.greatest()+1);
792  Value rightValue = policy_.split(foundInterval, v /*in,out*/, rt.second.least());
793  insertions.insert(rt.second, rightValue);
794  IntervalPair lt = splitInterval(rt.first, erasure.least());
795  policy_.truncate(rt.first, v /*in,out*/, erasure.least());
796  insertions.insert(lt.first, v);
797  size_ -= erasure.size();
798  } else if (erasure.least() > foundInterval.least()) {
799  // erase the right part of the node
800  ASSERT_require(eraseBegin==nodes().end());
801  eraseBegin = iter;
802  IntervalPair halves = splitInterval(foundInterval, erasure.least());
803  policy_.truncate(foundInterval, v /*in,out*/, erasure.least());
804  insertions.insert(halves.first, v);
805  size_ -= halves.second.size();
806  } else if (erasure.greatest() < foundInterval.greatest()) {
807  // erase the left part of the node
808  if (eraseBegin==nodes().end())
809  eraseBegin = iter;
810  IntervalPair halves = splitInterval(foundInterval, erasure.greatest()+1);
811  Value rightValue = policy_.split(foundInterval, v /*in,out*/, halves.second.least());
812  insertions.insert(halves.second, rightValue);
813  size_ -= halves.first.size();
814  }
815  }
816 
817  // Do the actual erasing and insert the new stuff, which is easy now because we know it doesn't overlap with anything.
818  if (eraseBegin!=nodes().end())
819  map_.eraseAtMultiple(eraseBegin, iter);
820  map_.insertMultiple(insertions.nodes());
821  }
822 
826  template<typename T2, class Policy2>
828  ASSERT_forbid2((const void*)&other == (const void*)this, "use clear() instead");
830  for (OtherIter oi=other.nodes().begin(); oi!=other.nodes().end(); ++oi)
831  erase(oi->key());
832  }
833 
838  void insert(Interval key, Value value, bool makeHole=true) {
839  if (key.isEmpty())
840  return;
841  if (makeHole) {
842  erase(key);
843  } else {
844  NodeIterator found = lowerBound(key.least());
845  if (found!=nodes().end() && key.isOverlapping(found->key()))
846  return;
847  }
848 
849  // Attempt to merge with a left-adjoining node
850  if (key.least() - 1 < key.least()) {
851  NodeIterator left = find(key.least() - 1);
852  if (left!=nodes().end() &&
853  left->key().greatest()+1==key.least() &&
854  policy_.merge(left->key(), left->value(), key, value)) {
855  key = Interval::hull(left->key().least(), key.greatest());
856  std::swap(value, left->value());
857  size_ -= left->key().size();
858  map_.eraseAt(left);
859  }
860  }
861 
862  // Attempt to merge with a right-adjoining node
863  if (key.greatest() + 1 > key.greatest()) {
864  NodeIterator right = find(key.greatest() + 1);
865  if (right!=nodes().end() &&
866  key.greatest()+1==right->key().least() &&
867  policy_.merge(key, value, right->key(), right->value())) {
868  key = Interval::hull(key.least(), right->key().greatest());
869  size_ -= right->key().size();
870  map_.eraseAt(right);
871  }
872  }
873 
874  map_.insert(key, value);
875  size_ += key.size();
876  }
877 
882  template<typename T2, class Policy2>
883  void insertMultiple(const IntervalMap<Interval, T2, Policy2> &other, bool makeHole=true) {
884  ASSERT_forbid2((const void*)&other == (const void*)this, "cannot insert a container into itself");
885  typedef typename IntervalMap<Interval, T2, Policy>::ConstNodeIterator OtherIter;
886  for (OtherIter oi=other.nodes().begin(); oi!=other.nodes().end(); ++oi)
887  insert(oi->key(), Value(oi->value()), makeHole);
888  }
889 
890 // FIXME[Robb Matzke 2014-04-13]
891 // // Intersection
892 // void intersect(const Interval&);
893 
894 
895 
897  // Predicates
899 public:
900  bool isOverlapping(const Interval &interval) const {
901  return findFirstOverlap(interval)!=nodes().end();
902  }
903 
904  template<typename T2, class Policy2>
905  bool isOverlapping(const IntervalMap<Interval, T2, Policy2> &other) const {
906  return findFirstOverlap(nodes().begin(), other, other.nodes().begin()).first != nodes().end();
907  }
908 
909  bool isDistinct(const Interval &interval) const {
910  return !isOverlapping(interval);
911  }
912 
913  template<typename T2, class Policy2>
914  bool isDistinct(const IntervalMap<Interval, T2, Policy2> &other) const {
915  return !isOverlapping(other);
916  }
917 
918  bool contains(Interval key) const {
919  if (key.isEmpty())
920  return true;
921  ConstNodeIterator found = find(key.least());
922  while (1) {
923  if (found==nodes().end())
924  return false;
925  if (key.least() < found->key().least())
926  return false;
927  ASSERT_require(key.isOverlapping(found->key()));
928  if (key.greatest() <= found->key().greatest())
929  return true;
930  key = splitInterval(key, found->key().greatest()+1).second;
931  ++found;
932  }
933  }
934 
935  template<typename T2, class Policy2>
936  bool contains(const IntervalMap<Interval, T2, Policy2> &other) const {
937  for (ConstNodeIterator iter=other.nodes().begin(); iter!=other.nodes().end(); ++iter) {
938  if (!contains(iter->key()))
939  return false;
940  }
941  return true;
942  }
943 
944 
946  // Private support methods
948 private:
949  static IntervalPair splitInterval(const Interval &interval, const typename Interval::Value &splitPoint) {
950  ASSERT_forbid(interval.isEmpty());
951  ASSERT_require(splitPoint > interval.least() && splitPoint <= interval.greatest());
952 
953  Interval left = Interval::hull(interval.least(), splitPoint-1);
954  Interval right = Interval::hull(splitPoint, interval.greatest());
955  return IntervalPair(left, right);
956  }
957 
958  // a more convenient way to check whether interval contains at least size items and still handle overflow
959  static bool isLarge(const Interval &interval, boost::uint64_t size) {
960  return !interval.isEmpty() && (interval.size()==0 || interval.size() >= size);
961  }
962 };
963 
964 } // namespace
965 } // namespace
966 
967 #endif
NodeIterator upperBound(const typename Interval::Value &scalar)
Find the first node whose interval begins above the specified scalar key.
Definition: IntervalMap.h:321
NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start)
Find the first fit node at or after a starting point.
Definition: IntervalMap.h:486
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.
Definition: IntervalMap.h:527
Interval lastUnmapped(typename Interval::Value maxAddr) const
Find the last unmapped region.
Definition: IntervalMap.h:564
bool merge(const Interval &leftInterval, Value &leftValue, const Interval &rightInterval, Value &rightValue)
Merge two values if possible.
Definition: IntervalMap.h:61
boost::iterator_range< ConstNodeIterator > findAll(const Interval &interval) const
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:393
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterators for traversing keys.
Definition: IntervalMap.h:291
An associative container whose keys are non-overlapping intervals.
Definition: IntervalMap.h:171
const Value & getOrElse(const typename Interval::Value &scalar, const Value &dflt) const
Lookup and return a value or something else.
Definition: IntervalMap.h:641
NodeIterator findPrior(const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
Definition: IntervalMap.h:340
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
IntervalMap::NodeIterator NodeIterator
Node iterator.
Definition: IntervalMap.h:26
ConstNodeIterator findPrior(const typename Interval::Value &scalar) const
Find the last node whose interval starts at or below the specified scalar key.
Definition: IntervalMap.h:343
ConstNodeIterator findFirstOverlap(const Interval &interval) const
Find first interval that overlaps with the specified interval.
Definition: IntervalMap.h:418
ConstNodeIterator lowerBound(const typename Interval::Value &scalar) const
Find the first node whose interval ends at or above the specified scalar key.
Definition: IntervalMap.h:311
Interval::Value least() const
Returns the minimum scalar key.
Definition: IntervalMap.h:686
Traits for IntervalMap.
Definition: IntervalMap.h:25
Optional< typename Interval::Value > least(typename Interval::Value lowerLimit) const
Returns the limited-minimum scalar key.
Definition: IntervalMap.h:702
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.
Definition: IntervalMap.h:349
NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start)
Find the best fit node at or after a starting point.
Definition: IntervalMap.h:518
Map::Node Node
Storage node.
Definition: IntervalMap.h:196
ConstNodeIterator find(const typename Interval::Value &scalar) const
Find the node containing the specified scalar key.
Definition: IntervalMap.h:370
bool isEmpty() const
Determine if the container is empty.
Definition: IntervalMap.h:665
Interval::Value size() const
Returns the number of values represented by this container.
Definition: IntervalMap.h:681
Map & clear()
Remove all nodes.
Definition: Sawyer/Map.h:616
Interval::Value greatest() const
Returns the maximum scalar key.
Definition: IntervalMap.h:692
boost::iterator_range< ValueIterator > values()
Iterators for container values.
Definition: Sawyer/Map.h:298
IntervalMap::ValueIterator ValueIterator
Value iterator.
Definition: IntervalMap.h:27
Name space for the entire library.
Definition: Access.h:11
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:137
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.
Definition: IntervalMap.h:450
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
Definition: IntervalMap.h:299
bool isEmpty() const
Determines whether this container is empty.
Definition: Sawyer/Map.h:315
Map::NodeIterator NodeIterator
Node iterator.
Definition: IntervalMap.h:220
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
Definition: IntervalMap.h:724
Value split(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Split one value into two values.
Definition: IntervalMap.h:73
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.
Definition: IntervalMap.h:495
Container::Map< Interval, Value, IntervalCompare > Map
Type of the underlying map.
Definition: IntervalMap.h:190
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.
Definition: IntervalMap.h:444
NodeIterator lowerBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:390
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Definition: IntervalMap.h:415
IntervalMap & operator=(const IntervalMap< Interval2, T2, Policy2 > &other)
Assignment operator.
Definition: IntervalMap.h:264
ConstNodeIterator firstFit(const typename Interval::Value &size, ConstNodeIterator start) const
Find the first fit node at or after a starting point.
Definition: IntervalMap.h:489
Value & getOrElse(const typename Interval::Value &scalar, Value &dflt)
Lookup and return a value or something else.
Definition: IntervalMap.h:637
boost::iterator_range< ConstValueIterator > values() const
Iterators for traversing values.
Definition: IntervalMap.h:300
bool exists(const typename Interval::Value &size) const
Returns true if element exists.
Definition: IntervalMap.h:579
void clear()
Empties the container.
Definition: IntervalMap.h:764
void erase(const Interval &erasure)
Erase the specified interval.
Definition: IntervalMap.h:770
static IntervalMapTraits< IMap >::NodeIterator findFirstOverlapImpl(IMap &imap, const Interval &interval)
Find first interval that overlaps with the specified interval.
Definition: IntervalMap.h:424
Bidirectional iterator over values.
Definition: Sawyer/Map.h:188
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Definition: IntervalMap.h:838
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.
Definition: IntervalMap.h:458
static Interval whole()
Construct an interval that covers the entire domain.
Definition: Interval.h:167
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
void insertMultiple(const IntervalMap< Interval, T2, Policy2 > &other, bool makeHole=true)
Insert values from another container.
Definition: IntervalMap.h:883
Optional< typename Interval::Value > greatestUnmapped(typename Interval::Value upperLimit) const
Returns the limited-maximum unmapped scalar key.
Definition: IntervalMap.h:739
ConstNodeIterator bestFit(const typename Interval::Value &size, ConstNodeIterator start) const
Find the best fit node at or after a starting point.
Definition: IntervalMap.h:521
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:96
Map & insertMultiple(const OtherNodeIterator &begin, const OtherNodeIterator &end)
Insert multiple values.
Definition: Sawyer/Map.h:566
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Definition: IntervalMap.h:283
Map::ConstKeyIterator ConstIntervalIterator
Interval iterator.
Definition: IntervalMap.h:202
Interval hull() const
Returns the range of values in this map.
Definition: IntervalMap.h:753
const Value & operator[](const typename Interval::Value &scalar) const
Returns a reference to an existing value.
Definition: IntervalMap.h:597
Bidirectional iterator over values.
Definition: Sawyer/Map.h:202
Map::ConstValueIterator ConstValueIterator
Value iterator.
Definition: IntervalMap.h:211
IntervalMap::Value & ValueReference
Reference to value.
Definition: IntervalMap.h:28
static IntervalMapTraits< IMap >::NodeIterator findImpl(IMap &imap, const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
Definition: IntervalMap.h:376
Policy indicating how values are merged and split.
Definition: IntervalMap.h:43
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIterator > findAllImpl(IMap &imap, const Interval &interval)
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:399
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:390
Map & eraseAt(const NodeIterator &iter)
Remove a node by iterator.
Definition: Sawyer/Map.h:655
IntervalMap()
Default constructor.
Definition: IntervalMap.h:246
Map::ConstNodeIterator ConstNodeIterator
Node iterator.
Definition: IntervalMap.h:221
boost::iterator_range< ConstKeyIterator > keys()
Iterators for container keys.
Definition: Sawyer/Map.h:284
Map & eraseAtMultiple(const Iter &begin, const Iter &end)
Remove multiple nodes by iterator range.
Definition: Sawyer/Map.h:681
Optional< typename Interval::Value > greatest(typename Interval::Value upperLimit) const
Returns the limited-maximum scalar key.
Definition: IntervalMap.h:713
boost::iterator_range< ConstNodeIterator > nodes() const
Iterators for traversing nodes.
Definition: IntervalMap.h:284
IntervalMap(const IntervalMap< Interval2, T2, Policy2 > &other)
Copy constructor.
Definition: IntervalMap.h:253
Map & insert(const Key &key, const Value &value)
Insert or update a key/value pair.
Definition: Sawyer/Map.h:530
const Value & getOrDefault(const typename Interval::Value &scalar) const
Lookup and return a value or a default.
Definition: IntervalMap.h:651
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:173
NodeIterator upperBound(const Key &key)
Find a node close to a key.
Definition: Sawyer/Map.h:407
Optional< Value > getOptional(const typename Interval::Value &scalar) const
Lookup and return a value or nothing.
Definition: IntervalMap.h:625
size_t nIntervals() const
Number of nodes in the container.
Definition: IntervalMap.h:673
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
Definition: IntervalMap.h:308
Represents no value.
Definition: Optional.h:32
void truncate(const Interval &interval, Value &value, const typename Interval::Value &splitPoint)
Discard the right part of a value.
Definition: IntervalMap.h:83
boost::iterator_range< NodeIterator > nodes()
Iterators for container nodes.
Definition: Sawyer/Map.h:271
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
Definition: IntervalMap.h:367
Interval firstUnmapped(typename Interval::Value minAddr) const
Find the first unmapped region.
Definition: IntervalMap.h:546
size_t size() const
Number of nodes, keys, or values in this container.
Definition: Sawyer/Map.h:322
Map::ValueIterator ValueIterator
Value iterator.
Definition: IntervalMap.h:210
void eraseMultiple(const IntervalMap< Interval, T2, Policy2 > &other)
Erase intervals specified in another IntervalMap.
Definition: IntervalMap.h:827
ConstNodeIterator upperBound(const typename Interval::Value &scalar) const
Find the first node whose interval begins above the specified scalar key.
Definition: IntervalMap.h:327
Type for stored nodes.
Definition: Sawyer/Map.h:87
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:154