ROSE  0.11.51.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 
230  bool isOverlapping(const Interval &other) const {
231  return !intersection(other).isEmpty();
232  }
233 
238  bool isContaining(const Interval &other) const {
239  return (other.isEmpty() ||
240  (!isEmpty() && least()<=other.least() && greatest()>=other.greatest()));
241  }
242 
249  bool isLeftAdjacent(const Interval &right) const {
250  return isEmpty() || right.isEmpty() || (!isWhole() && greatest()+1 == right.least());
251  }
252  bool isRightAdjacent(const Interval &left) const {
253  return isEmpty() || left.isEmpty() || (!left.isWhole() && left.greatest()+1 == least());
254  }
255  bool isAdjacent(const Interval &other) const {
256  return (isEmpty() || other.isEmpty() ||
257  (!isWhole() && greatest()+1 == other.least()) ||
258  (!other.isWhole() && other.greatest()+1 == least()));
259  }
268  bool isLeftOf(const Interval &right) const {
269  return isEmpty() || right.isEmpty() || greatest() < right.least();
270  }
271  bool isRightOf(const Interval &left) const {
272  return isEmpty() || left.isEmpty() || left.greatest() < least();
273  }
279  Value size() const {
280  return isEmpty() ? 0 : hi_ - lo_ + 1;
281  }
282 
289  bool operator==(const Interval &other) const {
290  return lo_==other.lo_ && hi_==other.hi_;
291  }
292  bool operator!=(const Interval &other) const {
293  return lo_!=other.lo_ || hi_!=other.hi_;
294  }
302  Interval intersection(const Interval &other) const {
303  if (isEmpty() || other.isEmpty() || greatest()<other.least() || least()>other.greatest())
304  return Interval();
305  return Interval::hull(std::max(least(), other.least()), std::min(greatest(), other.greatest()));
306  }
307  Interval operator&(const Interval &other) const {
308  return intersection(other);
309  }
317  Interval hull(const Interval &other) const {
318  if (isEmpty()) {
319  return other;
320  } else if (other.isEmpty()) {
321  return *this;
322  } else {
323  return Interval::hull(std::min(least(), other.least()), std::max(greatest(), other.greatest()));
324  }
325  }
326 
330  Interval hull(T value) const {
331  if (isEmpty()) {
332  return Interval(value);
333  } else {
334  return Interval::hull(std::min(least(), value), std::max(greatest(), value));
335  }
336  }
337 
344  std::pair<Interval, Interval> split(T splitPoint) const {
345  if (isEmpty()) {
346  return std::make_pair(Interval(), Interval());
347  } else if (splitPoint < least()) {
348  return std::make_pair(Interval(), *this);
349  } else if (splitPoint < greatest()) {
350  return std::make_pair(Interval::hull(least(), splitPoint), Interval::hull(splitPoint+1, greatest()));
351  } else {
352  return std::make_pair(*this, Interval());
353  }
354  }
355 
363  Interval join(const Interval &right) const {
364  if (isEmpty()) {
365  return right;
366  } else if (right.isEmpty()) {
367  return *this;
368  } else {
369  ASSERT_require(greatest()+1 == right.least() && right.least() > greatest());
370  return hull(right);
371  }
372  }
373 
379  Interval shiftRightSat(Value n) const {
380  if (isEmpty() || baseSizeOverflows(least(), n)) {
381  return Interval();
382  } else if (baseSizeOverflows(greatest(), n)) {
383  return hull(least() + n, boost::integer_traits<T>::const_max);
384  } else {
385  return hull(least() + n, greatest() + n);
386  }
387  }
388 
389  // These types are needed for BOOST_FOREACH but are not advertised as part of this interface.
390  typedef ConstIterator const_iterator;
391  typedef ConstIterator iterator;
392 
400  ConstIterator begin() const {
401  return isEmpty() ? ConstIterator() : ConstIterator(least(), greatest(), least());
402  }
403 
411  ConstIterator end() const {
412  return isEmpty() ? ConstIterator() : ++ConstIterator(least(), greatest(), greatest());
413  }
414 
416  boost::iterator_range<ConstIterator> values() const {
417  return boost::iterator_range<ConstIterator>(begin(), end());
418  }
419 
420  // The following trickery is to allow things like "if (x)" to work but without having an implicit
421  // conversion to bool which would cause no end of other problems. This is fixed in C++11
422 private:
423  typedef void(Interval::*unspecified_bool)() const;
424  void this_type_does_not_support_comparisons() const {}
425 public:
438  operator unspecified_bool() const {
439  return isEmpty() ? 0 : &Interval::this_type_does_not_support_comparisons;
440  }
441 };
442 
443 } // namespace
444 } // namespace
445 
446 #endif
Interval shiftRightSat(Value n) const
Shift interval upward.
Definition: Interval.h:379
std::pair< Interval, Interval > split(T splitPoint) const
Split interval in two.
Definition: Interval.h:344
Interval operator&(const Interval &other) const
Intersection.
Definition: Interval.h:307
bool isOverlapping(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:230
Value size() const
Size of interval.
Definition: Interval.h:279
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:302
ConstIterator end() const
Iterator positioned one past the greatest value.
Definition: Interval.h:411
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:249
bool isSingleton() const
True if interval is a singleton.
Definition: Interval.h:222
bool isContaining(const Interval &other) const
Containment predicate.
Definition: Interval.h:238
Interval hull(T value) const
Hull.
Definition: Interval.h:330
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:363
Name space for the entire library.
Definition: FeasiblePath.h:787
bool isAdjacent(const Interval &other) const
Adjacency predicate.
Definition: Interval.h:255
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:400
bool isLeftOf(const Interval &right) const
Relative position predicate.
Definition: Interval.h:268
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:292
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:416
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
Interval hull(const Interval &other) const
Hull.
Definition: Interval.h:317
Range of values delimited by endpoints.
Definition: Interval.h:33
bool operator==(const Interval &other) const
Equality test.
Definition: Interval.h:289
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:271
Interval()
Constructs an empty interval.
Definition: Interval.h:130
bool isRightAdjacent(const Interval &left) const
Adjacency predicate.
Definition: Interval.h:252