Description

template<class I>
class Sawyer::Container::IntervalSet

A container holding a set of values.

This container is somewhat like the STL std::set container except it is optimized for the case when large numbers of values are contiguous. It adds the ability to insert and erase intervals as well as scalars, and provides a mechanism to iterate over the storage nodes (intervals) rather than over the scalar values.

An interval set always maintains a list containing a minimum number of largest possible intervals regardless of what intervals are inserted and erased. This feature makes for a very convenient way to compute address ranges for small things, or things that might overlap. For instance, if one has a list of intervals corresponding to machine instructions that belong to a single function in an executable (some of which might even overlap), we can easily compute whether the function is contiguous in memory, and whether any instructions overlap with each other:

// Input is a list of intervals for instructions in a function
typedef Sawyer::Container::Interval<uint32_t> AddressInterval;
std::vector<AddressInterval> instructionIntervals = ...;
 
// Build the functionExtent and count total instruction size
Sawyer::Container::IntervalSet<AddressInterval> functionExtent;
uint32_t insnTotalSize = 0;
for (const AddressInterval &insnInterval: instructionIntervals) {
    functionExtent.insert(insnInterval);
    insnTotalSize += insnInterval.size();
}
 
// Final results
bool isFunctionContiguous = functionExtent.nIntervals() <= 1;
bool isInsnsDisjoint = functionExtent.size() == insnTotalSize;

The Interval template parameter must implement the Sawyer::Container::Interval API, at least to some extent.

Definition at line 53 of file IntervalSet.h.

#include <Sawyer/IntervalSet.h>

Inheritance diagram for Sawyer::Container::IntervalSet:

[legend]

Classes
class	ConstIntervalIterator
	Interval iterator. More...

class	ConstScalarIterator
	Scalar value iterator. More...

Public Types
typedef I	Interval

typedef I::Value	Scalar
	Type of scalar values stored in this set.

Public Member Functions
	IntervalSet ()
	Default constructor.

template<class Interval2 >
	IntervalSet (const IntervalSet< Interval2 > &other)
	Copy constructor.

template<class Interval2 , class T , class Policy >
	IntervalSet (const IntervalMap< Interval2, T, Policy > &other)
	Construct from an IntervalMap.

template<class Iterator >
	IntervalSet (const boost::iterator_range< Iterator > &intervals)
	Construct from an iterator range.

template<class Interval2 >
IntervalSet &	operator= (const IntervalSet< Interval2 > &other)
	Assignment from another set.

template<class Interval2 , class T , class Policy >
IntervalSet &	operator= (const IntervalMap< Interval2, T, Policy > &other)
	Assignment from an IntervalMap.

template<class Iterator >
IntervalSet &	operator= (const boost::iterator_range< Iterator > &intervals)
	Assignment from an iterator range.

boost::iterator_range< ConstIntervalIterator >	intervals () const
	Iterator range for all intervals actually stored by this set.

boost::iterator_range< ConstScalarIterator >	scalars () const
	Iterator range for all scalar values logically represented by this set.

ConstIntervalIterator	lowerBound (const typename Interval::Value &scalar) const
	Find the first node whose interval ends at or above the specified scalar key.

ConstIntervalIterator	upperBound (const typename Interval::Value &scalar) const
	Find the first node whose interval begins above the specified scalar key.

ConstIntervalIterator	findPrior (const typename Interval::Value &scalar) const
	Find the last node whose interval starts at or below the specified scalar key.

ConstIntervalIterator	find (const typename Interval::Value &scalar) const
	Find the node containing the specified scalar key.

boost::iterator_range< ConstIntervalIterator >	findAll (const Interval &interval) const
	Finds all nodes overlapping the specified interval.

ConstIntervalIterator	findFirstOverlap (const Interval &interval) const
	Finds first node that overlaps with the specified interval.

std::pair< ConstIntervalIterator, ConstIntervalIterator >	findFirstOverlap (ConstIntervalIterator thisIter, const IntervalSet &other, ConstIntervalIterator otherIter) const
	Find first nodes that overlap.

bool	isEmpty () const
	Determine whether the container is empty.

Interval::Value	size () const
	Number of scalar elements represented.

size_t	nIntervals () const
	Number of storage nodes.

Interval	hull () const
	Returns the range of values in this map.

bool	exists (const typename Interval::Value &scalar) const
	Determines if a value exists in the set.

Scalar	least () const
	Returns the minimum scalar contained in this set.

Scalar	greatest () const
	Returns the maximum scalar contained in this set.

