5 // An Interval<T> is a data structure used to represent a contiguous, mutable
7 // see whether it is included in the interval, comparing two intervals, and
14 // An Interval<T> is represented using the usual C++ STL convention, namely as
15 // the half-open interval [min, max). A point p is considered to be contained in
16 // the interval iff p >= min && p < max. One consequence of this definition is
17 // that for any non-empty interval, min is contained in the interval but max is
18 // not. There is no canonical representation for the empty interval; rather, any
19 // interval where max <= min is regarded as empty. As a consequence, two empty
27 // >).  A difference operator (operator-()) is required if Interval<T>::Length
30 // For equality comparisons, Interval<T> supports an Equals() method and an
33 // compare equal. For ordered comparisons, Interval<T> also provides the
34 // comparator Interval<T>::Less and an operator<() which delegates to it.
44 //   Interval<int> r1(0, 100);  // The interval [0, 100).
47 //   EXPECT_FALSE(r1.Contains(100));  // 100 is just outside the interval.
49 //   Interval<int> r2(50, 150);  // The interval [50, 150).
53 //   EXPECT_EQ(Interval<int>(50, 100), r1);  // r1 is now [50, 100).
55 //   Interval<int> r3(1000, 2000);  // The interval [1000, 2000).
74 class Interval {
78   // Type trait for deriving the return type for Interval::Length.  If
97   using Less = std::less<Interval>;
99   // Construct an Interval representing an empty interval.
100   Interval() : min_(), max_() {}  in Interval()  function
102   // Construct an Interval representing the interval [min, max). If min < max,
103   // the constructed object will represent the non-empty interval containing all
105   // max, the constructed object will represent the empty interval.
106   Interval(const T& min, const T& max) : min_(min), max_(max) {}  in Interval()  function
119   void CopyFrom(const Interval& i) { *this = i; }  in CopyFrom()
120   bool Equals(const Interval& i) const { return *this == i; }  in Equals()
123   // Returns the length of this interval. The value returned is zero if
133   // returns false when i is the empty interval.
134   bool Contains(const Interval& i) const {  in Contains()
140   bool Intersects(const Interval& i) const {  in Intersects()
149   bool Intersects(const Interval& i, Interval* out) const;
153   bool IntersectWith(const Interval& i);
155   // Calculates the smallest interval containing both *this i, and updates *this
156   // to represent that interval, and returns true iff *this was modified.
157   bool SpanningUnion(const Interval& i);
160   // Difference(Interval&, vector*), but stores the results directly in out
161   // parameters rather than dynamically allocating an Interval* and appending
165   // empty interval (it is possible that *lo will be empty and *hi non-empty).
167   bool Difference(const Interval& i, Interval* lo, Interval* hi) const;
169   friend bool operator==(const Interval& a, const Interval& b) {
179   friend bool operator!=(const Interval& a, const Interval& b) {
191   friend bool operator<(const Interval& a, const Interval& b) {
195   friend std::ostream& operator<<(std::ostream& out, const Interval& i) {
208 bool Interval<T>::Intersects(const Interval& i, Interval* out) const {  in Intersects()
212     *out = Interval(std::max(min(), i.min()), std::min(max(), i.max()));  in Intersects()
218 bool Interval<T>::IntersectWith(const Interval& i) {  in IntersectWith()
234 bool Interval<T>::SpanningUnion(const Interval& i) {  in SpanningUnion()
254 bool Interval<T>::Difference(const Interval& i,  in Difference()
255                              Interval* lo,  in Difference()
256                              Interval* hi) const {  in Difference()
270     *hi = Interval(i.max(), max());  in Difference()
277     *lo = Interval(min(), i.min());  in Difference()
285     *lo = Interval(min(), i.min());  in Difference()
286     *hi = Interval(i.max(), max());  in Difference()
292     // Intersection is <this>, so difference yields the empty interval.  in Difference()