interval.h 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301
  1. // Copyright 2015 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. //
  5. // An Interval<T> is a data structure used to represent a contiguous, mutable
  6. // range over an ordered type T. Supported operations include testing a value to
  7. // see whether it is included in the interval, comparing two intervals, and
  8. // performing their union, intersection, and difference. For the purposes of
  9. // this library, an "ordered type" is any type that induces a total order on its
  10. // values via its less-than operator (operator<()). Examples of such types are
  11. // basic arithmetic types like int and double as well as class types like
  12. // string.
  13. //
  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
  20. // intervals will still compare as equal despite possibly having different
  21. // underlying min() or max() values. Also beware of the terminology used here:
  22. // the library uses the terms "min" and "max" rather than "begin" and "end" as
  23. // is conventional for the STL.
  24. //
  25. // T is required to be default- and copy-constructable, to have an assignment
  26. // operator, and the full complement of comparison operators (<, <=, ==, !=, >=,
  27. // >). A difference operator (operator-()) is required if Interval<T>::Length
  28. // is used.
  29. //
  30. // For equality comparisons, Interval<T> supports an Equals() method and an
  31. // operator==() which delegates to it. Two intervals are considered equal if
  32. // either they are both empty or if their corresponding min and max fields
  33. // compare equal. For ordered comparisons, Interval<T> also provides the
  34. // comparator Interval<T>::Less and an operator<() which delegates to it.
  35. // Unfortunately this comparator is currently buggy because its behavior is
  36. // inconsistent with Equals(): two empty ranges with different representations
  37. // may be regarded as equivalent by Equals() but regarded as different by
  38. // the comparator. Bug 9240050 has been created to address this.
  39. //
  40. // This class is thread-compatible if T is thread-compatible. (See
  41. // go/thread-compatible).
  42. //
  43. // Examples:
  44. // Interval<int> r1(0, 100); // The interval [0, 100).
  45. // EXPECT_TRUE(r1.Contains(0));
  46. // EXPECT_TRUE(r1.Contains(50));
  47. // EXPECT_FALSE(r1.Contains(100)); // 100 is just outside the interval.
  48. //
  49. // Interval<int> r2(50, 150); // The interval [50, 150).
  50. // EXPECT_TRUE(r1.Intersects(r2));
  51. // EXPECT_FALSE(r1.Contains(r2));
  52. // EXPECT_TRUE(r1.IntersectWith(r2)); // Mutates r1.
  53. // EXPECT_EQ(Interval<int>(50, 100), r1); // r1 is now [50, 100).
  54. //
  55. // Interval<int> r3(1000, 2000); // The interval [1000, 2000).
  56. // EXPECT_TRUE(r1.IntersectWith(r3)); // Mutates r1.
  57. // EXPECT_TRUE(r1.Empty()); // Now r1 is empty.
  58. // EXPECT_FALSE(r1.Contains(r1.min())); // e.g. doesn't contain its own min.
  59. #ifndef NET_BASE_INTERVAL_H_
  60. #define NET_BASE_INTERVAL_H_
  61. #include <stddef.h>
  62. #include <algorithm>
  63. #include <functional>
  64. #include <ostream>
  65. #include <utility>
  66. #include <vector>
  67. namespace net {
  68. template <typename T>
  69. class Interval {
  70. private:
  71. // TODO(rtenneti): Implement after suupport for std::decay.
  72. #if 0
  73. // Type trait for deriving the return type for Interval::Length. If
  74. // operator-() is not defined for T, then the return type is void. This makes
  75. // the signature for Length compile so that the class can be used for such T,
  76. // but code that calls Length would still generate a compilation error.
  77. template <typename U>
  78. class DiffTypeOrVoid {
  79. private:
  80. template <typename V>
  81. static auto f(const V* v) -> decltype(*v - *v);
  82. template <typename V>
  83. static void f(...);
  84. public:
  85. using type = typename std::decay<decltype(f<U>(0))>::type;
  86. };
  87. #endif
  88. public:
  89. // Compatibility alias.
  90. using Less = std::less<Interval>;
  91. // Construct an Interval representing an empty interval.
  92. Interval() : min_(), max_() {}
  93. // Construct an Interval representing the interval [min, max). If min < max,
  94. // the constructed object will represent the non-empty interval containing all
  95. // values from min up to (but not including) max. On the other hand, if min >=
  96. // max, the constructed object will represent the empty interval.
  97. Interval(const T& min, const T& max) : min_(min), max_(max) {}
  98. const T& min() const { return min_; }
  99. const T& max() const { return max_; }
  100. void SetMin(const T& t) { min_ = t; }
  101. void SetMax(const T& t) { max_ = t; }
  102. void Set(const T& min, const T& max) {
  103. SetMin(min);
  104. SetMax(max);
  105. }
  106. void Clear() { *this = {}; }
  107. void CopyFrom(const Interval& i) { *this = i; }
  108. bool Equals(const Interval& i) const { return *this == i; }
  109. bool Empty() const { return min() >= max(); }
  110. // Returns the length of this interval. The value returned is zero if
  111. // IsEmpty() is true; otherwise the value returned is max() - min().
  112. const T Length() const { return (min_ >= max_ ? min_ : max_) - min_; }
  113. // Returns true iff t >= min() && t < max().
  114. bool Contains(const T& t) const { return min() <= t && max() > t; }
  115. // Returns true iff *this and i are non-empty, and *this includes i. "*this
  116. // includes i" means that for all t, if i.Contains(t) then this->Contains(t).
  117. // Note the unintuitive consequence of this definition: this method always
  118. // returns false when i is the empty interval.
  119. bool Contains(const Interval& i) const {
  120. return !Empty() && !i.Empty() && min() <= i.min() && max() >= i.max();
  121. }
  122. // Returns true iff there exists some point t for which this->Contains(t) &&
  123. // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
  124. bool Intersects(const Interval& i) const {
  125. return !Empty() && !i.Empty() && min() < i.max() && max() > i.min();
  126. }
  127. // Returns true iff there exists some point t for which this->Contains(t) &&
  128. // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty.
  129. // Furthermore, if the intersection is non-empty and the intersection pointer
  130. // is not null, this method stores the calculated intersection in
  131. // *intersection.
  132. bool Intersects(const Interval& i, Interval* out) const;
  133. // Sets *this to be the intersection of itself with i. Returns true iff
  134. // *this was modified.
  135. bool IntersectWith(const Interval& i);
  136. // Calculates the smallest interval containing both *this i, and updates *this
  137. // to represent that interval, and returns true iff *this was modified.
  138. bool SpanningUnion(const Interval& i);
  139. // Determines the difference between two intervals as in
  140. // Difference(Interval&, vector*), but stores the results directly in out
  141. // parameters rather than dynamically allocating an Interval* and appending
  142. // it to a vector. If two results are generated, the one with the smaller
  143. // value of min() will be stored in *lo and the other in *hi. Otherwise (if
  144. // fewer than two results are generated), unused arguments will be set to the
  145. // empty interval (it is possible that *lo will be empty and *hi non-empty).
  146. // The method returns true iff the intersection of *this and i is non-empty.
  147. bool Difference(const Interval& i, Interval* lo, Interval* hi) const;
  148. friend bool operator==(const Interval& a, const Interval& b) {
  149. bool ae = a.Empty();
  150. bool be = b.Empty();
  151. if (ae && be)
  152. return true; // All empties are equal.
  153. if (ae != be)
  154. return false; // Empty cannot equal nonempty.
  155. return a.min() == b.min() && a.max() == b.max();
  156. }
  157. friend bool operator!=(const Interval& a, const Interval& b) {
  158. return !(a == b);
  159. }
  160. // Defines a comparator which can be used to induce an order on Intervals, so
  161. // that, for example, they can be stored in an ordered container such as
  162. // std::set. The ordering is arbitrary, but does provide the guarantee that,
  163. // for non-empty intervals X and Y, if X contains Y, then X <= Y.
  164. // TODO(kosak): The current implementation of this comparator has a problem
  165. // because the ordering it induces is inconsistent with that of Equals(). In
  166. // particular, this comparator does not properly consider all empty intervals
  167. // equivalent. Bug b/9240050 has been created to track this.
  168. friend bool operator<(const Interval& a, const Interval& b) {
  169. return a.min() < b.min() || (a.min() == b.min() && a.max() > b.max());
  170. }
  171. friend std::ostream& operator<<(std::ostream& out, const Interval& i) {
  172. return out << "[" << i.min() << ", " << i.max() << ")";
  173. }
  174. private:
  175. T min_; // Inclusive lower bound.
  176. T max_; // Exclusive upper bound.
  177. };
  178. //==============================================================================
  179. // Implementation details: Clients can stop reading here.
  180. template <typename T>
  181. bool Interval<T>::Intersects(const Interval& i, Interval* out) const {
  182. if (!Intersects(i))
  183. return false;
  184. if (out != nullptr) {
  185. *out = Interval(std::max(min(), i.min()), std::min(max(), i.max()));
  186. }
  187. return true;
  188. }
  189. template <typename T>
  190. bool Interval<T>::IntersectWith(const Interval& i) {
  191. if (Empty())
  192. return false;
  193. bool modified = false;
  194. if (i.min() > min()) {
  195. SetMin(i.min());
  196. modified = true;
  197. }
  198. if (i.max() < max()) {
  199. SetMax(i.max());
  200. modified = true;
  201. }
  202. return modified;
  203. }
  204. template <typename T>
  205. bool Interval<T>::SpanningUnion(const Interval& i) {
  206. if (i.Empty())
  207. return false;
  208. if (Empty()) {
  209. *this = i;
  210. return true;
  211. }
  212. bool modified = false;
  213. if (i.min() < min()) {
  214. SetMin(i.min());
  215. modified = true;
  216. }
  217. if (i.max() > max()) {
  218. SetMax(i.max());
  219. modified = true;
  220. }
  221. return modified;
  222. }
  223. template <typename T>
  224. bool Interval<T>::Difference(const Interval& i,
  225. Interval* lo,
  226. Interval* hi) const {
  227. // Initialize *lo and *hi to empty
  228. *lo = {};
  229. *hi = {};
  230. if (Empty())
  231. return false;
  232. if (i.Empty()) {
  233. *lo = *this;
  234. return false;
  235. }
  236. if (min() < i.max() && min() >= i.min() && max() > i.max()) {
  237. // [------ this ------)
  238. // [------ i ------)
  239. // [-- result ---)
  240. *hi = Interval(i.max(), max());
  241. return true;
  242. }
  243. if (max() > i.min() && max() <= i.max() && min() < i.min()) {
  244. // [------ this ------)
  245. // [------ i ------)
  246. // [- result -)
  247. *lo = Interval(min(), i.min());
  248. return true;
  249. }
  250. if (min() < i.min() && max() > i.max()) {
  251. // [------- this --------)
  252. // [---- i ----)
  253. // [ R1 ) [ R2 )
  254. // There are two results: R1 and R2.
  255. *lo = Interval(min(), i.min());
  256. *hi = Interval(i.max(), max());
  257. return true;
  258. }
  259. if (min() >= i.min() && max() <= i.max()) {
  260. // [--- this ---)
  261. // [------ i --------)
  262. // Intersection is <this>, so difference yields the empty interval.
  263. return true;
  264. }
  265. *lo = *this; // No intersection.
  266. return false;
  267. }
  268. } // namespace net
  269. #endif // NET_BASE_INTERVAL_H_