unittests/ADT/IntervalMapTest.cpp

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