| 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 #include "net/quic/interval_set.h" | |
| 6 | |
| 7 #include <stdarg.h> | |
| 8 | |
| 9 #include <iostream> | |
| 10 #include <iterator> | |
| 11 #include <limits> | |
| 12 | |
| 13 #include "net/test/gtest_util.h" | |
| 14 #include "testing/gtest/include/gtest/gtest.h" | |
| 15 | |
| 16 using std::pair; | |
| 17 using std::string; | |
| 18 using std::vector; | |
| 19 | |
| 20 namespace net { | |
| 21 namespace test { | |
| 22 namespace { | |
| 23 | |
| 24 using ::testing::ElementsAreArray; | |
| 25 | |
| 26 class IntervalSetTest : public ::testing::Test { | |
| 27 protected: | |
| 28 void SetUp() override { | |
| 29 // Initialize two IntervalSets for union, intersection, and difference | |
| 30 // tests | |
| 31 is.Add(100, 200); | |
| 32 is.Add(300, 400); | |
| 33 is.Add(500, 600); | |
| 34 is.Add(700, 800); | |
| 35 is.Add(900, 1000); | |
| 36 is.Add(1100, 1200); | |
| 37 is.Add(1300, 1400); | |
| 38 is.Add(1500, 1600); | |
| 39 is.Add(1700, 1800); | |
| 40 is.Add(1900, 2000); | |
| 41 is.Add(2100, 2200); | |
| 42 | |
| 43 // Lots of different cases: | |
| 44 other.Add(50, 70); // disjoint, at the beginning | |
| 45 other.Add(2250, 2270); // disjoint, at the end | |
| 46 other.Add(650, 670); // disjoint, in the middle | |
| 47 other.Add(350, 360); // included | |
| 48 other.Add(370, 380); // also included (two at once) | |
| 49 other.Add(470, 530); // overlaps low end | |
| 50 other.Add(770, 830); // overlaps high end | |
| 51 other.Add(870, 900); // meets at low end | |
| 52 other.Add(1200, 1230); // meets at high end | |
| 53 other.Add(1270, 1830); // overlaps multiple ranges | |
| 54 } | |
| 55 | |
| 56 void TearDown() override { | |
| 57 is.Clear(); | |
| 58 EXPECT_TRUE(is.Empty()); | |
| 59 other.Clear(); | |
| 60 EXPECT_TRUE(other.Empty()); | |
| 61 } | |
| 62 IntervalSet<int> is; | |
| 63 IntervalSet<int> other; | |
| 64 }; | |
| 65 | |
| 66 TEST_F(IntervalSetTest, IsDisjoint) { | |
| 67 EXPECT_TRUE(is.IsDisjoint(Interval<int>(0, 99))); | |
| 68 EXPECT_TRUE(is.IsDisjoint(Interval<int>(0, 100))); | |
| 69 EXPECT_TRUE(is.IsDisjoint(Interval<int>(200, 200))); | |
| 70 EXPECT_TRUE(is.IsDisjoint(Interval<int>(200, 299))); | |
| 71 EXPECT_TRUE(is.IsDisjoint(Interval<int>(400, 407))); | |
| 72 EXPECT_TRUE(is.IsDisjoint(Interval<int>(405, 499))); | |
| 73 EXPECT_TRUE(is.IsDisjoint(Interval<int>(2300, 2300))); | |
| 74 EXPECT_TRUE( | |
| 75 is.IsDisjoint(Interval<int>(2300, std::numeric_limits<int>::max()))); | |
| 76 EXPECT_FALSE(is.IsDisjoint(Interval<int>(100, 100))); | |
| 77 EXPECT_FALSE(is.IsDisjoint(Interval<int>(100, 105))); | |
| 78 EXPECT_FALSE(is.IsDisjoint(Interval<int>(199, 300))); | |
| 79 EXPECT_FALSE(is.IsDisjoint(Interval<int>(250, 450))); | |
| 80 EXPECT_FALSE(is.IsDisjoint(Interval<int>(299, 400))); | |
| 81 EXPECT_FALSE(is.IsDisjoint(Interval<int>(250, 2000))); | |
| 82 EXPECT_FALSE( | |
| 83 is.IsDisjoint(Interval<int>(2199, std::numeric_limits<int>::max()))); | |
| 84 } | |
| 85 | |
| 86 // Base helper method for verifying the contents of an interval set. | |
| 87 // Returns true iff <is> contains <count> intervals whose successive | |
| 88 // endpoints match the sequence of args in <ap>: | |
| 89 static bool VA_Check(const IntervalSet<int>& is, size_t count, va_list ap) { | |
| 90 vector<Interval<int>> intervals; | |
| 91 is.Get(&intervals); | |
| 92 if (count != intervals.size()) { | |
| 93 LOG(ERROR) << "Expected " << count << " intervals, got " << intervals.size() | |
| 94 << ": " << is.ToString(); | |
| 95 return false; | |
| 96 } | |
| 97 if (count != is.Size()) { | |
| 98 LOG(ERROR) << "Expected " << count << " intervals, got Size " << is.Size() | |
| 99 << ": " << is.ToString(); | |
| 100 return false; | |
| 101 } | |
| 102 bool result = true; | |
| 103 for (size_t i = 0; i < count; i++) { | |
| 104 int min = va_arg(ap, int); | |
| 105 int max = va_arg(ap, int); | |
| 106 if (min != intervals[i].min() || max != intervals[i].max()) { | |
| 107 LOG(ERROR) << "Expected: [" << min << ", " << max << ") got " | |
| 108 << intervals[i] << " in " << is.ToString(); | |
| 109 result = false; | |
| 110 } | |
| 111 } | |
| 112 return result; | |
| 113 } | |
| 114 | |
| 115 static bool Check(const IntervalSet<int>& is, int count, ...) { | |
| 116 va_list ap; | |
| 117 va_start(ap, count); | |
| 118 const bool result = VA_Check(is, count, ap); | |
| 119 va_end(ap); | |
| 120 return result; | |
| 121 } | |
| 122 | |
| 123 // Some helper functions for testing Contains and Find, which are logically the | |
| 124 // same. | |
| 125 static void TestContainsAndFind(const IntervalSet<int>& is, int value) { | |
| 126 EXPECT_TRUE(is.Contains(value)) << "Set does not contain " << value; | |
| 127 auto it = is.Find(value); | |
| 128 EXPECT_NE(it, is.end()) << "No iterator to interval containing " << value; | |
| 129 EXPECT_TRUE(it->Contains(value)) << "Iterator does not contain " << value; | |
| 130 } | |
| 131 | |
| 132 static void TestContainsAndFind(const IntervalSet<int>& is, int min, int max) { | |
| 133 EXPECT_TRUE(is.Contains(min, max)) | |
| 134 << "Set does not contain interval with min " << min << "and max " << max; | |
| 135 auto it = is.Find(min, max); | |
| 136 EXPECT_NE(it, is.end()) << "No iterator to interval with min " << min | |
| 137 << "and max " << max; | |
| 138 EXPECT_TRUE(it->Contains(Interval<int>(min, max))) | |
| 139 << "Iterator does not contain interval with min " << min << "and max " | |
| 140 << max; | |
| 141 } | |
| 142 | |
| 143 static void TestNotContainsAndFind(const IntervalSet<int>& is, int value) { | |
| 144 EXPECT_FALSE(is.Contains(value)) << "Set contains " << value; | |
| 145 auto it = is.Find(value); | |
| 146 EXPECT_EQ(it, is.end()) << "There is iterator to interval containing " | |
| 147 << value; | |
| 148 } | |
| 149 | |
| 150 static void TestNotContainsAndFind(const IntervalSet<int>& is, | |
| 151 int min, | |
| 152 int max) { | |
| 153 EXPECT_FALSE(is.Contains(min, max)) << "Set contains interval with min " | |
| 154 << min << "and max " << max; | |
| 155 auto it = is.Find(min, max); | |
| 156 EXPECT_EQ(it, is.end()) << "There is iterator to interval with min " << min | |
| 157 << "and max " << max; | |
| 158 } | |
| 159 | |
| 160 TEST_F(IntervalSetTest, IntervalSetBasic) { | |
| 161 // Test Add, Get, Contains and Find | |
| 162 IntervalSet<int> iset; | |
| 163 EXPECT_TRUE(iset.Empty()); | |
| 164 EXPECT_EQ(0u, iset.Size()); | |
| 165 iset.Add(100, 200); | |
| 166 EXPECT_FALSE(iset.Empty()); | |
| 167 EXPECT_EQ(1u, iset.Size()); | |
| 168 iset.Add(100, 150); | |
| 169 iset.Add(150, 200); | |
| 170 iset.Add(130, 170); | |
| 171 iset.Add(90, 150); | |
| 172 iset.Add(170, 220); | |
| 173 iset.Add(300, 400); | |
| 174 iset.Add(250, 450); | |
| 175 EXPECT_FALSE(iset.Empty()); | |
| 176 EXPECT_EQ(2u, iset.Size()); | |
| 177 EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450)); | |
| 178 | |
| 179 // Test two intervals with a.max == b.min, that will just join up. | |
| 180 iset.Clear(); | |
| 181 iset.Add(100, 200); | |
| 182 iset.Add(200, 300); | |
| 183 EXPECT_FALSE(iset.Empty()); | |
| 184 EXPECT_EQ(1u, iset.Size()); | |
| 185 EXPECT_TRUE(Check(iset, 1, 100, 300)); | |
| 186 | |
| 187 // Test adding two sets together. | |
| 188 iset.Clear(); | |
| 189 IntervalSet<int> iset_add; | |
| 190 iset.Add(100, 200); | |
| 191 iset.Add(100, 150); | |
| 192 iset.Add(150, 200); | |
| 193 iset.Add(130, 170); | |
| 194 iset_add.Add(90, 150); | |
| 195 iset_add.Add(170, 220); | |
| 196 iset_add.Add(300, 400); | |
| 197 iset_add.Add(250, 450); | |
| 198 | |
| 199 iset.Add(iset_add); | |
| 200 EXPECT_FALSE(iset.Empty()); | |
| 201 EXPECT_EQ(2u, iset.Size()); | |
| 202 EXPECT_TRUE(Check(iset, 2, 90, 220, 250, 450)); | |
| 203 | |
| 204 // Test Get() (using an output iterator), begin()/end(), and rbegin()/rend() | |
| 205 // to iterate over intervals. | |
| 206 { | |
| 207 vector<Interval<int>> expected; | |
| 208 iset.Get(&expected); | |
| 209 | |
| 210 vector<Interval<int>> actual1; | |
| 211 iset.Get(back_inserter(actual1)); | |
| 212 ASSERT_EQ(expected.size(), actual1.size()); | |
| 213 | |
| 214 vector<Interval<int>> actual2; | |
| 215 std::copy(iset.begin(), iset.end(), back_inserter(actual2)); | |
| 216 ASSERT_EQ(expected.size(), actual2.size()); | |
| 217 | |
| 218 for (size_t i = 0; i < expected.size(); i++) { | |
| 219 EXPECT_EQ(expected[i].min(), actual1[i].min()); | |
| 220 EXPECT_EQ(expected[i].max(), actual1[i].max()); | |
| 221 | |
| 222 EXPECT_EQ(expected[i].min(), actual2[i].min()); | |
| 223 EXPECT_EQ(expected[i].max(), actual2[i].max()); | |
| 224 } | |
| 225 | |
| 226 // Ensure that the rbegin()/rend() iterators correctly yield the intervals | |
| 227 // in reverse order. | |
| 228 EXPECT_THAT(vector<Interval<int>>(iset.rbegin(), iset.rend()), | |
| 229 ElementsAreArray(expected.rbegin(), expected.rend())); | |
| 230 } | |
| 231 | |
| 232 TestNotContainsAndFind(iset, 89); | |
| 233 TestContainsAndFind(iset, 90); | |
| 234 TestContainsAndFind(iset, 120); | |
| 235 TestContainsAndFind(iset, 219); | |
| 236 TestNotContainsAndFind(iset, 220); | |
| 237 TestNotContainsAndFind(iset, 235); | |
| 238 TestNotContainsAndFind(iset, 249); | |
| 239 TestContainsAndFind(iset, 250); | |
| 240 TestContainsAndFind(iset, 300); | |
| 241 TestContainsAndFind(iset, 449); | |
| 242 TestNotContainsAndFind(iset, 450); | |
| 243 TestNotContainsAndFind(iset, 451); | |
| 244 | |
| 245 TestNotContainsAndFind(iset, 50, 60); | |
| 246 TestNotContainsAndFind(iset, 50, 90); | |
| 247 TestNotContainsAndFind(iset, 50, 200); | |
| 248 TestNotContainsAndFind(iset, 90, 90); | |
| 249 TestContainsAndFind(iset, 90, 200); | |
| 250 TestContainsAndFind(iset, 100, 200); | |
| 251 TestContainsAndFind(iset, 100, 220); | |
| 252 TestNotContainsAndFind(iset, 100, 221); | |
| 253 TestNotContainsAndFind(iset, 220, 220); | |
| 254 TestNotContainsAndFind(iset, 240, 300); | |
| 255 TestContainsAndFind(iset, 250, 300); | |
| 256 TestContainsAndFind(iset, 260, 300); | |
| 257 TestContainsAndFind(iset, 300, 450); | |
| 258 TestNotContainsAndFind(iset, 300, 451); | |
| 259 | |
| 260 IntervalSet<int> iset_contains; | |
| 261 iset_contains.Add(50, 90); | |
| 262 EXPECT_FALSE(iset.Contains(iset_contains)); | |
| 263 iset_contains.Clear(); | |
| 264 | |
| 265 iset_contains.Add(90, 200); | |
| 266 EXPECT_TRUE(iset.Contains(iset_contains)); | |
| 267 iset_contains.Add(100, 200); | |
| 268 EXPECT_TRUE(iset.Contains(iset_contains)); | |
| 269 iset_contains.Add(100, 220); | |
| 270 EXPECT_TRUE(iset.Contains(iset_contains)); | |
| 271 iset_contains.Add(250, 300); | |
| 272 EXPECT_TRUE(iset.Contains(iset_contains)); | |
| 273 iset_contains.Add(300, 450); | |
| 274 EXPECT_TRUE(iset.Contains(iset_contains)); | |
| 275 iset_contains.Add(300, 451); | |
| 276 EXPECT_FALSE(iset.Contains(iset_contains)); | |
| 277 EXPECT_FALSE(iset.Contains(Interval<int>())); | |
| 278 EXPECT_FALSE(iset.Contains(IntervalSet<int>())); | |
| 279 } | |
| 280 | |
| 281 TEST_F(IntervalSetTest, IntervalSetContainsEmpty) { | |
| 282 const IntervalSet<int> empty; | |
| 283 const IntervalSet<int> other_empty; | |
| 284 EXPECT_FALSE(empty.Contains(empty)); | |
| 285 EXPECT_FALSE(empty.Contains(other_empty)); | |
| 286 // TODO(rtenneti): Implement after suupport for std::initializer_list. | |
| 287 #if 0 | |
| 288 const IntervalSet<int> non_empty({{10, 20}, {40, 50}}); | |
| 289 EXPECT_FALSE(empty.Contains(non_empty)); | |
| 290 EXPECT_FALSE(non_empty.Contains(empty)); | |
| 291 #endif | |
| 292 } | |
| 293 | |
| 294 TEST_F(IntervalSetTest, Equality) { | |
| 295 IntervalSet<int> is_copy = is; | |
| 296 EXPECT_TRUE(is.Equals(is)); | |
| 297 EXPECT_EQ(is, is); | |
| 298 EXPECT_TRUE(is.Equals(is_copy)); | |
| 299 EXPECT_EQ(is, is_copy); | |
| 300 EXPECT_FALSE(is.Equals(other)); | |
| 301 EXPECT_NE(is, other); | |
| 302 EXPECT_FALSE(is.Equals(IntervalSet<int>())); | |
| 303 EXPECT_NE(is, IntervalSet<int>()); | |
| 304 EXPECT_TRUE(IntervalSet<int>().Equals(IntervalSet<int>())); | |
| 305 EXPECT_EQ(IntervalSet<int>(), IntervalSet<int>()); | |
| 306 } | |
| 307 | |
| 308 TEST_F(IntervalSetTest, SpanningInterval) { | |
| 309 // Spanning interval of an empty set is empty: | |
| 310 { | |
| 311 IntervalSet<int> iset; | |
| 312 const Interval<int>& ival = iset.SpanningInterval(); | |
| 313 EXPECT_TRUE(ival.Empty()); | |
| 314 } | |
| 315 | |
| 316 // Spanning interval of a set with one interval is that interval: | |
| 317 { | |
| 318 IntervalSet<int> iset; | |
| 319 iset.Add(100, 200); | |
| 320 const Interval<int>& ival = iset.SpanningInterval(); | |
| 321 EXPECT_EQ(100, ival.min()); | |
| 322 EXPECT_EQ(200, ival.max()); | |
| 323 } | |
| 324 | |
| 325 // Spanning interval of a set with multiple elements is determined | |
| 326 // by the endpoints of the first and last element: | |
| 327 { | |
| 328 const Interval<int>& ival = is.SpanningInterval(); | |
| 329 EXPECT_EQ(100, ival.min()); | |
| 330 EXPECT_EQ(2200, ival.max()); | |
| 331 } | |
| 332 { | |
| 333 const Interval<int>& ival = other.SpanningInterval(); | |
| 334 EXPECT_EQ(50, ival.min()); | |
| 335 EXPECT_EQ(2270, ival.max()); | |
| 336 } | |
| 337 } | |
| 338 | |
| 339 TEST_F(IntervalSetTest, IntervalSetUnion) { | |
| 340 is.Union(other); | |
| 341 EXPECT_TRUE(Check(is, 12, 50, 70, 100, 200, 300, 400, 470, 600, 650, 670, 700, | |
| 342 830, 870, 1000, 1100, 1230, 1270, 1830, 1900, 2000, 2100, | |
| 343 2200, 2250, 2270)); | |
| 344 } | |
| 345 | |
| 346 TEST_F(IntervalSetTest, IntervalSetIntersection) { | |
| 347 EXPECT_TRUE(is.Intersects(other)); | |
| 348 EXPECT_TRUE(other.Intersects(is)); | |
| 349 is.Intersection(other); | |
| 350 EXPECT_TRUE(Check(is, 7, 350, 360, 370, 380, 500, 530, 770, 800, 1300, 1400, | |
| 351 1500, 1600, 1700, 1800)); | |
| 352 EXPECT_TRUE(is.Intersects(other)); | |
| 353 EXPECT_TRUE(other.Intersects(is)); | |
| 354 } | |
| 355 | |
| 356 TEST_F(IntervalSetTest, IntervalSetIntersectionBothEmpty) { | |
| 357 IntervalSet<string> mine, theirs; | |
| 358 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 359 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 360 mine.Intersection(theirs); | |
| 361 EXPECT_TRUE(mine.Empty()); | |
| 362 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 363 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 364 } | |
| 365 | |
| 366 TEST_F(IntervalSetTest, IntervalSetIntersectionEmptyMine) { | |
| 367 IntervalSet<string> mine; | |
| 368 IntervalSet<string> theirs("a", "b"); | |
| 369 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 370 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 371 mine.Intersection(theirs); | |
| 372 EXPECT_TRUE(mine.Empty()); | |
| 373 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 374 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 375 } | |
| 376 | |
| 377 TEST_F(IntervalSetTest, IntervalSetIntersectionEmptyTheirs) { | |
| 378 IntervalSet<string> mine("a", "b"); | |
| 379 IntervalSet<string> theirs; | |
| 380 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 381 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 382 mine.Intersection(theirs); | |
| 383 EXPECT_TRUE(mine.Empty()); | |
| 384 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 385 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 386 } | |
| 387 | |
| 388 TEST_F(IntervalSetTest, IntervalSetIntersectionTheirsBeforeMine) { | |
| 389 IntervalSet<string> mine("y", "z"); | |
| 390 IntervalSet<string> theirs; | |
| 391 theirs.Add("a", "b"); | |
| 392 theirs.Add("c", "d"); | |
| 393 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 394 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 395 mine.Intersection(theirs); | |
| 396 EXPECT_TRUE(mine.Empty()); | |
| 397 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 398 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 399 } | |
| 400 | |
| 401 TEST_F(IntervalSetTest, IntervalSetIntersectionMineBeforeTheirs) { | |
| 402 IntervalSet<string> mine; | |
| 403 mine.Add("a", "b"); | |
| 404 mine.Add("c", "d"); | |
| 405 IntervalSet<string> theirs("y", "z"); | |
| 406 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 407 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 408 mine.Intersection(theirs); | |
| 409 EXPECT_TRUE(mine.Empty()); | |
| 410 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 411 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 412 } | |
| 413 | |
| 414 // TODO(rtenneti): Implement after suupport for std::initializer_list. | |
| 415 #if 0 | |
| 416 TEST_F(IntervalSetTest, | |
| 417 IntervalSetIntersectionTheirsBeforeMineInt64Singletons) { | |
| 418 IntervalSet<int64_t> mine({{10, 15}}); | |
| 419 IntervalSet<int64_t> theirs({{-20, -5}}); | |
| 420 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 421 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 422 mine.Intersection(theirs); | |
| 423 EXPECT_TRUE(mine.Empty()); | |
| 424 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 425 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 426 } | |
| 427 | |
| 428 TEST_F(IntervalSetTest, IntervalSetIntersectionMineBeforeTheirsIntSingletons) { | |
| 429 IntervalSet<int> mine({{10, 15}}); | |
| 430 IntervalSet<int> theirs({{90, 95}}); | |
| 431 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 432 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 433 mine.Intersection(theirs); | |
| 434 EXPECT_TRUE(mine.Empty()); | |
| 435 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 436 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 437 } | |
| 438 | |
| 439 TEST_F(IntervalSetTest, IntervalSetIntersectionTheirsBetweenMine) { | |
| 440 IntervalSet<int64_t> mine({{0, 5}, {40, 50}}); | |
| 441 IntervalSet<int64_t> theirs({{10, 15}}); | |
| 442 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 443 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 444 mine.Intersection(theirs); | |
| 445 EXPECT_TRUE(mine.Empty()); | |
| 446 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 447 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 448 } | |
| 449 | |
| 450 TEST_F(IntervalSetTest, IntervalSetIntersectionMineBetweenTheirs) { | |
| 451 IntervalSet<int> mine({{20, 25}}); | |
| 452 IntervalSet<int> theirs({{10, 15}, {30, 32}}); | |
| 453 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 454 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 455 mine.Intersection(theirs); | |
| 456 EXPECT_TRUE(mine.Empty()); | |
| 457 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 458 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 459 } | |
| 460 #endif // 0 | |
| 461 | |
| 462 TEST_F(IntervalSetTest, IntervalSetIntersectionAlternatingIntervals) { | |
| 463 IntervalSet<int> mine, theirs; | |
| 464 mine.Add(10, 20); | |
| 465 mine.Add(40, 50); | |
| 466 mine.Add(60, 70); | |
| 467 theirs.Add(25, 39); | |
| 468 theirs.Add(55, 59); | |
| 469 theirs.Add(75, 79); | |
| 470 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 471 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 472 mine.Intersection(theirs); | |
| 473 EXPECT_TRUE(mine.Empty()); | |
| 474 EXPECT_FALSE(mine.Intersects(theirs)); | |
| 475 EXPECT_FALSE(theirs.Intersects(mine)); | |
| 476 } | |
| 477 | |
| 478 // TODO(rtenneti): Implement after suupport for std::initializer_list. | |
| 479 #if 0 | |
| 480 TEST_F(IntervalSetTest, | |
| 481 IntervalSetIntersectionAdjacentAlternatingNonIntersectingIntervals) { | |
| 482 // Make sure that intersection with adjacent interval set is empty. | |
| 483 const IntervalSet<int> x1({{0, 10}}); | |
| 484 const IntervalSet<int> y1({{-50, 0}, {10, 95}}); | |
| 485 | |
| 486 IntervalSet<int> result1 = x1; | |
| 487 result1.Intersection(y1); | |
| 488 EXPECT_TRUE(result1.Empty()) << result1; | |
| 489 | |
| 490 const IntervalSet<int16_t> x2({{0, 10}, {20, 30}, {40, 90}}); | |
| 491 const IntervalSet<int16_t> y2( | |
| 492 {{-50, -40}, {-2, 0}, {10, 20}, {32, 40}, {90, 95}}); | |
| 493 | |
| 494 IntervalSet<int16_t> result2 = x2; | |
| 495 result2.Intersection(y2); | |
| 496 EXPECT_TRUE(result2.Empty()) << result2; | |
| 497 | |
| 498 const IntervalSet<int64_t> x3({{-1, 5}, {5, 10}}); | |
| 499 const IntervalSet<int64_t> y3({{-10, -1}, {10, 95}}); | |
| 500 | |
| 501 IntervalSet<int64_t> result3 = x3; | |
| 502 result3.Intersection(y3); | |
| 503 EXPECT_TRUE(result3.Empty()) << result3; | |
| 504 } | |
| 505 | |
| 506 TEST_F(IntervalSetTest, | |
| 507 IntervalSetIntersectionAlternatingIntersectingIntervals) { | |
| 508 const IntervalSet<int> x1({{0, 10}}); | |
| 509 const IntervalSet<int> y1({{-50, 1}, {9, 95}}); | |
| 510 const IntervalSet<int> expected_result1({{0, 1}, {9, 10}}); | |
| 511 | |
| 512 IntervalSet<int> result1 = x1; | |
| 513 result1.Intersection(y1); | |
| 514 EXPECT_EQ(result1, expected_result1); | |
| 515 | |
| 516 const IntervalSet<int16_t> x2({{0, 10}, {20, 30}, {40, 90}}); | |
| 517 const IntervalSet<int16_t> y2( | |
| 518 {{-50, -40}, {-2, 2}, {9, 21}, {32, 41}, {85, 95}}); | |
| 519 const IntervalSet<int16_t> expected_result2( | |
| 520 {{0, 2}, {9, 10}, {20, 21}, {40, 41}, {85, 90}}); | |
| 521 | |
| 522 IntervalSet<int16_t> result2 = x2; | |
| 523 result2.Intersection(y2); | |
| 524 EXPECT_EQ(result2, expected_result2); | |
| 525 | |
| 526 const IntervalSet<int64_t> x3({{-1, 5}, {5, 10}}); | |
| 527 const IntervalSet<int64_t> y3({{-10, 3}, {4, 95}}); | |
| 528 const IntervalSet<int64_t> expected_result3({{-1, 3}, {4, 10}}); | |
| 529 | |
| 530 IntervalSet<int64_t> result3 = x3; | |
| 531 result3.Intersection(y3); | |
| 532 EXPECT_EQ(result3, expected_result3); | |
| 533 } | |
| 534 | |
| 535 #endif // 0 | |
| 536 | |
| 537 TEST_F(IntervalSetTest, IntervalSetIntersectionIdentical) { | |
| 538 IntervalSet<int> copy(is); | |
| 539 EXPECT_TRUE(copy.Intersects(is)); | |
| 540 EXPECT_TRUE(is.Intersects(copy)); | |
| 541 is.Intersection(copy); | |
| 542 EXPECT_EQ(copy, is); | |
| 543 } | |
| 544 | |
| 545 TEST_F(IntervalSetTest, IntervalSetIntersectionSuperset) { | |
| 546 IntervalSet<int> mine(-1, 10000); | |
| 547 EXPECT_TRUE(mine.Intersects(is)); | |
| 548 EXPECT_TRUE(is.Intersects(mine)); | |
| 549 mine.Intersection(is); | |
| 550 EXPECT_EQ(is, mine); | |
| 551 } | |
| 552 | |
| 553 TEST_F(IntervalSetTest, IntervalSetIntersectionSubset) { | |
| 554 IntervalSet<int> copy(is); | |
| 555 IntervalSet<int> theirs(-1, 10000); | |
| 556 EXPECT_TRUE(copy.Intersects(theirs)); | |
| 557 EXPECT_TRUE(theirs.Intersects(copy)); | |
| 558 is.Intersection(theirs); | |
| 559 EXPECT_EQ(copy, is); | |
| 560 } | |
| 561 | |
| 562 TEST_F(IntervalSetTest, IntervalSetIntersectionLargeSet) { | |
| 563 IntervalSet<int> mine, theirs; | |
| 564 // mine: [0, 9), [10, 19), ..., [990, 999) | |
| 565 for (int i = 0; i < 1000; i += 10) { | |
| 566 mine.Add(i, i + 9); | |
| 567 } | |
| 568 | |
| 569 theirs.Add(500, 520); | |
| 570 theirs.Add(535, 545); | |
| 571 theirs.Add(801, 809); | |
| 572 EXPECT_TRUE(mine.Intersects(theirs)); | |
| 573 EXPECT_TRUE(theirs.Intersects(mine)); | |
| 574 mine.Intersection(theirs); | |
| 575 EXPECT_TRUE(Check(mine, 5, 500, 509, 510, 519, 535, 539, 540, 545, 801, 809)); | |
| 576 EXPECT_TRUE(mine.Intersects(theirs)); | |
| 577 EXPECT_TRUE(theirs.Intersects(mine)); | |
| 578 } | |
| 579 | |
| 580 TEST_F(IntervalSetTest, IntervalSetDifference) { | |
| 581 is.Difference(other); | |
| 582 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600, | |
| 583 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200)); | |
| 584 IntervalSet<int> copy = is; | |
| 585 is.Difference(copy); | |
| 586 EXPECT_TRUE(is.Empty()); | |
| 587 } | |
| 588 | |
| 589 TEST_F(IntervalSetTest, IntervalSetDifferenceSingleBounds) { | |
| 590 vector<Interval<int>> ivals; | |
| 591 other.Get(&ivals); | |
| 592 for (size_t i = 0; i < ivals.size(); ++i) { | |
| 593 is.Difference(ivals[i].min(), ivals[i].max()); | |
| 594 } | |
| 595 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600, | |
| 596 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200)); | |
| 597 } | |
| 598 | |
| 599 TEST_F(IntervalSetTest, IntervalSetDifferenceSingleInterval) { | |
| 600 vector<Interval<int>> ivals; | |
| 601 other.Get(&ivals); | |
| 602 for (size_t i = 0; i < ivals.size(); ++i) { | |
| 603 is.Difference(ivals[i]); | |
| 604 } | |
| 605 EXPECT_TRUE(Check(is, 10, 100, 200, 300, 350, 360, 370, 380, 400, 530, 600, | |
| 606 700, 770, 900, 1000, 1100, 1200, 1900, 2000, 2100, 2200)); | |
| 607 } | |
| 608 | |
| 609 TEST_F(IntervalSetTest, IntervalSetDifferenceAlternatingIntervals) { | |
| 610 IntervalSet<int> mine, theirs; | |
| 611 mine.Add(10, 20); | |
| 612 mine.Add(40, 50); | |
| 613 mine.Add(60, 70); | |
| 614 theirs.Add(25, 39); | |
| 615 theirs.Add(55, 59); | |
| 616 theirs.Add(75, 79); | |
| 617 | |
| 618 mine.Difference(theirs); | |
| 619 EXPECT_TRUE(Check(mine, 3, 10, 20, 40, 50, 60, 70)); | |
| 620 } | |
| 621 | |
| 622 TEST_F(IntervalSetTest, IntervalSetDifferenceEmptyMine) { | |
| 623 IntervalSet<string> mine, theirs; | |
| 624 theirs.Add("a", "b"); | |
| 625 | |
| 626 mine.Difference(theirs); | |
| 627 EXPECT_TRUE(mine.Empty()); | |
| 628 } | |
| 629 | |
| 630 TEST_F(IntervalSetTest, IntervalSetDifferenceEmptyTheirs) { | |
| 631 IntervalSet<string> mine, theirs; | |
| 632 mine.Add("a", "b"); | |
| 633 | |
| 634 mine.Difference(theirs); | |
| 635 EXPECT_EQ(1u, mine.Size()); | |
| 636 EXPECT_EQ("a", mine.begin()->min()); | |
| 637 EXPECT_EQ("b", mine.begin()->max()); | |
| 638 } | |
| 639 | |
| 640 TEST_F(IntervalSetTest, IntervalSetDifferenceTheirsBeforeMine) { | |
| 641 IntervalSet<string> mine, theirs; | |
| 642 mine.Add("y", "z"); | |
| 643 theirs.Add("a", "b"); | |
| 644 | |
| 645 mine.Difference(theirs); | |
| 646 EXPECT_EQ(1u, mine.Size()); | |
| 647 EXPECT_EQ("y", mine.begin()->min()); | |
| 648 EXPECT_EQ("z", mine.begin()->max()); | |
| 649 } | |
| 650 | |
| 651 TEST_F(IntervalSetTest, IntervalSetDifferenceMineBeforeTheirs) { | |
| 652 IntervalSet<string> mine, theirs; | |
| 653 mine.Add("a", "b"); | |
| 654 theirs.Add("y", "z"); | |
| 655 | |
| 656 mine.Difference(theirs); | |
| 657 EXPECT_EQ(1u, mine.Size()); | |
| 658 EXPECT_EQ("a", mine.begin()->min()); | |
| 659 EXPECT_EQ("b", mine.begin()->max()); | |
| 660 } | |
| 661 | |
| 662 TEST_F(IntervalSetTest, IntervalSetDifferenceIdentical) { | |
| 663 IntervalSet<string> mine; | |
| 664 mine.Add("a", "b"); | |
| 665 mine.Add("c", "d"); | |
| 666 IntervalSet<string> theirs(mine); | |
| 667 | |
| 668 mine.Difference(theirs); | |
| 669 EXPECT_TRUE(mine.Empty()); | |
| 670 } | |
| 671 | |
| 672 TEST_F(IntervalSetTest, EmptyComplement) { | |
| 673 // The complement of an empty set is the input interval: | |
| 674 IntervalSet<int> iset; | |
| 675 iset.Complement(100, 200); | |
| 676 EXPECT_TRUE(Check(iset, 1, 100, 200)); | |
| 677 } | |
| 678 | |
| 679 TEST(IntervalSetMultipleCompactionTest, OuterCovering) { | |
| 680 IntervalSet<int> iset; | |
| 681 // First add a bunch of disjoint ranges | |
| 682 iset.Add(100, 150); | |
| 683 iset.Add(200, 250); | |
| 684 iset.Add(300, 350); | |
| 685 iset.Add(400, 450); | |
| 686 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450)); | |
| 687 // Now add a big range that covers all of these ranges | |
| 688 iset.Add(0, 500); | |
| 689 EXPECT_TRUE(Check(iset, 1, 0, 500)); | |
| 690 } | |
| 691 | |
| 692 TEST(IntervalSetMultipleCompactionTest, InnerCovering) { | |
| 693 IntervalSet<int> iset; | |
| 694 // First add a bunch of disjoint ranges | |
| 695 iset.Add(100, 150); | |
| 696 iset.Add(200, 250); | |
| 697 iset.Add(300, 350); | |
| 698 iset.Add(400, 450); | |
| 699 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450)); | |
| 700 // Now add a big range that partially covers the left and right most ranges. | |
| 701 iset.Add(125, 425); | |
| 702 EXPECT_TRUE(Check(iset, 1, 100, 450)); | |
| 703 } | |
| 704 | |
| 705 TEST(IntervalSetMultipleCompactionTest, LeftCovering) { | |
| 706 IntervalSet<int> iset; | |
| 707 // First add a bunch of disjoint ranges | |
| 708 iset.Add(100, 150); | |
| 709 iset.Add(200, 250); | |
| 710 iset.Add(300, 350); | |
| 711 iset.Add(400, 450); | |
| 712 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450)); | |
| 713 // Now add a big range that partially covers the left most range. | |
| 714 iset.Add(125, 500); | |
| 715 EXPECT_TRUE(Check(iset, 1, 100, 500)); | |
| 716 } | |
| 717 | |
| 718 TEST(IntervalSetMultipleCompactionTest, RightCovering) { | |
| 719 IntervalSet<int> iset; | |
| 720 // First add a bunch of disjoint ranges | |
| 721 iset.Add(100, 150); | |
| 722 iset.Add(200, 250); | |
| 723 iset.Add(300, 350); | |
| 724 iset.Add(400, 450); | |
| 725 EXPECT_TRUE(Check(iset, 4, 100, 150, 200, 250, 300, 350, 400, 450)); | |
| 726 // Now add a big range that partially covers the right most range. | |
| 727 iset.Add(0, 425); | |
| 728 EXPECT_TRUE(Check(iset, 1, 0, 450)); | |
| 729 } | |
| 730 | |
| 731 // Helper method for testing and verifying the results of a one-interval | |
| 732 // completement case. | |
| 733 static bool CheckOneComplement(int add_min, | |
| 734 int add_max, | |
| 735 int comp_min, | |
| 736 int comp_max, | |
| 737 int count, | |
| 738 ...) { | |
| 739 IntervalSet<int> iset; | |
| 740 iset.Add(add_min, add_max); | |
| 741 iset.Complement(comp_min, comp_max); | |
| 742 bool result = true; | |
| 743 va_list ap; | |
| 744 va_start(ap, count); | |
| 745 if (!VA_Check(iset, count, ap)) { | |
| 746 result = false; | |
| 747 } | |
| 748 va_end(ap); | |
| 749 return result; | |
| 750 } | |
| 751 | |
| 752 TEST_F(IntervalSetTest, SingleIntervalComplement) { | |
| 753 // Verify the complement of a set with one interval (i): | |
| 754 // |----- i -----| | |
| 755 // |----- args -----| | |
| 756 EXPECT_TRUE(CheckOneComplement(0, 10, 50, 150, 1, 50, 150)); | |
| 757 | |
| 758 // |----- i -----| | |
| 759 // |----- args -----| | |
| 760 EXPECT_TRUE(CheckOneComplement(50, 150, 0, 100, 1, 0, 50)); | |
| 761 | |
| 762 // |----- i -----| | |
| 763 // |----- args -----| | |
| 764 EXPECT_TRUE(CheckOneComplement(50, 150, 50, 150, 0)); | |
| 765 | |
| 766 // |---------- i ----------| | |
| 767 // |----- args -----| | |
| 768 EXPECT_TRUE(CheckOneComplement(50, 500, 100, 300, 0)); | |
| 769 | |
| 770 // |----- i -----| | |
| 771 // |---------- args ----------| | |
| 772 EXPECT_TRUE(CheckOneComplement(50, 500, 0, 800, 2, 0, 50, 500, 800)); | |
| 773 | |
| 774 // |----- i -----| | |
| 775 // |----- args -----| | |
| 776 EXPECT_TRUE(CheckOneComplement(50, 150, 100, 300, 1, 150, 300)); | |
| 777 | |
| 778 // |----- i -----| | |
| 779 // |----- args -----| | |
| 780 EXPECT_TRUE(CheckOneComplement(50, 150, 200, 300, 1, 200, 300)); | |
| 781 } | |
| 782 | |
| 783 // Helper method that copies <iset> and takes its complement, | |
| 784 // returning false if Check succeeds. | |
| 785 static bool CheckComplement(const IntervalSet<int>& iset, | |
| 786 int comp_min, | |
| 787 int comp_max, | |
| 788 int count, | |
| 789 ...) { | |
| 790 IntervalSet<int> iset_copy = iset; | |
| 791 iset_copy.Complement(comp_min, comp_max); | |
| 792 bool result = true; | |
| 793 va_list ap; | |
| 794 va_start(ap, count); | |
| 795 if (!VA_Check(iset_copy, count, ap)) { | |
| 796 result = false; | |
| 797 } | |
| 798 va_end(ap); | |
| 799 return result; | |
| 800 } | |
| 801 | |
| 802 TEST_F(IntervalSetTest, MultiIntervalComplement) { | |
| 803 // Initialize a small test set: | |
| 804 IntervalSet<int> iset; | |
| 805 iset.Add(100, 200); | |
| 806 iset.Add(300, 400); | |
| 807 iset.Add(500, 600); | |
| 808 | |
| 809 // |----- i -----| | |
| 810 // |----- comp -----| | |
| 811 EXPECT_TRUE(CheckComplement(iset, 0, 50, 1, 0, 50)); | |
| 812 | |
| 813 // |----- i -----| | |
| 814 // |----- comp -----| | |
| 815 EXPECT_TRUE(CheckComplement(iset, 0, 200, 1, 0, 100)); | |
| 816 EXPECT_TRUE(CheckComplement(iset, 0, 220, 2, 0, 100, 200, 220)); | |
| 817 | |
| 818 // |----- i -----| | |
| 819 // |----- comp -----| | |
| 820 EXPECT_TRUE(CheckComplement(iset, 100, 600, 2, 200, 300, 400, 500)); | |
| 821 | |
| 822 // |---------- i ----------| | |
| 823 // |----- comp -----| | |
| 824 EXPECT_TRUE(CheckComplement(iset, 300, 400, 0)); | |
| 825 EXPECT_TRUE(CheckComplement(iset, 250, 400, 1, 250, 300)); | |
| 826 EXPECT_TRUE(CheckComplement(iset, 300, 450, 1, 400, 450)); | |
| 827 EXPECT_TRUE(CheckComplement(iset, 250, 450, 2, 250, 300, 400, 450)); | |
| 828 | |
| 829 // |----- i -----| | |
| 830 // |---------- comp ----------| | |
| 831 EXPECT_TRUE( | |
| 832 CheckComplement(iset, 0, 700, 4, 0, 100, 200, 300, 400, 500, 600, 700)); | |
| 833 | |
| 834 // |----- i -----| | |
| 835 // |----- comp -----| | |
| 836 EXPECT_TRUE(CheckComplement(iset, 400, 700, 2, 400, 500, 600, 700)); | |
| 837 EXPECT_TRUE(CheckComplement(iset, 350, 700, 2, 400, 500, 600, 700)); | |
| 838 | |
| 839 // |----- i -----| | |
| 840 // |----- comp -----| | |
| 841 EXPECT_TRUE(CheckComplement(iset, 700, 800, 1, 700, 800)); | |
| 842 } | |
| 843 | |
| 844 // Verifies ToString, operator<< don't assert. | |
| 845 // TODO(rtenneti): Implement ToString() method of IntervalSet. | |
| 846 TEST_F(IntervalSetTest, DISABLED_ToString) { | |
| 847 IntervalSet<int> iset; | |
| 848 iset.Add(300, 400); | |
| 849 iset.Add(100, 200); | |
| 850 iset.Add(500, 600); | |
| 851 EXPECT_TRUE(!iset.ToString().empty()); | |
| 852 VLOG(2) << iset.ToString(); | |
| 853 // Order and format of ToString() output is guaranteed. | |
| 854 EXPECT_EQ("[100, 200) [300, 400) [500, 600)", iset.ToString()); | |
| 855 EXPECT_EQ("[1, 2)", IntervalSet<int>(1, 2).ToString()); | |
| 856 EXPECT_EQ("", IntervalSet<int>().ToString()); | |
| 857 } | |
| 858 | |
| 859 TEST_F(IntervalSetTest, ConstructionDiscardsEmptyInterval) { | |
| 860 EXPECT_TRUE(IntervalSet<int>(Interval<int>(2, 2)).Empty()); | |
| 861 EXPECT_TRUE(IntervalSet<int>(2, 2).Empty()); | |
| 862 EXPECT_FALSE(IntervalSet<int>(Interval<int>(2, 3)).Empty()); | |
| 863 EXPECT_FALSE(IntervalSet<int>(2, 3).Empty()); | |
| 864 } | |
| 865 | |
| 866 TEST_F(IntervalSetTest, Swap) { | |
| 867 IntervalSet<int> a, b; | |
| 868 a.Add(300, 400); | |
| 869 b.Add(100, 200); | |
| 870 b.Add(500, 600); | |
| 871 a.Swap(&b); | |
| 872 EXPECT_TRUE(Check(a, 2, 100, 200, 500, 600)); | |
| 873 EXPECT_TRUE(Check(b, 1, 300, 400)); | |
| 874 swap(a, b); | |
| 875 EXPECT_TRUE(Check(a, 1, 300, 400)); | |
| 876 EXPECT_TRUE(Check(b, 2, 100, 200, 500, 600)); | |
| 877 } | |
| 878 | |
| 879 // TODO(rtenneti): Enabled these tests. | |
| 880 #if 0 | |
| 881 static void BM_Difference(int iters) { | |
| 882 // StopBenchmarkTiming(); | |
| 883 IntervalSet<int> difference_set; | |
| 884 int start = 10; | |
| 885 for (int i = 0; i < 1000000; ++i) { | |
| 886 difference_set.Add(start, start+5); | |
| 887 start += 7; | |
| 888 } | |
| 889 | |
| 890 // Create an interval somewhere in the middle of the difference set. | |
| 891 // StartBenchmarkTiming(); | |
| 892 for (int i = 0; i < iters; ++i) { | |
| 893 IntervalSet<int> initial(1000000, 1000020); | |
| 894 initial.Difference(difference_set); | |
| 895 } | |
| 896 } | |
| 897 | |
| 898 BENCHMARK(BM_Difference); | |
| 899 | |
| 900 static void BM_IntersectionSmallAndLarge(int iters, int size) { | |
| 901 // Intersects constant size 'mine' with large 'theirs'. | |
| 902 StopBenchmarkTiming(); | |
| 903 IntervalSet<int> theirs; | |
| 904 for (int i = 0; i < size; ++i) { | |
| 905 theirs.Add(2 * i, 2 * i + 1); | |
| 906 } | |
| 907 | |
| 908 StartBenchmarkTiming(); | |
| 909 for (int i = 0; i < iters; ++i) { | |
| 910 // 'mine' starts in the middle of 'theirs'. | |
| 911 IntervalSet<int> mine(size, size + 10); | |
| 912 mine.Intersection(theirs); | |
| 913 } | |
| 914 } | |
| 915 | |
| 916 BENCHMARK_RANGE(BM_IntersectionSmallAndLarge, 0, 1 << 23); | |
| 917 | |
| 918 static void BM_IntersectionIdentical(int iters, int size) { | |
| 919 // Intersects identical 'mine' and 'theirs'. | |
| 920 StopBenchmarkTiming(); | |
| 921 IntervalSet<int> mine; | |
| 922 for (int i = 0; i < size; ++i) { | |
| 923 mine.Add(2 * i, 2 * i + 1); | |
| 924 } | |
| 925 IntervalSet<int> theirs(mine); | |
| 926 | |
| 927 StartBenchmarkTiming(); | |
| 928 for (int i = 0; i < iters; ++i) { | |
| 929 mine.Intersection(theirs); | |
| 930 } | |
| 931 } | |
| 932 | |
| 933 BENCHMARK_RANGE(BM_IntersectionIdentical, 0, 1 << 23); | |
| 934 | |
| 935 class IntervalSetInitTest : public testing::Test { | |
| 936 protected: | |
| 937 const std::vector<Interval<int>> intervals_{{0, 1}, {2, 4}}; | |
| 938 }; | |
| 939 | |
| 940 TEST_F(IntervalSetInitTest, DirectInit) { | |
| 941 std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}}; | |
| 942 IntervalSet<int> s(il); | |
| 943 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 944 } | |
| 945 | |
| 946 TEST_F(IntervalSetInitTest, CopyInit) { | |
| 947 std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}}; | |
| 948 IntervalSet<int> s = il; | |
| 949 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 950 } | |
| 951 | |
| 952 TEST_F(IntervalSetInitTest, AssignIterPair) { | |
| 953 IntervalSet<int> s(0, 1000); // Make sure assign clears. | |
| 954 s.assign(intervals_.begin(), intervals_.end()); | |
| 955 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 956 } | |
| 957 | |
| 958 TEST_F(IntervalSetInitTest, AssignInitList) { | |
| 959 IntervalSet<int> s(0, 1000); // Make sure assign clears. | |
| 960 s.assign({{0, 1}, {2, 3}, {3, 4}}); | |
| 961 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 962 } | |
| 963 | |
| 964 TEST_F(IntervalSetInitTest, AssignmentInitList) { | |
| 965 std::initializer_list<Interval<int>> il = {{0, 1}, {2, 3}, {3, 4}}; | |
| 966 IntervalSet<int> s; | |
| 967 s = il; | |
| 968 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 969 } | |
| 970 | |
| 971 TEST_F(IntervalSetInitTest, BracedInitThenBracedAssign) { | |
| 972 IntervalSet<int> s{{0, 1}, {2, 3}, {3, 4}}; | |
| 973 s = {{0, 1}, {2, 4}}; | |
| 974 EXPECT_THAT(s, ElementsAreArray(intervals_)); | |
| 975 } | |
| 976 | |
| 977 #endif // 0 | |
| 978 | |
| 979 } // namespace | |
| 980 } // namespace test | |
| 981 } // namespace net | |
| 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