ROSE  0.9.10.89
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 &my_range) {
560  assert(!my_range.empty());
561  }
562 
566  void truncate(const Range &my_range, const typename Range::Value &new_end) {
567  assert(new_end>my_range.first() && new_end<=my_range.last());
568  }
569 
584  bool merge(const Range &/*my_range*/, const Range &/*other_range*/, const RangeMapVoid &/*other_value*/) {
585  return true;
586  }
587 
592  RangeMapVoid split(const Range &my_range, const typename Range::Value &new_end) {
593  assert(my_range.contains(Range(new_end)));
594  return RangeMapVoid();
595  }
596 
597  void print(std::ostream &o) const {}
598  friend std::ostream& operator<<(std::ostream &o, const RangeMapVoid &x) {
599  x.print(o);
600  return o;
601  }
602 };
603 
604 /******************************************************************************************************************************
605  * RangeMap numeric values
606  ******************************************************************************************************************************/
607 
610 template<class R, class T>
611 class RangeMapNumeric /*final*/ {
612 public:
613  typedef R Range;
614  typedef T Value;
615 
617  RangeMapNumeric(): value(0) {}
618 
620  RangeMapNumeric(Value v): value(v) {} // implicit
621 
624  void set(Value v) /*final*/ {
625  value = v;
626  }
627  virtual Value get() const /*final*/ {
628  return value;
629  }
634  void removing(const Range &my_range) /*final*/ {
635  assert(!my_range.empty());
636  }
637 
639  void truncate(const Range &my_range, const typename Range::Value &new_end) /*final*/ {
640  assert(new_end>my_range.first() && new_end<=my_range.last());
641  }
642 
644  bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value) /*final*/ {
645  assert(!my_range.empty() && !other_range.empty());
646  return get()==other_value.get();
647  }
648 
650  RangeMapNumeric split(const Range &my_range, typename Range::Value new_end) /*final*/ {
651  assert(my_range.contains(Range(new_end)));
652  return *this;
653  }
654 
657  void print(std::ostream &o) const /*final*/ {
658  o <<value;
659  }
660  friend std::ostream& operator<<(std::ostream &o, const RangeMapNumeric &x) {
661  x.print(o);
662  return o;
663  }
666 private:
667  Value value;
668 };
669 
670 /******************************************************************************************************************************
671  * RangeMap simple values
672  ******************************************************************************************************************************/
673 
677 template<class R, class T>
679 public:
680  typedef R Range;
681  typedef T Value;
682 
685 
687  RangeMapValue(const Value &v) { // implicit
688  value = v;
689  }
690 
691  /* This class often serves as a base class, so we have some virtual methods. */
692  virtual ~RangeMapValue() {}
693 
694 
697  virtual void set(const Value &v) {
698  value = v;
699  }
700  virtual Value get() const {
701  return value;
702  }
707  virtual void removing(const Range &my_range) {
708  assert(!my_range.empty());
709  }
710 
712  virtual void truncate(const Range &my_range, const typename Range::Value &new_end) {
713  assert(new_end>my_range.first() && new_end<=my_range.last());
714  }
715 
717  bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value) {
718  assert(!my_range.empty() && !other_range.empty());
719  return get()==other_value.get();
720  }
721 
722 #if 0 /* Must be implemented in the subclass due to return type. */
723 
724  RangeMapValue split(const Range &my_range, const typename Range::Value &new_end) {
725  assert(my_range.contains(Range(new_end)));
726  return *this;
727  }
728 #endif
729 
732  virtual void print(std::ostream &o) const {
733  o <<value;
734  }
735  friend std::ostream& operator<<(std::ostream &o, const RangeMapValue &x) {
736  x.print(o);
737  return o;
738  }
741 protected:
742  Value value;
743 };
744 
745 /******************************************************************************************************************************
746  * RangeMap<>
747  ******************************************************************************************************************************/
748 
851 template<class R, class T=RangeMapVoid<R> >
852 class RangeMap {
853 public:
854  typedef R Range;
855  typedef T Value;
857 protected:
858  /* The keys of the underlying map are sorted by their last value rather than beginning value. This allows us to use the
859  * map's lower_bound() method to find the range to which an address might belong. Since the ranges in the map are
860  * non-overlapping, sorting by ending address has the same effect as sorting by starting address. */
861  struct RangeCompare {
862  bool operator()(const Range &a, const Range &b) const {
863  return a.last() < b.last();
864  }
865  };
866 
867  typedef std::pair<Range, Range> RangePair;
868  typedef std::pair<Range, Value> MapPair;
869  typedef std::map<Range, Value, RangeCompare> Map;
870  Map ranges;
871 
872 public:
873  typedef typename Map::iterator iterator;
874  typedef typename Map::const_iterator const_iterator;
875  typedef typename Map::reverse_iterator reverse_iterator;
876  typedef typename Map::const_reverse_iterator const_reverse_iterator;
877 
878  /**************************************************************************************************************************
879  * Constructors
880  **************************************************************************************************************************/
881 public:
882 
884  RangeMap() {}
885 
887  template<class Other>
888  explicit RangeMap(const Other &other) {
889  for (typename Other::const_iterator ri=other.begin(); ri!=other.end(); ++ri) {
890  Range new_range(ri->first);
891  Value new_value(ri->second);
892  insert(new_range, new_value);
893  }
894  }
895 
896  /**************************************************************************************************************************
897  * Iterators and searching
898  **************************************************************************************************************************/
899 public:
900 
905  iterator begin() {
906  return ranges.begin();
907  }
908  const_iterator begin() const {
909  return ranges.begin();
910  }
917  iterator end() {
918  return ranges.end();
919  }
920  const_iterator end() const {
921  return ranges.end();
922  }
929  reverse_iterator rbegin() {
930  return ranges.rbegin();
931  }
932  const_reverse_iterator rbegin() const {
933  return ranges.rbegin();
934  }
942  reverse_iterator rend() {
943  return ranges.rend();
944  }
945  const_reverse_iterator rend() const {
946  return ranges.rend();
947  }
954  iterator find(const typename Range::Value &addr) {
955  iterator ei = lower_bound(addr);
956  if (ei==end() || Range(addr).left_of(ei->first))
957  return end();
958  return ei;
959  }
960  const_iterator find(const typename Range::Value &addr) const {
961  const_iterator ei = lower_bound(addr);
962  if (ei==end() || Range(addr).left_of(ei->first))
963  return end();
964  return ei;
965  }
972  iterator lower_bound(const typename Range::Value &addr) {
973  return ranges.lower_bound(Range(addr));
974  }
975  const_iterator lower_bound(const typename Range::Value &addr) const {
976  return ranges.lower_bound(Range(addr));
977  }
983  iterator find_prior(const typename Range::Value &addr) {
984  if (empty())
985  return end();
986  iterator lb = lower_bound(addr);
987  if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
988  return lb;
989  if (lb==begin())
990  return end();
991  return --lb;
992  }
993  const_iterator find_prior(const typename Range::Value &addr) const {
994  if (empty())
995  return end();
996  const_iterator lb = lower_bound(addr);
997  if (lb!=end() && lb->first.begins_before(Range(addr), false/*non-strict*/))
998  return lb;
999  if (lb==begin())
1000  return end();
1001  return --lb;
1002  }
1010  iterator best_fit(const typename Range::Value &size, iterator start) {
1011  iterator best = end();
1012  for (iterator ri=start; ri!=end(); ++ri) {
1013  if (ri->first.size()==size)
1014  return ri;
1015  if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
1016  best = ri;
1017  }
1018  return best;
1019  }
1020  const_iterator best_fit(const typename Range::Value &size, const_iterator start) const {
1021  const_iterator best = end();
1022  for (const_iterator ri=start; ri!=end(); ++ri) {
1023  if (ri->first.size()==size)
1024  return ri;
1025  if (ri->first.size()>size && (best==end() || ri->first.size()<best->first.size()))
1026  best = ri;
1027  }
1028  return best;
1029  }
1036  iterator first_fit(const typename Range::Value &size, iterator start) {
1037  for (iterator ri=start; ri!=end(); ++ri) {
1038  if (ri->first.size()>=size)
1039  return ri;
1040  }
1041  return end();
1042  }
1043  const_iterator first_fit(const typename Range::Value &size, const_iterator start) {
1044  for (const_iterator ri=start; ri!=end(); ++ri) {
1045  if (ri->first.size()>=size)
1046  return ri;
1047  }
1048  return end();
1049  }
1052  /**************************************************************************************************************************
1053  * Capacity
1054  **************************************************************************************************************************/
1055 public:
1056 
1058  bool empty() const {
1059  return ranges.empty();
1060  }
1061 
1064  size_t nranges() const {
1065  return ranges.size();
1066  }
1067 
1072  typename Range::Value size() const {
1073  typename Range::Value retval = 0;
1074  for (const_iterator ei=begin(); ei!=end(); ++ei)
1075  retval += ei->first.size();
1076  return retval;
1077  }
1078 
1080  typename Range::Value min() const {
1081  assert(!empty());
1082  return ranges.begin()->first.first();
1083  }
1084 
1086  typename Range::Value max() const {
1087  assert(!empty());
1088  return ranges.rbegin()->first.last();
1089  }
1090 
1092  Range minmax() const {
1093  typename Range::Value lt=min(), rt=max();
1094  return Range::inin(lt, rt);
1095  }
1096 
1097  /**************************************************************************************************************************
1098  * Low-level support functions
1099  **************************************************************************************************************************/
1100 protected:
1101 
1102  /**************************************************************************************************************************
1103  * Modifiers
1104  **************************************************************************************************************************/
1105 public:
1106 
1109  void clear(bool notify=true) {
1110  if (notify) {
1111  for (iterator ei=begin(); ei!=end(); ++ei)
1112  ei->second.removing(ei->first);
1113  }
1114  ranges.clear();
1115  }
1116 
1121  void erase(const Range &erase_range) {
1122  /* This loop figures out what needs to be removed and calls the elements' removing(), truncate(), etc. methods but does
1123  * not actually erase them from the underlying map yet. We must not erase them yet because the std::map::erase()
1124  * method doesn't return any iterator. Instead, we create a list (via an iterator range) of elements that will need to
1125  * be erased from the underlying map.
1126  *
1127  * This loop also creates a list of items that need to be inserted into the underlying map. Even though the
1128  * std::map::insert() can return an iterator, we can't call it inside the loop because then our erasure iterators will
1129  * become invalid. */
1130  if (erase_range.empty())
1131  return;
1132  Map insertions;
1133  iterator erase_begin=end();
1134  iterator ei;
1135  for (ei=lower_bound(erase_range.first()); ei!=end() && !erase_range.left_of(ei->first); ++ei) {
1136  Range found_range = ei->first;
1137  Value &v = ei->second;
1138  if (erase_range.contains(found_range)) {
1139  /* Erase entire found range. */
1140  if (erase_begin==end())
1141  erase_begin = ei;
1142  v.removing(found_range);
1143  } else if (erase_range.contained_in(found_range, true/*strict*/)) {
1144  /* Erase middle of found range. */
1145  assert(erase_begin==end());
1146  erase_begin = ei;
1147  RangePair rt = found_range.split_range_at(erase_range.last()+1);
1148  insertions[rt.second] = v.split(found_range, rt.second.first());
1149  RangePair lt = rt.first.split_range_at(erase_range.first());
1150  v.truncate(rt.first, erase_range.first());
1151  insertions[lt.first] = v;
1152  } else if (erase_range.begins_after(found_range, true/*strict*/)) {
1153  /* Erase right part of found range. */
1154  assert(erase_begin==end());
1155  erase_begin = ei;
1156  RangePair halves = found_range.split_range_at(erase_range.first());
1157  v.truncate(found_range, erase_range.first());
1158  insertions[halves.first] = v;
1159  } else if (erase_range.ends_before(found_range, true/*strict*/)) {
1160  /* Erase left part of found range. */
1161  if (erase_begin==end())
1162  erase_begin = ei;
1163  RangePair halves = found_range.split_range_at(erase_range.last()+1);
1164  insertions[halves.second] = v.split(found_range, halves.second.first());
1165  v.removing(halves.first);
1166  }
1167  }
1168 
1169  /* Inserting is easy here because we already know that no merging is necessary. */
1170  if (erase_begin!=end())
1171  ranges.erase(erase_begin, ei);
1172  ranges.insert(insertions.begin(), insertions.end());
1173 #ifdef RANGEMAP_CHECK
1174  check();
1175 #endif
1176  }
1177 
1180  template<class OtherMap>
1181  void erase_ranges(const OtherMap &other) {
1182  assert((const void*)&other!=(const void*)this);
1183  for (typename OtherMap::const_iterator ri=other.begin(); ri!=other.end(); ++ri)
1184  erase(Range::inin(ri->first.first(), ri->first.last()));
1185  }
1186 
1192  iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true) {
1193  if (new_range.empty())
1194  return end();
1195 
1196  if (make_hole) {
1197  erase(new_range);
1198  } else {
1199  iterator found = lower_bound(new_range.first());
1200  if (found!=end() && new_range.overlaps(found->first))
1201  return end();
1202  }
1203 
1204  /* Attempt to merge with a left and/or right value. */
1205  iterator left = new_range.first()>Range::minimum() ? find(new_range.first()-1) : end();
1206  if (left!=end() && new_range.abuts_gt(left->first) && new_value.merge(new_range, left->first, left->second)) {
1207  new_range = left->first.join(new_range);
1208  ranges.erase(left);
1209  }
1210  iterator right = new_range.last()<new_range.maximum() ? find(new_range.last()+1) : end();
1211  if (right!=end() && new_range.abuts_lt(right->first) && new_value.merge(new_range, right->first, right->second)) {
1212  new_range = new_range.join(right->first);
1213  ranges.erase(right);
1214  }
1215 
1216  iterator retval = ranges.insert(end(), std::make_pair(new_range, new_value));
1217 #ifdef RANGEMAP_CHECK
1218  check();
1219 #endif
1220  return retval;
1221  }
1222 
1224  void insert_ranges(const RangeMap &x, bool make_hole=true) {
1225  assert(&x!=this);
1226  insert_ranges(x.begin(), x.end(), make_hole);
1227  }
1228 
1231  void insert_ranges(const_iterator start, const_iterator stop, bool make_hole=true) {
1232  for (const_iterator ri=start; ri!=stop; ri++)
1233  insert(ri->first, ri->second, make_hole);
1234  }
1235 
1236  /**************************************************************************************************************************
1237  * Predicates
1238  **************************************************************************************************************************/
1239 public:
1240 
1242  bool overlaps(const RangeMap &x) const {
1243  return first_overlap(x)!=end();
1244  }
1245 
1248  bool overlaps(const Range &r) const {
1249  if (r.empty())
1250  return false;
1251  const_iterator found = lower_bound(r.first());
1252  return found!=end() && r.overlaps(found->first);
1253  }
1254 
1257  bool distinct(const Range &r) const {
1258  return !overlaps(r);
1259  }
1260 
1263  bool distinct(const RangeMap &x) const {
1264  return first_overlap(x)==end();
1265  }
1266 
1269  bool contains(Range need) const {
1270  if (need.empty())
1271  return true;
1272  const_iterator found=find(need.first());
1273  while (1) {
1274  if (found==end())
1275  return false;
1276  if (need.begins_before(found->first))
1277  return false;
1278  assert(need.overlaps(found->first));
1279  if (need.ends_before(found->first, false/*non-strict*/))
1280  return true;
1281  need = need.split_range_at(found->first.last()+1).second;
1282  ++found;
1283  }
1284  assert(!"should not be reached");
1285  return true;
1286  }
1287 
1290  bool contains(const RangeMap &x) const {
1291  if (x.empty())
1292  return true;
1293  for (const_iterator xi=x.begin(); xi!=x.end(); ++xi) {
1294  if (!contains(xi->first))
1295  return false;
1296  }
1297  return true;
1298  }
1299 
1300  /**************************************************************************************************************************
1301  * Comparisons
1302  **************************************************************************************************************************/
1303 public:
1304 
1309  iterator find_overlap(const RangeMap &x) {
1310  return find_overlap(begin(), end(), x);
1311  }
1312  const_iterator first_overlap(const RangeMap &x) const {
1313  return find_overlap(begin(), end(), x);
1314  }
1323  iterator find_overlap(iterator start, iterator stop, const RangeMap &x) {
1324  if (start==stop)
1325  return end();
1326 
1327  iterator ia = start;
1328  const_iterator ib = x.lower_bound(start->first.first());
1329  while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
1330  while (ia!=stop && ia->first.left_of(ib->first))
1331  ++ia;
1332  while (ib!=x.end() && ib->first.left_of(ia->first))
1333  ++ib;
1334  }
1335 
1336  return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first);
1337  }
1338  const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const {
1339  if (start==stop)
1340  return end();
1341 
1342  const_iterator ia = start;
1343  const_iterator ib = x.lower_bound(start->first.first());
1344  while (ia!=stop && ib!=x.end() && ia->first.distinct(ib->first)) {
1345  while (ia!=stop && ia->first.left_of(ib->first))
1346  ++ia;
1347  while (ib!=x.end() && ib->first.left_of(ia->first))
1348  ++ib;
1349  }
1350 
1351  return ia!=stop && ib!=x.end() && ia->first.overlaps(ib->first) ? ia : end();
1352  }
1355  /**************************************************************************************************************************
1356  * Operators
1357  **************************************************************************************************************************/
1358 public:
1359 
1361  template<class ResultMap>
1362  ResultMap invert() const {
1363  return invert_within<ResultMap>(Range::all());
1364  }
1365 
1368  template<class ResultMap>
1369  ResultMap invert_within(const Range &limits) const {
1370  ResultMap retval;
1371  if (limits.empty())
1372  return retval;
1373  typename Range::Value pending = limits.first();
1374  for (const_iterator ri=lower_bound(limits.first()); ri!=end() && !limits.left_of(ri->first); ++ri) {
1375  if (pending < ri->first.first())
1376  retval.insert(Range::inin(pending, ri->first.first()-1));
1377  pending = ri->first.last()+1;
1378  }
1379  if (pending <= limits.last())
1380  retval.insert(Range::inin(pending, limits.last()));
1381  if (!retval.empty())
1382  assert(retval.minmax().contained_in(limits, false));
1383  return retval;
1384  }
1385 
1388  RangeMap select_overlapping_ranges(const Range &selector) const {
1389  RangeMap retval;
1390  if (!selector.empty()) {
1391  for (const_iterator ri=lower_bound(selector.start()); ri!=end() && !selector.left_of(ri->first); ++ri) {
1392  if (selector.overlaps(ri->first))
1393  retval.insert(ri->first, ri->second);
1394  }
1395  }
1396  return retval;
1397  }
1398 
1399  /**************************************************************************************************************************
1400  * Debugging
1401  **************************************************************************************************************************/
1402 public:
1403 
1404  void check() const {
1405 // DQ (11/8/2011): Commented out as part of ROSE compiling this ROSE source code (EDG frontend complains about errors).
1406 #ifndef USE_ROSE
1407 #ifndef NDEBUG
1408 #define RANGEMAP_CHECK(EXPR) if (!(EXPR)) { \
1409  std::cerr <<"RangeMap::check() failed at r1=" <<r1 <<" r2=" <<r2 <<": " #EXPR "\n"; \
1410  std::cerr <<"Entire range map at point of failure:\n"; \
1411  print(std::cerr, " "); \
1412  assert(EXPR); \
1413  }
1414 
1415  for (const_iterator i1=begin(); i1!=end(); ++i1) {
1416  const Range &r1 = i1->first;
1417  const_iterator i2 = i1; ++i2;
1418  if (i2!=end()) {
1419  const Range &r2 = i2->first;
1420 
1421  RANGEMAP_CHECK(!r2.empty());
1422 
1423  RANGEMAP_CHECK(!r1.begins_with(r2));
1424  RANGEMAP_CHECK(!r2.begins_with(r1));
1425 
1426  RANGEMAP_CHECK(!r1.ends_with(r2));
1427  RANGEMAP_CHECK(!r2.ends_with(r1));
1428 
1429  RANGEMAP_CHECK(!r1.begins_after(r2, false));
1430  RANGEMAP_CHECK(!r1.begins_after(r2, true));
1431  RANGEMAP_CHECK(r2.begins_after(r1, false));
1432  RANGEMAP_CHECK(r2.begins_after(r1, true));
1433 
1434  RANGEMAP_CHECK(r1.begins_before(r2, false));
1435  RANGEMAP_CHECK(r1.begins_before(r2, true));
1436  RANGEMAP_CHECK(!r2.begins_before(r1, false));
1437  RANGEMAP_CHECK(!r2.begins_before(r1, true));
1438 
1439  RANGEMAP_CHECK(!r1.ends_after(r2, false));
1440  RANGEMAP_CHECK(!r1.ends_after(r2, true));
1441  RANGEMAP_CHECK(r2.ends_after(r1, false));
1442  RANGEMAP_CHECK(r2.ends_after(r1, true));
1443 
1444  RANGEMAP_CHECK(r1.ends_before(r2, false));
1445  RANGEMAP_CHECK(r1.ends_before(r2, true));
1446  RANGEMAP_CHECK(!r2.ends_before(r1, false));
1447  RANGEMAP_CHECK(!r2.ends_before(r1, true));
1448 
1449  RANGEMAP_CHECK(!r1.contains(r2, false));
1450  RANGEMAP_CHECK(!r1.contains(r2, true));
1451  RANGEMAP_CHECK(!r2.contains(r1, false));
1452  RANGEMAP_CHECK(!r2.contains(r1, true));
1453 
1454  RANGEMAP_CHECK(!r1.contained_in(r2, false));
1455  RANGEMAP_CHECK(!r1.contained_in(r2, true));
1456  RANGEMAP_CHECK(!r2.contained_in(r1, false));
1457  RANGEMAP_CHECK(!r2.contained_in(r1, true));
1458 
1459  RANGEMAP_CHECK(!r1.congruent(r2));
1460  RANGEMAP_CHECK(!r2.congruent(r1));
1461 
1462  RANGEMAP_CHECK(r1.left_of(r2));
1463  RANGEMAP_CHECK(!r2.left_of(r1));
1464 
1465  RANGEMAP_CHECK(!r1.right_of(r2));
1466  RANGEMAP_CHECK(r2.right_of(r1));
1467 
1468  RANGEMAP_CHECK(!r1.overlaps(r2));
1469  RANGEMAP_CHECK(!r2.overlaps(r1));
1470 
1471  RANGEMAP_CHECK(r1.distinct(r2));
1472  RANGEMAP_CHECK(r2.distinct(r1));
1473 
1474  RANGEMAP_CHECK(!r1.abuts_gt(r2)); // r1.abuts_lt(r2) is possible
1475  RANGEMAP_CHECK(!r2.abuts_lt(r1)); // r2.abuts_gt(r1) is possible
1476  }
1477  }
1478 #undef RANGEMAP_CHECK
1479 #endif
1480 #endif
1481  }
1482 
1484  void print(std::ostream &o) const {
1485  for (const_iterator ri=begin(); ri!=end(); ++ri) {
1486  std::ostringstream s;
1487  s <<ri->second;
1488  o <<(ri==begin()?"":", ") <<ri->first;
1489  if (!s.str().empty())
1490  o <<" {" <<s.str() <<"}";
1491  }
1492  }
1493 
1494  friend std::ostream& operator<<(std::ostream &o, const RangeMap &rmap) {
1495  rmap.print(o);
1496  return o;
1497  }
1498 
1499 };
1500 
1501 #endif
const_iterator best_fit(const typename Range::Value &size, const_iterator start) const
Find range with closest size.
Definition: rangemap.h:1020
const_iterator begin() const
First-item iterator.
Definition: rangemap.h:908
bool merge(const Range &, const Range &, const RangeMapVoid &)
Attempts to merge the specified range into this range.
Definition: rangemap.h:584
bool distinct(const Range &r) const
Determines if a range map does not contain any part of the specified range.
Definition: rangemap.h:1257
bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value)
Called to merge two RangeMap values.
Definition: rangemap.h:644
ResultMap invert_within(const Range &limits) const
Create a range map that's the inverse of some other map.
Definition: rangemap.h:1369
iterator find(const typename Range::Value &addr)
Find the range containing specified value.
Definition: rangemap.h:954
const_iterator find(const typename Range::Value &addr) const
Find the range containing specified value.
Definition: rangemap.h:960
virtual Value get() const
Accessor for the value actually stored here.
Definition: rangemap.h:627
bool empty() const
Returns true if this RangeMap is empty.
Definition: rangemap.h:1058
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:639
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:972
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:942
virtual Value get() const
Accessor for the value actually stored here.
Definition: rangemap.h:700
Scalar value type for a RangeMap.
Definition: rangemap.h:678
RangeMapNumeric(Value v)
Constructor creates object with specified value.
Definition: rangemap.h:620
A contiguous range of values.
Definition: rangemap.h:50
Range::Value max() const
Returns the maximum value in an extent map.
Definition: rangemap.h:1086
iterator best_fit(const typename Range::Value &size, iterator start)
Find range with closest size.
Definition: rangemap.h:1010
RangeMapValue(const Value &v)
Constructor creates object with specified value.
Definition: rangemap.h:687
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:1309
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:1036
reverse_iterator rbegin()
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap...
Definition: rangemap.h:929
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:1388
T Value
A type having the Range interface, used as keys in the underlying std::map.
Definition: rangemap.h:855
void print(std::ostream &o) const
Prints unformatted RangeMap on a single line.
Definition: rangemap.h:1484
Range::Value min() const
Returns the minimum value in an extent map.
Definition: rangemap.h:1080
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:1248
virtual void set(const Value &v)
Accessor for the value actually stored here.
Definition: rangemap.h:697
void clear(bool notify=true)
Clears the map.
Definition: rangemap.h:1109
void erase(const Range &erase_range)
Erases the specified range from this map.
Definition: rangemap.h:1121
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:657
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:717
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
Definition: rangemap.h:1192
bool overlaps(const RangeMap &x) const
Determines if two range maps overlap.
Definition: rangemap.h:1242
Range::Value size() const
Returns the number of values represented by this RangeMap.
Definition: rangemap.h:1072
bool contains(const RangeMap &x) const
Determins if this range map contains all of some other range map.
Definition: rangemap.h:1290
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:1064
void insert_ranges(const RangeMap &x, bool make_hole=true)
Insert one rangemap into another.
Definition: rangemap.h:1224
void erase_ranges(const OtherMap &other)
Erase ranges from this map.
Definition: rangemap.h:1181
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:1231
RangeMapNumeric split(const Range &my_range, typename Range::Value new_end)
Split a RangeMap value into two parts.
Definition: rangemap.h:650
const_iterator first_overlap(const RangeMap &x) const
Find the first overlap between two RangeMap objects.
Definition: rangemap.h:1312
RangeMapValue()
Constructor creates object whose underlying value is default constructed.
Definition: rangemap.h:684
iterator find_prior(const typename Range::Value &addr)
Finds the last range starting at or below the specified value.
Definition: rangemap.h:983
void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
Definition: rangemap.h:634
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:905
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:712
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:932
const_reverse_iterator rend() const
Returns a reverse iterator referring to the element right before the first element in the map...
Definition: rangemap.h:945
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:617
RangeMapVoid split(const Range &my_range, const typename Range::Value &new_end)
Split a value into two parts.
Definition: rangemap.h:592
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:1269
const_iterator end() const
End-item iterator.
Definition: rangemap.h:920
The value attached to each range in this RangeMap.
Definition: rangemap.h:861
const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const
Find an overlap between two RangeMap objects.
Definition: rangemap.h:1338
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:735
void removing(const Range &my_range)
Remove a value from a RangeMap.
Definition: rangemap.h:559
iterator end()
End-item iterator.
Definition: rangemap.h:917
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
void truncate(const Range &my_range, const typename Range::Value &new_end)
Truncate the RangeMap value.
Definition: rangemap.h:566
const_iterator find_prior(const typename Range::Value &addr) const
Finds the last range starting at or below the specified value.
Definition: rangemap.h:993
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:624
const_iterator first_fit(const typename Range::Value &size, const_iterator start)
Find first range of larger size.
Definition: rangemap.h:1043
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:884
Scalar value type for a RangeMap.
Definition: rangemap.h:611
Range minmax() const
Returns the range of values in this map.
Definition: rangemap.h:1092
bool distinct(const RangeMap &x) const
Determines if two range maps are distinct.
Definition: rangemap.h:1263
virtual void print(std::ostream &o) const
Print a RangeMap value.
Definition: rangemap.h:732
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:852
iterator find_overlap(iterator start, iterator stop, const RangeMap &x)
Find an overlap between two RangeMap objects.
Definition: rangemap.h:1323
ResultMap invert() const
Create an inverse of a range map.
Definition: rangemap.h:1362
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:975
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:888
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:660
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:707
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