|
typedef T | bound_type |
| Type of the bounds. More...
|
|
typedef std::set< std::pair< T, T >, range_compare< T > > | container_type |
| Synonym type defining the base class container std::set. More...
|
|
typedef container_type::value_type | value_type |
| Synonym type defining the base class container std::set::value_type. More...
|
|
typedef container_type::key_compare | key_compare |
| Synonym type defining the key/value comparison std::set::key_compare. More...
|
|
typedef container_type::value_compare | value_compare |
|
typedef container_type::iterator | iterator |
| Synonym type defining the base class container std::set::iterator. More...
|
|
typedef container_type::const_iterator | const_iterator |
| Synonym type defining the base class container std::set::const_iterator. More...
|
|
typedef T | bound_type |
| Type of the bounds. More...
|
|
typedef std::set< std::pair< T, T >, range_compare< T > > | container_type |
| Synonym type defining the base class container std::set. More...
|
|
typedef container_type::value_type | value_type |
| Synonym type defining the base class container std::set::value_type. More...
|
|
typedef container_type::key_compare | key_compare |
| Synonym type defining the key/value comparison std::set::key_compare. More...
|
|
typedef container_type::value_compare | value_compare |
|
typedef container_type::iterator | iterator |
| Synonym type defining the base class container std::set::iterator. More...
|
|
typedef container_type::const_iterator | const_iterator |
| Synonym type defining the base class container std::set::iterator. More...
|
|
|
| ORanges () |
| Construct an empty range. More...
|
|
| ORanges (const value_type &r) |
| Construct a copy of a range [lo,hi]. More...
|
|
| ORanges (const bound_type &lo, const bound_type &hi) |
| Construct a range [lo,hi]. More...
|
|
| ORanges (const bound_type &val) |
| Construct a singleton range [val,val]. More...
|
|
std::pair< iterator, bool > | insert (const bound_type &lo, const bound_type &hi) |
| Update ranges to include range [lo,hi] by merging overlapping and adjacent ranges into one range. More...
|
|
std::pair< iterator, bool > | insert (const bound_type &val) |
| Update ranges to include range [val,val] by merging overlapping and adjacent ranges into one range. More...
|
|
bool | erase (const bound_type &lo, const bound_type &hi) |
| Update ranges by deleting the given range [lo,hi]. More...
|
|
bool | erase (const bound_type &val) |
| Update ranges by deleting the given range [val,val]. More...
|
|
const_iterator | find (const bound_type &lo, const bound_type &hi) const |
| Find the first range that overlaps the given range. More...
|
|
const_iterator | find (const bound_type &val) const |
| Find the range that includes the given value. More...
|
|
ORanges & | operator-= (const ORanges &rs) |
| Update ranges to remove ranges rs, has lower complexity than repeating erase(). More...
|
|
ORanges & | operator&= (const ORanges &rs) |
| Update ranges to intersect the ranges of the given range set. More...
|
|
ORanges | operator- (const ORanges &rs) const |
| Returns the difference of two open-ended range sets. More...
|
|
ORanges | operator& (const ORanges &rs) const |
| Returns the intersection of two open-ended range sets. More...
|
|
bool | intersects (const ORanges &rs) const |
| Return true if this set of ranges intersects with ranges rs, i.e. this set has at least one range [lo',hi'] that overlaps with a range [lo,hi] in rs such that lo <= hi' and lo' <= hi. More...
|
|
| Ranges () |
| Construct an empty range. More...
|
|
| Ranges (const value_type &r) |
| Construct a copy of a range [lo,hi]. More...
|
|
| Ranges (const bound_type &lo, const bound_type &hi) |
| Construct a range [lo,hi]. More...
|
|
| Ranges (const bound_type &val) |
| Construct a singleton range [val,val]. More...
|
|
std::pair< iterator, bool > | insert (const value_type &r) |
| Update ranges to include range [lo,hi] by merging overlapping ranges into one range. More...
|
|
std::pair< iterator, bool > | insert (const bound_type &lo, const bound_type &hi) |
| Update ranges to include range [lo,hi] by merging overlapping ranges into one range. More...
|
|
std::pair< iterator, bool > | insert (const bound_type &val) |
| Update ranges to include the range [val,val]. More...
|
|
const_iterator | find (const bound_type &lo, const bound_type &hi) const |
| Find the first range [lo',hi'] that overlaps the given range [lo,hi], i.e. lo <= hi' and lo' <= hi. More...
|
|
const_iterator | find (const bound_type &val) const |
| Find the range [lo',hi'] that includes the given value val, i.e. lo' <= val <= hi'. More...
|
|
Ranges & | operator|= (const Ranges &rs) |
| Update ranges to insert the given range set, where this method has lower complexity than iterating insert() for each range in rs. More...
|
|
Ranges & | operator+= (const Ranges &rs) |
| Update ranges to insert the ranges of the given range set, same as Ranges::operator|=(rs). More...
|
|
Ranges & | operator&= (const Ranges &rs) |
| Update ranges to intersect the ranges of the given range set. More...
|
|
Ranges | operator| (const Ranges &rs) const |
| Returns the union of two range sets. More...
|
|
Ranges | operator+ (const Ranges &rs) const |
| Returns the union of two range sets, same as Ranges::operator|(rs). More...
|
|
Ranges | operator& (const Ranges &rs) const |
| Returns the intersection of two range sets. More...
|
|
bool | operator< (const Ranges &rs) const |
| True if this range set is lexicographically less than range set rs. More...
|
|
bool | operator> (const Ranges &rs) const |
| True if this range set is lexicographically greater than range set rs. More...
|
|
bool | operator<= (const Ranges &rs) const |
| True if this range set is lexicographically less or equal to range set rs. More...
|
|
bool | operator>= (const Ranges &rs) const |
| True if this range set is lexicographically greater or equal to range set rs. More...
|
|
bool | any () const |
| Return true if this set of ranges contains at least one range, i.e. is not empty. More...
|
|
bool | intersects (const Ranges &rs) const |
| Return true if this set of ranges intersects with ranges rs, i.e. this set has at least one range [lo',hi'] that overlaps with a range [lo,hi] in rs such that lo <= hi' and lo' <= hi. More...
|
|
bool | contains (const Ranges &rs) const |
| Return true if this set of ranges contains all ranges in rs, i.e. rs is a subset of this set which means that for each range [lo,hi] in rs, there is a range [lo',hi'] such that lo' <= lo and hi <= hi'. More...
|
|
template<typename T>
class reflex::ORanges< T >
RE/flex ORanges (open-ended, ordinal value range) template class.
The ORanges class is an optimization of the ranges class for ordinal types, i.e. types with the property that values can be counted and have a +
(plus) operator.
The optimization merges adjacent ranges. Two ranges [a,b]
and [c,d]
are adjacent when b+1=c
. It is safe to merge adjacent ranges over values of an ordinal type, because [a,b]<+>[b+1,c]=[a,c]
with <+>
representing range merging.
By storing open-ended ranges [lo,hi+1)
in the ranges class container, adjacent ranges are merged automatically by the fact that the bounds of open-ended adjacent ranges overlap.
In addition to the methods inherited from the Range base class, open-ended ranges can be updated by erasing ranges:
Open-ended ranges are more efficient than std::set
when values are adjacent, since std::set
stores values individually whereas open-ended ranges merges adjacent values thereby reducing storage overhead and saving search time.
Example:
ints = 0;
std::cout << "Set of " << ints.size() << " open-ended ranges:" << std::endl;
std::cout << "[" << i->first << "," << i->second << ")" << std::endl;
if (ints.
find(200) != ints.end())
std::cout << "200 is in the set" << std::endl;
if (ints.
find(99) == ints.end())
std::cout << "99 is not in the set" << std::endl;
if (ints.
find(401) == ints.end())
std::cout << "401 is not in the set" << std::endl;
std::cout << "[" << i->first << "," << i->second << ")" << std::endl;
Output:
Set of 2 open-ended ranges: [0,1) [100,401) 200 is in the set 99 is not in the set 401 is not in the set [0,1) [100,250) [351,401)