X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=unittests%2FADT%2FIntervalMapTest.cpp;h=b5556d265ae49bb5cb433deb67615a63f808c9cb;hp=c7def84340a69399821609a8d00424e68fb2e1c1;hb=63b14baf799b4c3ba8182596073ad5b3f37cd1cc;hpb=db52566d684a36cf1f320f91ca5c15d5cd075b95

diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index c7def84340a..b5556d265ae 100644
--- a/unittests/ADT/IntervalMapTest.cpp
+++ b/unittests/ADT/IntervalMapTest.cpp
@@ -14,7 +14,7 @@ using namespace llvm;
 
 namespace {
 
-typedef IntervalMap<unsigned, unsigned> UUMap;
+typedef IntervalMap<unsigned, unsigned, 4> UUMap;
 
 // Empty map tests
 TEST(IntervalMapTest, EmptyMap) {
@@ -40,6 +40,14 @@ TEST(IntervalMapTest, EmptyMap) {
   UUMap::iterator I = map.begin();
   EXPECT_FALSE(I.valid());
   EXPECT_TRUE(I == map.end());
+
+  // Default constructor and cross-constness compares.
+  UUMap::const_iterator CI;
+  CI = map.begin();
+  EXPECT_TRUE(CI == I);
+  UUMap::iterator I2;
+  I2 = map.end();
+  EXPECT_TRUE(I2 == CI);
 }
 
 // Single entry map tests
@@ -89,6 +97,44 @@ TEST(IntervalMapTest, SingleEntryMap) {
   EXPECT_EQ(1u, I.value());
   EXPECT_TRUE(I == map.begin());
   EXPECT_FALSE(I == map.end());
+
+  // Change the value.
+  I.setValue(2);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(100u, I.start());
+  EXPECT_EQ(150u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  // Grow the bounds.
+  I.setStart(0);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(0u, I.start());
+  EXPECT_EQ(150u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  I.setStop(200);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(0u, I.start());
+  EXPECT_EQ(200u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  // Shrink the bounds.
+  I.setStart(150);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(150u, I.start());
+  EXPECT_EQ(200u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  I.setStop(160);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(150u, I.start());
+  EXPECT_EQ(160u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  // Erase last elem.
+  I.erase();
+  EXPECT_TRUE(map.empty());
+  EXPECT_EQ(0, std::distance(map.begin(), map.end()));
 }
 
 // Flat coalescing tests.
@@ -103,50 +149,26 @@ TEST(IntervalMapTest, RootCoalescing) {
   EXPECT_EQ(90u, map.start());
   EXPECT_EQ(150u, map.stop());
 
-  // Overlap left.
-  map.insert(80, 100, 1);
-  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
-  EXPECT_EQ(80u, map.start());
-  EXPECT_EQ(150u, map.stop());
-
-  // Inside.
-  map.insert(100, 130, 1);
-  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
-  EXPECT_EQ(80u, map.start());
-  EXPECT_EQ(150u, map.stop());
-
-  // Overlap both.
-  map.insert(70, 160, 1);
-  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
-  EXPECT_EQ(70u, map.start());
-  EXPECT_EQ(160u, map.stop());
-
-  // Overlap right.
-  map.insert(80, 170, 1);
-  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
-  EXPECT_EQ(70u, map.start());
-  EXPECT_EQ(170u, map.stop());
-
   // Coalesce from the right.
-  map.insert(170, 200, 1);
+  map.insert(151, 200, 1);
   EXPECT_EQ(1, std::distance(map.begin(), map.end()));
-  EXPECT_EQ(70u, map.start());
+  EXPECT_EQ(90u, map.start());
   EXPECT_EQ(200u, map.stop());
 
   // Non-coalesce from the left.
-  map.insert(60, 69, 2);
+  map.insert(60, 89, 2);
   EXPECT_EQ(2, std::distance(map.begin(), map.end()));
   EXPECT_EQ(60u, map.start());
   EXPECT_EQ(200u, map.stop());
-  EXPECT_EQ(2u, map.lookup(69));
-  EXPECT_EQ(1u, map.lookup(70));
+  EXPECT_EQ(2u, map.lookup(89));
+  EXPECT_EQ(1u, map.lookup(90));
 
   UUMap::iterator I = map.begin();
   EXPECT_EQ(60u, I.start());
-  EXPECT_EQ(69u, I.stop());
+  EXPECT_EQ(89u, I.stop());
   EXPECT_EQ(2u, I.value());
   ++I;
-  EXPECT_EQ(70u, I.start());
+  EXPECT_EQ(90u, I.start());
   EXPECT_EQ(200u, I.stop());
   EXPECT_EQ(1u, I.value());
   ++I;
@@ -159,6 +181,30 @@ TEST(IntervalMapTest, RootCoalescing) {
   EXPECT_EQ(210u, map.stop());
   EXPECT_EQ(2u, map.lookup(201));
   EXPECT_EQ(1u, map.lookup(200));
+
+  // Erase from the left.
+  map.begin().erase();
+  EXPECT_EQ(2, std::distance(map.begin(), map.end()));
+  EXPECT_EQ(90u, map.start());
+  EXPECT_EQ(210u, map.stop());
+
+  // Erase from the right.
+  (--map.end()).erase();
+  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
+  EXPECT_EQ(90u, map.start());
+  EXPECT_EQ(200u, map.stop());
+
+  // Add non-coalescing, then trigger coalescing with setValue.
+  map.insert(80, 89, 2);
+  map.insert(201, 210, 2);
+  EXPECT_EQ(3, std::distance(map.begin(), map.end()));
+  (++map.begin()).setValue(2);
+  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
+  I = map.begin();
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(80u, I.start());
+  EXPECT_EQ(210u, I.stop());
+  EXPECT_EQ(2u, I.value());
 }
 
 // Flat multi-coalescing tests.
@@ -189,6 +235,23 @@ TEST(IntervalMapTest, RootMultiCoalescing) {
   ++I;
   EXPECT_FALSE(I.valid());
 
+  // Test advanceTo on flat tree.
+  I = map.begin();
+  I.advanceTo(135);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(140u, I.start());
+  EXPECT_EQ(150u, I.stop());
+
+  I.advanceTo(145);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(140u, I.start());
+  EXPECT_EQ(150u, I.stop());
+
+  I.advanceTo(200);
+  EXPECT_FALSE(I.valid());
+
+  I.advanceTo(300);
+  EXPECT_FALSE(I.valid());
 
   // Coalesce left with followers.
   // [100;110] [120;130] [140;150] [160;170]
@@ -252,88 +315,171 @@ TEST(IntervalMapTest, RootMultiCoalescing) {
   ++I;
   EXPECT_FALSE(I.valid());
 
-  // Coalesce multiple with overlap right.
-  // [100;115] [120;150] [160;170]
-  map.insert(116, 165, 1);
-  I = map.begin();
-  ASSERT_TRUE(I.valid());
-  EXPECT_EQ(100u, I.start());
-  EXPECT_EQ(170u, I.stop());
-  ++I;
+  // Test clear() on non-branched map.
+  map.clear();
+  EXPECT_TRUE(map.empty());
+  EXPECT_TRUE(map.begin() == map.end());
+}
+
+// Branched, non-coalescing tests.
+TEST(IntervalMapTest, Branched) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+
+  // Insert enough intervals to force a branched tree.
+  // This creates 9 leaf nodes with 11 elements each, tree height = 1.
+  for (unsigned i = 1; i < 100; ++i) {
+    map.insert(10*i, 10*i+5, i);
+    EXPECT_EQ(10u, map.start());
+    EXPECT_EQ(10*i+5, map.stop());
+  }
+
+  // Tree limits.
+  EXPECT_FALSE(map.empty());
+  EXPECT_EQ(10u, map.start());
+  EXPECT_EQ(995u, map.stop());
+
+  // Tree lookup.
+  for (unsigned i = 1; i < 100; ++i) {
+    EXPECT_EQ(0u, map.lookup(10*i-1));
+    EXPECT_EQ(i, map.lookup(10*i));
+    EXPECT_EQ(i, map.lookup(10*i+5));
+    EXPECT_EQ(0u, map.lookup(10*i+6));
+  }
+
+  // Forward iteration.
+  UUMap::iterator I = map.begin();
+  for (unsigned i = 1; i < 100; ++i) {
+    ASSERT_TRUE(I.valid());
+    EXPECT_EQ(10*i, I.start());
+    EXPECT_EQ(10*i+5, I.stop());
+    EXPECT_EQ(i, *I);
+    ++I;
+  }
   EXPECT_FALSE(I.valid());
+  EXPECT_TRUE(I == map.end());
 
-  // Coalesce multiple with overlap left
-  // [100;170]
-  map.insert(180, 190, 1);
-  map.insert(200, 210, 1);
-  map.insert(220, 230, 1);
-  // [100;170] [180;190] [200;210] [220;230]
-  map.insert(160, 199, 1);
-  I = map.begin();
+  // Backwards iteration.
+  for (unsigned i = 99; i; --i) {
+    --I;
+    ASSERT_TRUE(I.valid());
+    EXPECT_EQ(10*i, I.start());
+    EXPECT_EQ(10*i+5, I.stop());
+    EXPECT_EQ(i, *I);
+  }
+  EXPECT_TRUE(I == map.begin());
+
+  // Test advanceTo in same node.
+  I.advanceTo(20);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(100u, I.start());
-  EXPECT_EQ(210u, I.stop());
-  ++I;
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(25u, I.stop());
+
+  // Change value, no coalescing.
+  I.setValue(0);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(220u, I.start());
-  EXPECT_EQ(230u, I.stop());
-  ++I;
-  EXPECT_FALSE(I.valid());
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(25u, I.stop());
+  EXPECT_EQ(0u, I.value());
 
-  // Overwrite 2 from gap to gap.
-  // [100;210] [220;230]
-  map.insert(50, 250, 1);
-  I = map.begin();
+  // Close the gap right, no coalescing.
+  I.setStop(29);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(50u, I.start());
-  EXPECT_EQ(250u, I.stop());
-  ++I;
-  EXPECT_FALSE(I.valid());
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(29u, I.stop());
+  EXPECT_EQ(0u, I.value());
 
-  // Coalesce at end of full root.
-  // [50;250]
-  map.insert(260, 270, 1);
-  map.insert(280, 290, 1);
-  map.insert(300, 310, 1);
-  // [50;250] [260;270] [280;290] [300;310]
-  map.insert(311, 320, 1);
-  I = map.begin();
+  // Change value, no coalescing.
+  I.setValue(2);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(50u, I.start());
-  EXPECT_EQ(250u, I.stop());
-  ++I;
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(29u, I.stop());
+  EXPECT_EQ(2u, I.value());
+
+  // Change value, now coalescing.
+  I.setValue(3);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(260u, I.start());
-  EXPECT_EQ(270u, I.stop());
-  ++I;
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(35u, I.stop());
+  EXPECT_EQ(3u, I.value());
+
+  // Close the gap, now coalescing.
+  I.setValue(4);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(280u, I.start());
-  EXPECT_EQ(290u, I.stop());
-  ++I;
+  I.setStop(39);
   ASSERT_TRUE(I.valid());
-  EXPECT_EQ(300u, I.start());
-  EXPECT_EQ(320u, I.stop());
-  ++I;
-  EXPECT_FALSE(I.valid());
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(45u, I.stop());
+  EXPECT_EQ(4u, I.value());
+
+  // advanceTo another node.
+  I.advanceTo(200);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(200u, I.start());
+  EXPECT_EQ(205u, I.stop());
+
+  // Close the gap left, no coalescing.
+  I.setStart(196);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(196u, I.start());
+  EXPECT_EQ(205u, I.stop());
+  EXPECT_EQ(20u, I.value());
+
+  // Change value, no coalescing.
+  I.setValue(0);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(196u, I.start());
+  EXPECT_EQ(205u, I.stop());
+  EXPECT_EQ(0u, I.value());
+
+  // Change value, now coalescing.
+  I.setValue(19);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(190u, I.start());
+  EXPECT_EQ(205u, I.stop());
+  EXPECT_EQ(19u, I.value());
+
+  // Close the gap, now coalescing.
+  I.setValue(18);
+  ASSERT_TRUE(I.valid());
+  I.setStart(186);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(180u, I.start());
+  EXPECT_EQ(205u, I.stop());
+  EXPECT_EQ(18u, I.value());
+
+  // Erase from the front.
+  I = map.begin();
+  for (unsigned i = 0; i != 20; ++i) {
+    I.erase();
+    EXPECT_TRUE(I == map.begin());
+    EXPECT_FALSE(map.empty());
+    EXPECT_EQ(I.start(), map.start());
+    EXPECT_EQ(995u, map.stop());
+  }
+
+  // Test clear() on branched map.
+  map.clear();
+  EXPECT_TRUE(map.empty());
+  EXPECT_TRUE(map.begin() == map.end());
 }
 
-// Branched, non-coalescing tests.
-TEST(IntervalMapTest, Branched) {
+// Branched, high, non-coalescing tests.
+TEST(IntervalMapTest, Branched2) {
   UUMap::Allocator allocator;
   UUMap map(allocator);
 
-  // Insert enough intervals to force a branched tree.
-  // This creates 9 leaf nodes with 11 elements each, tree height = 1.
-  for (unsigned i = 1; i < 100; ++i)
+  // Insert enough intervals to force a height >= 2 tree.
+  for (unsigned i = 1; i < 1000; ++i)
     map.insert(10*i, 10*i+5, i);
 
   // Tree limits.
   EXPECT_FALSE(map.empty());
   EXPECT_EQ(10u, map.start());
-  EXPECT_EQ(995u, map.stop());
+  EXPECT_EQ(9995u, map.stop());
 
   // Tree lookup.
-  for (unsigned i = 1; i < 100; ++i) {
+  for (unsigned i = 1; i < 1000; ++i) {
     EXPECT_EQ(0u, map.lookup(10*i-1));
     EXPECT_EQ(i, map.lookup(10*i));
     EXPECT_EQ(i, map.lookup(10*i+5));
@@ -342,7 +488,7 @@ TEST(IntervalMapTest, Branched) {
 
   // Forward iteration.
   UUMap::iterator I = map.begin();
-  for (unsigned i = 1; i < 100; ++i) {
+  for (unsigned i = 1; i < 1000; ++i) {
     ASSERT_TRUE(I.valid());
     EXPECT_EQ(10*i, I.start());
     EXPECT_EQ(10*i+5, I.stop());
@@ -353,7 +499,7 @@ TEST(IntervalMapTest, Branched) {
   EXPECT_TRUE(I == map.end());
 
   // Backwards iteration.
-  for (unsigned i = 99; i; --i) {
+  for (unsigned i = 999; i; --i) {
     --I;
     ASSERT_TRUE(I.valid());
     EXPECT_EQ(10*i, I.start());
@@ -362,6 +508,209 @@ TEST(IntervalMapTest, Branched) {
   }
   EXPECT_TRUE(I == map.begin());
 
+  // Test advanceTo in same node.
+  I.advanceTo(20);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(20u, I.start());
+  EXPECT_EQ(25u, I.stop());
+
+  // advanceTo sibling leaf node.
+  I.advanceTo(200);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(200u, I.start());
+  EXPECT_EQ(205u, I.stop());
+
+  // advanceTo further.
+  I.advanceTo(2000);
+  ASSERT_TRUE(I.valid());
+  EXPECT_EQ(2000u, I.start());
+  EXPECT_EQ(2005u, I.stop());
+
+  // advanceTo beyond end()
+  I.advanceTo(20000);
+  EXPECT_FALSE(I.valid());
+
+  // end().advanceTo() is valid as long as x > map.stop()
+  I.advanceTo(30000);
+  EXPECT_FALSE(I.valid());
+
+  // Test clear() on branched map.
+  map.clear();
+  EXPECT_TRUE(map.empty());
+  EXPECT_TRUE(map.begin() == map.end());
+}
+
+// Random insertions, coalescing to a single interval.
+TEST(IntervalMapTest, RandomCoalescing) {
+  UUMap::Allocator allocator;
+  UUMap map(allocator);
+
+  // This is a poor PRNG with maximal period:
+  // x_n = 5 x_{n-1} + 1 mod 2^N
+
+  unsigned x = 100;
+  for (unsigned i = 0; i != 4096; ++i) {
+    map.insert(10*x, 10*x+9, 1);
+    EXPECT_GE(10*x, map.start());
+    EXPECT_LE(10*x+9, map.stop());
+    x = (5*x+1)%4096;
+  }
+
+  // Map should be fully coalesced after that exercise.
+  EXPECT_FALSE(map.empty());
+  EXPECT_EQ(0u, map.start());
+  EXPECT_EQ(40959u, map.stop());
+  EXPECT_EQ(1, std::distance(map.begin(), map.end()));
+
+}
+
+TEST(IntervalMapOverlapsTest, SmallMaps) {
+  typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
+  UUMap::Allocator allocator;
+  UUMap mapA(allocator);
+  UUMap mapB(allocator);
+
+  // empty, empty.
+  EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
+
+  mapA.insert(1, 2, 3);
+
+  // full, empty
+  EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
+  // empty, full
+  EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
+
+  mapB.insert(3, 4, 5);
+
+  // full, full, non-overlapping
+  EXPECT_FALSE(UUOverlaps(mapA, mapB).valid());
+  EXPECT_FALSE(UUOverlaps(mapB, mapA).valid());
+
+  // Add an overlapping segment.
+  mapA.insert(4, 5, 6);
+
+  UUOverlaps AB(mapA, mapB);
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(4u, AB.a().start());
+  EXPECT_EQ(3u, AB.b().start());
+  ++AB;
+  EXPECT_FALSE(AB.valid());
+
+  UUOverlaps BA(mapB, mapA);
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(3u, BA.a().start());
+  EXPECT_EQ(4u, BA.b().start());
+  // advance past end.
+  BA.advanceTo(6);
+  EXPECT_FALSE(BA.valid());
+  // advance an invalid iterator.
+  BA.advanceTo(7);
+  EXPECT_FALSE(BA.valid());
+}
+
+TEST(IntervalMapOverlapsTest, BigMaps) {
+  typedef IntervalMapOverlaps<UUMap,UUMap> UUOverlaps;
+  UUMap::Allocator allocator;
+  UUMap mapA(allocator);
+  UUMap mapB(allocator);
+
+  // [0;4] [10;14] [20;24] ...
+  for (unsigned n = 0; n != 100; ++n)
+    mapA.insert(10*n, 10*n+4, n);
+
+  // [5;6] [15;16] [25;26] ...
+  for (unsigned n = 10; n != 20; ++n)
+    mapB.insert(10*n+5, 10*n+6, n);
+
+  // [208;209] [218;219] ...
+  for (unsigned n = 20; n != 30; ++n)
+    mapB.insert(10*n+8, 10*n+9, n);
+
+  // insert some overlapping segments.
+  mapB.insert(400, 400, 400);
+  mapB.insert(401, 401, 401);
+  mapB.insert(402, 500, 402);
+  mapB.insert(600, 601, 402);
+
+  UUOverlaps AB(mapA, mapB);
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(400u, AB.a().start());
+  EXPECT_EQ(400u, AB.b().start());
+  ++AB;
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(400u, AB.a().start());
+  EXPECT_EQ(401u, AB.b().start());
+  ++AB;
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(400u, AB.a().start());
+  EXPECT_EQ(402u, AB.b().start());
+  ++AB;
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(410u, AB.a().start());
+  EXPECT_EQ(402u, AB.b().start());
+  ++AB;
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(420u, AB.a().start());
+  EXPECT_EQ(402u, AB.b().start());
+  AB.skipB();
+  ASSERT_TRUE(AB.valid());
+  EXPECT_EQ(600u, AB.a().start());
+  EXPECT_EQ(600u, AB.b().start());
+  ++AB;
+  EXPECT_FALSE(AB.valid());
+
+  // Test advanceTo.
+  UUOverlaps AB2(mapA, mapB);
+  AB2.advanceTo(410);
+  ASSERT_TRUE(AB2.valid());
+  EXPECT_EQ(410u, AB2.a().start());
+  EXPECT_EQ(402u, AB2.b().start());
+
+  // It is valid to advanceTo with any monotonic sequence.
+  AB2.advanceTo(411);
+  ASSERT_TRUE(AB2.valid());
+  EXPECT_EQ(410u, AB2.a().start());
+  EXPECT_EQ(402u, AB2.b().start());
+
+  // Check reversed maps.
+  UUOverlaps BA(mapB, mapA);
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(400u, BA.b().start());
+  EXPECT_EQ(400u, BA.a().start());
+  ++BA;
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(400u, BA.b().start());
+  EXPECT_EQ(401u, BA.a().start());
+  ++BA;
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(400u, BA.b().start());
+  EXPECT_EQ(402u, BA.a().start());
+  ++BA;
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(410u, BA.b().start());
+  EXPECT_EQ(402u, BA.a().start());
+  ++BA;
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(420u, BA.b().start());
+  EXPECT_EQ(402u, BA.a().start());
+  BA.skipA();
+  ASSERT_TRUE(BA.valid());
+  EXPECT_EQ(600u, BA.b().start());
+  EXPECT_EQ(600u, BA.a().start());
+  ++BA;
+  EXPECT_FALSE(BA.valid());
+
+  // Test advanceTo.
+  UUOverlaps BA2(mapB, mapA);
+  BA2.advanceTo(410);
+  ASSERT_TRUE(BA2.valid());
+  EXPECT_EQ(410u, BA2.b().start());
+  EXPECT_EQ(402u, BA2.a().start());
+
+  BA2.advanceTo(411);
+  ASSERT_TRUE(BA2.valid());
+  EXPECT_EQ(410u, BA2.b().start());
+  EXPECT_EQ(402u, BA2.a().start());
 }
 
 } // namespace