Sawyer::Container::IntervalMap< I, T, Policy > Class Template Reference

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

#include <Sawyer/IntervalMap.h>

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

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.
typedef Map::ConstKeyIterator	ConstIntervalIterator
	Interval iterator.
typedef Map::ValueIterator	ValueIterator
	Value iterator.
typedef Map::ConstValueIterator	ConstValueIterator
	Value iterator.
typedef Map::NodeIterator	NodeIterator
	Node iterator.
typedef Map::ConstNodeIterator	ConstNodeIterator
	Node iterator.

Public Member Functions
	IntervalMap ()
	Default constructor.
template<class Interval2 , class T2 , class Policy2 >
	IntervalMap (const IntervalMap< Interval2, T2, Policy2 > &other)
	Copy constructor.
template<class Interval2 , class T2 , class Policy2 >
IntervalMap &	operator= (const IntervalMap< Interval2, T2, Policy2 > &other)
	Assignment operator.
boost::iterator_range< ConstIntervalIterator >	intervals () const
	Iterators for traversing keys.
Interval	firstUnmapped (typename Interval::Value minAddr) const
	Find the first unmapped region.
Interval	lastUnmapped (typename Interval::Value maxAddr) const
	Find the last unmapped region.
bool	exists (const typename Interval::Value &size) const
	Returns true if element exists.
Optional< Value >	getOptional (const typename Interval::Value &scalar) const
	Lookup and return a value or nothing.
const Value &	getOrDefault (const typename Interval::Value &scalar) const
	Lookup and return a value or a default.
bool	isEmpty () const
	Determine if the container is empty.
size_t	nIntervals () const
	Number of nodes in the container.
Interval::Value	size () const
	Returns the number of values represented by this container.
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.
Optional< typename Interval::Value >	greatest (typename Interval::Value upperLimit) const
	Returns the limited-maximum scalar key.
Optional< typename Interval::Value >	leastUnmapped (typename Interval::Value lowerLimit) const
	Returns the limited-minimum unmapped scalar key.
Optional< typename Interval::Value >	greatestUnmapped (typename Interval::Value upperLimit) const
	Returns the limited-maximum unmapped scalar key.
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.
void	insert (Interval key, Value value, bool makeHole=true)
	Insert a key/value pair.
template<typename T2 , class Policy2 >
void	insertMultiple (const IntervalMap< Interval, T2, Policy2 > &other, bool makeHole=true)
	Insert values from another container.
bool	overlaps (const Interval &interval) const
bool	isOverlapping (const Interval &interval) const
template<typename T2 , class Policy2 >
bool	overlaps (const IntervalMap< Interval, T2, Policy2 > &other) 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.
boost::iterator_range< ConstNodeIterator >	nodes () const
	Iterators for traversing nodes.
boost::iterator_range< ValueIterator >	values ()
	Iterators for traversing values.
boost::iterator_range< ConstValueIterator >	values () const
	Iterators for traversing values.
NodeIterator	lowerBound (const typename Interval::Value &scalar)
	Find the first node whose interval ends at or above the specified scalar key.
ConstNodeIterator	lowerBound (const typename Interval::Value &scalar) const
	Find the first node whose interval ends at or above the specified scalar key.
NodeIterator	upperBound (const typename Interval::Value &scalar)
	Find the first node whose interval begins above the specified scalar key.
ConstNodeIterator	upperBound (const typename Interval::Value &scalar) const
	Find the first node whose interval begins above the specified scalar key.
const Value &	operator[] (const typename Interval::Value &scalar) const
	Returns a reference to an existing value.
const Value &	get (const typename Interval::Value &scalar) const
	Returns a reference to an existing value.
Value &	getOrElse (const typename Interval::Value &scalar, Value &dflt)
	Lookup and return a value or something else.
const Value &	getOrElse (const typename Interval::Value &scalar, const Value &dflt) const
	Lookup and return a value or something else.
NodeIterator	findPrior (const typename Interval::Value &scalar)
	Find the last node whose interval starts at or below the specified scalar key.
ConstNodeIterator	findPrior (const typename Interval::Value &scalar) const
	Find the last node whose interval starts at or below the specified scalar key.
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.
NodeIterator	find (const typename Interval::Value &scalar)
	Find the node containing the specified scalar key.
ConstNodeIterator	find (const typename Interval::Value &scalar) const
	Find the node containing the specified scalar key.
template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	findImpl (IMap &imap, const typename Interval::Value &scalar)
	Find the node containing the specified scalar key.
boost::iterator_range< NodeIterator >	findAll (const Interval &interval)
	Finds all nodes overlapping the specified interval.
boost::iterator_range< ConstNodeIterator >	findAll (const Interval &interval) const
	Finds all nodes overlapping the specified interval.
template<class IMap >
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIterator >	findAllImpl (IMap &imap, const Interval &interval)
	Finds all nodes overlapping the specified interval.
NodeIterator	findFirstOverlap (const Interval &interval)
	Find first interval that overlaps with the specified interval.
ConstNodeIterator	findFirstOverlap (const Interval &interval) const
	Find first interval that overlaps with the specified interval.
template<class IMap >
static IntervalMapTraits< IMap >::NodeIterator	findFirstOverlapImpl (IMap &imap, const Interval &interval)
	Find first interval that overlaps with the specified interval.
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.
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.
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.
NodeIterator	firstFit (const typename Interval::Value &size, NodeIterator start)
	Find the first fit node at or after a starting point.
ConstNodeIterator	firstFit (const typename Interval::Value &size, ConstNodeIterator start) const
	Find the first fit node at or after a starting point.
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.
NodeIterator	bestFit (const typename Interval::Value &size, NodeIterator start)
	Find the best fit node at or after a starting point.
ConstNodeIterator	bestFit (const typename Interval::Value &size, ConstNodeIterator start) const
	Find the best fit node at or after a starting point.
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.

Member Typedef Documentation

Interval

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

typedef I Sawyer::Container::IntervalMap< I, T, Policy >::Interval

Interval type.

Definition at line 182 of file IntervalMap.h.

Value

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

typedef T Sawyer::Container::IntervalMap< I, T, Policy >::Value

Value type.

Definition at line 183 of file IntervalMap.h.

Map

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

typedef Container::Map<Interval, Value, IntervalCompare> Sawyer::Container::IntervalMap< I, T, Policy >::Map

Type of the underlying map.

Definition at line 199 of file IntervalMap.h.

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 205 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 211 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 219 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 220 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 229 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 230 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 269 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 276 of file IntervalMap.h.

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

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

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

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes().

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::IntervalMap(), Sawyer::Container::IntervalSet< I >::IntervalSet(), Sawyer::Container::IntervalMap< I, T, Policy >::erase(), Sawyer::Container::IntervalMap< I, T, Policy >::eraseMultiple(), Sawyer::Container::IntervalMap< I, T, Policy >::exists(), Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlapImpl(), Sawyer::Container::IntervalMap< I, T, Policy >::firstUnmapped(), Sawyer::Container::IntervalMap< I, T, Policy >::get(), Sawyer::Container::IntervalMap< I, T, Policy >::getOptional(), Sawyer::Container::IntervalMap< I, T, Policy >::getOrDefault(), Sawyer::Container::IntervalMap< I, T, Policy >::getOrElse(), Sawyer::Container::IntervalMap< I, T, Policy >::getOrElse(), Sawyer::Container::IntervalMap< I, T, Policy >::greatest(), Sawyer::Container::IntervalMap< I, T, Policy >::greatestUnmapped(), Sawyer::Container::IntervalMap< I, T, Policy >::insert(), Sawyer::Container::IntervalMap< I, T, Policy >::insertMultiple(), Sawyer::Container::IntervalSet< I >::intervals(), Sawyer::Container::IntervalMap< I, T, Policy >::lastUnmapped(), Sawyer::Container::IntervalMap< I, T, Policy >::least(), Sawyer::Container::IntervalMap< I, T, Policy >::leastUnmapped(), Sawyer::Container::AddressMap< A, T >::nodes(), Sawyer::Container::AddressMap< A, T >::nodes(), Sawyer::Container::IntervalSet< I >::operator=(), Sawyer::Container::IntervalMap< I, T, Policy >::operator=(), and Sawyer::Container::IntervalMap< I, T, Policy >::operator[]().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::keys().

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

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::values().

