namespace {
-typedef IntervalMap<unsigned, unsigned> UUMap;
-typedef IntervalMap<unsigned, unsigned, 4> UU4Map;
+typedef IntervalMap<unsigned, unsigned, 4> UUMap;
// Empty map tests
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
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.
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;
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.
++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]
++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;
- EXPECT_FALSE(I.valid());
-
- // 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();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(100u, I.start());
- EXPECT_EQ(210u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(220u, I.start());
- EXPECT_EQ(230u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
- // Overwrite 2 from gap to gap.
- // [100;210] [220;230]
- map.insert(50, 250, 1);
- I = map.begin();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(50u, I.start());
- EXPECT_EQ(250u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
- // 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();
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(50u, I.start());
- EXPECT_EQ(250u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(260u, I.start());
- EXPECT_EQ(270u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(280u, I.start());
- EXPECT_EQ(290u, I.stop());
- ++I;
- ASSERT_TRUE(I.valid());
- EXPECT_EQ(300u, I.start());
- EXPECT_EQ(320u, I.stop());
- ++I;
- EXPECT_FALSE(I.valid());
-
// Test clear() on non-branched map.
map.clear();
EXPECT_TRUE(map.empty());
// 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)
+ 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_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());
+
+ // Change value, no coalescing.
+ I.setValue(0);
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(20u, I.start());
+ EXPECT_EQ(25u, I.stop());
+ EXPECT_EQ(0u, I.value());
+
+ // Close the gap right, no coalescing.
+ I.setStop(29);
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(20u, I.start());
+ EXPECT_EQ(29u, I.stop());
+ EXPECT_EQ(0u, I.value());
+
+ // Change value, no coalescing.
+ I.setValue(2);
+ ASSERT_TRUE(I.valid());
+ 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(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());
+ I.setStop(39);
+ ASSERT_TRUE(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());
// Branched, high, non-coalescing tests.
TEST(IntervalMapTest, Branched2) {
- UU4Map::Allocator allocator;
- UU4Map map(allocator);
+ UUMap::Allocator allocator;
+ UUMap map(allocator);
// Insert enough intervals to force a height >= 2 tree.
for (unsigned i = 1; i < 1000; ++i)
}
// Forward iteration.
- UU4Map::iterator I = map.begin();
+ UUMap::iterator I = map.begin();
for (unsigned i = 1; i < 1000; ++i) {
ASSERT_TRUE(I.valid());
EXPECT_EQ(10*i, I.start());
}
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());
// Random insertions, coalescing to a single interval.
TEST(IntervalMapTest, RandomCoalescing) {
- UU4Map::Allocator allocator;
- UU4Map map(allocator);
+ UUMap::Allocator allocator;
+ UUMap map(allocator);
// This is a poor PRNG with maximal period:
// x_n = 5 x_{n-1} + 1 mod 2^N
}
+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
projects / oota-llvm.git / blobdiff