ROSE  0.11.109.0
Interval.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_Interval_H
9 #define Sawyer_Interval_H
10 
11 #include <Sawyer/Assert.h>
12 #include <Sawyer/Sawyer.h>
13 #include <boost/integer_traits.hpp>
14 #include <boost/iterator/iterator_facade.hpp>
15 #include <boost/range/iterator_range.hpp>
16 #include <boost/serialization/access.hpp>
17 #include <boost/serialization/nvp.hpp>
18 
19 namespace Sawyer {
20 namespace Container {
21 
32 template<class T>
33 class Interval {
34 public:
36  typedef T Value;
37 private:
38  T lo_, hi_;
39 
40 private:
41  friend class boost::serialization::access;
42 
43  template<class S>
44  void serialize(S &s, const unsigned /*version*/) {
45  s & BOOST_SERIALIZATION_NVP(lo_);
46  s & BOOST_SERIALIZATION_NVP(hi_);
47  }
48 
49 public:
63  class ConstIterator: public boost::iterator_facade<ConstIterator, const Value, boost::bidirectional_traversal_tag,
64  Value> {
65  friend class Interval;
66  friend class boost::iterator_core_access;
67 
68  T first_, cur_, last_;
69  bool atEnd_;
70 
71  ConstIterator(T first, T last, T cur): first_(first), cur_(cur), last_(last), atEnd_(false) {}
72  public:
78  ConstIterator(): first_(0), cur_(0), last_(0), atEnd_(true) {}
79 
85  bool atEnd() const {
86  return atEnd_;
87  }
88 
89  private:
90  Value dereference() const {
91  ASSERT_forbid(atEnd());
92  return cur_;
93  }
94 
95  bool equal(const ConstIterator &other) const {
96  if (atEnd() || other.atEnd())
97  return atEnd() && other.atEnd();
98  return cur_ == other.cur_;
99  }
100 
101  // Incrementing an iterator associated with an empty interval is a no-op, and such an interval's @ref atEnd always
102  // returns true. Otherwise, incrementing an iterator positioned one past the interval's greatest end is a
103  // no-op. Otherwise, incrementing an iterator positioned one prior to the interval's least end returns the iterator to
104  // the interval's least value. Otherwise the iterator derefences to a value one greater than before this call.
105  void increment() {
106  if (cur_ == last_) { // avoid overflow
107  atEnd_ = true;
108  } else if (atEnd_) {
109  ASSERT_require(cur_ == first_);
110  atEnd_ = false;
111  } else {
112  ++cur_;
113  }
114  }
115 
116  void decrement() {
117  if (cur_ == first_) { // avoid overflow
118  atEnd_ = true;
119  } else if (atEnd_) {
120  ASSERT_require(cur_ == last_);
121  atEnd_ = false;
122  } else {
123  --cur_;
124  }
125  }
126  };
127 
128 public:
130  Interval(): lo_(1), hi_(0) {}
131 
133  Interval(const Interval &other): lo_(other.lo_), hi_(other.hi_) {}
134 
136  Interval(T value): lo_(value), hi_(value) {}
137 
138 #if 0 // [Robb Matzke 2014-05-14]: too much confusion with "hi" vs. "size". Use either baseSize or hull instead.
139 
143  Interval(T lo, T hi): lo_(lo), hi_(hi) {
144  ASSERT_require(lo <= hi);
145  }
146 #endif
147 
151  static Interval hull(T v1, T v2) {
152  Interval retval;
153  retval.lo_ = std::min(v1, v2);
154  retval.hi_ = std::max(v1, v2);
155  return retval;
156  }
157 
162  static Interval baseSize(T lo, T size) {
163  ASSERT_forbid(baseSizeOverflows(lo, size));
164  return 0==size ? Interval() : Interval::hull(lo, lo+size-1);
165  }
166 
171  static Interval baseSizeSat(T lo, T size) {
172  if (baseSizeOverflows(lo, size)) {
173  return hull(lo, boost::integer_traits<T>::const_max);
174  } else {
175  return baseSize(lo, size);
176  }
177  }
178 
180  static Interval whole() {
181  return hull(boost::integer_traits<T>::const_min, boost::integer_traits<T>::const_max);
182  }
183 
185  Interval& operator=(const Interval &other) {
186  lo_ = other.lo_;
187  hi_ = other.hi_;
188  return *this;
189  }
190 
192  Interval& operator=(T value) {
193  lo_ = hi_ = value;
194  return *this;
195  }
196 
201  static bool baseSizeOverflows(T base, T size) {
202  // Warning: This only works when T is unsigned since signed integer overflow is undefined behavior in C++.
203  return base + size < base;
204  }
205 
207  T least() const {
208  ASSERT_forbid(isEmpty());
209  return lo_;
210  }
211 
213  T greatest() const {
214  ASSERT_forbid(isEmpty());
215  return hi_;
216  }
217 
219  bool isEmpty() const { return 1==lo_ && 0==hi_; }
220 
222  bool isSingleton() const { return lo_ == hi_; }
223 
225  bool isWhole() const { return lo_==boost::integer_traits<T>::const_min && hi_==boost::integer_traits<T>::const_max; }
226 
232  bool overlaps(const Interval &other) const {
233  return !intersection(other).isEmpty();
234  }
235  bool isOverlapping(const Interval &other) const {
236  return overlaps(other);
237  }
246  bool contains(const Interval &other) const {
247  return (other.isEmpty() ||
248  (!isEmpty() && least()<=other.least() && greatest()>=other.greatest()));
249  }
250  bool isContaining(const Interval &other) const {
251  return contains(other);
252  }
261  bool isLeftAdjacent(const Interval &right) const {
262  return isEmpty() || right.isEmpty() || (!isWhole() && greatest()+1 == right.least());
263  }
264  bool isRightAdjacent(const Interval &left) const {
265  return isEmpty() || left.isEmpty() || (!left.isWhole() && left.greatest()+1 == least());
266  }
267  bool isAdjacent(const Interval &other) const {
268  return (isEmpty() || other.isEmpty() ||
269  (!isWhole() && greatest()+1 == other.least()) ||
270  (!other.isWhole() && other.greatest()+1 == least()));
271  }
280  bool isLeftOf(const Interval &right) const {
281  return isEmpty() || right.isEmpty() || greatest() < right.least();
282  }
283  bool isRightOf(const Interval &left) const {
284  return isEmpty() || left.isEmpty() || left.greatest() < least();
285  }
291  Value size() const {
292  return isEmpty() ? 0 : hi_ - lo_ + 1;
293  }
294 
301  bool operator==(const Interval &other) const {
302  return lo_==other.lo_ && hi_==other.hi_;
303  }
304  bool operator!=(const Interval &other) const {
305  return lo_!=other.lo_ || hi_!=other.hi_;
306  }
314  Interval intersection(const Interval &other) const {
315  if (isEmpty() || other.isEmpty() || greatest()<other.least() || least()>other.greatest())
316  return Interval();
317  return Interval::hull(std::max(least(), other.least()), std::min(greatest(), other.greatest()));
318  }
319  Interval operator&(const Interval &other) const {
320  return intersection(other);
321  }
329  Interval hull(const Interval &other) const {
330  if (isEmpty()) {
331  return other;
332  } else if (other.isEmpty()) {
333  return *this;
334  } else {
335  return Interval::hull(std::min(least(), other.least()), std::max(greatest(), other.greatest()));
336  }
337  }
338 
342  Interval hull(T value) const {
343  if (isEmpty()) {
344  return Interval(value);
345  } else {
346  return Interval::hull(std::min(least(), value), std::max(greatest(), value));
347  }
348  }
349 
356  std::pair<Interval, Interval> split(T splitPoint) const {
357  if (isEmpty()) {
358  return std::make_pair(Interval(), Interval());
359  } else if (splitPoint < least()) {
360  return std::make_pair(Interval(), *this);
361  } else if (splitPoint < greatest()) {
362  return std::make_pair(Interval::hull(least(), splitPoint), Interval::hull(splitPoint+1, greatest()));
363  } else {
364  return std::make_pair(*this, Interval());
365  }
366  }
367 
375  Interval join(const Interval &right) const {
376  if (isEmpty()) {
377  return right;
378  } else if (right.isEmpty()) {
379  return *this;
380  } else {
381  ASSERT_require(greatest()+1 == right.least() && right.least() > greatest());
382  return hull(right);
383  }
384  }
385 
391  Interval shiftRightSat(Value n) const {
392  if (isEmpty() || baseSizeOverflows(least(), n)) {
393  return Interval();
394  } else if (baseSizeOverflows(greatest(), n)) {
395  return hull(least() + n, boost::integer_traits<T>::const_max);
396  } else {
397  return hull(least() + n, greatest() + n);
398  }
399  }
400 
401  // These types are needed for BOOST_FOREACH but are not advertised as part of this interface.
402  typedef ConstIterator const_iterator;
403  typedef ConstIterator iterator;
404 
412  ConstIterator begin() const {
413  return isEmpty() ? ConstIterator() : ConstIterator(least(), greatest(), least());
414  }
415 
423  ConstIterator end() const {
424  return isEmpty() ? ConstIterator() : ++ConstIterator(least(), greatest(), greatest());
425  }
426 
428  boost::iterator_range<ConstIterator> values() const {
429  return boost::iterator_range<ConstIterator>(begin(), end());
430  }
431 
432  // The following trickery is to allow things like "if (x)" to work but without having an implicit
433  // conversion to bool which would cause no end of other problems. This is fixed in C++11
434 private:
435  typedef void(Interval::*unspecified_bool)() const;
436  void this_type_does_not_support_comparisons() const {}
437 public:
450  operator unspecified_bool() const {
451  return isEmpty() ? 0 : &Interval::this_type_does_not_support_comparisons;
452  }
453 };
454 
455 } // namespace
456 } // namespace
457 
458 #endif
Interval shiftRightSat(Value n) const
Shift interval upward.
Definition: Interval.h:391
std::pair< Interval, Interval > split(T splitPoint) const
Split interval in two.
Definition: Interval.h:356
Interval operator&(const Interval &other) const
Intersection.
Definition: Interval.h:319
bool isOverlapping(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:235
Value size() const
Size of interval.
Definition: Interval.h:291
Interval & operator=(const Interval &other)
Assignment from an interval.
Definition: Interval.h:185
Bidirectional forward iterator.
Definition: Interval.h:63
Interval intersection(const Interval &other) const
Intersection.
Definition: Interval.h:314
ConstIterator end() const
Iterator positioned one past the greatest value.
Definition: Interval.h:423
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:219
bool isWhole() const
True if interval covers entire space.
Definition: Interval.h:225
bool isLeftAdjacent(const Interval &right) const
Adjacency predicate.
Definition: Interval.h:261
bool isSingleton() const
True if interval is a singleton.
Definition: Interval.h:222
bool isContaining(const Interval &other) const
Containment predicate.
Definition: Interval.h:250
Interval hull(T value) const
Hull.
Definition: Interval.h:342
T Value
Types of values in the interval.
Definition: Interval.h:36
Interval join(const Interval &right) const
Creates an interval by joining two adjacent intervals.
Definition: Interval.h:375
Name space for the entire library.
Definition: FeasiblePath.h:767
bool isAdjacent(const Interval &other) const
Adjacency predicate.
Definition: Interval.h:267
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:162
Interval(T value)
Constructs a singleton interval.
Definition: Interval.h:136
ConstIterator begin() const
Iterator positioned at the least value.
Definition: Interval.h:412
bool isLeftOf(const Interval &right) const
Relative position predicate.
Definition: Interval.h:280
bool contains(const Interval &other) const
Containment predicate.
Definition: Interval.h:246
T least() const
Returns lower limit.
Definition: Interval.h:207
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
Interval & operator=(T value)
Assignment from a scalar.
Definition: Interval.h:192
static bool baseSizeOverflows(T base, T size)
Tests whether a base and size overflows.
Definition: Interval.h:201
bool operator!=(const Interval &other) const
Equality test.
Definition: Interval.h:304
bool atEnd() const
Predicate to determine if an iterator is at one of its end positions.
Definition: Interval.h:85
boost::iterator_range< ConstIterator > values() const
Iterator range for values.
Definition: Interval.h:428
ConstIterator()
Create an empty iterator.
Definition: Interval.h:78
static Interval baseSizeSat(T lo, T size)
Construct an interval from one endpoint and size, and clip overflows.
Definition: Interval.h:171
bool overlaps(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:232
Interval hull(const Interval &other) const
Hull.
Definition: Interval.h:329
Range of values delimited by endpoints.
Definition: Interval.h:33
bool operator==(const Interval &other) const
Equality test.
Definition: Interval.h:301
T greatest() const
Returns upper limit.
Definition: Interval.h:213
Interval(const Interval &other)
Copy-constructs an interval.
Definition: Interval.h:133
bool isRightOf(const Interval &left) const
Relative position predicate.
Definition: Interval.h:283
Interval()
Constructs an empty interval.
Definition: Interval.h:130
bool isRightAdjacent(const Interval &left) const
Adjacency predicate.
Definition: Interval.h:264