RangeList< RangeType > Class Template Reference

#include <rangelist.h>

Inheritance diagram for RangeList< RangeType >:

Inheritance graph
[legend]
List of all members.

Detailed Description

template<typename RangeType>
class RangeList< RangeType >

RangeList<T> is a generic container for Range<T> type objects.

It supports all the operations single Range<T> objects support, however is also capable of performing those operations over several ranges. RangeList<T> provides public typedef CIter for iterating on the underlying implementation. Ranges in RangeList are guaranteed to be ordered based on Range begin values, as defined by Range<T> object.

RangeList does not perform any lower or upper bound checking, except for those inherent from the underlying data type.

Ranges can be either push()'ed or merge()'d into RangeList. In the former case, duplicates are allowed, and overlapping/bordering ranges are not merged together into larger ranges. In the latter case, overlapping/bordering ranges are compacted into bigger Range objects. The same logic applies to remove() and erase() methods, former erasing an exact copy of the passed Range, latter erasing a region of RangeList, possibly modifying existing ranges. After call to erase(X, Y), it is guaranteed that RangeList::contains(X, Y) shall return false, however in case of remove(), there is no such guarantee.

All operations on RangeLists have logarithmic complexity, so it is possible to store vast amounts of ranges here with little performance penalty.

Parameters:
T Data type the ranges consist of. This is generally integer.
RangeType Derived from
T,this indicates the actual Range object type. It is possible to override this parameter with user-defined class, which implements the requirements posed by Range class.

Definition at line 63 of file rangelist.h.


Public Types

typedef std::multiset< RangeType > Impl
 Implementation object type.
typedef Impl::iterator Iter
 For iterating on the implementation.
typedef Impl::const_iterator CIter
 For iterating on the implementation.
typedef RangeType::size_type size_type
 The size type.

Public Member Functions

 RangeList ()
 Default constructor.
 ~RangeList ()
 Destructor.
 RangeList (std::istream &i)
 Construct and load from stream.
bool push (const RangeType &r)
 Push a range into the rangelist.
bool remove (const RangeType &r)
 Remove an exact range from the rangelist.
void merge (RangeType r)
 Merge a range into the existing rangelist.
void erase (const RangeType &r)
 Erase a range from the rangelist.
RangeType getFirstFree (const size_type &limit=std::numeric_limits< size_type >::max()) const
 Locate the first free (unused) range in the rangelist, optionally indicating the upper bound until which to search.
bool contains (const RangeType &r) const
 Check if a given range is contained within this rangelist.
bool containsFull (const RangeType &r) const
 Check whether a given range is completely contained within this.
CIter getContains (const RangeType &r) const
 Locate the first (?) range which contains the passed range.
CIter getBorders (const RangeType &r) const
 Locate the first (?) range which borders with the passed range.
More convenient versions for the above functions
These methods construct the RangeType object internally from the passed values.

These only work when using built-in Range types, or user-defined types which do not pose additional constructor argument requirements.

template<typename X, typename Y>
bool push (const X &x, const Y &y)
template<typename X, typename Y>
bool remove (const X &x, const Y &y)
template<typename X, typename Y>
void merge (const X &x, const Y &y)
template<typename X, typename Y>
void erase (const X &x, const Y &y)
template<typename X>
bool contains (const X &x) const
template<typename X, typename Y>
bool contains (const X &x, const Y &y) const
template<typename X>
bool containsFull (const X &x) const
template<typename X, typename Y>
bool containsFull (const X &x, const Y &y) const
template<typename X>
CIter getContains (const X &x) const
template<typename X, typename Y>
CIter getContains (const X &x, const Y &y) const
Generic accessors
Returns number of elements in the rangelist

size_t size () const
void clear ()
 Erases all elements in the list.
bool empty () const
 Tests if the rangelist is empty, e.g. size() == 0.
Accessors
Note:
The list is sorted based on the center-point of the ranges, thus the first element in the list is not guaranteed to start before every other element, however, it is guaranteed to have the lowest begin+end/2 value.


