ROSE  0.11.145.0
rangemap.h
1 // This interface will be deprecated at some point in the not-to-distant future. Use Sawyer::Container::IntervalMap instead.
2 
3 
4 
5 #ifndef ROSE_RANGEMAP_H
6 #define ROSE_RANGEMAP_H
7 
8 /* This file defines four main template classes:
9  * - RangeMap: Time and space efficient storage of non-overlapping Range objects each associated with an arbitrary value.
10  * - Range: Contiguous set of integers defined by the starting value and size.
11  * - RangeMapVoid: Void value for RangeMap classes that don't store any useful value (just the ranges themselves).
12  * - RangeMapValue: Class for storing simple values in a RangeMap.
13  */
14 
15 
16 /* There is no need to include "sage3basic.h"; this file defines all it needs. */
17 
18 #ifndef __STDC_FORMAT_MACROS
19 #define __STDC_FORMAT_MACROS
20 #endif
21 #include <inttypes.h>
22 
23 #include <cassert>
24 #include <cmath>
25 #include <cstdlib>
26 #include <iostream>
27 #include <map>
28 #include <sstream>
29 #include <string>
30 #include <vector>
31 
32 /* Define this if you want the class to do fairly extensive testing of the consistency of the map after every operation. Note
33  * that this substantially increases execution time. The NDEBUG preprocessor symbol must not be defined, or else the check()
34  * method won't really do anything. */
35 //#define RANGEMAP_CHECK
36 
37 /******************************************************************************************************************************
38  * Range<>
39  ******************************************************************************************************************************/
40 
49 template<class T>
50 class Range {
51 public:
52  typedef T Value;
53  typedef std::pair<Range, Range> Pair;
55 protected:
56  Value r_first;
57  Value r_last;
59 public:
63  : r_first(1), r_last(0) {} // see clear()
64 
66  explicit Range(const Value &first)
67  : r_first(first), r_last(first) {}
68 
73  Range(const Value &first, const Value &size)
74  : r_first(first), r_last(first+size-1) {
75  if (0==size) {
76  r_last = first; // or else clear() is a no-op leaving invalid values
77  clear();
78  } else {
79  assert(!empty()); // checks for overflow
80  }
81  }
82 
84  template<class Other>
85  explicit Range(const Other &other)
86  : r_first(other.relaxed_first()), r_last(other.relaxed_last()) {}
87 
92  static Range inin(const Value &v1, const Value &v2) {
93  assert(v1<=v2);
94  Range retval;
95  retval.first(v1);
96  retval.last(v2);
97  return retval;
98  }
99 
103  void first(const Value &first) {
104  r_first = first;
105  }
106  const Value first() const {
107  assert(!empty());
108  return r_first;
109  }
110 
111 // DQ (9/3/2015): Intel v14 compiler warns that use of "const" is meaningless.
112 // I think this is correct since this is being returned by value.
113 // const Value
114  Value
115  relaxed_first() const {
116  if (!empty())
117  return first();
118  if (1==r_first-r_last)
119  return r_first-1;
120  return r_first;
121  }
127  void last(const Value &last) {
128  r_last = last;
129  }
130  const Value last() const {
131  assert(!empty());
132  return r_last;
133  }
134  const Value relaxed_last() const {
135  return empty() ? relaxed_first() : last();
136  }
147  Value size() const {
148  if (empty())
149  return 0;
150  return r_last + 1 - r_first;
151  }
152 
162  void resize(const Value &new_size) {
163  assert(!empty());
164  if (0==new_size) {
165  clear();
166  } else {
167  r_last = r_first + new_size - 1;
168  assert(!empty()); // this one is to check for overflow of r_last
169  }
170  }
171  void relaxed_resize(const Value &new_size) {
172  if (0==new_size) {
173  clear();
174  } else {
175  r_first = relaxed_first();
176  r_last = r_first + new_size - 1;
177  assert(!empty()); // this one is to check for overflow of r_last
178  }
179  }
184  Pair split_range_at(const Value &at) const {
185  assert(!empty());
186  assert(at>first() && at<=last()); // neither half can be empty
187  Range left(first(), at-first());
188  Range right(at, last()+1-at);
189  return std::make_pair(left, right);
190  }
191 
195  Range join(const Range &right) const {
196  if (empty())
197  return right;
198  if (right.empty())
199  return *this;
200  assert(abuts_lt(right));
201  return Range::inin(first(), right.last());
202  }
203 
218  std::vector<Range> erase(const Range &to_erase) const {
219  std::vector<Range> retval;
220  if (to_erase.empty() || distinct(to_erase)) {
221  retval.push_back(*this);
222  } else if (contained_in(to_erase)) {
223  // void
224  } else {
225  if (begins_before(to_erase))
226  retval.push_back(Range::inin(first(), to_erase.first()-1));
227  if (ends_after(to_erase))
228  retval.push_back(Range::inin(to_erase.last()+1, last()));
229  }
230  return retval;
231  }
232 
234  Range intersect(const Range &other) const {
235  if (empty() || contains(other))
236  return other;
237  if (other.empty() || other.contains(*this))
238  return *this;
239  if (!overlaps(other))
240  return Range();
241  return Range::inin(
242  std::max(first(), other.first()),
243  std::min(last(), other.last()));
244  }
245 
249  bool empty() const {
250  return r_last<r_first; // can't use first() or last() here because they're not valid for empty ranges.
251  }
252 
255  void clear() {
256  if (!empty()) {
257  if (r_first<maximum()) {
258  r_first = r_first + 1;
259  r_last = r_first - 1;
260  } else {
261  r_last = r_first - 2;
262  }
263  assert(empty());
264  }
265  }
266 
270  bool begins_with(const Range &x) const {
271  if (empty() || x.empty())
272  return false;
273  return first() == x.first();
274  }
275 
279  bool ends_with(const Range &x) const {
280  if (empty() || x.empty())
281  return false;
282  return last() == x.last();
283  }
284 
288  bool begins_after(const Range &x, bool strict=true) const {
289  if (empty() || x.empty())
290  return false;
291  return strict ? first() > x.first() : first() >= x.first();
292  }
293 
297  bool begins_before(const Range &x, bool strict=true) const {
298  if (empty() || x.empty())
299  return false;
300  return strict ? first() < x.first() : first() <= x.first();
301  }
302 
306  bool ends_after(const Range &x, bool strict=true) const {
307  if (empty() || x.empty())
308  return false;
309  return strict ? last() > x.last() : last() >= x.last();
310  }
311 
315  bool ends_before(const Range &x, bool strict=true) const {
316  if (empty() || x.empty())
317  return false;
318  return strict ? last() < x.last() : last() <= x.last();
319  }
320 
326  bool contains(const Range &x, bool strict=false) const {
327  if (empty() || x.empty())
328  return false;
329  return strict ? x.first()>first() && x.last()<last() : x.first()>=first() && x.last()<=last();
330  }
331 
337  bool contained_in(const Range &x, bool strict=false) const {
338  if (empty() || x.empty())
339  return false;
340  return strict ? first()>x.first() && last()<x.last() : first()>=x.first() && last()<=x.last();
341  }
342 
346  bool congruent(const Range &x) const {
347  if (empty() || x.empty())
348  return empty() && x.empty();
349  return first()==x.first() && last()==x.last();
350  }
351 
356  bool left_of(const Range &x) const {
357  if (empty() || x.empty())
358  return false;
359  return last() < x.first();
360  }
361 
366  bool right_of(const Range &x) const {
367  if (empty() || x.empty())
368  return false;
369  return first() > x.last();
370  }
371 
375  bool overlaps(const Range &x) const {
376  if (empty() || x.empty())
377  return false;
378  return !left_of(x) && !right_of(x);
379  }
380 
385  bool distinct(const Range &x) const {
386  if (empty() || x.empty())
387  return true;
388  return !overlaps(x);
389  }
390 
395  bool abuts_lt(const Range &x) const {
396  if (empty() || x.empty())
397  return false;
398  return last()+1 == x.first();
399  }
400 
405  bool abuts_gt(const Range &x) const {
406  if (empty() || x.empty())
407  return false;
408  return first() == x.last()+1;
409  }
410 
412  static Value minimum() {
413  return 0; // FIXME
414  }
415 
417  static Value maximum() {
418  return (Value)(-1); // FIXME
419  }
420 
422  static Range all() {
423  return Range::inin(minimum(), maximum());
424  }
425 
426  bool operator==(const Range &x) const {
427  return congruent(x);
428  }
429  bool operator!=(const Range &x) const {
430  return !congruent(x);
431  }
432 
433  void print(std::ostream &o) const {
434  if (empty()) {
435  o <<"<empty>";
436  } else if (first()==last()) {
437  o <<first();
438  } else {
439  o <<first() <<".." <<last();
440  }
441  }
442 
443  friend std::ostream& operator<<(std::ostream &o, const Range &x) {
444  x.print(o);
445  return o;
446  }
447 };
448 
449 /******************************************************************************************************************************
450  * Specializations for Range<double>
451  ******************************************************************************************************************************/
452 
453 template<>
455 
456 template<>
457 bool
458 Range<double>::empty() const;
459 
460 template<>
461 void
463 
464 template<>
465 // DQ (9/3/2015): Intel v14 compiler warns that use of "const" is meaningless.
466 // I think this is correct since this is being returned by value.
467 // const double
468 double
470 
471 template<>
472 double
473 Range<double>::size() const;
474 
475 template<>
476 void
477 Range<double>::resize(const double &new_size);
478 
479 template<>
480 void
481 Range<double>::relaxed_resize(const double &new_size);
482 
483 template<>
485 Range<double>::split_range_at(const double &at) const;
486 
487 template<>
488 double
490 
491 template<>
492 double
494 
495 /******************************************************************************************************************************
496  * Specializations for Range<float>
497  ******************************************************************************************************************************/
498 
499 template<>
501 
502 template<>
503 bool
504 Range<float>::empty() const;
505 
506 template<>
507 void
509 
510 template<>
511 // DQ (9/3/2015): Intel v14 compiler warns that use of "const" is meaningless.
512 // I think this is correct since this is being returned by value.
513 // const float
514 float
516 
517 template<>
518 float
519 Range<float>::size() const;
520 
521 template<>
522 void
523 Range<float>::resize(const float &new_size);
524 
525 template<>
526 void
527 Range<float>::relaxed_resize(const float &new_size);
528 
529 template<>
531 Range<float>::split_range_at(const float &at) const;
532 
533 template<>
534 float
536 
537 template<>
538 float
540 
541 /******************************************************************************************************************************
542  * RangeMap void values
543  ******************************************************************************************************************************/
544 
547 template<class R>
549 public:
550  typedef R Range;
551 
552  RangeMapVoid() {}
553 
554  template<class Other>
555  explicit RangeMapVoid(const Other&) {}
556 
559  void removing(const Range&) {}
560 
564  void truncate(const Range&, const typename Range::Value&) {
565  }
566 
581  bool merge(const Range &/*my_range*/, const Range &/*other_range*/, const RangeMapVoid &/*other_value*/) {
582  return true;
583  }
584 
589  RangeMapVoid split(const Range&, const typename Range::Value&) {
590  return RangeMapVoid();
591  }
592 
593  void print(std::ostream&) const {}
594  friend std::ostream& operator<<(std::ostream &o, const RangeMapVoid &x) {
595  x.print(o);
596  return o;
597  }
598 };
599 
600 /******************************************************************************************************************************
601  * RangeMap numeric values
602  ******************************************************************************************************************************/
603 
606 template<class R, class T>
607 class RangeMapNumeric /*final*/ {
608 public:
609  typedef R Range;
610  typedef T Value;
611 
613  RangeMapNumeric(): value(0) {}
614 
616  RangeMapNumeric(Value v): value(v) {} // implicit
617 
620  void set(Value v) /*final*/ {
621  value = v;
622  }
623  virtual Value get() const /*final*/ {
624  return value;
625  }
630  void removing(const Range &my_range) /*final*/ {
631  assert(!my_range.empty());
632  }
633 
635  void truncate(const Range &my_range, const typename Range::Value &new_end) /*final*/ {
636  assert(new_end>my_range.first() && new_end<=my_range.last());
637  }
638 
640  bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value) /*final*/ {
641  assert(!my_range.empty() && !other_range.empty());
642  return get()==other_value.get();
643  }
644 
646  RangeMapNumeric split(const Range &my_range, typename Range::Value new_end) /*final*/ {
647  assert(my_range.contains(Range(new_end)));
648  return *this;
649  }
650 
653  void print(std::ostream &o) const /*final*/ {
654  o <<value;
655  }
656  friend std::ostream& operator<<(std::ostream &o, const RangeMapNumeric &x) {
657  x.print(o);
658  return o;
659  }
662 private:
663  Value value;
664 };
665 
666 /******************************************************************************************************************************
667  * RangeMap simple values
668  ******************************************************************************************************************************/
669 
673 template<class R, class T>
675 public:
676  typedef R Range;
677  typedef T Value;
678 
681 
683  RangeMapValue(const Value &v) { // implicit
684  value = v;
685  }
686 
687  /* This class often serves as a base class, so we have some virtual methods. */
688  virtual ~RangeMapValue() {}
689 
690 
693  virtual void set(const Value &v) {
694  value = v;
695  }
696  virtual Value get() const {
697  return value;
698  }
703  virtual void removing(const Range &my_range) {
704  ASSERT_always_require(!my_range.empty());
705  }
706 
708  virtual void truncate(const Range &my_range, const typename Range::Value &new_end) {
709  ASSERT_always_require(new_end>my_range.first() && new_end<=my_range.last());
710  }
711 
713  bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value) {
714  ASSERT_always_require(!my_range.empty() && !other_range.empty());
715  return get()==other_value.get();
716  }
717 
718 #if 0 /* Must be implemented in the subclass due to return type. */
719 
720  RangeMapValue split(const Range &my_range, const typename Range::Value &new_end) {
721  assert(my_range.contains(Range(new_end)));
722  return *this;
723  }
724 #endif
725 
728  virtual void print(std::ostream &o) const {
729  o <<value;
730  }
731  friend std::ostream& operator<<(std::ostream &o, const RangeMapValue &x) {
732  x.print(o);
733  return o;
734  }
737 protected:
738  Value value;
739 };
740 
741 /******************************************************************************************************************************
742  * RangeMap<>
743  ******************************************************************************************************************************/
744 
847 template<class R, class T=RangeMapVoid<R> >
848 class RangeMap {
849 public:
850  typedef R Range;
851  typedef T Value;
853 protected:
854  /* The keys of the underlying map are sorted by their last value rather than beginning value. This allows us to use the
855  * map's lower_bound() method to find the range to which an address might belong. Since the ranges in the map are
856  * non-overlapping, sorting by ending address has the same effect as sorting by starting address. */
857  struct RangeCompare {
858  bool operator()(const Range &a, const Range &b) const {
859  return a.last() < b.last();
860  }
861  };
862 
863  typedef std::pair<Range, Range> RangePair;
864  typedef std::pair<Range, Value> MapPair;
865  typedef std::map<Range, Value, RangeCompare> Map;
866  Map ranges;
867 
868 public:
869  typedef typename Map::iterator iterator;
870  typedef typename Map::const_iterator const_iterator;
871  typedef typename Map::reverse_iterator reverse_iterator;
872  typedef typename Map::const_reverse_iterator const_reverse_iterator;
873 
874  /**************************************************************************************************************************
875  * Constructors
876  **************************************************************************************************************************/
877 public:
878 
880  RangeMap() {}
881 
883  template<class Other>
884  explicit RangeMap(const Other &other) {
885  for (typename Other::const_iterator ri=other.begin(); ri!=other.end(); ++ri) {
886  Range new_range(ri->first);
887  Value new_value(ri->second);
888  insert(new_range, new_value);
889  }
890  }
891 
892  /**************************************************************************************************************************
893  * Iterators and searching
894  **************************************************************************************************************************/
895 public:
896 
901  iterator begin() {
902  return ranges.begin();
903  }
904  const_iterator begin() const {
905  return ranges.begin();
906  }
913  iterator end() {
914  return ranges.end();
915  }
916  const_iterator end() const {
917  return ranges.end();
918  }
925  reverse_iterator rbegin() {
926  return ranges.rbegin();
927  }
928  const_reverse_iterator rbegin() const {
929  return ranges.rbegin();
930  }
938  reverse_iterator rend() {
939  return ranges.rend();
940  }
941  const_reverse_iterator rend() const {
942  return ranges.rend();
943  }
950  iterator find(const typename Range::Value &addr) {
951  iterator ei = lower_bound(addr);
952  if (ei==end() || Range(addr).left_of(ei->first))
953  return end();
954  return ei;
955  }
956  const_iterator find(const typename Range::Value &addr) const {
957  const_iterator ei = lower_bound(addr);
958  if (ei==end() || Range(addr).left_of(ei->first))
959  return end();
960  return ei;
961  }
968  iterator lower_bound(const typename Range::Value &addr) {
969  return ranges.lower_bound(Range(addr));
970  }
971  const_iterator lower_bound(const typename Range::Value &addr) const {
972  return ranges.lower_bound(Range(addr));
973  }
979  iterator find_prior(const typename Range::Value &addr) {
980  if (empty())
981  return end();
982  iterator lb = lower_bound(addr);
983  if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
984  return lb;
985  if (lb==begin())
986  return end();
987  return --lb;
988  }
989  const_iterator find_prior(const typename Range::Value &addr) const {
990  if (empty())
991  return end();
992  const_iterator lb = lower_bound(addr);
993  if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
994  return lb;
995  if (lb==begin())
996  return end();
997  return --lb;
998  }
1006  iterator best_fit(const typename Range::Value &size, iterator start) {
1007  iterator best = end();
1008  for (iterator ri=start; ri!=end(); ++ri) {
1009  if (ri->first.size()==size)
1010  return ri;
1011  if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
1012  best = ri;
1013  }
1014  return best;
1015  }
1016  const_iterator best_fit(const typename Range::Value &size, const_iterator start) const {
1017  const_iterator best = end();
1018  for (const_iterator ri=start; ri!=end(); ++ri) {
1019  if (ri->first.size()==size)
1020  return ri;
1021  if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
1022  best = ri;
1023  }
1024  return best;
1025  }
1032  iterator first_fit(const typename Range::Value &size, iterator start) {
1033  for (iterator ri=start; ri!=end(); ++ri) {
1034  if (ri->first.size()>=size)
1035  return ri;
1036  }
1037  return end();
1038  }
1039  const_iterator first_fit(const typename Range::Value &size, const_iterator start) {
1040  for (const_iterator ri=start; ri!=end(); ++ri) {
1041  if (ri->first.size()>=size)
1042  return ri;
1043  }
1044  return end();
1045  }
1048  /**************************************************************************************************************************
1049  * Capacity
1050  **************************************************************************************************************************/
1051 public:
1052 
1054  bool empty() const {
1055  return ranges.empty();
1056  }
1057 
1060  size_t nranges() const {
1061  return ranges.size();
1062  }
1063 
1068  typename Range::Value size() const {
1069  typename Range::Value retval = 0;
1070  for (const_iterator ei=begin(); ei!=end(); ++ei)
1071  retval += ei->first.size();
1072  return retval;
1073  }
1074 
1076  typename Range::Value min() const {
1077  assert(!empty());
1078  return ranges.begin()->first.first();
1079  }
1080 
1082  typename Range::Value max() const {
1083  assert(!empty());
1084  return ranges.rbegin()->first.last();
1085  }
1086 
1088  Range minmax() const {
1089  typename Range::Value lt=min(), rt=max();
1090  return Range::inin(lt, rt);
1091  }
1092 
1093  /**************************************************************************************************************************
1094  * Low-level support functions
1095  **************************************************************************************************************************/
1096 protected:
1097 
1098  /**************************************************************************************************************************
1099  * Modifiers
1100  **************************************************************************************************************************/
1101 public:
1102 
1105  void clear(bool notify=true) {
1106  if (notify) {
1107  for (iterator ei=begin(); ei!=end(); ++ei)
1108  ei->second.removing(ei->first);
1109  }
1110  ranges.clear();
1111  }
1112 
1117  void erase(const Range &erase_range) {
1118  /* This loop figures out what needs to be removed and calls the elements' removing(), truncate(), etc. methods but does
1119  * not actually erase them from the underlying map yet. We must not erase them yet because the std::map::erase()
1120  * method doesn't return any iterator. Instead, we create a list (via an iterator range) of elements that will need to
1121  * be erased from the underlying map.
1122  *
1123  * This loop also creates a list of items that need to be inserted into the underlying map. Even though the
1124  * std::map::insert() can return an iterator, we can't call it inside the loop because then our erasure iterators will
1125  * become invalid. */
1126  if (erase_range.empty())
1127  return;
1128  Map insertions;
1129  iterator erase_begin=end();
1130  iterator ei;
1131  for (ei=lower_bound(erase_range.first()); ei!=end() && !erase_range.left_of(ei->first); ++ei) {
1132  Range found_range = ei->first;
1133  Value &v = ei->second;
1134  if (erase_range.contains(found_range)) {
1135  /* Erase entire found range. */
1136  if (erase_begin==end())
1137  erase_begin = ei;
1138  v.removing(found_range);
1139  } else if (erase_range.contained_in(found_range, true/*strict*/)) {
1140  /* Erase middle of found range. */
1141  assert(erase_begin==end());
1142  erase_begin = ei;
1143  RangePair rt = found_range.split_range_at(erase_range.last()+1);
1144  insertions[rt.second] = v.split(found_range, rt.second.first());
1145  RangePair lt = rt.first.split_range_at(erase_range.first());
1146  v.truncate(rt.first, erase_range.first());
1147  insertions[lt.first] = v;
1148  } else if (erase_range.begins_after(found_range, true/*strict*/)) {
1149  /* Erase right part of found range. */
1150  assert(erase_begin==end());
1151  erase_begin = ei;
1152  RangePair halves = found_range.split_range_at(erase_range.first());
1153  v.truncate(found_range, erase_range.first());
1154  insertions[halves.first] = v;
1155  } else if (erase_range.ends_before(found_range, true/*strict*/)) {
1156  /* Erase left part of found range. */
1157  if (erase_begin==end())
1158  erase_begin = ei;
1159  RangePair halves = found_range.split_range_at(erase_range.last()+1);
1160  insertions[halves.second] = v.split(found_range, halves.second.first());
1161  v.removing(halves.first);
1162  }
1163  }
1164 
1165  /* Inserting is easy here because we already know that no merging is necessary. */
1166  if (erase_begin!=end())
1167  ranges.erase(erase_begin, ei);
1168  ranges.insert(insertions.begin(), insertions.end());
1169 #ifdef RANGEMAP_CHECK
1170  check();
1171 #endif
1172  }
1173 
1176  template<class OtherMap>
1177  void erase_ranges(const OtherMap &other) {
1178  assert((const void*)&other!=(const void*)this);
1179  for (typename OtherMap::const_iterator ri=other.begin(); ri!=other.end(); ++ri)
1180  erase(Range::inin(ri->first.first(), ri->first.last()));
1181  }
1182 
1188  iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true) {
1189  if (new_range.empty())
1190  return end();
1191 
1192  if (make_hole) {
1193  erase(new_range);
1194  } else {
1195  iterator found = lower_bound(new_range.first());
1196  if (found!=end() && new_range.overlaps(found->first))
1197  return end();
1198  }
1199 
1200  /* Attempt to merge with a left and/or right value. */
1201  iterator left = new_range.first()>Range::minimum() ? find(new_range.first()-1) : end();
1202  if (left!=end() && new_range.abuts_gt(left->first) && new_value.merge(new_range, left->first, left->second)) {
1203  new_range = left->first.join(new_range);
1204  ranges.erase(left);
1205  }
1206  iterator right = new_range.last()<new_range.maximum() ? find(new_range.last()+1) : end();
1207  if (right!=end() && new_range.abuts_lt(right->first) && new_value.merge(new_range, right->first, right->second)) {
1208  new_range = new_range.join(right->first);
1209  ranges.erase(right);
1210  }
1211 
1212  iterator retval = ranges.insert(end(), std::make_pair(new_range, new_value));
1213 #ifdef RANGEMAP_CHECK
1214  check();
1215 #endif
1216  return retval;
1217  }
1218 
1220  void insert_ranges(const RangeMap &x, bool make_hole=true) {
1221  assert(&x!=this);
1222  insert_ranges(x.begin(), x.end(), make_hole);
1223  }
1224 
1227  void insert_ranges(const_iterator start, const_iterator stop, bool make_hole=true) {
1228  for (const_iterator ri=start; ri!=stop; ri++)
1229  insert(ri->first, ri->second, make_hole);
1230  }
1231 
1232  /**************************************************************************************************************************
1233  * Predicates
1234  **************************************************************************************************************************/
1235 public:
1236 
1238  bool overlaps(const RangeMap &x) const {
1239  return first_overlap(x)!=end();
1240  }
1241 
1244  bool overlaps(const Range &r) const {
1245  if (r.empty())
1246  return false;
1247  const_iterator found = lower_bound(r.first());
1248  return found!=end() && r.overlaps(found->first);
1249  }
1250 
1253  bool distinct(const Range &r) const {
1254  return !overlaps(r);
1255  }
1256 
1259  bool distinct(const RangeMap &x) const {
1260  return first_overlap(x)==end();
1261  }
1262 
1265  bool contains(Range need) const {
1266  if (need.empty())
1267  return true;
1268  const_iterator found=find(need.first());
1269  while (1) {
1270  if (found==end())
1271  return false;
1272  if (need.begins_before(found->first))
1273  return false;
1274  assert(need.overlaps(found->first));
1275  if (need.ends_before(found->first, false/*non-strict*/))
1276  return true;
1277  need = need.split_range_at(found->first.last()+1).second;
1278  ++found;
1279  }
1280  assert(!"should not be reached");
1281  return true;
1282  }
1283 
1286  bool contains(const RangeMap &x) const {
1287  if (x.empty())
1288  return true;
1289  for (const_iterator xi=x.begin(); xi!=x.end(); ++xi) {
1290  if (!contains(xi->first))
1291  return false;
1292  }
1293  return true;
1294  }
1295 
1296  /**************************************************************************************************************************
1297  * Comparisons
1298  **************************************************************************************************************************/
1299 public:
1300 
1305  iterator find_overlap(const RangeMap &x) {
1306  return find_overlap(begin(), end(), x);
1307  }
1308  const_iterator first_overlap(const RangeMap &x) const {
1309  return find_overlap(begin(), end(), x);
1310  }
1319  iterator find_overlap(iterator start, iterator stop, const RangeMap &x) {
1320  if (start==stop)
1321  return end();
1322 
1323  iterator ia = start;
1324  const_iterator ib = x.lower_bound(start->first.first());
1325  while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
1326  while (ia!=stop && ia->first.left_of(ib->first))
1327  ++ia;
1328  while (ib!=x.end() && ib->first.left_of(ia->first))
1329  ++ib;
1330  }
1331 
1332  return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first);
1333  }
1334  const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const {
1335  if (start==stop)
1336  return end();
1337 
1338  const_iterator ia = start;
1339  const_iterator ib = x.lower_bound(start->first.first());
1340  while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
1341  while (ia!=stop && ia->first.left_of(ib->first))
1342  ++ia;
1343  while (ib!=x.end() && ib->first.left_of(ia->first))
1344  ++ib;
1345  }
1346 
1347  return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first) ? ia : end();
1348  }
1351  /**************************************************************************************************************************
1352  * Operators
1353  **************************************************************************************************************************/
1354 public:
1355 
1357  template<class ResultMap>
1358  ResultMap invert() const {
1359  return invert_within<ResultMap>(Range::all());
1360  }
1361 
1364  template<class ResultMap>
1365  ResultMap invert_within(const Range &limits) const {
1366  ResultMap retval;
1367  if (limits.empty())
1368  return retval;
1369  typename Range::Value pending = limits.first();
1370  for (const_iterator ri=lower_bound(limits.first()); ri!=end() && !limits.left_of(ri->first); ++ri) {
1371  if (pending < ri->first.first())
1372  retval.insert(Range::inin(pending, ri->first.first()-1));
1373  pending = ri->first.last()+1;
1374  }
1375  if (pending <= limits.last())
1376  retval.insert(Range::inin(pending, limits.last()));
1377  if (!retval.empty())
1378  assert(retval.minmax().contained_in(limits, false));
1379  return retval;
1380  }
1381 
1384  RangeMap select_overlapping_ranges(const Range &selector) const {
1385  RangeMap retval;
1386  if (!selector.empty()) {
1387  for (const_iterator ri=lower_bound(selector.start()); ri!=end() && !selector.left_of(ri->first); ++ri) {
1388  if (selector.overlaps(ri->first))
1389  retval.insert(ri->first, ri->second);
1390  }
1391  }
1392  return retval;
1393  }
1394 
1395  /**************************************************************************************************************************
1396  * Debugging
1397  **************************************************************************************************************************/
1398 public:
1399 
1400  void check() const {
1401 // DQ (11/8/2011): Commented out as part of ROSE compiling this ROSE source code (EDG frontend complains about errors).
1402 #ifndef USE_ROSE
1403 #ifndef NDEBUG
1404 #define RANGEMAP_CHECK(EXPR) if (!(EXPR)) { \
1405  std::cerr <<"RangeMap::check() failed at r1=" <<r1 <<" r2=" <<r2 <<": " #EXPR "\n"; \
1406  std::cerr <<"Entire range map at point of failure:\n"; \
1407  print(std::cerr, " "); \
1408  assert(EXPR); \
1409  }
1410 
1411  for (const_iterator i1=begin(); i1!=end(); ++i1) {
1412  const Range &r1 = i1->first;
1413  const_iterator i2 = i1; ++i2;
1414  if (i2!=end()) {
1415  const Range &r2 = i2->first;
1416 
1417  RANGEMAP_CHECK(!r2.empty());
1418 
1419  RANGEMAP_CHECK(!r1.begins_with(r2));
1420  RANGEMAP_CHECK(!r2.begins_with(r1));
1421 
1422  RANGEMAP_CHECK(!r1.ends_with(r2));
1423  RANGEMAP_CHECK(!r2.ends_with(r1));
1424 
1425  RANGEMAP_CHECK(!r1.begins_after(r2, false));
1426  RANGEMAP_CHECK(!r1.begins_after(r2, true));
1427  RANGEMAP_CHECK(r2.begins_after(r1, false));
1428  RANGEMAP_CHECK(r2.begins_after(r1, true));
1429 
1430  RANGEMAP_CHECK(r1.begins_before(r2, false));
1431  RANGEMAP_CHECK(r1.begins_before(r2, true));
1432  RANGEMAP_CHECK(!r2.begins_before(r1, false));
1433  RANGEMAP_CHECK(!r2.begins_before(r1, true));
1434 
1435  RANGEMAP_CHECK(!r1.ends_after(r2, false));
1436  RANGEMAP_CHECK(!r1.ends_after(r2, true));
1437  RANGEMAP_CHECK(r2.ends_after(r1, false));
1438  RANGEMAP_CHECK(r2.ends_after(r1, true));
1439 
1440  RANGEMAP_CHECK(r1.ends_before(r2, false));
1441  RANGEMAP_CHECK(r1.ends_before(r2, true));
1442  RANGEMAP_CHECK(!r2.ends_before(r1, false));
1443  RANGEMAP_CHECK(!r2.ends_before(r1, true));
1444 
1445  RANGEMAP_CHECK(!r1.contains(r2, false));
1446  RANGEMAP_CHECK(!r1.contains(r2, true));
1447  RANGEMAP_CHECK(!r2.contains(r1, false));
1448  RANGEMAP_CHECK(!r2.contains(r1, true));
1449 
1450  RANGEMAP_CHECK(!r1.contained_in(r2, false));
1451  RANGEMAP_CHECK(!r1.contained_in(r2, true));
1452  RANGEMAP_CHECK(!r2.contained_in(r1, false));
1453  RANGEMAP_CHECK(!r2.contained_in(r1, true));
1454 
1455  RANGEMAP_CHECK(!r1.congruent(r2));
1456  RANGEMAP_CHECK(!r2.congruent(r1));
1457 
1458  RANGEMAP_CHECK(r1.left_of(r2));
1459  RANGEMAP_CHECK(!r2.left_of(r1));
1460 
1461  RANGEMAP_CHECK(!r1.right_of(r2));
1462  RANGEMAP_CHECK(r2.right_of(r1));
1463 
1464  RANGEMAP_CHECK(!r1.overlaps(r2));
1465  RANGEMAP_CHECK(!r2.overlaps(r1));
1466 
1467  RANGEMAP_CHECK(r1.distinct(r2));
1468  RANGEMAP_CHECK(r2.distinct(r1));
1469 
1470  RANGEMAP_CHECK(!r1.abuts_gt(r2)); // r1.abuts_lt(r2) is possible
1471  RANGEMAP_CHECK(!r2.abuts_lt(r1)); // r2.abuts_gt(r1) is possible
1472  }
1473  }
1474 #undef RANGEMAP_CHECK
1475 #endif
1476 #endif
1477  }
1478 
1480  void print(std::ostream &o) const {
1481  for (const_iterator ri=begin(); ri!=end(); ++ri) {
1482  std::ostringstream s;
1483  s <<ri->second;
1484  o <<(ri==begin()?"":", ") <<ri->first;
1485  if (!s.str().empty())
1486  o <<" {" <<s.str() <<"}";
1487  }
1488  }
1489 
1490  friend std::ostream& operator<<(std::ostream &o, const RangeMap &rmap) {
1491  rmap.print(o);
1492  return o;
1493  }
1494 
1495 };
1496 
1497 #endif
const_iterator best_fit(const typename Range::Value &size, const_iterator start) const
Find range with closest size.
Definition: rangemap.h:1016
const_iterator begin() const
First-item iterator.
Definition: rangemap.h:904
bool merge(const Range &, const Range &, const RangeMapVoid &)
Attempts to merge the specified range into this range.
Definition: rangemap.h:581
void truncate(const Range &, const typename Range::Value &)
Truncate the RangeMap value.
Definition: rangemap.h:564
bool distinct(const Range &r) const
Determines if a range map does not contain any part of the specified range.
Definition: rangemap.h:1253
bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value)
Called to merge two RangeMap values.
Definition: rangemap.h:640
ResultMap invert_within(const Range &limits) const
Create a range map that's the inverse of some other map.
Definition: rangemap.h:1365
iterator find(const typename Range::Value &addr)
Find the range containing specified value.
Definition: rangemap.h:950
const_iterator find(const typename Range::Value &addr) const
Find the range containing specified value.
Definition: rangemap.h:956
virtual Value get() const
Accessor for the value actually stored here.
Definition: rangemap.h:623
bool empty() const
Returns true if this RangeMap is empty.
Definition: rangemap.h:1054
Range(const Value &first, const Value &size)
Create a new range of specified size.
Definition: rangemap.h:73
const Value first() const
Accessor for the first value of a range.
Definition: rangemap.h:106
bool right_of(const Range &x) const
Is this range right of the argument range?
Definition: rangemap.h:366
bool ends_after(const Range &x, bool strict=true) const
Does this range end (strictly) after the end of another range?
Definition: rangemap.h:306
void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
Definition: rangemap.h:635
std::pair< Range, Range > Pair
A pair of ranges.
Definition: rangemap.h:53
iterator lower_bound(const typename Range::Value &addr)
Finds the first range ending above the specified value.
Definition: rangemap.h:968
Range()
Create an empty range.
Definition: rangemap.h:62
bool abuts_lt(const Range &x) const
Is this range immediately left of the argument range?
Definition: rangemap.h:395
reverse_iterator rend()
Returns a reverse iterator referring to the element right before the first element in the map...
Definition: rangemap.h:938
virtual Value get() const
Accessor for the value actually stored here.
Definition: rangemap.h:696
Scalar value type for a RangeMap.
Definition: rangemap.h:674
RangeMapNumeric(Value v)
Constructor creates object with specified value.
Definition: rangemap.h:616
A contiguous range of values.
Definition: rangemap.h:50
Range::Value max() const
Returns the maximum value in an extent map.
Definition: rangemap.h:1082
iterator best_fit(const typename Range::Value &size, iterator start)
Find range with closest size.
Definition: rangemap.h:1006
RangeMapValue(const Value &v)
Constructor creates object with specified value.
Definition: rangemap.h:683
void clear()
Make a range empty.
Definition: rangemap.h:255
iterator find_overlap(const RangeMap &x)
Find the first overlap between two RangeMap objects.
Definition: rangemap.h:1305
bool ends_before(const Range &x, bool strict=true) const
Does this range end (strictly) before the end of another range?
Definition: rangemap.h:315
iterator first_fit(const typename Range::Value &size, iterator start)
Find first range of larger size.
Definition: rangemap.h:1032
reverse_iterator rbegin()
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap...
Definition: rangemap.h:925
Value relaxed_first() const
Accessor for the first value of a range.
Definition: rangemap.h:115
RangeMap select_overlapping_ranges(const Range &selector) const
Select ranges overlapping selector range.
Definition: rangemap.h:1384
T Value
A type having the Range interface, used as keys in the underlying std::map.
Definition: rangemap.h:851
void print(std::ostream &o) const
Prints unformatted RangeMap on a single line.
Definition: rangemap.h:1480
Range::Value min() const
Returns the minimum value in an extent map.
Definition: rangemap.h:1076
RangeMapVoid split(const Range &, const typename Range::Value &)
Split a value into two parts.
Definition: rangemap.h:589
Range intersect(const Range &other) const
Intersection of two ranges.
Definition: rangemap.h:234
bool overlaps(const Range &r) const
Determines if a range map overlaps with a specified range.
Definition: rangemap.h:1244
virtual void set(const Value &v)
Accessor for the value actually stored here.
Definition: rangemap.h:693
void clear(bool notify=true)
Clears the map.
Definition: rangemap.h:1105
void erase(const Range &erase_range)
Erases the specified range from this map.
Definition: rangemap.h:1117
bool congruent(const Range &x) const
Are two ranges equal?
Definition: rangemap.h:346
void print(std::ostream &o) const
Print a RangeMap value.
Definition: rangemap.h:653
Value r_last
Last value in range.
Definition: rangemap.h:57
bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value)
Called to merge two RangeMap values.
Definition: rangemap.h:713
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
Definition: rangemap.h:1188
bool overlaps(const RangeMap &x) const
Determines if two range maps overlap.
Definition: rangemap.h:1238
Range::Value size() const
Returns the number of values represented by this RangeMap.
Definition: rangemap.h:1068
bool contains(const RangeMap &x) const
Determins if this range map contains all of some other range map.
Definition: rangemap.h:1286
bool begins_with(const Range &x) const
Do both ranges begin at the same place?
Definition: rangemap.h:270
size_t nranges() const
Returns the number of ranges in the range map.
Definition: rangemap.h:1060
void insert_ranges(const RangeMap &x, bool make_hole=true)
Insert one rangemap into another.
Definition: rangemap.h:1220
void erase_ranges(const OtherMap &other)
Erase ranges from this map.
Definition: rangemap.h:1177
static Range all()
Return a range that covers all possible values.
Definition: rangemap.h:422
void insert_ranges(const_iterator start, const_iterator stop, bool make_hole=true)
Insert part of one rangemap into another.
Definition: rangemap.h:1227
RangeMapNumeric split(const Range &my_range, typename Range::Value new_end)
Split a RangeMap value into two parts.
Definition: rangemap.h:646
const_iterator first_overlap(const RangeMap &x) const
Find the first overlap between two RangeMap objects.
Definition: rangemap.h:1308
RangeMapValue()
Constructor creates object whose underlying value is default constructed.
Definition: rangemap.h:680
void removing(const Range &)
Remove a value from a RangeMap.
Definition: rangemap.h:559
iterator find_prior(const typename Range::Value &addr)
Finds the last range starting at or below the specified value.
Definition: rangemap.h:979
void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
Definition: rangemap.h:630
const Value relaxed_last() const
Accessor for the last value of a range.
Definition: rangemap.h:134
iterator begin()
First-item iterator.
Definition: rangemap.h:901
virtual void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
Definition: rangemap.h:708
const_reverse_iterator rbegin() const
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap...
Definition: rangemap.h:928
const_reverse_iterator rend() const
Returns a reverse iterator referring to the element right before the first element in the map...
Definition: rangemap.h:941
Value size() const
Returns the number of values represented by the range.
Definition: rangemap.h:147
bool begins_before(const Range &x, bool strict=true) const
Does this range begin (strictly) before the beginning of another range?
Definition: rangemap.h:297
RangeMapNumeric()
Constructor creates object whose underlying value is zero.
Definition: rangemap.h:613
bool left_of(const Range &x) const
Is this range left of the argument range?
Definition: rangemap.h:356
bool empty() const
Returns true if this range is empty.
Definition: rangemap.h:249
bool contains(Range need) const
Determines if this range map contains all of the specified range.
Definition: rangemap.h:1265
const_iterator end() const
End-item iterator.
Definition: rangemap.h:916
The value attached to each range in this RangeMap.
Definition: rangemap.h:857
const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const
Find an overlap between two RangeMap objects.
Definition: rangemap.h:1334
void last(const Value &last)
Accessor for the last value of a range.
Definition: rangemap.h:127
friend std::ostream & operator<<(std::ostream &o, const RangeMapValue &x)
Print a RangeMap value.
Definition: rangemap.h:731
iterator end()
End-item iterator.
Definition: rangemap.h:913
bool begins_after(const Range &x, bool strict=true) const
Does this range begin (strictly) after the beginning of another range?
Definition: rangemap.h:288
const_iterator find_prior(const typename Range::Value &addr) const
Finds the last range starting at or below the specified value.
Definition: rangemap.h:989
Value type for a RangeMap with no useful data attached to the ranges.
Definition: rangemap.h:548
static Value maximum()
Return the maximum possible value represented by this range.
Definition: rangemap.h:417
Range(const Other &other)
Create a new range from a different range.
Definition: rangemap.h:85
void set(Value v)
Accessor for the value actually stored here.
Definition: rangemap.h:620
const_iterator first_fit(const typename Range::Value &size, const_iterator start)
Find first range of larger size.
Definition: rangemap.h:1039
Pair split_range_at(const Value &at) const
Split a range into two parts.
Definition: rangemap.h:184
void resize(const Value &new_size)
Sets the range size by adjusting the maximum value.
Definition: rangemap.h:162
RangeMap()
Create a new, empty map.
Definition: rangemap.h:880
Scalar value type for a RangeMap.
Definition: rangemap.h:607
Range minmax() const
Returns the range of values in this map.
Definition: rangemap.h:1088
bool distinct(const RangeMap &x) const
Determines if two range maps are distinct.
Definition: rangemap.h:1259
virtual void print(std::ostream &o) const
Print a RangeMap value.
Definition: rangemap.h:728
Value r_first
First value in range.
Definition: rangemap.h:56
void first(const Value &first)
Accessor for the first value of a range.
Definition: rangemap.h:103
bool contains(const Range &x, bool strict=false) const
Does this range contain the argument range?
Definition: rangemap.h:326
A container of ranges, somewhat like a set.
Definition: rangemap.h:848
iterator find_overlap(iterator start, iterator stop, const RangeMap &x)
Find an overlap between two RangeMap objects.
Definition: rangemap.h:1319
ResultMap invert() const
Create an inverse of a range map.
Definition: rangemap.h:1358
Range(const Value &first)
Create a new range of unit size.
Definition: rangemap.h:66
bool contained_in(const Range &x, bool strict=false) const
Is this range contained in the argument range?
Definition: rangemap.h:337
const_iterator lower_bound(const typename Range::Value &addr) const
Finds the first range ending above the specified value.
Definition: rangemap.h:971
bool abuts_gt(const Range &x) const
Is this range immediately right of the argument range?
Definition: rangemap.h:405
static Value minimum()
Return the minimum possible value represented by this range.
Definition: rangemap.h:412
static Range inin(const Value &v1, const Value &v2)
Create a new range by giving the first (inclusive) and last value (inclusive).
Definition: rangemap.h:92
RangeMap(const Other &other)
Create a new map from an existing map.
Definition: rangemap.h:884
bool ends_with(const Range &x) const
Do both ranges end at the same place?
Definition: rangemap.h:279
Range join(const Range &right) const
Joins two adjacent ranges.
Definition: rangemap.h:195
friend std::ostream & operator<<(std::ostream &o, const RangeMapNumeric &x)
Print a RangeMap value.
Definition: rangemap.h:656
std::vector< Range > erase(const Range &to_erase) const
Erase part of a range to return zero, one, or two new ranges.
Definition: rangemap.h:218
virtual void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
Definition: rangemap.h:703
bool overlaps(const Range &x) const
Does this range overlap with the argument range?
Definition: rangemap.h:375
bool distinct(const Range &x) const
Is this range non-overlapping with the argument range?
Definition: rangemap.h:385
const Value last() const
Accessor for the last value of a range.
Definition: rangemap.h:130
void relaxed_resize(const Value &new_size)
Sets the range size by adjusting the maximum value.
Definition: rangemap.h:171