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 <util/Sawyer/Interval.h>

Inheritance diagram for Sawyer::Container::Interval< T >:

[legend]

Classes
class	ConstIterator
	Bidirectional forward iterator. More...

Public Types
typedef T	Value
	Types of values in the interval. More...

typedef ConstIterator	const_iterator

typedef ConstIterator	iterator

Public Member Functions
	Interval ()
	Constructs an empty interval. More...

	Interval (const Interval &other)
	Copy-constructs an interval. More...

	Interval (T value)
	Constructs a singleton interval. More...

Interval &	operator= (const Interval &other)
	Assignment from an interval. More...

Interval &	operator= (T value)
	Assignment from a scalar. More...

T	least () const
	Returns lower limit. More...

T	greatest () const
	Returns upper limit. More...

bool	isEmpty () const
	True if interval is empty. More...

bool	isSingleton () const
	True if interval is a singleton. More...

bool	isWhole () const
	True if interval covers entire space. 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. More...

	operator unspecified_bool () const
	Type for Boolean context. More...


bool	overlaps (const Interval &other) const
	True if two intervals overlap. More...

bool	isOverlapping (const Interval &other) const
	True if two intervals overlap. More...


bool	contains (const Interval &other) const
	Containment predicate. More...

bool	isContaining (const Interval &other) const
	Containment predicate. 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. More...

static bool	baseSizeOverflows (T base, T size)
	Tests whether a base and size overflows. More...

Member Typedef Documentation

template<class T>

typedef T Sawyer::Container::Interval< T >::Value

Types of values in the interval.

Definition at line 36 of file Interval.h.

Constructor & Destructor Documentation

template<class T>

Sawyer::Container::Interval< T >::Interval ( )

inline

Constructs an empty interval.

Definition at line 130 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::baseSize(), Sawyer::Container::Interval< Address >::hull(), Sawyer::Container::Interval< Address >::intersection(), Sawyer::Container::Interval< Address >::shiftRightSat(), and Sawyer::Container::Interval< Address >::split().

template<class T>

Sawyer::Container::Interval< T >::Interval ( const Interval< T > & other )

inline

Copy-constructs an interval.

Definition at line 133 of file Interval.h.

template<class T>

Sawyer::Container::Interval< T >::Interval ( T value )

inline

Constructs a singleton interval.

Definition at line 136 of file Interval.h.

Member Function Documentation

template<class T>

static Interval Sawyer::Container::Interval< T >::hull	(	T	v1,
		T	v2
	)

inlinestatic

Construct an interval from two endpoints.

Returns the smallest interal that contains both points.

Definition at line 151 of file Interval.h.

template<class T>

static Interval Sawyer::Container::Interval< T >::baseSize	(	T	lo,
		T	size
	)

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(), and Rose::BinaryAnalysis::RegisterDescriptor::bits().

template<class T>

static Interval Sawyer::Container::Interval< T >::baseSizeSat	(	T	lo,
		T	size
	)

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.

template<class T>

static Interval Sawyer::Container::Interval< T >::whole ( )

inlinestatic

Construct an interval that covers the entire domain.

Definition at line 180 of file Interval.h.

Referenced by Sawyer::Container::AddressMap< rose_addr_t, uint8_t >::findFreeSpace(), Sawyer::Container::IntervalMap< Interval, int >::firstUnmapped(), Sawyer::Container::IntervalSet< AddressInterval >::invert(), and Sawyer::Container::IntervalMap< Interval, int >::lastUnmapped().

template<class T>

Interval& Sawyer::Container::Interval< T >::operator= ( const Interval< T > & other )

inline

Assignment from an interval.

Definition at line 185 of file Interval.h.

template<class T>

Interval& Sawyer::Container::Interval< T >::operator= ( T value )

inline

Assignment from a scalar.

Definition at line 192 of file Interval.h.

template<class T>

static bool Sawyer::Container::Interval< T >::baseSizeOverflows	(	T	base,
		T	size
	)

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().

template<class T>

T Sawyer::Container::Interval< T >::least ( ) const

inline

Returns lower limit.

Definition at line 207 of file Interval.h.

template<class T>

T Sawyer::Container::Interval< T >::greatest ( ) const

inline

Returns upper limit.

Definition at line 213 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isEmpty ( ) const

inline

True if interval is empty.

Definition at line 219 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isSingleton ( ) const

inline

True if interval is a singleton.

