|
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) |
|
std::pair< iterator, bool > | insert (const bound_type &val) |
|
bool | erase (const bound_type &lo, const bound_type &hi) |
|
bool | erase (const bound_type &val) |
|
const_iterator | find (const bound_type &lo, const bound_type &hi) const |
| < upper bound More...
|
|
const_iterator | find (const bound_type &val) const |
| < value to search for More...
|
|
ORanges & | operator-= (const ORanges &rs) |
|
ORanges & | operator&= (const ORanges &rs) |
|
ORanges | operator- (const ORanges &rs) const |
| < ranges More...
|
|
ORanges | operator& (const ORanges &rs) const |
| < ranges to intersect More...
|
|
bool | intersects (const ORanges &rs) const |
| < 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) |
|
std::pair< iterator, bool > | insert (const bound_type &lo, const bound_type &hi) |
|
std::pair< iterator, bool > | insert (const bound_type &val) |
|
const_iterator | find (const bound_type &lo, const bound_type &hi) const |
| < upper bound More...
|
|
const_iterator | find (const bound_type &val) const |
| < value to search for More...
|
|
Ranges & | operator|= (const Ranges &rs) |
|
Ranges & | operator+= (const Ranges &rs) |
|
Ranges & | operator&= (const Ranges &rs) |
|
Ranges | operator| (const Ranges &rs) const |
| < ranges to merge More...
|
|
Ranges | operator+ (const Ranges &rs) const |
| < ranges to merge More...
|
|
Ranges | operator& (const Ranges &rs) const |
| < ranges to intersect More...
|
|
bool | any () const |
| TODO. More...
|
|
bool | intersects (const Ranges &rs) const |
| < ranges More...
|
|
bool | contains (const Ranges &rs) const |
| < ranges 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)