ROSE  0.11.145.0
IntervalSet.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_IntervalSet_H
9 #define Sawyer_IntervalSet_H
10 
11 #include <Sawyer/IntervalMap.h>
12 #include <Sawyer/Optional.h>
13 #include <Sawyer/Sawyer.h>
14 
15 #include <boost/integer_traits.hpp>
16 #include <boost/iterator/iterator_facade.hpp>
17 #include <boost/serialization/access.hpp>
18 #include <boost/serialization/nvp.hpp>
19 
20 namespace Sawyer {
21 namespace Container {
22 
54 template<class I>
55 class IntervalSet {
56  // We use an IntervalMap to do all our work, always storing int(0) as the value.
57  typedef IntervalMap<I, int> Map;
58  Map map_;
59 
60 private:
61  friend class boost::serialization::access;
62 
63  template<class S>
64  void serialize(S &s, const unsigned /*version*/) {
65  s & BOOST_SERIALIZATION_NVP(map_);
66  }
67 
68 public:
69  typedef I Interval;
70  typedef typename I::Value Scalar;
76  class ConstIntervalIterator: public boost::iterator_facade<ConstIntervalIterator, const Interval,
77  boost::bidirectional_traversal_tag> {
78  typedef typename IntervalMap<Interval, int>::ConstNodeIterator MapNodeIterator;
79  MapNodeIterator iter_;
80  public:
82  private:
83  friend class boost::iterator_core_access;
84  friend class IntervalSet;
85  explicit ConstIntervalIterator(MapNodeIterator iter): iter_(iter) {}
86  const Interval& dereference() const { return iter_->key(); }
87  bool equal(const ConstIntervalIterator &other) const { return iter_ == other.iter_; }
88  void increment() { ++iter_; }
89  void decrement() { --iter_; }
90  MapNodeIterator base() const { return iter_; }
91  };
92 
100  class ConstScalarIterator: public boost::iterator_facade<ConstScalarIterator, const typename Interval::Value,
101  boost::bidirectional_traversal_tag> {
102  ConstIntervalIterator iter_;
103  typename Interval::Value offset_;
104  mutable typename Interval::Value value_; // so dereference() can return a reference
105  public:
106  ConstScalarIterator(): offset_(0) {}
107  ConstScalarIterator(ConstIntervalIterator iter): iter_(iter), offset_(0) {}
108  private:
109  friend class boost::iterator_core_access;
110  friend class IntervalSet;
111  const typename Interval::Value& dereference() const {
112  ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
113  ASSERT_require(iter_->least() + offset_ <= iter_->greatest());
114  value_ = iter_->least() + offset_;
115  return value_; // must return a reference
116  }
117  bool equal(const ConstScalarIterator &other) const {
118  return iter_ == other.iter_ && offset_ == other.offset_;
119  }
120  void increment() {
121  ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
122  if (iter_->least() + offset_ == iter_->greatest()) {
123  ++iter_;
124  offset_ = 0;
125  } else {
126  ++offset_;
127  }
128  }
129  void decrement() {
130  ASSERT_require2(iter_->least() <= iter_->greatest(), "stored interval cannot be empty");
131  if (0==offset_) {
132  --iter_;
133  offset_ = width(*iter_);
134  } else {
135  --offset_;
136  }
137  }
138  };
139 
141  // Constructors
143 
148 
152  template<class Interval2>
154  typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
155  for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
156  insert(*otherIter);
157  }
158 
163  template<class Interval2, class T, class Policy>
165  typedef typename IntervalMap<Interval2, T, Policy>::ConstNodeIterator OtherNodeIterator;
166  for (OtherNodeIterator otherIter=other.nodes().begin(); otherIter!=other.nodes().end(); ++otherIter)
167  insert(otherIter->key());
168  }
169 
174  template<class Iterator>
175  IntervalSet(const boost::iterator_range<Iterator> &intervals) {
176  for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
177  insert(*iter);
178  }
179 
184  template<class Interval2>
186  clear();
187  typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
188  for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
189  insert(*otherIter);
190  return *this;
191  }
192 
199  template<class Interval2, class T, class Policy>
201  clear();
202  typedef typename IntervalMap<Interval2, T, Policy>::ConstNodeIterator OtherNodeIterator;
203  for (OtherNodeIterator otherIter=other.nodes().begin(); otherIter!=other.nodes().end(); ++otherIter)
204  insert(otherIter->key());
205  return *this;
206  }
207 
212  template<class Iterator>
213  IntervalSet& operator=(const boost::iterator_range<Iterator> &intervals) {
214  clear();
215  for (Iterator iter=intervals.begin(); iter!=intervals.end(); ++iter)
216  insert(*iter);
217  return *this;
218  }
219 
221  // Iteration
223 
225  boost::iterator_range<ConstIntervalIterator> intervals() const {
226  return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(map_.nodes().begin()),
227  ConstIntervalIterator(map_.nodes().end()));
228  }
229 
231  boost::iterator_range<ConstScalarIterator> scalars() const {
232  return boost::iterator_range<ConstScalarIterator>(ConstScalarIterator(intervals().begin()),
233  ConstScalarIterator(intervals().end()));
234  }
235 
239  ConstIntervalIterator lowerBound(const typename Interval::Value &scalar) const {
240  return ConstIntervalIterator(map_.lowerBound(scalar));
241  }
242 
246  ConstIntervalIterator upperBound(const typename Interval::Value &scalar) const {
247  return ConstIntervalIterator(map_.upperBound(scalar));
248  }
249 
253  ConstIntervalIterator findPrior(const typename Interval::Value &scalar) const {
254  return ConstIntervalIterator(map_.findPrior(scalar));
255  }
256 
260  ConstIntervalIterator find(const typename Interval::Value &scalar) const {
261  return ConstIntervalIterator(map_.find(scalar));
262  }
263 
267  boost::iterator_range<ConstIntervalIterator> findAll(const Interval &interval) const {
268  boost::iterator_range<typename Map::ConstNodeIterator> range = map_.findAll(interval);
269  return boost::iterator_range<ConstIntervalIterator>(ConstIntervalIterator(range.begin()),
270  ConstIntervalIterator(range.end()));
271  }
272 
276  ConstIntervalIterator findFirstOverlap(const Interval &interval) const {
277  return ConstIntervalIterator(map_.findFirstOverlap(interval));
278  }
285  std::pair<ConstIntervalIterator, ConstIntervalIterator>
286  findFirstOverlap(ConstIntervalIterator thisIter, const IntervalSet &other, ConstIntervalIterator otherIter) const {
287  std::pair<typename Map::ConstNodeIterator, typename Map::ConstNodeIterator> found =
288  map_.findFirstOverlap(thisIter.base(), other.map_, otherIter.base());
289  return std::make_pair(ConstIntervalIterator(found.first), ConstIntervalIterator(found.second));
290  }
291 
293  // Size
295 
299  bool isEmpty() const {
300  return map_.isEmpty();
301  }
302 
308  typename Interval::Value size() const {
309  return map_.size();
310  }
311 
316  size_t nIntervals() const {
317  return map_.nIntervals();
318  }
319 
321  Interval hull() const {
322  return map_.hull();
323  }
324 
326  // Predicates
328 
334  template<class Interval2>
335  bool overlaps(const Interval2 &interval) const {
336  return map_.isOverlapping(interval);
337  }
338  template<class Interval2>
339  bool isOverlapping(const Interval2 &interval) const {
340  return overlaps(interval);
341  }
342 
343  template<class Interval2>
344  bool overlaps(const IntervalSet<Interval2> &other) const {
345  return map_.overlaps(other.map_);
346  }
347  template<class Interval2>
348  bool isOverlapping(const IntervalSet<Interval2> &other) const {
349  return overlaps(other);
350  }
351 
352  template<class Interval2, class T2, class Policy2>
354  return map_.overlaps(other);
355  }
356  template<class Interval2, class T2, class Policy2>
358  return overlaps(other);
359  }
367  template<class Interval2>
368  bool isDistinct(const Interval2 &interval) const {
369  return !overlaps();
370  }
371 
372  template<class Interval2>
373  bool isDistinct(const IntervalSet<Interval2> &other) const {
374  return !overlaps(other);
375  }
376 
377  template<class Interval2, class T2, class Policy2>
379  return !overlaps(other);
380  }
386  bool exists(const typename Interval::Value &scalar) const {
387  return find(scalar)!=intervals().end();
388  }
389 
395  bool contains(const typename Interval::Value &scalar) const {
396  return exists(scalar);
397  }
398 
399  template<class Interval2>
400  bool contains(const Interval2 &interval) const {
401  return map_.contains(interval);
402  }
403 
404  template<class Interval2>
405  bool contains(const IntervalSet<Interval2> &other) const {
406  return map_.contains(other.map_);
407  }
408 
409  template<class Interval2, class T2, class Policy2>
411  return map_.contains(other);
412  }
415  // Searching
418 
420  Scalar least() const {
421  ASSERT_forbid(isEmpty());
422  return map_.least();
423  }
424 
426  Scalar greatest() const {
427  ASSERT_forbid(isEmpty());
428  return map_.greatest();
429  }
430 
435  Optional<Scalar> least(Scalar lowerLimit) const {
436  return map_.least(lowerLimit);
437  }
438 
443  Optional<Scalar> greatest(Scalar upperLimit) const {
444  return map_.greatest(upperLimit);
445  }
446 
451  Optional<Scalar> leastNonExistent(Scalar lowerLimit) const {
452  return map_.leastUnmapped(lowerLimit);
453  }
454 
459  Optional<Scalar> greatestNonExistent(Scalar upperLimit) const {
460  return map_.greatestUnmapped(upperLimit);
461  }
462 
472  ConstIntervalIterator firstFit(const typename Interval::Value &size, ConstIntervalIterator start) const {
473  return ConstIntervalIterator(map_.firstFit(size, start.iter_));
474  }
475 
486  ConstIntervalIterator bestFit(const typename Interval::Value &size, ConstIntervalIterator start) const {
487  return ConstIntervalIterator(map_.bestFit(size, start.iter_));
488  }
489 
490 
491 
493  // Modifiers
495 
499  void clear() {
500  map_.clear();
501  }
502 
506  void invert() {
508  }
509 
513  void invert(const Interval &restricted) {
514  IntervalSet inverted;
515  if (!restricted.isEmpty()) {
516  typename Interval::Value pending = restricted.least();
517  bool insertTop = true;
518  for (typename Map::ConstIntervalIterator iter=map_.lowerBound(restricted.least());
519  iter!=map_.intervals().end(); ++iter) {
520  if (iter->least() > restricted.greatest())
521  break;
522  if (pending < iter->least())
523  inverted.insert(Interval::hull(pending, iter->least()-1));
524  if (iter->greatest() < restricted.greatest()) {
525  pending = iter->greatest() + 1;
526  } else {
527  insertTop = false;
528  break;
529  }
530  }
531  if (insertTop)
532  inverted.insert(Interval::hull(pending, restricted.greatest()));
533  }
534  std::swap(map_, inverted.map_);
535  }
536 
543  template<class Interval2>
544  void insert(const Interval2 &interval) {
545  map_.insert(interval, 0);
546  }
547 
548  template<class Interval2>
550  typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIterator;
551  for (OtherIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
552  map_.insert(*otherIter, 0);
553  }
554 
555  template<class Interval2, class T, class Policy>
557  typedef typename IntervalMap<Interval2, T, Policy>::ConstIntervalIterator OtherIterator;
558  for (OtherIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
559  map_.insert(*otherIter, 0);
560  }
569  template<class Interval2>
570  void erase(const Interval2 &interval) {
571  map_.erase(interval);
572  }
573 
574  template<class Interval2>
576  ASSERT_forbid2((void*)&other==(void*)this, "use IntervalSet::clear() instead");
577  typedef typename IntervalSet<Interval2>::ConstIntervalIterator OtherIntervalIterator;
578  for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
579  map_.erase(*otherIter);
580  }
581 
582  template<class Interval2, class T, class Policy>
584  typedef typename IntervalMap<Interval2, T, Policy>::ConstIntervalIterator OtherIntervalIterator;
585  for (OtherIntervalIterator otherIter=other.intervals().begin(); otherIter!=other.intervals().end(); ++otherIter)
586  map_.erase(otherIter->first);
587  }
597  template<class Interval2>
598  void intersect(const Interval2 &interval) {
599  if (isEmpty())
600  return;
601  if (interval.isEmpty()) {
602  clear();
603  return;
604  }
605  if (hull().least() < interval.least())
606  map_.erase(Interval::hull(hull().least(), interval.least()-1));
607  if (hull().greatest() > interval.greatest())
608  map_.erase(Interval::hull(interval.greatest(), hull().greatest()));
609  }
610 
611  template<class Interval2>
613  other.invert(hull());
614  map_.eraseMultiple(other.map_);
615  }
616 
617  template<class Interval2, class T, class Policy>
618  void intersect(const IntervalMap<Interval2, T, Policy> &other);// FIXME[Robb Matzke 2014-04-12]: not implemented yet
622  // Operators
625 
627  bool operator==(const IntervalSet &other) const {
628  return !(*this!=other);
629  }
630 
632  bool operator!=(const IntervalSet &other) const {
633  if (map_.nIntervals()!=other.map_.nIntervals())
634  return true;
635  for (ConstIntervalIterator ai=intervals().begin(), bi=other.intervals().begin(); ai!=intervals().end(); ++ai, ++bi) {
636  if (*ai!=*bi)
637  return true;
638  }
639  return false;
640  }
641 
644  IntervalSet tmp = *this;
645  tmp.invert();
646  return tmp;
647  }
648 
653  insertMultiple(other);
654  return *this;
655  }
656 
660  IntervalSet& operator|=(const Interval &interval) {
661  insert(interval);
662  return *this;
663  }
664 
666  IntervalSet operator|(const IntervalSet &other) const {
667  if (nIntervals() < other.nIntervals()) {
668  IntervalSet tmp = other;
669  tmp.insertMultiple(*this);
670  return tmp;
671  }
672  IntervalSet tmp = *this;
673  tmp.insertMultiple(other);
674  return tmp;
675  }
676 
680  IntervalSet operator|(const Interval &interval) const {
681  IntervalSet retval = *this;
682  retval.insert(interval);
683  return retval;
684  }
685 
690  intersect(other);
691  return *this;
692  }
693 
697  IntervalSet& operator&=(const Interval &interval) {
698  intersect(interval);
699  return *this;
700  }
701 
703  IntervalSet operator&(const IntervalSet &other) const {
704  if (nIntervals() < other.nIntervals()) {
705  IntervalSet tmp = other;
706  tmp.intersect(*this);
707  return tmp;
708  }
709  IntervalSet tmp = *this;
710  tmp.intersect(other);
711  return tmp;
712  }
713 
715  IntervalSet operator&(const Interval &interval) const {
716  IntervalSet retval = *this;
717  retval.intersect(interval);
718  return retval;
719  }
720 
725  eraseMultiple(other);
726  return *this;
727  }
728 
732  IntervalSet& operator-=(const Interval &interval) {
733  erase(interval);
734  return *this;
735  }
736 
740  IntervalSet operator-(const IntervalSet &other) const {
741  IntervalSet tmp = *this;
742  tmp.eraseMultiple(other);
743  return tmp;
744  }
745 
747  IntervalSet operator-(const Interval &interval) const {
748  IntervalSet tmp = *this;
749  tmp.erase(interval);
750  return tmp;
751  }
752 };
753 
754 } // namespace
755 } // namespace
756 
757 #endif
NodeIterator upperBound(const typename Interval::Value &scalar)
Find the first node whose interval begins above the specified scalar key.
Definition: IntervalMap.h:321
NodeIterator firstFit(const typename Interval::Value &size, NodeIterator start)
Find the first fit node at or after a starting point.
Definition: IntervalMap.h:486
IntervalSet operator|(const IntervalSet &other) const
Union of two sets.
Definition: IntervalSet.h:666
Interval hull() const
Returns the range of values in this map.
Definition: IntervalSet.h:321
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterators for traversing keys.
Definition: IntervalMap.h:291
IntervalSet & operator-=(const Interval &interval)
In-place subtraction of an interval.
Definition: IntervalSet.h:732
size_t nIntervals() const
Number of storage nodes.
Definition: IntervalSet.h:316
IntervalSet & operator-=(const IntervalSet &other)
In-place subtraction.
Definition: IntervalSet.h:724
ConstIntervalIterator upperBound(const typename Interval::Value &scalar) const
Find the first node whose interval begins above the specified scalar key.
Definition: IntervalSet.h:246
ConstIntervalIterator bestFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the best fit node at or after a starting point.
Definition: IntervalSet.h:486
Optional< Scalar > greatestNonExistent(Scalar upperLimit) const
Returns the limited-maximum scalar not contained in this set.
Definition: IntervalSet.h:459
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
NodeIterator findPrior(const typename Interval::Value &scalar)
Find the last node whose interval starts at or below the specified scalar key.
Definition: IntervalMap.h:340
IntervalSet & operator&=(const Interval &interval)
In-place intersection with an interval.
Definition: IntervalSet.h:697
IntervalSet operator-(const IntervalSet &other) const
Subtract another set from this one.
Definition: IntervalSet.h:740
IntervalSet & operator&=(const IntervalSet &other)
In-place intersection.
Definition: IntervalSet.h:689
IntervalSet operator~() const
Return inverse of specified set.
Definition: IntervalSet.h:643
bool contains(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set fully contains the argument.
Definition: IntervalSet.h:410
ConstIntervalIterator lowerBound(const typename Interval::Value &scalar) const
Find the first node whose interval ends at or above the specified scalar key.
Definition: IntervalSet.h:239
IntervalSet()
Default constructor.
Definition: IntervalSet.h:147
Interval::Value least() const
Returns the minimum scalar key.
Definition: IntervalMap.h:686
bool exists(const typename Interval::Value &scalar) const
Determines if a value exists in the set.
Definition: IntervalSet.h:386
IntervalSet operator&(const IntervalSet &other) const
Intersection of two sets.
Definition: IntervalSet.h:703
Optional< Scalar > least(Scalar lowerLimit) const
Returns the limited-minimum scalar contained in this set.
Definition: IntervalSet.h:435
bool isEmpty() const
Determine whether the container is empty.
Definition: IntervalSet.h:299
Holds a value or nothing.
Definition: Optional.h:49
NodeIterator bestFit(const typename Interval::Value &size, NodeIterator start)
Find the best fit node at or after a starting point.
Definition: IntervalMap.h:518
bool contains(const Interval2 &interval) const
Determines whether this set fully contains the argument.
Definition: IntervalSet.h:400
bool isOverlapping(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:357
IntervalSet operator&(const Interval &interval) const
Intersection of set with interval.
Definition: IntervalSet.h:715
IntervalSet operator-(const Interval &interval) const
Subtract an interval from this set.
Definition: IntervalSet.h:747
bool operator!=(const IntervalSet &other) const
Determines if two sets contain different elements.
Definition: IntervalSet.h:632
IntervalSet(const boost::iterator_range< Iterator > &intervals)
Construct from an iterator range.
Definition: IntervalSet.h:175
bool isDistinct(const IntervalSet< Interval2 > &other) const
Determines whether this set is distinct from the argument.
Definition: IntervalSet.h:373
T Value
Types of values in the interval.
Definition: Interval.h:36
bool overlaps(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:353
Interval::Value size() const
Returns the number of values represented by this container.
Definition: IntervalMap.h:681
bool isEmpty() const
Determine if the container is empty.
Definition: IntervalMap.h:665
Interval::Value greatest() const
Returns the maximum scalar key.
Definition: IntervalMap.h:692
void insertMultiple(const IntervalSet< Interval2 > &other)
Insert specified values.
Definition: IntervalSet.h:549
IntervalSet(const IntervalSet< Interval2 > &other)
Copy constructor.
Definition: IntervalSet.h:153
A container holding a set of values.
Definition: IntervalSet.h:55
IntervalSet & operator|=(const IntervalSet &other)
In-place union.
Definition: IntervalSet.h:652
void insert(const Interval2 &interval)
Insert specified values.
Definition: IntervalSet.h:544
Name space for the entire library.
Definition: FeasiblePath.h:767
void eraseMultiple(const IntervalSet< Interval2 > &other)
Remove specified values.
Definition: IntervalSet.h:575
Optional< typename Interval::Value > leastUnmapped(typename Interval::Value lowerLimit) const
Returns the limited-minimum unmapped scalar key.
Definition: IntervalMap.h:724
T least() const
Returns lower limit.
Definition: Interval.h:207
IntervalSet operator|(const Interval &interval) const
Union of set with interval.
Definition: IntervalSet.h:680
NodeIterator findFirstOverlap(const Interval &interval)
Find first interval that overlaps with the specified interval.
Definition: IntervalMap.h:415
ConstIntervalIterator findPrior(const typename Interval::Value &scalar) const
Find the last node whose interval starts at or below the specified scalar key.
Definition: IntervalSet.h:253
IntervalSet(const IntervalMap< Interval2, T, Policy > &other)
Construct from an IntervalMap.
Definition: IntervalSet.h:164
void clear()
Empties the container.
Definition: IntervalMap.h:764
void erase(const Interval &erasure)
Erase the specified interval.
Definition: IntervalMap.h:770
IntervalSet & operator=(const IntervalMap< Interval2, T, Policy > &other)
Assignment from an IntervalMap.
Definition: IntervalSet.h:200
boost::iterator_range< ConstScalarIterator > scalars() const
Iterator range for all scalar values logically represented by this set.
Definition: IntervalSet.h:231
void insert(Interval key, Value value, bool makeHole=true)
Insert a key/value pair.
Definition: IntervalMap.h:838
void erase(const Interval2 &interval)
Remove specified values.
Definition: IntervalSet.h:570
static Interval whole()
Construct an interval that covers the entire domain.
Definition: Interval.h:180
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:151
ConstIntervalIterator findFirstOverlap(const Interval &interval) const
Finds first node that overlaps with the specified interval.
Definition: IntervalSet.h:276
Optional< Scalar > greatest(Scalar upperLimit) const
Returns the limited-maximum scalar contained in this set.
Definition: IntervalSet.h:443
bool isOverlapping(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:348
Optional< typename Interval::Value > greatestUnmapped(typename Interval::Value upperLimit) const
Returns the limited-maximum unmapped scalar key.
Definition: IntervalMap.h:739
bool contains(const typename Interval::Value &scalar) const
Determines whether this set fully contains the argument.
Definition: IntervalSet.h:395
void intersect(const Interval2 &interval)
Interset with specified values.
Definition: IntervalSet.h:598
void eraseMultiple(const IntervalMap< Interval2, T, Policy > &other)
Remove specified values.
Definition: IntervalSet.h:583
boost::iterator_range< NodeIterator > nodes()
Iterators for traversing nodes.
Definition: IntervalMap.h:283
Optional< Scalar > leastNonExistent(Scalar lowerLimit) const
Returns the limited-minimum scalar not contained in this set.
Definition: IntervalSet.h:451
Interval hull() const
Returns the range of values in this map.
Definition: IntervalMap.h:753
IntervalSet & operator=(const boost::iterator_range< Iterator > &intervals)
Assignment from an iterator range.
Definition: IntervalSet.h:213
bool isOverlapping(const Interval2 &interval) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:339
void clear()
Remove all values.
Definition: IntervalSet.h:499
boost::iterator_range< NodeIterator > findAll(const Interval &interval)
Finds all nodes overlapping the specified interval.
Definition: IntervalMap.h:390
IntervalSet & operator=(const IntervalSet< Interval2 > &other)
Assignment from another set.
Definition: IntervalSet.h:185
boost::iterator_range< ConstIntervalIterator > intervals() const
Iterator range for all intervals actually stored by this set.
Definition: IntervalSet.h:225
Scalar least() const
Returns the minimum scalar contained in this set.
Definition: IntervalSet.h:420
IntervalSet & operator|=(const Interval &interval)
In-place union with interval.
Definition: IntervalSet.h:660
bool isDistinct(const IntervalMap< Interval2, T2, Policy2 > &other) const
Determines whether this set is distinct from the argument.
Definition: IntervalSet.h:378
bool isDistinct(const Interval2 &interval) const
Determines whether this set is distinct from the argument.
Definition: IntervalSet.h:368
Bidirectional iterator over keys.
Definition: Sawyer/Map.h:225
void insertMultiple(const IntervalMap< Interval2, T, Policy > &other)
Insert specified values.
Definition: IntervalSet.h:556
size_t nIntervals() const
Number of nodes in the container.
Definition: IntervalMap.h:673
void invert(const Interval &restricted)
Invert and intersect.
Definition: IntervalSet.h:513
NodeIterator lowerBound(const typename Interval::Value &scalar)
Find the first node whose interval ends at or above the specified scalar key.
Definition: IntervalMap.h:308
Interval::Value size() const
Number of scalar elements represented.
Definition: IntervalSet.h:308
bool contains(const IntervalSet< Interval2 > &other) const
Determines whether this set fully contains the argument.
Definition: IntervalSet.h:405
ConstIntervalIterator firstFit(const typename Interval::Value &size, ConstIntervalIterator start) const
Find the first fit node at or after a starting point.
Definition: IntervalSet.h:472
T greatest() const
Returns upper limit.
Definition: Interval.h:213
NodeIterator find(const typename Interval::Value &scalar)
Find the node containing the specified scalar key.
Definition: IntervalMap.h:367
bool operator==(const IntervalSet &other) const
Determines if two sets contain the same elements.
Definition: IntervalSet.h:627
void intersect(IntervalSet< Interval2 > other)
Interset with specified values.
Definition: IntervalSet.h:612
Scalar greatest() const
Returns the maximum scalar contained in this set.
Definition: IntervalSet.h:426
ConstIntervalIterator find(const typename Interval::Value &scalar) const
Find the node containing the specified scalar key.
Definition: IntervalSet.h:260
I::Value Scalar
Type of scalar values stored in this set.
Definition: IntervalSet.h:70
void eraseMultiple(const IntervalMap< Interval, T2, Policy2 > &other)
Erase intervals specified in another IntervalMap.
Definition: IntervalMap.h:827
boost::iterator_range< ConstIntervalIterator > findAll(const Interval &interval) const
Finds all nodes overlapping the specified interval.
Definition: IntervalSet.h:267
bool overlaps(const Interval2 &interval) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:335
Bidirectional iterator over key/value nodes.
Definition: Sawyer/Map.h:195
bool overlaps(const IntervalSet< Interval2 > &other) const
Determines whether this set overlaps with the argument.
Definition: IntervalSet.h:344
std::pair< ConstIntervalIterator, ConstIntervalIterator > findFirstOverlap(ConstIntervalIterator thisIter, const IntervalSet &other, ConstIntervalIterator otherIter) const
Find first nodes that overlap.
Definition: IntervalSet.h:286