CIter begin () const
CIter end () const
 Constant iterator to one-past-end of the list.
Iter begin ()
 Iterator to the first element of the list.
Iter end ()
 Iterator to one-past-end of the list.
Accessors for first and last members of the list
Returns:
Reference to the element requested.
Exceptions:
std::runtime_error if the list is empty.


const RangeType & front () const
const RangeType & back () const

Private Member Functions

Iter doGetContains (const RangeType &r)
 Implementation of getContains() method, using non-const types; Locates the first (?) range which contains the passed range.
Iter doGetBorders (const RangeType &r)
 Implementation of getBorders() method, using non-const types; Locates the first range which borders with the passed range.

Private Attributes

Impl m_ranges

Friends

std::ostream & operator<< (std::ostream &o, const RangeList &rl)
 Output operator for streams.

Member Typedef Documentation

template<typename RangeType>
typedef Impl::const_iterator RangeList< RangeType >::CIter
 

For iterating on the implementation.

Definition at line 70 of file rangelist.h.

template<typename RangeType>
typedef std::multiset<RangeType> RangeList< RangeType >::Impl
 

Implementation object type.

Definition at line 66 of file rangelist.h.

template<typename RangeType>
typedef Impl::iterator RangeList< RangeType >::Iter
 

For iterating on the implementation.

Definition at line 68 of file rangelist.h.

template<typename RangeType>
typedef RangeType::size_type RangeList< RangeType >::size_type
 

The size type.

Definition at line 72 of file rangelist.h.


Constructor & Destructor Documentation

template<typename RangeType>
RangeList< RangeType >::RangeList  )  [inline]
 

Default constructor.

Definition at line 75 of file rangelist.h.

template<typename RangeType>
RangeList< RangeType >::~RangeList  )  [inline]
 

Destructor.

Definition at line 77 of file rangelist.h.

template<typename RangeType>
RangeList< RangeType >::RangeList std::istream &  i  )  [inline]
 

Construct and load from stream.

Definition at line 79 of file rangelist.h.


Member Function Documentation

template<typename RangeType>
const RangeType& RangeList< RangeType >::back  )  const [inline]
 

Definition at line 375 of file rangelist.h.

template<typename RangeType>
Iter RangeList< RangeType >::begin  )  [inline]
 

Iterator to the first element of the list.

Definition at line 359 of file rangelist.h.

template<typename RangeType>
CIter RangeList< RangeType >::begin  )  const [inline]
 

Constant iterator to the first element of the list

Definition at line 355 of file rangelist.h.

Referenced by RangeList< Range32 >::containsFull(), RangeList< Range32 >::doGetBorders(), RangeList< Range32 >::doGetContains(), RangeList< Range32 >::front(), RangeList< Range32 >::getBorders(), PartData::getCompleted(), RangeList< Range32 >::getContains(), RangeList< Range32 >::getFirstFree(), PartData::isComplete(), and PartData::printCompleted().

template<typename RangeType>
void RangeList< RangeType >::clear  )  [inline]
 

Erases all elements in the list.

Definition at line 340 of file rangelist.h.

Referenced by PartData::flushBuffer(), and PartData::getRange().

template<typename RangeType>
template<typename X, typename Y>
bool RangeList< RangeType >::contains const X &  x,
const Y &  y
const [inline]
 

Definition at line 314 of file rangelist.h.

template<typename RangeType>
template<typename X>
bool RangeList< RangeType >::contains const X &  x  )  const [inline]
 

Definition at line 310 of file rangelist.h.

template<typename RangeType>
bool RangeList< RangeType >::contains const RangeType &  r  )  const [inline]
 

Check if a given range is contained within this rangelist.

Parameters:
x Range to be tested
Returns:
True if the range is even partially contained within one of the existing ranges of this rangelist.
Note:
Keep in mind that this method returns true even during partial matches, e.g. when a subrange of
Parameters:
x overlaps with one (or more) of the existing ranges. True return value thus does not indicate here that
x is fully contained within this rangelist.
See also:
RangeList::containsFull()

