5 #ifndef ROSE_RANGEMAP_H
6 #define ROSE_RANGEMAP_H
18 #ifndef __STDC_FORMAT_MACROS
19 #define __STDC_FORMAT_MACROS
53 typedef std::pair<Range, Range>
Pair;
63 : r_first(1), r_last(0) {}
67 : r_first(first), r_last(first) {}
74 : r_first(first), r_last(first+size-1) {
85 explicit Range(
const Other &other)
92 static Range inin(
const Value &v1,
const Value &v2) {
118 if (1==r_first-r_last)
167 r_last = r_first + new_size - 1;
176 r_last = r_first + new_size - 1;
189 return std::make_pair(left, right);
219 std::vector<Range> retval;
221 retval.push_back(*
this);
258 r_first = r_first + 1;
259 r_last = r_first - 1;
261 r_last = r_first - 2;
426 bool operator==(
const Range &x)
const {
429 bool operator!=(
const Range &x)
const {
433 void print(std::ostream &o)
const {
443 friend std::ostream& operator<<(std::ostream &o,
const Range &x) {
554 template<
class Other>
564 void truncate(
const Range&,
const typename Range::Value&) {
593 void print(std::ostream&)
const {}
594 friend std::ostream& operator<<(std::ostream &o,
const RangeMapVoid &x) {
606 template<
class R,
class T>
623 virtual Value
get()
const {
631 assert(!my_range.
empty());
635 void truncate(
const Range &my_range,
const typename Range::Value &new_end) {
636 assert(new_end>my_range.
first() && new_end<=my_range.
last());
641 assert(!my_range.
empty() && !other_range.
empty());
642 return get()==other_value.
get();
647 assert(my_range.
contains(Range(new_end)));
673 template<
class R,
class T>
693 virtual void set(
const Value &v) {
696 virtual Value
get()
const {
704 ASSERT_always_require(!my_range.
empty());
708 virtual void truncate(
const Range &my_range,
const typename Range::Value &new_end) {
709 ASSERT_always_require(new_end>my_range.
first() && new_end<=my_range.
last());
714 ASSERT_always_require(!my_range.
empty() && !other_range.
empty());
715 return get()==other_value.
get();
720 RangeMapValue split(
const Range &my_range,
const typename Range::Value &new_end) {
721 assert(my_range.
contains(Range(new_end)));
728 virtual void print(std::ostream &o)
const {
847 template<
class R,
class T=RangeMapVo
id<R> >
858 bool operator()(
const Range &a,
const Range &b)
const {
863 typedef std::pair<Range, Range> RangePair;
864 typedef std::pair<Range, Value> MapPair;
865 typedef std::map<Range, Value, RangeCompare> Map;
869 typedef typename Map::iterator iterator;
870 typedef typename Map::const_iterator const_iterator;
871 typedef typename Map::reverse_iterator reverse_iterator;
872 typedef typename Map::const_reverse_iterator const_reverse_iterator;
883 template<
class Other>
885 for (
typename Other::const_iterator ri=other.begin(); ri!=other.end(); ++ri) {
886 Range new_range(ri->first);
887 Value new_value(ri->second);
888 insert(new_range, new_value);
902 return ranges.begin();
905 return ranges.begin();
916 const_iterator
end()
const {
926 return ranges.rbegin();
929 return ranges.rbegin();
939 return ranges.rend();
941 const_reverse_iterator
rend()
const {
942 return ranges.rend();
950 iterator
find(
const typename Range::Value &addr) {
952 if (ei==
end() || Range(addr).left_of(ei->first))
956 const_iterator
find(
const typename Range::Value &addr)
const {
958 if (ei==
end() || Range(addr).left_of(ei->first))
969 return ranges.lower_bound(Range(addr));
971 const_iterator
lower_bound(
const typename Range::Value &addr)
const {
972 return ranges.lower_bound(Range(addr));
983 if (lb!=
end() && lb->first.begins_before(Range(addr),
false))
989 const_iterator
find_prior(
const typename Range::Value &addr)
const {
993 if (lb!=
end() && lb->first.begins_before(Range(addr),
false))
1007 iterator best =
end();
1008 for (iterator ri=start; ri!=
end(); ++ri) {
1009 if (ri->first.size()==
size)
1011 if (ri->first.size()>size && (best==
end() || ri->first.size()<best->first.size()))
1016 const_iterator
best_fit(
const typename Range::Value &
size, const_iterator start)
const {
1017 const_iterator best =
end();
1018 for (const_iterator ri=start; ri!=
end(); ++ri) {
1019 if (ri->first.size()==
size)
1021 if (ri->first.size()>size && (best==
end() || ri->first.size()<best->first.size()))
1033 for (iterator ri=start; ri!=
end(); ++ri) {
1034 if (ri->first.size()>=
size)
1039 const_iterator
first_fit(
const typename Range::Value &
size, const_iterator start) {
1040 for (const_iterator ri=start; ri!=
end(); ++ri) {
1041 if (ri->first.size()>=
size)
1055 return ranges.empty();
1061 return ranges.size();
1068 typename Range::Value
size()
const {
1069 typename Range::Value retval = 0;
1070 for (const_iterator ei=
begin(); ei!=
end(); ++ei)
1071 retval += ei->first.size();
1076 typename Range::Value
min()
const {
1078 return ranges.begin()->first.first();
1082 typename Range::Value
max()
const {
1084 return ranges.rbegin()->first.last();
1089 typename Range::Value lt=
min(), rt=
max();
1107 for (iterator ei=
begin(); ei!=
end(); ++ei)
1108 ei->second.removing(ei->first);
1126 if (erase_range.
empty())
1129 iterator erase_begin=
end();
1132 Range found_range = ei->first;
1133 Value &v = ei->second;
1134 if (erase_range.
contains(found_range)) {
1136 if (erase_begin==
end())
1139 }
else if (erase_range.
contained_in(found_range,
true)) {
1141 assert(erase_begin==
end());
1144 insertions[rt.second] = v.
split(found_range, rt.second.
first());
1145 RangePair lt = rt.first.split_range_at(erase_range.
first());
1147 insertions[lt.first] = v;
1148 }
else if (erase_range.
begins_after(found_range,
true)) {
1150 assert(erase_begin==
end());
1154 insertions[halves.first] = v;
1155 }
else if (erase_range.
ends_before(found_range,
true)) {
1157 if (erase_begin==
end())
1160 insertions[halves.second] = v.
split(found_range, halves.second.
first());
1166 if (erase_begin!=
end())
1167 ranges.erase(erase_begin, ei);
1168 ranges.insert(insertions.begin(), insertions.end());
1169 #ifdef RANGEMAP_CHECK
1176 template<
class OtherMap>
1178 assert((
const void*)&other!=(
const void*)
this);
1179 for (
typename OtherMap::const_iterator ri=other.begin(); ri!=other.end(); ++ri)
1188 iterator
insert(Range new_range, Value new_value=
Value(),
bool make_hole=
true) {
1189 if (new_range.
empty())
1196 if (found!=
end() && new_range.
overlaps(found->first))
1202 if (left!=
end() && new_range.
abuts_gt(left->first) && new_value.merge(new_range, left->
first, left->second)) {
1203 new_range = left->
first.join(new_range);
1207 if (right!=
end() && new_range.
abuts_lt(right->first) && new_value.merge(new_range, right->
first, right->second)) {
1208 new_range = new_range.
join(right->first);
1209 ranges.
erase(right);
1212 iterator retval = ranges.insert(
end(), std::make_pair(new_range, new_value));
1213 #ifdef RANGEMAP_CHECK
1227 void insert_ranges(const_iterator start, const_iterator stop,
bool make_hole=
true) {
1228 for (const_iterator ri=start; ri!=stop; ri++)
1229 insert(ri->first, ri->second, make_hole);
1268 const_iterator found=
find(need.
first());
1274 assert(need.
overlaps(found->first));
1280 assert(!
"should not be reached");
1289 for (const_iterator xi=x.
begin(); xi!=x.
end(); ++xi) {
1323 iterator ia = start;
1324 const_iterator ib = x.
lower_bound(start->first.first());
1325 while (ia!=stop && ib!=x.
end() && ia->first.distinct(ib->first)) {
1326 while (ia!=stop && ia->first.left_of(ib->first))
1328 while (ib!=x.
end() && ib->first.left_of(ia->first))
1332 return ia!=stop && ib!=x.
end() && ia->first.overlaps(ib->first);
1338 const_iterator ia = start;
1339 const_iterator ib = x.
lower_bound(start->first.first());
1340 while (ia!=stop && ib!=x.
end() && ia->first.distinct(ib->first)) {
1341 while (ia!=stop && ia->first.left_of(ib->first))
1343 while (ib!=x.
end() && ib->first.left_of(ia->first))
1347 return ia!=stop && ib!=x.
end() && ia->first.overlaps(ib->first) ? ia :
end();
1357 template<
class ResultMap>
1359 return invert_within<ResultMap>(
Range::all());
1364 template<
class ResultMap>
1369 typename Range::Value pending = limits.
first();
1371 if (pending < ri->first.first())
1372 retval.insert(
Range::inin(pending, ri->first.first()-1));
1373 pending = ri->first.last()+1;
1375 if (pending <= limits.
last())
1377 if (!retval.empty())
1378 assert(retval.minmax().contained_in(limits,
false));
1386 if (!selector.
empty()) {
1387 for (const_iterator ri=
lower_bound(selector.start()); ri!=
end() && !selector.
left_of(ri->first); ++ri) {
1389 retval.
insert(ri->first, ri->second);
1400 void check()
const {
1404 #define RANGEMAP_CHECK(EXPR) if (!(EXPR)) { \
1405 std::cerr <<"RangeMap::check() failed at r1=" <<r1 <<" r2=" <<r2 <<": " #EXPR "\n"; \
1406 std::cerr <<"Entire range map at point of failure:\n"; \
1407 print(std::cerr, " "); \
1411 for (const_iterator i1=
begin(); i1!=
end(); ++i1) {
1412 const Range &r1 = i1->first;
1413 const_iterator i2 = i1; ++i2;
1415 const Range &r2 = i2->first;
1417 RANGEMAP_CHECK(!r2.
empty());
1445 RANGEMAP_CHECK(!r1.
contains(r2,
false));
1446 RANGEMAP_CHECK(!r1.
contains(r2,
true));
1447 RANGEMAP_CHECK(!r2.
contains(r1,
false));
1448 RANGEMAP_CHECK(!r2.
contains(r1,
true));
1458 RANGEMAP_CHECK(r1.
left_of(r2));
1459 RANGEMAP_CHECK(!r2.
left_of(r1));
1474 #undef RANGEMAP_CHECK
1481 for (const_iterator ri=
begin(); ri!=
end(); ++ri) {
1482 std::ostringstream s;
1484 o <<(ri==
begin()?
"":
", ") <<ri->first;
1485 if (!s.str().empty())
1486 o <<
" {" <<s.str() <<
"}";
1490 friend std::ostream& operator<<(std::ostream &o,
const RangeMap &rmap) {
const_iterator best_fit(const typename Range::Value &size, const_iterator start) const
Find range with closest size.
const_iterator begin() const
First-item iterator.
bool merge(const Range &, const Range &, const RangeMapVoid &)
Attempts to merge the specified range into this range.
void truncate(const Range &, const typename Range::Value &)
Truncate the RangeMap value.
bool distinct(const Range &r) const
Determines if a range map does not contain any part of the specified range.
bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value)
Called to merge two RangeMap values.
ResultMap invert_within(const Range &limits) const
Create a range map that's the inverse of some other map.
iterator find(const typename Range::Value &addr)
Find the range containing specified value.
const_iterator find(const typename Range::Value &addr) const
Find the range containing specified value.
virtual Value get() const
Accessor for the value actually stored here.
bool empty() const
Returns true if this RangeMap is empty.
Range(const Value &first, const Value &size)
Create a new range of specified size.
const Value first() const
Accessor for the first value of a range.
bool right_of(const Range &x) const
Is this range right of the argument range?
bool ends_after(const Range &x, bool strict=true) const
Does this range end (strictly) after the end of another range?
void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
std::pair< Range, Range > Pair
A pair of ranges.
iterator lower_bound(const typename Range::Value &addr)
Finds the first range ending above the specified value.
Range()
Create an empty range.
bool abuts_lt(const Range &x) const
Is this range immediately left of the argument range?
reverse_iterator rend()
Returns a reverse iterator referring to the element right before the first element in the map...
virtual Value get() const
Accessor for the value actually stored here.
Scalar value type for a RangeMap.
RangeMapNumeric(Value v)
Constructor creates object with specified value.
A contiguous range of values.
Range::Value max() const
Returns the maximum value in an extent map.
iterator best_fit(const typename Range::Value &size, iterator start)
Find range with closest size.
RangeMapValue(const Value &v)
Constructor creates object with specified value.
void clear()
Make a range empty.
iterator find_overlap(const RangeMap &x)
Find the first overlap between two RangeMap objects.
bool ends_before(const Range &x, bool strict=true) const
Does this range end (strictly) before the end of another range?
iterator first_fit(const typename Range::Value &size, iterator start)
Find first range of larger size.
reverse_iterator rbegin()
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap...
Value relaxed_first() const
Accessor for the first value of a range.
RangeMap select_overlapping_ranges(const Range &selector) const
Select ranges overlapping selector range.
T Value
A type having the Range interface, used as keys in the underlying std::map.
void print(std::ostream &o) const
Prints unformatted RangeMap on a single line.
Range::Value min() const
Returns the minimum value in an extent map.
RangeMapVoid split(const Range &, const typename Range::Value &)
Split a value into two parts.
Range intersect(const Range &other) const
Intersection of two ranges.
bool overlaps(const Range &r) const
Determines if a range map overlaps with a specified range.
virtual void set(const Value &v)
Accessor for the value actually stored here.
void clear(bool notify=true)
Clears the map.
void erase(const Range &erase_range)
Erases the specified range from this map.
bool congruent(const Range &x) const
Are two ranges equal?
void print(std::ostream &o) const
Print a RangeMap value.
Value r_last
Last value in range.
bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value)
Called to merge two RangeMap values.
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
bool overlaps(const RangeMap &x) const
Determines if two range maps overlap.
Range::Value size() const
Returns the number of values represented by this RangeMap.
bool contains(const RangeMap &x) const
Determins if this range map contains all of some other range map.
bool begins_with(const Range &x) const
Do both ranges begin at the same place?
size_t nranges() const
Returns the number of ranges in the range map.
void insert_ranges(const RangeMap &x, bool make_hole=true)
Insert one rangemap into another.
void erase_ranges(const OtherMap &other)
Erase ranges from this map.
static Range all()
Return a range that covers all possible values.
void insert_ranges(const_iterator start, const_iterator stop, bool make_hole=true)
Insert part of one rangemap into another.
RangeMapNumeric split(const Range &my_range, typename Range::Value new_end)
Split a RangeMap value into two parts.
const_iterator first_overlap(const RangeMap &x) const
Find the first overlap between two RangeMap objects.
RangeMapValue()
Constructor creates object whose underlying value is default constructed.
void removing(const Range &)
Remove a value from a RangeMap.
iterator find_prior(const typename Range::Value &addr)
Finds the last range starting at or below the specified value.
void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
const Value relaxed_last() const
Accessor for the last value of a range.
iterator begin()
First-item iterator.
virtual void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
const_reverse_iterator rbegin() const
Returns a reverse iterator referring to the last item of the map, the rend() iterator if the RangeMap...
const_reverse_iterator rend() const
Returns a reverse iterator referring to the element right before the first element in the map...
Value size() const
Returns the number of values represented by the range.
bool begins_before(const Range &x, bool strict=true) const
Does this range begin (strictly) before the beginning of another range?
RangeMapNumeric()
Constructor creates object whose underlying value is zero.
bool left_of(const Range &x) const
Is this range left of the argument range?
bool empty() const
Returns true if this range is empty.
bool contains(Range need) const
Determines if this range map contains all of the specified range.
const_iterator end() const
End-item iterator.
The value attached to each range in this RangeMap.
const_iterator find_overlap(const_iterator start, const_iterator stop, const RangeMap &x) const
Find an overlap between two RangeMap objects.
void last(const Value &last)
Accessor for the last value of a range.
friend std::ostream & operator<<(std::ostream &o, const RangeMapValue &x)
Print a RangeMap value.
iterator end()
End-item iterator.
bool begins_after(const Range &x, bool strict=true) const
Does this range begin (strictly) after the beginning of another range?
const_iterator find_prior(const typename Range::Value &addr) const
Finds the last range starting at or below the specified value.
Value type for a RangeMap with no useful data attached to the ranges.
static Value maximum()
Return the maximum possible value represented by this range.
Range(const Other &other)
Create a new range from a different range.
void set(Value v)
Accessor for the value actually stored here.
const_iterator first_fit(const typename Range::Value &size, const_iterator start)
Find first range of larger size.
Pair split_range_at(const Value &at) const
Split a range into two parts.
void resize(const Value &new_size)
Sets the range size by adjusting the maximum value.
RangeMap()
Create a new, empty map.
Scalar value type for a RangeMap.
Range minmax() const
Returns the range of values in this map.
bool distinct(const RangeMap &x) const
Determines if two range maps are distinct.
virtual void print(std::ostream &o) const
Print a RangeMap value.
Value r_first
First value in range.
void first(const Value &first)
Accessor for the first value of a range.
bool contains(const Range &x, bool strict=false) const
Does this range contain the argument range?
A container of ranges, somewhat like a set.
iterator find_overlap(iterator start, iterator stop, const RangeMap &x)
Find an overlap between two RangeMap objects.
ResultMap invert() const
Create an inverse of a range map.
Range(const Value &first)
Create a new range of unit size.
bool contained_in(const Range &x, bool strict=false) const
Is this range contained in the argument range?
const_iterator lower_bound(const typename Range::Value &addr) const
Finds the first range ending above the specified value.
bool abuts_gt(const Range &x) const
Is this range immediately right of the argument range?
static Value minimum()
Return the minimum possible value represented by this range.
static Range inin(const Value &v1, const Value &v2)
Create a new range by giving the first (inclusive) and last value (inclusive).
RangeMap(const Other &other)
Create a new map from an existing map.
bool ends_with(const Range &x) const
Do both ranges end at the same place?
Range join(const Range &right) const
Joins two adjacent ranges.
friend std::ostream & operator<<(std::ostream &o, const RangeMapNumeric &x)
Print a RangeMap value.
std::vector< Range > erase(const Range &to_erase) const
Erase part of a range to return zero, one, or two new ranges.
virtual void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
bool overlaps(const Range &x) const
Does this range overlap with the argument range?
bool distinct(const Range &x) const
Is this range non-overlapping with the argument range?
const Value last() const
Accessor for the last value of a range.
void relaxed_resize(const Value &new_size)
Sets the range size by adjusting the maximum value.