unittests/ADT/IntervalMapTest.cpp

   1 //===---- ADT/IntervalMapTest.cpp - IntervalMap unit tests ------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/IntervalMap.h"
  10 #include "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 typedef IntervalMap<unsigned, unsigned, 4> UUMap;
  17 typedef IntervalMap<unsigned, unsigned, 4,
  18                     IntervalMapHalfOpenInfo<unsigned>> UUHalfOpenMap;
  19
  20 // Empty map tests
  21 TEST(IntervalMapTest, EmptyMap) {
  22   UUMap::Allocator allocator;
  23   UUMap map(allocator);
  24   EXPECT_TRUE(map.empty());
  25
  26   // Lookup on empty map.
  27   EXPECT_EQ(0u, map.lookup(0));
  28   EXPECT_EQ(7u, map.lookup(0, 7));
  29   EXPECT_EQ(0u, map.lookup(~0u-1));
  30   EXPECT_EQ(7u, map.lookup(~0u-1, 7));
  31
  32   // Iterators.
  33   EXPECT_TRUE(map.begin() == map.begin());
  34   EXPECT_TRUE(map.begin() == map.end());
  35   EXPECT_TRUE(map.end() == map.end());
  36   EXPECT_FALSE(map.begin() != map.begin());
  37   EXPECT_FALSE(map.begin() != map.end());
  38   EXPECT_FALSE(map.end() != map.end());
  39   EXPECT_FALSE(map.begin().valid());
  40   EXPECT_FALSE(map.end().valid());
  41   UUMap::iterator I = map.begin();
  42   EXPECT_FALSE(I.valid());
  43   EXPECT_TRUE(I == map.end());
  44
  45   // Default constructor and cross-constness compares.
  46   UUMap::const_iterator CI;
  47   CI = map.begin();
  48   EXPECT_TRUE(CI == I);
  49   UUMap::iterator I2;
  50   I2 = map.end();
  51   EXPECT_TRUE(I2 == CI);
  52 }
  53
  54 // Single entry map tests
  55 TEST(IntervalMapTest, SingleEntryMap) {
  56   UUMap::Allocator allocator;
  57   UUMap map(allocator);
  58   map.insert(100, 150, 1);
  59   EXPECT_FALSE(map.empty());
  60
  61   // Lookup around interval.
  62   EXPECT_EQ(0u, map.lookup(0));
  63   EXPECT_EQ(0u, map.lookup(99));
  64   EXPECT_EQ(1u, map.lookup(100));
  65   EXPECT_EQ(1u, map.lookup(101));
  66   EXPECT_EQ(1u, map.lookup(125));
  67   EXPECT_EQ(1u, map.lookup(149));
  68   EXPECT_EQ(1u, map.lookup(150));
  69   EXPECT_EQ(0u, map.lookup(151));
  70   EXPECT_EQ(0u, map.lookup(200));
  71   EXPECT_EQ(0u, map.lookup(~0u-1));
  72
  73   // Iterators.
  74   EXPECT_TRUE(map.begin() == map.begin());
  75   EXPECT_FALSE(map.begin() == map.end());
  76   EXPECT_TRUE(map.end() == map.end());
  77   EXPECT_TRUE(map.begin().valid());
  78   EXPECT_FALSE(map.end().valid());
  79
  80   // Iter deref.
  81   UUMap::iterator I = map.begin();
  82   ASSERT_TRUE(I.valid());
  83   EXPECT_EQ(100u, I.start());
  84   EXPECT_EQ(150u, I.stop());
  85   EXPECT_EQ(1u, I.value());
  86
  87   // Preincrement.
  88   ++I;
  89   EXPECT_FALSE(I.valid());
  90   EXPECT_FALSE(I == map.begin());
  91   EXPECT_TRUE(I == map.end());
  92
  93   // PreDecrement.
  94   --I;
  95   ASSERT_TRUE(I.valid());
  96   EXPECT_EQ(100u, I.start());
  97   EXPECT_EQ(150u, I.stop());
  98   EXPECT_EQ(1u, I.value());
  99   EXPECT_TRUE(I == map.begin());
 100   EXPECT_FALSE(I == map.end());
 101
 102   // Change the value.
 103   I.setValue(2);
 104   ASSERT_TRUE(I.valid());
 105   EXPECT_EQ(100u, I.start());
 106   EXPECT_EQ(150u, I.stop());
 107   EXPECT_EQ(2u, I.value());
 108
 109   // Grow the bounds.
 110   I.setStart(0);
 111   ASSERT_TRUE(I.valid());
 112   EXPECT_EQ(0u, I.start());
 113   EXPECT_EQ(150u, I.stop());
 114   EXPECT_EQ(2u, I.value());
 115
 116   I.setStop(200);
 117   ASSERT_TRUE(I.valid());
 118   EXPECT_EQ(0u, I.start());
 119   EXPECT_EQ(200u, I.stop());
 120   EXPECT_EQ(2u, I.value());
 121
 122   // Shrink the bounds.
 123   I.setStart(150);
 124   ASSERT_TRUE(I.valid());
 125   EXPECT_EQ(150u, I.start());
 126   EXPECT_EQ(200u, I.stop());
 127   EXPECT_EQ(2u, I.value());
 128
 129   // Shrink the interval to have a length of 1
 130   I.setStop(150);
 131   ASSERT_TRUE(I.valid());
 132   EXPECT_EQ(150u, I.start());
 133   EXPECT_EQ(150u, I.stop());
 134   EXPECT_EQ(2u, I.value());
 135
 136   I.setStop(160);
 137   ASSERT_TRUE(I.valid());
 138   EXPECT_EQ(150u, I.start());
 139   EXPECT_EQ(160u, I.stop());
 140   EXPECT_EQ(2u, I.value());
 141
 142   // Shrink the interval to have a length of 1
 143   I.setStart(160);
 144   ASSERT_TRUE(I.valid());
 145   EXPECT_EQ(160u, I.start());
 146   EXPECT_EQ(160u, I.stop());
 147   EXPECT_EQ(2u, I.value());
 148
 149   // Erase last elem.
 150   I.erase();
 151   EXPECT_TRUE(map.empty());
 152   EXPECT_EQ(0, std::distance(map.begin(), map.end()));
 153 }
 154
 155 // Single entry half-open map tests
 156 TEST(IntervalMapTest, SingleEntryHalfOpenMap) {
 157   UUHalfOpenMap::Allocator allocator;
 158   UUHalfOpenMap map(allocator);
 159   map.insert(100, 150, 1);
 160   EXPECT_FALSE(map.empty());
 161
 162   UUHalfOpenMap::iterator I = map.begin();
 163   ASSERT_TRUE(I.valid());
 164
 165   // Shrink the interval to have a length of 1
 166   I.setStart(149);
 167   ASSERT_TRUE(I.valid());
 168   EXPECT_EQ(149u, I.start());
 169   EXPECT_EQ(150u, I.stop());
 170   EXPECT_EQ(1u, I.value());
 171
 172   I.setStop(160);
 173   ASSERT_TRUE(I.valid());
 174   EXPECT_EQ(149u, I.start());
 175   EXPECT_EQ(160u, I.stop());
 176   EXPECT_EQ(1u, I.value());
 177
 178   // Shrink the interval to have a length of 1
 179   I.setStop(150);
 180   ASSERT_TRUE(I.valid());
 181   EXPECT_EQ(149u, I.start());
 182   EXPECT_EQ(150u, I.stop());
 183   EXPECT_EQ(1u, I.value());
 184 }
 185
 186 // Flat coalescing tests.
 187 TEST(IntervalMapTest, RootCoalescing) {
 188   UUMap::Allocator allocator;
 189   UUMap map(allocator);
 190   map.insert(100, 150, 1);
 191
 192   // Coalesce from the left.
 193   map.insert(90, 99, 1);
 194   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 195   EXPECT_EQ(90u, map.start());
 196   EXPECT_EQ(150u, map.stop());
 197
 198   // Coalesce from the right.
 199   map.insert(151, 200, 1);
 200   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 201   EXPECT_EQ(90u, map.start());
 202   EXPECT_EQ(200u, map.stop());
 203
 204   // Non-coalesce from the left.
 205   map.insert(60, 89, 2);
 206   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 207   EXPECT_EQ(60u, map.start());
 208   EXPECT_EQ(200u, map.stop());
 209   EXPECT_EQ(2u, map.lookup(89));
 210   EXPECT_EQ(1u, map.lookup(90));
 211
 212   UUMap::iterator I = map.begin();
 213   EXPECT_EQ(60u, I.start());
 214   EXPECT_EQ(89u, I.stop());
 215   EXPECT_EQ(2u, I.value());
 216   ++I;
 217   EXPECT_EQ(90u, I.start());
 218   EXPECT_EQ(200u, I.stop());
 219   EXPECT_EQ(1u, I.value());
 220   ++I;
 221   EXPECT_FALSE(I.valid());
 222
 223   // Non-coalesce from the right.
 224   map.insert(201, 210, 2);
 225   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 226   EXPECT_EQ(60u, map.start());
 227   EXPECT_EQ(210u, map.stop());
 228   EXPECT_EQ(2u, map.lookup(201));
 229   EXPECT_EQ(1u, map.lookup(200));
 230
 231   // Erase from the left.
 232   map.begin().erase();
 233   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
 234   EXPECT_EQ(90u, map.start());
 235   EXPECT_EQ(210u, map.stop());
 236
 237   // Erase from the right.
 238   (--map.end()).erase();
 239   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 240   EXPECT_EQ(90u, map.start());
 241   EXPECT_EQ(200u, map.stop());
 242
 243   // Add non-coalescing, then trigger coalescing with setValue.
 244   map.insert(80, 89, 2);
 245   map.insert(201, 210, 2);
 246   EXPECT_EQ(3, std::distance(map.begin(), map.end()));
 247   (++map.begin()).setValue(2);
 248   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 249   I = map.begin();
 250   ASSERT_TRUE(I.valid());
 251   EXPECT_EQ(80u, I.start());
 252   EXPECT_EQ(210u, I.stop());
 253   EXPECT_EQ(2u, I.value());
 254 }
 255
 256 // Flat multi-coalescing tests.
 257 TEST(IntervalMapTest, RootMultiCoalescing) {
 258   UUMap::Allocator allocator;
 259   UUMap map(allocator);
 260   map.insert(140, 150, 1);
 261   map.insert(160, 170, 1);
 262   map.insert(100, 110, 1);
 263   map.insert(120, 130, 1);
 264   EXPECT_EQ(4, std::distance(map.begin(), map.end()));
 265   EXPECT_EQ(100u, map.start());
 266   EXPECT_EQ(170u, map.stop());
 267
 268   // Verify inserts.
 269   UUMap::iterator I = map.begin();
 270   EXPECT_EQ(100u, I.start());
 271   EXPECT_EQ(110u, I.stop());
 272   ++I;
 273   EXPECT_EQ(120u, I.start());
 274   EXPECT_EQ(130u, I.stop());
 275   ++I;
 276   EXPECT_EQ(140u, I.start());
 277   EXPECT_EQ(150u, I.stop());
 278   ++I;
 279   EXPECT_EQ(160u, I.start());
 280   EXPECT_EQ(170u, I.stop());
 281   ++I;
 282   EXPECT_FALSE(I.valid());
 283
 284   // Test advanceTo on flat tree.
 285   I = map.begin();
 286   I.advanceTo(135);
 287   ASSERT_TRUE(I.valid());
 288   EXPECT_EQ(140u, I.start());
 289   EXPECT_EQ(150u, I.stop());
 290
 291   I.advanceTo(145);
 292   ASSERT_TRUE(I.valid());
 293   EXPECT_EQ(140u, I.start());
 294   EXPECT_EQ(150u, I.stop());
 295
 296   I.advanceTo(200);
 297   EXPECT_FALSE(I.valid());
 298
 299   I.advanceTo(300);
 300   EXPECT_FALSE(I.valid());
 301
 302   // Coalesce left with followers.
 303   // [100;110] [120;130] [140;150] [160;170]
 304   map.insert(111, 115, 1);
 305   I = map.begin();
 306   ASSERT_TRUE(I.valid());
 307   EXPECT_EQ(100u, I.start());
 308   EXPECT_EQ(115u, I.stop());
 309   ++I;
 310   ASSERT_TRUE(I.valid());
 311   EXPECT_EQ(120u, I.start());
 312   EXPECT_EQ(130u, I.stop());
 313   ++I;
 314   ASSERT_TRUE(I.valid());
 315   EXPECT_EQ(140u, I.start());
 316   EXPECT_EQ(150u, I.stop());
 317   ++I;
 318   ASSERT_TRUE(I.valid());
 319   EXPECT_EQ(160u, I.start());
 320   EXPECT_EQ(170u, I.stop());
 321   ++I;
 322   EXPECT_FALSE(I.valid());
 323
 324   // Coalesce right with followers.
 325   // [100;115] [120;130] [140;150] [160;170]
 326   map.insert(135, 139, 1);
 327   I = map.begin();
 328   ASSERT_TRUE(I.valid());
 329   EXPECT_EQ(100u, I.start());
 330   EXPECT_EQ(115u, I.stop());
 331   ++I;
 332   ASSERT_TRUE(I.valid());
 333   EXPECT_EQ(120u, I.start());
 334   EXPECT_EQ(130u, I.stop());
 335   ++I;
 336   ASSERT_TRUE(I.valid());
 337   EXPECT_EQ(135u, I.start());
 338   EXPECT_EQ(150u, I.stop());
 339   ++I;
 340   ASSERT_TRUE(I.valid());
 341   EXPECT_EQ(160u, I.start());
 342   EXPECT_EQ(170u, I.stop());
 343   ++I;
 344   EXPECT_FALSE(I.valid());
 345
 346   // Coalesce left and right with followers.
 347   // [100;115] [120;130] [135;150] [160;170]
 348   map.insert(131, 134, 1);
 349   I = map.begin();
 350   ASSERT_TRUE(I.valid());
 351   EXPECT_EQ(100u, I.start());
 352   EXPECT_EQ(115u, I.stop());
 353   ++I;
 354   ASSERT_TRUE(I.valid());
 355   EXPECT_EQ(120u, I.start());
 356   EXPECT_EQ(150u, I.stop());
 357   ++I;
 358   ASSERT_TRUE(I.valid());
 359   EXPECT_EQ(160u, I.start());
 360   EXPECT_EQ(170u, I.stop());
 361   ++I;
 362   EXPECT_FALSE(I.valid());
 363
 364   // Test clear() on non-branched map.
 365   map.clear();
 366   EXPECT_TRUE(map.empty());
 367   EXPECT_TRUE(map.begin() == map.end());
 368 }
 369
 370 // Branched, non-coalescing tests.
 371 TEST(IntervalMapTest, Branched) {
 372   UUMap::Allocator allocator;
 373   UUMap map(allocator);
 374
 375   // Insert enough intervals to force a branched tree.
 376   // This creates 9 leaf nodes with 11 elements each, tree height = 1.
 377   for (unsigned i = 1; i < 100; ++i) {
 378     map.insert(10*i, 10*i+5, i);
 379     EXPECT_EQ(10u, map.start());
 380     EXPECT_EQ(10*i+5, map.stop());
 381   }
 382
 383   // Tree limits.
 384   EXPECT_FALSE(map.empty());
 385   EXPECT_EQ(10u, map.start());
 386   EXPECT_EQ(995u, map.stop());
 387
 388   // Tree lookup.
 389   for (unsigned i = 1; i < 100; ++i) {
 390     EXPECT_EQ(0u, map.lookup(10*i-1));
 391     EXPECT_EQ(i, map.lookup(10*i));
 392     EXPECT_EQ(i, map.lookup(10*i+5));
 393     EXPECT_EQ(0u, map.lookup(10*i+6));
 394   }
 395
 396   // Forward iteration.
 397   UUMap::iterator I = map.begin();
 398   for (unsigned i = 1; i < 100; ++i) {
 399     ASSERT_TRUE(I.valid());
 400     EXPECT_EQ(10*i, I.start());
 401     EXPECT_EQ(10*i+5, I.stop());
 402     EXPECT_EQ(i, *I);
 403     ++I;
 404   }
 405   EXPECT_FALSE(I.valid());
 406   EXPECT_TRUE(I == map.end());
 407
 408   // Backwards iteration.
 409   for (unsigned i = 99; i; --i) {
 410     --I;
 411     ASSERT_TRUE(I.valid());
 412     EXPECT_EQ(10*i, I.start());
 413     EXPECT_EQ(10*i+5, I.stop());
 414     EXPECT_EQ(i, *I);
 415   }
 416   EXPECT_TRUE(I == map.begin());
 417
 418   // Test advanceTo in same node.
 419   I.advanceTo(20);
 420   ASSERT_TRUE(I.valid());
 421   EXPECT_EQ(20u, I.start());
 422   EXPECT_EQ(25u, I.stop());
 423
 424   // Change value, no coalescing.
 425   I.setValue(0);
 426   ASSERT_TRUE(I.valid());
 427   EXPECT_EQ(20u, I.start());
 428   EXPECT_EQ(25u, I.stop());
 429   EXPECT_EQ(0u, I.value());
 430
 431   // Close the gap right, no coalescing.
 432   I.setStop(29);
 433   ASSERT_TRUE(I.valid());
 434   EXPECT_EQ(20u, I.start());
 435   EXPECT_EQ(29u, I.stop());
 436   EXPECT_EQ(0u, I.value());
 437
 438   // Change value, no coalescing.
 439   I.setValue(2);
 440   ASSERT_TRUE(I.valid());
 441   EXPECT_EQ(20u, I.start());
 442   EXPECT_EQ(29u, I.stop());
 443   EXPECT_EQ(2u, I.value());
 444
 445   // Change value, now coalescing.
 446   I.setValue(3);
 447   ASSERT_TRUE(I.valid());
 448   EXPECT_EQ(20u, I.start());
 449   EXPECT_EQ(35u, I.stop());
 450   EXPECT_EQ(3u, I.value());
 451
 452   // Close the gap, now coalescing.
 453   I.setValue(4);
 454   ASSERT_TRUE(I.valid());
 455   I.setStop(39);
 456   ASSERT_TRUE(I.valid());
 457   EXPECT_EQ(20u, I.start());
 458   EXPECT_EQ(45u, I.stop());
 459   EXPECT_EQ(4u, I.value());
 460
 461   // advanceTo another node.
 462   I.advanceTo(200);
 463   ASSERT_TRUE(I.valid());
 464   EXPECT_EQ(200u, I.start());
 465   EXPECT_EQ(205u, I.stop());
 466
 467   // Close the gap left, no coalescing.
 468   I.setStart(196);
 469   ASSERT_TRUE(I.valid());
 470   EXPECT_EQ(196u, I.start());
 471   EXPECT_EQ(205u, I.stop());
 472   EXPECT_EQ(20u, I.value());
 473
 474   // Change value, no coalescing.
 475   I.setValue(0);
 476   ASSERT_TRUE(I.valid());
 477   EXPECT_EQ(196u, I.start());
 478   EXPECT_EQ(205u, I.stop());
 479   EXPECT_EQ(0u, I.value());
 480
 481   // Change value, now coalescing.
 482   I.setValue(19);
 483   ASSERT_TRUE(I.valid());
 484   EXPECT_EQ(190u, I.start());
 485   EXPECT_EQ(205u, I.stop());
 486   EXPECT_EQ(19u, I.value());
 487
 488   // Close the gap, now coalescing.
 489   I.setValue(18);
 490   ASSERT_TRUE(I.valid());
 491   I.setStart(186);
 492   ASSERT_TRUE(I.valid());
 493   EXPECT_EQ(180u, I.start());
 494   EXPECT_EQ(205u, I.stop());
 495   EXPECT_EQ(18u, I.value());
 496
 497   // Erase from the front.
 498   I = map.begin();
 499   for (unsigned i = 0; i != 20; ++i) {
 500     I.erase();
 501     EXPECT_TRUE(I == map.begin());
 502     EXPECT_FALSE(map.empty());
 503     EXPECT_EQ(I.start(), map.start());
 504     EXPECT_EQ(995u, map.stop());
 505   }
 506
 507   // Test clear() on branched map.
 508   map.clear();
 509   EXPECT_TRUE(map.empty());
 510   EXPECT_TRUE(map.begin() == map.end());
 511 }
 512
 513 // Branched, high, non-coalescing tests.
 514 TEST(IntervalMapTest, Branched2) {
 515   UUMap::Allocator allocator;
 516   UUMap map(allocator);
 517
 518   // Insert enough intervals to force a height >= 2 tree.
 519   for (unsigned i = 1; i < 1000; ++i)
 520     map.insert(10*i, 10*i+5, i);
 521
 522   // Tree limits.
 523   EXPECT_FALSE(map.empty());
 524   EXPECT_EQ(10u, map.start());
 525   EXPECT_EQ(9995u, map.stop());
 526
 527   // Tree lookup.
 528   for (unsigned i = 1; i < 1000; ++i) {
 529     EXPECT_EQ(0u, map.lookup(10*i-1));
 530     EXPECT_EQ(i, map.lookup(10*i));
 531     EXPECT_EQ(i, map.lookup(10*i+5));
 532     EXPECT_EQ(0u, map.lookup(10*i+6));
 533   }
 534
 535   // Forward iteration.
 536   UUMap::iterator I = map.begin();
 537   for (unsigned i = 1; i < 1000; ++i) {
 538     ASSERT_TRUE(I.valid());
 539     EXPECT_EQ(10*i, I.start());
 540     EXPECT_EQ(10*i+5, I.stop());
 541     EXPECT_EQ(i, *I);
 542     ++I;
 543   }
 544   EXPECT_FALSE(I.valid());
 545   EXPECT_TRUE(I == map.end());
 546
 547   // Backwards iteration.
 548   for (unsigned i = 999; i; --i) {
 549     --I;
 550     ASSERT_TRUE(I.valid());
 551     EXPECT_EQ(10*i, I.start());
 552     EXPECT_EQ(10*i+5, I.stop());
 553     EXPECT_EQ(i, *I);
 554   }
 555   EXPECT_TRUE(I == map.begin());
 556
 557   // Test advanceTo in same node.
 558   I.advanceTo(20);
 559   ASSERT_TRUE(I.valid());
 560   EXPECT_EQ(20u, I.start());
 561   EXPECT_EQ(25u, I.stop());
 562
 563   // advanceTo sibling leaf node.
 564   I.advanceTo(200);
 565   ASSERT_TRUE(I.valid());
 566   EXPECT_EQ(200u, I.start());
 567   EXPECT_EQ(205u, I.stop());
 568
 569   // advanceTo further.
 570   I.advanceTo(2000);
 571   ASSERT_TRUE(I.valid());
 572   EXPECT_EQ(2000u, I.start());
 573   EXPECT_EQ(2005u, I.stop());
 574
 575   // advanceTo beyond end()
 576   I.advanceTo(20000);
 577   EXPECT_FALSE(I.valid());
 578
 579   // end().advanceTo() is valid as long as x > map.stop()
 580   I.advanceTo(30000);
 581   EXPECT_FALSE(I.valid());
 582
 583   // Test clear() on branched map.
 584   map.clear();
 585   EXPECT_TRUE(map.empty());
 586   EXPECT_TRUE(map.begin() == map.end());
 587 }
 588
 589 // Random insertions, coalescing to a single interval.
 590 TEST(IntervalMapTest, RandomCoalescing) {
 591   UUMap::Allocator allocator;
 592   UUMap map(allocator);
 593
 594   // This is a poor PRNG with maximal period:
 595   // x_n = 5 x_{n-1} + 1 mod 2^N
 596
 597   unsigned x = 100;
 598   for (unsigned i = 0; i != 4096; ++i) {
 599     map.insert(10*x, 10*x+9, 1);
 600     EXPECT_GE(10*x, map.start());
 601     EXPECT_LE(10*x+9, map.stop());
 602     x = (5*x+1)%4096;
 603   }
 604
 605   // Map should be fully coalesced after that exercise.
 606   EXPECT_FALSE(map.empty());
 607   EXPECT_EQ(0u, map.start());
 608   EXPECT_EQ(40959u, map.stop());
 609   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
 610
 611 }
 612
 613 TEST(IntervalMapTest, Overlaps) {
 614   UUMap::Allocator allocator;
 615   UUMap map(allocator);
 616   map.insert(10, 20, 0);
 617   map.insert(30, 40, 0);
 618   map.insert(50, 60, 0);
 619
 620   EXPECT_FALSE(map.overlaps(0, 9));
 621   EXPECT_TRUE(map.overlaps(0, 10));
 622   EXPECT_TRUE(map.overlaps(0, 15));
 623   EXPECT_TRUE(map.overlaps(0, 25));
 624   EXPECT_TRUE(map.overlaps(0, 45));
 625   EXPECT_TRUE(map.overlaps(10, 45));
 626   EXPECT_TRUE(map.overlaps(30, 45));
 627   EXPECT_TRUE(map.overlaps(35, 36));
 628   EXPECT_TRUE(map.overlaps(40, 45));
 629   EXPECT_FALSE(map.overlaps(45, 45));
 630   EXPECT_TRUE(map.overlaps(60, 60));
 631   EXPECT_TRUE(map.overlaps(60, 66));
 632   EXPECT_FALSE(map.overlaps(66, 66));
 633 }
 634
 635 TEST(IntervalMapTest, OverlapsHalfOpen) {
 636   UUHalfOpenMap::Allocator allocator;
 637   UUHalfOpenMap map(allocator);
 638   map.insert(10, 20, 0);
 639   map.insert(30, 40, 0);
 640   map.insert(50, 60, 0);
 641
 642   EXPECT_FALSE(map.overlaps(0, 9));
 643   EXPECT_FALSE(map.overlaps(0, 10));
 644   EXPECT_TRUE(map.overlaps(0, 15));
 645   EXPECT_TRUE(map.overlaps(0, 25));
 646   EXPECT_TRUE(map.overlaps(0, 45));
 647   EXPECT_TRUE(map.overlaps(10, 45));
 648   EXPECT_TRUE(map.overlaps(30, 45));
 649   EXPECT_TRUE(map.overlaps(35, 36));
 650   EXPECT_FALSE(map.overlaps(40, 45));
 651   EXPECT_FALSE(map.overlaps(45, 46));
 652   EXPECT_FALSE(map.overlaps(60, 61));
 653   EXPECT_FALSE(map.overlaps(60, 66));
 654   EXPECT_FALSE(map.overlaps(66, 67));
 655 }
 656
 657 TEST(IntervalMapOverlapsTest, SmallMaps) {
 658   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
 659   UUMap::Allocator allocator;
 660   UUMap mapA(allocator);
 661   UUMap mapB(allocator);
 662
 663   // empty, empty.
 664   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 665
 666   mapA.insert(1, 2, 3);
 667
 668   // full, empty
 669   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 670   // empty, full
 671   EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
 672
 673   mapB.insert(3, 4, 5);
 674
 675   // full, full, non-overlapping
 676   EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
 677   EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
 678
 679   // Add an overlapping segment.
 680   mapA.insert(4, 5, 6);
 681
 682   UUOverlaps AB(mapA, mapB);
 683   ASSERT_TRUE(AB.valid());
 684   EXPECT_EQ(4u, AB.a().start());
 685   EXPECT_EQ(3u, AB.b().start());
 686   ++AB;
 687   EXPECT_FALSE(AB.valid());
 688
 689   UUOverlaps BA(mapB, mapA);
 690   ASSERT_TRUE(BA.valid());
 691   EXPECT_EQ(3u, BA.a().start());
 692   EXPECT_EQ(4u, BA.b().start());
 693   // advance past end.
 694   BA.advanceTo(6);
 695   EXPECT_FALSE(BA.valid());
 696   // advance an invalid iterator.
 697   BA.advanceTo(7);
 698   EXPECT_FALSE(BA.valid());
 699 }
 700
 701 TEST(IntervalMapOverlapsTest, BigMaps) {
 702   typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
 703   UUMap::Allocator allocator;
 704   UUMap mapA(allocator);
 705   UUMap mapB(allocator);
 706
 707   // [0;4] [10;14] [20;24] ...
 708   for (unsigned n = 0; n != 100; ++n)
 709     mapA.insert(10*n, 10*n+4, n);
 710
 711   // [5;6] [15;16] [25;26] ...
 712   for (unsigned n = 10; n != 20; ++n)
 713     mapB.insert(10*n+5, 10*n+6, n);
 714
 715   // [208;209] [218;219] ...
 716   for (unsigned n = 20; n != 30; ++n)
 717     mapB.insert(10*n+8, 10*n+9, n);
 718
 719   // insert some overlapping segments.
 720   mapB.insert(400, 400, 400);
 721   mapB.insert(401, 401, 401);
 722   mapB.insert(402, 500, 402);
 723   mapB.insert(600, 601, 402);
 724
 725   UUOverlaps AB(mapA, mapB);
 726   ASSERT_TRUE(AB.valid());
 727   EXPECT_EQ(400u, AB.a().start());
 728   EXPECT_EQ(400u, AB.b().start());
 729   ++AB;
 730   ASSERT_TRUE(AB.valid());
 731   EXPECT_EQ(400u, AB.a().start());
 732   EXPECT_EQ(401u, AB.b().start());
 733   ++AB;
 734   ASSERT_TRUE(AB.valid());
 735   EXPECT_EQ(400u, AB.a().start());
 736   EXPECT_EQ(402u, AB.b().start());
 737   ++AB;
 738   ASSERT_TRUE(AB.valid());
 739   EXPECT_EQ(410u, AB.a().start());
 740   EXPECT_EQ(402u, AB.b().start());
 741   ++AB;
 742   ASSERT_TRUE(AB.valid());
 743   EXPECT_EQ(420u, AB.a().start());
 744   EXPECT_EQ(402u, AB.b().start());
 745   AB.skipB();
 746   ASSERT_TRUE(AB.valid());
 747   EXPECT_EQ(600u, AB.a().start());
 748   EXPECT_EQ(600u, AB.b().start());
 749   ++AB;
 750   EXPECT_FALSE(AB.valid());
 751
 752   // Test advanceTo.
 753   UUOverlaps AB2(mapA, mapB);
 754   AB2.advanceTo(410);
 755   ASSERT_TRUE(AB2.valid());
 756   EXPECT_EQ(410u, AB2.a().start());
 757   EXPECT_EQ(402u, AB2.b().start());
 758
 759   // It is valid to advanceTo with any monotonic sequence.
 760   AB2.advanceTo(411);
 761   ASSERT_TRUE(AB2.valid());
 762   EXPECT_EQ(410u, AB2.a().start());
 763   EXPECT_EQ(402u, AB2.b().start());
 764
 765   // Check reversed maps.
 766   UUOverlaps BA(mapB, mapA);
 767   ASSERT_TRUE(BA.valid());
 768   EXPECT_EQ(400u, BA.b().start());
 769   EXPECT_EQ(400u, BA.a().start());
 770   ++BA;
 771   ASSERT_TRUE(BA.valid());
 772   EXPECT_EQ(400u, BA.b().start());
 773   EXPECT_EQ(401u, BA.a().start());
 774   ++BA;
 775   ASSERT_TRUE(BA.valid());
 776   EXPECT_EQ(400u, BA.b().start());
 777   EXPECT_EQ(402u, BA.a().start());
 778   ++BA;
 779   ASSERT_TRUE(BA.valid());
 780   EXPECT_EQ(410u, BA.b().start());
 781   EXPECT_EQ(402u, BA.a().start());
 782   ++BA;
 783   ASSERT_TRUE(BA.valid());
 784   EXPECT_EQ(420u, BA.b().start());
 785   EXPECT_EQ(402u, BA.a().start());
 786   BA.skipA();
 787   ASSERT_TRUE(BA.valid());
 788   EXPECT_EQ(600u, BA.b().start());
 789   EXPECT_EQ(600u, BA.a().start());
 790   ++BA;
 791   EXPECT_FALSE(BA.valid());
 792
 793   // Test advanceTo.
 794   UUOverlaps BA2(mapB, mapA);
 795   BA2.advanceTo(410);
 796   ASSERT_TRUE(BA2.valid());
 797   EXPECT_EQ(410u, BA2.b().start());
 798   EXPECT_EQ(402u, BA2.a().start());
 799
 800   BA2.advanceTo(411);
 801   ASSERT_TRUE(BA2.valid());
 802   EXPECT_EQ(410u, BA2.b().start());
 803   EXPECT_EQ(402u, BA2.a().start());
 804 }
 805
 806 } // namespace