]>
Commit | Line | Data |
---|---|---|
b32b8144 FG |
1 | |
2 | // Copyright 2016 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 | #include "../helpers/postfix.hpp" | |
7 | #include "../helpers/prefix.hpp" | |
8 | #include <boost/unordered_map.hpp> | |
9 | #include <boost/unordered_set.hpp> | |
10 | ||
11 | #include "../helpers/count.hpp" | |
12 | #include "../helpers/helpers.hpp" | |
13 | #include "../helpers/invariants.hpp" | |
14 | #include "../helpers/random_values.hpp" | |
15 | #include "../helpers/test.hpp" | |
16 | #include "../helpers/tracker.hpp" | |
17 | #include "../objects/test.hpp" | |
b32b8144 FG |
18 | |
19 | namespace merge_tests { | |
20 | ||
21 | UNORDERED_AUTO_TEST (merge_set) { | |
22 | boost::unordered_set<int> x; | |
23 | boost::unordered_set<int> y; | |
24 | ||
25 | x.merge(y); | |
26 | BOOST_TEST(x.empty()); | |
27 | BOOST_TEST(y.empty()); | |
28 | ||
29 | x.insert(10); | |
30 | x.merge(y); | |
31 | BOOST_TEST(x.size() == 1); | |
32 | BOOST_TEST(x.count(10) == 1); | |
33 | BOOST_TEST(y.empty()); | |
34 | ||
35 | y.merge(x); | |
36 | BOOST_TEST(x.empty()); | |
37 | BOOST_TEST(y.size() == 1); | |
38 | BOOST_TEST(y.count(10) == 1); | |
39 | ||
40 | x.insert(10); | |
41 | x.insert(50); | |
42 | y.insert(70); | |
43 | y.insert(80); | |
44 | x.merge(y); | |
45 | BOOST_TEST_EQ(x.size(), 4u); | |
46 | BOOST_TEST_EQ(y.size(), 1u); | |
47 | BOOST_TEST_EQ(x.count(10), 1u); | |
48 | BOOST_TEST_EQ(x.count(50), 1u); | |
49 | BOOST_TEST_EQ(x.count(70), 1u); | |
50 | BOOST_TEST_EQ(x.count(80), 1u); | |
51 | BOOST_TEST_EQ(y.count(10), 1u); | |
52 | BOOST_TEST_EQ(y.count(50), 0u); | |
53 | BOOST_TEST_EQ(y.count(70), 0u); | |
54 | BOOST_TEST_EQ(y.count(80), 0u); | |
55 | ||
56 | test::check_equivalent_keys(x); | |
57 | test::check_equivalent_keys(y); | |
58 | } | |
59 | ||
60 | UNORDERED_AUTO_TEST (merge_multiset) { | |
61 | boost::unordered_multiset<int> x; | |
62 | boost::unordered_multiset<int> y; | |
63 | ||
64 | x.merge(y); | |
65 | BOOST_TEST(x.empty()); | |
66 | BOOST_TEST(y.empty()); | |
67 | ||
68 | x.insert(10); | |
69 | x.merge(y); | |
70 | BOOST_TEST(x.size() == 1); | |
71 | BOOST_TEST(x.count(10) == 1); | |
72 | BOOST_TEST(y.empty()); | |
73 | ||
74 | y.merge(x); | |
75 | BOOST_TEST(x.empty()); | |
76 | BOOST_TEST(y.size() == 1); | |
77 | BOOST_TEST(y.count(10) == 1); | |
78 | ||
79 | x.insert(10); | |
80 | x.insert(50); | |
81 | y.insert(70); | |
82 | y.insert(80); | |
83 | x.merge(y); | |
84 | BOOST_TEST_EQ(x.size(), 5u); | |
85 | BOOST_TEST_EQ(y.size(), 0u); | |
86 | BOOST_TEST_EQ(x.count(10), 2u); | |
87 | BOOST_TEST_EQ(x.count(50), 1u); | |
88 | BOOST_TEST_EQ(x.count(70), 1u); | |
89 | BOOST_TEST_EQ(x.count(80), 1u); | |
90 | BOOST_TEST_EQ(y.count(10), 0u); | |
91 | BOOST_TEST_EQ(y.count(50), 0u); | |
92 | BOOST_TEST_EQ(y.count(70), 0u); | |
93 | BOOST_TEST_EQ(y.count(80), 0u); | |
94 | ||
95 | test::check_equivalent_keys(x); | |
96 | test::check_equivalent_keys(y); | |
97 | } | |
98 | ||
99 | UNORDERED_AUTO_TEST (merge_set_and_multiset) { | |
100 | boost::unordered_set<int> x; | |
101 | boost::unordered_multiset<int> y; | |
102 | ||
103 | x.merge(y); | |
104 | BOOST_TEST(x.empty()); | |
105 | BOOST_TEST(y.empty()); | |
106 | ||
107 | x.insert(10); | |
108 | x.merge(y); | |
109 | BOOST_TEST(x.size() == 1); | |
110 | BOOST_TEST(x.count(10) == 1); | |
111 | BOOST_TEST(y.empty()); | |
112 | ||
113 | y.merge(x); | |
114 | BOOST_TEST(x.empty()); | |
115 | BOOST_TEST(y.size() == 1); | |
116 | BOOST_TEST(y.count(10) == 1); | |
117 | ||
118 | x.insert(10); | |
119 | x.insert(50); | |
120 | y.insert(70); | |
121 | y.insert(80); | |
122 | x.merge(y); | |
123 | BOOST_TEST_EQ(x.size(), 4u); | |
124 | BOOST_TEST_EQ(y.size(), 1u); | |
125 | BOOST_TEST_EQ(x.count(10), 1u); | |
126 | BOOST_TEST_EQ(x.count(50), 1u); | |
127 | BOOST_TEST_EQ(x.count(70), 1u); | |
128 | BOOST_TEST_EQ(x.count(80), 1u); | |
129 | BOOST_TEST_EQ(y.count(10), 1u); | |
130 | BOOST_TEST_EQ(y.count(50), 0u); | |
131 | BOOST_TEST_EQ(y.count(70), 0u); | |
132 | BOOST_TEST_EQ(y.count(80), 0u); | |
133 | ||
134 | test::check_equivalent_keys(x); | |
135 | test::check_equivalent_keys(y); | |
136 | } | |
137 | ||
138 | template <class X1, class X2> | |
139 | void merge_empty_test(X1*, X2*, test::random_generator generator) | |
140 | { | |
141 | test::check_instances check_; | |
142 | ||
143 | test::random_values<X1> v(1000, generator); | |
144 | X1 x1(v.begin(), v.end()); | |
145 | X2 x2; | |
146 | x1.merge(x2); | |
147 | test::check_container(x1, v); | |
148 | BOOST_TEST(x2.empty()); | |
149 | test::check_equivalent_keys(x1); | |
150 | test::check_equivalent_keys(x2); | |
151 | } | |
152 | ||
153 | template <class X> | |
154 | void merge_into_empty_test(X*, test::random_generator generator) | |
155 | { | |
156 | test::check_instances check_; | |
157 | ||
158 | test::random_values<X> v(1000, generator); | |
159 | X x1; | |
160 | X x2(v.begin(), v.end()); | |
161 | x1.merge(x2); | |
162 | test::check_container(x1, v); | |
163 | BOOST_TEST(x2.empty()); | |
164 | test::check_equivalent_keys(x1); | |
165 | test::check_equivalent_keys(x2); | |
166 | } | |
167 | ||
168 | template <class X1, class X2> | |
169 | void merge_into_unique_keys_test(X1*, X2*, int hash_equal1, int hash_equal2, | |
170 | test::random_generator generator) | |
171 | { | |
172 | test::check_instances check_; | |
173 | ||
174 | test::random_values<X1> v1(1000, generator); | |
175 | test::random_values<X2> v2(1000, generator); | |
11fdf7f2 TL |
176 | v1.insert(v2.begin(), test::next(v2.begin(), 100)); |
177 | v2.insert(v1.begin(), test::next(v1.begin(), 100)); | |
b32b8144 FG |
178 | |
179 | X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1), | |
180 | test::equal_to(hash_equal1)); | |
181 | X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2), | |
182 | test::equal_to(hash_equal2)); | |
183 | ||
184 | test::ordered<X1> tracker1 = test::create_ordered(x1); | |
185 | test::ordered<X2> tracker2 = test::create_ordered(x2); | |
186 | tracker1.insert(v1.begin(), v1.end()); | |
187 | for (typename X2::iterator it = x2.begin(); it != x2.end(); ++it) { | |
188 | if (!tracker1.insert(*it).second) { | |
189 | tracker2.insert(*it); | |
190 | } | |
191 | } | |
192 | ||
193 | x1.merge(x2); | |
194 | ||
195 | tracker1.compare(x1); | |
196 | tracker2.compare(x2); | |
197 | test::check_equivalent_keys(x1); | |
198 | test::check_equivalent_keys(x2); | |
199 | } | |
200 | ||
201 | template <class X1, class X2> | |
202 | void merge_into_equiv_keys_test(X1*, X2*, int hash_equal1, int hash_equal2, | |
203 | test::random_generator generator) | |
204 | { | |
205 | test::check_instances check_; | |
206 | ||
207 | test::random_values<X1> v1(1000, generator); | |
208 | test::random_values<X2> v2(1000, generator); | |
11fdf7f2 TL |
209 | v1.insert(v2.begin(), test::next(v2.begin(), 100)); |
210 | v2.insert(v1.begin(), test::next(v1.begin(), 100)); | |
b32b8144 FG |
211 | |
212 | X1 x1(v1.begin(), v1.end(), 0, test::hash(hash_equal1), | |
213 | test::equal_to(hash_equal1)); | |
214 | X2 x2(v2.begin(), v2.end(), 0, test::hash(hash_equal2), | |
215 | test::equal_to(hash_equal2)); | |
216 | x1.merge(x2); | |
217 | ||
218 | test::ordered<X1> tracker1 = test::create_ordered(x1); | |
219 | test::ordered<X2> tracker2 = test::create_ordered(x2); | |
220 | tracker1.insert(v1.begin(), v1.end()); | |
221 | tracker2.insert(v2.begin(), v2.end()); | |
222 | tracker1.insert(tracker2.begin(), tracker2.end()); | |
223 | tracker2.clear(); | |
224 | ||
225 | tracker1.compare(x1); | |
226 | tracker2.compare(x2); | |
227 | test::check_equivalent_keys(x1); | |
228 | test::check_equivalent_keys(x2); | |
229 | } | |
230 | ||
231 | boost::unordered_set<test::movable, test::hash, test::equal_to, | |
232 | std::allocator<test::movable> >* test_set_std_alloc; | |
233 | boost::unordered_multiset<test::movable, test::hash, test::equal_to, | |
234 | std::allocator<test::movable> >* test_multiset_std_alloc; | |
235 | ||
236 | boost::unordered_map<test::object, test::object, test::hash, test::equal_to, | |
237 | std::allocator<test::object> >* test_map_std_alloc; | |
238 | boost::unordered_multimap<test::object, test::object, test::hash, | |
239 | test::equal_to, std::allocator<test::object> >* test_multimap_std_alloc; | |
240 | ||
241 | boost::unordered_set<test::object, test::hash, test::equal_to, | |
242 | test::allocator1<test::object> >* test_set; | |
243 | boost::unordered_multiset<test::object, test::hash, test::equal_to, | |
244 | test::allocator1<test::object> >* test_multiset; | |
245 | ||
246 | boost::unordered_map<test::movable, test::movable, test::hash, test::equal_to, | |
247 | test::allocator2<test::movable> >* test_map; | |
248 | boost::unordered_multimap<test::movable, test::movable, test::hash, | |
249 | test::equal_to, test::allocator2<test::movable> >* test_multimap; | |
250 | ||
251 | using test::default_generator; | |
252 | using test::generate_collisions; | |
253 | ||
254 | // clang-format off | |
255 | UNORDERED_TEST(merge_empty_test, | |
256 | ((test_set_std_alloc)(test_multiset_std_alloc)) | |
257 | ((test_set_std_alloc)(test_multiset_std_alloc)) | |
258 | ((default_generator)(generate_collisions))) | |
259 | UNORDERED_TEST(merge_empty_test, | |
260 | ((test_map_std_alloc)(test_multimap_std_alloc)) | |
261 | ((test_map_std_alloc)(test_multimap_std_alloc)) | |
262 | ((default_generator)(generate_collisions))) | |
263 | UNORDERED_TEST(merge_empty_test, | |
264 | ((test_set)(test_multiset)) | |
265 | ((test_set)(test_multiset)) | |
266 | ((default_generator)(generate_collisions))) | |
267 | UNORDERED_TEST(merge_empty_test, | |
268 | ((test_map)(test_multimap)) | |
269 | ((test_map)(test_multimap)) | |
270 | ((default_generator)(generate_collisions))) | |
271 | ||
272 | UNORDERED_TEST(merge_into_empty_test, | |
273 | ((test_set_std_alloc)(test_multiset_std_alloc)) | |
274 | ((default_generator)(generate_collisions))) | |
275 | UNORDERED_TEST(merge_into_empty_test, | |
276 | ((test_map_std_alloc)(test_multimap_std_alloc)) | |
277 | ((default_generator)(generate_collisions))) | |
278 | UNORDERED_TEST(merge_into_empty_test, | |
279 | ((test_set)(test_multiset)) | |
280 | ((default_generator)(generate_collisions))) | |
281 | UNORDERED_TEST(merge_into_empty_test, | |
282 | ((test_map)(test_multimap)) | |
283 | ((default_generator)(generate_collisions))) | |
284 | ||
285 | UNORDERED_TEST(merge_into_unique_keys_test, | |
286 | ((test_set_std_alloc)) | |
287 | ((test_set_std_alloc)(test_multiset_std_alloc)) | |
288 | ((0)(1)(2)) | |
289 | ((0)(1)(2)) | |
290 | ((default_generator)(generate_collisions))) | |
291 | UNORDERED_TEST(merge_into_unique_keys_test, | |
292 | ((test_map_std_alloc)) | |
293 | ((test_map_std_alloc)(test_multimap_std_alloc)) | |
294 | ((0)(1)(2)) | |
295 | ((0)(1)(2)) | |
296 | ((default_generator)(generate_collisions))) | |
297 | UNORDERED_TEST(merge_into_unique_keys_test, | |
298 | ((test_set)) | |
299 | ((test_set)(test_multiset)) | |
300 | ((0)(1)(2)) | |
301 | ((0)(1)(2)) | |
302 | ((default_generator)(generate_collisions))) | |
303 | UNORDERED_TEST(merge_into_unique_keys_test, | |
304 | ((test_map)) | |
305 | ((test_map)(test_multimap)) | |
306 | ((0)(1)(2)) | |
307 | ((0)(1)(2)) | |
308 | ((default_generator)(generate_collisions))) | |
309 | ||
310 | UNORDERED_TEST(merge_into_equiv_keys_test, | |
311 | ((test_multiset_std_alloc)) | |
312 | ((test_set_std_alloc)(test_multiset_std_alloc)) | |
313 | ((0)(1)(2)) | |
314 | ((0)(1)(2)) | |
315 | ((default_generator)(generate_collisions))) | |
316 | UNORDERED_TEST(merge_into_equiv_keys_test, | |
317 | ((test_multimap_std_alloc)) | |
318 | ((test_map_std_alloc)(test_multimap_std_alloc)) | |
319 | ((0)(1)(2)) | |
320 | ((0)(1)(2)) | |
321 | ((default_generator)(generate_collisions))) | |
322 | UNORDERED_TEST(merge_into_equiv_keys_test, | |
323 | ((test_multiset)) | |
324 | ((test_set)(test_multiset)) | |
325 | ((0)(1)(2)) | |
326 | ((0)(1)(2)) | |
327 | ((default_generator)(generate_collisions))) | |
328 | UNORDERED_TEST(merge_into_equiv_keys_test, | |
329 | ((test_multimap)) | |
330 | ((test_map)(test_multimap)) | |
331 | ((0)(1)(2)) | |
332 | ((0)(1)(2)) | |
333 | ((default_generator)(generate_collisions))) | |
334 | // clang-format on | |
335 | } | |
336 | ||
337 | RUN_TESTS() |