Description

template<typename I, typename T, class Policy = MergePolicy<I, T>>
class Sawyer::Container::IntervalMap< I, T, Policy >

An associative container whose keys are non-overlapping intervals.

This container is somewhat like an STL std::map in that it stores key/value pairs. However, it is optimized for the case when many consecutive keys are the same or related. The values may be any type; the keys are any interval type that follows the API and semantics of Sawyer::Container::Interval, namely a closed interval with members least and greatest demarcating the inclusive end points, and a few other methods.

The interval/value pair nodes that are stored in this container are managed by the container, automatically joining adjacent nodes when they are inserted, if possible and permitted, and automatically spliting nodes if necessary when something is erased. For the most part, the user can think of this container as associating scalar keys with values, and almost forget that the container uses intervals as an optimization.

When two neighboring interval/value nodes are inserted, the container will possibly join them into a single interval/value node. Normally, the merging of two nodes happens if the two values are equal, but this can be influenced by a policy class provided as an argument of the container's constructor. See MergePolicy for details. Similarly, when part of an interval is erased, the container might need to split the affected node into two nodes, which is also handled by the policy.

The following examples demonstrates some aspects of the interface:

typedef Sawyer::Container::Interval<unsigned> Interval; // integral types work best
class Stats {...} stats1=..., stats2=...; // needs at least a copy c'tor, assignment, and equality predicate.
typedef IntervalMap<Interval, Stats> Map;
Map map;
map.insert(Interval(1,5), stats1);
map.insert(6, stats2);

If the policy allows the two "stats" objects to be merged (the default policy allows them to merge only if they are equal), then the container will end up having one node, the pair ([1,6], merge(stats1,stats2)), otherwise it will have two nodes.

map.erase(Interval(2,3));

Erasing keys 2 and 3 causes the affected node to split into two discontiguous nodes and a new copy of the node's value. Assuming we started with the two nodes { ([1,5], stats1), (6, stats2) }, then after erasing [2,3] the container will hold three nodes: { (1, stats1), ([4,5], stats1), (6, stats2) }.

Iteration over the container returns references to the nodes as Node object that has key and value methods to access the interval key and user-defined value parts of each storage node. For example, here's one way to print the contents of the container, assuming the interval itself doesn't already have a printing function:

std::cout <<"{";
for (Map::ConstNodeIterator iter=map.nodes().begin(); iter!=map.nodes().end(); ++iter) {
    const Interval &interval = iter->key();
    const Stats &stats = iter->value();
    std::cout <<" (";
    if (interval.isSingleton())
        std::cout <<interval.least() <<", ";
    } else {
        std::cout <<"[" <<interval.least() <<"," <<interval.greatest() <<"], ";
    }
    std::cout <<stats <<")";
}
std::cout <<" }";

Here's another way:

BOOST_FOREACH (const Map::Node &node, map.nodes()) {
    const Interval &interval = node.key();
    const Stats &stats = node.value();
    ...
}

Besides nodes(), there's also values() and intervals() that return bidirectional iterators over the user-defined values or the intervals when dereferenced.