Definition at line 222 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isWhole ( ) const

inline

True if interval covers entire space.

Definition at line 225 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::isAdjacent(), Sawyer::Container::Interval< Address >::isLeftAdjacent(), and Sawyer::Container::Interval< Address >::isRightAdjacent().

template<class T>

bool Sawyer::Container::Interval< T >::overlaps ( const Interval< T > & other ) const

inline

True if two intervals overlap.

An empty interval never overlaps with any other interval, empty or not.

Definition at line 232 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::isOverlapping(), and Sawyer::Container::BitVectorSupport::swap().

template<class T>

bool Sawyer::Container::Interval< T >::isOverlapping ( const Interval< T > & other ) const

inline

True if two intervals overlap.

An empty interval never overlaps with any other interval, empty or not.

Definition at line 235 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::contains ( const Interval< T > & other ) const

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 246 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::isContaining(), and Rose::BinaryAnalysis::Partitioner2::Trigger::shouldTrigger().

template<class T>

bool Sawyer::Container::Interval< T >::isContaining ( const Interval< T > & other ) const

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 250 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isLeftAdjacent ( const Interval< T > & right ) const

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 261 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isRightAdjacent ( const Interval< T > & left ) const

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 264 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isAdjacent ( const Interval< T > & other ) const

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 267 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isLeftOf ( const Interval< T > & right ) const

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 280 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::isRightOf ( const Interval< T > & left ) const

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 283 of file Interval.h.

template<class T>

Value Sawyer::Container::Interval< T >::size ( void ) const

inline

Size of interval.

If the interval is the whole space then the return value is zero due to overflow.

Definition at line 291 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::operator== ( const Interval< T > & other ) const

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 301 of file Interval.h.

template<class T>

bool Sawyer::Container::Interval< T >::operator!= ( const Interval< T > & other ) const

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 304 of file Interval.h.

template<class T>

Interval Sawyer::Container::Interval< T >::intersection ( const Interval< T > & other ) const

inline

Intersection.

Returns an interval which is the intersection of this interval with another.

Definition at line 314 of file Interval.h.

Referenced by Sawyer::Container::IntervalSetMap< I, S >::erase(), Sawyer::Container::IntervalSetMap< I, S >::insert(), Sawyer::Container::Interval< Address >::operator&(), and Sawyer::Container::Interval< Address >::overlaps().

template<class T>

Interval Sawyer::Container::Interval< T >::operator& ( const Interval< T > & other ) const

inline

Intersection.

Returns an interval which is the intersection of this interval with another.

Definition at line 319 of file Interval.h.

template<class T>

Interval Sawyer::Container::Interval< T >::hull ( const Interval< T > & other ) const

inline

Hull.

Returns the smallest interval that contains both this interval and the other interval.

See also: join

Definition at line 329 of file Interval.h.

template<class T>

Interval Sawyer::Container::Interval< T >::hull ( T value ) const

inline

Hull.

Returns the smallest interval that contains both this interval and another value.

Definition at line 342 of file Interval.h.

template<class T>

std::pair<Interval, Interval> Sawyer::Container::Interval< T >::split ( T splitPoint ) const

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 356 of file Interval.h.

template<class T>

Interval Sawyer::Container::Interval< T >::join ( const Interval< T > & right ) const

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 375 of file Interval.h.

template<class T>

Interval Sawyer::Container::Interval< T >::shiftRightSat ( Value n ) const

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 391 of file Interval.h.

template<class T>

ConstIterator Sawyer::Container::Interval< T >::begin ( ) const

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 412 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::values().

template<class T>

ConstIterator Sawyer::Container::Interval< T >::end ( ) const

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 423 of file Interval.h.

Referenced by Sawyer::Container::Interval< Address >::values().

template<class T>

boost::iterator_range<ConstIterator> Sawyer::Container::Interval< T >::values ( ) const

inline

Iterator range for values.

Definition at line 428 of file Interval.h.

template<class T>

Sawyer::Container::Interval< T >::operator unspecified_bool ( ) const

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:

if (Interval<unsigned> x = doSomething(...)) {
   // this is reached only if x is non-empty
}

The inteval evaluates to true if it is non-empty, and false if it is empty.

Definition at line 450 of file Interval.h.

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

Interval.h

Description

template<class T> class Sawyer::Container::Interval< T >

Classes

Public Types

Public Member Functions

Static Public Member Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class T>
class Sawyer::Container::Interval< T >