Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/FlatSetTest.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/FlatSet.h"
+
+#include "testing/gmock/include/gmock/gmock.h"
+
+using testing::ElementsAre;
+
+namespace WTF {
+
+TEST(FlatSetTest, Basic) {
+  FlatSet<int> set;
+  EXPECT_TRUE(set.empty());
+  EXPECT_EQ(0ul, set.size());
+}
+
+TEST(FlatSetTest, InsertBasic) {
+  FlatSet<int> set;
+
+  EXPECT_TRUE(set.insert(1).second);
+  EXPECT_FALSE(set.empty());
+  EXPECT_EQ(1ul, set.size());
+  EXPECT_EQ(1, *set.find(1));
+
+  EXPECT_FALSE(set.insert(1).second);
+}
+
+TEST(FlatSetTest, InsertAndFind) {
+  FlatSet<int> set;
+
+  for (int i = 0; i < 50; i++)
+    set.insert(i * 2);
+
+  EXPECT_EQ(50ul, set.size());
+
+  for (int i = 0; i < 50; i++) {
+    EXPECT_TRUE(set.find(i * 2) != set.end()) << "i = " << i;
+    EXPECT_FALSE(set.find(i * 2 + 1) != set.end()) << "i = " << i;
+  }
+}
+
+TEST(FlatSetTest, InsertUniqueAndFind) {
+  FlatSet<int> set;
+
+  for (int i = 0; i < 50; i++)
+    set.insertUnique(i * 2);
+
+  EXPECT_EQ(50ul, set.size());
+
+  for (int i = 0; i < 50; i++) {
+    EXPECT_TRUE(set.find(i * 2) != set.end()) << "i = " << i;
+    EXPECT_FALSE(set.find(i * 2 + 1) != set.end()) << "i = " << i;
+  }
+}
+
+TEST(FlatSetTest, EraseIterator) {
+  FlatSet<int> set;
+
+  for (int i = 0; i < 50; i++)
+    set.insertUnique(i * 2);
+
+  for (size_t i = 0; !set.empty(); i++) {
+    EXPECT_EQ(50ul - i, set.size());
+    EXPECT_EQ(static_cast<int>(i * 2), *set.begin());
+    EXPECT_EQ(98, *set.rbegin());
+    set.erase(set.begin());
+  }
+}
+
+TEST(FlatSetTest, EraseReverseIterator) {
+  FlatSet<int> set;
+
+  for (int i = 0; i < 50; i++)
+    set.insertUnique(i * 2);
+
+  for (size_t i = 0; !set.empty(); i++) {
+    EXPECT_EQ(50ul - i, set.size());
+    EXPECT_EQ(0, *set.begin());
+    EXPECT_EQ(static_cast<int>((49 - i) * 2), *set.rbegin());
+    set.erase(set.rbegin());
+  }
+
+  EXPECT_TRUE(set.empty());
+}
+
+TEST(FlatSetTest, Iterators) {
+  FlatSet<int> set;
+
+  set.insert(5);
+  set.insert(4);
+  set.insert(1);
+  set.insert(6);
+  set.insert(2);
+  set.insert(7);
+  set.insert(3);
+
+  EXPECT_NE(set.begin(), set.end());
+  EXPECT_NE(set.rbegin(), set.rend());
+
+  auto it = set.begin();
+  EXPECT_EQ(1, *it++);
+  EXPECT_EQ(2, *it++);
+  EXPECT_EQ(3, *it++);
+  EXPECT_EQ(4, *it++);
+  EXPECT_EQ(5, *it++);
+  EXPECT_EQ(6, *it++);
+  EXPECT_EQ(7, *it++);
+  EXPECT_EQ(set.end(), it);
+
+  auto rit = set.rbegin();
+  EXPECT_EQ(7, *rit++);
+  EXPECT_EQ(6, *rit++);
+  EXPECT_EQ(5, *rit++);
+  EXPECT_EQ(4, *rit++);
+  EXPECT_EQ(3, *rit++);
+  EXPECT_EQ(2, *rit++);
+  EXPECT_EQ(1, *rit++);
+  EXPECT_EQ(set.rend(), rit);
+}
+
+TEST(FlatSetTest, Bug) {
+  FlatSet<int> set;
+
+  for (int i = 0; i < 8; i++)
+    EXPECT_TRUE(set.insert(i).second);
+
+  for (int i = 0; i < 8; i++) {
+    set.erase(set.begin());
+    EXPECT_TRUE(set.insert(10 + i).second);
+  }
+
+  int first = *set.begin();
+  set.erase(set.begin());
+  EXPECT_TRUE(set.insert(first).second);
+  // EXPECT_EQ(set.find(first), set.end());
+}
+
+}  // namespace WTF