|
| 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 union of two range sets. More...
|
| |
| ORanges | operator+ (const ORanges &rs) const |
| | Returns the union of two range sets. 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...
|
| |
| bound_type | hi () const |
| | Return the highest value in the set of ranges (the set cannot be empty) More...
|
| |
| size_t | count () const |
| | Return the number of items stored in ranges. 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 with 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...
|
| |
| bound_type | lo () const |
| | Return the lowest value in the set of ranges (the set cannot be empty) More...
|
| |
| bound_type | hi () const |
| | Return the highest value in the set of ranges (the set cannot be empty) 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 (enumerable, e.g. integers and enumerations).
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 (set union).
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 deleting ranges from the set with:
Open-ended ranges are more efficient than std::set when the values stored are adjacent (e.g. integers 2 and 3 are adjacent), since std::set stores values individually whereas open-ended ranges merges adjacent values into ranges. This lowers storage overhead and reduces insertion, deletion, and search time.
We can iterate over open-ended ranges. The iterator dereferences values are [lo,hi+1) pairs, i.e. lo = i->first and hi = i->second - 1.
Additional ORanges methods not defined by Ranges:
size_t count() returns the number of items stored in ranges, note that size() returns the number of ranges.
IMPORTANT:
The largest value that can be stored in an open-ended range of value type T is the maximum T-representable value minus 1. For example, the character range reflex::ORanges<char> holds values -128 to 126 and excludes 127.
- Pick sufficiently wide container value types T, e.g. int instead of char.
- Or the macro WITH_ORANGES_CLAMPED can be defined to use this library such that the maximum value is clamped to prevent overflow, e.g.
reflex::ORanges<char> ch = 127 is clamped to 126. However, this still excludes 127 from the range set.
- It is in principle possible to store and search for character 127 separately with insert(127) and find(127), respectively. Repeated insert(127) will add more 127 values, which is not desirable, since the unique set property no longer holds. Beware that insert(ch, 127) will not work. Also, value 127 cannot be deleted.
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)
Public Types inherited from reflex::Ranges< T >