Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatMapTest.cpp

+// 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