Optional< Scalar >	least (Scalar lowerLimit) const
	Returns the limited-minimum scalar contained in this set.

Optional< Scalar >	greatest (Scalar upperLimit) const
	Returns the limited-maximum scalar contained in this set.

Optional< Scalar >	leastNonExistent (Scalar lowerLimit) const
	Returns the limited-minimum scalar not contained in this set.

Optional< Scalar >	greatestNonExistent (Scalar upperLimit) const
	Returns the limited-maximum scalar not contained in this set.

ConstIntervalIterator	firstFit (const typename Interval::Value &size, ConstIntervalIterator start) const
	Find the first fit node at or after a starting point.

ConstIntervalIterator	bestFit (const typename Interval::Value &size, ConstIntervalIterator start) const
	Find the best fit node at or after a starting point.

void	clear ()
	Remove all values.

void	invert ()
	Invert.

void	invert (const Interval &restricted)
	Invert and intersect.

bool	operator== (const IntervalSet &other) const
	Determines if two sets contain the same elements.

bool	operator!= (const IntervalSet &other) const
	Determines if two sets contain different elements.

IntervalSet	operator~ () const
	Return inverse of specified set.

IntervalSet &	operator&= (const IntervalSet &other)
	In-place intersection.

IntervalSet &	operator&= (const Interval &interval)
	In-place intersection with an interval.

IntervalSet	operator& (const IntervalSet &other) const
	Intersection of two sets.

IntervalSet	operator& (const Interval &interval) const
	Intersection of set with interval.

IntervalSet &	operator-= (const IntervalSet &other)
	In-place subtraction.

IntervalSet &	operator-= (const Interval &interval)
	In-place subtraction of an interval.

IntervalSet	operator- (const IntervalSet &other) const
	Subtract another set from this one.

IntervalSet	operator- (const Interval &interval) const
	Subtract an interval from this set.


template<class Interval2 >
bool	overlaps (const Interval2 &interval) const
	Determines whether this set overlaps with the argument.

template<class Interval2 >
bool	isOverlapping (const Interval2 &interval) const
	Determines whether this set overlaps with the argument.

template<class Interval2 >
bool	overlaps (const IntervalSet< Interval2 > &other) const
	Determines whether this set overlaps with the argument.

template<class Interval2 >
bool	isOverlapping (const IntervalSet< Interval2 > &other) const
	Determines whether this set overlaps with the argument.

template<class Interval2 , class T2 , class Policy2 >
bool	overlaps (const IntervalMap< Interval2, T2, Policy2 > &other) const
	Determines whether this set overlaps with the argument.

template<class Interval2 , class T2 , class Policy2 >
bool	isOverlapping (const IntervalMap< Interval2, T2, Policy2 > &other) const
	Determines whether this set overlaps with the argument.


template<class Interval2 >
bool	isDistinct (const Interval2 &interval) const
	Determines whether this set is distinct from the argument.

template<class Interval2 >
bool	isDistinct (const IntervalSet< Interval2 > &other) const
	Determines whether this set is distinct from the argument.

template<class Interval2 , class T2 , class Policy2 >
bool	isDistinct (const IntervalMap< Interval2, T2, Policy2 > &other) const
	Determines whether this set is distinct from the argument.


bool	contains (const typename Interval::Value &scalar) const
	Determines whether this set fully contains the argument.

template<class Interval2 >
bool	contains (const Interval2 &interval) const
	Determines whether this set fully contains the argument.

template<class Interval2 >
bool	contains (const IntervalSet< Interval2 > &other) const
	Determines whether this set fully contains the argument.

template<class Interval2 , class T2 , class Policy2 >
bool	contains (const IntervalMap< Interval2, T2, Policy2 > &other) const
	Determines whether this set fully contains the argument.


template<class Interval2 >
void	insert (const Interval2 &interval)
	Insert specified values.

template<class Interval2 >
void	insertMultiple (const IntervalSet< Interval2 > &other)
	Insert specified values.

template<class Interval2 , class T , class Policy >
void	insertMultiple (const IntervalMap< Interval2, T, Policy > &other)
	Insert specified values.


template<class Interval2 >
void	erase (const Interval2 &interval)
	Remove specified values.

template<class Interval2 >
void	eraseMultiple (const IntervalSet< Interval2 > &other)
	Remove specified values.

template<class Interval2 , class T , class Policy >
void	eraseMultiple (const IntervalMap< Interval2, T, Policy > &other)
	Remove specified values.


template<class Interval2 >
void	intersect (const Interval2 &interval)
	Interset with specified values.

