| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 60 #ifndef NET_QUIC_INTERVAL_H_ | |
| 61 #define NET_QUIC_INTERVAL_H_ | |
| 62 | |
| 63 #include <stddef.h> | |
| 64 | |
| 65 #include <algorithm> | |
| 66 #include <functional> | |
| 67 #include <ostream> | |
| 68 #include <string> | |
| 69 #include <utility> | |
| 70 #include <vector> | |
| 71 | |
| 72 namespace net { | |
| 73 | |
| 74 template <typename T> | |
| 75 class Interval { | |
| 76 private: | |
| 77 // TODO(rtenneti): Implement after suupport for std::decay. | |
| 78 #if 0 | |
| 79 // Type trait for deriving the return type for Interval::Length. If | |
| 80 // operator-() is not defined for T, then the return type is void. This makes | |
| 81 // the signature for Length compile so that the class can be used for such T, | |
| 82 // but code that calls Length would still generate a compilation error. | |
| 83 template <typename U> | |
| 84 class DiffTypeOrVoid { | |
| 85 private: | |
| 86 template <typename V> | |
| 87 static auto f(const V* v) -> decltype(*v - *v); | |
| 88 template <typename V> | |
| 89 static void f(...); | |
| 90 | |
| 91 public: | |
| 92 using type = typename std::decay<decltype(f<U>(0))>::type; | |
| 93 }; | |
| 94 #endif | |
| 95 | |
| 96 public: | |
| 97 // Compatibility alias. | |
| 98 using Less = std::less<Interval>; | |
| 99 | |
| 100 // Construct an Interval representing an empty interval. | |
| 101 Interval() : min_(), max_() {} | |
| 102 | |
| 103 // Construct an Interval representing the interval [min, max). If min < max, | |
| 104 // the constructed object will represent the non-empty interval containing all | |
| 105 // values from min up to (but not including) max. On the other hand, if min >= | |
| 106 // max, the constructed object will represent the empty interval. | |
| 107 Interval(const T& min, const T& max) : min_(min), max_(max) {} | |
| 108 | |
| 109 const T& min() const { return min_; } | |
| 110 const T& max() const { return max_; } | |
| 111 void SetMin(const T& t) { min_ = t; } | |
| 112 void SetMax(const T& t) { max_ = t; } | |
| 113 | |
| 114 void Set(const T& min, const T& max) { | |
| 115 SetMin(min); | |
| 116 SetMax(max); | |
| 117 } | |
| 118 | |
| 119 void Clear() { *this = {}; } | |
| 120 void CopyFrom(const Interval& i) { *this = i; } | |
| 121 bool Equals(const Interval& i) const { return *this == i; } | |
| 122 bool Empty() const { return min() >= max(); } | |
| 123 | |
| 124 // Returns the length of this interval. The value returned is zero if | |
| 125 // IsEmpty() is true; otherwise the value returned is max() - min(). | |
| 126 const T Length() const { return (min_ >= max_ ? min_ : max_) - min_; } | |
| 127 | |
| 128 // Returns true iff t >= min() && t < max(). | |
| 129 bool Contains(const T& t) const { return min() <= t && max() > t; } | |
| 130 | |
| 131 // Returns true iff *this and i are non-empty, and *this includes i. "*this | |
| 132 // includes i" means that for all t, if i.Contains(t) then this->Contains(t). | |
| 133 // Note the unintuitive consequence of this definition: this method always | |
| 134 // returns false when i is the empty interval. | |
| 135 bool Contains(const Interval& i) const { | |
| 136 return !Empty() && !i.Empty() && min() <= i.min() && max() >= i.max(); | |
| 137 } | |
| 138 | |
| 139 // Returns true iff there exists some point t for which this->Contains(t) && | |
| 140 // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty. | |
| 141 bool Intersects(const Interval& i) const { | |
| 142 return !Empty() && !i.Empty() && min() < i.max() && max() > i.min(); | |
| 143 } | |
| 144 | |
| 145 // Returns true iff there exists some point t for which this->Contains(t) && | |
| 146 // i.Contains(t) evaluates to true, i.e. if the intersection is non-empty. | |
| 147 // Furthermore, if the intersection is non-empty and the intersection pointer | |
| 148 // is not null, this method stores the calculated intersection in | |
| 149 // *intersection. | |
| 150 bool Intersects(const Interval& i, Interval* out) const; | |
| 151 | |
| 152 // Sets *this to be the intersection of itself with i. Returns true iff | |
| 153 // *this was modified. | |
| 154 bool IntersectWith(const Interval& i); | |
| 155 | |
| 156 // Calculates the smallest interval containing both *this i, and updates *this | |
| 157 // to represent that interval, and returns true iff *this was modified. | |
| 158 bool SpanningUnion(const Interval& i); | |
| 159 | |
| 160 // Determines the difference between two intervals by finding all points that | |
| 161 // are contained in *this but not in i, coalesces those points into the | |
| 162 // largest possible contiguous intervals, and appends those intervals to the | |
| 163 // *difference vector. Intuitively this can be thought of as "erasing" i from | |
| 164 // *this. This will either completely erase *this (leaving nothing behind), | |
| 165 // partially erase some of *this from the left or right side (leaving some | |
| 166 // residual behind), or erase a hole in the middle of *this (leaving behind an | |
| 167 // interval on either side). Therefore, 0, 1, or 2 intervals will be appended | |
| 168 // to *difference. The method returns true iff the intersection of *this and i | |
| 169 // is non-empty. The caller owns the vector and the Interval* pointers | |
| 170 // inside it. The difference vector is required to be non-null. | |
| 171 bool Difference(const Interval& i, std::vector<Interval*>* difference) const; | |
| 172 | |
| 173 // Determines the difference between two intervals as in | |
| 174 // Difference(Interval&, vector*), but stores the results directly in out | |
| 175 // parameters rather than dynamically allocating an Interval* and appending | |
| 176 // it to a vector. If two results are generated, the one with the smaller | |
| 177 // value of min() will be stored in *lo and the other in *hi. Otherwise (if | |
| 178 // fewer than two results are generated), unused arguments will be set to the | |
| 179 // empty interval (it is possible that *lo will be empty and *hi non-empty). | |
| 180 // The method returns true iff the intersection of *this and i is non-empty. | |
| 181 bool Difference(const Interval& i, Interval* lo, Interval* hi) const; | |
| 182 | |
| 183 friend bool operator==(const Interval& a, const Interval& b) { | |
| 184 bool ae = a.Empty(); | |
| 185 bool be = b.Empty(); | |
| 186 if (ae && be) | |
| 187 return true; // All empties are equal. | |
| 188 if (ae != be) | |
| 189 return false; // Empty cannot equal nonempty. | |
| 190 return a.min() == b.min() && a.max() == b.max(); | |
| 191 } | |
| 192 | |
| 193 friend bool operator!=(const Interval& a, const Interval& b) { | |
| 194 return !(a == b); | |
| 195 } | |
| 196 | |
| 197 // Defines a comparator which can be used to induce an order on Intervals, so | |
| 198 // that, for example, they can be stored in an ordered container such as | |
| 199 // std::set. The ordering is arbitrary, but does provide the guarantee that, | |
| 200 // for non-empty intervals X and Y, if X contains Y, then X <= Y. | |
| 201 // TODO(kosak): The current implementation of this comparator has a problem | |
| 202 // because the ordering it induces is inconsistent with that of Equals(). In | |
| 203 // particular, this comparator does not properly consider all empty intervals | |
| 204 // equivalent. Bug b/9240050 has been created to track this. | |
| 205 friend bool operator<(const Interval& a, const Interval& b) { | |
| 206 return a.min() < b.min() || (a.min() == b.min() && a.max() > b.max()); | |
| 207 } | |
| 208 | |
| 209 friend std::ostream& operator<<(std::ostream& out, const Interval& i) { | |
| 210 return out << "[" << i.min() << ", " << i.max() << ")"; | |
| 211 } | |
| 212 | |
| 213 private: | |
| 214 T min_; // Inclusive lower bound. | |
| 215 T max_; // Exclusive upper bound. | |
| 216 }; | |
| 217 | |
| 218 //============================================================================== | |
| 219 // Implementation details: Clients can stop reading here. | |
| 220 | |
| 221 template <typename T> | |
| 222 bool Interval<T>::Intersects(const Interval& i, Interval* out) const { | |
| 223 if (!Intersects(i)) | |
| 224 return false; | |
| 225 if (out != nullptr) { | |
| 226 *out = Interval(std::max(min(), i.min()), std::min(max(), i.max())); | |
| 227 } | |
| 228 return true; | |
| 229 } | |
| 230 | |
| 231 template <typename T> | |
| 232 bool Interval<T>::IntersectWith(const Interval& i) { | |
| 233 if (Empty()) | |
| 234 return false; | |
| 235 bool modified = false; | |
| 236 if (i.min() > min()) { | |
| 237 SetMin(i.min()); | |
| 238 modified = true; | |
| 239 } | |
| 240 if (i.max() < max()) { | |
| 241 SetMax(i.max()); | |
| 242 modified = true; | |
| 243 } | |
| 244 return modified; | |
| 245 } | |
| 246 | |
| 247 template <typename T> | |
| 248 bool Interval<T>::SpanningUnion(const Interval& i) { | |
| 249 if (i.Empty()) | |
| 250 return false; | |
| 251 if (Empty()) { | |
| 252 *this = i; | |
| 253 return true; | |
| 254 } | |
| 255 bool modified = false; | |
| 256 if (i.min() < min()) { | |
| 257 SetMin(i.min()); | |
| 258 modified = true; | |
| 259 } | |
| 260 if (i.max() > max()) { | |
| 261 SetMax(i.max()); | |
| 262 modified = true; | |
| 263 } | |
| 264 return modified; | |
| 265 } | |
| 266 | |
| 267 template <typename T> | |
| 268 bool Interval<T>::Difference(const Interval& i, | |
| 269 std::vector<Interval*>* difference) const { | |
| 270 if (Empty()) { | |
| 271 // <empty> - <i> = <empty> | |
| 272 return false; | |
| 273 } | |
| 274 if (i.Empty()) { | |
| 275 // <this> - <empty> = <this> | |
| 276 difference->push_back(new Interval(*this)); | |
| 277 return false; | |
| 278 } | |
| 279 if (min() < i.max() && min() >= i.min() && max() > i.max()) { | |
| 280 // [------ this ------) | |
| 281 // [------ i ------) | |
| 282 // [-- result ---) | |
| 283 difference->push_back(new Interval(i.max(), max())); | |
| 284 return true; | |
| 285 } | |
| 286 if (max() > i.min() && max() <= i.max() && min() < i.min()) { | |
| 287 // [------ this ------) | |
| 288 // [------ i ------) | |
| 289 // [- result -) | |
| 290 difference->push_back(new Interval(min(), i.min())); | |
| 291 return true; | |
| 292 } | |
| 293 if (min() < i.min() && max() > i.max()) { | |
| 294 // [------- this --------) | |
| 295 // [---- i ----) | |
| 296 // [ R1 ) [ R2 ) | |
| 297 // There are two results: R1 and R2. | |
| 298 difference->push_back(new Interval(min(), i.min())); | |
| 299 difference->push_back(new Interval(i.max(), max())); | |
| 300 return true; | |
| 301 } | |
| 302 if (min() >= i.min() && max() <= i.max()) { | |
| 303 // [--- this ---) | |
| 304 // [------ i --------) | |
| 305 // Intersection is <this>, so difference yields the empty interval. | |
| 306 // Nothing is appended to *difference. | |
| 307 return true; | |
| 308 } | |
| 309 // No intersection. Append <this>. | |
| 310 difference->push_back(new Interval(*this)); | |
| 311 return false; | |
| 312 } | |
| 313 | |
| 314 template <typename T> | |
| 315 bool Interval<T>::Difference(const Interval& i, | |
| 316 Interval* lo, | |
| 317 Interval* hi) const { | |
| 318 // Initialize *lo and *hi to empty | |
| 319 *lo = {}; | |
| 320 *hi = {}; | |
| 321 if (Empty()) | |
| 322 return false; | |
| 323 if (i.Empty()) { | |
| 324 *lo = *this; | |
| 325 return false; | |
| 326 } | |
| 327 if (min() < i.max() && min() >= i.min() && max() > i.max()) { | |
| 328 // [------ this ------) | |
| 329 // [------ i ------) | |
| 330 // [-- result ---) | |
| 331 *hi = Interval(i.max(), max()); | |
| 332 return true; | |
| 333 } | |
| 334 if (max() > i.min() && max() <= i.max() && min() < i.min()) { | |
| 335 // [------ this ------) | |
| 336 // [------ i ------) | |
| 337 // [- result -) | |
| 338 *lo = Interval(min(), i.min()); | |
| 339 return true; | |
| 340 } | |
| 341 if (min() < i.min() && max() > i.max()) { | |
| 342 // [------- this --------) | |
| 343 // [---- i ----) | |
| 344 // [ R1 ) [ R2 ) | |
| 345 // There are two results: R1 and R2. | |
| 346 *lo = Interval(min(), i.min()); | |
| 347 *hi = Interval(i.max(), max()); | |
| 348 return true; | |
| 349 } | |
| 350 if (min() >= i.min() && max() <= i.max()) { | |
| 351 // [--- this ---) | |
| 352 // [------ i --------) | |
| 353 // Intersection is <this>, so difference yields the empty interval. | |
| 354 return true; | |
| 355 } | |
| 356 *lo = *this; // No intersection. | |
| 357 return false; | |
| 358 } | |
| 359 | |
| 360 } // namespace net | |
| 361 | |
| 362 #endif // NET_QUIC_INTERVAL_H_ | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2193073003:
Move shared files in net/quic/ into net/quic/core/ (Closed)
Base URL: https://chromium.googlesource.com/chromium/src.git@master