This class uses CamelCase for all its methods and inner types in conformance with the naming convention for the rest of the library. This includes iterator names (we don't use iterator, const_iterator, etc).

See also

See IntervalSetMap for a similar container that stores sets of values per interval.

Definition at line 171 of file IntervalMap.h.

#include <IntervalMap.h>

Inheritance diagram for Sawyer::Container::IntervalMap< I, T, Policy >:

[legend]

Public Types
typedef I	Interval
	Interval type.

typedef T	Value
	Value type.

typedef Container::Map< Interval, Value, IntervalCompare >	Map
	Type of the underlying map.

typedef Map::Node	Node
	Storage node. More...

typedef Map::ConstKeyIterator	ConstIntervalIterator
	Interval iterator. More...


typedef Map::ValueIterator	ValueIterator
	Value iterator. More...

typedef Map::ConstValueIterator	ConstValueIterator
	Value iterator. More...


typedef Map::NodeIterator	NodeIterator
	Node iterator. More...

typedef Map::ConstNodeIterator	ConstNodeIterator
	Node iterator. More...

Public Member Functions
	IntervalMap ()
	Default constructor. More...

template<class Interval2 , class T2 , class Policy2 >
	IntervalMap (const IntervalMap< Interval2, T2, Policy2 > &other)
	Copy constructor. More...

template<class Interval2 , class T2 , class Policy2 >
IntervalMap &	operator= (const IntervalMap< Interval2, T2, Policy2 > &other)
	Assignment operator. More...

boost::iterator_range< ConstIntervalIterator >	intervals () const
	Iterators for traversing keys. More...

Interval	firstUnmapped (typename Interval::Value minAddr) const
	Find the first unmapped region. More...

Interval	lastUnmapped (typename Interval::Value maxAddr) const
	Find the last unmapped region. More...

bool	exists (const typename Interval::Value &size) const
	Returns true if element exists. More...

Optional< Value >	getOptional (const typename Interval::Value &scalar) const
	Lookup and return a value or nothing. More...

const Value &	getOrDefault (const typename Interval::Value &scalar) const
	Lookup and return a value or a default. More...

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

size_t	nIntervals () const
	Number of nodes in the container. More...

Interval::Value	size () const
	Returns the number of values represented by this container. More...

Interval::Value	least () const
	Returns the minimum scalar key.

Interval::Value	greatest () const
	Returns the maximum scalar key.

Optional< typename Interval::Value >	least (typename Interval::Value lowerLimit) const
	Returns the limited-minimum scalar key. More...

Optional< typename Interval::Value >	greatest (typename Interval::Value upperLimit) const
	Returns the limited-maximum scalar key. More...

Optional< typename Interval::Value >	leastUnmapped (typename Interval::Value lowerLimit) const
	Returns the limited-minimum unmapped scalar key. More...

Optional< typename Interval::Value >	greatestUnmapped (typename Interval::Value upperLimit) const
	Returns the limited-maximum unmapped scalar key. More...

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

void	clear ()
	Empties the container.

void	erase (const Interval &erasure)
	Erase the specified interval.

template<typename T2 , class Policy2 >
void	eraseMultiple (const IntervalMap< Interval, T2, Policy2 > &other)
	Erase intervals specified in another IntervalMap. More...

void	insert (Interval key, Value value, bool makeHole=true)
	Insert a key/value pair. More...

template<typename T2 , class Policy2 >
void	insertMultiple (const IntervalMap< Interval, T2, Policy2 > &other, bool makeHole=true)
	Insert values from another container. More...

bool	isOverlapping (const Interval &interval) const

template<typename T2 , class Policy2 >
bool	isOverlapping (const IntervalMap< Interval, T2, Policy2 > &other) const

bool	isDistinct (const Interval &interval) const

template<typename T2 , class Policy2 >
bool	isDistinct (const IntervalMap< Interval, T2, Policy2 > &other) const

bool	contains (Interval key) const

template<typename T2 , class Policy2 >
bool	contains (const IntervalMap< Interval, T2, Policy2 > &other) const


boost::iterator_range< NodeIterator >	nodes ()
	Iterators for traversing nodes. More...

boost::iterator_range< ConstNodeIterator >	nodes () const
	Iterators for traversing nodes. More...


boost::iterator_range< ValueIterator >	values ()
	Iterators for traversing values. More...

boost::iterator_range< ConstValueIterator >	values () const
	Iterators for traversing values. More...


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

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


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

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


const Value &	operator[] (const typename Interval::Value &scalar) const
	Returns a reference to an existing value. More...

const Value &	get (const typename Interval::Value &scalar) const
	Returns a reference to an existing value. More...


Value &	getOrElse (const typename Interval::Value &scalar, Value &dflt)
	Lookup and return a value or something else. More...

const Value &	getOrElse (const typename Interval::Value &scalar, const Value &dflt) const
	Lookup and return a value or something else. More...

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

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

template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	findPriorImpl (IMap &imap, const typename Interval::Value &scalar)
	Find the last node whose interval starts at or below the specified scalar key. More...

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

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

template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	findImpl (IMap &imap, const typename Interval::Value &scalar)
	Find the node containing the specified scalar key. More...

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

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

template<class IMap >
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIterator >	findAllImpl (IMap &imap, const Interval &interval)
	Finds all nodes overlapping the specified interval. More...

NodeIterator	findFirstOverlap (const Interval &interval)
	Find first interval that overlaps with the specified interval. More...

ConstNodeIterator	findFirstOverlap (const Interval &interval) const
	Find first interval that overlaps with the specified interval. More...

template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	findFirstOverlapImpl (IMap &imap, const Interval &interval)
	Find first interval that overlaps with the specified interval. More...

template<typename T2 , class Policy2 >
std::pair< NodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator >	findFirstOverlap (typename IntervalMap::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter)
	Find first interval that overlaps with any in another container. More...

template<typename T2 , class Policy2 >
std::pair< ConstNodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator >	findFirstOverlap (typename IntervalMap::ConstNodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter) const
	Find first interval that overlaps with any in another container. More...

template<class IMap , typename T2 , class Policy2 >
static std::pair< typename IntervalMapTraits< IMap >::NodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator >	findFirstOverlapImpl (IMap &imap, typename IntervalMapTraits< IMap >::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter)
	Find first interval that overlaps with any in another container. More...

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

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

template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	firstFitImpl (IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits< IMap >::NodeIterator start)
	Find the first fit node at or after a starting point. More...

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

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

template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	bestFitImpl (IMap &imap, const typename Interval::Value &size, typename IntervalMapTraits< IMap >::NodeIterator start)
	Find the best fit node at or after a starting point. More...

Member Typedef Documentation

◆ Node

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::Node Sawyer::Container::IntervalMap< I, T, Policy >::Node

Storage node.

An interval/value pair with methods key and value for accessing the interval key and its associated user-defined value.

Definition at line 196 of file IntervalMap.h.

◆ ConstIntervalIterator

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::ConstKeyIterator Sawyer::Container::IntervalMap< I, T, Policy >::ConstIntervalIterator

Interval iterator.

This iterator visits the intervals of the container. Dereferencing the iterator returns a reference to a const interval.

Definition at line 202 of file IntervalMap.h.

◆ ValueIterator

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::ValueIterator Sawyer::Container::IntervalMap< I, T, Policy >::ValueIterator

Value iterator.

This iterator visits the values of the container. Dereferencing the iterator returns a reference (const or mutable, depending on the iterator) to a user-defined value.

Definition at line 210 of file IntervalMap.h.

◆ ConstValueIterator

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::ConstValueIterator Sawyer::Container::IntervalMap< I, T, Policy >::ConstValueIterator

Value iterator.

This iterator visits the values of the container. Dereferencing the iterator returns a reference (const or mutable, depending on the iterator) to a user-defined value.

Definition at line 211 of file IntervalMap.h.

◆ NodeIterator

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::NodeIterator

Node iterator.

This iterator visits the nodes of the container. Dereferencing the iterator returns a Node reference (const or mutable depending on the iterator), from which the interval key and user-define value can be obtained.

Definition at line 220 of file IntervalMap.h.

◆ ConstNodeIterator

template<typename I , typename T , class Policy = MergePolicy<I, T>>

typedef Map::ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::ConstNodeIterator

Node iterator.

This iterator visits the nodes of the container. Dereferencing the iterator returns a Node reference (const or mutable depending on the iterator), from which the interval key and user-define value can be obtained.

Definition at line 221 of file IntervalMap.h.

Constructor & Destructor Documentation

◆ IntervalMap() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

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

inline

Default constructor.

Creates an empty container.

Definition at line 246 of file IntervalMap.h.

◆ IntervalMap() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class Interval2 , class T2 , class Policy2 >

Sawyer::Container::IntervalMap< I, T, Policy >::IntervalMap ( const IntervalMap< Interval2, T2, Policy2 > & other )

inline

Copy constructor.

Initialize this container by copying all nodes from the other container. This constructor has O(n) complexity, where n is the number of nodes in the container.

Definition at line 253 of file IntervalMap.h.

Member Function Documentation

◆ operator=()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class Interval2 , class T2 , class Policy2 >

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

inline

Assignment operator.

Makes this container look like the other container by clearing this container and then copying all nodes from the other container.

Definition at line 264 of file IntervalMap.h.

◆ nodes() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<NodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::nodes ( )

inline

Iterators for traversing nodes.

Returns a range of iterators that traverse storage nodes (key/value pairs) for all nodes of this container. The nodes are traversed in key order.

Definition at line 283 of file IntervalMap.h.

Here is the caller graph for this function:

◆ nodes() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<ConstNodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::nodes ( ) const

inline

Iterators for traversing nodes.

Returns a range of iterators that traverse storage nodes (key/value pairs) for all nodes of this container. The nodes are traversed in key order.

Definition at line 284 of file IntervalMap.h.

◆ intervals()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<ConstIntervalIterator> Sawyer::Container::IntervalMap< I, T, Policy >::intervals ( ) const

inline

Iterators for traversing keys.

Returns a range of iteratores that traverse all keys (non-overlapping intervals) of this container according to the order of the intervals.

Definition at line 291 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::eraseMultiple(), Sawyer::Container::IntervalSet< Interval >::insertMultiple(), and Sawyer::Container::IntervalSet< Interval >::invert().

Here is the caller graph for this function:

◆ values() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<ValueIterator> Sawyer::Container::IntervalMap< I, T, Policy >::values ( )

inline

Iterators for traversing values.

Returns a range of iterators that traverse the values (user-defined type) of this container. The values are traversed in the order of their associated keys.

Definition at line 299 of file IntervalMap.h.

◆ values() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<ConstValueIterator> Sawyer::Container::IntervalMap< I, T, Policy >::values ( ) const

inline

Iterators for traversing values.

Returns a range of iterators that traverse the values (user-defined type) of this container. The values are traversed in the order of their associated keys.

Definition at line 300 of file IntervalMap.h.

◆ lowerBound() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound ( const typename Interval::Value & scalar )

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

Referenced by Sawyer::Container::IntervalMap< Interval, int >::erase(), Sawyer::Container::IntervalMap< Interval, int >::firstUnmapped(), Sawyer::Container::IntervalMap< Interval, int >::insert(), Sawyer::Container::IntervalSet< Interval >::invert(), Sawyer::Container::IntervalMap< Interval, int >::least(), Sawyer::Container::IntervalMap< Interval, int >::leastUnmapped(), and Sawyer::Container::IntervalSet< Interval >::lowerBound().

Here is the caller graph for this function:

◆ lowerBound() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::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 311 of file IntervalMap.h.

◆ upperBound() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::upperBound ( const typename Interval::Value & scalar )

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 321 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ upperBound() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::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 327 of file IntervalMap.h.

◆ findPrior() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findPrior ( const typename Interval::Value & scalar )

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 340 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::findPrior(), Sawyer::Container::IntervalMap< Interval, int >::greatest(), Sawyer::Container::IntervalMap< Interval, int >::greatestUnmapped(), and Sawyer::Container::IntervalMap< Interval, int >::lastUnmapped().

Here is the caller graph for this function:

◆ findPrior() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::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 343 of file IntervalMap.h.

◆ findPriorImpl()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static IntervalMapTraits<IMap>::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findPriorImpl	(	IMap &	imap,
		const typename Interval::Value &	scalar
	)

inlinestatic

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 349 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::findPrior().

Here is the caller graph for this function:

◆ find() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::find ( const typename Interval::Value & scalar )

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 367 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::exists(), Sawyer::Container::IntervalSet< Interval >::find(), Sawyer::Container::IntervalMap< Interval, int >::get(), Sawyer::Container::IntervalMap< Interval, int >::getOptional(), Sawyer::Container::IntervalMap< Interval, int >::getOrDefault(), Sawyer::Container::IntervalMap< Interval, int >::getOrElse(), Sawyer::Container::IntervalMap< Interval, int >::insert(), and Sawyer::Container::IntervalMap< Interval, int >::operator[]().

Here is the caller graph for this function:

◆ find() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::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 370 of file IntervalMap.h.

◆ findImpl()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static IntervalMapTraits<IMap>::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findImpl	(	IMap &	imap,
		const typename Interval::Value &	scalar
	)

inlinestatic

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 376 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::find().

Here is the caller graph for this function:

◆ findAll() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<NodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::findAll ( const Interval & interval )

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 390 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ findAll() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

boost::iterator_range<ConstNodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::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 393 of file IntervalMap.h.

◆ findAllImpl()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static boost::iterator_range<typename IntervalMapTraits<IMap>::NodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::findAllImpl	(	IMap &	imap,
		const Interval &	interval
	)

inlinestatic

Finds all nodes overlapping the specified interval.

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

Definition at line 399 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::findAll().

Here is the caller graph for this function:

◆ findFirstOverlap() [1/4]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap ( const Interval & interval )

inline

Find first interval 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 415 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ findFirstOverlap() [2/4]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap ( const Interval & interval ) const

inline

Find first interval 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 418 of file IntervalMap.h.

◆ findFirstOverlapImpl() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static IntervalMapTraits<IMap>::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlapImpl	(	IMap &	imap,
		const Interval &	interval
	)

inlinestatic

Find first interval 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 424 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::findFirstOverlap().

Here is the caller graph for this function:

◆ findFirstOverlap() [3/4]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<typename T2 , class Policy2 >

std::pair<NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap	(	typename IntervalMap< I, T, Policy >::NodeIterator	thisIter,
		const IntervalMap< Interval, T2, Policy2 > &	other,
		typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator	otherIter
	)

inline

Find first interval that overlaps with any in another container.

The other container must use the same interval type, but may have different values and merge policies. The search begins at the specified iterators and returns a pair of iterators pointing to the two nodes that overlap. The first member of the pair is an iterator to this container, and the second is an iterator for the other container. If no such nodes exist at or after the starting locations, then the return value will be a pair of end iterators for their respective containers.

Definition at line 444 of file IntervalMap.h.

◆ findFirstOverlap() [4/4]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<typename T2 , class Policy2 >

std::pair<ConstNodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap	(	typename IntervalMap< I, T, Policy >::ConstNodeIterator	thisIter,
		const IntervalMap< Interval, T2, Policy2 > &	other,
		typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator	otherIter
	)		const

inline

Find first interval that overlaps with any in another container.

The other container must use the same interval type, but may have different values and merge policies. The search begins at the specified iterators and returns a pair of iterators pointing to the two nodes that overlap. The first member of the pair is an iterator to this container, and the second is an iterator for the other container. If no such nodes exist at or after the starting locations, then the return value will be a pair of end iterators for their respective containers.

Definition at line 450 of file IntervalMap.h.

◆ findFirstOverlapImpl() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap , typename T2 , class Policy2 >

static std::pair<typename IntervalMapTraits<IMap>::NodeIterator, typename IntervalMap<Interval, T2, Policy2>::ConstNodeIterator> Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlapImpl	(	IMap &	imap,
		typename IntervalMapTraits< IMap >::NodeIterator	thisIter,
		const IntervalMap< Interval, T2, Policy2 > &	other,
		typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator	otherIter
	)

inlinestatic

Find first interval that overlaps with any in another container.

The other container must use the same interval type, but may have different values and merge policies. The search begins at the specified iterators and returns a pair of iterators pointing to the two nodes that overlap. The first member of the pair is an iterator to this container, and the second is an iterator for the other container. If no such nodes exist at or after the starting locations, then the return value will be a pair of end iterators for their respective containers.

Definition at line 458 of file IntervalMap.h.

◆ firstFit() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::firstFit	(	const typename Interval::Value &	size,
		NodeIterator	start
	)

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 486 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ firstFit() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::firstFit	(	const typename Interval::Value &	size,
		ConstNodeIterator	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 489 of file IntervalMap.h.

◆ firstFitImpl()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static IntervalMapTraits<IMap>::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::firstFitImpl	(	IMap &	imap,
		const typename Interval::Value &	size,
		typename IntervalMapTraits< IMap >::NodeIterator	start
	)

inlinestatic

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 495 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::firstFit().

Here is the caller graph for this function:

◆ bestFit() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::bestFit	(	const typename Interval::Value &	size,
		NodeIterator	start
	)

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 518 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ bestFit() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

ConstNodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::bestFit	(	const typename Interval::Value &	size,
		ConstNodeIterator	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 521 of file IntervalMap.h.

◆ bestFitImpl()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<class IMap >

static IntervalMapTraits<IMap>::NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::bestFitImpl	(	IMap &	imap,
		const typename Interval::Value &	size,
		typename IntervalMapTraits< IMap >::NodeIterator	start
	)

inlinestatic

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 527 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::bestFit().

Here is the caller graph for this function:

◆ firstUnmapped()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Interval Sawyer::Container::IntervalMap< I, T, Policy >::firstUnmapped ( typename Interval::Value minAddr ) const

inline

Find the first unmapped region.

Returns an interval that describes the lowest unmapped interval that begins at or after the specified starting address and ends immediately prior to the mapped address that follows the unmapped interval, or the greatest possible address if there are no following mapped addresses. If minAddr is after the last unmapped address then an empty interval is returned. The returned interval will not include addresses less than minAddr.

Definition at line 546 of file IntervalMap.h.

◆ lastUnmapped()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Interval Sawyer::Container::IntervalMap< I, T, Policy >::lastUnmapped ( typename Interval::Value maxAddr ) const

inline

Find the last unmapped region.

Returns an interval that describes the lowest unmapped interval that ends at or before the specified maximum address and starts immediately after the next lower mapped address, or the least possible address is no lower mapped address is present. If maxAddr is before the first unmapped address then an empty interval is returned. The returned interval will not include addresses greater than maxAddr.

Definition at line 564 of file IntervalMap.h.

◆ exists()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

bool Sawyer::Container::IntervalMap< I, T, Policy >::exists ( const typename Interval::Value & size ) const

inline

Returns true if element exists.

Returns true if and only if the specified key exists in the map.

Definition at line 579 of file IntervalMap.h.

◆ operator[]()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

const Value& Sawyer::Container::IntervalMap< I, T, Policy >::operator[] ( const typename Interval::Value & scalar ) const

inline

Returns a reference to an existing value.

Returns a reference to the value at the node with the specified scalar. Unlike std::map, this container does not instantiate a new value if the scalar key is not in the map's domain. In other words, the array operator for this class is more like an array operator on arrays or vectors–such objects are not automatically extended if dereferenced with an operand that is outside the domain.

If the scalar is not part of this map's domain then an std:domain_error is thrown.

Definition at line 597 of file IntervalMap.h.

◆ get()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

const Value& Sawyer::Container::IntervalMap< I, T, Policy >::get ( const typename Interval::Value & scalar ) const

inline

Returns a reference to an existing value.

Returns a reference to the value at the node with the specified scalar. Unlike std::map, this container does not instantiate a new value if the scalar key is not in the map's domain. In other words, the array operator for this class is more like an array operator on arrays or vectors–such objects are not automatically extended if dereferenced with an operand that is outside the domain.

If the scalar is not part of this map's domain then an std:domain_error is thrown.

Definition at line 604 of file IntervalMap.h.

◆ getOptional()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Optional<Value> Sawyer::Container::IntervalMap< I, T, Policy >::getOptional ( const typename Interval::Value & scalar ) const

inline

Lookup and return a value or nothing.

Looks up the node with the specified scalar key and returns either a copy of its value, or nothing. This method executes in logorithmic time.

Here's an example of one convenient way to use this:

IntervalMap<AddressInterval, FileInfo> files;
...
if (Optional<FileInfo> fileInfo = files.getOptional(address))
    std::cout <<"file info for " <<address <<" is " <<*fileInfo <<"\n";

Definition at line 625 of file IntervalMap.h.

◆ getOrElse() [1/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Value& Sawyer::Container::IntervalMap< I, T, Policy >::getOrElse	(	const typename Interval::Value &	scalar,
		Value &	dflt
	)

inline

Lookup and return a value or something else.

This is similar to the getOptional method, except a default can be provided. If a node with the specified scalar key is present in this container, then a reference to that node's value is returned, otherwise the (reference to) supplied default is returned.

Definition at line 637 of file IntervalMap.h.

◆ getOrElse() [2/2]

template<typename I , typename T , class Policy = MergePolicy<I, T>>

const Value& Sawyer::Container::IntervalMap< I, T, Policy >::getOrElse	(	const typename Interval::Value &	scalar,
		const Value &	dflt
	)		const

inline

Lookup and return a value or something else.

This is similar to the getOptional method, except a default can be provided. If a node with the specified scalar key is present in this container, then a reference to that node's value is returned, otherwise the (reference to) supplied default is returned.

Definition at line 641 of file IntervalMap.h.

◆ getOrDefault()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

const Value& Sawyer::Container::IntervalMap< I, T, Policy >::getOrDefault ( const typename Interval::Value & scalar ) const

inline

Lookup and return a value or a default.

This is similar to the getOrElse method except when the scalar key is not present in the map, a reference to a const, default-constructed value is returned.

Definition at line 651 of file IntervalMap.h.

◆ isEmpty()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

bool Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty ( ) const

inline

Determine if the container is empty.

Returns true if this container has no nodes.

Definition at line 665 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::greatest(), Sawyer::Container::IntervalMap< Interval, int >::hull(), Sawyer::Container::IntervalSet< Interval >::isEmpty(), and Sawyer::Container::IntervalMap< Interval, int >::least().

Here is the caller graph for this function:

◆ nIntervals()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

size_t Sawyer::Container::IntervalMap< I, T, Policy >::nIntervals ( ) const

inline

Number of nodes in the container.

Each node is a pair consisting of an interval and a value. The container normally merges two juxtaposed intervals if their values can be combined.

Definition at line 673 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ size()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Interval::Value Sawyer::Container::IntervalMap< I, T, Policy >::size ( ) const

inline

Returns the number of values represented by this container.

The number of values in a container is the sum of the widths of all the nodes. This can be calculated in constant time.

Definition at line 681 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::bestFit(), Sawyer::Container::IntervalMap< Interval, int >::bestFitImpl(), Sawyer::Container::IntervalMap< Interval, int >::exists(), Sawyer::Container::IntervalMap< Interval, int >::firstFit(), Sawyer::Container::IntervalMap< Interval, int >::firstFitImpl(), and Sawyer::Container::IntervalSet< Interval >::size().

Here is the caller graph for this function:

◆ least()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Optional<typename Interval::Value> Sawyer::Container::IntervalMap< I, T, Policy >::least ( typename Interval::Value lowerLimit ) const

inline

Returns the limited-minimum scalar key.

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

Definition at line 702 of file IntervalMap.h.

◆ greatest()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Optional<typename Interval::Value> Sawyer::Container::IntervalMap< I, T, Policy >::greatest ( typename Interval::Value upperLimit ) const

inline

Returns the limited-maximum scalar key.

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

Definition at line 713 of file IntervalMap.h.

◆ leastUnmapped()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Optional<typename Interval::Value> Sawyer::Container::IntervalMap< I, T, Policy >::leastUnmapped ( typename Interval::Value lowerLimit ) const

inline

Returns the limited-minimum unmapped scalar key.

Returns the lowest unmapped scalar key equal to or greater than the lowerLimit. If no such value exists then nothing is returned.

Definition at line 724 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ greatestUnmapped()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

Optional<typename Interval::Value> Sawyer::Container::IntervalMap< I, T, Policy >::greatestUnmapped ( typename Interval::Value upperLimit ) const

inline

Returns the limited-maximum unmapped scalar key.

Returns the maximum unmapped scalar key equal to or less than the upperLimit. If no such value exists then nothing is returned.

Definition at line 739 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ eraseMultiple()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<typename T2 , class Policy2 >

void Sawyer::Container::IntervalMap< I, T, Policy >::eraseMultiple ( const IntervalMap< Interval, T2, Policy2 > & other )

inline

Erase intervals specified in another IntervalMap.

Every interval in other is erased from this container.

Definition at line 827 of file IntervalMap.h.

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

Here is the caller graph for this function:

◆ insert()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

void Sawyer::Container::IntervalMap< I, T, Policy >::insert	(	Interval	key,
		Value	value,
		bool	makeHole = `true`
	)

inline

Insert a key/value pair.

If makeHole is true then the interval being inserted is first erased; otherwise the insertion happens only if none of the interval being inserted already exists in the container.

Definition at line 838 of file IntervalMap.h.

Referenced by Sawyer::Container::IntervalSet< Interval >::insert(), Sawyer::Container::IntervalSet< Interval >::insertMultiple(), Sawyer::Container::IntervalMap< Interval, int >::insertMultiple(), Sawyer::Container::IntervalMap< Interval, int >::IntervalMap(), and Sawyer::Container::IntervalMap< Interval, int >::operator=().

Here is the caller graph for this function:

◆ insertMultiple()

template<typename I , typename T , class Policy = MergePolicy<I, T>>

template<typename T2 , class Policy2 >

void Sawyer::Container::IntervalMap< I, T, Policy >::insertMultiple	(	const IntervalMap< Interval, T2, Policy2 > &	other,
		bool	makeHole = `true`
	)

inline

Insert values from another container.

The values in the other container must be convertable to values of this container, and the intervals must be the same type.

Definition at line 883 of file IntervalMap.h.

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

IntervalMap.h

Description

template<typename I, typename T, class Policy = MergePolicy<I, T>> class Sawyer::Container::IntervalMap< I, T, Policy >

Public Types

Public Member Functions

Member Typedef Documentation

◆ Node

◆ ConstIntervalIterator

◆ ValueIterator

◆ ConstValueIterator

◆ NodeIterator

◆ ConstNodeIterator

Constructor & Destructor Documentation

◆ IntervalMap() [1/2]

◆ IntervalMap() [2/2]

Member Function Documentation

◆ operator=()

◆ nodes() [1/2]

◆ nodes() [2/2]

◆ intervals()

◆ values() [1/2]

◆ values() [2/2]

◆ lowerBound() [1/2]

◆ lowerBound() [2/2]

◆ upperBound() [1/2]

◆ upperBound() [2/2]

◆ findPrior() [1/2]

◆ findPrior() [2/2]

◆ findPriorImpl()

◆ find() [1/2]

◆ find() [2/2]

◆ findImpl()

◆ findAll() [1/2]

◆ findAll() [2/2]

◆ findAllImpl()

◆ findFirstOverlap() [1/4]

◆ findFirstOverlap() [2/4]

◆ findFirstOverlapImpl() [1/2]

◆ findFirstOverlap() [3/4]

◆ findFirstOverlap() [4/4]

◆ findFirstOverlapImpl() [2/2]

◆ firstFit() [1/2]

◆ firstFit() [2/2]

◆ firstFitImpl()

◆ bestFit() [1/2]

◆ bestFit() [2/2]

◆ bestFitImpl()

◆ firstUnmapped()

◆ lastUnmapped()

◆ exists()

◆ operator[]()

◆ get()

◆ getOptional()

◆ getOrElse() [1/2]

◆ getOrElse() [2/2]

◆ getOrDefault()

◆ isEmpty()

◆ nIntervals()

◆ size()

◆ least()

◆ greatest()

◆ leastUnmapped()

◆ greatestUnmapped()

◆ eraseMultiple()

◆ insert()

◆ insertMultiple()

template<typename I, typename T, class Policy = MergePolicy<I, T>>
class Sawyer::Container::IntervalMap< I, T, Policy >