template<class Interval2 >
void	intersect (IntervalSet< Interval2 > other)
	Interset with specified values.

template<class Interval2 , class T , class Policy >
void	intersect (const IntervalMap< Interval2, T, Policy > &other)
	Interset with specified values.


IntervalSet &	operator\|= (const IntervalSet &other)
	In-place union.

IntervalSet &	operator+= (const IntervalSet &other)
	In-place union.


IntervalSet &	operator\|= (const Interval &interval)
	In-place union with interval.

IntervalSet &	operator+= (const Interval &interval)
	In-place union with interval.


IntervalSet	operator\| (const IntervalSet &other) const
	Union of two sets.

IntervalSet	operator+ (const IntervalSet &other) const
	Union of two sets.


IntervalSet	operator\| (const Interval &interval) const
	Union of set with interval.

IntervalSet	operator+ (const Interval &interval) const
	Union of set with interval.

Member Typedef Documentation

◆ Interval

template<class I >

typedef I Sawyer::Container::IntervalSet::Interval

Definition at line 80 of file IntervalSet.h.

◆ Scalar

template<class I >

typedef I::Value Sawyer::Container::IntervalSet::Scalar

Type of scalar values stored in this set.

Definition at line 81 of file IntervalSet.h.

Constructor & Destructor Documentation

◆ IntervalSet() [1/4]

template<class I >

Sawyer::Container::IntervalSet::IntervalSet ( )

inline

Default constructor.

Creates an empty set.

Definition at line 158 of file IntervalSet.h.

◆ IntervalSet() [2/4]

template<class I >

template<class Interval2 >

Sawyer::Container::IntervalSet::IntervalSet ( const IntervalSet< Interval2 > & other )

inline

Copy constructor.

The newly constructed set will contain copies of the nodes from other.

Definition at line 164 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalSet::intervals().

◆ IntervalSet() [3/4]

template<class I >

template<class Interval2 , class T , class Policy >

Sawyer::Container::IntervalSet::IntervalSet ( const IntervalMap< Interval2, T, Policy > & other )

inlineexplicit

Construct from an IntervalMap.

The newly constructed set will contain copies of the intervals from the specified IntervalMap. The map's intervals must be convertible to the set's interval type. The map's values are not used.

Definition at line 175 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

◆ IntervalSet() [4/4]

template<class I >

template<class Iterator >

Sawyer::Container::IntervalSet::IntervalSet ( const boost::iterator_range< Iterator > & intervals )

inline

Construct from an iterator range.

The newly constructed set will contain copies of the intervals from the specified iterator range. The range's dereferenced iterators must be convertible to the set's interval type.

Definition at line 186 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalSet::intervals().

Member Function Documentation

◆ operator=() [1/3]

template<class I >

template<class Interval2 >

IntervalSet & Sawyer::Container::IntervalSet::operator= ( const IntervalSet< Interval2 > & other )

inline

Assignment from another set.

Causes this set to contain the same intervals as the other set. The other set's intervals must be convertible to this set's interval type.

Definition at line 196 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::clear(), Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalSet::intervals().

◆ operator=() [2/3]

template<class I >

template<class Interval2 , class T , class Policy >

IntervalSet & Sawyer::Container::IntervalSet::operator= ( const IntervalMap< Interval2, T, Policy > & other )

inline

Assignment from an IntervalMap.

Causes this set to contain the same intervals as the specified map. The map's intervals must be convertible to this set's interval type. Since sets and maps have different requirements regarding merging of neighboring intervals, the returned container might not have node-to-node correspondence with the map, but both will contain the same logical intervals.

Definition at line 211 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::clear(), Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

◆ operator=() [3/3]

template<class I >

template<class Iterator >

IntervalSet & Sawyer::Container::IntervalSet::operator= ( const boost::iterator_range< Iterator > & intervals )

inline

Assignment from an iterator range.

The newly constructed set will contain copies of the intervals from the specified iterator range. The range's dereferenced iterators must be convertible to the set's interval type.

Definition at line 224 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::clear(), Sawyer::Container::IntervalSet::insert(), and Sawyer::Container::IntervalSet::intervals().

◆ intervals()

template<class I >

boost::iterator_range< ConstIntervalIterator > Sawyer::Container::IntervalSet::intervals ( ) const

inline

Iterator range for all intervals actually stored by this set.

Definition at line 236 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

◆ scalars()

template<class I >

boost::iterator_range< ConstScalarIterator > Sawyer::Container::IntervalSet::scalars ( ) const

inline

Iterator range for all scalar values logically represented by this set.

Definition at line 242 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intervals().

◆ lowerBound()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet::lowerBound ( const typename Interval::Value & scalar ) const

inline

Find the first node whose interval ends at or above the specified scalar key.

Returns an iterator to the node, or the end iterator if no such node exists.

Definition at line 250 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound().

◆ upperBound()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet::upperBound ( const typename Interval::Value & scalar ) const

inline

Find the first node whose interval begins above the specified scalar key.

Returns an iterator to the node, or the end iterator if no such node exists.

Definition at line 257 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::upperBound().

◆ findPrior()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet::findPrior ( const typename Interval::Value & scalar ) const

inline

Find the last node whose interval starts at or below the specified scalar key.

Returns an iterator to the node, or the end iterator if no such node exists.

Definition at line 264 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findPrior().

◆ find()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet::find ( const typename Interval::Value & scalar ) const

inline

Find the node containing the specified scalar key.

Returns an iterator to the matching node, or the end iterator if no such node exists.

Definition at line 271 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::find().

Referenced by Sawyer::Container::IntervalSet::exists().

◆ findAll()

template<class I >

boost::iterator_range< ConstIntervalIterator > Sawyer::Container::IntervalSet::findAll ( const Interval & interval ) const

inline

Finds all nodes overlapping the specified interval.

Returns an iterator range that enumerates the nodes that overlap with the specified interval.

Definition at line 278 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findAll().

◆ findFirstOverlap() [1/2]

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet::findFirstOverlap ( const Interval & interval ) const

inline

Finds first node that overlaps with the specified interval.

Returns an iterator to the matching node, or the end iterator if no such node exists.

Definition at line 287 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap().

◆ findFirstOverlap() [2/2]

template<class I >

std::pair< ConstIntervalIterator, ConstIntervalIterator > Sawyer::Container::IntervalSet< I >::findFirstOverlap	(	ConstIntervalIterator	thisIter,
		const IntervalSet< I > &	other,
		ConstIntervalIterator	otherIter
	)		const

inline

Find first nodes that overlap.

Given two ranges of iterators for two sets, advance the iterators to the closest nodes that overlap with each other, and return the result as two iterators. If no overlaps can be found then the return value is two end iterators.

Definition at line 296 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap().

◆ isEmpty()

template<class I >

bool Sawyer::Container::IntervalSet::isEmpty ( ) const

inline

Determine whether the container is empty.

Returns true only if this set contains no elements.

Definition at line 309 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty().

Referenced by Sawyer::Container::IntervalSet::greatest(), Sawyer::Container::IntervalSet::intersect(), and Sawyer::Container::IntervalSet::least().

◆ size()

template<class I >

Interval::Value Sawyer::Container::IntervalSet::size ( ) const

inline

Number of scalar elements represented.

Returns the number of scalar elements (not intervals or storage nodes) contained in this set. Since the return type is the same as the type used in the interval end points, this function can return overflowed values. For instance, a set that contains all possible values in the value space is likely to return zero.

Definition at line 318 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::size().

Referenced by Sawyer::Container::IntervalSet::bestFit(), and Sawyer::Container::IntervalSet::firstFit().

◆ nIntervals()

template<class I >

size_t Sawyer::Container::IntervalSet::nIntervals ( ) const

inline

Number of storage nodes.

Returns the number of nodes stored in this container, which for sets is always the number of maximally contiguous intervals. Most algorithms employed by IntervalSet methods are either logarithmic or scalar in this number.

Definition at line 326 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::nIntervals().

Referenced by Sawyer::Container::IntervalSet::operator&(), and Sawyer::Container::IntervalSet::operator|().

◆ hull()

template<class I >

Interval Sawyer::Container::IntervalSet::hull ( ) const

inline

Returns the range of values in this map.

Definition at line 331 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::hull().

Referenced by Sawyer::Container::IntervalSet::intersect(), and Sawyer::Container::IntervalSet::intersect().

