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 <Sawyer/IntervalSetMap.h>

Inheritance diagram for Sawyer::Container::IntervalSetMap< I, S >:

[legend]

Collaboration diagram for Sawyer::Container::IntervalSetMap< I, S >:

[legend]

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.

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
Set	getUnion (const Interval &interval) const
	Union of values over an interval of keys.

Set	getIntersection (const Interval &interval) const
	Intersection of values over an interval of keys.

bool	exists (const Interval &interval) const
	Determines if values are stored for an interval.

bool	existsAnywhere (const Interval &interval, const typename Set::Value &value) const
	Determines if a particular value is stored in an interval.

bool	existsEverywhere (const Interval &interval, const typename Set::Value &value) const
	Determines if a particular value is stored everywhere in the interval.

void	erase (const Interval &interval)
	Erase sets for an interval.

bool	erase (const Interval &interval, const typename Set::Value &value)
	Erases one value from a set over an interval.

bool	erase (const Interval &interval, const Set &values)
	Erase specified values from the sets of an interval.

bool	insert (const Interval &interval, const typename Set::Value &value)
	Insert one value to the sets of an interval.

bool	insert (const Interval &interval, const Set &values)
	Insert a set of values into the sets of an interval.

void	replace (const Interval &interval, const Set &set)
	Replace sets with a new set.

Public Member Functions inherited from Sawyer::Container::IntervalMap< I, S >
	IntervalMap ()
	Default constructor.

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

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.

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

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.

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.

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.

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

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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.

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.

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 S >

typedef I Sawyer::Container::IntervalSetMap< I, S >::Interval

Interval type for keys.

Definition at line 82 of file IntervalSetMap.h.

◆ Set

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

◆ getUnion()

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

◆ getIntersection()

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(), Sawyer::Container::IntervalMap< I, S >::get(), and Sawyer::Container::Map< K, T, Cmp, Alloc >::Node::key().

◆ exists()

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.

◆ existsAnywhere()

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

◆ existsEverywhere()

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

◆ erase() [1/3]

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

◆ erase() [2/3]

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

◆ erase() [3/3]

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::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]

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.

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

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

◆ insert() [2/2]

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

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:

IntervalSetMap.h

Description

Public Types

Public Member Functions

Additional Inherited Members

Member Typedef Documentation

◆ Interval

◆ Set

Member Function Documentation

◆ getUnion()

◆ getIntersection()

◆ exists()

◆ existsAnywhere()

◆ existsEverywhere()

◆ erase() [1/3]

◆ erase() [2/3]

◆ erase() [3/3]

◆ insert() [1/2]

◆ insert() [2/2]

◆ replace()