ROSE  0.11.145.0
Public Types | Public Member Functions | List of all members
Sawyer::Container::IntervalSetMap< I, S > Class Template Reference

Description

template<typename I, typename S>
class Sawyer::Container::IntervalSetMap< I, S >

Mapping from integers to sets.

This container maps integer keys to sets of values and is optimized to store the same set across adjacent keys by using intervals of the key. For instance, an IntervalSetMap that maps integer keys to sets of characters is declared like this:

typedef Interval<int> IntRange;
typedef Set<char> CharSet;
typedef IntervalSetMap<IntRange, CharSet> IntCharMap;
IntCharMap icmap;

Such a map stores a set of characters for each integer key, but does so efficiently when the same set is stored across many consecutive keys. For instance, one can store the set {'a', 'b'} across a few million keys and use very little storage:

icmap.insert(IntRange::baseSize(0,5000000), 'a');
icmap.insert(IntRange::baseSize(0,5000000), 'b');

At this point icmap is storing 'a' and 'b' at every key from 0 through 4999999, inclusive. This could also have been done by constructing the set first and then inserting the set. The real power of this container comes from the fact that one can insert values without regard for what intervals currently exist. For instance, we now insert a few more characters:

icmap.insert(5, 'c'); // 5 is a singleton range
icmap.insert(IntRange::hull(10,19), 'd');

Now icmap stores {'a', 'b'} at keys 0 through 4, {'a', 'b', 'c'} at key 5, {'a', 'b'} at keys 6 through 9, {'a', 'b', 'd'} at keys 10 through 19, and {'a', 'b'} at keys 20 through 4999999.

Erasing values works similarly: one can erase a character from an interval or single key without regard for what intervals already exist. Attempting to erase a character from a set that doesn't contain the character is a no-op. Here we erase 'b' and 'e' from large parts of the map key space:

icmap.erase(icmap.hull(), 'b'); // erase 'b' from everywhere
icmap.erase(IntRange::hull(-1000000,1000000), 'e');

Querying is also quite efficient. Here we obtain the set of all values stored in the map's sets:

Set allValues = icmap.getUnion(icmap.hull());

There are also predicates to determine whether a key or value is present in the map.

icmap.contains(IntRange::hull(10,19)); // Do keys 10 through 19 all have non-empty sets?
icmap.containsAnywhere(icmap.hull(), 'b'); // Is value 'b' present anywhere in the map?
icmap.containsEverywhere(IntRange::hull(10,19), 'a'); // Is value 'a' present for all keys 10 through 19?

The S template parameter is the set type and must implement the API defined by Sawyer::Container::Set.

See also

See IntervalMap for a similar container whose values don't act like sets.

Definition at line 79 of file IntervalSetMap.h.

#include <util/Sawyer/IntervalSetMap.h>

Inheritance diagram for Sawyer::Container::IntervalSetMap< I, S >:
Inheritance graph
[legend]
Collaboration diagram for Sawyer::Container::IntervalSetMap< I, S >:
Collaboration graph
[legend]

Public Types

typedef I Interval
 Interval type for keys. More...
 
typedef S Set
 Set type for values. More...
 
- Public Types inherited from Sawyer::Container::IntervalMap< I, S >
typedef I Interval
 Interval type. More...
 
typedef S 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

Set getUnion (const Interval &interval) const
 Union of values over an interval of keys. More...
 
Set getIntersection (const Interval &interval) const
 Intersection of values over an interval of keys. More...
 
bool exists (const Interval &interval) const
 Determines if values are stored for an interval. More...
 
bool existsAnywhere (const Interval &interval, const typename Set::Value &value) const
 Determines if a particular value is stored in an interval. More...
 
bool existsEverywhere (const Interval &interval, const typename Set::Value &value) const
 Determines if a particular value is stored everywhere in the interval. More...
 
void erase (const Interval &interval)
 Erase sets for an interval. More...
 
bool erase (const Interval &interval, const typename Set::Value &value)
 Erases one value from a set over an interval. More...
 
bool erase (const Interval &interval, const Set &values)
 Erase specified values from the sets of an interval. More...
 
bool insert (const Interval &interval, const typename Set::Value &value)
 Insert one value to the sets of an interval. More...
 
bool insert (const Interval &interval, const Set &values)
 Insert a set of values into the sets of an interval. More...
 
void replace (const Interval &interval, const Set &set)
 Replace sets with a new set. More...
 
- Public Member Functions inherited from Sawyer::Container::IntervalMap< I, S >
 IntervalMap ()
 Default constructor. More...
 
 IntervalMap (const IntervalMap< Interval2, T2, Policy2 > &other)
 Copy constructor. More...
 
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...
 
Optional< typename Interval::Valueleast (typename Interval::Value lowerLimit) const
 Returns the limited-minimum scalar key. More...
 
Interval::Value greatest () const
 Returns the maximum 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...
 
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...
 
void insertMultiple (const IntervalMap< Interval, T2, Policy2 > &other, bool makeHole=true)
 Insert values from another container. More...
 
bool overlaps (const Interval &interval) const
 
bool overlaps (const IntervalMap< Interval, T2, Policy2 > &other) const
 
bool isOverlapping (const Interval &interval) const
 
bool isOverlapping (const IntervalMap< Interval, T2, Policy2 > &other) const
 
bool isDistinct (const Interval &interval) const
 
bool isDistinct (const IntervalMap< Interval, T2, Policy2 > &other) const
 
bool contains (Interval key) const
 
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...
 
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...
 
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...
 
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...
 
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...
 
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...
 
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...
 
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...
 

Additional Inherited Members

- Static Public Member Functions inherited from Sawyer::Container::IntervalMap< I, S >
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...
 
static IntervalMapTraits< IMap >::NodeIterator findImpl (IMap &imap, const typename Interval::Value &scalar)
 Find the node containing the specified scalar key. More...
 
static boost::iterator_range< typename IntervalMapTraits< IMap >::NodeIteratorfindAllImpl (IMap &imap, const Interval &interval)
 Finds all nodes overlapping the specified interval. More...
 
static IntervalMapTraits< IMap >::NodeIterator findFirstOverlapImpl (IMap &imap, const Interval &interval)
 Find first interval that overlaps with the specified interval. More...
 
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...
 
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...
 
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 S >
typedef I Sawyer::Container::IntervalSetMap< I, S >::Interval

Interval type for keys.

Definition at line 82 of file IntervalSetMap.h.

template<typename I , typename S >
typedef S Sawyer::Container::IntervalSetMap< I, S >::Set

Set type for values.

Definition at line 83 of file IntervalSetMap.h.

Member Function Documentation

template<typename I , typename S >
Set Sawyer::Container::IntervalSetMap< I, S >::getUnion ( const Interval interval) const
inline

Union of values over an interval of keys.

Returns the union of the sets stored across an interval of keys.

Definition at line 92 of file IntervalSetMap.h.

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

template<typename I , typename S >
Set Sawyer::Container::IntervalSetMap< I, S >::getIntersection ( const Interval interval) const
inline

Intersection of values over an interval of keys.

Returns the set of values that are present for all keys in the interval.

Definition at line 105 of file IntervalSetMap.h.

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

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::exists ( const Interval interval) const
inline

Determines if values are stored for an interval.

Returns true if get(interval) would return a non-empty set.

Definition at line 126 of file IntervalSetMap.h.

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::existsAnywhere ( const Interval interval,
const typename Set::Value value 
) const
inline

Determines if a particular value is stored in an interval.

Returns true if getUnion(interval) would return a set containing value as a member. In particular, this returns false if the interval is empty. This is more efficient than calling getUnion(interval) and checking whether it contains value.

Definition at line 135 of file IntervalSetMap.h.

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

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::existsEverywhere ( const Interval interval,
const typename Set::Value value 
) const
inline

Determines if a particular value is stored everywhere in the interval.

Returns true if getIntersection(interval) would return a set containing value as a member. In particular, this returns false if the interval is empty. This is more efficient than calling getIntersection(interval) and checking whether it contains value.

Definition at line 148 of file IntervalSetMap.h.

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

template<typename I , typename S >
void Sawyer::Container::IntervalSetMap< I, S >::erase ( const Interval interval)
inline

Erase sets for an interval.

Erases the sets associated with the given interval of keys.

Definition at line 166 of file IntervalSetMap.h.

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

Referenced by Sawyer::Container::IntervalSetMap< I, S >::erase().

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::erase ( const Interval interval,
const typename Set::Value value 
)
inline

Erases one value from a set over an interval.

Erases the specified value from all sets over the specified interval of keys. Any sets that become empty are removed from the map as if erase had been called on that sub-interval.

Definition at line 174 of file IntervalSetMap.h.

References Sawyer::Container::IntervalSetMap< I, S >::erase().

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::erase ( const Interval interval,
const Set values 
)
inline

Erase specified values from the sets of an interval.

Erases the specified values from all sets over the specified interval of keys. Any sets that become empty are removed from the map as if single-argument erase hd been called on that sub-interval. Returns true if any values were erased, false if none of the values were members of the affected sets.

Definition at line 185 of file IntervalSetMap.h.

References Sawyer::Container::IntervalMap< I, S >::findFirstOverlap(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::Interval< T >::intersection(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, S >::nodes(), and Sawyer::Container::IntervalSetMap< I, S >::replace().

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::insert ( const Interval interval,
const typename Set::Value value 
)
inline

Insert one value to the sets of an interval.

Inserts the specified value to all sets in the interval of keys. Returns true if the value was inserted anywhere, false if the value already existed everywhere.

Definition at line 213 of file IntervalSetMap.h.

template<typename I , typename S >
bool Sawyer::Container::IntervalSetMap< I, S >::insert ( const Interval interval,
const Set values 
)
inline

Insert a set of values into the sets of an interval.

Inserts the specified values into all sets in the interval of keys. Returns true if any value was inserted anywhere, false if all values already existed in the sets of all specified keys.

Definition at line 223 of file IntervalSetMap.h.

References Sawyer::Container::IntervalMap< I, S >::findFirstOverlap(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::IntervalMap< I, S >::insert(), Sawyer::Container::Interval< T >::intersection(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), and Sawyer::Container::IntervalMap< I, S >::nodes().

template<typename I , typename S >
void Sawyer::Container::IntervalSetMap< I, S >::replace ( const Interval interval,
const Set set 
)
inline

Replace sets with a new set.

Replaces sets for keys in the specified interval with the specified set.

Definition at line 252 of file IntervalSetMap.h.

References Sawyer::Container::IntervalMap< I, S >::erase(), and Sawyer::Container::IntervalMap< I, S >::insert().

Referenced by Sawyer::Container::IntervalSetMap< I, S >::erase().


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