◆ overlaps() [1/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::overlaps ( const Interval2 & interval ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 345 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet::isDistinct(), Sawyer::Container::IntervalSet::isDistinct(), Sawyer::Container::IntervalSet::isDistinct(), Sawyer::Container::IntervalSet::isOverlapping(), Sawyer::Container::IntervalSet::isOverlapping(), and Sawyer::Container::IntervalSet::isOverlapping().

◆ isOverlapping() [1/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::isOverlapping ( const Interval2 & interval ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 349 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ overlaps() [2/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::overlaps ( const IntervalSet< Interval2 > & other ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 354 of file IntervalSet.h.

◆ isOverlapping() [2/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::isOverlapping ( const IntervalSet< Interval2 > & other ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 358 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ overlaps() [3/3]

template<class I >

template<class Interval2 , class T2 , class Policy2 >

bool Sawyer::Container::IntervalSet::overlaps ( const IntervalMap< Interval2, T2, Policy2 > & other ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 363 of file IntervalSet.h.

◆ isOverlapping() [3/3]

template<class I >

template<class Interval2 , class T2 , class Policy2 >

bool Sawyer::Container::IntervalSet::isOverlapping ( const IntervalMap< Interval2, T2, Policy2 > & other ) const

inline

Determines whether this set overlaps with the argument.

Returns true if this set contains any values that are also present in the argument.

Definition at line 367 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ isDistinct() [1/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::isDistinct ( const Interval2 & interval ) const

inline

Determines whether this set is distinct from the argument.

Returns true if none of the values of this set are equal to any value in the argument.

Definition at line 378 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ isDistinct() [2/3]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::isDistinct ( const IntervalSet< Interval2 > & other ) const

inline

Determines whether this set is distinct from the argument.

Returns true if none of the values of this set are equal to any value in the argument.

Definition at line 383 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ isDistinct() [3/3]

template<class I >

template<class Interval2 , class T2 , class Policy2 >

bool Sawyer::Container::IntervalSet::isDistinct ( const IntervalMap< Interval2, T2, Policy2 > & other ) const

inline

Determines whether this set is distinct from the argument.

Returns true if none of the values of this set are equal to any value in the argument.

Definition at line 388 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::overlaps().

◆ exists()

template<class I >

bool Sawyer::Container::IntervalSet::exists ( const typename Interval::Value & scalar ) const

inline

Determines if a value exists in the set.

Returns true if the specified value is a member of the set.

Definition at line 396 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::find(), and Sawyer::Container::IntervalSet::intervals().

Referenced by Sawyer::Container::IntervalSet::contains().

◆ contains() [1/4]

template<class I >

bool Sawyer::Container::IntervalSet::contains ( const typename Interval::Value & scalar ) const

inline

Determines whether this set fully contains the argument.

Returns true if this set contains all values represented by the argument.

Definition at line 405 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::exists().

◆ contains() [2/4]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::contains ( const Interval2 & interval ) const

inline

Determines whether this set fully contains the argument.

Returns true if this set contains all values represented by the argument.

Definition at line 410 of file IntervalSet.h.

◆ contains() [3/4]

template<class I >

template<class Interval2 >

bool Sawyer::Container::IntervalSet::contains ( const IntervalSet< Interval2 > & other ) const

inline

Determines whether this set fully contains the argument.

Returns true if this set contains all values represented by the argument.

Definition at line 415 of file IntervalSet.h.

◆ contains() [4/4]

template<class I >

template<class Interval2 , class T2 , class Policy2 >

bool Sawyer::Container::IntervalSet::contains ( const IntervalMap< Interval2, T2, Policy2 > & other ) const

inline

Determines whether this set fully contains the argument.

Returns true if this set contains all values represented by the argument.

Definition at line 420 of file IntervalSet.h.

◆ least() [1/2]

template<class I >

Scalar Sawyer::Container::IntervalSet::least ( ) const

inline

Returns the minimum scalar contained in this set.

Definition at line 430 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::isEmpty(), and Sawyer::Container::IntervalMap< I, T, Policy >::least().

Referenced by Sawyer::Container::IntervalSet::intersect(), and Sawyer::Container::IntervalSet::invert().

◆ greatest() [1/2]

template<class I >

Scalar Sawyer::Container::IntervalSet::greatest ( ) const

inline

Returns the maximum scalar contained in this set.

Definition at line 436 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::greatest(), and Sawyer::Container::IntervalSet::isEmpty().

Referenced by Sawyer::Container::IntervalSet::intersect().

◆ least() [2/2]

template<class I >

Optional< Scalar > Sawyer::Container::IntervalSet::least ( Scalar lowerLimit ) const

inline

Returns the limited-minimum scalar contained in this set.

Returns the minimum scalar that exists in this set and which is greater than or equal to lowerLimit. If no such value exists then nothing is returned.

Definition at line 445 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::least().

◆ greatest() [2/2]

template<class I >

Optional< Scalar > Sawyer::Container::IntervalSet::greatest ( Scalar upperLimit ) const

inline

Returns the limited-maximum scalar contained in this set.

Returns the maximum scalar that exists in this set and which is less than or equal to upperLimit. If no such value exists then nothing is returned.

Definition at line 453 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::greatest().

◆ leastNonExistent()

template<class I >

Optional< Scalar > Sawyer::Container::IntervalSet::leastNonExistent ( Scalar lowerLimit ) const

inline

Returns the limited-minimum scalar not contained in this set.

Returns the minimum scalar equal to or greater than the lowerLimit which is not in this set. If no such value exists then nothing is returned.

Definition at line 461 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::leastUnmapped().

◆ greatestNonExistent()

template<class I >

Optional< Scalar > Sawyer::Container::IntervalSet::greatestNonExistent ( Scalar upperLimit ) const

inline

Returns the limited-maximum scalar not contained in this set.

Returns the maximum scalar equal to or less than the upperLimit which is not in this set. If no such value exists then nothing is returned.

Definition at line 469 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::greatestUnmapped().

◆ firstFit()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet< I >::firstFit	(	const typename Interval::Value &	size,
		ConstIntervalIterator	start
	)		const

inline

Find the first fit node at or after a starting point.

Finds the first node of contiguous values beginning at or after the specified starting iterator, start, and which is at least as large as the desired size. If there are no such nodes then the end iterator is returned.

Caveat emptor: The size argument has the name type as the interval end points. If the end points have a signed type, then it is entirely likely that the size will overflow. In fact, it is also possible that unsigned sizes overflow since, for example, an 8-bit unsigned size cannot hold the size of an interval representing the entire 8-bit space. Therefore, use this method with care.

Definition at line 482 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::firstFit(), and Sawyer::Container::IntervalSet::size().

◆ bestFit()

template<class I >

ConstIntervalIterator Sawyer::Container::IntervalSet< I >::bestFit	(	const typename Interval::Value &	size,
		ConstIntervalIterator	start
	)		const

inline

Find the best fit node at or after a starting point.

Finds a node of contiguous values beginning at or after the specified starting iterator, start, and which is at least as large as the desired size. If there is more than one such node, then the first smallest such node is returned. If there are no such nodes then the end iterator is returned.

Caveat emptor: The size argument has the name type as the interval end points. If the end points have a signed type, then it is entirely likely that the size will overflow. In fact, it is also possible that unsigned sizes overflow since, for example, an 8-bit unsigned size cannot hold the size of an interval representing the entire 8-bit space. Therefore, use this method with care.

Definition at line 496 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::bestFit(), and Sawyer::Container::IntervalSet::size().

◆ clear()

template<class I >

void Sawyer::Container::IntervalSet::clear ( )

inline

Remove all values.

All values are removed from this set and the set becomes empty.

Definition at line 509 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::clear().

Referenced by Sawyer::Container::IntervalSet::intersect(), Sawyer::Container::IntervalSet::operator=(), Sawyer::Container::IntervalSet::operator=(), and Sawyer::Container::IntervalSet::operator=().

◆ invert() [1/2]

template<class I >

void Sawyer::Container::IntervalSet::invert ( )

inline

Invert.

Invert this set in place.

Definition at line 516 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::invert(), and Sawyer::Container::Interval< T >::whole().

Referenced by Sawyer::Container::IntervalSet::intersect(), Sawyer::Container::IntervalSet::invert(), Sawyer::Container::AddressMap< A, T >::keep(), and Sawyer::Container::IntervalSet::operator~().

◆ invert() [2/2]

template<class I >

void Sawyer::Container::IntervalSet::invert ( const Interval & restricted )

inline

Invert and intersect.

Inverts this set and then intersects it with restricted.

Definition at line 523 of file IntervalSet.h.

References Sawyer::Container::Interval< T >::hull(), Sawyer::Container::IntervalSet::insert(), Sawyer::Container::IntervalMap< I, T, Policy >::intervals(), Sawyer::Container::IntervalSet::least(), and Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound().

◆ insert()

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::insert ( const Interval2 & interval )

inline

Insert specified values.

The values can be specified by a interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 554 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::insert().

◆ insertMultiple() [1/2]

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::insertMultiple ( const IntervalSet< Interval2 > & other )

inline

Insert specified values.

The values can be specified by a interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 559 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::insert(), and Sawyer::Container::IntervalSet::intervals().

Referenced by Sawyer::Container::IntervalSet::operator+=(), Sawyer::Container::IntervalSet::operator|(), and Sawyer::Container::IntervalSet::operator|=().

◆ insertMultiple() [2/2]

template<class I >

template<class Interval2 , class T , class Policy >

void Sawyer::Container::IntervalSet::insertMultiple ( const IntervalMap< Interval2, T, Policy > & other )

inline

Insert specified values.

The values can be specified by a interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 566 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::insert(), and Sawyer::Container::IntervalMap< I, T, Policy >::intervals().

◆ erase()

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::erase ( const Interval2 & interval )

inline

Remove specified values.

The values can be specified by an interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 580 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::erase().

Referenced by Sawyer::Container::IntervalSet::operator-(), and Sawyer::Container::IntervalSet::operator-=().

◆ eraseMultiple() [1/2]

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::eraseMultiple ( const IntervalSet< Interval2 > & other )

inline

Remove specified values.

The values can be specified by an interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 585 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::erase(), and Sawyer::Container::IntervalSet::intervals().

Referenced by Sawyer::Container::IntervalSet::operator-(), and Sawyer::Container::IntervalSet::operator-=().

◆ eraseMultiple() [2/2]

template<class I >

template<class Interval2 , class T , class Policy >

void Sawyer::Container::IntervalSet::eraseMultiple ( const IntervalMap< Interval2, T, Policy > & other )

inline

Remove specified values.

The values can be specified by an interval (or scalar if the interval has an implicit constructor), another set whose interval type is convertible to this set's interval type, or an IntervalMap whose intervals are convertible.

Definition at line 593 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::erase(), and Sawyer::Container::IntervalMap< I, T, Policy >::intervals().

◆ intersect() [1/3]

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::intersect ( const Interval2 & interval )

inline

Interset with specified values.

Computes in place intersection of this container with the specified argument. The argument may be an interval (or scalar if the interval has an implicit constructor), or another set whose interval type is convertible to this set's interval type.

Definition at line 608 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::clear(), Sawyer::Container::IntervalMap< I, T, Policy >::erase(), Sawyer::Container::IntervalSet::greatest(), Sawyer::Container::IntervalSet::hull(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::IntervalSet::isEmpty(), and Sawyer::Container::IntervalSet::least().

Referenced by Sawyer::Container::IntervalSet::operator&(), Sawyer::Container::IntervalSet::operator&(), Sawyer::Container::IntervalSet::operator&=(), and Sawyer::Container::IntervalSet::operator&=().

◆ intersect() [2/3]

template<class I >

template<class Interval2 >

void Sawyer::Container::IntervalSet::intersect ( IntervalSet< Interval2 > other )

inline

Interset with specified values.

Computes in place intersection of this container with the specified argument. The argument may be an interval (or scalar if the interval has an implicit constructor), or another set whose interval type is convertible to this set's interval type.

Definition at line 622 of file IntervalSet.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::eraseMultiple(), Sawyer::Container::IntervalSet::hull(), and Sawyer::Container::IntervalSet::invert().

◆ intersect() [3/3]

template<class I >

template<class Interval2 , class T , class Policy >

void Sawyer::Container::IntervalSet::intersect ( const IntervalMap< Interval2, T, Policy > & other )

Interset with specified values.

Computes in place intersection of this container with the specified argument. The argument may be an interval (or scalar if the interval has an implicit constructor), or another set whose interval type is convertible to this set's interval type.

◆ operator==()

template<class I >

bool Sawyer::Container::IntervalSet::operator== ( const IntervalSet & other ) const

inline

Determines if two sets contain the same elements.

Definition at line 637 of file IntervalSet.h.

◆ operator!=()

template<class I >

bool Sawyer::Container::IntervalSet::operator!= ( const IntervalSet & other ) const

inline

Determines if two sets contain different elements.

Definition at line 642 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intervals(), and Sawyer::Container::IntervalMap< I, T, Policy >::nIntervals().

◆ operator~()

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator~ ( ) const

inline

Return inverse of specified set.

Definition at line 653 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::invert().

◆ operator|=() [1/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator|= ( const IntervalSet & other )

inline

In-place union.

Inserts the members of other set into this set.

Definition at line 664 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insertMultiple().

◆ operator+=() [1/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator+= ( const IntervalSet & other )

inline

In-place union.

Inserts the members of other set into this set.

Definition at line 669 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insertMultiple().

◆ operator|=() [2/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator|= ( const Interval & interval )

inline

In-place union with interval.

Inserts the interval into this set.

Definition at line 680 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert().

◆ operator+=() [2/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator+= ( const Interval & interval )

inline

In-place union with interval.

Inserts the interval into this set.

Definition at line 685 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert().

◆ operator|() [1/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator| ( const IntervalSet & other ) const

inline

Union of two sets.

Definition at line 694 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insertMultiple(), and Sawyer::Container::IntervalSet::nIntervals().

◆ operator+() [1/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator+ ( const IntervalSet & other ) const

inline

Union of two sets.

Definition at line 705 of file IntervalSet.h.

◆ operator|() [2/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator| ( const Interval & interval ) const

inline

Union of set with interval.

It's probably more efficient to insert the interval in place, but this method is sometimes convenient.

Definition at line 715 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::insert().

◆ operator+() [2/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator+ ( const Interval & interval ) const

inline

Union of set with interval.

It's probably more efficient to insert the interval in place, but this method is sometimes convenient.

Definition at line 721 of file IntervalSet.h.

◆ operator&=() [1/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator&= ( const IntervalSet & other )

inline

In-place intersection.

Modifies this set so it contains only those members that are also in the other set.

Definition at line 729 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intersect().

◆ operator&=() [2/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator&= ( const Interval & interval )

inline

In-place intersection with an interval.

Modifies this set so it contains only those members that are also in interval.

Definition at line 737 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intersect().

◆ operator&() [1/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator& ( const IntervalSet & other ) const

inline

Intersection of two sets.

Definition at line 743 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intersect(), and Sawyer::Container::IntervalSet::nIntervals().

◆ operator&() [2/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator& ( const Interval & interval ) const

inline

Intersection of set with interval.

Definition at line 755 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::intersect().

◆ operator-=() [1/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator-= ( const IntervalSet & other )

inline

In-place subtraction.

Subtracts from this set those members of the other set.

Definition at line 764 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::eraseMultiple().

◆ operator-=() [2/2]

template<class I >

IntervalSet & Sawyer::Container::IntervalSet::operator-= ( const Interval & interval )

inline

In-place subtraction of an interval.

Removes the specified interval of values from this set.

Definition at line 772 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::erase().

◆ operator-() [1/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator- ( const IntervalSet & other ) const

inline

Subtract another set from this one.

A-B is equivalent to A & ~B but perhaps faster.

Definition at line 780 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::eraseMultiple().

◆ operator-() [2/2]

template<class I >

IntervalSet Sawyer::Container::IntervalSet::operator- ( const Interval & interval ) const

inline

Subtract an interval from this set.

Definition at line 787 of file IntervalSet.h.

References Sawyer::Container::IntervalSet::erase().

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

IntervalSet.h

Description

Classes

Public Types

Public Member Functions

Member Typedef Documentation

◆ Interval

◆ Scalar

Constructor & Destructor Documentation

◆ IntervalSet() [1/4]

◆ IntervalSet() [2/4]

◆ IntervalSet() [3/4]

◆ IntervalSet() [4/4]

Member Function Documentation

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ intervals()

◆ scalars()

◆ lowerBound()

◆ upperBound()

◆ findPrior()

◆ find()

◆ findAll()

◆ findFirstOverlap() [1/2]

◆ findFirstOverlap() [2/2]

◆ isEmpty()

◆ size()

◆ nIntervals()

◆ hull()

◆ overlaps() [1/3]

◆ isOverlapping() [1/3]

◆ overlaps() [2/3]

◆ isOverlapping() [2/3]

◆ overlaps() [3/3]

◆ isOverlapping() [3/3]

◆ isDistinct() [1/3]

◆ isDistinct() [2/3]

◆ isDistinct() [3/3]

◆ exists()

◆ contains() [1/4]

◆ contains() [2/4]

◆ contains() [3/4]

◆ contains() [4/4]

◆ least() [1/2]

◆ greatest() [1/2]

◆ least() [2/2]

◆ greatest() [2/2]

◆ leastNonExistent()

◆ greatestNonExistent()

◆ firstFit()

◆ bestFit()

◆ clear()

◆ invert() [1/2]

◆ invert() [2/2]

◆ insert()

◆ insertMultiple() [1/2]

◆ insertMultiple() [2/2]

◆ erase()

◆ eraseMultiple() [1/2]

◆ eraseMultiple() [2/2]

◆ intersect() [1/3]

◆ intersect() [2/3]

◆ intersect() [3/3]

◆ operator==()

◆ operator!=()

◆ operator~()

◆ operator|=() [1/2]

◆ operator+=() [1/2]

◆ operator|=() [2/2]

◆ operator+=() [2/2]

◆ operator|() [1/2]

◆ operator+() [1/2]

◆ operator|() [2/2]

◆ operator+() [2/2]

◆ operator&=() [1/2]

◆ operator&=() [2/2]

◆ operator&() [1/2]

◆ operator&() [2/2]

◆ operator-=() [1/2]

◆ operator-=() [2/2]