1 // Copyright 2018 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #ifndef ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
16 #define ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
17
18 #include "gmock/gmock.h"
19 #include "gtest/gtest.h"
20 #include "absl/container/internal/hash_generator_testing.h"
21 #include "absl/container/internal/hash_policy_testing.h"
22
23 namespace absl {
24 ABSL_NAMESPACE_BEGIN
25 namespace container_internal {
26
27 template <class UnordSet>
28 class ModifiersTest : public ::testing::Test {};
29
30 TYPED_TEST_SUITE_P(ModifiersTest);
31
TYPED_TEST_P(ModifiersTest,Clear)32 TYPED_TEST_P(ModifiersTest, Clear) {
33 using T = hash_internal::GeneratedType<TypeParam>;
34 std::vector<T> values;
35 std::generate_n(std::back_inserter(values), 10,
36 hash_internal::Generator<T>());
37 TypeParam m(values.begin(), values.end());
38 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
39 m.clear();
40 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
41 EXPECT_TRUE(m.empty());
42 }
43
TYPED_TEST_P(ModifiersTest,Insert)44 TYPED_TEST_P(ModifiersTest, Insert) {
45 using T = hash_internal::GeneratedType<TypeParam>;
46 T val = hash_internal::Generator<T>()();
47 TypeParam m;
48 auto p = m.insert(val);
49 EXPECT_TRUE(p.second);
50 EXPECT_EQ(val, *p.first);
51 p = m.insert(val);
52 EXPECT_FALSE(p.second);
53 }
54
TYPED_TEST_P(ModifiersTest,InsertHint)55 TYPED_TEST_P(ModifiersTest, InsertHint) {
56 using T = hash_internal::GeneratedType<TypeParam>;
57 T val = hash_internal::Generator<T>()();
58 TypeParam m;
59 auto it = m.insert(m.end(), val);
60 EXPECT_TRUE(it != m.end());
61 EXPECT_EQ(val, *it);
62 it = m.insert(it, val);
63 EXPECT_TRUE(it != m.end());
64 EXPECT_EQ(val, *it);
65 }
66
TYPED_TEST_P(ModifiersTest,InsertRange)67 TYPED_TEST_P(ModifiersTest, InsertRange) {
68 using T = hash_internal::GeneratedType<TypeParam>;
69 std::vector<T> values;
70 std::generate_n(std::back_inserter(values), 10,
71 hash_internal::Generator<T>());
72 TypeParam m;
73 m.insert(values.begin(), values.end());
74 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
75 }
76
TYPED_TEST_P(ModifiersTest,Emplace)77 TYPED_TEST_P(ModifiersTest, Emplace) {
78 using T = hash_internal::GeneratedType<TypeParam>;
79 T val = hash_internal::Generator<T>()();
80 TypeParam m;
81 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
82 // with test traits/policy.
83 auto p = m.emplace(val);
84 EXPECT_TRUE(p.second);
85 EXPECT_EQ(val, *p.first);
86 p = m.emplace(val);
87 EXPECT_FALSE(p.second);
88 EXPECT_EQ(val, *p.first);
89 }
90
TYPED_TEST_P(ModifiersTest,EmplaceHint)91 TYPED_TEST_P(ModifiersTest, EmplaceHint) {
92 using T = hash_internal::GeneratedType<TypeParam>;
93 T val = hash_internal::Generator<T>()();
94 TypeParam m;
95 // TODO(alkis): We need a way to run emplace in a more meaningful way. Perhaps
96 // with test traits/policy.
97 auto it = m.emplace_hint(m.end(), val);
98 EXPECT_EQ(val, *it);
99 it = m.emplace_hint(it, val);
100 EXPECT_EQ(val, *it);
101 }
102
103 template <class V>
104 using IfNotVoid = typename std::enable_if<!std::is_void<V>::value, V>::type;
105
106 // In openmap we chose not to return the iterator from erase because that's
107 // more expensive. As such we adapt erase to return an iterator here.
108 struct EraseFirst {
109 template <class Map>
110 auto operator()(Map* m, int) const
111 -> IfNotVoid<decltype(m->erase(m->begin()))> {
112 return m->erase(m->begin());
113 }
114 template <class Map>
operatorEraseFirst115 typename Map::iterator operator()(Map* m, ...) const {
116 auto it = m->begin();
117 m->erase(it++);
118 return it;
119 }
120 };
121
TYPED_TEST_P(ModifiersTest,Erase)122 TYPED_TEST_P(ModifiersTest, Erase) {
123 using T = hash_internal::GeneratedType<TypeParam>;
124 std::vector<T> values;
125 std::generate_n(std::back_inserter(values), 10,
126 hash_internal::Generator<T>());
127 TypeParam m(values.begin(), values.end());
128 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
129 std::vector<T> values2;
130 for (const auto& val : values)
131 if (val != *m.begin()) values2.push_back(val);
132 auto it = EraseFirst()(&m, 0);
133 ASSERT_TRUE(it != m.end());
134 EXPECT_EQ(1, std::count(values2.begin(), values2.end(), *it));
135 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values2.begin(),
136 values2.end()));
137 }
138
TYPED_TEST_P(ModifiersTest,EraseRange)139 TYPED_TEST_P(ModifiersTest, EraseRange) {
140 using T = hash_internal::GeneratedType<TypeParam>;
141 std::vector<T> values;
142 std::generate_n(std::back_inserter(values), 10,
143 hash_internal::Generator<T>());
144 TypeParam m(values.begin(), values.end());
145 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
146 auto it = m.erase(m.begin(), m.end());
147 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAre());
148 EXPECT_TRUE(it == m.end());
149 }
150
TYPED_TEST_P(ModifiersTest,EraseKey)151 TYPED_TEST_P(ModifiersTest, EraseKey) {
152 using T = hash_internal::GeneratedType<TypeParam>;
153 std::vector<T> values;
154 std::generate_n(std::back_inserter(values), 10,
155 hash_internal::Generator<T>());
156 TypeParam m(values.begin(), values.end());
157 ASSERT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values));
158 EXPECT_EQ(1, m.erase(values[0]));
159 EXPECT_EQ(0, std::count(m.begin(), m.end(), values[0]));
160 EXPECT_THAT(keys(m), ::testing::UnorderedElementsAreArray(values.begin() + 1,
161 values.end()));
162 }
163
TYPED_TEST_P(ModifiersTest,Swap)164 TYPED_TEST_P(ModifiersTest, Swap) {
165 using T = hash_internal::GeneratedType<TypeParam>;
166 std::vector<T> v1;
167 std::vector<T> v2;
168 std::generate_n(std::back_inserter(v1), 5, hash_internal::Generator<T>());
169 std::generate_n(std::back_inserter(v2), 5, hash_internal::Generator<T>());
170 TypeParam m1(v1.begin(), v1.end());
171 TypeParam m2(v2.begin(), v2.end());
172 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v1));
173 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v2));
174 m1.swap(m2);
175 EXPECT_THAT(keys(m1), ::testing::UnorderedElementsAreArray(v2));
176 EXPECT_THAT(keys(m2), ::testing::UnorderedElementsAreArray(v1));
177 }
178
179 // TODO(alkis): Write tests for extract.
180 // TODO(alkis): Write tests for merge.
181
182 REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint,
183 InsertRange, Emplace, EmplaceHint, Erase, EraseRange,
184 EraseKey, Swap);
185
186 } // namespace container_internal
187 ABSL_NAMESPACE_END
188 } // namespace absl
189
190 #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_
191