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