Definition at line 221 of file rangelist.h.

Referenced by RangeList< Range32 >::contains(), RangeList< Range32 >::doGetContains(), PartData::doWrite(), RangeList< Range32 >::getContains(), and PartData::write().

template<typename RangeType>
template<typename X, typename Y>
bool RangeList< RangeType >::containsFull const X &  x,
const Y &  y
const [inline]
 

Definition at line 322 of file rangelist.h.

template<typename RangeType>
template<typename X>
bool RangeList< RangeType >::containsFull const X &  x  )  const [inline]
 

Definition at line 318 of file rangelist.h.

template<typename RangeType>
bool RangeList< RangeType >::containsFull const RangeType &  r  )  const [inline]
 

Check whether a given range is completely contained within this.

Parameters:
x Range to be tested
Returns:
True if the range is fully contained in here.

Definition at line 231 of file rangelist.h.

Referenced by RangeList< Range32 >::containsFull(), PartData::isComplete(), and CheckPred::operator()().

template<typename RangeType>
Iter RangeList< RangeType >::doGetBorders const RangeType &  r  )  [inline, private]
 

Implementation of getBorders() method, using non-const types; Locates the first range which borders with the passed range.

Parameters:
r Range to be searched for
Returns:
Iterator to the bordering range, or end() if not found

Definition at line 408 of file rangelist.h.

Referenced by RangeList< Range32 >::merge().

template<typename RangeType>
Iter RangeList< RangeType >::doGetContains const RangeType &  r  )  [inline, private]
 

Implementation of getContains() method, using non-const types; Locates the first (?) range which contains the passed range.

Parameters:
r Range to be searched for
Returns:
Iterator to the range, or end() if not found

Definition at line 390 of file rangelist.h.

Referenced by RangeList< Range32 >::erase(), and RangeList< Range32 >::merge().

template<typename RangeType>
bool RangeList< RangeType >::empty  )  const [inline]
 

Tests if the rangelist is empty, e.g. size() == 0.

Definition at line 342 of file rangelist.h.

Referenced by PartData::doGetRange().

template<typename RangeType>
Iter RangeList< RangeType >::end  )  [inline]
 

Iterator to one-past-end of the list.

Definition at line 361 of file rangelist.h.

template<typename RangeType>
CIter RangeList< RangeType >::end  )  const [inline]
 

Constant iterator to one-past-end of the list.

Definition at line 357 of file rangelist.h.

Referenced by RangeList< Range32 >::back(), RangeList< Range32 >::contains(), RangeList< Range32 >::containsFull(), RangeList< Range32 >::doGetBorders(), RangeList< Range32 >::doGetContains(), PartData::doGetRange(), RangeList< Range32 >::getBorders(), PartData::getCompleted(), RangeList< Range32 >::getContains(), RangeList< Range32 >::getFirstFree(), PartData::getLock(), PartData::isComplete(), RangeList< Range32 >::merge(), PartData::printCompleted(), RangeList< Range32 >::push(), and RangeList< Range32 >::remove().

template<typename RangeType>
template<typename X, typename Y>
void RangeList< RangeType >::erase const X &  x,
const Y &  y
[inline]
 

Definition at line 306 of file rangelist.h.

template<typename RangeType>
void RangeList< RangeType >::erase const RangeType &  r  )  [inline]
 

Erase a range from the rangelist.

Parameters:
r Range to be erased

Definition at line 160 of file rangelist.h.

Referenced by RangeList< Range32 >::erase(), Detail::Chunk::onHashEvent(), PartData::verifyHashSet(), and Detail::LockedRange::~LockedRange().

template<typename RangeType>
const RangeType& RangeList< RangeType >::front  )  const [inline]
 

Definition at line 371 of file rangelist.h.

Referenced by PartData::doGetRange().

template<typename RangeType>
CIter RangeList< RangeType >::getBorders const RangeType &  r  )  const [inline]
 

Locate the first (?) range which borders with the passed range.

Parameters:
r Range to be searched for
Returns:
Iterator to the found range, or end() if not found

Definition at line 268 of file rangelist.h.

template<typename RangeType>
template<typename X, typename Y>
CIter RangeList< RangeType >::getContains const X &  x,
const Y &  y
const [inline]
 

Definition at line 330 of file rangelist.h.

template<typename RangeType>
template<typename X>
CIter RangeList< RangeType >::getContains const X &  x  )  const [inline]
 

Definition at line 326 of file rangelist.h.

template<typename RangeType>
CIter RangeList< RangeType >::getContains const RangeType &  r  )  const [inline]
 

Locate the first (?) range which contains the passed range.

Parameters:
r Range to be searched for
Returns:
Iterator to the found range, or end() if not found.
Note:
It is guaranteed that the returned range is the first range (first in the sense of lower-value) range that contains the questioned range. (hence the while-loop in here).

Definition at line 251 of file rangelist.h.

Referenced by RangeList< Range32 >::contains(), RangeList< Range32 >::containsFull(), RangeList< Range32 >::getContains(), and PartData::getLock().

template<typename RangeType>
RangeType RangeList< RangeType >::getFirstFree const size_type limit = std::numeric_limits<size_type>::max()  )  const [inline]
 

Locate the first free (unused) range in the rangelist, optionally indicating the upper bound until which to search.

Parameters:
limit Optional upper bound for searching
Returns:
An unused range

Definition at line 183 of file rangelist.h.

template<typename RangeType>
template<typename X, typename Y>
void RangeList< RangeType >::merge const X &  x,
const Y &  y
[inline]
 

Definition at line 302 of file rangelist.h.

template<typename RangeType>
void RangeList< RangeType >::merge RangeType  r  )  [inline]
 

Merge a range into the existing rangelist.

Merging concept means all ranges bordering or overlapping with the passed range will be "merged" together with the passed range, and erased from the list, after which the (now modified) passed range is inserted to the list.

Parameters:
r Range to be merged into the rangelist.

Definition at line 139 of file rangelist.h.

Referenced by PartData::doWrite(), Detail::LockedRange::LockedRange(), RangeList< Range32 >::merge(), and PartData::verifyHashSet().

template<typename RangeType>
template<typename X, typename Y>
bool RangeList< RangeType >::push const X &  x,
const Y &  y
[inline]
 

Definition at line 294 of file rangelist.h.

template<typename RangeType>
bool RangeList< RangeType >::push const RangeType &  r  )  [inline]
 

Push a range into the rangelist.

Parameters:
r Range to be inserted
Returns:
True if the range was inserted, false if it already existed (e.g. duplicates are not allowed)

Definition at line 105 of file rangelist.h.

Referenced by PartData::getRange(), RangeList< Range32 >::push(), and SchedBase::SchedBase().

template<typename RangeType>
template<typename X, typename Y>
bool RangeList< RangeType >::remove const X &  x,
const Y &  y
[inline]
 

Definition at line 298 of file rangelist.h.

template<typename RangeType>
bool RangeList< RangeType >::remove const RangeType &  r  )  [inline]
 

Remove an exact range from the rangelist.

Parameters:
r Range to be removed
Returns:
True if the exact range was found and removed, false otherwise.

Definition at line 121 of file rangelist.h.

Referenced by RangeList< Range32 >::remove().

template<typename RangeType>
size_t RangeList< RangeType >::size  )  const [inline]
 

Definition at line 338 of file rangelist.h.

Referenced by RangeList< Range32 >::back(), PartData::doWrite(), RangeList< Range32 >::empty(), RangeList< Range32 >::front(), RangeList< Range32 >::getFirstFree(), and PartData::isComplete().


Friends And Related Function Documentation

template<typename RangeType>
std::ostream& operator<< std::ostream &  o,
const RangeList< RangeType > &  rl
[friend]
 

Output operator for streams.

Definition at line 90 of file rangelist.h.


Member Data Documentation

template<typename RangeType>
Impl RangeList< RangeType >::m_ranges [private]
 

Definition at line 381 of file rangelist.h.


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