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:
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:
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:
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:
Querying is also quite efficient. Here we obtain the set of all values stored in the map's sets:
There are also predicates to determine whether a key or value is present in the map.
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 <IntervalSetMap.h>
Public Types | |
| typedef I | Interval |
| Interval type for keys. | |
| typedef S | Set |
| Set type for values. | |
 Public Types inherited from Sawyer::Container::IntervalMap< I, S > | |
| typedef I | Interval |
| Interval type. | |
| typedef S | Value |
| Value type. | |
| typedef Container::Map< Interval, Value, IntervalCompare > | Map |
| Type of the underlying map. | |
| typedef Map::Node | Node |
| Storage node. More... | |
| typedef Map::ConstKeyIterator | ConstIntervalIterator |
| Interval iterator. More... | |
| typedef Map::ValueIterator | ValueIterator |
| Value iterator. More... | |
| typedef Map::ConstValueIterator | ConstValueIterator |
| Value iterator. More... | |
| typedef Map::NodeIterator | NodeIterator |
| Node iterator. More... | |
| typedef Map::ConstNodeIterator | ConstNodeIterator |
| Node iterator. More... | |
Public Member Functions | |
| 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... | |
| IntervalMap & | operator= (const IntervalMap< Interval2, T2, Policy2 > &other) |
| Assignment operator. More... | |
| boost::iterator_range< ConstIntervalIterator > | intervals () const |
| Iterators for traversing keys. More... | |
| Interval | firstUnmapped (typename Interval::Value minAddr) const |
| Find the first unmapped region. More... | |
| Interval | lastUnmapped (typename Interval::Value maxAddr) const |
| Find the last unmapped region. More... | |
| bool | exists (const typename Interval::Value &size) const |
| Returns true if element exists. More... | |
| Optional< Value > | getOptional (const typename Interval::Value &scalar) const |
| Lookup and return a value or nothing. More... | |
| const Value & | getOrDefault (const typename Interval::Value &scalar) const |
| Lookup and return a value or a default. More... | |
| bool | isEmpty () const |
| Determine if the container is empty. More... | |
| size_t | nIntervals () const |
| Number of nodes in the container. More... | |
| Interval::Value | size () const |
| Returns the number of values represented by this container. More... | |
| Interval::Value | least () const |
| Returns the minimum scalar key. | |
| Optional< typename Interval::Value > | least (typename Interval::Value lowerLimit) const |
| Returns the limited-minimum scalar key. More... | |
| Interval::Value | greatest () const |
| Returns the maximum scalar key. | |
| Optional< typename Interval::Value > | greatest (typename Interval::Value upperLimit) const |
| Returns the limited-maximum scalar key. More... | |
| Optional< typename Interval::Value > | leastUnmapped (typename Interval::Value lowerLimit) const |
| Returns the limited-minimum unmapped scalar key. More... | |
| Optional< typename Interval::Value > | greatestUnmapped (typename Interval::Value upperLimit) const |
| Returns the limited-maximum unmapped scalar key. More... | |
| Interval | hull () const |
| Returns the range of values in this map. | |
| void | clear () |
| Empties the container. | |
| void | erase (const Interval &erasure) |
| Erase the specified interval. | |
| 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 | 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< NodeIterator > | nodes () |
| Iterators for traversing nodes. More... | |
| boost::iterator_range< ConstNodeIterator > | nodes () const |
| Iterators for traversing nodes. More... | |
| boost::iterator_range< ValueIterator > | values () |
| Iterators for traversing values. More... | |
| boost::iterator_range< ConstValueIterator > | values () const |
| Iterators for traversing values. More... | |
| NodeIterator | lowerBound (const typename Interval::Value &scalar) |
| Find the first node whose interval ends at or above the specified scalar key. More... | |
| ConstNodeIterator | lowerBound (const typename Interval::Value &scalar) const |
| Find the first node whose interval ends at or above the specified scalar key. More... | |
| NodeIterator | upperBound (const typename Interval::Value &scalar) |
| Find the first node whose interval begins above the specified scalar key. More... | |
| ConstNodeIterator | upperBound (const typename Interval::Value &scalar) const |
| Find the first node whose interval begins above the specified scalar key. More... | |
| const Value & | operator[] (const typename Interval::Value &scalar) const |
| Returns a reference to an existing value. More... | |
| const Value & | get (const typename Interval::Value &scalar) const |
| Returns a reference to an existing value. More... | |
| Value & | getOrElse (const typename Interval::Value &scalar, Value &dflt) |
| Lookup and return a value or something else. More... | |
| const Value & | getOrElse (const typename Interval::Value &scalar, const Value &dflt) const |
| Lookup and return a value or something else. More... | |
| NodeIterator | findPrior (const typename Interval::Value &scalar) |
| Find the last node whose interval starts at or below the specified scalar key. More... | |
| ConstNodeIterator | findPrior (const typename Interval::Value &scalar) const |
| Find the last node whose interval starts at or below the specified scalar key. More... | |
| 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< NodeIterator > | findAll (const Interval &interval) |
| Finds all nodes overlapping the specified interval. More... | |
| boost::iterator_range< ConstNodeIterator > | findAll (const Interval &interval) const |
| Finds all nodes overlapping the specified interval. More... | |
| 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 >::ConstNodeIterator > | findFirstOverlap (typename IntervalMap::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter) |
| Find first interval that overlaps with any in another container. More... | |
| std::pair< ConstNodeIterator, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator > | findFirstOverlap (typename IntervalMap::ConstNodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter) const |
| Find first interval that overlaps with any in another container. More... | |
| 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 >::NodeIterator > | findAllImpl (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 >::ConstNodeIterator > | findFirstOverlapImpl (IMap &imap, typename IntervalMapTraits< IMap >::NodeIterator thisIter, const IntervalMap< Interval, T2, Policy2 > &other, typename IntervalMap< Interval, T2, Policy2 >::ConstNodeIterator otherIter) |
| Find first interval that overlaps with any in another container. More... | |
| 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 Function Documentation
◆ getUnion()
|
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().
◆ getIntersection()
|
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(), Sawyer::Container::IntervalMap< I, S >::get(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key().
◆ exists()
|
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.
◆ existsAnywhere()
|
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().
◆ existsEverywhere()
|
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().
◆ erase() [1/3]
|
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().
◆ erase() [2/3]
|
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().
◆ erase() [3/3]
|
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::IntervalMap< I, S >::get(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, S >::nodes(), Sawyer::Container::IntervalSetMap< I, S >::replace(), and Sawyer::Container::IntervalMap< I, S >::values().
◆ insert() [1/2]
|
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.
◆ insert() [2/2]
|
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::IntervalMap< I, S >::get(), Sawyer::Container::Interval< T >::hull(), Sawyer::Container::IntervalMap< I, S >::insert(), Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key(), Sawyer::Container::IntervalMap< I, S >::nodes(), and Sawyer::Container::IntervalMap< I, S >::values().
◆ replace()
|
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:
