8#ifndef Sawyer_Container_IntervalSetMap_H
9#define Sawyer_Container_IntervalSetMap_H
11#include <boost/foreach.hpp>
12#include <Sawyer/IntervalMap.h>
13#include <Sawyer/Sawyer.h>
78template<
typename I,
typename S>
95 BOOST_FOREACH (
const typename Set::Value &member, node.
value().values()) {
96 retval.insert(member);
109 const Set &set = this->
get(node.
key().least());
127 return Super::contains(interval);
137 if (node.
value().exists(value))
149 if (interval.isEmpty())
152 if (!node.
value().exists(value))
177 return erase(interval, set);
186 bool isErased =
false;
188 while (!worklist.isEmpty()) {
190 if (iter == this->
nodes().end()) {
192 }
else if (worklist.least() < iter->
key().least()) {
195 Interval work = worklist.intersection(iter->
key());
196 Set set = this->
get(work.least());
201 if (work == worklist)
203 worklist =
Interval::hull(work.greatest()+1, worklist.greatest());
216 return insert(interval, set);
224 bool isInserted =
false;
226 while (!worklist.isEmpty()) {
230 if (iter == this->
nodes().end()) {
232 }
else if (worklist.least() < iter->
key().least()) {
235 work = worklist.intersection(iter->
key());
236 set = this->
get(work.least());
242 if (work == worklist)
244 worklist =
Interval::hull(work.greatest()+1, worklist.greatest());
An associative container whose keys are non-overlapping intervals.
const Value & get(const typename Interval::Value &scalar) const
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
void erase(const Interval &erasure)
Erase the specified interval.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Mapping from integers to sets.
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 insert(const Interval &interval, const Set &values)
Insert a set of values into the sets of an interval.
S Set
Set type for values.
I Interval
Interval type for keys.
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 erase(const Interval &interval, const typename Set::Value &value)
Erases one value from a set over an interval.
void replace(const Interval &interval, const Set &set)
Replace sets with a new set.
void erase(const Interval &interval)
Erase sets for an interval.
bool exists(const Interval &interval) const
Determines if values are stored for an interval.
bool existsEverywhere(const Interval &interval, const typename Set::Value &value) const
Determines if a particular value is stored everywhere in the interval.
bool existsAnywhere(const Interval &interval, const typename Set::Value &value) const
Determines if a particular value is stored in an interval.
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Bidirectional iterator over key/value nodes.
const Key & key() const
Key part of key/value node.
Value & value()
Value part of key/value node.
T Value
Type of values stored in this set.