ROSE  0.11.145.0
Classes | Public Types | Public Member Functions | List of all members
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 171 of file IntervalMap.h.

#include <util/Sawyer/IntervalMap.h>

Inheritance diagram for Sawyer::Container::IntervalMap< I, T, Policy >:
Inheritance graph
[legend]

Public Types

typedef I Interval
 Interval type. More...
 
typedef T Value
 Value type. More...
 
typedef Container::Map< Interval, Value, IntervalCompare > Map
 Type of the underlying map. More...
 
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 >
IntervalMapoperator= (const IntervalMap< Interval2, T2, Policy2 > &other)
 Assignment operator. More...
 
boost::iterator_range< ConstIntervalIteratorintervals () 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< ValuegetOptional (const typename Interval::Value &scalar) const
 Lookup and return a value or nothing. More...
 
const ValuegetOrDefault (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. More...
 
Interval::Value greatest () const
 Returns the maximum scalar key. More...
 
Optional< typename Interval::Valueleast (typename Interval::Value lowerLimit) const
 Returns the limited-minimum scalar key. More...
 
Optional< typename Interval::Valuegreatest (typename Interval::Value upperLimit) const
 Returns the limited-maximum scalar key. More...
 
Optional< typename Interval::ValueleastUnmapped (typename Interval::Value lowerLimit) const
 Returns the limited-minimum unmapped scalar key. More...
 
Optional< typename Interval::ValuegreatestUnmapped (typename Interval::Value upperLimit) const
 Returns the limited-maximum unmapped scalar key. More...
 
Interval hull () const
 Returns the range of values in this map. More...
 
void clear ()
 Empties the container. More...
 
void erase (const Interval &erasure)
 Erase the specified interval. More...
 
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 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< NodeIteratornodes ()
 Iterators for traversing nodes. More...
 
boost::iterator_range< ConstNodeIteratornodes () const
 Iterators for traversing nodes. More...
 
boost::iterator_range< ValueIteratorvalues ()
 Iterators for traversing values. More...
 
boost::iterator_range< ConstValueIteratorvalues () 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 Valueoperator[] (const typename Interval::Value &scalar) const
 Returns a reference to an existing value. More...
 
const Valueget (const typename Interval::Value &scalar) const
 Returns a reference to an existing value. More...
 
ValuegetOrElse (const typename Interval::Value &scalar, Value &dflt)
 Lookup and return a value or something else. More...
 
const ValuegetOrElse (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< NodeIteratorfindAll (const Interval &interval)
 Finds all nodes overlapping the specified interval. More...
 
boost::iterator_range< ConstNodeIteratorfindAll (const Interval &interval) const
 Finds all nodes overlapping the specified interval. More...
 
template<class IMap >
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIteratorfindAllImpl (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 >::ConstNodeIteratorfindFirstOverlap (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 >::ConstNodeIteratorfindFirstOverlap (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 >::ConstNodeIteratorfindFirstOverlapImpl (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

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

Interval type.

Definition at line 173 of file IntervalMap.h.

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

Value type.

Definition at line 174 of file IntervalMap.h.

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

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.

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.

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.

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.

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.

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

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.

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

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.

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.

Referenced by Sawyer::Container::IntervalMap< Interval, int >::erase(), Sawyer::Container::IntervalMap< Interval, int >::eraseMultiple(), Sawyer::Container::IntervalMap< Interval, int >::exists(), Sawyer::Container::IntervalMap< Interval, int >::findFirstOverlapImpl(), Sawyer::Container::IntervalMap< Interval, int >::firstUnmapped(), 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 >::greatest(), Sawyer::Container::IntervalMap< Interval, int >::greatestUnmapped(), Sawyer::Container::IntervalMap< Interval, int >::insert(), Sawyer::Container::IntervalMap< Interval, int >::insertMultiple(), Sawyer::Container::IntervalMap< Interval, int >::IntervalMap(), Sawyer::Container::IntervalSet< AddressInterval >::intervals(), Sawyer::Container::IntervalSet< AddressInterval >::IntervalSet(), Sawyer::Container::IntervalMap< Interval, int >::lastUnmapped(), Sawyer::Container::IntervalMap< Interval, int >::least(), Sawyer::Container::IntervalMap< Interval, int >::leastUnmapped(), Sawyer::Container::AddressMap< rose_addr_t, uint8_t >::nodes(), Sawyer::Container::IntervalSet< AddressInterval >::operator=(), Sawyer::Container::IntervalMap< Interval, int >::operator=(), and Sawyer::Container::IntervalMap< Interval, int >::operator[]().

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.

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< AddressInterval >::eraseMultiple(), Sawyer::Container::IntervalSet< AddressInterval >::insertMultiple(), and Sawyer::Container::IntervalSet< AddressInterval >::invert().

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.

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.

template<typename I, typename T, class Policy = MergePolicy<I, T>>
NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::lowerBound ( const typename Interval::Value scalar)
inline
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.

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< AddressInterval >::upperBound().

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.

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< AddressInterval >::findPrior(), Sawyer::Container::IntervalMap< Interval, int >::greatest(), Sawyer::Container::IntervalMap< Interval, int >::greatestUnmapped(), and Sawyer::Container::IntervalMap< Interval, int >::lastUnmapped().

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.

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

template<typename I, typename T, class Policy = MergePolicy<I, T>>
NodeIterator Sawyer::Container::IntervalMap< I, T, Policy >::find ( const typename Interval::Value scalar)
inline
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.

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

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< AddressInterval >::findAll(), Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::overlapping(), and Rose::BinaryAnalysis::Partitioner2::AddressUsageMap::spanning().

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.

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

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< AddressInterval >::findFirstOverlap().

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.

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

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.

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.

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.

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< AddressInterval >::firstFit().

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.

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

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< AddressInterval >::bestFit().

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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.

template<typename I, typename T, class Policy = MergePolicy<I, T>>
bool Sawyer::Container::IntervalMap< I, T, Policy >::isEmpty ( ) const
inline
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< AddressInterval >::nIntervals(), and Sawyer::Container::IntervalSet< AddressInterval >::operator!=().

template<typename I, typename T, class Policy = MergePolicy<I, T>>
Interval::Value Sawyer::Container::IntervalMap< I, T, Policy >::size ( void  ) 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 >::firstFitImpl(), and Sawyer::Container::IntervalSet< AddressInterval >::size().

template<typename I, typename T, class Policy = MergePolicy<I, T>>
Interval::Value Sawyer::Container::IntervalMap< I, T, Policy >::least ( ) const
inline
template<typename I, typename T, class Policy = MergePolicy<I, T>>
Interval::Value Sawyer::Container::IntervalMap< I, T, Policy >::greatest ( ) const
inline
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.

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.

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< AddressInterval >::leastNonExistent().

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< AddressInterval >::greatestNonExistent().

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

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

template<typename I, typename T, class Policy = MergePolicy<I, T>>
void Sawyer::Container::IntervalMap< I, T, Policy >::clear ( )
inline
template<typename I, typename T, class Policy = MergePolicy<I, T>>
void Sawyer::Container::IntervalMap< I, T, Policy >::erase ( const Interval erasure)
inline
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< AddressInterval >::intersect().

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< AddressInterval >::insert(), Sawyer::Container::IntervalSet< AddressInterval >::insertMultiple(), Sawyer::Container::IntervalMap< Interval, int >::insertMultiple(), Sawyer::Container::IntervalMap< Interval, int >::IntervalMap(), and Sawyer::Container::IntervalMap< Interval, int >::operator=().

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: