Description
template<class T>
class Sawyer::Container::Interval< T >
Range of values delimited by endpoints.
This class represents a range of contiguous values by specifying the lower and upper end points, both of which are included in the range. Alternatively, a range may be empty; the default constructor creates empty ranges. The value type, T, is intended to be an unsigned integer type. Signed integers may be used, but the caller should be prepared to handle negative sizes due to overflow (see size). Non-integer types are not recommended since some methods (e.g., size) assume that n and n+1 are adjacent values, which is not the case for floating point.
Values of this type are immutable except for the assignment operator; operations like intersection return a new object rather than modifying an existing object.
Definition at line 33 of file Interval.h.
#include <Interval.h>
Classes | |
| class | ConstIterator |
| Bidirectional forward iterator. More... | |
Public Types | |
| typedef T | Value |
| Types of values in the interval. | |
| typedef ConstIterator | const_iterator |
| typedef ConstIterator | iterator |
Public Member Functions | |
| Interval () | |
| Constructs an empty interval. | |
| Interval (const Interval &other) | |
| Copy-constructs an interval. | |
| Interval (T value) | |
| Constructs a singleton interval. | |
| Interval & | operator= (const Interval &other) |
| Assignment from an interval. | |
| Interval & | operator= (T value) |
| Assignment from a scalar. | |
| T | least () const |
| Returns lower limit. | |
| T | greatest () const |
| Returns upper limit. | |
| bool | isEmpty () const |
| True if interval is empty. | |
| bool | isSingleton () const |
| True if interval is a singleton. | |
| bool | isWhole () const |
| True if interval covers entire space. | |
| bool | isOverlapping (const Interval &other) const |
| True if two intervals overlap. More... | |
| bool | isContaining (const Interval &other) const |
| Containment predicate. More... | |
| Value | size () const |
| Size of interval. More... | |
| Interval | hull (const Interval &other) const |
| Hull. More... | |
| Interval | hull (T value) const |
| Hull. More... | |
| std::pair< Interval, Interval > | split (T splitPoint) const |
| Split interval in two. More... | |
| Interval | join (const Interval &right) const |
| Creates an interval by joining two adjacent intervals. More... | |
| Interval | shiftRightSat (Value n) const |
| Shift interval upward. More... | |
| ConstIterator | begin () const |
| Iterator positioned at the least value. More... | |
| ConstIterator | end () const |
| Iterator positioned one past the greatest value. More... | |
| boost::iterator_range< ConstIterator > | values () const |
| Iterator range for values. | |
| operator unspecified_bool () const | |
| Type for Boolean context. More... | |
| bool | isLeftAdjacent (const Interval &right) const |
| Adjacency predicate. More... | |
| bool | isRightAdjacent (const Interval &left) const |
| Adjacency predicate. More... | |
| bool | isAdjacent (const Interval &other) const |
| Adjacency predicate. More... | |
| bool | isLeftOf (const Interval &right) const |
| Relative position predicate. More... | |
| bool | isRightOf (const Interval &left) const |
| Relative position predicate. More... | |
| bool | operator== (const Interval &other) const |
| Equality test. More... | |
| bool | operator!= (const Interval &other) const |
| Equality test. More... | |
| Interval | intersection (const Interval &other) const |
| Intersection. More... | |
| Interval | operator& (const Interval &other) const |
| Intersection. More... | |
Static Public Member Functions | |
| static Interval | hull (T v1, T v2) |
| Construct an interval from two endpoints. More... | |
| static Interval | baseSize (T lo, T size) |
| Construct an interval from one endpoint and a size. More... | |
| static Interval | baseSizeSat (T lo, T size) |
| Construct an interval from one endpoint and size, and clip overflows. More... | |
| static Interval | whole () |
| Construct an interval that covers the entire domain. | |
| static bool | baseSizeOverflows (T base, T size) |
| Tests whether a base and size overflows. More... | |
Member Function Documentation
◆ hull() [1/3]
|
inlinestatic |
Construct an interval from two endpoints.
Returns the smallest interal that contains both points.
Definition at line 151 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::baseSize(), Sawyer::Container::Interval< Address >::baseSizeSat(), Sawyer::Container::IntervalSetMap< I, S >::erase(), Sawyer::Container::IntervalMap< Interval, int >::firstUnmapped(), Sawyer::Container::Set< Key >::hull(), Sawyer::Container::Interval< Address >::hull(), Sawyer::Container::Map< VertexOrEdgeKey, VertexOrEdgeConstIterator >::hull(), Sawyer::Container::IntervalMap< Interval, int >::hull(), Sawyer::Container::IntervalSetMap< I, S >::insert(), Sawyer::Container::IntervalMap< Interval, int >::insert(), Sawyer::Container::IntervalSet< Interval >::intersect(), Sawyer::Container::Interval< Address >::intersection(), Sawyer::Container::IntervalSet< Interval >::invert(), Sawyer::Container::Interval< Address >::join(), Sawyer::Container::IntervalMap< Interval, int >::lastUnmapped(), Sawyer::Container::Interval< Address >::shiftRightSat(), Sawyer::Container::Interval< Address >::split(), and Sawyer::Container::Interval< Address >::whole().
◆ baseSize()
|
inlinestatic |
Construct an interval from one endpoint and a size.
Returns the smallest interval that contains lo (inclusive) through lo + size (exclusive). If size is zero then an empty interval is created, in which case lo is irrelevant.
Definition at line 162 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::baseSizeSat().
◆ baseSizeSat()
|
inlinestatic |
Construct an interval from one endpoint and size, and clip overflows.
Returns the smallest interval that contains lo (inclusive) through lo + size (exclusvie). If lo + size doesn't fit in an instance of Value then the greatest possible value is used.
Definition at line 171 of file Interval.h.
◆ baseSizeOverflows()
|
inlinestatic |
Tests whether a base and size overflows.
If the base (least value) plus the size would be larger than the maximum possible value, then returns true, otherwise returns false.
Definition at line 201 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::baseSize(), Sawyer::Container::Interval< Address >::baseSizeSat(), and Sawyer::Container::Interval< Address >::shiftRightSat().
◆ isOverlapping()
|
inline |
True if two intervals overlap.
An empty interval never overlaps with any other interval, empty or not.
Definition at line 230 of file Interval.h.
Referenced by Sawyer::Container::BitVectorSupport::swap().
◆ isContaining()
|
inline |
Containment predicate.
Returns true if this interval contains all of the other interval. An empty interval is always contained in any other interval, even another empty interval.
Definition at line 238 of file Interval.h.
◆ isLeftAdjacent()
|
inline |
Adjacency predicate.
Returns true if the two intervals are adjacent. An empty interval is adjacent to all other intervals, including another empty interval.
Definition at line 249 of file Interval.h.
◆ isRightAdjacent()
|
inline |
Adjacency predicate.
Returns true if the two intervals are adjacent. An empty interval is adjacent to all other intervals, including another empty interval.
Definition at line 252 of file Interval.h.
◆ isAdjacent()
|
inline |
Adjacency predicate.
Returns true if the two intervals are adjacent. An empty interval is adjacent to all other intervals, including another empty interval.
Definition at line 255 of file Interval.h.
◆ isLeftOf()
|
inline |
Relative position predicate.
Returns true if the intervals do not overlap and one is positioned left or right of the other. Empty intervals are considered to be both left and right of the other.
Definition at line 268 of file Interval.h.
◆ isRightOf()
|
inline |
Relative position predicate.
Returns true if the intervals do not overlap and one is positioned left or right of the other. Empty intervals are considered to be both left and right of the other.
Definition at line 271 of file Interval.h.
◆ size()
|
inline |
Size of interval.
If the interval is the whole space then the return value is zero due to overflow.
Definition at line 279 of file Interval.h.
Referenced by Sawyer::Container::BitVectorSupport::areEqual(), Sawyer::Container::Interval< Address >::baseSize(), Sawyer::Container::Interval< Address >::baseSizeOverflows(), Sawyer::Container::Interval< Address >::baseSizeSat(), Sawyer::Container::AddressMap< A, T >::checkConsistency(), Sawyer::Container::BitVectorSupport::compare(), Sawyer::Container::BitVectorSupport::compareSigned(), Sawyer::Container::BitVectorSupport::equalTo(), Sawyer::Container::AddressMap< A, T >::findFreeSpace(), Sawyer::Container::BitVectorSupport::fromDecimal(), Sawyer::Container::BitVectorSupport::fromInteger(), Sawyer::Container::BitVectorSupport::mostSignificantClearBit(), Sawyer::Container::BitVectorSupport::mostSignificantDifference(), Sawyer::Container::BitVectorSupport::mostSignificantSetBit(), Sawyer::Container::BitVectorSupport::multiply10(), Sawyer::Container::AddressMap< A, T >::read(), Sawyer::Container::BitVectorSupport::rotateLeft(), Sawyer::Container::BitVectorSupport::rotateRight(), Sawyer::Container::BitVectorSupport::shiftLeft(), Sawyer::Container::BitVectorSupport::shiftRight(), Sawyer::Container::BitVectorSupport::signExtend(), Sawyer::Container::BitVectorSupport::subtract(), Sawyer::Container::BitVectorSupport::toInteger(), Sawyer::Container::BitVectorSupport::toSignedInteger(), Sawyer::Container::BitVectorSupport::traverse(), Sawyer::Container::BitVectorSupport::traverse2(), and Sawyer::Container::AddressMap< A, T >::write().
◆ operator==()
|
inline |
Equality test.
Two intervals are equal if they have the same lower and upper bound, and unequal if either bound differs. Two empty ranges are considered to be equal.
Definition at line 289 of file Interval.h.
◆ operator!=()
|
inline |
Equality test.
Two intervals are equal if they have the same lower and upper bound, and unequal if either bound differs. Two empty ranges are considered to be equal.
Definition at line 292 of file Interval.h.
◆ intersection()
|
inline |
Intersection.
Returns an interval which is the intersection of this interval with another.
Definition at line 302 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::isOverlapping(), and Sawyer::Container::Interval< Address >::operator&().
◆ operator&()
|
inline |
Intersection.
Returns an interval which is the intersection of this interval with another.
Definition at line 307 of file Interval.h.
◆ hull() [2/3]
|
inline |
Hull.
Returns the smallest interval that contains both this interval and the other interval.
- See also
- join
Definition at line 317 of file Interval.h.
◆ hull() [3/3]
|
inline |
Hull.
Returns the smallest interval that contains both this interval and another value.
Definition at line 330 of file Interval.h.
◆ split()
|
inline |
Split interval in two.
Returns two interval by splitting this interval so that splitPoint is in the left returned interval. If the split is not a member of this interval then one of the two returned intervals will be empty, depending on whether the split point is less than or greater than this interval. If this interval is empty then both returned intervals will be empty regardless of the split point.
Definition at line 344 of file Interval.h.
◆ join()
|
inline |
Creates an interval by joining two adjacent intervals.
Concatenates this interval with the right interval and returns the result. This is similar to hull except when neither interval is empty then the greatest value of this interval must be one less than the least value of the right interval.
- See also
- hull
Definition at line 363 of file Interval.h.
◆ shiftRightSat()
|
inline |
Shift interval upward.
Adds n to all values of the interval to return a new interval. An empty interval is returned if this interval is empty or adding n to its least value would overflow. A smaller interval is returned if adding n to the greatest value would overflow.
Definition at line 379 of file Interval.h.
◆ begin()
|
inline |
Iterator positioned at the least value.
Returns an iterator positioned at this interval's least value. If this interval is empty then the returned iterator's atEnd predicate will always return true. Iterators are useful for accessing the values of an interval because they have special logic to avoid arithmetic overflows which can happen if the interval's least and/or greatest value happens to also be the least or greatest value representable by type T. See ConstIterator for details.
Definition at line 400 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::values().
◆ end()
|
inline |
Iterator positioned one past the greatest value.
Returns an iterator positioned one past this interval's least value even if such a value cannot be represented by type T. If this interval is empty then the returned iterator's atEnd predicate will always return true. Iterators are useful for accessing the values of an interval because they have special logic to avoid arithmetic overflows which can happen if the interval's least and/or greatest value happens to also be the least or greatest value representable by type T. See ConstIterator for details.
Definition at line 411 of file Interval.h.
Referenced by Sawyer::Container::Interval< Address >::values().
◆ operator unspecified_bool()
|
inline |
Type for Boolean context.
Implicit conversion to a type that can be used in a boolean context such as an if or while statement. For instance:
The inteval evaluates to true if it is non-empty, and false if it is empty.
Definition at line 438 of file Interval.h.
The documentation for this class was generated from the following file:
