]>
Commit | Line | Data |
---|---|---|
20effc67 TL |
1 | /* Boost.MultiIndex test for node handling operations. |
2 | * | |
1e59de90 | 3 | * Copyright 2003-2021 Joaquin M Lopez Munoz. |
20effc67 TL |
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> | |
1e59de90 TL |
26 | #include <boost/type_traits/is_same.hpp> |
27 | #include <boost/type_traits/remove_reference.hpp> | |
20effc67 | 28 | #include <functional> |
1e59de90 TL |
29 | #include <iterator> |
30 | #include <utility> | |
31 | #include <vector> | |
20effc67 TL |
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(0); | |
55 | c.insert(1); | |
56 | c.insert(2); | |
57 | const int* addr0=&*c.find(0); | |
58 | const int* addr1=&*c.find(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(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(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(n2)); | |
80 | BOOST_TEST(n4.empty()); | |
81 | BOOST_TEST(allocator_count==1); | |
82 | ||
83 | n1=boost::move(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(1); | |
92 | BOOST_TEST(n5.value()==1); | |
93 | BOOST_TEST(&n5.value()==addr1); | |
94 | BOOST_TEST(allocator_count==2); | |
95 | ||
96 | n1.swap(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(n2,n3); | |
104 | BOOST_TEST(n2.empty()); | |
105 | BOOST_TEST(n3.empty()); | |
106 | BOOST_TEST(allocator_count==2); | |
107 | ||
108 | swap(n1,n2); | |
109 | BOOST_TEST(!n2.empty()); | |
110 | BOOST_TEST(&n2.value()==addr1); | |
111 | BOOST_TEST(allocator_count==2); | |
112 | ||
113 | swap(n1,n2); | |
114 | BOOST_TEST(&n1.value()==addr1); | |
115 | BOOST_TEST(n2.empty()); | |
116 | BOOST_TEST(allocator_count==2); | |
117 | ||
118 | n2=boost::move(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(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(n5); | |
131 | BOOST_TEST(n1.empty()); | |
132 | BOOST_TEST(element_count==1); | |
133 | BOOST_TEST(allocator_count==0); | |
134 | ||
135 | c.extract(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 */ | |
1e59de90 TL |
143 | (boost::tuples::length<typename boost::remove_reference<Index>:: |
144 | type::ctor_args>::value > 0) | |
20effc67 TL |
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 checked_extract( | |
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 checked_extract(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(i); | |
401 | } | |
402 | ||
403 | test_transfer(src0,dst01,dst11,dst21,dst31); | |
404 | test_transfer(src1,dst02,dst12,dst22,dst32); | |
405 | test_transfer(src2,dst03,dst13,dst23,dst33); | |
406 | test_transfer(src3,dst04,dst14,dst24,dst34); | |
407 | test_transfer(src4,dst00,dst10,dst20,dst30); | |
408 | BOOST_TEST(src.size()==8); | |
409 | } | |
410 | ||
1e59de90 TL |
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(i); | |
799 | c2.insert(2*i); | |
800 | } | |
801 | ||
802 | test_merge<0,1>(c1,c1); | |
803 | test_merge<1,2>(c1,c1); | |
804 | test_merge<2,3>(c1,c1); | |
805 | test_merge<3,4>(c1,c1); | |
806 | test_merge<4,0>(c1,c1); | |
807 | test_merge<0,3>(c2,c2); | |
808 | test_merge<1,4>(c2,c2); | |
809 | test_merge<4,2>(c2,c2); | |
810 | ||
811 | test_merge<0,1>(c1,c2); | |
812 | test_merge<1,2>(c1,c2); | |
813 | test_merge<2,3>(c1,c2); | |
814 | test_merge<3,4>(c1,c2); | |
815 | test_merge<4,0>(c1,c2); | |
816 | test_merge<0,3>(c2,c1); | |
817 | test_merge<1,4>(c2,c1); | |
818 | test_merge<4,2>(c2,c1); | |
819 | } | |
820 | ||
20effc67 TL |
821 | void test_node_handling() |
822 | { | |
823 | test_node_handle(); | |
824 | test_transfer(); | |
1e59de90 | 825 | test_merge(); |
20effc67 | 826 | } |