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;
85 explicit Range(
const Other &other)
92 static Range inin(
const Value &v1,
const Value &v2) {
106 const Value
first()
const {
130 const Value
last()
const {
162 void resize(
const Value &new_size) {
189 return std::make_pair(left, right);
218 std::vector<Range>
erase(
const Range &to_erase)
const {
219 std::vector<Range> retval;
221 retval.push_back(*
this);
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>
560 assert(!my_range.
empty());
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());
597 void print(std::ostream &o)
const {}
598 friend std::ostream& operator<<(std::ostream &o,
const RangeMapVoid &x) {
610 template<
class R,
class T>
627 virtual Value
get() const {
635 assert(!my_range.
empty());
639 void truncate(
const Range &my_range,
const typename Range::Value &new_end) {
640 assert(new_end>my_range.
first() && new_end<=my_range.
last());
645 assert(!my_range.
empty() && !other_range.
empty());
657 void print(std::ostream &o)
const {
677 template<
class R,
class T>
697 virtual void set(
const Value &v) {
700 virtual Value
get()
const {
708 assert(!my_range.
empty());
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());
718 assert(!my_range.
empty() && !other_range.
empty());
732 virtual void print(std::ostream &o)
const {
851 template<
class R,
class T=RangeMapVo
id<R> >
862 bool operator()(
const Range &a,
const Range &b)
const {
867 typedef std::pair<Range, Range> RangePair;
868 typedef std::pair<Range, Value> MapPair;
869 typedef std::map<Range, Value, RangeCompare>
Map;
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;
887 template<
class Other>
888 explicit RangeMap(
const Other &other) {
889 for (
typename Other::const_iterator ri=other.begin(); ri!=other.end(); ++ri) {
891 Value new_value(ri->second);
892 insert(new_range, new_value);
906 return ranges.begin();
908 const_iterator
begin()
const {
909 return ranges.begin();
920 const_iterator
end()
const {
929 reverse_iterator
rbegin() {
930 return ranges.rbegin();
932 const_reverse_iterator
rbegin()
const {
933 return ranges.rbegin();
942 reverse_iterator
rend() {
943 return ranges.rend();
945 const_reverse_iterator
rend()
const {
946 return ranges.rend();
954 iterator
find(
const typename Range::Value &addr) {
960 const_iterator
find(
const typename Range::Value &addr)
const {
972 iterator
lower_bound(
const typename Range::Value &addr) {
973 return ranges.lower_bound(
Range(addr));
975 const_iterator
lower_bound(
const typename Range::Value &addr)
const {
976 return ranges.lower_bound(
Range(addr));
983 iterator
find_prior(
const typename Range::Value &addr) {
987 if (lb!=
end() && lb->first.begins_before(
Range(addr),
false))
993 const_iterator
find_prior(
const typename Range::Value &addr)
const {
997 if (lb!=
end() && lb->first.begins_before(
Range(addr),
false))
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)
1015 if (ri->first.size()>
size && (best==
end() || ri->first.size()<best->first.size()))
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)
1025 if (ri->first.size()>
size && (best==
end() || ri->first.size()<best->first.size()))
1036 iterator
first_fit(
const typename Range::Value &
size, iterator start) {
1037 for (iterator ri=start; ri!=
end(); ++ri) {
1043 const_iterator
first_fit(
const typename Range::Value &
size, const_iterator start) {
1044 for (const_iterator ri=start; ri!=
end(); ++ri) {
1058 bool empty()
const {
1059 return ranges.empty();
1065 return ranges.size();
1072 typename Range::Value
size()
const {
1073 typename Range::Value retval = 0;
1075 retval += ei->first.size();
1080 typename Range::Value
min()
const {
1082 return ranges.begin()->first.first();
1086 typename Range::Value
max()
const {
1088 return ranges.rbegin()->first.last();
1093 typename Range::Value lt=
min(), rt=
max();
1109 void clear(
bool notify=
true) {
1112 ei->second.removing(ei->first);
1130 if (erase_range.
empty())
1133 iterator erase_begin=
end();
1137 Value &v = ei->second;
1138 if (erase_range.
contains(found_range)) {
1140 if (erase_begin==
end())
1142 v.removing(found_range);
1143 }
else if (erase_range.
contained_in(found_range,
true)) {
1145 assert(erase_begin==
end());
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)) {
1154 assert(erase_begin==
end());
1157 v.truncate(found_range, erase_range.
first());
1158 insertions[halves.first] = v;
1159 }
else if (erase_range.
ends_before(found_range,
true)) {
1161 if (erase_begin==
end())
1164 insertions[halves.second] = v.split(found_range, halves.second.first());
1165 v.removing(halves.first);
1170 if (erase_begin!=
end())
1171 ranges.erase(erase_begin, ei);
1172 ranges.insert(insertions.begin(), insertions.end());
1173 #ifdef RANGEMAP_CHECK
1180 template<
class OtherMap>
1182 assert((
const void*)&other!=(
const void*)
this);
1183 for (
typename OtherMap::const_iterator ri=other.begin(); ri!=other.end(); ++ri)
1193 if (new_range.
empty())
1200 if (found!=
end() && new_range.
overlaps(found->first))
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);
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);
1216 iterator retval = ranges.insert(
end(), std::make_pair(new_range, new_value));
1217 #ifdef RANGEMAP_CHECK
1231 void insert_ranges(const_iterator start, const_iterator stop,
bool make_hole=
true) {
1232 for (const_iterator ri=start; ri!=stop; ri++)
1272 const_iterator found=
find(need.
first());
1278 assert(need.
overlaps(found->first));
1284 assert(!
"should not be reached");
1293 for (const_iterator xi=x.
begin(); xi!=x.
end(); ++xi) {
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))
1332 while (ib!=x.
end() && ib->first.left_of(ia->first))
1336 return ia!=stop && ib!=x.
end() && ia->first.overlaps(ib->first);
1338 const_iterator
find_overlap(const_iterator start, const_iterator stop,
const RangeMap &x)
const {
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))
1347 while (ib!=x.
end() && ib->first.left_of(ia->first))
1351 return ia!=stop && ib!=x.
end() && ia->first.overlaps(ib->first) ? ia :
end();
1361 template<
class ResultMap>
1362 ResultMap
invert()
const {
1363 return invert_within<ResultMap>(
Range::all());
1368 template<
class ResultMap>
1373 typename Range::Value pending = limits.
first();
1375 if (pending < ri->first.first())
1376 retval.insert(
Range::inin(pending, ri->first.first()-1));
1377 pending = ri->first.last()+1;
1379 if (pending <= limits.
last())
1381 if (!retval.empty())
1382 assert(retval.minmax().contained_in(limits,
false));
1391 for (const_iterator ri=
lower_bound(selector.start()); ri!=
end() && !selector.
left_of(ri->first); ++ri) {
1393 retval.
insert(ri->first, ri->second);
1404 void check()
const {
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, " "); \
1415 for (const_iterator i1=
begin(); i1!=
end(); ++i1) {
1417 const_iterator i2 = i1; ++i2;
1421 RANGEMAP_CHECK(!r2.
empty());
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));
1462 RANGEMAP_CHECK(r1.
left_of(r2));
1463 RANGEMAP_CHECK(!r2.
left_of(r1));
1478 #undef RANGEMAP_CHECK
1484 void print(std::ostream &o)
const {
1485 for (const_iterator ri=
begin(); ri!=
end(); ++ri) {
1486 std::ostringstream s;
1488 o <<(ri==
begin()?
"":
", ") <<ri->first;
1489 if (!s.str().empty())
1490 o <<
" {" <<s.str() <<
"}";
1494 friend std::ostream& operator<<(std::ostream &o,
const RangeMap &rmap) {
bool left_of(const Range &x) const
Is this range left of the argument range?
void print(std::ostream &o) const
Print a RangeMap value.
void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
size_t nranges() const
Returns the number of ranges in the range map.
virtual Value get() const
Accessor for the value actually stored here.
bool empty() const
Returns true if this RangeMap is empty.
void relaxed_resize(const Value &new_size)
Sets the range size by adjusting the maximum value.
static Value minimum()
Return the minimum possible value represented by this range.
const_iterator first_overlap(const RangeMap &x) const
Find the first overlap between two RangeMap objects.
virtual void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
void erase_ranges(const OtherMap &other)
Erase ranges from this map.
ResultMap invert_within(const Range &limits) const
Create a range map that's the inverse of some other map.
Value size() const
Returns the number of values represented by the range.
void clear(bool notify=true)
Clears the map.
virtual Value get() const
Accessor for the value actually stored here.
bool contains(const Range &x, bool strict=false) const
Does this range contain the argument range?
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.
bool begins_before(const Range &x, bool strict=true) const
Does this range begin (strictly) before the beginning of another range?
void truncate(const Range &my_range, const typename Range::Value &new_end)
Truncate the RangeMap value.
bool merge(const Range &, const Range &, const RangeMapVoid &)
Attempts to merge the specified range into this range.
bool abuts_lt(const Range &x) const
Is this range immediately left of the argument range?
Scalar value type for a RangeMap.
bool ends_before(const Range &x, bool strict=true) const
Does this range end (strictly) before the end of another range?
Value r_last
Last value in range.
iterator end()
End-item iterator.
Range intersect(const Range &other) const
Intersection of two ranges.
Range()
Create an empty range.
Range minmax() const
Returns the range of values in this map.
bool congruent(const Range &x) const
Are two ranges equal?
bool distinct(const Range &r) const
Determines if a range map does not contain any part of the specified range.
RangeMap()
Create a new, empty map.
RangeMapNumeric()
Constructor creates object whose underlying value is zero.
RangeMap select_overlapping_ranges(const Range &selector) const
Select ranges overlapping selector range.
const Value relaxed_last() const
Accessor for the last value of a range.
A container of ranges, somewhat like a set.
void clear()
Make a range empty.
bool begins_after(const Range &x, bool strict=true) const
Does this range begin (strictly) after the beginning of another range?
const Value first() const
Accessor for the first value of a range.
RangeMapNumeric split(const Range &my_range, typename Range::Value new_end)
Split a RangeMap value into two parts.
iterator find_prior(const typename Range::Value &addr)
Finds the last range starting at or below the specified value.
Range::Value max() const
Returns the maximum value in an extent map.
RangeMapVoid split(const Range &my_range, const typename Range::Value &new_end)
Split a value into two parts.
Range::Value min() const
Returns the minimum value in an extent map.
static Range all()
Return a range that covers all possible values.
virtual void set(const Value &v)
Accessor for the value actually stored here.
void insert_ranges(const RangeMap &x, bool make_hole=true)
Insert one rangemap into another.
iterator insert(Range new_range, Value new_value=Value(), bool make_hole=true)
Insert a range/value pair into the map.
iterator lower_bound(const typename Range::Value &addr)
Finds the first range ending above the specified value.
bool merge(const Range &my_range, const Range &other_range, RangeMapNumeric other_value)
Called to merge two RangeMap values.
iterator best_fit(const typename Range::Value &size, iterator start)
Find range with closest size.
bool distinct(const Range &x) const
Is this range non-overlapping with the argument range?
reverse_iterator rend()
Returns a reverse iterator referring to the element right before the first element in the map,...
bool begins_with(const Range &x) const
Do both ranges begin at the same place?
const Value last() const
Accessor for the last value of a range.
bool overlaps(const Range &x) const
Does this range overlap with the argument range?
friend std::ostream & operator<<(std::ostream &o, const RangeMapValue &x)
Print a RangeMap value.
RangeMapValue()
Constructor creates object whose underlying value is default constructed.
friend std::ostream & operator<<(std::ostream &o, const RangeMapNumeric &x)
Print a RangeMap value.
iterator find_overlap(const RangeMap &x)
Find the first overlap between two RangeMap objects.
Range::Value size() const
Returns the number of values represented by this RangeMap.
The value attached to each range in this RangeMap.
bool contained_in(const Range &x, bool strict=false) const
Is this range contained in the argument range?
static Value maximum()
Return the maximum possible value represented by this range.
std::vector< Range > erase(const Range &to_erase) const
Erase part of a range to return zero, one, or two new ranges.
void resize(const Value &new_size)
Sets the range size by adjusting the maximum value.
Scalar value type for a RangeMap.
bool right_of(const Range &x) const
Is this range right of the argument range?
A contiguous range of values.
bool merge(const Range &my_range, const Range &other_range, const RangeMapValue &other_value)
Called to merge two RangeMap values.
bool contains(Range need) const
Determines if this range map contains all of the specified range.
T Value
A type having the Range interface, used as keys in the underlying std::map.
Value type for a RangeMap with no useful data attached to the ranges.
bool empty() const
Returns true if this range is empty.
Pair split_range_at(const Value &at) const
Split a range into two parts.
bool ends_with(const Range &x) const
Do both ranges end at the same place?
Extends std::map with methods that return optional values.
virtual void print(std::ostream &o) const
Print a RangeMap value.
void last(const Value &last)
Accessor for the last value of a range.
Range join(const Range &right) const
Joins two adjacent ranges.
void removing(const Range &my_range)
Called when this value is being removed from a RangeMap.
void set(Value v)
Accessor for the value actually stored here.
iterator begin()
First-item iterator.
iterator find(const typename Range::Value &addr)
Find the range containing specified value.
static Range inin(const Value &v1, const Value &v2)
Create a new range by giving the first (inclusive) and last value (inclusive).
Value r_first
First value in range.
void first(const Value &first)
Accessor for the first value of a range.
void erase(const Range &erase_range)
Erases the specified range from this map.
bool overlaps(const RangeMap &x) const
Determines if two range maps overlap.
virtual void truncate(const Range &my_range, const typename Range::Value &new_end)
Called when removing part of a value from a RangeMap.
void removing(const Range &my_range)
Remove a value from a RangeMap.
ResultMap invert() const
Create an inverse of a range map.
void print(std::ostream &o) const
Prints unformatted RangeMap on a single line.
iterator first_fit(const typename Range::Value &size, iterator start)
Find first range of larger size.
bool ends_after(const Range &x, bool strict=true) const
Does this range end (strictly) after the end of another range?
bool abuts_gt(const Range &x) const
Is this range immediately right of the argument range?
std::pair< Range, Range > Pair
A pair of ranges.