ROSE  0.9.9.139
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:
35  typedef T Value;
36 private:
37  T lo_, hi_;
38 
39 private:
40  friend class boost::serialization::access;
41 
42  template<class S>
43  void serialize(S &s, const unsigned /*version*/) {
44  s & BOOST_SERIALIZATION_NVP(lo_);
45  s & BOOST_SERIALIZATION_NVP(hi_);
46  }
47 
48 public:
62  class ConstIterator: public boost::iterator_facade<ConstIterator, const Value, boost::bidirectional_traversal_tag,
63  Value> {
64  friend class Interval;
65  friend class boost::iterator_core_access;
66 
67  T first_, cur_, last_;
68  bool atEnd_;
69 
70  ConstIterator(T first, T last, T cur): first_(first), cur_(cur), last_(last), atEnd_(false) {}
71  public:
77  ConstIterator(): first_(0), cur_(0), last_(0), atEnd_(true) {}
78 
84  bool atEnd() const {
85  return atEnd_;
86  }
87 
88  private:
89  Value dereference() const {
90  ASSERT_forbid(atEnd());
91  return cur_;
92  }
93 
94  bool equal(const ConstIterator &other) const {
95  if (atEnd() || other.atEnd())
96  return atEnd() && other.atEnd();
97  return cur_ == other.cur_;
98  }
99 
100  // Incrementing an iterator associated with an empty interval is a no-op, and such an interval's @ref atEnd always
101  // returns true. Otherwise, incrementing an iterator positioned one past the interval's greatest end is a
102  // no-op. Otherwise, incrementing an iterator positioned one prior to the interval's least end returns the iterator to
103  // the interval's least value. Otherwise the iterator derefences to a value one greater than before this call.
104  void increment() {
105  if (cur_ == last_) { // avoid overflow
106  atEnd_ = true;
107  } else if (atEnd_) {
108  ASSERT_require(cur_ == first_);
109  atEnd_ = false;
110  } else {
111  ++cur_;
112  }
113  }
114 
115  void decrement() {
116  if (cur_ == first_) { // avoid overflow
117  atEnd_ = true;
118  } else if (atEnd_) {
119  ASSERT_require(cur_ == last_);
120  atEnd_ = false;
121  } else {
122  --cur_;
123  }
124  }
125  };
126 
127 public:
129  Interval(): lo_(1), hi_(0) {}
130 
132  Interval(const Interval &other): lo_(other.lo_), hi_(other.hi_) {}
133 
135  Interval(T value): lo_(value), hi_(value) {}
136 
137 #if 0 // [Robb Matzke 2014-05-14]: too much confusion with "hi" vs. "size". Use either baseSize or hull instead.
138 
142  Interval(T lo, T hi): lo_(lo), hi_(hi) {
143  ASSERT_require(lo <= hi);
144  }
145 #endif
146 
150  static Interval hull(T v1, T v2) {
151  Interval retval;
152  retval.lo_ = std::min(v1, v2);
153  retval.hi_ = std::max(v1, v2);
154  return retval;
155  }
156 
161  static Interval baseSize(T lo, T size) {
162  ASSERT_require2(lo + size >= lo, "overflow");
163  return 0==size ? Interval() : Interval::hull(lo, lo+size-1);
164  }
165 
167  static Interval whole() {
168  return hull(boost::integer_traits<T>::const_min, boost::integer_traits<T>::const_max);
169  }
170 
172  Interval& operator=(const Interval &other) {
173  lo_ = other.lo_;
174  hi_ = other.hi_;
175  return *this;
176  }
177 
179  Interval& operator=(T value) {
180  lo_ = hi_ = value;
181  return *this;
182  }
183 
185  T least() const {
186  ASSERT_forbid(isEmpty());
187  return lo_;
188  }
189 
191  T greatest() const {
192  ASSERT_forbid(isEmpty());
193  return hi_;
194  }
195 
197  bool isEmpty() const { return 1==lo_ && 0==hi_; }
198 
200  bool isSingleton() const { return lo_ == hi_; }
201 
203  bool isWhole() const { return lo_==boost::integer_traits<T>::const_min && hi_==boost::integer_traits<T>::const_max; }
204 
208  bool isOverlapping(const Interval &other) const {
209  return !intersection(other).isEmpty();
210  }
211 
216  bool isContaining(const Interval &other) const {
217  return (other.isEmpty() ||
218  (!isEmpty() && least()<=other.least() && greatest()>=other.greatest()));
219  }
220 
227  bool isLeftAdjacent(const Interval &right) const {
228  return isEmpty() || right.isEmpty() || (!isWhole() && greatest()+1 == right.least());
229  }
230  bool isRightAdjacent(const Interval &left) const {
231  return isEmpty() || left.isEmpty() || (!left.isWhole() && left.greatest()+1 == least());
232  }
233  bool isAdjacent(const Interval &other) const {
234  return (isEmpty() || other.isEmpty() ||
235  (!isWhole() && greatest()+1 == other.least()) ||
236  (!other.isWhole() && other.greatest()+1 == least()));
237  }
246  bool isLeftOf(const Interval &right) const {
247  return isEmpty() || right.isEmpty() || greatest() < right.least();
248  }
249  bool isRightOf(const Interval &left) const {
250  return isEmpty() || left.isEmpty() || left.greatest() < least();
251  }
257  Value size() const { return isEmpty() ? 0 : hi_ - lo_ + 1; }
258 
265  bool operator==(const Interval &other) const {
266  return lo_==other.lo_ && hi_==other.hi_;
267  }
268  bool operator!=(const Interval &other) const {
269  return lo_!=other.lo_ || hi_!=other.hi_;
270  }
278  Interval intersection(const Interval &other) const {
279  if (isEmpty() || other.isEmpty() || greatest()<other.least() || least()>other.greatest())
280  return Interval();
281  return Interval::hull(std::max(least(), other.least()), std::min(greatest(), other.greatest()));
282  }
283  Interval operator&(const Interval &other) const {
284  return intersection(other);
285  }
293  Interval hull(const Interval &other) const {
294  if (isEmpty()) {
295  return other;
296  } else if (other.isEmpty()) {
297  return *this;
298  } else {
299  return Interval::hull(std::min(least(), other.least()), std::max(greatest(), other.greatest()));
300  }
301  }
302 
306  Interval hull(T value) const {
307  if (isEmpty()) {
308  return Interval(value);
309  } else {
310  return Interval::hull(std::min(least(), value), std::max(greatest(), value));
311  }
312  }
313 
320  std::pair<Interval, Interval> split(T splitPoint) const {
321  if (isEmpty()) {
322  return std::make_pair(Interval(), Interval());
323  } else if (splitPoint < least()) {
324  return std::make_pair(Interval(), *this);
325  } else if (splitPoint <= greatest()) {
326  return std::make_pair(Interval(least(), splitPoint), Interval(splitPoint+1, greatest()));
327  } else {
328  return std::make_pair(*this, Interval());
329  }
330  }
331 
339  Interval join(const Interval &right) const {
340  if (isEmpty()) {
341  return right;
342  } else if (right.isEmpty()) {
343  return *this;
344  } else {
345  ASSERT_require(greatest()+1 == right.least() && right.least() > greatest());
346  return hull(right);
347  }
348  }
349 
350  // These types are needed for BOOST_FOREACH but are not advertised as part of this interface.
351  typedef ConstIterator const_iterator;
352  typedef ConstIterator iterator;
353 
361  ConstIterator begin() const {
362  return isEmpty() ? ConstIterator() : ConstIterator(least(), greatest(), least());
363  }
364 
372  ConstIterator end() const {
373  return isEmpty() ? ConstIterator() : ++ConstIterator(least(), greatest(), greatest());
374  }
375 
377  boost::iterator_range<ConstIterator> values() const {
378  return boost::iterator_range<ConstIterator>(begin(), end());
379  }
380 
381  // The following trickery is to allow things like "if (x)" to work but without having an implicit
382  // conversion to bool which would cause no end of other problems. This is fixed in C++11
383 private:
384  typedef void(Interval::*unspecified_bool)() const;
385  void this_type_does_not_support_comparisons() const {}
386 public:
399  operator unspecified_bool() const {
400  return isEmpty() ? 0 : &Interval::this_type_does_not_support_comparisons;
401  }
402 };
403 
404 } // namespace
405 } // namespace
406 
407 #endif
std::pair< Interval, Interval > split(T splitPoint) const
Split interval in two.
Definition: Interval.h:320
Interval operator&(const Interval &other) const
Intersection.
Definition: Interval.h:283
bool isOverlapping(const Interval &other) const
True if two intervals overlap.
Definition: Interval.h:208
Value size() const
Size of interval.
Definition: Interval.h:257
Interval & operator=(const Interval &other)
Assignment from an interval.
Definition: Interval.h:172
Bidirectional forward iterator.
Definition: Interval.h:62
Interval intersection(const Interval &other) const
Intersection.
Definition: Interval.h:278
ConstIterator end() const
Iterator positioned one past the greatest value.
Definition: Interval.h:372
bool isEmpty() const
True if interval is empty.
Definition: Interval.h:197
bool isWhole() const
True if interval covers entire space.
Definition: Interval.h:203
bool isLeftAdjacent(const Interval &right) const
Adjacency predicate.
Definition: Interval.h:227
bool isSingleton() const
True if interval is a singleton.
Definition: Interval.h:200
bool isContaining(const Interval &other) const
Containment predicate.
Definition: Interval.h:216
Interval hull(T value) const
Hull.
Definition: Interval.h:306
Interval join(const Interval &right) const
Creates an interval by joining two adjacent intervals.
Definition: Interval.h:339
Name space for the entire library.
Definition: Access.h:11
bool isAdjacent(const Interval &other) const
Adjacency predicate.
Definition: Interval.h:233
static Interval baseSize(T lo, T size)
Construct an interval from one endpoint and a size.
Definition: Interval.h:161
Interval(T value)
Constructs a singleton interval.
Definition: Interval.h:135
ConstIterator begin() const
Iterator positioned at the least value.
Definition: Interval.h:361
bool isLeftOf(const Interval &right) const
Relative position predicate.
Definition: Interval.h:246
T least() const
Returns lower limit.
Definition: Interval.h:185
static Interval whole()
Construct an interval that covers the entire domain.
Definition: Interval.h:167
static Interval hull(T v1, T v2)
Construct an interval from two endpoints.
Definition: Interval.h:150
Interval & operator=(T value)
Assignment from a scalar.
Definition: Interval.h:179
bool operator!=(const Interval &other) const
Equality test.
Definition: Interval.h:268
bool atEnd() const
Predicate to determine if an iterator is at one of its end positions.
Definition: Interval.h:84
boost::iterator_range< ConstIterator > values() const
Iterator range for values.
Definition: Interval.h:377
ConstIterator()
Create an empty iterator.
Definition: Interval.h:77
Interval hull(const Interval &other) const
Hull.
Definition: Interval.h:293
Range of values delimited by endpoints.
Definition: Interval.h:33
bool operator==(const Interval &other) const
Equality test.
Definition: Interval.h:265
T greatest() const
Returns upper limit.
Definition: Interval.h:191
Interval(const Interval &other)
Copy-constructs an interval.
Definition: Interval.h:132
bool isRightOf(const Interval &left) const
Relative position predicate.
Definition: Interval.h:249
Interval()
Constructs an empty interval.
Definition: Interval.h:129
bool isRightAdjacent(const Interval &left) const
Adjacency predicate.
Definition: Interval.h:230