1//
2// OrderedContainersTest.cpp
3//
4// Copyright (c) 2006, Applied Informatics Software Engineering GmbH.
5// All rights reserved.
6//
7// SPDX-License-Identifier: BSL-1.0
8//
9
10
11#include "OrderedContainersTest.h"
12#include "Poco/CppUnit/TestCaller.h"
13#include "Poco/CppUnit/TestSuite.h"
14#include "Poco/Exception.h"
15
16#ifdef POCO_COMPILER_MSVC
17#pragma warning(push)
18#pragma warning(disable : 4244)
19#pragma warning(disable : 4267)
20#endif // POCO_COMPILER_MSVC
21
22using Poco::OrderedMap;
23using Poco::OrderedSet;
24using Poco::Exception;
25
26
27namespace {
28
29 static std::size_t nb_custom_allocs = 0;
30
31 template<typename T>
32 class custom_allocator
33 {
34 public:
35 using value_type = T;
36 using pointer = T*;
37 using const_pointer = const T*;
38 using reference = T &;
39 using const_reference = const T &;
40 using size_type = std::size_t;
41 using difference_type = std::ptrdiff_t;
42 using propagate_on_container_move_assignment = std::true_type;
43
44
45 template<typename U>
46 struct rebind
47 {
48 using other = custom_allocator<U>;
49 };
50
51 custom_allocator() = default;
52
53 custom_allocator(const custom_allocator &) = default;
54
55 template<typename U>
56 custom_allocator(const custom_allocator<U> &)
57 {
58 }
59
60 pointer address(reference x) const noexcept
61 {
62 return &x;
63 }
64
65 const_pointer address(const_reference x) const noexcept
66 {
67 return &x;
68 }
69
70 pointer allocate(size_type n, const void* /*hint*/ = 0)
71 {
72 nb_custom_allocs++;
73
74 pointer ptr = static_cast<pointer>(std::malloc(n * sizeof(T)));
75 if(ptr == nullptr)
76 {
77 throw std::bad_alloc();
78 }
79
80 return ptr;
81 }
82
83 void deallocate(T*p, size_type /*n*/)
84 {
85 std::free(p);
86 }
87
88 size_type max_size() const noexcept
89 {
90 return std::numeric_limits<size_type>::max() / sizeof(value_type);
91 }
92
93 template<typename U, typename... Args>
94 void construct(U*p, Args &&... args)
95 {
96 ::new(static_cast<void*>(p)) U(std::forward<Args>(args)...);
97 }
98
99 template<typename U>
100 void destroy(U*p)
101 {
102 p->~U();
103 }
104 };
105
106
107 template<class T, class U>
108 bool operator==(const custom_allocator<T> &, const custom_allocator<U> &)
109 {
110 return true;
111 }
112
113 template<class T, class U>
114 bool operator!=(const custom_allocator<T> &, const custom_allocator<U> &)
115 {
116 return false;
117 }
118
119}
120
121
122OrderedContainersTest::OrderedContainersTest(const std::string& rName): CppUnit::TestCase(rName)
123{
124}
125
126
127OrderedContainersTest::~OrderedContainersTest()
128{
129}
130
131
132void OrderedContainersTest::testMapInsert()
133{
134 testMapFuncFwd(OrderedMap, testMapInsertImpl);
135}
136
137
138void OrderedContainersTest::testRangeInsert()
139{
140 // insert x values in vector, range insert x-15 values from vector to map, check values
141 const int nb_values = 1000;
142 std::vector<std::pair<int, int>> values;
143 for(int i = 0; i < nb_values; i++)
144 values.push_back(std::make_pair(i, i+1));
145
146
147 OrderedMap<int, int> map = {{-1, 0}, {-2, 0}};
148 map.insert(values.begin() + 10, values.end() - 5);
149
150 assertEquals(map.size(), 987);
151
152 assertEquals(map.values_container()[0].first, -1);
153 assertEquals(map.values_container()[0].second, 0);
154
155 assertEquals(map.values_container()[1].first, -2);
156 assertEquals(map.values_container()[1].second, 0);
157
158 for(int i = 10, j = 2; i < nb_values - 5; i++, j++)
159 {
160 assertEquals(map.values_container()[j].first, i);
161 assertEquals(map.values_container()[j].second, i+1);
162 }
163
164}
165
166
167void OrderedContainersTest::testInsertWithHint()
168{
169 OrderedMap<int, int> map{{1, 0}, {2, 1}, {3, 2}};
170
171 // Wrong hint
172 assertTrue(map.insert(map.find(2), std::make_pair(3, 4)) == map.find(3));
173
174 // Good hint
175 assertTrue(map.insert(map.find(2), std::make_pair(2, 4)) == map.find(2));
176
177 // end() hint
178 assertTrue(map.insert(map.find(10), std::make_pair(2, 4)) == map.find(2));
179
180 assertEquals(map.size(), 3);
181
182 // end() hint, new value
183 assertEquals(map.insert(map.find(10), std::make_pair(4, 3))->first, 4);
184
185 // Wrong hint, new value
186 assertEquals(map.insert(map.find(2), std::make_pair(5, 4))->first, 5);
187
188 assertEquals(map.size(), 5);
189}
190
191
192void OrderedContainersTest::testEmplace()
193{
194 OrderedMap<std::int64_t, move_only_test> map;
195 OrderedMap<std::int64_t, move_only_test>::iterator it;
196 bool inserted;
197
198
199 std::tie(it, inserted) = map.emplace(std::piecewise_construct,
200 std::forward_as_tuple(10),
201 std::forward_as_tuple(1));
202 assertEquals(it->first, 10);
203 assert(it->second == move_only_test(1));
204 assertTrue(inserted);
205
206
207 std::tie(it, inserted) = map.emplace(std::piecewise_construct,
208 std::forward_as_tuple(10),
209 std::forward_as_tuple(3));
210 assertEquals(it->first, 10);
211 assert(it->second == move_only_test(1));
212 assertTrue(!inserted);
213}
214
215
216void OrderedContainersTest::testTryEmplace()
217{
218 OrderedMap<std::int64_t, move_only_test> map;
219 OrderedMap<std::int64_t, move_only_test>::iterator it;
220 bool inserted;
221
222
223 std::tie(it, inserted) = map.try_emplace(10, 1);
224 assertEquals(it->first, 10);
225 assert(it->second == move_only_test(1));
226 assertTrue(inserted);
227
228
229 std::tie(it, inserted) = map.try_emplace(10, 3);
230 assertEquals(it->first, 10);
231 assert(it->second == move_only_test(1));
232 assertTrue(!inserted);
233}
234
235
236void OrderedContainersTest::testTryEmplace2()
237{
238 OrderedMap<std::string, move_only_test> map;
239 OrderedMap<std::string, move_only_test>::iterator it;
240 bool inserted;
241
242 const std::size_t nb_values = 1000;
243 for(std::size_t i = 0; i < nb_values; i++) {
244 std::tie(it, inserted) = map.try_emplace(utils::get_key<std::string>(i), i);
245
246 assertEquals(it->first, utils::get_key<std::string>(i));
247 assert(it->second == move_only_test(i));
248 assertTrue(inserted);
249 }
250 assertEquals(map.size(), nb_values);
251
252 for(std::size_t i = 0; i < nb_values; i++) {
253 std::tie(it, inserted) = map.try_emplace(utils::get_key<std::string>(i), i + 1);
254
255 assertEquals(it->first, utils::get_key<std::string>(i));
256 assert(it->second == move_only_test(i));
257 assertTrue(!inserted);
258 }
259
260 for(std::size_t i = 0; i < nb_values; i++) {
261 it = map.find(utils::get_key<std::string>(i));
262
263 assertEquals(it->first, utils::get_key<std::string>(i));
264 assert(it->second == move_only_test(i));
265 }
266}
267
268
269void OrderedContainersTest::testTryEmplaceHint()
270{
271 OrderedMap<std::int64_t, move_only_test> map(0);
272
273 // end() hint, new value
274 auto it = map.try_emplace(map.find(10), 10, 1);
275 assertEquals(it->first, 10);
276 assert(it->second == move_only_test(1));
277
278 // Good hint
279 it = map.try_emplace(map.find(10), 10, 3);
280 assertEquals(it->first, 10);
281 assert(it->second == move_only_test(1));
282
283 // Wrong hint, new value
284 it = map.try_emplace(map.find(10), 1, 3);
285 assertEquals(it->first, 1);
286 assert(it->second == move_only_test(3));
287}
288
289
290void OrderedContainersTest::testInsertOrAssign()
291{
292 OrderedMap<std::int64_t, move_only_test> map;
293 OrderedMap<std::int64_t, move_only_test>::iterator it;
294 bool inserted;
295
296
297 std::tie(it, inserted) = map.insert_or_assign(10, move_only_test(1));
298 assertEquals(it->first, 10);
299 assert(it->second == move_only_test(1));
300 assertTrue(inserted);
301
302
303 std::tie(it, inserted) = map.insert_or_assign(10, move_only_test(3));
304 assertEquals(it->first, 10);
305 assert(it->second == move_only_test(3));
306 assertTrue(!inserted);
307}
308
309
310void OrderedContainersTest::testInsertOrAssignHint()
311{
312 OrderedMap<std::int64_t, move_only_test> map(0);
313
314 // end() hint, new value
315 auto it = map.insert_or_assign(map.find(10), 10, move_only_test(1));
316 assertEquals(it->first, 10);
317 assert(it->second == move_only_test(1));
318
319 // Good hint
320 it = map.insert_or_assign(map.find(10), 10, move_only_test(3));
321 assertEquals(it->first, 10);
322 assert(it->second == move_only_test(3));
323
324 // Bad hint, new value
325 it = map.insert_or_assign(map.find(10), 1, move_only_test(3));
326 assertEquals(it->first, 1);
327 assert(it->second == move_only_test(3));
328}
329
330
331void OrderedContainersTest::testInsertAtPosition()
332{
333 OrderedMap<std::string, int> map = {{"Key2", 2}, {"Key4", 4}, {"Key6", 6}};
334
335 map.insert_at_position(map.begin(), {"Key1", 1});
336 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key4", 4}, {"Key6", 6}}));
337
338 map.insert_at_position(map.nth(2), {"Key3", 3});
339 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
340 {"Key4", 4}, {"Key6", 6}}));
341
342 map.insert_at_position(map.end(), {"Key7", 7});
343 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
344 {"Key4", 4}, {"Key6", 6}, {"Key7", 7}}));
345
346 map.insert_at_position(map.nth(4), {"Key5", 5});
347 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
348 {"Key4", 4}, {"Key5", 5}, {"Key6", 6}, {"Key7", 7}}));
349}
350
351
352void OrderedContainersTest::testTryEmplaceAtPosition()
353{
354 OrderedMap<std::string, int> map = {{"Key2", 2}, {"Key4", 4}, {"Key6", 6}};
355
356 map.try_emplace_at_position(map.begin(), "Key1", 1);
357 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key4", 4}, {"Key6", 6}}));
358
359 map.try_emplace_at_position(map.nth(2), "Key3", 3);
360 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
361 {"Key4", 4}, {"Key6", 6}}));
362
363 map.try_emplace_at_position(map.end(), "Key7", 7);
364 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
365 {"Key4", 4}, {"Key6", 6}, {"Key7", 7}}));
366
367 map.try_emplace_at_position(map.nth(4), "Key5", 5);
368 assertTrue(map == (OrderedMap<std::string, int>{{"Key1", 1}, {"Key2", 2}, {"Key3", 3},
369 {"Key4", 4}, {"Key5", 5}, {"Key6", 6}, {"Key7", 7}}));
370}
371
372
373void OrderedContainersTest::testRangeEraseAll()
374{
375 // insert x values, delete all
376 using HMap = OrderedMap<std::string, std::int64_t>;
377
378 const std::size_t nb_values = 1000;
379 HMap map = utils::get_filled_hash_map<HMap>(nb_values);
380
381 auto it = map.erase(map.begin(), map.end());
382 assertTrue(it == map.end());
383 assertTrue(map.empty());
384}
385
386
387void OrderedContainersTest::testRangeErase()
388{
389 // insert x values, delete all except 10 first and 10 last value
390 using HMap = OrderedMap<std::string, std::int64_t>;
391
392 const std::size_t nb_values = 1000;
393 HMap map = utils::get_filled_hash_map<HMap>(nb_values);
394
395 auto it = map.erase(map.begin() + 10, map.end() - 10);
396 assertTrue(it == map.end() - 10);
397 assertEquals(map.size(), 20);
398 assertEquals(std::distance(map.begin(), map.end()), 20);
399
400 for(std::size_t i = 0; i < 10; i++) {
401 assertEquals(map.at(utils::get_key<std::string>(i)), utils::get_value<std::int64_t>(i));
402 assertEquals(map.at(utils::get_key<std::string>(nb_values - 10 + i)),
403 utils::get_value<std::int64_t>(nb_values - 10 + i));
404 }
405}
406
407
408void OrderedContainersTest::testMapEraseLoop()
409{
410 testMapFuncFwd(OrderedMap, testMapEraseLoopImpl);
411}
412
413
414void OrderedContainersTest::testMapInsertEraseInsert()
415{
416 testMapFuncFwd(OrderedMap, testMapInsertEraseInsertImpl);
417}
418
419
420void OrderedContainersTest::testRangeEraseSameIterators()
421{
422 const std::size_t nb_values = 100;
423 auto map = utils::get_filled_hash_map<OrderedMap<std::int64_t, std::int64_t>>(nb_values);
424
425 OrderedMap<std::int64_t, std::int64_t>::const_iterator it_const = map.cbegin();
426 std::advance(it_const, 10);
427
428 OrderedMap<std::int64_t, std::int64_t>::iterator it_mutable = map.erase(it_const, it_const);
429 assertTrue(it_const == it_mutable);
430 assertTrue(map.mutable_iterator(it_const) == it_mutable);
431 assertEquals(map.size(), 100);
432
433 it_mutable.value() = -100;
434 assertEquals(it_const.value(), -100);
435}
436
437
438void OrderedContainersTest::testUnorderedErase()
439{
440 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {2, 20}, {3, 30},
441 {4, 40}, {5, 50}, {6, 60}};
442 assertEquals(map.size(), 6);
443
444
445 assertEquals(map.unordered_erase(3), 1);
446 assertEquals(map.size(), 5);
447
448 assertEquals(map.unordered_erase(0), 0);
449 assertEquals(map.size(), 5);
450
451 auto it = map.begin();
452 while(it != map.end()) {
453 it = map.unordered_erase(it);
454 }
455
456 assertEquals(map.size(), 0);
457}
458
459
460void OrderedContainersTest::testCompare()
461{
462 const OrderedMap<std::string, int> map = {{"D", 1}, {"L", 2}, {"A", 3}};
463
464 assertTrue(map == (OrderedMap<std::string, int>{{"D", 1}, {"L", 2}, {"A", 3}}));
465 assertTrue(map != (OrderedMap<std::string, int>{{"L", 2}, {"D", 1}, {"A", 3}}));
466
467
468 assertTrue(map < (OrderedMap<std::string, int>{{"D", 1}, {"L", 2}, {"B", 3}}));
469 assertTrue(map <= (OrderedMap<std::string, int>{{"D", 1}, {"L", 2}, {"B", 3}}));
470 assertTrue(map <= (OrderedMap<std::string, int>{{"D", 1}, {"L", 2}, {"A", 3}}));
471
472 assertTrue(map > (OrderedMap<std::string, int>{{"D", 1}, {"K", 2}, {"A", 3}}));
473 assertTrue(map >= (OrderedMap<std::string, int>{{"D", 1}, {"K", 2}, {"A", 3}}));
474 assertTrue(map >= (OrderedMap<std::string, int>{{"D", 1}, {"L", 2}, {"A", 3}}));
475}
476
477
478
479void OrderedContainersTest::testClear()
480{
481 // insert x values, clear map, insert new values
482 using HMap = OrderedMap<std::int64_t, std::int64_t>;
483
484 const std::size_t nb_values = 1000;
485 auto map = utils::get_filled_hash_map<HMap>(nb_values);
486
487 map.clear();
488 assertEquals(map.size(), 0);
489 assertEquals(std::distance(map.begin(), map.end()), 0);
490
491 map.insert({5, -5});
492 map.insert({{1, -1}, {2, -1}, {4, -4}, {3, -3}});
493
494 assertTrue(map == (HMap({{5, -5}, {1, -1}, {2, -1}, {4, -4}, {3, -3}})));
495}
496
497
498void OrderedContainersTest::testReverseIterator()
499{
500 OrderedMap<std::int64_t, std::int64_t> map = {{1, 1}, {-2, 2}, {3, 3}};
501 map[2] = 4;
502
503 std::size_t i = 4;
504 for(auto it = map.rbegin(); it != map.rend(); ++it) {
505 assertEquals(it->second, i);
506 i--;
507 }
508
509 i = 4;
510 for(auto it = map.rcbegin(); it != map.rcend(); ++it) {
511 assertEquals(it->second, i);
512 i--;
513 }
514}
515
516
517void OrderedContainersTest::testIteratorArithmetic()
518{
519 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {2, 20}, {3, 30},
520 {4, 40}, {5, 50}, {6, 60}};
521
522 OrderedMap<std::int64_t, std::int64_t>::const_iterator it;
523 OrderedMap<std::int64_t, std::int64_t>::const_iterator it2;
524
525 it = map.cbegin();
526 // it += n
527 it += 3;
528 assertEquals(it->second, 40);
529
530 // it + n
531 assertEquals((map.cbegin() + 3)->second, 40);
532 // n + it
533 assertEquals((3 + map.cbegin())->second, 40);
534
535 it = map.cbegin() + 4;
536 // it -= n
537 it -= 2;
538 assertEquals(it->second, 30);
539
540 // it - n
541 assertEquals((it - 1)->second, 20);
542
543 it = map.cbegin() + 2;
544 it2 = map.cbegin() + 4;
545 // it - it
546 assertEquals(it2 - it, 2);
547
548 // it[n]
549 assertEquals(map.cbegin()[2].second, 30);
550
551 it = map.cbegin() + 1;
552 // it[n]
553 assertEquals(it[2].second, 40);
554
555 it = map.cbegin();
556 // it++
557 it++;
558 assertEquals((it++)->second, 20);
559
560 it = map.cbegin();
561 // ++it
562 ++it;
563 assertEquals((++it)->second, 30);
564
565 it = map.cend();
566 // it--
567 it--;
568 assertEquals((it--)->second, 60);
569
570 it = map.cend();
571 // --it
572 --it;
573 assertEquals((--it)->second, 50);
574}
575
576
577void OrderedContainersTest::testIteratorComparators()
578{
579 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {2, 20}, {3, 30},
580 {4, 40}, {5, 50}, {6, 60}};
581
582 OrderedMap<std::int64_t, std::int64_t>::const_iterator it;
583 OrderedMap<std::int64_t, std::int64_t>::const_iterator it2;
584
585 it = map.begin() + 1;
586 it2 = map.end() - 1;
587
588 assertTrue(it < it2);
589 assertTrue(it <= it2);
590 assertTrue(it2 > it);
591 assertTrue(it2 >= it);
592
593 it = map.begin() + 3;
594 it2 = map.end() - 3;
595
596 assertTrue(it == it2);
597 assertTrue(it <= it2);
598 assertTrue(it >= it2);
599 assertTrue(it2 <= it);
600 assertTrue(it2 >= it);
601 assertTrue(!(it < it2));
602 assertTrue(!(it > it2));
603 assertTrue(!(it2 < it));
604 assertTrue(!(it2 > it));
605}
606
607
608void OrderedContainersTest::testModifyValue()
609{
610 // insert x values, modify value of even keys, check values
611 const std::size_t nb_values = 100;
612 auto map = utils::get_filled_hash_map<OrderedMap<std::int64_t, std::int64_t>>(nb_values);
613
614 for(auto it = map.begin(); it != map.end(); ++it)
615 {
616 if(it->first % 2 == 0) it.value() = -1;
617 }
618
619 for(auto& val : map)
620 {
621 if(val.first % 2 == 0)
622 assertEquals(val.second, -1);
623 else
624 assert(val.second != -1);
625 }
626}
627
628
629void OrderedContainersTest::testAssignOperator()
630{
631 OrderedMap<std::int64_t, std::int64_t> map = {{0, 10}, {-2, 20}};
632 assertEquals(map.size(), 2);
633
634 map = {{1, 3}, {2, 4}};
635 assertEquals(map.size(), 2);
636 assertEquals(map.at(1), 3);
637 assertEquals(map.at(2), 4);
638 assertTrue(map.find(0) == map.end());
639}
640
641
642void OrderedContainersTest::testMoveConstructor()
643{
644 // insert x values in map, move map into map_move, check map and map_move,
645 // insert additional values in map_move, check map_move
646 using HMap = OrderedMap<std::string, move_only_test>;
647
648 const std::size_t nb_values = 100;
649 HMap map = utils::get_filled_hash_map<HMap>(nb_values);
650 HMap map_move(std::move(map));
651
652 assertTrue(map_move == utils::get_filled_hash_map<HMap>(nb_values));
653 assertTrue(map == (HMap()));
654
655
656
657 for(std::size_t i = nb_values; i < nb_values*2; i++) {
658 map_move.insert({utils::get_key<std::string>(i), utils::get_value<move_only_test>(i)});
659 }
660
661 assertEquals(map_move.size(), nb_values*2);
662 assertTrue(map_move == utils::get_filled_hash_map<HMap>(nb_values*2));
663}
664
665
666void OrderedContainersTest::testMoveOperator()
667{
668 // insert x values in map, move map into map_move, check map and map_move,
669 // insert additional values in map_move, check map_move
670 using HMap = OrderedMap<std::string, move_only_test>;
671
672 const std::size_t nb_values = 100;
673 HMap map = utils::get_filled_hash_map<HMap>(nb_values);
674 HMap map_move = utils::get_filled_hash_map<HMap>(1);
675 map_move = std::move(map);
676
677 assertTrue(map_move == utils::get_filled_hash_map<HMap>(nb_values));
678 assertTrue(map == (HMap()));
679
680
681
682 for(std::size_t i = nb_values; i < nb_values*2; i++) {
683 map_move.insert({utils::get_key<std::string>(i), utils::get_value<move_only_test>(i)});
684 }
685
686 assertEquals(map_move.size(), nb_values*2);
687 assertTrue(map_move == utils::get_filled_hash_map<HMap>(nb_values*2));
688}
689
690
691void OrderedContainersTest::testReassignMovedObjectMoveConstructor()
692{
693 using HMap = OrderedMap<std::string, std::string>;
694
695 HMap map = {{"Key1", "Value1"}, {"Key2", "Value2"}, {"Key3", "Value3"}};
696 HMap map_move(std::move(map));
697
698 assertEquals(map_move.size(), 3);
699 assertEquals(map.size(), 0);
700
701 map = {{"Key4", "Value4"}, {"Key5", "Value5"}};
702 assertTrue(map == (HMap({{"Key4", "Value4"}, {"Key5", "Value5"}})));
703}
704
705
706void OrderedContainersTest::testReassignMovedObjectMoveOperator()
707{
708 using HMap = OrderedMap<std::string, std::string>;
709
710 HMap map = {{"Key1", "Value1"}, {"Key2", "Value2"}, {"Key3", "Value3"}};
711 HMap map_move = std::move(map);
712
713 assertEquals(map_move.size(), 3);
714 assertEquals(map.size(), 0);
715
716 map = {{"Key4", "Value4"}, {"Key5", "Value5"}};
717 assertTrue(map == (HMap({{"Key4", "Value4"}, {"Key5", "Value5"}})));
718}
719
720
721void OrderedContainersTest::testCopyConstructorOperator()
722{
723 using HMap = OrderedMap<std::string, std::string, mod_hash<9>>;
724
725 const std::size_t nb_values = 100;
726 HMap map = utils::get_filled_hash_map<HMap>(nb_values);
727
728 HMap map_copy = map;
729 HMap map_copy2(map);
730 HMap map_copy3;
731 map_copy3 = map;
732
733 assertTrue(map == map_copy);
734 map.clear();
735
736 assertTrue(map_copy == map_copy2);
737 assertTrue(map_copy == map_copy3);
738}
739
740
741void OrderedContainersTest::testAt()
742{
743 // insert x values, use at for known and unknown values.
744 OrderedMap<std::int64_t, std::int64_t> map = {{0, 10}, {-2, 20}};
745
746 assertEquals(map.at(0), 10);
747 assertEquals(map.at(-2), 20);
748 try
749 {
750 map.at(1);
751 fail("must throw out of range");
752 }
753 catch (std::out_of_range&) {}
754}
755
756
757void OrderedContainersTest::testEqualRange()
758{
759 OrderedMap<std::int64_t, std::int64_t> map = {{0, 10}, {-2, 20}};
760
761 auto it_pair = map.equal_range(0);
762 assertTrue(std::distance(it_pair.first, it_pair.second) == 1);
763 assertEquals(it_pair.first->second, 10);
764
765 it_pair = map.equal_range(1);
766 assertTrue(it_pair.first == it_pair.second);
767 assertTrue(it_pair.first == map.end());
768}
769
770
771void OrderedContainersTest::testData()
772{
773 OrderedMap<std::int64_t, std::int64_t, std::hash<std::int64_t>, std::equal_to<std::int64_t>,
774 std::allocator<std::pair<std::int64_t, std::int64_t>>,
775 std::vector<std::pair<std::int64_t, std::int64_t>>> map = {{1, -1}, {2, -2}, {4, -4}, {3, -3}};
776
777 assertTrue(map.data() == map.values_container().data());
778}
779
780
781void OrderedContainersTest::testAccessOperator()
782{
783 // insert x values, use at for known and unknown values.
784 OrderedMap<std::int64_t, std::int64_t> map = {{0, 10}, {-2, 20}};
785
786 assertEquals(map[0], 10);
787 assertEquals(map[-2], 20);
788 assertEquals(map[2], std::int64_t());
789
790 assertEquals(map.size(), 3);
791}
792
793
794void OrderedContainersTest::testSwap()
795{
796 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {8, 80}, {3, 30}};
797 OrderedMap<std::int64_t, std::int64_t> map2 = {{4, 40}, {5, 50}};
798
799 using std::swap;
800 swap(map, map2);
801
802 assertTrue(map == (OrderedMap<std::int64_t, std::int64_t>{{4, 40}, {5, 50}}));
803 assertTrue(map2 == (OrderedMap<std::int64_t, std::int64_t>{{1, 10}, {8, 80}, {3, 30}}));
804}
805
806
807void OrderedContainersTest::testFrontBack()
808{
809 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {2, 20}};
810 map.insert({0, 0});
811
812 assertTrue(map.front() == (std::pair<std::int64_t, std::int64_t>(1, 10)));
813 assertTrue(map.back() == (std::pair<std::int64_t, std::int64_t>(0, 0)));
814
815
816 map.clear();
817 map.insert({3, 30});
818 assertTrue(map.front() == (std::pair<std::int64_t, std::int64_t>(3, 30)));
819 assertTrue(map.back() == (std::pair<std::int64_t, std::int64_t>(3, 30)));
820}
821
822
823void OrderedContainersTest::testNth()
824{
825 OrderedMap<std::int64_t, std::int64_t> map = {{1, 10}, {2, 20}};
826 map.insert({0, 0});
827
828 assertTrue(map.nth(0) != map.end());
829 assertTrue(*map.nth(0) == (std::pair<std::int64_t, std::int64_t>(1, 10)));
830
831 assertTrue(map.nth(1) != map.end());
832 assertTrue(*map.nth(1) == (std::pair<std::int64_t, std::int64_t>(2, 20)));
833
834 assertTrue(map.nth(2) != map.end());
835 assertTrue(*map.nth(2) == (std::pair<std::int64_t, std::int64_t>(0, 0)));
836
837 assertTrue(map.nth(3) == map.end());
838
839
840 map.clear();
841 assertTrue(map.nth(0) == map.end());
842}
843
844
845void OrderedContainersTest::testHeterogeneousLookups()
846{
847 struct hash_ptr
848 {
849 std::size_t operator()(const std::unique_ptr<int>& p) const {
850 return std::hash<std::uintptr_t>()(reinterpret_cast<std::uintptr_t>(p.get()));
851 }
852
853 std::size_t operator()(std::uintptr_t p) const {
854 return std::hash<std::uintptr_t>()(p);
855 }
856
857 std::size_t operator()(const int* const& p) const {
858 return std::hash<std::uintptr_t>()(reinterpret_cast<std::uintptr_t>(p));
859 }
860 };
861
862 struct equal_to_ptr {
863 using is_transparent = std::true_type;
864
865 bool operator()(const std::unique_ptr<int>& p1, const std::unique_ptr<int>& p2) const {
866 return p1 == p2;
867 }
868
869 bool operator()(const std::unique_ptr<int>& p1, std::uintptr_t p2) const {
870 return reinterpret_cast<std::uintptr_t>(p1.get()) == p2;
871 }
872
873 bool operator()(std::uintptr_t p1, const std::unique_ptr<int>& p2) const {
874 return p1 == reinterpret_cast<std::uintptr_t>(p2.get());
875 }
876
877 bool operator()(const std::unique_ptr<int>& p1, const int* const& p2) const {
878 return p1.get() == p2;
879 }
880
881 bool operator()(const int* const& p1, const std::unique_ptr<int>& p2) const {
882 return p1 == p2.get();
883 }
884 };
885
886 std::unique_ptr<int> ptr1(new int(1));
887 std::unique_ptr<int> ptr2(new int(2));
888 std::unique_ptr<int> ptr3(new int(3));
889 int other = -1;
890
891 const std::uintptr_t addr1 = reinterpret_cast<std::uintptr_t>(ptr1.get());
892 const int* const addr2 = ptr2.get();
893 const int* const addr_unknown = &other;
894
895 OrderedMap<std::unique_ptr<int>, int, hash_ptr, equal_to_ptr> map;
896 map.insert({std::move(ptr1), 4});
897 map.insert({std::move(ptr2), 5});
898 map.insert({std::move(ptr3), 6});
899
900 assertEquals(map.size(), 3);
901
902 assertEquals(map.at(addr1), 4);
903 assertEquals(map.at(addr2), 5);
904 try
905 {
906 map.at(addr_unknown);
907 fail("must throw");
908 }
909 catch (std::out_of_range) {}
910
911 assertTrue(map.find(addr1) != map.end());
912 assertEquals(*map.find(addr1)->first, 1);
913
914 assertTrue(map.find(addr2) != map.end());
915 assertEquals(*map.find(addr2)->first, 2);
916
917 assertTrue(map.find(addr_unknown) == map.end());
918
919 assertEquals(map.count(addr1), 1);
920 assertEquals(map.count(addr2), 1);
921 assertEquals(map.count(addr_unknown), 0);
922
923 assertEquals(map.erase(addr1), 1);
924 assertEquals(map.unordered_erase(addr2), 1);
925 assertEquals(map.erase(addr_unknown), 0);
926 assertEquals(map.unordered_erase(addr_unknown), 0);
927
928 assertEquals(map.size(), 1);
929}
930
931
932void OrderedContainersTest::testEmptyMap()
933{
934 OrderedMap<std::string, int> map(0);
935
936 assertEquals(map.size(), 0);
937 assertTrue(map.empty());
938
939 assertTrue(map.begin() == map.end());
940 assertTrue(map.begin() == map.cend());
941 assertTrue(map.cbegin() == map.cend());
942
943 assertTrue(map.find("") == map.end());
944 assertTrue(map.find("test") == map.end());
945
946 assertEquals(map.count(""), 0);
947 assertEquals(map.count("test"), 0);
948
949 try
950 {
951 map.at("");
952 fail ("must throw");
953 }
954 catch (std::out_of_range&) {}
955 try
956 {
957 map.at("test");
958 fail ("must throw");
959 }
960 catch (std::out_of_range&) {}
961
962 auto range = map.equal_range("test");
963 assertTrue(range.first == range.second);
964
965 assertEquals(map.erase("test"), 0);
966 assertTrue(map.erase(map.begin(), map.end()) == map.end());
967
968 assertEquals(map["new value"], int{});
969}
970
971
972void OrderedContainersTest::testPrecalculatedHash()
973{
974 OrderedMap<int, int, std::hash<int>> map = {{1, -1}, {2, -2}, {3, -3}, {4, -4}, {5, -5}, {6, -6}};
975 const OrderedMap<int, int> map_const = map;
976
977 /**
978 * find
979 */
980 assertTrue(map.find(3, map.hash_function()(3)) != map.end());
981 assertEquals(map.find(3, map.hash_function()(3))->second, -3);
982
983 assertTrue(map_const.find(3, map_const.hash_function()(3)) != map_const.end());
984 assertEquals(map_const.find(3, map_const.hash_function()(3))->second, -3);
985
986 assertTrue(map.hash_function()(2) != map.hash_function()(3));
987 assertTrue(map.find(3, map.hash_function()(2)) == map.end());
988
989 /**
990 * at
991 */
992 assertEquals(map.at(3, map.hash_function()(3)), -3);
993 assertEquals(map_const.at(3, map_const.hash_function()(3)), -3);
994
995 assertTrue(map.hash_function()(2) != map.hash_function()(3));
996 try
997 {
998 map.at(3, map.hash_function()(2));
999 } catch(std::out_of_range&) {}
1000
1001 /**
1002 * count
1003 */
1004 assertEquals(map.count(3, map.hash_function()(3)), 1);
1005 assertEquals(map_const.count(3, map_const.hash_function()(3)), 1);
1006
1007 assertTrue(map.hash_function()(2) != map.hash_function()(3));
1008 assertEquals(map.count(3, map.hash_function()(2)), 0);
1009
1010 /**
1011 * equal_range
1012 */
1013 auto it_range = map.equal_range(3, map.hash_function()(3));
1014 assertTrue(std::distance(it_range.first, it_range.second) == 1);
1015 assertEquals(it_range.first->second, -3);
1016
1017 auto it_range_const = map_const.equal_range(3, map_const.hash_function()(3));
1018 assertTrue(std::distance(it_range_const.first, it_range_const.second) == 1);
1019 assertEquals(it_range_const.first->second, -3);
1020
1021 it_range = map.equal_range(3, map.hash_function()(2));
1022 assertTrue(map.hash_function()(2) != map.hash_function()(3));
1023 assertEquals(std::distance(it_range.first, it_range.second), 0);
1024
1025 /**
1026 * erase
1027 */
1028 assertEquals(map.erase(3, map.hash_function()(3)), 1);
1029
1030 assertTrue(map.hash_function()(2) != map.hash_function()(4));
1031 assertEquals(map.erase(4, map.hash_function()(2)), 0);
1032}
1033
1034
1035void OrderedContainersTest::testSetInsert()
1036{
1037 testSetFuncFwd(OrderedSet, testSetInsertImpl);
1038}
1039
1040
1041void OrderedContainersTest::testCustomAllocator1()
1042{
1043 nb_custom_allocs = 0;
1044
1045 OrderedMap<int, int, std::hash<int>, std::equal_to<int>,
1046 custom_allocator<std::pair<int, int>>> map;
1047
1048 const int nb_elements = 10000;
1049 for(int i = 0; i < nb_elements; i++)
1050 {
1051 map.insert({i, i*2});
1052 }
1053
1054 assertTrue(nb_custom_allocs != 0);
1055}
1056
1057
1058void OrderedContainersTest::setUp()
1059{
1060}
1061
1062
1063void OrderedContainersTest::tearDown()
1064{
1065}
1066
1067
1068CppUnit::Test* OrderedContainersTest::suite()
1069{
1070 CppUnit::TestSuite* pSuite = new CppUnit::TestSuite("OrderedContainersTest");
1071
1072 CppUnit_addTest(pSuite, OrderedContainersTest, testMapInsert);
1073 CppUnit_addTest(pSuite, OrderedContainersTest, testRangeInsert);
1074 CppUnit_addTest(pSuite, OrderedContainersTest, testInsertWithHint);
1075 CppUnit_addTest(pSuite, OrderedContainersTest, testEmplace);
1076 CppUnit_addTest(pSuite, OrderedContainersTest, testTryEmplace);
1077 CppUnit_addTest(pSuite, OrderedContainersTest, testTryEmplace2);
1078 CppUnit_addTest(pSuite, OrderedContainersTest, testTryEmplaceHint);
1079 CppUnit_addTest(pSuite, OrderedContainersTest, testInsertOrAssign);
1080 CppUnit_addTest(pSuite, OrderedContainersTest, testInsertOrAssignHint);
1081 CppUnit_addTest(pSuite, OrderedContainersTest, testInsertAtPosition);
1082 CppUnit_addTest(pSuite, OrderedContainersTest, testTryEmplaceAtPosition);
1083 CppUnit_addTest(pSuite, OrderedContainersTest, testRangeErase);
1084 CppUnit_addTest(pSuite, OrderedContainersTest, testMapEraseLoop);
1085 CppUnit_addTest(pSuite, OrderedContainersTest, testMapInsertEraseInsert);
1086 CppUnit_addTest(pSuite, OrderedContainersTest, testRangeEraseAll);
1087 CppUnit_addTest(pSuite, OrderedContainersTest, testRangeEraseSameIterators);
1088 CppUnit_addTest(pSuite, OrderedContainersTest, testUnorderedErase);
1089 CppUnit_addTest(pSuite, OrderedContainersTest, testCompare);
1090 CppUnit_addTest(pSuite, OrderedContainersTest, testClear);
1091 CppUnit_addTest(pSuite, OrderedContainersTest, testReverseIterator);
1092 CppUnit_addTest(pSuite, OrderedContainersTest, testIteratorArithmetic);
1093 CppUnit_addTest(pSuite, OrderedContainersTest, testIteratorComparators);
1094 CppUnit_addTest(pSuite, OrderedContainersTest, testModifyValue);
1095 CppUnit_addTest(pSuite, OrderedContainersTest, testAssignOperator);
1096 CppUnit_addTest(pSuite, OrderedContainersTest, testMoveConstructor);
1097 CppUnit_addTest(pSuite, OrderedContainersTest, testMoveOperator);
1098 CppUnit_addTest(pSuite, OrderedContainersTest, testReassignMovedObjectMoveConstructor);
1099 CppUnit_addTest(pSuite, OrderedContainersTest, testReassignMovedObjectMoveOperator);
1100 CppUnit_addTest(pSuite, OrderedContainersTest, testCopyConstructorOperator);
1101 CppUnit_addTest(pSuite, OrderedContainersTest, testAt);
1102 CppUnit_addTest(pSuite, OrderedContainersTest, testEqualRange);
1103 CppUnit_addTest(pSuite, OrderedContainersTest, testData);
1104 CppUnit_addTest(pSuite, OrderedContainersTest, testAccessOperator);
1105 CppUnit_addTest(pSuite, OrderedContainersTest, testSwap);
1106 CppUnit_addTest(pSuite, OrderedContainersTest, testFrontBack);
1107 CppUnit_addTest(pSuite, OrderedContainersTest, testNth);
1108 CppUnit_addTest(pSuite, OrderedContainersTest, testHeterogeneousLookups);
1109 CppUnit_addTest(pSuite, OrderedContainersTest, testEmptyMap);
1110 CppUnit_addTest(pSuite, OrderedContainersTest, testPrecalculatedHash);
1111 CppUnit_addTest(pSuite, OrderedContainersTest, testSetInsert);
1112 CppUnit_addTest(pSuite, OrderedContainersTest, testCustomAllocator1);
1113
1114 return pSuite;
1115}
1116
1117#ifdef POCO_COMPILER_MSVC
1118#pragma warning(pop)
1119#endif // POCO_COMPILER_MSVC
1120