]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | // Copyright 2006-2009 Daniel James. | |
3 | // Distributed under the Boost Software License, Version 1.0. (See accompanying | |
4 | // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | // The code for erasing elements from containers with equivalent keys is very | |
7 | // hairy with several tricky edge cases - so explicitly test each one. | |
8 | ||
b32b8144 | 9 | // clang-format off |
7c673cae FG |
10 | #include "../helpers/prefix.hpp" |
11 | #include <boost/unordered_map.hpp> | |
12 | #include "../helpers/postfix.hpp" | |
b32b8144 | 13 | // clang-format on |
7c673cae FG |
14 | |
15 | #include "../helpers/test.hpp" | |
16 | #include "../helpers/list.hpp" | |
17 | #include "../helpers/invariants.hpp" | |
18 | #include "../helpers/helpers.hpp" | |
19 | #include <set> | |
7c673cae FG |
20 | #include <iterator> |
21 | #include "../objects/test.hpp" | |
22 | ||
23 | #if BOOST_WORKAROUND(BOOST_MSVC, < 1400) | |
b32b8144 FG |
24 | #pragma warning(disable : 4267) // conversion from 'size_t' to 'unsigned int', |
25 | // possible loss of data. | |
7c673cae FG |
26 | #endif |
27 | ||
28 | struct write_pair_type | |
29 | { | |
b32b8144 FG |
30 | template <class X1, class X2> |
31 | void operator()(std::pair<X1, X2> const& x) const | |
32 | { | |
33 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "(" << x.first << "," << x.second << ")"; | |
34 | } | |
7c673cae FG |
35 | } write_pair; |
36 | ||
b32b8144 | 37 | template <class Container> void write_container(Container const& x) |
7c673cae | 38 | { |
b32b8144 FG |
39 | std::for_each(x.begin(), x.end(), write_pair); |
40 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; | |
7c673cae FG |
41 | } |
42 | ||
43 | // Make everything collide - for testing erase in a single bucket. | |
44 | struct collision_hash | |
45 | { | |
b32b8144 | 46 | std::size_t operator()(int) const { return 0; } |
7c673cae FG |
47 | }; |
48 | ||
49 | // For testing erase in 2 buckets. | |
50 | struct collision2_hash | |
51 | { | |
b32b8144 FG |
52 | std::size_t operator()(int x) const |
53 | { | |
54 | return static_cast<std::size_t>(x & 1); | |
55 | } | |
7c673cae FG |
56 | }; |
57 | ||
58 | // For testing erase in lots of buckets. | |
59 | struct collision3_hash | |
60 | { | |
b32b8144 | 61 | std::size_t operator()(int x) const { return static_cast<std::size_t>(x); } |
7c673cae FG |
62 | }; |
63 | ||
b32b8144 FG |
64 | typedef boost::unordered_multimap<int, int, collision_hash, std::equal_to<int>, |
65 | test::allocator1<std::pair<int const, int> > > | |
66 | collide_map; | |
67 | typedef boost::unordered_multimap<int, int, collision2_hash, std::equal_to<int>, | |
68 | test::allocator2<std::pair<int const, int> > > | |
69 | collide_map2; | |
70 | typedef boost::unordered_multimap<int, int, collision3_hash, std::equal_to<int>, | |
71 | test::allocator2<std::pair<int const, int> > > | |
72 | collide_map3; | |
7c673cae FG |
73 | typedef collide_map::value_type collide_value; |
74 | typedef test::list<collide_value> collide_list; | |
75 | ||
b32b8144 FG |
76 | UNORDERED_AUTO_TEST (empty_range_tests) { |
77 | collide_map x; | |
78 | x.erase(x.begin(), x.end()); | |
79 | x.erase(x.begin(), x.begin()); | |
80 | x.erase(x.end(), x.end()); | |
81 | test::check_equivalent_keys(x); | |
7c673cae FG |
82 | } |
83 | ||
b32b8144 FG |
84 | UNORDERED_AUTO_TEST (single_item_tests) { |
85 | collide_list init; | |
86 | init.push_back(collide_value(1, 1)); | |
87 | ||
88 | collide_map x(init.begin(), init.end()); | |
89 | x.erase(x.begin(), x.begin()); | |
90 | BOOST_TEST(x.count(1) == 1 && x.size() == 1); | |
91 | test::check_equivalent_keys(x); | |
92 | x.erase(x.end(), x.end()); | |
93 | BOOST_TEST(x.count(1) == 1 && x.size() == 1); | |
94 | test::check_equivalent_keys(x); | |
95 | x.erase(x.begin(), x.end()); | |
96 | BOOST_TEST(x.count(1) == 0 && x.size() == 0); | |
97 | test::check_equivalent_keys(x); | |
98 | } | |
7c673cae | 99 | |
b32b8144 FG |
100 | UNORDERED_AUTO_TEST (two_equivalent_item_tests) { |
101 | collide_list init; | |
102 | init.push_back(collide_value(1, 1)); | |
103 | init.push_back(collide_value(1, 2)); | |
104 | ||
105 | { | |
7c673cae | 106 | collide_map x(init.begin(), init.end()); |
7c673cae FG |
107 | x.erase(x.begin(), x.end()); |
108 | BOOST_TEST(x.count(1) == 0 && x.size() == 0); | |
109 | test::check_equivalent_keys(x); | |
b32b8144 | 110 | } |
7c673cae | 111 | |
b32b8144 FG |
112 | { |
113 | collide_map x(init.begin(), init.end()); | |
114 | int value = test::next(x.begin())->second; | |
115 | x.erase(x.begin(), test::next(x.begin())); | |
116 | BOOST_TEST(x.count(1) == 1 && x.size() == 1 && x.begin()->first == 1 && | |
117 | x.begin()->second == value); | |
118 | test::check_equivalent_keys(x); | |
119 | } | |
7c673cae | 120 | |
b32b8144 FG |
121 | { |
122 | collide_map x(init.begin(), init.end()); | |
123 | int value = x.begin()->second; | |
124 | x.erase(test::next(x.begin()), x.end()); | |
125 | BOOST_TEST(x.count(1) == 1 && x.size() == 1 && x.begin()->first == 1 && | |
126 | x.begin()->second == value); | |
127 | test::check_equivalent_keys(x); | |
128 | } | |
7c673cae FG |
129 | } |
130 | ||
131 | // More automated tests... | |
132 | ||
b32b8144 | 133 | template <class Range1, class Range2> |
7c673cae FG |
134 | bool compare(Range1 const& x, Range2 const& y) |
135 | { | |
b32b8144 FG |
136 | collide_list a(x.begin(), x.end()); |
137 | collide_list b(y.begin(), y.end()); | |
138 | a.sort(); | |
139 | b.sort(); | |
140 | return a == b; | |
7c673cae FG |
141 | } |
142 | ||
143 | template <class Container> | |
144 | bool general_erase_range_test(Container& x, std::size_t start, std::size_t end) | |
145 | { | |
b32b8144 | 146 | collide_list l(x.begin(), x.end()); |
7c673cae | 147 | |
b32b8144 FG |
148 | l.erase(test::next(l.begin(), start), test::next(l.begin(), end)); |
149 | x.erase(test::next(x.begin(), start), test::next(x.begin(), end)); | |
7c673cae | 150 | |
b32b8144 FG |
151 | test::check_equivalent_keys(x); |
152 | return compare(l, x); | |
7c673cae FG |
153 | } |
154 | ||
b32b8144 FG |
155 | template <class Container> void erase_subrange_tests(Container const& x) |
156 | { | |
157 | for (std::size_t length = 0; length < x.size(); ++length) { | |
158 | for (std::size_t position = 0; position < x.size() - length; ++position) { | |
159 | Container y(x); | |
160 | collide_list init(y.begin(), y.end()); | |
161 | if (!general_erase_range_test(y, position, position + length)) { | |
162 | BOOST_ERROR("general_erase_range_test failed."); | |
163 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Erase: [" << position << "," | |
164 | << position + length << ")\n"; | |
165 | write_container(init); | |
166 | write_container(y); | |
167 | } | |
7c673cae | 168 | } |
b32b8144 | 169 | } |
7c673cae FG |
170 | } |
171 | ||
172 | template <class Container> | |
173 | void x_by_y_erase_range_tests(Container*, int values, int duplicates) | |
174 | { | |
b32b8144 | 175 | Container y; |
7c673cae | 176 | |
b32b8144 FG |
177 | for (int i = 0; i < values; ++i) { |
178 | for (int j = 0; j < duplicates; ++j) { | |
179 | y.insert(collide_value(i, j)); | |
7c673cae | 180 | } |
b32b8144 | 181 | } |
7c673cae | 182 | |
b32b8144 FG |
183 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "Values: " << values |
184 | << ", Duplicates: " << duplicates << "\n"; | |
185 | erase_subrange_tests(y); | |
7c673cae FG |
186 | } |
187 | ||
188 | template <class Container> | |
b32b8144 | 189 | void exhaustive_erase_tests(Container* x, int num_values, int num_duplicated) |
7c673cae | 190 | { |
b32b8144 FG |
191 | for (int i = 0; i < num_values; ++i) { |
192 | for (int j = 0; j < num_duplicated; ++j) { | |
193 | x_by_y_erase_range_tests(x, i, j); | |
7c673cae | 194 | } |
b32b8144 | 195 | } |
7c673cae FG |
196 | } |
197 | ||
b32b8144 FG |
198 | UNORDERED_AUTO_TEST (exhaustive_collide_tests) { |
199 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide_tests:\n"; | |
200 | collide_map m; | |
201 | exhaustive_erase_tests((collide_map*)0, 4, 4); | |
202 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; | |
7c673cae FG |
203 | } |
204 | ||
b32b8144 FG |
205 | UNORDERED_AUTO_TEST (exhaustive_collide2_tests) { |
206 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide2_tests:\n"; | |
207 | exhaustive_erase_tests((collide_map2*)0, 8, 4); | |
208 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; | |
7c673cae FG |
209 | } |
210 | ||
b32b8144 FG |
211 | UNORDERED_AUTO_TEST (exhaustive_collide3_tests) { |
212 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "exhaustive_collide3_tests:\n"; | |
213 | exhaustive_erase_tests((collide_map3*)0, 8, 4); | |
214 | BOOST_LIGHTWEIGHT_TEST_OSTREAM << "\n"; | |
7c673cae FG |
215 | } |
216 | ||
217 | RUN_TESTS() |