OLD | NEW |
1 // Copyright 2017 The Chromium Authors. All rights reserved. | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "base/containers/flat_set.h" | 5 #include "base/containers/flat_tree.h" |
6 | 6 |
7 // Following tests are ported and extended tests from libcpp for std::set. | 7 // Following tests are ported and extended tests from libcpp for std::set. |
8 // They can be found here: | 8 // They can be found here: |
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa
tive/set | 9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associa
tive/set |
10 // | 10 // |
11 // Not ported tests: | 11 // Not ported tests: |
12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T> | 12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T> |
13 // These tests have to do with C++14 std::less<> | 13 // These tests have to do with C++14 std::less<> |
14 // http://en.cppreference.com/w/cpp/utility/functional/less_void | 14 // http://en.cppreference.com/w/cpp/utility/functional/less_void |
15 // and add support for templated versions of lookup functions. | 15 // and add support for templated versions of lookup functions. |
(...skipping 14 matching lines...) Expand all Loading... |
30 // equal. Currently we use std::vector iterators and they don't implement | 30 // equal. Currently we use std::vector iterators and they don't implement |
31 // this. | 31 // this. |
32 // * No tests with min_allocator and no tests counting allocations. | 32 // * No tests with min_allocator and no tests counting allocations. |
33 // Flat sets currently don't support allocators. | 33 // Flat sets currently don't support allocators. |
34 // * No tests for range insertion. Flat sets currently do not support this | 34 // * No tests for range insertion. Flat sets currently do not support this |
35 // functionality. | 35 // functionality. |
36 | 36 |
37 #include <string> | 37 #include <string> |
38 #include <vector> | 38 #include <vector> |
39 | 39 |
| 40 #include "base/containers/container_test_utils.h" |
40 #include "base/macros.h" | 41 #include "base/macros.h" |
41 #include "testing/gmock/include/gmock/gmock.h" | 42 #include "testing/gmock/include/gmock/gmock.h" |
42 #include "testing/gtest/include/gtest/gtest.h" | 43 #include "testing/gtest/include/gtest/gtest.h" |
43 | 44 |
| 45 namespace base { |
| 46 namespace internal { |
| 47 |
44 namespace { | 48 namespace { |
45 | 49 |
46 class MoveOnly { | |
47 public: | |
48 explicit MoveOnly(int data = 1) : data_(data) {} | |
49 MoveOnly(MoveOnly&& other) : data_(other.data_) { other.data_ = 0; } | |
50 MoveOnly& operator=(MoveOnly&& other) { | |
51 data_ = other.data_; | |
52 other.data_ = 0; | |
53 return *this; | |
54 } | |
55 | |
56 friend bool operator<(const MoveOnly& lhs, const MoveOnly& rhs) { | |
57 return lhs.data_ < rhs.data_; | |
58 } | |
59 | |
60 int data() const { return data_; } | |
61 | |
62 private: | |
63 int data_; | |
64 | |
65 DISALLOW_COPY_AND_ASSIGN(MoveOnly); | |
66 }; | |
67 | |
68 template <class It> | 50 template <class It> |
69 class InputIterator { | 51 class InputIterator { |
70 public: | 52 public: |
71 using iterator_category = std::input_iterator_tag; | 53 using iterator_category = std::input_iterator_tag; |
72 using value_type = typename std::iterator_traits<It>::value_type; | 54 using value_type = typename std::iterator_traits<It>::value_type; |
73 using difference_type = typename std::iterator_traits<It>::difference_type; | 55 using difference_type = typename std::iterator_traits<It>::difference_type; |
74 using pointer = It; | 56 using pointer = It; |
75 using reference = typename std::iterator_traits<It>::reference; | 57 using reference = typename std::iterator_traits<It>::reference; |
76 | 58 |
77 InputIterator() : it_() {} | 59 InputIterator() : it_() {} |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
136 double double_; | 118 double double_; |
137 | 119 |
138 DISALLOW_COPY_AND_ASSIGN(Emplaceable); | 120 DISALLOW_COPY_AND_ASSIGN(Emplaceable); |
139 }; | 121 }; |
140 | 122 |
141 class NonDefaultConstructibleCompare { | 123 class NonDefaultConstructibleCompare { |
142 public: | 124 public: |
143 explicit NonDefaultConstructibleCompare(int) {} | 125 explicit NonDefaultConstructibleCompare(int) {} |
144 | 126 |
145 template <typename T> | 127 template <typename T> |
146 bool operator()(const T& lhs, const T& rhs) { | 128 bool operator()(const T& lhs, const T& rhs) const { |
147 return std::less<T>()(lhs, rhs); | 129 return std::less<T>()(lhs, rhs); |
148 } | 130 } |
149 }; | 131 }; |
150 | 132 |
151 // Common test sets. | 133 // Common test trees. |
152 using IntSet = base::flat_set<int>; | |
153 using MoveOnlySet = base::flat_set<MoveOnly>; | |
154 using EmplaceableSet = base::flat_set<Emplaceable>; | |
155 using ReversedSet = base::flat_set<int, std::greater<int>>; | |
156 | 134 |
157 // TODO(dyaroshev): replace less<int> with less<>, once we have it | 135 // TODO(dyaroshev): replace less<int> with less<>, once we have it |
158 // crbug.com/682254. | 136 // crbug.com/682254. This will make it different than IntTree. |
159 using SetWithLess = base::flat_set<int, std::less<int>>; | 137 using IntTreeWithLess = |
| 138 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; |
| 139 using IntTree = |
| 140 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; |
| 141 using MoveOnlyTree = flat_tree<MoveOnlyInt, |
| 142 MoveOnlyInt, |
| 143 GetKeyFromValueIdentity<MoveOnlyInt>, |
| 144 std::less<MoveOnlyInt>>; |
| 145 using EmplaceableTree = flat_tree<Emplaceable, |
| 146 Emplaceable, |
| 147 GetKeyFromValueIdentity<Emplaceable>, |
| 148 std::less<Emplaceable>>; |
| 149 using ReversedTree = |
| 150 flat_tree<int, int, GetKeyFromValueIdentity<int>, std::greater<int>>; |
160 | 151 |
161 using SetWithStrangeCompare = | 152 using TreeWithStrangeCompare = flat_tree<int, |
162 base::flat_set<int, NonDefaultConstructibleCompare>; | 153 int, |
| 154 GetKeyFromValueIdentity<int>, |
| 155 NonDefaultConstructibleCompare>; |
163 | 156 |
164 using ::testing::ElementsAre; | 157 using ::testing::ElementsAre; |
165 | 158 |
166 } // namespace | 159 } // namespace |
167 | 160 |
168 // ---------------------------------------------------------------------------- | 161 // ---------------------------------------------------------------------------- |
169 // Class. | 162 // Class. |
170 | 163 |
171 // Check that base::flat_set and its iterators can be instantiated with an | 164 // Check that flat_tree and its iterators can be instantiated with an |
172 // incomplete type. | 165 // incomplete type. |
173 | 166 |
174 TEST(FlatSet, IncompleteType) { | 167 TEST(FlatTree, IncompleteType) { |
175 struct A { | 168 struct A { |
176 using Set = base::flat_set<A>; | 169 using Tree = flat_tree<A, A, GetKeyFromValueIdentity<A>, std::less<A>>; |
177 int data; | 170 int data; |
178 Set set_with_incomplete_type; | 171 Tree set_with_incomplete_type; |
179 Set::iterator it; | 172 Tree::iterator it; |
180 Set::const_iterator cit; | 173 Tree::const_iterator cit; |
181 | 174 |
182 // We do not declare operator< because clang complains that it's unused. | 175 // We do not declare operator< because clang complains that it's unused. |
183 }; | 176 }; |
184 | 177 |
185 A a; | 178 A a; |
186 } | 179 } |
187 | 180 |
188 TEST(FlatSet, Stability) { | 181 TEST(FlatTree, Stability) { |
189 using Pair = std::pair<int, int>; | 182 using Pair = std::pair<int, int>; |
190 | 183 |
191 struct LessByFirst { | 184 struct LessByFirst { |
192 bool operator()(const Pair& lhs, const Pair& rhs) { | 185 bool operator()(const Pair& lhs, const Pair& rhs) const { |
193 return lhs.first < rhs.first; | 186 return lhs.first < rhs.first; |
194 } | 187 } |
195 }; | 188 }; |
196 | 189 |
197 using Set = base::flat_set<Pair, LessByFirst>; | 190 using Tree = |
| 191 flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>; |
198 | 192 |
199 // Constructors are not stable. | 193 // Constructors are not stable. |
200 Set cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; | 194 Tree cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; |
201 | 195 |
202 auto NoneOfSecondsAreTwo = [&cont] { | 196 auto NoneOfSecondsAreTwo = [&cont] { |
203 return std::none_of(cont.begin(), cont.end(), | 197 return std::none_of(cont.begin(), cont.end(), |
204 [](const Pair& elem) { return elem.second == 2; }); | 198 [](const Pair& elem) { return elem.second == 2; }); |
205 }; | 199 }; |
206 | 200 |
207 // Should not replace existing. | 201 // Should not replace existing. |
208 cont.insert(Pair(0, 2)); | 202 cont.insert(Pair(0, 2)); |
209 cont.insert(Pair(1, 2)); | 203 cont.insert(Pair(1, 2)); |
210 cont.insert(Pair(2, 2)); | 204 cont.insert(Pair(2, 2)); |
(...skipping 19 matching lines...) Expand all Loading... |
230 // const_pointer | 224 // const_pointer |
231 // reference | 225 // reference |
232 // const_reference | 226 // const_reference |
233 // size_type | 227 // size_type |
234 // difference_type | 228 // difference_type |
235 // iterator | 229 // iterator |
236 // const_iterator | 230 // const_iterator |
237 // reverse_iterator | 231 // reverse_iterator |
238 // const_reverse_iterator | 232 // const_reverse_iterator |
239 | 233 |
240 TEST(FlatSet, Types) { | 234 TEST(FlatTree, Types) { |
241 // These are guaranteed to be portable. | 235 // These are guaranteed to be portable. |
242 static_assert((std::is_same<int, IntSet::key_type>::value), ""); | 236 static_assert((std::is_same<int, IntTree::key_type>::value), ""); |
243 static_assert((std::is_same<int, IntSet::value_type>::value), ""); | 237 static_assert((std::is_same<int, IntTree::value_type>::value), ""); |
244 static_assert((std::is_same<std::less<int>, IntSet::key_compare>::value), ""); | 238 static_assert((std::is_same<std::less<int>, IntTree::key_compare>::value), |
245 static_assert((std::is_same<std::less<int>, IntSet::value_compare>::value), | |
246 ""); | 239 ""); |
247 static_assert((std::is_same<int&, IntSet::reference>::value), ""); | 240 static_assert((std::is_same<int&, IntTree::reference>::value), ""); |
248 static_assert((std::is_same<const int&, IntSet::const_reference>::value), ""); | 241 static_assert((std::is_same<const int&, IntTree::const_reference>::value), |
249 static_assert((std::is_same<int*, IntSet::pointer>::value), ""); | 242 ""); |
250 static_assert((std::is_same<const int*, IntSet::const_pointer>::value), ""); | 243 static_assert((std::is_same<int*, IntTree::pointer>::value), ""); |
| 244 static_assert((std::is_same<const int*, IntTree::const_pointer>::value), ""); |
251 } | 245 } |
252 | 246 |
253 // ---------------------------------------------------------------------------- | 247 // ---------------------------------------------------------------------------- |
254 // Lifetime. | 248 // Lifetime. |
255 | 249 |
256 // flat_set() | 250 // flat_tree() |
257 // flat_set(const Compare& comp) | 251 // flat_tree(const Compare& comp) |
258 | 252 |
259 TEST(FlatSet, DefaultConstructor) { | 253 TEST(FlatTree, DefaultConstructor) { |
260 { | 254 { |
261 IntSet cont; | 255 IntTree cont; |
262 EXPECT_THAT(cont, ElementsAre()); | 256 EXPECT_THAT(cont, ElementsAre()); |
263 } | 257 } |
264 | 258 |
265 { | 259 { |
266 SetWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); | 260 TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); |
267 EXPECT_THAT(cont, ElementsAre()); | 261 EXPECT_THAT(cont, ElementsAre()); |
268 } | 262 } |
269 } | 263 } |
270 | 264 |
271 // flat_set(InputIterator first, | 265 // flat_tree(InputIterator first, |
272 // InputIterator last, | 266 // InputIterator last, |
273 // const Compare& comp = Compare()) | 267 // const Compare& comp = Compare()) |
274 | 268 |
275 TEST(FlatSet, RangeConstructor) { | 269 TEST(FlatTree, RangeConstructor) { |
276 { | 270 { |
277 IntSet::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; | 271 IntTree::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; |
278 | 272 |
279 IntSet cont(MakeInputIterator(std::begin(input_vals)), | 273 IntTree cont(MakeInputIterator(std::begin(input_vals)), |
280 MakeInputIterator(std::end(input_vals))); | 274 MakeInputIterator(std::end(input_vals))); |
281 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); | 275 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); |
282 } | 276 } |
283 { | 277 { |
284 SetWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, | 278 TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, |
285 2, 3, 3, 3}; | 279 2, 3, 3, 3}; |
286 | 280 |
287 SetWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), | 281 TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), |
288 MakeInputIterator(std::end(input_vals)), | 282 MakeInputIterator(std::end(input_vals)), |
289 NonDefaultConstructibleCompare(0)); | 283 NonDefaultConstructibleCompare(0)); |
290 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); | 284 EXPECT_THAT(cont, ElementsAre(1, 2, 3)); |
291 } | 285 } |
292 } | 286 } |
293 | 287 |
294 // flat_set(const flat_set& x) | 288 // flat_tree(const flat_tree& x) |
295 | 289 |
296 TEST(FlatSet, CopyConstructor) { | 290 TEST(FlatTree, CopyConstructor) { |
297 IntSet original{1, 2, 3, 4}; | 291 IntTree original{1, 2, 3, 4}; |
298 IntSet copied(original); | 292 IntTree copied(original); |
299 | 293 |
300 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | 294 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); |
301 | 295 |
302 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | 296 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); |
303 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); | 297 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); |
304 EXPECT_EQ(original, copied); | 298 EXPECT_EQ(original, copied); |
305 } | 299 } |
306 | 300 |
307 // flat_set(flat_set&& x) | 301 // flat_tree(flat_tree&& x) |
308 | 302 |
309 TEST(FlatSet, MoveConstructor) { | 303 TEST(FlatTree, MoveConstructor) { |
310 int input_range[] = {1, 2, 3, 4}; | 304 int input_range[] = {1, 2, 3, 4}; |
311 | 305 |
312 MoveOnlySet original(std::begin(input_range), std::end(input_range)); | 306 MoveOnlyTree original(std::begin(input_range), std::end(input_range)); |
313 MoveOnlySet moved(std::move(original)); | 307 MoveOnlyTree moved(std::move(original)); |
314 | 308 |
315 EXPECT_EQ(1U, moved.count(MoveOnly(1))); | 309 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); |
316 EXPECT_EQ(1U, moved.count(MoveOnly(2))); | 310 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); |
317 EXPECT_EQ(1U, moved.count(MoveOnly(3))); | 311 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); |
318 EXPECT_EQ(1U, moved.count(MoveOnly(4))); | 312 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); |
319 } | 313 } |
320 | 314 |
321 // flat_set(std::initializer_list<value_type> ilist, | 315 // flat_tree(std::initializer_list<value_type> ilist, |
322 // const Compare& comp = Compare()) | 316 // const Compare& comp = Compare()) |
323 | 317 |
324 TEST(FlatSet, InitializerListConstructor) { | 318 TEST(FlatTree, InitializerListConstructor) { |
325 { | 319 { |
326 IntSet cont{1, 2, 3, 4, 5, 6, 10, 8}; | 320 IntTree cont{1, 2, 3, 4, 5, 6, 10, 8}; |
327 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | 321 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
328 } | 322 } |
329 { | 323 { |
330 SetWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, | 324 TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, |
331 NonDefaultConstructibleCompare(0)); | 325 NonDefaultConstructibleCompare(0)); |
332 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | 326 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
333 } | 327 } |
334 } | 328 } |
335 | 329 |
336 // ---------------------------------------------------------------------------- | 330 // ---------------------------------------------------------------------------- |
337 // Assignments. | 331 // Assignments. |
338 | 332 |
339 // flat_set& operator=(const flat_set&) | 333 // flat_tree& operator=(const flat_tree&) |
340 | 334 |
341 TEST(FlatSet, CopyAssignable) { | 335 TEST(FlatTree, CopyAssignable) { |
342 IntSet original{1, 2, 3, 4}; | 336 IntTree original{1, 2, 3, 4}; |
343 IntSet copied; | 337 IntTree copied; |
344 copied = original; | 338 copied = original; |
345 | 339 |
346 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); | 340 EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); |
347 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); | 341 EXPECT_THAT(original, ElementsAre(1, 2, 3, 4)); |
348 EXPECT_EQ(original, copied); | 342 EXPECT_EQ(original, copied); |
349 } | 343 } |
350 | 344 |
351 // flat_set& operator=(flat_set&&) | 345 // flat_tree& operator=(flat_tree&&) |
352 | 346 |
353 TEST(FlatSet, MoveAssignable) { | 347 TEST(FlatTree, MoveAssignable) { |
354 int input_range[] = {1, 2, 3, 4}; | 348 int input_range[] = {1, 2, 3, 4}; |
355 | 349 |
356 MoveOnlySet original(std::begin(input_range), std::end(input_range)); | 350 MoveOnlyTree original(std::begin(input_range), std::end(input_range)); |
357 MoveOnlySet moved; | 351 MoveOnlyTree moved; |
358 moved = std::move(original); | 352 moved = std::move(original); |
359 | 353 |
360 EXPECT_EQ(1U, moved.count(MoveOnly(1))); | 354 EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); |
361 EXPECT_EQ(1U, moved.count(MoveOnly(2))); | 355 EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); |
362 EXPECT_EQ(1U, moved.count(MoveOnly(3))); | 356 EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); |
363 EXPECT_EQ(1U, moved.count(MoveOnly(4))); | 357 EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); |
364 } | 358 } |
365 | 359 |
366 // flat_set& operator=(std::initializer_list<value_type> ilist) | 360 // flat_tree& operator=(std::initializer_list<value_type> ilist) |
367 | 361 |
368 TEST(FlatSet, InitializerListAssignable) { | 362 TEST(FlatTree, InitializerListAssignable) { |
369 IntSet cont{0}; | 363 IntTree cont{0}; |
370 cont = {1, 2, 3, 4, 5, 6, 10, 8}; | 364 cont = {1, 2, 3, 4, 5, 6, 10, 8}; |
371 | 365 |
372 EXPECT_EQ(0U, cont.count(0)); | 366 EXPECT_EQ(0U, cont.count(0)); |
373 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); | 367 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
374 } | 368 } |
375 | 369 |
376 // -------------------------------------------------------------------------- | 370 // -------------------------------------------------------------------------- |
377 // Memory management. | 371 // Memory management. |
378 | 372 |
379 // void reserve(size_type new_capacity) | 373 // void reserve(size_type new_capacity) |
380 | 374 |
381 TEST(FlatSet, Reserve) { | 375 TEST(FlatTree, Reserve) { |
382 IntSet cont{1, 2, 3}; | 376 IntTree cont{1, 2, 3}; |
383 | 377 |
384 cont.reserve(5); | 378 cont.reserve(5); |
385 EXPECT_LE(5U, cont.capacity()); | 379 EXPECT_LE(5U, cont.capacity()); |
386 } | 380 } |
387 | 381 |
388 // size_type capacity() const | 382 // size_type capacity() const |
389 | 383 |
390 TEST(FlatSet, Capacity) { | 384 TEST(FlatTree, Capacity) { |
391 IntSet cont{1, 2, 3}; | 385 IntTree cont{1, 2, 3}; |
392 | 386 |
393 EXPECT_LE(cont.size(), cont.capacity()); | 387 EXPECT_LE(cont.size(), cont.capacity()); |
394 cont.reserve(5); | 388 cont.reserve(5); |
395 EXPECT_LE(cont.size(), cont.capacity()); | 389 EXPECT_LE(cont.size(), cont.capacity()); |
396 } | 390 } |
397 | 391 |
398 // void shrink_to_fit() | 392 // void shrink_to_fit() |
399 | 393 |
400 TEST(FlatSet, ShrinkToFit) { | 394 TEST(FlatTree, ShrinkToFit) { |
401 IntSet cont{1, 2, 3}; | 395 IntTree cont{1, 2, 3}; |
402 | 396 |
403 IntSet::size_type capacity_before = cont.capacity(); | 397 IntTree::size_type capacity_before = cont.capacity(); |
404 cont.shrink_to_fit(); | 398 cont.shrink_to_fit(); |
405 EXPECT_GE(capacity_before, cont.capacity()); | 399 EXPECT_GE(capacity_before, cont.capacity()); |
406 } | 400 } |
407 | 401 |
408 // ---------------------------------------------------------------------------- | 402 // ---------------------------------------------------------------------------- |
409 // Size management. | 403 // Size management. |
410 | 404 |
411 // void clear() | 405 // void clear() |
412 | 406 |
413 TEST(FlatSet, Clear) { | 407 TEST(FlatTree, Clear) { |
414 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | 408 IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
415 cont.clear(); | 409 cont.clear(); |
416 EXPECT_THAT(cont, ElementsAre()); | 410 EXPECT_THAT(cont, ElementsAre()); |
417 } | 411 } |
418 | 412 |
419 // size_type size() const | 413 // size_type size() const |
420 | 414 |
421 TEST(FlatSet, Size) { | 415 TEST(FlatTree, Size) { |
422 IntSet cont; | 416 IntTree cont; |
423 | 417 |
424 EXPECT_EQ(0U, cont.size()); | 418 EXPECT_EQ(0U, cont.size()); |
425 cont.insert(2); | 419 cont.insert(2); |
426 EXPECT_EQ(1U, cont.size()); | 420 EXPECT_EQ(1U, cont.size()); |
427 cont.insert(1); | 421 cont.insert(1); |
428 EXPECT_EQ(2U, cont.size()); | 422 EXPECT_EQ(2U, cont.size()); |
429 cont.insert(3); | 423 cont.insert(3); |
430 EXPECT_EQ(3U, cont.size()); | 424 EXPECT_EQ(3U, cont.size()); |
431 cont.erase(cont.begin()); | 425 cont.erase(cont.begin()); |
432 EXPECT_EQ(2U, cont.size()); | 426 EXPECT_EQ(2U, cont.size()); |
433 cont.erase(cont.begin()); | 427 cont.erase(cont.begin()); |
434 EXPECT_EQ(1U, cont.size()); | 428 EXPECT_EQ(1U, cont.size()); |
435 cont.erase(cont.begin()); | 429 cont.erase(cont.begin()); |
436 EXPECT_EQ(0U, cont.size()); | 430 EXPECT_EQ(0U, cont.size()); |
437 } | 431 } |
438 | 432 |
439 // bool empty() const | 433 // bool empty() const |
440 | 434 |
441 TEST(FlatSet, Empty) { | 435 TEST(FlatTree, Empty) { |
442 IntSet cont; | 436 IntTree cont; |
443 | 437 |
444 EXPECT_TRUE(cont.empty()); | 438 EXPECT_TRUE(cont.empty()); |
445 cont.insert(1); | 439 cont.insert(1); |
446 EXPECT_FALSE(cont.empty()); | 440 EXPECT_FALSE(cont.empty()); |
447 cont.clear(); | 441 cont.clear(); |
448 EXPECT_TRUE(cont.empty()); | 442 EXPECT_TRUE(cont.empty()); |
449 } | 443 } |
450 | 444 |
451 // ---------------------------------------------------------------------------- | 445 // ---------------------------------------------------------------------------- |
452 // Iterators. | 446 // Iterators. |
453 | 447 |
454 // iterator begin() | 448 // iterator begin() |
455 // const_iterator begin() const | 449 // const_iterator begin() const |
456 // iterator end() | 450 // iterator end() |
457 // const_iterator end() const | 451 // const_iterator end() const |
458 // | 452 // |
459 // reverse_iterator rbegin() | 453 // reverse_iterator rbegin() |
460 // const_reverse_iterator rbegin() const | 454 // const_reverse_iterator rbegin() const |
461 // reverse_iterator rend() | 455 // reverse_iterator rend() |
462 // const_reverse_iterator rend() const | 456 // const_reverse_iterator rend() const |
463 // | 457 // |
464 // const_iterator cbegin() const | 458 // const_iterator cbegin() const |
465 // const_iterator cend() const | 459 // const_iterator cend() const |
466 // const_reverse_iterator crbegin() const | 460 // const_reverse_iterator crbegin() const |
467 // const_reverse_iterator crend() const | 461 // const_reverse_iterator crend() const |
468 | 462 |
469 TEST(FlatSet, Iterators) { | 463 TEST(FlatTree, Iterators) { |
470 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | 464 IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
471 | 465 |
472 auto size = static_cast<IntSet::difference_type>(cont.size()); | 466 auto size = static_cast<IntTree::difference_type>(cont.size()); |
473 | 467 |
474 EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); | 468 EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); |
475 EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); | 469 EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); |
476 EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend())); | 470 EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend())); |
477 EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); | 471 EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); |
478 | 472 |
479 { | 473 { |
480 IntSet::iterator it = cont.begin(); | 474 IntTree::iterator it = cont.begin(); |
481 IntSet::const_iterator c_it = cont.cbegin(); | 475 IntTree::const_iterator c_it = cont.cbegin(); |
482 EXPECT_EQ(it, c_it); | 476 EXPECT_EQ(it, c_it); |
483 for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { | 477 for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { |
484 EXPECT_EQ(j, *it); | 478 EXPECT_EQ(j, *it); |
485 EXPECT_EQ(j, *c_it); | 479 EXPECT_EQ(j, *c_it); |
486 } | 480 } |
487 } | 481 } |
488 { | 482 { |
489 IntSet::reverse_iterator rit = cont.rbegin(); | 483 IntTree::reverse_iterator rit = cont.rbegin(); |
490 IntSet::const_reverse_iterator c_rit = cont.crbegin(); | 484 IntTree::const_reverse_iterator c_rit = cont.crbegin(); |
491 EXPECT_EQ(rit, c_rit); | 485 EXPECT_EQ(rit, c_rit); |
492 for (int j = static_cast<int>(size); rit != cont.rend(); | 486 for (int j = static_cast<int>(size); rit != cont.rend(); |
493 ++rit, ++c_rit, --j) { | 487 ++rit, ++c_rit, --j) { |
494 EXPECT_EQ(j, *rit); | 488 EXPECT_EQ(j, *rit); |
495 EXPECT_EQ(j, *c_rit); | 489 EXPECT_EQ(j, *c_rit); |
496 } | 490 } |
497 } | 491 } |
498 } | 492 } |
499 | 493 |
500 // ---------------------------------------------------------------------------- | 494 // ---------------------------------------------------------------------------- |
501 // Insert operations. | 495 // Insert operations. |
502 | 496 |
503 // pair<iterator, bool> insert(const value_type& val) | 497 // pair<iterator, bool> insert(const value_type& val) |
504 | 498 |
505 TEST(FlatSet, InsertLValue) { | 499 TEST(FlatTree, InsertLValue) { |
506 IntSet cont; | 500 IntTree cont; |
507 | 501 |
508 int value = 2; | 502 int value = 2; |
509 std::pair<IntSet::iterator, bool> result = cont.insert(value); | 503 std::pair<IntTree::iterator, bool> result = cont.insert(value); |
510 EXPECT_TRUE(result.second); | 504 EXPECT_TRUE(result.second); |
511 EXPECT_EQ(cont.begin(), result.first); | 505 EXPECT_EQ(cont.begin(), result.first); |
512 EXPECT_EQ(1U, cont.size()); | 506 EXPECT_EQ(1U, cont.size()); |
513 EXPECT_EQ(2, *result.first); | 507 EXPECT_EQ(2, *result.first); |
514 | 508 |
515 value = 1; | 509 value = 1; |
516 result = cont.insert(value); | 510 result = cont.insert(value); |
517 EXPECT_TRUE(result.second); | 511 EXPECT_TRUE(result.second); |
518 EXPECT_EQ(cont.begin(), result.first); | 512 EXPECT_EQ(cont.begin(), result.first); |
519 EXPECT_EQ(2U, cont.size()); | 513 EXPECT_EQ(2U, cont.size()); |
520 EXPECT_EQ(1, *result.first); | 514 EXPECT_EQ(1, *result.first); |
521 | 515 |
522 value = 3; | 516 value = 3; |
523 result = cont.insert(value); | 517 result = cont.insert(value); |
524 EXPECT_TRUE(result.second); | 518 EXPECT_TRUE(result.second); |
525 EXPECT_EQ(std::prev(cont.end()), result.first); | 519 EXPECT_EQ(std::prev(cont.end()), result.first); |
526 EXPECT_EQ(3U, cont.size()); | 520 EXPECT_EQ(3U, cont.size()); |
527 EXPECT_EQ(3, *result.first); | 521 EXPECT_EQ(3, *result.first); |
528 | 522 |
529 value = 3; | 523 value = 3; |
530 result = cont.insert(value); | 524 result = cont.insert(value); |
531 EXPECT_FALSE(result.second); | 525 EXPECT_FALSE(result.second); |
532 EXPECT_EQ(std::prev(cont.end()), result.first); | 526 EXPECT_EQ(std::prev(cont.end()), result.first); |
533 EXPECT_EQ(3U, cont.size()); | 527 EXPECT_EQ(3U, cont.size()); |
534 EXPECT_EQ(3, *result.first); | 528 EXPECT_EQ(3, *result.first); |
535 } | 529 } |
536 | 530 |
537 // pair<iterator, bool> insert(value_type&& val) | 531 // pair<iterator, bool> insert(value_type&& val) |
538 | 532 |
539 TEST(FlatSet, InsertRValue) { | 533 TEST(FlatTree, InsertRValue) { |
540 MoveOnlySet cont; | 534 MoveOnlyTree cont; |
541 | 535 |
542 std::pair<MoveOnlySet::iterator, bool> result = cont.insert(MoveOnly(2)); | 536 std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2)); |
543 EXPECT_TRUE(result.second); | 537 EXPECT_TRUE(result.second); |
544 EXPECT_EQ(cont.begin(), result.first); | 538 EXPECT_EQ(cont.begin(), result.first); |
545 EXPECT_EQ(1U, cont.size()); | 539 EXPECT_EQ(1U, cont.size()); |
546 EXPECT_EQ(2, result.first->data()); | 540 EXPECT_EQ(2, result.first->data()); |
547 | 541 |
548 result = cont.insert(MoveOnly(1)); | 542 result = cont.insert(MoveOnlyInt(1)); |
549 EXPECT_TRUE(result.second); | 543 EXPECT_TRUE(result.second); |
550 EXPECT_EQ(cont.begin(), result.first); | 544 EXPECT_EQ(cont.begin(), result.first); |
551 EXPECT_EQ(2U, cont.size()); | 545 EXPECT_EQ(2U, cont.size()); |
552 EXPECT_EQ(1, result.first->data()); | 546 EXPECT_EQ(1, result.first->data()); |
553 | 547 |
554 result = cont.insert(MoveOnly(3)); | 548 result = cont.insert(MoveOnlyInt(3)); |
555 EXPECT_TRUE(result.second); | 549 EXPECT_TRUE(result.second); |
556 EXPECT_EQ(std::prev(cont.end()), result.first); | 550 EXPECT_EQ(std::prev(cont.end()), result.first); |
557 EXPECT_EQ(3U, cont.size()); | 551 EXPECT_EQ(3U, cont.size()); |
558 EXPECT_EQ(3, result.first->data()); | 552 EXPECT_EQ(3, result.first->data()); |
559 | 553 |
560 result = cont.insert(MoveOnly(3)); | 554 result = cont.insert(MoveOnlyInt(3)); |
561 EXPECT_FALSE(result.second); | 555 EXPECT_FALSE(result.second); |
562 EXPECT_EQ(std::prev(cont.end()), result.first); | 556 EXPECT_EQ(std::prev(cont.end()), result.first); |
563 EXPECT_EQ(3U, cont.size()); | 557 EXPECT_EQ(3U, cont.size()); |
564 EXPECT_EQ(3, result.first->data()); | 558 EXPECT_EQ(3, result.first->data()); |
565 } | 559 } |
566 | 560 |
567 // iterator insert(const_iterator position_hint, const value_type& val) | 561 // iterator insert(const_iterator position_hint, const value_type& val) |
568 | 562 |
569 TEST(FlatSet, InsertPositionLValue) { | 563 TEST(FlatTree, InsertPositionLValue) { |
570 IntSet cont; | 564 IntTree cont; |
571 | 565 |
572 IntSet::iterator result = cont.insert(cont.cend(), 2); | 566 IntTree::iterator result = cont.insert(cont.cend(), 2); |
573 EXPECT_EQ(cont.begin(), result); | 567 EXPECT_EQ(cont.begin(), result); |
574 EXPECT_EQ(1U, cont.size()); | 568 EXPECT_EQ(1U, cont.size()); |
575 EXPECT_EQ(2, *result); | 569 EXPECT_EQ(2, *result); |
576 | 570 |
577 result = cont.insert(cont.cend(), 1); | 571 result = cont.insert(cont.cend(), 1); |
578 EXPECT_EQ(cont.begin(), result); | 572 EXPECT_EQ(cont.begin(), result); |
579 EXPECT_EQ(2U, cont.size()); | 573 EXPECT_EQ(2U, cont.size()); |
580 EXPECT_EQ(1, *result); | 574 EXPECT_EQ(1, *result); |
581 | 575 |
582 result = cont.insert(cont.cend(), 3); | 576 result = cont.insert(cont.cend(), 3); |
583 EXPECT_EQ(std::prev(cont.end()), result); | 577 EXPECT_EQ(std::prev(cont.end()), result); |
584 EXPECT_EQ(3U, cont.size()); | 578 EXPECT_EQ(3U, cont.size()); |
585 EXPECT_EQ(3, *result); | 579 EXPECT_EQ(3, *result); |
586 | 580 |
587 result = cont.insert(cont.cend(), 3); | 581 result = cont.insert(cont.cend(), 3); |
588 EXPECT_EQ(std::prev(cont.end()), result); | 582 EXPECT_EQ(std::prev(cont.end()), result); |
589 EXPECT_EQ(3U, cont.size()); | 583 EXPECT_EQ(3U, cont.size()); |
590 EXPECT_EQ(3, *result); | 584 EXPECT_EQ(3, *result); |
591 } | 585 } |
592 | 586 |
593 // iterator insert(const_iterator position_hint, value_type&& val) | 587 // iterator insert(const_iterator position_hint, value_type&& val) |
594 | 588 |
595 TEST(FlatSet, InsertPositionRValue) { | 589 TEST(FlatTree, InsertPositionRValue) { |
596 MoveOnlySet cont; | 590 MoveOnlyTree cont; |
597 | 591 |
598 MoveOnlySet::iterator result = cont.insert(cont.cend(), MoveOnly(2)); | 592 MoveOnlyTree::iterator result = cont.insert(cont.cend(), MoveOnlyInt(2)); |
599 EXPECT_EQ(cont.begin(), result); | 593 EXPECT_EQ(cont.begin(), result); |
600 EXPECT_EQ(1U, cont.size()); | 594 EXPECT_EQ(1U, cont.size()); |
601 EXPECT_EQ(2, result->data()); | 595 EXPECT_EQ(2, result->data()); |
602 | 596 |
603 result = cont.insert(cont.cend(), MoveOnly(1)); | 597 result = cont.insert(cont.cend(), MoveOnlyInt(1)); |
604 EXPECT_EQ(cont.begin(), result); | 598 EXPECT_EQ(cont.begin(), result); |
605 EXPECT_EQ(2U, cont.size()); | 599 EXPECT_EQ(2U, cont.size()); |
606 EXPECT_EQ(1, result->data()); | 600 EXPECT_EQ(1, result->data()); |
607 | 601 |
608 result = cont.insert(cont.cend(), MoveOnly(3)); | 602 result = cont.insert(cont.cend(), MoveOnlyInt(3)); |
609 EXPECT_EQ(std::prev(cont.end()), result); | 603 EXPECT_EQ(std::prev(cont.end()), result); |
610 EXPECT_EQ(3U, cont.size()); | 604 EXPECT_EQ(3U, cont.size()); |
611 EXPECT_EQ(3, result->data()); | 605 EXPECT_EQ(3, result->data()); |
612 | 606 |
613 result = cont.insert(cont.cend(), MoveOnly(3)); | 607 result = cont.insert(cont.cend(), MoveOnlyInt(3)); |
614 EXPECT_EQ(std::prev(cont.end()), result); | 608 EXPECT_EQ(std::prev(cont.end()), result); |
615 EXPECT_EQ(3U, cont.size()); | 609 EXPECT_EQ(3U, cont.size()); |
616 EXPECT_EQ(3, result->data()); | 610 EXPECT_EQ(3, result->data()); |
617 } | 611 } |
618 | 612 |
619 // template <class... Args> | 613 // template <class... Args> |
620 // pair<iterator, bool> emplace(Args&&... args) | 614 // pair<iterator, bool> emplace(Args&&... args) |
621 | 615 |
622 TEST(FlatSet, Emplace) { | 616 TEST(FlatTree, Emplace) { |
623 { | 617 { |
624 EmplaceableSet cont; | 618 EmplaceableTree cont; |
625 | 619 |
626 std::pair<EmplaceableSet::iterator, bool> result = cont.emplace(); | 620 std::pair<EmplaceableTree::iterator, bool> result = cont.emplace(); |
627 EXPECT_TRUE(result.second); | 621 EXPECT_TRUE(result.second); |
628 EXPECT_EQ(cont.begin(), result.first); | 622 EXPECT_EQ(cont.begin(), result.first); |
629 EXPECT_EQ(1U, cont.size()); | 623 EXPECT_EQ(1U, cont.size()); |
630 EXPECT_EQ(Emplaceable(), *cont.begin()); | 624 EXPECT_EQ(Emplaceable(), *cont.begin()); |
631 | 625 |
632 result = cont.emplace(2, 3.5); | 626 result = cont.emplace(2, 3.5); |
633 EXPECT_TRUE(result.second); | 627 EXPECT_TRUE(result.second); |
634 EXPECT_EQ(std::next(cont.begin()), result.first); | 628 EXPECT_EQ(std::next(cont.begin()), result.first); |
635 EXPECT_EQ(2U, cont.size()); | 629 EXPECT_EQ(2U, cont.size()); |
636 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | 630 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); |
637 | 631 |
638 result = cont.emplace(2, 3.5); | 632 result = cont.emplace(2, 3.5); |
639 EXPECT_FALSE(result.second); | 633 EXPECT_FALSE(result.second); |
640 EXPECT_EQ(std::next(cont.begin()), result.first); | 634 EXPECT_EQ(std::next(cont.begin()), result.first); |
641 EXPECT_EQ(2U, cont.size()); | 635 EXPECT_EQ(2U, cont.size()); |
642 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); | 636 EXPECT_EQ(Emplaceable(2, 3.5), *result.first); |
643 } | 637 } |
644 { | 638 { |
645 IntSet cont; | 639 IntTree cont; |
646 | 640 |
647 std::pair<IntSet::iterator, bool> result = cont.emplace(2); | 641 std::pair<IntTree::iterator, bool> result = cont.emplace(2); |
648 EXPECT_TRUE(result.second); | 642 EXPECT_TRUE(result.second); |
649 EXPECT_EQ(cont.begin(), result.first); | 643 EXPECT_EQ(cont.begin(), result.first); |
650 EXPECT_EQ(1U, cont.size()); | 644 EXPECT_EQ(1U, cont.size()); |
651 EXPECT_EQ(2, *result.first); | 645 EXPECT_EQ(2, *result.first); |
652 } | 646 } |
653 } | 647 } |
654 | 648 |
655 // template <class... Args> | 649 // template <class... Args> |
656 // iterator emplace_hint(const_iterator position_hint, Args&&... args) | 650 // iterator emplace_hint(const_iterator position_hint, Args&&... args) |
657 | 651 |
658 TEST(FlatSet, EmplacePosition) { | 652 TEST(FlatTree, EmplacePosition) { |
659 { | 653 { |
660 EmplaceableSet cont; | 654 EmplaceableTree cont; |
661 | 655 |
662 EmplaceableSet::iterator result = cont.emplace_hint(cont.cend()); | 656 EmplaceableTree::iterator result = cont.emplace_hint(cont.cend()); |
663 EXPECT_EQ(cont.begin(), result); | 657 EXPECT_EQ(cont.begin(), result); |
664 EXPECT_EQ(1U, cont.size()); | 658 EXPECT_EQ(1U, cont.size()); |
665 EXPECT_EQ(Emplaceable(), *cont.begin()); | 659 EXPECT_EQ(Emplaceable(), *cont.begin()); |
666 | 660 |
667 result = cont.emplace_hint(cont.cend(), 2, 3.5); | 661 result = cont.emplace_hint(cont.cend(), 2, 3.5); |
668 EXPECT_EQ(std::next(cont.begin()), result); | 662 EXPECT_EQ(std::next(cont.begin()), result); |
669 EXPECT_EQ(2U, cont.size()); | 663 EXPECT_EQ(2U, cont.size()); |
670 EXPECT_EQ(Emplaceable(2, 3.5), *result); | 664 EXPECT_EQ(Emplaceable(2, 3.5), *result); |
671 | 665 |
672 result = cont.emplace_hint(cont.cbegin(), 2, 3.5); | 666 result = cont.emplace_hint(cont.cbegin(), 2, 3.5); |
673 EXPECT_EQ(std::next(cont.begin()), result); | 667 EXPECT_EQ(std::next(cont.begin()), result); |
674 EXPECT_EQ(2U, cont.size()); | 668 EXPECT_EQ(2U, cont.size()); |
675 EXPECT_EQ(Emplaceable(2, 3.5), *result); | 669 EXPECT_EQ(Emplaceable(2, 3.5), *result); |
676 } | 670 } |
677 { | 671 { |
678 IntSet cont; | 672 IntTree cont; |
679 | 673 |
680 IntSet::iterator result = cont.emplace_hint(cont.cend(), 2); | 674 IntTree::iterator result = cont.emplace_hint(cont.cend(), 2); |
681 EXPECT_EQ(cont.begin(), result); | 675 EXPECT_EQ(cont.begin(), result); |
682 EXPECT_EQ(1U, cont.size()); | 676 EXPECT_EQ(1U, cont.size()); |
683 EXPECT_EQ(2, *result); | 677 EXPECT_EQ(2, *result); |
684 } | 678 } |
685 } | 679 } |
686 | 680 |
687 // ---------------------------------------------------------------------------- | 681 // ---------------------------------------------------------------------------- |
688 // Erase operations. | 682 // Erase operations. |
689 | 683 |
690 // iterator erase(const_iterator position_hint) | 684 // iterator erase(const_iterator position_hint) |
691 | 685 |
692 TEST(FlatSet, ErasePosition) { | 686 TEST(FlatTree, ErasePosition) { |
693 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | 687 IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
694 | 688 |
695 IntSet::iterator it = cont.erase(std::next(cont.cbegin(), 3)); | 689 IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3)); |
696 EXPECT_EQ(std::next(cont.begin(), 3), it); | 690 EXPECT_EQ(std::next(cont.begin(), 3), it); |
697 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | 691 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); |
698 | 692 |
699 it = cont.erase(std::next(cont.cbegin(), 0)); | 693 it = cont.erase(std::next(cont.cbegin(), 0)); |
700 EXPECT_EQ(cont.begin(), it); | 694 EXPECT_EQ(cont.begin(), it); |
701 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); | 695 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); |
702 | 696 |
703 it = cont.erase(std::next(cont.cbegin(), 5)); | 697 it = cont.erase(std::next(cont.cbegin(), 5)); |
704 EXPECT_EQ(cont.end(), it); | 698 EXPECT_EQ(cont.end(), it); |
705 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); | 699 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7)); |
(...skipping 14 matching lines...) Expand all Loading... |
720 EXPECT_EQ(std::next(cont.begin(), 0), it); | 714 EXPECT_EQ(std::next(cont.begin(), 0), it); |
721 EXPECT_THAT(cont, ElementsAre(5)); | 715 EXPECT_THAT(cont, ElementsAre(5)); |
722 | 716 |
723 it = cont.erase(cont.cbegin()); | 717 it = cont.erase(cont.cbegin()); |
724 EXPECT_EQ(cont.begin(), it); | 718 EXPECT_EQ(cont.begin(), it); |
725 EXPECT_EQ(cont.end(), it); | 719 EXPECT_EQ(cont.end(), it); |
726 } | 720 } |
727 | 721 |
728 // iterator erase(const_iterator first, const_iterator last) | 722 // iterator erase(const_iterator first, const_iterator last) |
729 | 723 |
730 TEST(FlatSet, EraseRange) { | 724 TEST(FlatTree, EraseRange) { |
731 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | 725 IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
732 | 726 |
733 IntSet::iterator it = | 727 IntTree::iterator it = |
734 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); | 728 cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); |
735 EXPECT_EQ(std::next(cont.begin(), 5), it); | 729 EXPECT_EQ(std::next(cont.begin(), 5), it); |
736 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); | 730 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); |
737 | 731 |
738 it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4)); | 732 it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4)); |
739 EXPECT_EQ(std::next(cont.begin(), 3), it); | 733 EXPECT_EQ(std::next(cont.begin(), 3), it); |
740 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | 734 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); |
741 | 735 |
742 it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5)); | 736 it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5)); |
743 EXPECT_EQ(std::next(cont.begin(), 2), it); | 737 EXPECT_EQ(std::next(cont.begin(), 2), it); |
744 EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8)); | 738 EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8)); |
745 | 739 |
746 it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2)); | 740 it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2)); |
747 EXPECT_EQ(std::next(cont.begin(), 0), it); | 741 EXPECT_EQ(std::next(cont.begin(), 0), it); |
748 EXPECT_THAT(cont, ElementsAre(7, 8)); | 742 EXPECT_THAT(cont, ElementsAre(7, 8)); |
749 | 743 |
750 it = cont.erase(cont.cbegin(), cont.cend()); | 744 it = cont.erase(cont.cbegin(), cont.cend()); |
751 EXPECT_EQ(cont.begin(), it); | 745 EXPECT_EQ(cont.begin(), it); |
752 EXPECT_EQ(cont.end(), it); | 746 EXPECT_EQ(cont.end(), it); |
753 } | 747 } |
754 | 748 |
755 // size_type erase(const key_type& key) | 749 // size_type erase(const key_type& key) |
756 | 750 |
757 TEST(FlatSet, EraseKey) { | 751 TEST(FlatTree, EraseKey) { |
758 IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; | 752 IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
759 | 753 |
760 EXPECT_EQ(0U, cont.erase(9)); | 754 EXPECT_EQ(0U, cont.erase(9)); |
761 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); | 755 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); |
762 | 756 |
763 EXPECT_EQ(1U, cont.erase(4)); | 757 EXPECT_EQ(1U, cont.erase(4)); |
764 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); | 758 EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); |
765 | 759 |
766 EXPECT_EQ(1U, cont.erase(1)); | 760 EXPECT_EQ(1U, cont.erase(1)); |
767 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); | 761 EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8)); |
768 | 762 |
(...skipping 14 matching lines...) Expand all Loading... |
783 | 777 |
784 EXPECT_EQ(1U, cont.erase(5)); | 778 EXPECT_EQ(1U, cont.erase(5)); |
785 EXPECT_THAT(cont, ElementsAre()); | 779 EXPECT_THAT(cont, ElementsAre()); |
786 } | 780 } |
787 | 781 |
788 // ---------------------------------------------------------------------------- | 782 // ---------------------------------------------------------------------------- |
789 // Comparators. | 783 // Comparators. |
790 | 784 |
791 // key_compare key_comp() const | 785 // key_compare key_comp() const |
792 | 786 |
793 TEST(FlatSet, KeyComp) { | 787 TEST(FlatTree, KeyComp) { |
794 ReversedSet cont{1, 2, 3, 4, 5}; | 788 ReversedTree cont{1, 2, 3, 4, 5}; |
795 | 789 |
796 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | 790 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); |
797 int new_elements[] = {6, 7, 8, 9, 10}; | 791 int new_elements[] = {6, 7, 8, 9, 10}; |
798 std::copy(std::begin(new_elements), std::end(new_elements), | 792 std::copy(std::begin(new_elements), std::end(new_elements), |
799 std::inserter(cont, cont.end())); | 793 std::inserter(cont, cont.end())); |
800 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); | 794 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); |
801 } | 795 } |
802 | 796 |
803 // value_compare value_comp() const | 797 // value_compare value_comp() const |
804 | 798 |
805 TEST(FlatSet, ValueComp) { | 799 TEST(FlatTree, ValueComp) { |
806 ReversedSet cont{1, 2, 3, 4, 5}; | 800 ReversedTree cont{1, 2, 3, 4, 5}; |
807 | 801 |
808 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | 802 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); |
809 int new_elements[] = {6, 7, 8, 9, 10}; | 803 int new_elements[] = {6, 7, 8, 9, 10}; |
810 std::copy(std::begin(new_elements), std::end(new_elements), | 804 std::copy(std::begin(new_elements), std::end(new_elements), |
811 std::inserter(cont, cont.end())); | 805 std::inserter(cont, cont.end())); |
812 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); | 806 EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); |
813 } | 807 } |
814 | 808 |
815 // ---------------------------------------------------------------------------- | 809 // ---------------------------------------------------------------------------- |
816 // Search operations. | 810 // Search operations. |
817 | 811 |
818 // size_type count(const key_type& key) const | 812 // size_type count(const key_type& key) const |
819 | 813 |
820 TEST(FlatSet, Count) { | 814 TEST(FlatTree, Count) { |
821 { | 815 { |
822 const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | 816 const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
823 | 817 |
824 EXPECT_EQ(1U, cont.count(5)); | 818 EXPECT_EQ(1U, cont.count(5)); |
825 EXPECT_EQ(1U, cont.count(6)); | 819 EXPECT_EQ(1U, cont.count(6)); |
826 EXPECT_EQ(1U, cont.count(7)); | 820 EXPECT_EQ(1U, cont.count(7)); |
827 EXPECT_EQ(1U, cont.count(8)); | 821 EXPECT_EQ(1U, cont.count(8)); |
828 EXPECT_EQ(1U, cont.count(9)); | 822 EXPECT_EQ(1U, cont.count(9)); |
829 EXPECT_EQ(1U, cont.count(10)); | 823 EXPECT_EQ(1U, cont.count(10)); |
830 EXPECT_EQ(1U, cont.count(11)); | 824 EXPECT_EQ(1U, cont.count(11)); |
831 EXPECT_EQ(1U, cont.count(12)); | 825 EXPECT_EQ(1U, cont.count(12)); |
832 EXPECT_EQ(0U, cont.count(4)); | 826 EXPECT_EQ(0U, cont.count(4)); |
833 } | 827 } |
834 { | 828 { |
835 const SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; | 829 const IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
836 | 830 |
837 EXPECT_EQ(1U, cont.count(5)); | 831 EXPECT_EQ(1U, cont.count(5)); |
838 EXPECT_EQ(1U, cont.count(6)); | 832 EXPECT_EQ(1U, cont.count(6)); |
839 EXPECT_EQ(1U, cont.count(7)); | 833 EXPECT_EQ(1U, cont.count(7)); |
840 EXPECT_EQ(1U, cont.count(8)); | 834 EXPECT_EQ(1U, cont.count(8)); |
841 EXPECT_EQ(1U, cont.count(9)); | 835 EXPECT_EQ(1U, cont.count(9)); |
842 EXPECT_EQ(1U, cont.count(10)); | 836 EXPECT_EQ(1U, cont.count(10)); |
843 EXPECT_EQ(1U, cont.count(11)); | 837 EXPECT_EQ(1U, cont.count(11)); |
844 EXPECT_EQ(1U, cont.count(12)); | 838 EXPECT_EQ(1U, cont.count(12)); |
845 EXPECT_EQ(0U, cont.count(4)); | 839 EXPECT_EQ(0U, cont.count(4)); |
846 } | 840 } |
847 } | 841 } |
848 | 842 |
849 // iterator find(const key_type& key) | 843 // iterator find(const key_type& key) |
850 // const_iterator find(const key_type& key) const | 844 // const_iterator find(const key_type& key) const |
851 | 845 |
852 TEST(FlatSet, Find) { | 846 TEST(FlatTree, Find) { |
853 { | 847 { |
854 IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | 848 IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
855 | 849 |
856 EXPECT_EQ(cont.begin(), cont.find(5)); | 850 EXPECT_EQ(cont.begin(), cont.find(5)); |
857 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | 851 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
858 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | 852 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); |
859 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | 853 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); |
860 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | 854 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); |
861 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | 855 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); |
862 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | 856 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); |
863 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | 857 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); |
864 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | 858 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
865 } | 859 } |
866 { | 860 { |
867 const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; | 861 const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
868 | 862 |
869 EXPECT_EQ(cont.begin(), cont.find(5)); | 863 EXPECT_EQ(cont.begin(), cont.find(5)); |
870 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | 864 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
871 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | 865 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); |
872 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | 866 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); |
873 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | 867 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); |
874 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | 868 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); |
875 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | 869 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); |
876 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | 870 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); |
877 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | 871 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
878 } | 872 } |
879 { | 873 { |
880 SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; | 874 IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
881 | 875 |
882 EXPECT_EQ(cont.begin(), cont.find(5)); | 876 EXPECT_EQ(cont.begin(), cont.find(5)); |
883 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); | 877 EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
884 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); | 878 EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7)); |
885 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); | 879 EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8)); |
886 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); | 880 EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9)); |
887 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); | 881 EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10)); |
888 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); | 882 EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11)); |
889 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); | 883 EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12)); |
890 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); | 884 EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
891 } | 885 } |
892 } | 886 } |
893 | 887 |
894 // pair<iterator, iterator> equal_range(const key_type& key) | 888 // pair<iterator, iterator> equal_range(const key_type& key) |
895 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const | 889 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const |
896 | 890 |
897 TEST(FlatSet, EqualRange) { | 891 TEST(FlatTree, EqualRange) { |
898 { | 892 { |
899 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 893 IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
900 | 894 |
901 std::pair<IntSet::iterator, IntSet::iterator> result = cont.equal_range(5); | 895 std::pair<IntTree::iterator, IntTree::iterator> result = |
| 896 cont.equal_range(5); |
902 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | 897 EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
903 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | 898 EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
904 result = cont.equal_range(7); | 899 result = cont.equal_range(7); |
905 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | 900 EXPECT_EQ(std::next(cont.begin(), 1), result.first); |
906 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | 901 EXPECT_EQ(std::next(cont.begin(), 2), result.second); |
907 result = cont.equal_range(9); | 902 result = cont.equal_range(9); |
908 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | 903 EXPECT_EQ(std::next(cont.begin(), 2), result.first); |
909 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | 904 EXPECT_EQ(std::next(cont.begin(), 3), result.second); |
910 result = cont.equal_range(11); | 905 result = cont.equal_range(11); |
911 EXPECT_EQ(std::next(cont.begin(), 3), result.first); | 906 EXPECT_EQ(std::next(cont.begin(), 3), result.first); |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
944 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | 939 EXPECT_EQ(std::next(cont.begin(), 6), result.first); |
945 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | 940 EXPECT_EQ(std::next(cont.begin(), 6), result.second); |
946 result = cont.equal_range(18); | 941 result = cont.equal_range(18); |
947 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | 942 EXPECT_EQ(std::next(cont.begin(), 7), result.first); |
948 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | 943 EXPECT_EQ(std::next(cont.begin(), 7), result.second); |
949 result = cont.equal_range(20); | 944 result = cont.equal_range(20); |
950 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | 945 EXPECT_EQ(std::next(cont.begin(), 8), result.first); |
951 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | 946 EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
952 } | 947 } |
953 { | 948 { |
954 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 949 const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
955 | 950 |
956 std::pair<IntSet::const_iterator, IntSet::const_iterator> result = | 951 std::pair<IntTree::const_iterator, IntTree::const_iterator> result = |
957 cont.equal_range(5); | 952 cont.equal_range(5); |
958 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | 953 EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
959 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | 954 EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
960 result = cont.equal_range(7); | 955 result = cont.equal_range(7); |
961 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | 956 EXPECT_EQ(std::next(cont.begin(), 1), result.first); |
962 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | 957 EXPECT_EQ(std::next(cont.begin(), 2), result.second); |
963 result = cont.equal_range(9); | 958 result = cont.equal_range(9); |
964 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | 959 EXPECT_EQ(std::next(cont.begin(), 2), result.first); |
965 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | 960 EXPECT_EQ(std::next(cont.begin(), 3), result.second); |
966 result = cont.equal_range(11); | 961 result = cont.equal_range(11); |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1000 EXPECT_EQ(std::next(cont.begin(), 6), result.first); | 995 EXPECT_EQ(std::next(cont.begin(), 6), result.first); |
1001 EXPECT_EQ(std::next(cont.begin(), 6), result.second); | 996 EXPECT_EQ(std::next(cont.begin(), 6), result.second); |
1002 result = cont.equal_range(18); | 997 result = cont.equal_range(18); |
1003 EXPECT_EQ(std::next(cont.begin(), 7), result.first); | 998 EXPECT_EQ(std::next(cont.begin(), 7), result.first); |
1004 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | 999 EXPECT_EQ(std::next(cont.begin(), 7), result.second); |
1005 result = cont.equal_range(20); | 1000 result = cont.equal_range(20); |
1006 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | 1001 EXPECT_EQ(std::next(cont.begin(), 8), result.first); |
1007 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | 1002 EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
1008 } | 1003 } |
1009 { | 1004 { |
1010 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1005 IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1011 | 1006 |
1012 std::pair<SetWithLess::iterator, SetWithLess::iterator> result = | 1007 std::pair<IntTree::iterator, IntTree::iterator> result = |
1013 cont.equal_range(5); | 1008 cont.equal_range(5); |
1014 EXPECT_EQ(std::next(cont.begin(), 0), result.first); | 1009 EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
1015 EXPECT_EQ(std::next(cont.begin(), 1), result.second); | 1010 EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
1016 result = cont.equal_range(7); | 1011 result = cont.equal_range(7); |
1017 EXPECT_EQ(std::next(cont.begin(), 1), result.first); | 1012 EXPECT_EQ(std::next(cont.begin(), 1), result.first); |
1018 EXPECT_EQ(std::next(cont.begin(), 2), result.second); | 1013 EXPECT_EQ(std::next(cont.begin(), 2), result.second); |
1019 result = cont.equal_range(9); | 1014 result = cont.equal_range(9); |
1020 EXPECT_EQ(std::next(cont.begin(), 2), result.first); | 1015 EXPECT_EQ(std::next(cont.begin(), 2), result.first); |
1021 EXPECT_EQ(std::next(cont.begin(), 3), result.second); | 1016 EXPECT_EQ(std::next(cont.begin(), 3), result.second); |
1022 result = cont.equal_range(11); | 1017 result = cont.equal_range(11); |
(...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1060 EXPECT_EQ(std::next(cont.begin(), 7), result.second); | 1055 EXPECT_EQ(std::next(cont.begin(), 7), result.second); |
1061 result = cont.equal_range(20); | 1056 result = cont.equal_range(20); |
1062 EXPECT_EQ(std::next(cont.begin(), 8), result.first); | 1057 EXPECT_EQ(std::next(cont.begin(), 8), result.first); |
1063 EXPECT_EQ(std::next(cont.begin(), 8), result.second); | 1058 EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
1064 } | 1059 } |
1065 } | 1060 } |
1066 | 1061 |
1067 // iterator lower_bound(const key_type& key); | 1062 // iterator lower_bound(const key_type& key); |
1068 // const_iterator lower_bound(const key_type& key) const; | 1063 // const_iterator lower_bound(const key_type& key) const; |
1069 | 1064 |
1070 TEST(FlatSet, LowerBound) { | 1065 TEST(FlatTree, LowerBound) { |
1071 { | 1066 { |
1072 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1067 IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1073 | 1068 |
1074 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | 1069 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
1075 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | 1070 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
1076 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | 1071 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); |
1077 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | 1072 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); |
1078 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | 1073 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); |
1079 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | 1074 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); |
1080 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | 1075 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); |
1081 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | 1076 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); |
1082 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | 1077 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); |
1083 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | 1078 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); |
1084 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | 1079 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); |
1085 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | 1080 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); |
1086 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | 1081 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); |
1087 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | 1082 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); |
1088 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | 1083 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); |
1089 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | 1084 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); |
1090 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | 1085 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
1091 } | 1086 } |
1092 { | 1087 { |
1093 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1088 const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1094 | 1089 |
1095 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | 1090 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
1096 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | 1091 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
1097 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | 1092 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); |
1098 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | 1093 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); |
1099 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | 1094 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); |
1100 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | 1095 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); |
1101 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | 1096 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); |
1102 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | 1097 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); |
1103 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | 1098 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); |
1104 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | 1099 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); |
1105 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | 1100 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); |
1106 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | 1101 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); |
1107 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | 1102 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); |
1108 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | 1103 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); |
1109 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | 1104 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); |
1110 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | 1105 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); |
1111 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | 1106 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
1112 } | 1107 } |
1113 { | 1108 { |
1114 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1109 IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1115 | 1110 |
1116 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); | 1111 EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
1117 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); | 1112 EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
1118 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); | 1113 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9)); |
1119 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); | 1114 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11)); |
1120 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); | 1115 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13)); |
1121 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); | 1116 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15)); |
1122 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); | 1117 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17)); |
1123 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); | 1118 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19)); |
1124 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); | 1119 EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4)); |
1125 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); | 1120 EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6)); |
1126 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); | 1121 EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8)); |
1127 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); | 1122 EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10)); |
1128 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); | 1123 EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12)); |
1129 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); | 1124 EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14)); |
1130 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); | 1125 EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16)); |
1131 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); | 1126 EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18)); |
1132 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); | 1127 EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
1133 } | 1128 } |
1134 } | 1129 } |
1135 | 1130 |
1136 // iterator upper_bound(const key_type& key) | 1131 // iterator upper_bound(const key_type& key) |
1137 // const_iterator upper_bound(const key_type& key) const | 1132 // const_iterator upper_bound(const key_type& key) const |
1138 | 1133 |
1139 TEST(FlatSet, UpperBound) { | 1134 TEST(FlatTree, UpperBound) { |
1140 { | 1135 { |
1141 IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1136 IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1142 | 1137 |
1143 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | 1138 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
1144 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | 1139 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
1145 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | 1140 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); |
1146 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | 1141 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); |
1147 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | 1142 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); |
1148 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | 1143 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); |
1149 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | 1144 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); |
1150 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | 1145 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); |
1151 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | 1146 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); |
1152 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | 1147 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); |
1153 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | 1148 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); |
1154 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | 1149 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); |
1155 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | 1150 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); |
1156 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | 1151 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); |
1157 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | 1152 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); |
1158 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | 1153 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); |
1159 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | 1154 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
1160 } | 1155 } |
1161 { | 1156 { |
1162 const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1157 const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1163 | 1158 |
1164 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | 1159 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
1165 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | 1160 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
1166 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | 1161 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); |
1167 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | 1162 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); |
1168 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | 1163 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); |
1169 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | 1164 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); |
1170 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | 1165 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); |
1171 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | 1166 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); |
1172 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | 1167 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); |
1173 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | 1168 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); |
1174 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | 1169 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); |
1175 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | 1170 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); |
1176 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | 1171 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); |
1177 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | 1172 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); |
1178 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | 1173 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); |
1179 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | 1174 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); |
1180 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | 1175 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
1181 } | 1176 } |
1182 { | 1177 { |
1183 SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; | 1178 IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
1184 | 1179 |
1185 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); | 1180 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
1186 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); | 1181 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
1187 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); | 1182 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9)); |
1188 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); | 1183 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11)); |
1189 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); | 1184 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13)); |
1190 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); | 1185 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15)); |
1191 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); | 1186 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17)); |
1192 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); | 1187 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19)); |
1193 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); | 1188 EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4)); |
1194 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); | 1189 EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6)); |
1195 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); | 1190 EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8)); |
1196 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); | 1191 EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10)); |
1197 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); | 1192 EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12)); |
1198 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); | 1193 EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14)); |
1199 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); | 1194 EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16)); |
1200 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); | 1195 EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18)); |
1201 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); | 1196 EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
1202 } | 1197 } |
1203 } | 1198 } |
1204 | 1199 |
1205 // ---------------------------------------------------------------------------- | 1200 // ---------------------------------------------------------------------------- |
1206 // General operations. | 1201 // General operations. |
1207 | 1202 |
1208 // void swap(flat_set& other) | 1203 // void swap(flat_tree& other) |
1209 // void swap(flat_set& lhs, flat_set& rhs) | 1204 // void swap(flat_tree& lhs, flat_tree& rhs) |
1210 | 1205 |
1211 TEST(FlatSetOurs, Swap) { | 1206 TEST(FlatTreeOurs, Swap) { |
1212 IntSet x{1, 2, 3}; | 1207 IntTree x{1, 2, 3}; |
1213 IntSet y{4}; | 1208 IntTree y{4}; |
1214 swap(x, y); | 1209 swap(x, y); |
1215 EXPECT_THAT(x, ElementsAre(4)); | 1210 EXPECT_THAT(x, ElementsAre(4)); |
1216 EXPECT_THAT(y, ElementsAre(1, 2, 3)); | 1211 EXPECT_THAT(y, ElementsAre(1, 2, 3)); |
1217 | 1212 |
1218 y.swap(x); | 1213 y.swap(x); |
1219 EXPECT_THAT(x, ElementsAre(1, 2, 3)); | 1214 EXPECT_THAT(x, ElementsAre(1, 2, 3)); |
1220 EXPECT_THAT(y, ElementsAre(4)); | 1215 EXPECT_THAT(y, ElementsAre(4)); |
1221 } | 1216 } |
1222 | 1217 |
1223 // bool operator==(const flat_set& lhs, const flat_set& rhs) | 1218 // bool operator==(const flat_tree& lhs, const flat_tree& rhs) |
1224 // bool operator!=(const flat_set& lhs, const flat_set& rhs) | 1219 // bool operator!=(const flat_tree& lhs, const flat_tree& rhs) |
1225 // bool operator<(const flat_set& lhs, const flat_set& rhs) | 1220 // bool operator<(const flat_tree& lhs, const flat_tree& rhs) |
1226 // bool operator>(const flat_set& lhs, const flat_set& rhs) | 1221 // bool operator>(const flat_tree& lhs, const flat_tree& rhs) |
1227 // bool operator<=(const flat_set& lhs, const flat_set& rhs) | 1222 // bool operator<=(const flat_tree& lhs, const flat_tree& rhs) |
1228 // bool operator>=(const flat_set& lhs, const flat_set& rhs) | 1223 // bool operator>=(const flat_tree& lhs, const flat_tree& rhs) |
1229 | 1224 |
1230 TEST(FlatSet, Comparison) { | 1225 TEST(FlatTree, Comparison) { |
1231 // Provided comparator does not participate in comparison. | 1226 // Provided comparator does not participate in comparison. |
1232 ReversedSet biggest{3}; | 1227 ReversedTree biggest{3}; |
1233 ReversedSet smallest{1}; | 1228 ReversedTree smallest{1}; |
1234 ReversedSet middle{1, 2}; | 1229 ReversedTree middle{1, 2}; |
1235 | 1230 |
1236 EXPECT_EQ(biggest, biggest); | 1231 EXPECT_EQ(biggest, biggest); |
1237 EXPECT_NE(biggest, smallest); | 1232 EXPECT_NE(biggest, smallest); |
1238 EXPECT_LT(smallest, middle); | 1233 EXPECT_LT(smallest, middle); |
1239 EXPECT_LE(smallest, middle); | 1234 EXPECT_LE(smallest, middle); |
1240 EXPECT_LE(middle, middle); | 1235 EXPECT_LE(middle, middle); |
1241 EXPECT_GT(biggest, middle); | 1236 EXPECT_GT(biggest, middle); |
1242 EXPECT_GE(biggest, middle); | 1237 EXPECT_GE(biggest, middle); |
1243 EXPECT_GE(biggest, biggest); | 1238 EXPECT_GE(biggest, biggest); |
1244 } | 1239 } |
1245 | 1240 |
1246 TEST(FlatSet, EraseIf) { | 1241 TEST(FlatSet, EraseIf) { |
1247 IntSet x; | 1242 IntTree x; |
1248 base::EraseIf(x, [](int) { return false; }); | 1243 EraseIf(x, [](int) { return false; }); |
1249 EXPECT_THAT(x, ElementsAre()); | 1244 EXPECT_THAT(x, ElementsAre()); |
1250 | 1245 |
1251 x = {1, 2, 3}; | 1246 x = {1, 2, 3}; |
1252 base::EraseIf(x, [](int elem) { return !(elem & 1); }); | 1247 EraseIf(x, [](int elem) { return !(elem & 1); }); |
1253 EXPECT_THAT(x, ElementsAre(1, 3)); | 1248 EXPECT_THAT(x, ElementsAre(1, 3)); |
1254 | 1249 |
1255 x = {1, 2, 3, 4}; | 1250 x = {1, 2, 3, 4}; |
1256 base::EraseIf(x, [](int elem) { return elem & 1; }); | 1251 EraseIf(x, [](int elem) { return elem & 1; }); |
1257 EXPECT_THAT(x, ElementsAre(2, 4)); | 1252 EXPECT_THAT(x, ElementsAre(2, 4)); |
1258 } | 1253 } |
| 1254 |
| 1255 } // namespace internal |
| 1256 } // namespace base |
OLD | NEW |