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;
BOOST_FOREACH (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 55 of file IntervalSet.h.

#include <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. More...

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

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

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

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

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

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

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. More...

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

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

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

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

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

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

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

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

size_t	nIntervals () const
	Number of storage nodes. More...

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. More...

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. More...

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

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

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

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

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

void	clear ()
	Remove all values. More...

void	invert ()
	Invert. More...

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

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 union. More...

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

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

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

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

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

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. More...

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

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

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


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

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

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


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

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

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. More...


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

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

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

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


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

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

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


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

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

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


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

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

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

Constructor & Destructor Documentation

◆ IntervalSet() [1/4]

template<class I >

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

inline

Default constructor.

Creates an empty set.

Definition at line 147 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 153 of file IntervalSet.h.

◆ 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 164 of file IntervalSet.h.

◆ 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 175 of file IntervalSet.h.

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 185 of file IntervalSet.h.

◆ 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 200 of file IntervalSet.h.

◆ 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 213 of file IntervalSet.h.

◆ 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 239 of file IntervalSet.h.

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

◆ 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 253 of file IntervalSet.h.

◆ 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 260 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::exists().

Here is the caller graph for this function:

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

◆ 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 276 of file IntervalSet.h.

◆ 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 286 of file IntervalSet.h.

◆ 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 299 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 308 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 316 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 335 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::isDistinct().

Here is the caller graph for this function:

◆ 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 340 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 345 of file IntervalSet.h.

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

◆ 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 361 of file IntervalSet.h.

◆ 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 366 of file IntervalSet.h.

◆ 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 374 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::contains().

Here is the caller graph for this function:

◆ 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 383 of file IntervalSet.h.

◆ 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 388 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 393 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 398 of file IntervalSet.h.

◆ least()

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

◆ greatest()

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 431 of file IntervalSet.h.

◆ 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 439 of file IntervalSet.h.

◆ 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 447 of file IntervalSet.h.

◆ 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 460 of file IntervalSet.h.

◆ 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 474 of file IntervalSet.h.

◆ 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 487 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ invert() [1/2]

template<class I >

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

inline

Invert.

Invert this set in place.

Definition at line 494 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 501 of file IntervalSet.h.

◆ 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 532 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::IntervalSet(), Sawyer::Container::IntervalSet< Interval >::invert(), Sawyer::Container::AddressMap< A, T >::keep(), Sawyer::Container::IntervalSet< Interval >::operator=(), Sawyer::Container::IntervalSet< Interval >::operator|(), Sawyer::Container::IntervalSet< Interval >::operator|=(), and Sawyer::Container::AddressMap< A, T >::prune().

Here is the caller graph for this function:

◆ 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 537 of file IntervalSet.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::operator|(), and Sawyer::Container::IntervalSet< Interval >::operator|=().

Here is the caller graph for this function:

◆ 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 544 of file IntervalSet.h.

◆ 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 558 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 563 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 571 of file IntervalSet.h.

◆ 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 586 of file IntervalSet.h.

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

Here is the caller graph for this function:

◆ 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 600 of file IntervalSet.h.

◆ 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|=() [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 640 of file IntervalSet.h.

◆ 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 648 of file IntervalSet.h.

◆ operator|()

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 668 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 677 of file IntervalSet.h.

◆ 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 685 of file IntervalSet.h.

◆ 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 712 of file IntervalSet.h.

◆ 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 720 of file IntervalSet.h.

◆ operator-()

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 728 of file IntervalSet.h.

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

IntervalSet.h

Description

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

Classes

Public Types

Public Member Functions

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]

◆ lowerBound()

◆ upperBound()

◆ findPrior()

◆ find()

◆ findAll()

◆ findFirstOverlap() [1/2]

◆ findFirstOverlap() [2/2]

◆ isEmpty()

◆ size()

◆ nIntervals()

◆ isOverlapping() [1/3]

◆ isOverlapping() [2/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()

◆ greatest()

◆ 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|=() [1/2]

◆ operator|=() [2/2]

◆ operator|()

◆ operator&=() [1/2]

◆ operator&=() [2/2]

◆ operator-=() [1/2]

◆ operator-=() [2/2]

◆ operator-()

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