ROSE  0.9.9.109
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://github.com/matzke1/sawyer.
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 
15 namespace Sawyer {
16 namespace Container {
17 
78 template<typename I, typename S>
79 class IntervalSetMap: public IntervalMap<I, S> {
80  typedef IntervalMap<I, S> Super;
81 public:
82  typedef I Interval;
83  typedef S Set;
85  // Iterators
88 public:
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
122 public:
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
161 public:
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.
Definition: IntervalMap.h:171
bool exists(const Interval &interval) const
Determines if values are stored for an interval.
Interval intersection(const Interval &other) const
Intersection.
Definition: Interval.h:278
Value & value()
Value part of key/value node.
Definition: Sawyer/Map.h:103
Mapping from integers to sets.
bool existsAnywhere(const Interval &interval, const typename Set::Value &value) const
Determines if a particular value is stored in an interval.
Name space for the entire library.
Definition: Access.h:11
bool erase(const Interval &interval, const Set &values)
Erase specified values from the sets of an interval.
boost::iterator_range< ValueIterator > values()
Iterators for traversing values.
Definition: IntervalMap.h:299
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Definition: IntervalMap.h:415
void replace(const Interval &interval, const Set &set)
Replace sets with a new set.
void erase(const Interval &erasure)
Erase the specified interval.
Definition: IntervalMap.h:770
bool erase(const Interval &interval, const typename Set::Value &value)
Erases one value from a set over an interval.
void erase(const Interval &interval)
Erase sets for an interval.
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Definition: IntervalMap.h:838
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
Set getUnion(const Interval &interval) const
Union of values over an interval of keys.
const Key & key() const
Key part of key/value node.
Definition: Sawyer/Map.h:96
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Definition: IntervalMap.h:283
bool insert(const Interval &interval, const typename Set::Value &value)
Insert one value to the sets of an interval.
bool existsEverywhere(const Interval &interval, const typename Set::Value &value) const
Determines if a particular value is stored everywhere in the interval.
Set getIntersection(const Interval &interval) const
Intersection of values over an interval of keys.
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:390
bool insert(const Interval &interval, const Set &values)
Insert a set of values into the sets of an interval.
T Value
Type of values stored in this set.
Definition: Set.h:50
S Set
Set type for values.
I Interval
Interval type for keys.
Type for stored nodes.
Definition: Sawyer/Map.h:87
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:154