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