Index: third_party/WebKit/Source/wtf/FlatMapTest.cpp |
diff --git a/third_party/WebKit/Source/wtf/FlatMapTest.cpp b/third_party/WebKit/Source/wtf/FlatMapTest.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..0e2034a3b828c83a3d7a876c1a527c3f644f932a |
--- /dev/null |
+++ b/third_party/WebKit/Source/wtf/FlatMapTest.cpp |
@@ -0,0 +1,322 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#include "wtf/FlatMap.h" |
+ |
+#include "testing/gmock/include/gmock/gmock.h" |
+ |
+using testing::ElementsAre; |
+ |
+namespace WTF { |
+ |
+TEST(FlatMapTest, Basic) { |
+ FlatMap<int, int> map; |
+ EXPECT_TRUE(map.empty()); |
+ EXPECT_EQ(0ul, map.size()); |
+} |
+ |
+TEST(FlatMapTest, InsertBasic) { |
+ FlatMap<int, int> map; |
+ |
+ EXPECT_TRUE(map.insert(std::make_pair(1, 2)).second); |
+ EXPECT_FALSE(map.empty()); |
+ EXPECT_EQ(1ul, map.size()); |
+ EXPECT_EQ(2, map.find(1)->second); |
+ |
+ EXPECT_FALSE(map.insert(std::make_pair(1, 3)).second); |
+ EXPECT_EQ(3, map.find(1)->second); |
+} |
+ |
+TEST(FlatMapTest, InsertIncrementing) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(static_cast<size_t>(i), map.size()); |
+ EXPECT_TRUE(map.insert(std::make_pair(i, 100 + i)).second); |
+ } |
+ |
+ EXPECT_EQ(16ul, map.size()); |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(100 + i, map.find(i)->second) << "i = " << i; |
+ } |
+} |
+ |
+TEST(FlatMapTest, InsertDecrementing) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(static_cast<size_t>(i), map.size()); |
+ EXPECT_TRUE(map.insert(std::make_pair(16 - i, 100 + i)).second); |
+ } |
+ |
+ EXPECT_EQ(16ul, map.size()); |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(100 + i, map.find(16 - i)->second) << "i = " << i; |
+ } |
+} |
+ |
+TEST(FlatMapTest, InsertOutsidesIn) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(static_cast<size_t>(i * 2), map.size()); |
+ EXPECT_TRUE(map.insert(std::make_pair(i, 100 + i)).second); |
+ EXPECT_TRUE(map.insert(std::make_pair(32 - i, 200 + i)).second); |
+ } |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(100 + i, map.find(i)->second) << "i = " << i; |
+ EXPECT_EQ(200 + i, map.find(32 - i)->second) << "i = " << i; |
+ } |
+} |
+ |
+TEST(FlatMapTest, InsertOutsidesIn2) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(static_cast<size_t>(i * 2), map.size()); |
+ EXPECT_TRUE(map.insert(std::make_pair(32 - i, 200 + i)).second); |
+ EXPECT_TRUE(map.insert(std::make_pair(i, 100 + i)).second); |
+ } |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(100 + i, map.find(i)->second) << "i = " << i; |
+ EXPECT_EQ(200 + i, map.find(32 - i)->second) << "i = " << i; |
+ } |
+} |
+ |
+TEST(FlatMapTest, Erase) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 50; i++) |
+ map.insertUnique(std::make_pair(i * 2, i * 10)); |
+ |
+ for (size_t i = 49; !map.empty(); i--) { |
+ EXPECT_EQ(i + 1u, map.size()); |
+ ASSERT_EQ(1u, map.erase(i * 2)); |
+ EXPECT_EQ(0u, map.erase(i * 2 + 1)); |
+ } |
+} |
+ |
+TEST(FlatMapTest, EraseOutsideIn) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 16; i++) { |
+ map.insert(std::make_pair(i, 100 + i)); |
+ map.insert(std::make_pair(32 - i, 200 + i)); |
+ } |
+ |
+ for (int i = 0; i < 16; i++) { |
+ EXPECT_EQ(static_cast<size_t>(32 - i * 2), map.size()); |
+ ASSERT_EQ(1u, map.erase(i)) << "i = " << i; |
+ ASSERT_EQ(1u, map.erase(32 - i)) << "i = " << i; |
+ } |
+ |
+ EXPECT_TRUE(map.empty()); |
+} |
+ |
+TEST(FlatMapTest, EraseIterator) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 50; i++) |
+ map.insertUnique(std::make_pair(i * 2, i * 10)); |
+ |
+ for (size_t i = 0; !map.empty(); i++) { |
+ EXPECT_EQ(50ul - i, map.size()); |
+ EXPECT_EQ(static_cast<int>(i * 2), map.begin()->first); |
+ EXPECT_EQ(static_cast<int>(i * 10), map.begin()->second); |
+ EXPECT_EQ(98, map.rbegin()->first); |
+ EXPECT_EQ(490, map.rbegin()->second); |
+ map.erase(map.begin()); |
+ } |
+ |
+ EXPECT_TRUE(map.empty()); |
+} |
+ |
+TEST(FlatMapTest, EraseReverseIterator) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 50; i++) |
+ map.insertUnique(std::make_pair(i * 2, i * 10)); |
+ |
+ for (size_t i = 0; !map.empty(); i++) { |
+ EXPECT_EQ(50ul - i, map.size()); |
+ EXPECT_EQ(0, map.begin()->first); |
+ EXPECT_EQ(0, map.begin()->second); |
+ EXPECT_EQ(static_cast<int>((49 - i) * 2), map.rbegin()->first); |
+ EXPECT_EQ(static_cast<int>((49 - i) * 10), map.rbegin()->second); |
+ map.erase(map.rbegin()); |
+ } |
+ |
+ EXPECT_TRUE(map.empty()); |
+} |
+ |
+TEST(FlatMapTest, EraseNonExistant) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(1, 100)); |
+ EXPECT_EQ(0u, map.erase(2)); |
+} |
+ |
+TEST(FlatMapTest, EraseAllButOneThenInsertOne) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(1, 1)); |
+ map.insert(std::make_pair(2, 2)); |
+ map.insert(std::make_pair(3, 3)); |
+ map.insert(std::make_pair(4, 4)); |
+ map.insert(std::make_pair(5, 5)); |
+ |
+ map.erase(1); |
+ map.erase(2); |
+ map.erase(3); |
+ map.erase(4); |
+ |
+ EXPECT_TRUE(map.find(5) != map.end()); |
+ |
+ map.insert(std::make_pair(6, 6)); |
+ EXPECT_TRUE(map.find(6) != map.end()); |
+} |
+ |
+TEST(FlatMapTest, ChangeKey) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(1, 11)); |
+ map.insert(std::make_pair(3, 33)); |
+ map.insert(std::make_pair(5, 55)); |
+ map.insert(std::make_pair(7, 77)); |
+ map.insert(std::make_pair(9, 99)); |
+ |
+ map.ChangeKey(map.find(7), 2); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(1, 11), std::make_pair(2, 77), |
+ std::make_pair(3, 33), std::make_pair(5, 55), |
+ std::make_pair(9, 99))); |
+ |
+ map.ChangeKey(map.find(2), 0); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(0, 77), std::make_pair(1, 11), |
+ std::make_pair(3, 33), std::make_pair(5, 55), |
+ std::make_pair(9, 99))); |
+ |
+ map.ChangeKey(map.begin(), 10); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(1, 11), std::make_pair(3, 33), |
+ std::make_pair(5, 55), std::make_pair(9, 99), |
+ std::make_pair(10, 77))); |
+} |
+ |
+TEST(FlatMapTest, ChangeKeyReplaceElement) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(1, 11)); |
+ map.insert(std::make_pair(3, 33)); |
+ map.insert(std::make_pair(5, 55)); |
+ map.insert(std::make_pair(7, 77)); |
+ map.insert(std::make_pair(9, 99)); |
+ |
+ map.ChangeKey(map.find(3), 7); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(1, 11), std::make_pair(5, 55), |
+ std::make_pair(7, 33), std::make_pair(9, 99))); |
+} |
+ |
+TEST(FlatMapTest, ChangeKeyUnique) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(1, 11)); |
+ map.insert(std::make_pair(3, 33)); |
+ map.insert(std::make_pair(5, 55)); |
+ map.insert(std::make_pair(7, 77)); |
+ map.insert(std::make_pair(9, 99)); |
+ |
+ map.ChangeKeyUnique(map.find(7), 2); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(1, 11), std::make_pair(2, 77), |
+ std::make_pair(3, 33), std::make_pair(5, 55), |
+ std::make_pair(9, 99))); |
+ |
+ map.ChangeKeyUnique(map.find(2), 0); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(0, 77), std::make_pair(1, 11), |
+ std::make_pair(3, 33), std::make_pair(5, 55), |
+ std::make_pair(9, 99))); |
+ |
+ map.ChangeKeyUnique(map.begin(), 10); |
+ |
+ EXPECT_THAT(map, ElementsAre(std::make_pair(1, 11), std::make_pair(3, 33), |
+ std::make_pair(5, 55), std::make_pair(9, 99), |
+ std::make_pair(10, 77))); |
+} |
+ |
+TEST(FlatMapTest, ChangeKeyUp) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 100; i++) |
+ map.insert(std::make_pair(i, i)); |
+ |
+ for (int i = 0; i < 100; i++) |
+ map.ChangeKey(map.begin(), 100 + i); |
+ |
+ auto it = map.begin(); |
+ for (int i = 0; i < 100; i++, it++) { |
+ EXPECT_EQ(i + 100, it->first); |
+ EXPECT_EQ(i, it->second); |
+ } |
+} |
+ |
+TEST(FlatMapTest, ChangeKeyDown) { |
+ FlatMap<int, int> map; |
+ |
+ for (int i = 0; i < 100; i++) |
+ map.insert(std::make_pair(i, i)); |
+ |
+ for (int i = 0; i < 100; i++) |
+ map.ChangeKey(map.find(i), i - 100); |
+ |
+ auto it = map.begin(); |
+ for (int i = 0; i < 100; i++, it++) { |
+ EXPECT_EQ(i - 100, it->first); |
+ EXPECT_EQ(i, it->second); |
+ } |
+} |
+ |
+TEST(FlatMapTest, Iterators) { |
+ FlatMap<int, int> map; |
+ |
+ map.insert(std::make_pair(5, 55)); |
+ map.insert(std::make_pair(4, 44)); |
+ map.insert(std::make_pair(1, 11)); |
+ map.insert(std::make_pair(6, 66)); |
+ map.insert(std::make_pair(2, 22)); |
+ map.insert(std::make_pair(7, 77)); |
+ map.insert(std::make_pair(3, 33)); |
+ |
+ EXPECT_NE(map.begin(), map.end()); |
+ EXPECT_NE(map.rbegin(), map.rend()); |
+ |
+ auto it = map.begin(); |
+ EXPECT_EQ(std::make_pair(1, 11), *it++); |
+ EXPECT_EQ(std::make_pair(2, 22), *it++); |
+ EXPECT_EQ(std::make_pair(3, 33), *it++); |
+ EXPECT_EQ(std::make_pair(4, 44), *it++); |
+ EXPECT_EQ(std::make_pair(5, 55), *it++); |
+ EXPECT_EQ(std::make_pair(6, 66), *it++); |
+ EXPECT_EQ(std::make_pair(7, 77), *it++); |
+ EXPECT_EQ(map.end(), it); |
+ |
+ auto rit = map.rbegin(); |
+ EXPECT_EQ(std::make_pair(7, 77), *rit++); |
+ EXPECT_EQ(std::make_pair(6, 66), *rit++); |
+ EXPECT_EQ(std::make_pair(5, 55), *rit++); |
+ EXPECT_EQ(std::make_pair(4, 44), *rit++); |
+ EXPECT_EQ(std::make_pair(3, 33), *rit++); |
+ EXPECT_EQ(std::make_pair(2, 22), *rit++); |
+ EXPECT_EQ(std::make_pair(1, 11), *rit++); |
+ EXPECT_EQ(map.rend(), rit); |
+} |
+ |
+} // namespace WTF |