1 | /* Boost.MultiIndex test for node handling operations. |
2 | * |
3 | * Copyright 2003-2021 Joaquin M Lopez Munoz. |
4 | * Distributed under the Boost Software License, Version 1.0. |
5 | * (See accompanying file LICENSE_1_0.txt or copy at |
6 | * http://www.boost.org/LICENSE_1_0.txt) |
7 | * |
8 | * See http://www.boost.org/libs/multi_index for library home page. |
9 | */ |
10 | |
11 | #include "test_node_handling.hpp" |
12 | |
13 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
14 | #include <boost/core/enable_if.hpp> |
15 | #include <boost/detail/lightweight_test.hpp> |
16 | #include <boost/move/utility_core.hpp> |
17 | #include "pre_multi_index.hpp" |
18 | #include <boost/multi_index_container.hpp> |
19 | #include <boost/multi_index/hashed_index.hpp> |
20 | #include <boost/multi_index/identity.hpp> |
21 | #include <boost/multi_index/ordered_index.hpp> |
22 | #include <boost/multi_index/random_access_index.hpp> |
23 | #include <boost/multi_index/ranked_index.hpp> |
24 | #include <boost/multi_index/sequenced_index.hpp> |
25 | #include <boost/next_prior.hpp> |
26 | #include <boost/type_traits/is_same.hpp> |
27 | #include <boost/type_traits/remove_reference.hpp> |
28 | #include <functional> |
29 | #include <iterator> |
30 | #include <utility> |
31 | #include <vector> |
32 | #include "count_allocator.hpp" |
33 | |
34 | using namespace boost::multi_index; |
35 | |
36 | void test_node_handle() |
37 | { |
38 | typedef count_allocator<int> allocator; |
39 | typedef multi_index_container< |
40 | int, |
41 | indexed_by< |
42 | ordered_unique<identity<int> > |
43 | >, |
44 | allocator |
45 | > container; |
46 | typedef container::node_type node_type; |
47 | |
48 | std::size_t element_count=0,allocator_count=0; |
49 | container c((allocator(element_count,allocator_count))); |
50 | |
51 | element_count=0; /* ignore non element-related allocations */ |
52 | allocator_count=0; /* ignore internal allocator(s) */ |
53 | |
54 | c.insert(x: 0); |
55 | c.insert(x: 1); |
56 | c.insert(x: 2); |
57 | const int* addr0=&*c.find(x: 0); |
58 | const int* addr1=&*c.find(x: 1); |
59 | BOOST_TEST(element_count==3); |
60 | |
61 | node_type n1; |
62 | BOOST_TEST(n1.empty()); |
63 | BOOST_TEST(!n1); |
64 | BOOST_TEST(allocator_count==0); |
65 | |
66 | node_type n2=c.extract(x: 0); |
67 | BOOST_TEST(!n2.empty()); |
68 | BOOST_TEST((bool)n2); |
69 | BOOST_TEST(n2.value()==0); |
70 | BOOST_TEST(&n2.value()==addr0); |
71 | BOOST_TEST(allocator_count==1); |
72 | |
73 | node_type n3(boost::move(t&: n2)); |
74 | BOOST_TEST(n2.empty()); |
75 | BOOST_TEST(!n3.empty()); |
76 | BOOST_TEST(&n3.value()==addr0); |
77 | BOOST_TEST(allocator_count==1); |
78 | |
79 | node_type n4(boost::move(t&: n2)); |
80 | BOOST_TEST(n4.empty()); |
81 | BOOST_TEST(allocator_count==1); |
82 | |
83 | n1=boost::move(t&: n3); |
84 | BOOST_TEST(!n1.empty()); |
85 | BOOST_TEST(&n1.value()==addr0); |
86 | BOOST_TEST(n3.empty()); |
87 | BOOST_TEST(allocator_count==1); |
88 | |
89 | BOOST_TEST(n1.get_allocator()==c.get_allocator()); |
90 | |
91 | node_type n5=c.extract(x: 1); |
92 | BOOST_TEST(n5.value()==1); |
93 | BOOST_TEST(&n5.value()==addr1); |
94 | BOOST_TEST(allocator_count==2); |
95 | |
96 | n1.swap(x&: n5); |
97 | BOOST_TEST(&n1.value()==addr1); |
98 | BOOST_TEST(&n5.value()==addr0); |
99 | BOOST_TEST(allocator_count==2); |
100 | |
101 | using std::swap; |
102 | |
103 | swap(x&: n2,y&: n3); |
104 | BOOST_TEST(n2.empty()); |
105 | BOOST_TEST(n3.empty()); |
106 | BOOST_TEST(allocator_count==2); |
107 | |
108 | swap(x&: n1,y&: n2); |
109 | BOOST_TEST(!n2.empty()); |
110 | BOOST_TEST(&n2.value()==addr1); |
111 | BOOST_TEST(allocator_count==2); |
112 | |
113 | swap(x&: n1,y&: n2); |
114 | BOOST_TEST(&n1.value()==addr1); |
115 | BOOST_TEST(n2.empty()); |
116 | BOOST_TEST(allocator_count==2); |
117 | |
118 | n2=boost::move(t&: n3); |
119 | BOOST_TEST(n2.empty()); |
120 | BOOST_TEST(n3.empty()); |
121 | BOOST_TEST(allocator_count==2); |
122 | |
123 | BOOST_TEST(element_count==3); |
124 | n1=boost::move(t&: n5); |
125 | BOOST_TEST(&n1.value()==addr0); |
126 | BOOST_TEST(n5.empty()); |
127 | BOOST_TEST(element_count==2); |
128 | BOOST_TEST(allocator_count==1); |
129 | |
130 | n1=boost::move(t&: n5); |
131 | BOOST_TEST(n1.empty()); |
132 | BOOST_TEST(element_count==1); |
133 | BOOST_TEST(allocator_count==0); |
134 | |
135 | c.extract(x: 2); |
136 | BOOST_TEST(element_count==0); |
137 | } |
138 | |
139 | template<typename Index> |
140 | struct is_key_based:boost::integral_constant< |
141 | bool, |
142 | /* rather fragile if new index types are included in the library */ |
143 | (boost::tuples::length<typename boost::remove_reference<Index>:: |
144 | type::ctor_args>::value > 0) |
145 | > |
146 | {}; |
147 | |
148 | template<typename T> |
149 | struct is_iterator |
150 | { |
151 | typedef char yes; |
152 | struct no{char m[2];}; |
153 | |
154 | template<typename Q> static no test(...); |
155 | template<typename Q> static yes test(typename Q::iterator_category*); |
156 | |
157 | BOOST_STATIC_CONSTANT(bool,value=(sizeof(test<T>(0))==sizeof(yes))); |
158 | }; |
159 | |
160 | template<typename T> |
161 | struct enable_if_not_iterator:boost::enable_if_c< |
162 | !is_iterator<T>::value, |
163 | void* |
164 | >{}; |
165 | |
166 | template<typename Dst,typename Ret,typename NodeHandle,typename Value> |
167 | void test_transfer_result( |
168 | Dst&,Ret res,const NodeHandle& n,const Value& x, |
169 | typename enable_if_not_iterator<Ret>::type=0) |
170 | { |
171 | BOOST_TEST(*(res.position)==x); |
172 | if(res.inserted){ |
173 | BOOST_TEST(res.node.empty()); |
174 | } |
175 | else{ |
176 | BOOST_TEST(res.node.value()==x); |
177 | } |
178 | BOOST_TEST(n.empty()); |
179 | } |
180 | |
181 | template<typename Dst,typename NodeHandle,typename Value> |
182 | void test_transfer_result( |
183 | Dst&,typename Dst::iterator res,const NodeHandle& n,const Value& x) |
184 | { |
185 | BOOST_TEST(*res==x); |
186 | if(n)BOOST_TEST(n.value()==x); |
187 | } |
188 | |
189 | template<typename Dst,typename Ret> |
190 | void test_transfer_result_empty( |
191 | Dst& dst,Ret res, |
192 | typename enable_if_not_iterator<Ret>::type=0) |
193 | { |
194 | BOOST_TEST(res.position==dst.end()); |
195 | BOOST_TEST(!res.inserted); |
196 | BOOST_TEST(res.node.empty()); |
197 | } |
198 | |
199 | template<typename Dst> |
200 | void test_transfer_result_empty(Dst& dst,typename Dst::iterator res) |
201 | { |
202 | BOOST_TEST(res==dst.end()); |
203 | } |
204 | |
205 | template<typename Dst,typename Ret,typename NodeHandle,typename Value> |
206 | void test_transfer_result( |
207 | Dst& dst,typename Dst::iterator pos,Ret res, |
208 | const NodeHandle& n,const Value& x, |
209 | typename enable_if_not_iterator<Ret>::type=0) |
210 | { |
211 | if(res.inserted&&pos!=dst.end()&& |
212 | (!is_key_based<Dst>::value||*pos==x)){ |
213 | BOOST_TEST(boost::next(res.position)==pos); |
214 | } |
215 | test_transfer_result(dst,Ret(boost::move(res)),n,x); |
216 | } |
217 | |
218 | template<typename Dst,typename NodeHandle,typename Value> |
219 | void test_transfer_result( |
220 | Dst& dst,typename Dst::iterator pos, |
221 | typename Dst::iterator res,const NodeHandle& n,const Value& x) |
222 | { |
223 | if(n.empty()&&pos!=dst.end()&& |
224 | (!is_key_based<Dst>::value||*pos==x)){ |
225 | BOOST_TEST(boost::next(res)==pos); |
226 | } |
227 | test_transfer_result(dst,res,n,x); |
228 | } |
229 | |
230 | template<typename Dst,typename Ret> |
231 | void test_transfer_result_empty( |
232 | Dst& dst,typename Dst::iterator,Ret res, |
233 | typename enable_if_not_iterator<Ret>::type=0) |
234 | { |
235 | test_transfer_result_empty(dst,Ret(boost::move(res))); |
236 | } |
237 | |
238 | template<typename Dst> |
239 | void test_transfer_result_empty( |
240 | Dst& dst,typename Dst::iterator,typename Dst::iterator res) |
241 | { |
242 | test_transfer_result_empty(dst,res); |
243 | } |
244 | |
245 | template<typename Src,typename Key> |
246 | typename Src::node_type ( |
247 | Src& src,Key k, |
248 | typename enable_if_not_iterator<Key>::type=0) |
249 | { |
250 | typename Src::node_type n=src.extract(k); |
251 | if(n)BOOST_TEST(src.key_extractor()(n.value())==k); |
252 | return boost::move(n); |
253 | } |
254 | |
255 | template<typename Src> |
256 | typename Src::node_type (Src& src,typename Src::iterator pos) |
257 | { |
258 | typename Src::value_type x=*pos; |
259 | typename Src::node_type n=src.extract(pos); |
260 | if(n)BOOST_TEST(n.value()==x); |
261 | return boost::move(n); |
262 | } |
263 | |
264 | template<typename Src,typename Locator,typename Dst> |
265 | void test_transfer(Src& src,Locator loc,Dst& dst) |
266 | { |
267 | typename Dst::node_type n=checked_extract(src,loc); |
268 | if(n){ |
269 | typename Dst::value_type x=n.value(); |
270 | test_transfer_result(dst,dst.insert(boost::move(n)),n,x); |
271 | } |
272 | else{ |
273 | test_transfer_result_empty(dst,dst.insert(boost::move(n))); |
274 | } |
275 | } |
276 | |
277 | template<typename Src,typename Locator,typename Dst,typename Iterator> |
278 | void test_transfer(Src& src,Locator loc,Dst& dst,Iterator pos) |
279 | { |
280 | typename Dst::node_type n=checked_extract(src,loc); |
281 | if(n){ |
282 | typename Dst::value_type x=n.value(); |
283 | test_transfer_result(dst,pos,dst.insert(pos,boost::move(n)),n,x); |
284 | } |
285 | else{ |
286 | test_transfer_result_empty(dst,pos,dst.insert(pos,boost::move(n))); |
287 | } |
288 | } |
289 | |
290 | template<typename Src,typename Dst> |
291 | void test_transfer( |
292 | Src& src,Dst& dst0,Dst& /* dst1 */,Dst& /* dst2 */,Dst& /* dst3 */, |
293 | boost::false_type /* Src key-based */,boost::false_type /* Dst key-based */) |
294 | { |
295 | test_transfer(src,src.begin(),dst0,dst0.begin()); |
296 | test_transfer(src,src.begin(),dst0,dst0.begin()); |
297 | for(int i=0;i<6;++i)src.extract(src.begin()); |
298 | } |
299 | |
300 | template<typename Src,typename Dst> |
301 | void test_transfer( |
302 | Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */, |
303 | boost::false_type /* Src key-based */,boost::true_type /* Dst key-based */) |
304 | { |
305 | test_transfer(src,src.begin(),dst0); |
306 | test_transfer(src,src.begin(),dst0); |
307 | test_transfer(src,src.begin(),dst1,dst1.find(*src.begin())); |
308 | test_transfer(src,src.begin(),dst1,dst1.find(*src.begin())); |
309 | for(int i=0;i<4;++i)src.extract(src.begin()); |
310 | } |
311 | |
312 | template<typename Src,typename Dst> |
313 | void test_transfer( |
314 | Src& src,Dst& dst0,Dst& dst1,Dst& /* dst2 */,Dst& /* dst3 */, |
315 | boost::true_type /* Src key-based */,boost::false_type /* Dst key-based */) |
316 | { |
317 | test_transfer(src, src.begin(),dst0,dst0.begin()); |
318 | test_transfer(src, src.begin(),dst0,dst0.begin()); |
319 | test_transfer(src,*src.begin(),dst1,dst1.begin()); |
320 | test_transfer(src,*src.begin(),dst1,dst1.begin()); |
321 | test_transfer(src, -1,dst1,dst1.begin()); |
322 | for(int i=0;i<4;++i)src.extract(src.begin()); |
323 | } |
324 | |
325 | template<typename Src,typename Dst> |
326 | void test_transfer( |
327 | Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3, |
328 | boost::true_type /* Src key-based */,boost::true_type /* Dst key-based */) |
329 | { |
330 | test_transfer(src, src.begin(),dst0); |
331 | test_transfer(src, src.begin(),dst0); |
332 | test_transfer(src,*src.begin(),dst1); |
333 | test_transfer(src,*src.begin(),dst1); |
334 | test_transfer(src, -1,dst1); |
335 | test_transfer(src, src.begin(),dst2,dst2.find(*src.begin())); |
336 | test_transfer(src, src.begin(),dst2,dst2.find(*src.begin())); |
337 | test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin())); |
338 | test_transfer(src,*src.begin(),dst3,dst3.find(*src.begin())); |
339 | test_transfer(src, -1,dst3,dst3.begin()); |
340 | } |
341 | |
342 | template<typename Src,typename Dst> |
343 | void test_transfer(Src& src,Dst& dst0,Dst& dst1,Dst& dst2,Dst& dst3) |
344 | { |
345 | test_transfer( |
346 | src,dst0,dst1,dst2,dst3,is_key_based<Src>(),is_key_based<Dst>()); |
347 | } |
348 | |
349 | void test_transfer() |
350 | { |
351 | typedef multi_index_container< |
352 | int, |
353 | indexed_by< |
354 | hashed_non_unique<identity<int> >, |
355 | ordered_non_unique<identity<int> >, |
356 | random_access<>, |
357 | sequenced<>, |
358 | ranked_non_unique<identity<int> > |
359 | > |
360 | > container1; |
361 | typedef multi_index_container< |
362 | int, |
363 | indexed_by< |
364 | hashed_non_unique<identity<int> >, |
365 | ordered_unique<identity<int>,std::greater<int> >, |
366 | random_access<>, |
367 | sequenced<>, |
368 | ranked_unique<identity<int>,std::greater<int> > |
369 | > |
370 | > container2; |
371 | |
372 | container1 src; |
373 | container1::nth_index<0>::type& src0=src.get<0>(); |
374 | container1::nth_index<1>::type& src1=src.get<1>(); |
375 | container1::nth_index<2>::type& src2=src.get<2>(); |
376 | container1::nth_index<3>::type& src3=src.get<3>(); |
377 | container1::nth_index<4>::type& src4=src.get<4>(); |
378 | container2 dst0,dst1,dst2,dst3; |
379 | container2::nth_index<0>::type& dst00=dst0.get<0>(), |
380 | & dst10=dst1.get<0>(), |
381 | & dst20=dst2.get<0>(), |
382 | & dst30=dst3.get<0>(); |
383 | container2::nth_index<1>::type& dst01=dst0.get<1>(), |
384 | & dst11=dst1.get<1>(), |
385 | & dst21=dst2.get<1>(), |
386 | & dst31=dst3.get<1>(); |
387 | container2::nth_index<2>::type& dst02=dst0.get<2>(), |
388 | & dst12=dst1.get<2>(), |
389 | & dst22=dst2.get<2>(), |
390 | & dst32=dst3.get<2>(); |
391 | container2::nth_index<3>::type& dst03=dst0.get<3>(), |
392 | & dst13=dst1.get<3>(), |
393 | & dst23=dst2.get<3>(), |
394 | & dst33=dst3.get<3>(); |
395 | container2::nth_index<4>::type& dst04=dst0.get<4>(), |
396 | & dst14=dst1.get<4>(), |
397 | & dst24=dst2.get<4>(), |
398 | & dst34=dst3.get<4>(); |
399 | for(int i=0;i<6;++i){ |
400 | for(int j=0;j<8;++j)src.insert(x: i); |
401 | } |
402 | |
403 | test_transfer(src&: src0,dst0&: dst01,dst1&: dst11,dst2&: dst21,dst3&: dst31); |
404 | test_transfer(src&: src1,dst0&: dst02,dst1&: dst12,dst2&: dst22,dst3&: dst32); |
405 | test_transfer(src&: src2,dst0&: dst03,dst1&: dst13,dst2&: dst23,dst3&: dst33); |
406 | test_transfer(src&: src3,dst0&: dst04,dst1&: dst14,dst2&: dst24,dst3&: dst34); |
407 | test_transfer(src&: src4,dst0&: dst00,dst1&: dst10,dst2&: dst20,dst3&: dst30); |
408 | BOOST_TEST(src.size()==8); |
409 | } |
410 | |
411 | template<typename T> |
412 | struct enable_if_key_based:boost::enable_if_c< |
413 | is_key_based<T>::value, |
414 | void* |
415 | >{}; |
416 | |
417 | template<typename T> |
418 | struct enable_if_not_key_based:boost::enable_if_c< |
419 | !is_key_based<T>::value, |
420 | void* |
421 | >{}; |
422 | |
423 | /* Boost.Move C++03 perfect forwarding emulation converts non-const lvalue |
424 | * refs to const lvalue refs. final_forward undoes that. |
425 | */ |
426 | |
427 | #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) |
428 | |
429 | template<typename T> |
430 | T&& final_forward(typename boost::remove_reference<T>::type& x) |
431 | { |
432 | return static_cast<T&&>(x); |
433 | } |
434 | |
435 | #else |
436 | |
437 | template<typename T> |
438 | T& final_forward(const T& x){return const_cast<T&>(x);} |
439 | |
440 | #endif |
441 | |
442 | template<typename Dst,typename Src> |
443 | void merge( |
444 | Dst& dst,BOOST_FWD_REF(Src) src, |
445 | typename enable_if_key_based<Dst>::type=0) |
446 | { |
447 | dst.merge(final_forward<Src>(src)); |
448 | } |
449 | |
450 | template<typename Dst,typename Src> |
451 | void merge( |
452 | Dst& dst,BOOST_FWD_REF(Src) src, |
453 | typename enable_if_not_key_based<Dst>::type=0) |
454 | { |
455 | dst.splice(dst.end(),final_forward<Src>(src)); |
456 | } |
457 | |
458 | template<typename Dst,typename Src> |
459 | std::pair<typename Dst::iterator,bool> merge( |
460 | Dst& dst,BOOST_FWD_REF(Src) src, |
461 | typename boost::remove_reference<Src>::type::iterator i, |
462 | typename enable_if_key_based<Dst>::type=0) |
463 | { |
464 | return dst.merge(final_forward<Src>(src),i); |
465 | } |
466 | |
467 | template<typename Dst,typename Src> |
468 | std::pair<typename Dst::iterator,bool> merge( |
469 | Dst& dst,BOOST_FWD_REF(Src) src, |
470 | typename boost::remove_reference<Src>::type::iterator i, |
471 | typename enable_if_not_key_based<Dst>::type=0) |
472 | { |
473 | return dst.splice(dst.end(),final_forward<Src>(src),i); |
474 | } |
475 | |
476 | template<typename Dst,typename Src> |
477 | void merge( |
478 | Dst& dst,BOOST_FWD_REF(Src) src, |
479 | typename boost::remove_reference<Src>::type::iterator first, |
480 | typename boost::remove_reference<Src>::type::iterator last, |
481 | typename enable_if_key_based<Dst>::type=0) |
482 | { |
483 | dst.merge(final_forward<Src>(src),first,last); |
484 | } |
485 | |
486 | template<typename Dst,typename Src> |
487 | void merge( |
488 | Dst& dst,BOOST_FWD_REF(Src) src, |
489 | typename boost::remove_reference<Src>::type::iterator first, |
490 | typename boost::remove_reference<Src>::type::iterator last, |
491 | typename enable_if_not_key_based<Dst>::type=0) |
492 | { |
493 | dst.splice(dst.end(),final_forward<Src>(src),first,last); |
494 | } |
495 | |
496 | template<typename Dst,typename Src> |
497 | void test_merge_same(Dst& dst,BOOST_FWD_REF(Src) src) |
498 | { |
499 | std::size_t n=dst.size(); |
500 | merge(dst,boost::forward<Src>(src)); |
501 | BOOST_TEST(dst.size()==n); |
502 | BOOST_TEST(src.size()==n); |
503 | } |
504 | |
505 | template<typename Iterator,typename Value> |
506 | bool find_address(Iterator first,Iterator last,const Value* x) |
507 | { |
508 | while(first!=last)if(&*first++==x)return true; |
509 | return false; |
510 | } |
511 | |
512 | template<typename Dst,typename Src> |
513 | void test_merge_different( |
514 | Dst& dst,BOOST_FWD_REF(Src) src,bool transferred_iters) |
515 | { |
516 | typedef typename boost::remove_reference<Src>:: |
517 | type::iterator src_iterator; |
518 | typedef typename boost::remove_reference<Src>:: |
519 | type::value_type src_value_type; |
520 | |
521 | std::size_t n=dst.size(),m=src.size(); |
522 | std::vector< |
523 | std::pair<src_iterator,const src_value_type*> |
524 | > v; |
525 | for(src_iterator first=src.begin(),last=src.end();first!=last;++first){ |
526 | v.push_back(std::make_pair(first,&*first)); |
527 | } |
528 | |
529 | merge(dst,boost::forward<Src>(src)); |
530 | BOOST_TEST(dst.size()>=n && m>=src.size() && dst.size()-n==m-src.size()); |
531 | for(std::size_t i=0;i<v.size();++i){ |
532 | BOOST_TEST( |
533 | find_address(src.begin(),src.end(),v[i].second)|| |
534 | find_address(dst.begin(),dst.end(),v[i].second)); |
535 | } |
536 | if(transferred_iters){ |
537 | for(std::size_t i=0;i<v.size();++i){ |
538 | BOOST_TEST(&*(v[i].first)==v[i].second); |
539 | } |
540 | } |
541 | } |
542 | |
543 | template<typename Dst,typename Src> |
544 | void test_merge_same( |
545 | Dst& dst,BOOST_FWD_REF(Src) src, |
546 | typename boost::remove_reference<Src>::type::iterator i, |
547 | bool key_based=is_key_based<Dst>::value) |
548 | { |
549 | typedef typename Dst::iterator dst_iterator; |
550 | |
551 | std::size_t n=dst.size(); |
552 | |
553 | std::pair<dst_iterator,bool> p=merge(dst,boost::forward<Src>(src),i); |
554 | BOOST_TEST(dst.size()==n); |
555 | BOOST_TEST(src.size()==n); |
556 | BOOST_TEST(&*(p.first)==&*i && p.second); |
557 | if(!key_based)BOOST_TEST(boost::next(p.first)==dst.end()); |
558 | } |
559 | |
560 | template<typename Dst,typename Src> |
561 | void test_merge_different( |
562 | Dst& dst,BOOST_FWD_REF(Src) src, |
563 | typename boost::remove_reference<Src>::type::iterator i, |
564 | bool key_based=is_key_based<Dst>::value) |
565 | { |
566 | typedef typename Dst::iterator dst_iterator; |
567 | |
568 | std::size_t n=dst.size(),m=src.size(); |
569 | const typename Dst::value_type* pi=&*i; |
570 | |
571 | std::pair<dst_iterator,bool> p=merge(dst,boost::forward<Src>(src),i); |
572 | BOOST_TEST(dst.size()+src.size()==n+m); |
573 | BOOST_TEST(p.second? |
574 | &*(p.first)==pi: |
575 | &*(p.first)!=pi && *(p.first)==*i); |
576 | if(!key_based)BOOST_TEST(!p.second || boost::next(p.first)==dst.end()); |
577 | } |
578 | |
579 | template<typename Dst,typename Src> |
580 | void test_merge_same( |
581 | Dst& dst,BOOST_FWD_REF(Src) src, |
582 | typename boost::remove_reference<Src>::type::iterator first, |
583 | typename boost::remove_reference<Src>::type::iterator last, |
584 | bool key_based=is_key_based<Dst>::value) |
585 | { |
586 | typedef typename Dst::iterator dst_iterator; |
587 | typedef typename boost::remove_reference<Src>:: |
588 | type::iterator src_iterator; |
589 | typedef typename boost::remove_reference<Src>:: |
590 | type::value_type src_value_type; |
591 | |
592 | std::size_t n=dst.size(),d=std::distance(first,last); |
593 | std::vector<const src_value_type*> v; |
594 | for(src_iterator it=first;it!=last;++it)v.push_back(&*it); |
595 | |
596 | merge(dst,boost::forward<Src>(src),first,last); |
597 | BOOST_TEST(dst.size()==n); |
598 | BOOST_TEST(src.size()==n); |
599 | if(!key_based){ |
600 | dst_iterator it=boost::next(dst.begin(),(std::ptrdiff_t)(dst.size()-d)); |
601 | for(std::size_t i=0;i<d;++i){ |
602 | BOOST_TEST(&*it++==v[i]); |
603 | } |
604 | } |
605 | else{ |
606 | src_iterator it=first; |
607 | for(std::size_t i=0;i<d;++i){ |
608 | BOOST_TEST(&*it++==v[i]); |
609 | } |
610 | } |
611 | } |
612 | |
613 | template<typename Dst,typename Src> |
614 | void test_merge_different( |
615 | Dst& dst,BOOST_FWD_REF(Src) src, |
616 | typename boost::remove_reference<Src>::type::iterator first, |
617 | typename boost::remove_reference<Src>::type::iterator last, |
618 | bool key_based=is_key_based<Dst>::value) |
619 | { |
620 | typedef typename Dst::iterator dst_iterator; |
621 | typedef typename boost::remove_reference<Src>:: |
622 | type::iterator src_iterator; |
623 | typedef typename boost::remove_reference<Src>:: |
624 | type::value_type src_value_type; |
625 | |
626 | std::size_t n=dst.size(), |
627 | m=src.size(); |
628 | std::vector<const src_value_type*> v; |
629 | for(src_iterator it=first;it!=last;++it)v.push_back(&*it); |
630 | |
631 | merge(dst,boost::forward<Src>(src),first,last); |
632 | BOOST_TEST(dst.size()>=n && m>=src.size() && dst.size()-n==m-src.size()); |
633 | if(!key_based){ |
634 | for(dst_iterator it=boost::next(dst.begin(),(std::ptrdiff_t)n); |
635 | it!=dst.end();++it){ |
636 | BOOST_TEST(std::find(v.begin(),v.end(),&*it)!=v.end()); |
637 | } |
638 | } |
639 | for(std::size_t i=0;i<v.size();++i){ |
640 | BOOST_TEST( |
641 | find_address(src.begin(),src.end(),v[i])|| |
642 | find_address(dst.begin(),dst.end(),v[i])); |
643 | } |
644 | } |
645 | |
646 | template<int N,int M,typename Dst> |
647 | void test_merge_same(Dst& dst) |
648 | { |
649 | const Dst dst1=dst; |
650 | { |
651 | Dst dst2=dst1; |
652 | test_merge_same( |
653 | dst2.template get<N>(),dst2.template get<M>()); |
654 | test_merge_same( |
655 | dst2.template get<N>(),boost::move(dst2.template get<M>())); |
656 | } |
657 | { |
658 | Dst dst2=dst1; |
659 | test_merge_same( |
660 | dst2.template get<N>(),dst2.template get<M>(), |
661 | boost::next( |
662 | dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2))); |
663 | test_merge_same( |
664 | dst2.template get<N>(),boost::move(dst2.template get<M>()), |
665 | boost::next( |
666 | dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2))); |
667 | } |
668 | { |
669 | Dst dst2=dst1; |
670 | test_merge_same( |
671 | dst2.template get<N>(),dst2.template get<M>(), |
672 | dst2.template get<M>().begin(), |
673 | boost::next( |
674 | dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2))); |
675 | test_merge_same( |
676 | dst2.template get<N>(),boost::move(dst2.template get<M>()), |
677 | dst2.template get<M>().begin(), |
678 | boost::next( |
679 | dst2.template get<M>().begin(),(std::ptrdiff_t)(dst2.size()/2))); |
680 | } |
681 | } |
682 | |
683 | template<int N,int M,typename Dst,typename Src> |
684 | void test_merge_different(Dst& dst,Src& src) |
685 | { |
686 | const Dst dst1=dst; |
687 | const Src src1=src; |
688 | const bool transferred_iters= |
689 | boost::is_same< |
690 | typename boost::multi_index::nth_index<Dst,M>::type::iterator, |
691 | typename boost::multi_index::nth_index<Src,M>::type::iterator>::value; |
692 | { |
693 | Dst dst2=dst1; |
694 | Src src2=src1; |
695 | test_merge_different( |
696 | dst2.template get<N>(),src2.template get<M>(),transferred_iters); |
697 | } |
698 | { |
699 | Dst dst2=dst1; |
700 | Src src2=src1; |
701 | test_merge_different( |
702 | dst2.template get<N>(),boost::move(src2.template get<M>()), |
703 | transferred_iters); |
704 | } |
705 | { |
706 | Dst dst2=dst1; |
707 | Src src2=src1; |
708 | test_merge_different( |
709 | dst2.template get<N>(),src2.template get<M>(), |
710 | boost::next( |
711 | src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2))); |
712 | } |
713 | { |
714 | Dst dst2=dst1; |
715 | Src src2=src1; |
716 | test_merge_different( |
717 | dst2.template get<N>(),boost::move(src2.template get<M>()), |
718 | boost::next( |
719 | src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2))); |
720 | } |
721 | { |
722 | Dst dst2=dst1; |
723 | Src src2=src1; |
724 | test_merge_different( |
725 | dst2.template get<N>(),src2.template get<M>(), |
726 | src2.template get<M>().begin(), |
727 | boost::next( |
728 | src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2))); |
729 | } |
730 | { |
731 | Dst dst2=dst1; |
732 | Src src2=src1; |
733 | test_merge_different( |
734 | dst2.template get<N>(),boost::move(src2.template get<M>()), |
735 | src2.template get<M>().begin(), |
736 | boost::next( |
737 | src2.template get<M>().begin(),(std::ptrdiff_t)(src2.size()/2))); |
738 | } |
739 | } |
740 | |
741 | template<int N,int M,typename Dst,typename Src> |
742 | void test_merge(Dst& dst,Src& src) |
743 | { |
744 | test_merge_different<N,M>(dst,src); |
745 | } |
746 | |
747 | template<int N,int M,typename Dst> |
748 | void test_merge(Dst& dst,Dst& src) |
749 | { |
750 | if(&dst==&src)test_merge_same<N,M>(dst); |
751 | else test_merge_different<N,M>(dst,src); |
752 | } |
753 | |
754 | struct another_int_hash |
755 | { |
756 | std::size_t operator()(int x)const |
757 | { |
758 | return boost::hash<int>()(x)*2; |
759 | } |
760 | }; |
761 | |
762 | void test_merge() |
763 | { |
764 | typedef multi_index_container< |
765 | int, |
766 | indexed_by< |
767 | ordered_non_unique<identity<int> >, |
768 | hashed_non_unique<identity<int> >, |
769 | random_access<>, |
770 | sequenced<>, |
771 | ranked_non_unique<identity<int> > |
772 | > |
773 | > container1; |
774 | |
775 | typedef multi_index_container< |
776 | int, |
777 | indexed_by< |
778 | ordered_unique< |
779 | identity<int>, |
780 | std::greater<int> |
781 | >, |
782 | hashed_unique< |
783 | identity<int>, |
784 | another_int_hash |
785 | >, |
786 | random_access<>, |
787 | sequenced<>, |
788 | ranked_unique< |
789 | identity<int>, |
790 | std::greater<int> |
791 | > |
792 | > |
793 | > container2; |
794 | |
795 | container1 c1; |
796 | container2 c2; |
797 | for(int i=0;i<10;++i){ |
798 | c1.insert(x: i); |
799 | c2.insert(x: 2*i); |
800 | } |
801 | |
802 | test_merge<0,1>(dst&: c1,src&: c1); |
803 | test_merge<1,2>(dst&: c1,src&: c1); |
804 | test_merge<2,3>(dst&: c1,src&: c1); |
805 | test_merge<3,4>(dst&: c1,src&: c1); |
806 | test_merge<4,0>(dst&: c1,src&: c1); |
807 | test_merge<0,3>(dst&: c2,src&: c2); |
808 | test_merge<1,4>(dst&: c2,src&: c2); |
809 | test_merge<4,2>(dst&: c2,src&: c2); |
810 | |
811 | test_merge<0,1>(dst&: c1,src&: c2); |
812 | test_merge<1,2>(dst&: c1,src&: c2); |
813 | test_merge<2,3>(dst&: c1,src&: c2); |
814 | test_merge<3,4>(dst&: c1,src&: c2); |
815 | test_merge<4,0>(dst&: c1,src&: c2); |
816 | test_merge<0,3>(dst&: c2,src&: c1); |
817 | test_merge<1,4>(dst&: c2,src&: c1); |
818 | test_merge<4,2>(dst&: c2,src&: c1); |
819 | } |
820 | |
821 | void test_node_handling() |
822 | { |
823 | test_node_handle(); |
824 | test_transfer(); |
825 | test_merge(); |
826 | } |
827 | |