Implement const_iterator::advanceTo().
This is a version of find() that always searches forwards and is faster for
local searches.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@120237 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/unittests/ADT/IntervalMapTest.cpp b/unittests/ADT/IntervalMapTest.cpp
index 4664650..f4b1ebc 100644
--- a/unittests/ADT/IntervalMapTest.cpp
+++ b/unittests/ADT/IntervalMapTest.cpp
@@ -206,6 +206,17 @@
++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());
// Coalesce left with followers.
// [100;110] [120;130] [140;150] [160;170]
@@ -387,7 +398,20 @@
}
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 another node.
+ I.advanceTo(200);
+ ASSERT_TRUE(I.valid());
+ EXPECT_EQ(200u, I.start());
+ EXPECT_EQ(205u, I.stop());
+
// Erase from the front.
+ I = map.begin();
for (unsigned i = 0; i != 20; ++i) {
I.erase();
EXPECT_TRUE(I == map.begin());
@@ -446,6 +470,24 @@
}
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());
+
// Test clear() on branched map.
map.clear();
EXPECT_TRUE(map.empty());