net/quic/interval_set_test.cc

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