ROSE 0.11.145.147
IntervalSetMap.h
1// WARNING: Changes to this file must be contributed back to Sawyer or else they will
2// be clobbered by the next update from Sawyer. The Sawyer repository is at
3// https://gitlab.com/charger7534/sawyer.git.
4
5
6
7
8#ifndef Sawyer_Container_IntervalSetMap_H
9#define Sawyer_Container_IntervalSetMap_H
10
11#include <boost/foreach.hpp>
12#include <Sawyer/IntervalMap.h>
13#include <Sawyer/Sawyer.h>
14
15namespace Sawyer {
16namespace Container {
17
78template<typename I, typename S>
79class IntervalSetMap: public IntervalMap<I, S> {
81public:
82 typedef I Interval;
83 typedef S Set;
86 // Iterators
88public:
92 Set getUnion(const Interval &interval) const {
93 Set retval;
94 BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
95 BOOST_FOREACH (const typename Set::Value &member, node.value().values()) {
96 retval.insert(member);
97 }
98 }
99 return retval;
100 }
101
105 Set getIntersection(const Interval &interval) const {
106 Set retval;
107 size_t nNodes = 0;
108 BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
109 const Set &set = this->get(node.key().least());
110 if (1 == ++nNodes) {
111 retval = set;
112 } else {
113 retval &= set;
114 }
115 }
116 return retval;
117 }
118
120 // Predicates and queries
122public:
126 bool exists(const Interval &interval) const {
127 return Super::contains(interval);
128 }
129
135 bool existsAnywhere(const Interval &interval, const typename Set::Value &value) const {
136 BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
137 if (node.value().exists(value))
138 return true;
139 }
140 return false;
141 }
142
148 bool existsEverywhere(const Interval &interval, const typename Set::Value &value) const {
149 if (interval.isEmpty())
150 return false;
151 BOOST_FOREACH (const typename Super::Node &node, this->findAll(interval)) {
152 if (!node.value().exists(value))
153 return false;
154 }
155 return true;
156 }
157
159 // Mutators
161public:
162
166 void erase(const Interval &interval) {
167 Super::erase(interval);
168 }
169
174 bool erase(const Interval &interval, const typename Set::Value &value) {
175 Set set;
176 set.insert(value);
177 return erase(interval, set);
178 }
179
185 bool erase(const Interval &interval, const Set &values) {
186 bool isErased = false;
187 Interval worklist = interval;
188 while (!worklist.isEmpty()) {
189 typename Super::ConstNodeIterator iter = this->findFirstOverlap(worklist);
190 if (iter == this->nodes().end()) {
191 break;
192 } else if (worklist.least() < iter->key().least()) {
193 worklist = Interval::hull(iter->key().least(), worklist.greatest());
194 } else {
195 Interval work = worklist.intersection(iter->key());
196 Set set = this->get(work.least());
197 if (set.erase(values)) {
198 replace(work, set);
199 isErased = true;
200 }
201 if (work == worklist)
202 break;
203 worklist = Interval::hull(work.greatest()+1, worklist.greatest());
204 }
205 }
206 return isErased;
207 }
208
213 bool insert(const Interval &interval, const typename Set::Value &value) {
214 Set set;
215 set.insert(value);
216 return insert(interval, set);
217 }
218
223 bool insert(const Interval &interval, const Set &values) {
224 bool isInserted = false;
225 Interval worklist = interval;
226 while (!worklist.isEmpty()) {
227 typename Super::ConstNodeIterator iter = this->findFirstOverlap(worklist);
228 Set set;
229 Interval work;
230 if (iter == this->nodes().end()) {
231 work = worklist;
232 } else if (worklist.least() < iter->key().least()) {
233 work = Interval::hull(worklist.least(), iter->key().least() - 1);
234 } else {
235 work = worklist.intersection(iter->key());
236 set = this->get(work.least());
237 }
238 if (set.insert(values)) {
239 Super::insert(work, set);
240 isInserted = true;
241 }
242 if (work == worklist)
243 break;
244 worklist = Interval::hull(work.greatest()+1, worklist.greatest());
245 }
246 return isInserted;
247 }
248
252 void replace(const Interval &interval, const Set &set) {
253 if (set.isEmpty()) {
254 Super::erase(interval);
255 } else {
256 Super::insert(interval, set);
257 }
258 }
259};
260
261} // namespace
262} // namespace
263
264#endif
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.
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.
Definition Interval.h:162
Bidirectional iterator over key/value nodes.
Definition Sawyer/Map.h:213
Type for stored nodes.
Definition Sawyer/Map.h:107
const Key & key() const
Key part of key/value node.
Definition Sawyer/Map.h:116
Value & value()
Value part of key/value node.
Definition Sawyer/Map.h:123
T Value
Type of values stored in this set.
Definition Set.h:60
Sawyer support library.