Referenced by Sawyer::Container::AddressMap< A, T >::AddressMap(), Sawyer::Container::AddressMap< A, T >::segments(), and Sawyer::Container::AddressMap< A, T >::segments().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::values().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::lowerBound().

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::erase(), Sawyer::Container::IntervalMap< I, T, Policy >::firstUnmapped(), Sawyer::Container::IntervalMap< I, T, Policy >::insert(), Sawyer::Container::IntervalSet< I >::invert(), Sawyer::Container::IntervalMap< I, T, Policy >::least(), Sawyer::Container::IntervalMap< I, T, Policy >::leastUnmapped(), Sawyer::Container::IntervalSet< I >::lowerBound(), and Sawyer::Container::AddressMap< A, T >::write().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::lowerBound().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::upperBound().

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

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::upperBound().

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

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

Referenced by Sawyer::Container::IntervalSet< I >::findPrior(), Sawyer::Container::IntervalMap< I, T, Policy >::greatest(), Sawyer::Container::IntervalMap< I, T, Policy >::greatestUnmapped(), and Sawyer::Container::IntervalMap< I, T, Policy >::lastUnmapped().

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::findPrior(), and Sawyer::Container::IntervalMap< I, T, Policy >::findPrior().

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

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

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

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

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::find(), and Sawyer::Container::IntervalMap< I, T, Policy >::find().

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

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

Referenced by Sawyer::Container::IntervalSet< I >::findAll(), Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::overlapping(), and Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::spanning().

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::findAll(), and Sawyer::Container::IntervalMap< I, T, Policy >::findAll().

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

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

Referenced by Sawyer::Container::IntervalSet< I >::findFirstOverlap(), and Sawyer::Container::IntervalSet< I >::findFirstOverlap().

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap(), Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap(), Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap(), and Sawyer::Container::IntervalMap< I, T, Policy >::findFirstOverlap().

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

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

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

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

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), and Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

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

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

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

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

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::firstFit(), and Sawyer::Container::IntervalMap< I, T, Policy >::firstFit().

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

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

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

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

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

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

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

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::bestFit(), and Sawyer::Container::IntervalMap< I, T, Policy >::bestFit().

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

References Sawyer::Container::Interval< T >::greatest(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Interval< T >::whole().

Referenced by Sawyer::Container::AddressMap< A, T >::unmapped().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::findPrior(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::Interval< T >::least(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Interval< T >::whole().

Referenced by Sawyer::Container::AddressMap< A, T >::unmapped().

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

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

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::isEmpty().

Referenced by Sawyer::Container::AddressMapConstraints< AddressMap >::at(), Sawyer::Container::AddressMapConstraints< AddressMap >::at(), Sawyer::Container::IntervalMap< I, T, Policy >::greatest(), Sawyer::Container::IntervalMap< I, T, Policy >::hull(), Sawyer::Container::IntervalSet< I >::isEmpty(), and Sawyer::Container::IntervalMap< I, T, Policy >::least().

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::size().

Referenced by Sawyer::Container::IntervalSet< I >::nIntervals(), Sawyer::Container::AddressMap< A, T >::nSegments(), and Sawyer::Container::IntervalSet< I >::operator!=().

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

Referenced by Sawyer::Container::AddressMap< A, T >::baseSize(), Sawyer::Container::AddressMap< A, T >::baseSize(), Sawyer::Container::IntervalMap< I, T, Policy >::bestFit(), Sawyer::Container::IntervalMap< I, T, Policy >::bestFit(), Sawyer::Container::IntervalMap< I, T, Policy >::bestFitImpl(), Sawyer::Container::IntervalMap< I, T, Policy >::exists(), Sawyer::Container::IntervalMap< I, T, Policy >::firstFit(), Sawyer::Container::IntervalMap< I, T, Policy >::firstFit(), Sawyer::Container::IntervalMap< I, T, Policy >::firstFitImpl(), Rose::BinaryAnalysis::MemoryMap::readLongUnsinged(), Rose::BinaryAnalysis::MemoryMap::readUnsigned(), and Sawyer::Container::IntervalSet< I >::size().

least() [1/2]

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

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

inline

Returns the minimum scalar key.

Definition at line 709 of file IntervalMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::keys().

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::findImpl(), Sawyer::Container::IntervalMap< I, T, Policy >::hull(), Sawyer::Container::IntervalSet< I >::least(), and Sawyer::Container::IntervalSet< I >::least().

greatest() [1/2]

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

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

inline

Returns the maximum scalar key.

Definition at line 715 of file IntervalMap.h.

References Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::keys().

Referenced by Sawyer::Container::IntervalSet< I >::greatest(), Sawyer::Container::IntervalSet< I >::greatest(), and Sawyer::Container::IntervalMap< I, T, Policy >::hull().

least() [2/2]

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

References Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound(), and Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

greatest() [2/2]

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

References Sawyer::Container::IntervalMap< I, T, Policy >::findPrior(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), and Sawyer::Container::IntervalMap< I, T, Policy >::nodes().

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

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

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

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

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

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

hull()

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

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

inline

Returns the range of values in this map.

Definition at line 776 of file IntervalMap.h.

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

Referenced by Sawyer::Container::IntervalSet< I >::hull().

clear()

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

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

inline

Empties the container.

Definition at line 787 of file IntervalMap.h.

References Sawyer::Container::Map< K, T, Cmp, Alloc >::clear().

Referenced by Sawyer::Container::IntervalSet< I >::clear(), and Sawyer::Container::IntervalMap< I, T, Policy >::operator=().

erase()

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

void Sawyer::Container::IntervalMap< I, T, Policy >::erase ( const Interval &  erasure )

inline

Erase the specified interval.

Definition at line 793 of file IntervalMap.h.

References Sawyer::Container::Map< K, T, Cmp, Alloc >::eraseAtMultiple(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insert(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insertMultiple(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), Sawyer::Container::Map< K, T, Cmp, Alloc >::nodes(), Sawyer::Container::Map< K, T, Cmp, Alloc >::size(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

Referenced by Sawyer::Container::IntervalSet< I >::erase(), Sawyer::Container::IntervalMap< I, T, Policy >::eraseMultiple(), Sawyer::Container::IntervalSet< I >::eraseMultiple(), Sawyer::Container::IntervalSet< I >::eraseMultiple(), Sawyer::Container::IntervalMap< I, T, Policy >::insert(), Sawyer::Container::IntervalSet< I >::intersect(), Sawyer::Container::AddressMap< A, T >::keep(), and Sawyer::Container::AddressMap< A, T >::prune().

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

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

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

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

References Sawyer::Container::IntervalMap< I, T, Policy >::erase(), Sawyer::Container::Map< K, T, Cmp, Alloc >::eraseAt(), Sawyer::Container::IntervalMap< I, T, Policy >::find(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::Map< K, T, Cmp, Alloc >::insert(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound(), Sawyer::Container::IntervalMap< I, T, Policy >::nodes(), Sawyer::Container::Map< K, T, Cmp, Alloc >::size(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::value().

Referenced by Sawyer::Container::IntervalMap< I, T, Policy >::IntervalMap(), Sawyer::Container::AddressMap< A, T >::changeAccess(), Sawyer::Container::IntervalSet< I >::insert(), Sawyer::Container::IntervalMap< I, T, Policy >::insertMultiple(), Sawyer::Container::IntervalSet< I >::insertMultiple(), Sawyer::Container::IntervalSet< I >::insertMultiple(), and Sawyer::Container::IntervalMap< I, T, Policy >::operator=().

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

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

overlaps() [1/2]

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

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

inline

Definition at line 923 of file IntervalMap.h.

isOverlapping() [1/2]

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

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

inline

Definition at line 926 of file IntervalMap.h.

overlaps() [2/2]

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

template<typename T2 , class Policy2 >

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

inline

Definition at line 931 of file IntervalMap.h.

isOverlapping() [2/2]

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

template<typename T2 , class Policy2 >

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

inline

Definition at line 935 of file IntervalMap.h.

isDistinct() [1/2]

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

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

inline

Definition at line 939 of file IntervalMap.h.

isDistinct() [2/2]

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

template<typename T2 , class Policy2 >

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

inline

Definition at line 944 of file IntervalMap.h.

contains() [1/2]

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

bool Sawyer::Container::IntervalMap< I, T, Policy >::contains ( Interval  key ) const

inline

Definition at line 948 of file IntervalMap.h.

contains() [2/2]

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

template<typename T2 , class Policy2 >

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

inline

Definition at line 966 of file IntervalMap.h.

---

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

• IntervalMap.h