reflex::ORanges< T > Class Template Reference

updated Tue Nov 15 2016
 
Public Types | Public Member Functions | Static Private Member Functions | List of all members
reflex::ORanges< T > Class Template Reference

#include <ranges.h>

Inheritance diagram for reflex::ORanges< T >:
Inheritance graph
[legend]
Collaboration diagram for reflex::ORanges< T >:
Collaboration graph
[legend]

Public Types

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...
 
- Public Types inherited from reflex::Ranges< T >
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...
 

Public Member Functions

 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...
 
ORangesoperator-= (const ORanges &rs)
 
ORangesoperator&= (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...
 
- Public Member Functions inherited from reflex::Ranges< T >
 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...
 
Rangesoperator|= (const Ranges &rs)
 
Rangesoperator+= (const Ranges &rs)
 
Rangesoperator&= (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...
 

Static Private Member Functions

static bound_type bump (bound_type val)
 

Detailed Description

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; // insert 0
ints.insert(100, 200); // insert 100..200
ints.insert(300, 400); // insert 300..400
ints.insert(200, 300); // insert 200..300
std::cout << "Set of " << ints.size() << " open-ended ranges:" << std::endl;
for (reflex::ORanges<int>::const_iterator i = ints.begin(); i != ints.end(); ++i)
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;
ints.erase(250, 350);
for (reflex::ORanges<int>::const_iterator i = ints.begin(); i != ints.end(); ++i)
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)

Member Typedef Documentation

template<typename T>
typedef T reflex::ORanges< T >::bound_type

Type of the bounds.

template<typename T>
typedef container_type::const_iterator reflex::ORanges< T >::const_iterator

Synonym type defining the base class container std::set::const_iterator.

template<typename T>
typedef std::set< std::pair<T,T>,range_compare<T> > reflex::ORanges< T >::container_type

Synonym type defining the base class container std::set.

template<typename T>
typedef container_type::iterator reflex::ORanges< T >::iterator

Synonym type defining the base class container std::set::iterator.

template<typename T>
typedef container_type::key_compare reflex::ORanges< T >::key_compare

Synonym type defining the key/value comparison std::set::key_compare.

template<typename T>
typedef container_type::value_compare reflex::ORanges< T >::value_compare
template<typename T>
typedef container_type::value_type reflex::ORanges< T >::value_type

Synonym type defining the base class container std::set::value_type.

Constructor & Destructor Documentation

template<typename T>
reflex::ORanges< T >::ORanges ( )
inline

Construct an empty range.

template<typename T>
reflex::ORanges< T >::ORanges ( const value_type r)
inline

Construct a copy of a range [lo,hi].

Parameters
rrange
template<typename T>
reflex::ORanges< T >::ORanges ( const bound_type lo,
const bound_type hi 
)
inline

Construct a range [lo,hi].

Parameters
lolower bound
hiupper bound
template<typename T>
reflex::ORanges< T >::ORanges ( const bound_type val)
inline

Construct a singleton range [val,val].

Parameters
valvalue

Member Function Documentation

template<typename T>
static bound_type reflex::ORanges< T >::bump ( bound_type  val)
inlinestaticprivate

Bump with clamping.

Returns
val + 1 or val when max.
Parameters
valthe value to bump
template<typename T>
bool reflex::ORanges< T >::erase ( const bound_type lo,
const bound_type hi 
)
inline

Update ranges by deleting the given range [lo,hi].

Returns
true if ranges was updated.
Parameters
lolower bound
hiupper bound
template<typename T>
bool reflex::ORanges< T >::erase ( const bound_type val)
inline

Update ranges by deleting the given range [val,val].

Returns
true if ranges was updated.
Parameters
valvalue to delete
template<typename T>
const_iterator reflex::ORanges< T >::find ( const bound_type lo,
const bound_type hi 
) const
inline

< upper bound

Find the first range that overlaps the given range.

Returns
iterator to the first range that overlaps the given range, or the end iterator.
Parameters
lolower bound
template<typename T>
const_iterator reflex::ORanges< T >::find ( const bound_type val) const
inline

< value to search for

Find the range that includes the given value.

Returns
iterator to the range that includes the value, or the end iterator.
template<typename T>
std::pair<iterator,bool> reflex::ORanges< T >::insert ( const bound_type lo,
const bound_type hi 
)
inline

Update ranges to include range [lo,hi] by merging overlapping and adjacent ranges into one range.

Returns
a pair of an iterator to the range and a flag indicating whether the range was inserted as new.
Parameters
lolower bound
hiupper bound
template<typename T>
std::pair<iterator,bool> reflex::ORanges< T >::insert ( const bound_type val)
inline

Update ranges to include range [val,val] by merging overlapping and adjacent ranges into one range.

Returns
a pair of an iterator to the range and a flag indicating whether the range was inserted as new.
Parameters
valvalue to insert
template<typename T>
bool reflex::ORanges< T >::intersects ( const ORanges< T > &  rs) const
inline

< ranges

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.

Returns
true if this set intersects rs.
template<typename T>
ORanges reflex::ORanges< T >::operator& ( const ORanges< T > &  rs) const
inline

< ranges to intersect

Returns the intersection of two open-ended range sets.

Returns
the intersection of this set and rs.
template<typename T>
ORanges& reflex::ORanges< T >::operator&= ( const ORanges< T > &  rs)
inline

Update ranges to intersect the ranges of the given range set.

Returns
reference to this object.
Parameters
rsranges to intersect
template<typename T>
ORanges reflex::ORanges< T >::operator- ( const ORanges< T > &  rs) const
inline

< ranges

Returns the difference of two open-ended range sets.

Returns
the difference of this set and rs.
template<typename T>
ORanges& reflex::ORanges< T >::operator-= ( const ORanges< T > &  rs)
inline

Update ranges to remove ranges rs, has lower complexity than repeating erase().

Returns
reference to this object.

The documentation for this class was generated from the following file: