1 // Boost.Bimap
2 //
3 // Copyright (c) 2006-2007 Matias Capeletto
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8
9 #ifndef LIBS_BIMAP_TEST_BIMAP_TEST_HPP
10 #define LIBS_BIMAP_TEST_BIMAP_TEST_HPP
11
12 #if defined(_MSC_VER)
13 #pragma once
14 #endif
15
16 #include <boost/config.hpp>
17
18 // std
19 #include <cassert>
20 #include <algorithm>
21 #include <iterator>
22
23 #include <boost/lambda/lambda.hpp>
24 #include <boost/static_assert.hpp>
25 #include <boost/type_traits/is_same.hpp>
26 #include <boost/utility.hpp>
27 #include <boost/next_prior.hpp>
28
29 template< class Container, class Data >
test_container(Container & c,const Data & d)30 void test_container(Container & c, const Data & d)
31 {
32 assert( d.size() > 2 );
33
34 c.clear();
35
36 BOOST_TEST( c.size() == 0 );
37 BOOST_TEST( c.empty() );
38
39 c.insert( *d.begin() );
40
41 c.insert( ++d.begin(),d.end() );
42
43 BOOST_TEST( c.size() == d.size() );
44
45 BOOST_TEST( c.size() <= c.max_size() );
46 BOOST_TEST( ! c.empty() );
47
48 c.erase( c.begin() );
49
50 BOOST_TEST( c.size() == d.size() - 1 );
51
52 c.erase( c.begin(), c.end() );
53
54 BOOST_TEST( c.empty() );
55
56 c.insert( *d.begin() );
57
58 BOOST_TEST( c.size() == 1 );
59
60 c.insert( c.begin(), *(++d.begin()) );
61
62 BOOST_TEST( c.size() == 2 );
63
64 BOOST_TEST( c.begin() != c.end() );
65 }
66
67 template< class Container, class Data >
test_sequence_container(Container & c,const Data & d)68 void test_sequence_container(Container & c, const Data & d)
69 {
70 assert( d.size() > 2 );
71
72 c.clear();
73
74 BOOST_TEST( c.size() == 0 );
75 BOOST_TEST( c.empty() );
76
77 c.push_front( * d.begin() );
78 c.push_back ( *(++d.begin()) );
79
80 BOOST_TEST( c.front() == * c.begin() );
81 BOOST_TEST( c.back () == *(++c.begin()) );
82
83 BOOST_TEST( c.size() == 2 );
84
85 BOOST_TEST( c.size() <= c.max_size() );
86 BOOST_TEST( ! c.empty() );
87
88 c.erase( c.begin() );
89
90 BOOST_TEST( c.size() == 1 );
91
92 c.insert( c.begin(), *(++d.begin()) );
93
94 c.erase( c.begin(), c.end() );
95
96 BOOST_TEST( c.empty() );
97
98 c.push_front( *d.begin() );
99
100 BOOST_TEST( c.size() == 1 );
101
102 BOOST_TEST( c.begin() != c.end() );
103
104 c.clear();
105 BOOST_TEST( c.empty() );
106
107 // assign
108
109 c.assign(d.begin(),d.end());
110 BOOST_TEST( c.size() == d.size() );
111 BOOST_TEST( std::equal( c.begin(), c.end(), d.begin() ) );
112
113 c.assign(d.size(),*d.begin());
114 BOOST_TEST( c.size() == d.size() );
115 BOOST_TEST( *c.begin() == *d.begin() );
116
117 // Check insert(IterPos,InputIter,InputIter)
118
119 c.clear();
120 c.insert( c.begin(), d.begin(), d.end() );
121 c.insert( boost::next(c.begin(),2), d.begin(), d.end() );
122
123 BOOST_TEST( std::equal( boost::next(c.begin(),2)
124 , boost::next(c.begin(),2+d.size()) , d.begin() ) );
125
126 // Check resize
127
128 c.clear() ;
129 c.resize(4,*d.begin());
130 BOOST_TEST( c.size() == 4 );
131 BOOST_TEST( *c.begin() == *d.begin() ) ;
132
133 BOOST_TEST( c == c );
134 BOOST_TEST( ! ( c != c ) );
135 BOOST_TEST( ! ( c < c ) );
136 BOOST_TEST( ( c <= c ) );
137 BOOST_TEST( ! ( c > c ) );
138 BOOST_TEST( ( c >= c ) );
139 }
140
141 template< class Container, class Data >
test_vector_container(Container & c,const Data & d)142 void test_vector_container(Container & c, const Data & d)
143 {
144 assert( d.size() > 2 );
145
146 c.clear() ;
147 c.reserve(2) ;
148 BOOST_TEST( c.capacity() >= 2 ) ;
149 c.assign(d.begin(),d.end());
150 BOOST_TEST( c.capacity() >= c.size() ) ;
151
152 BOOST_TEST( c[0] == *d.begin() ) ;
153 BOOST_TEST( c.at(1) == *boost::next(d.begin()) );
154
155 test_sequence_container(c,d) ;
156 }
157
158 template< class Container, class Data >
test_associative_container(Container & c,const Data & d)159 void test_associative_container(Container & c, const Data & d)
160 {
161 assert( d.size() > 2 );
162
163 c.clear();
164 c.insert(d.begin(),d.end());
165
166 for( typename Data::const_iterator di = d.begin(), de = d.end();
167 di != de; ++di )
168 {
169 BOOST_TEST( c.find(*di) != c.end() );
170 }
171
172 typename Data::const_iterator da = d.begin();
173 typename Data::const_iterator db = ++d.begin();
174
175 c.erase(*da);
176
177 BOOST_TEST( c.size() == d.size()-1 );
178
179 BOOST_TEST( c.count(*da) == 0 );
180 BOOST_TEST( c.count(*db) == 1 );
181
182 BOOST_TEST( c.find(*da) == c.end() );
183 BOOST_TEST( c.find(*db) != c.end() );
184
185 BOOST_TEST( c.equal_range(*db).first != c.end() );
186
187 c.clear();
188
189 BOOST_TEST( c.equal_range(*da).first == c.end() );
190 }
191
192
193 template< class Container >
test_mapped_container(Container &)194 void test_mapped_container(Container &)
195 {
196 typedef BOOST_DEDUCED_TYPENAME Container:: value_type value_type ;
197 typedef BOOST_DEDUCED_TYPENAME Container:: key_type key_type ;
198 typedef BOOST_DEDUCED_TYPENAME Container:: data_type data_type ;
199 typedef BOOST_DEDUCED_TYPENAME Container::mapped_type mapped_type ;
200
201 typedef BOOST_DEDUCED_TYPENAME
202 boost::is_same< key_type
203 , BOOST_DEDUCED_TYPENAME value_type::first_type
204 >::type test_key_type;
205 BOOST_STATIC_ASSERT(test_key_type::value);
206
207 typedef BOOST_DEDUCED_TYPENAME
208 boost::is_same< data_type
209 , BOOST_DEDUCED_TYPENAME value_type::second_type
210 >::type test_data_type;
211 BOOST_STATIC_ASSERT(test_data_type::value);
212
213 typedef BOOST_DEDUCED_TYPENAME
214 boost::is_same< mapped_type
215 , BOOST_DEDUCED_TYPENAME value_type::second_type
216 >::type test_mapped_type;
217 BOOST_STATIC_ASSERT(test_mapped_type::value);
218 }
219
220 template< class Container, class Data >
test_pair_associative_container(Container & c,const Data & d)221 void test_pair_associative_container(Container & c, const Data & d)
222 {
223 test_mapped_container(c);
224
225 assert( d.size() > 2 );
226
227 c.clear();
228 c.insert(d.begin(),d.end());
229
230 for( typename Data::const_iterator di = d.begin(), de = d.end();
231 di != de; ++di )
232 {
233 BOOST_TEST( c.find(di->first) != c.end() );
234 }
235
236 typename Data::const_iterator da = d.begin();
237 typename Data::const_iterator db = ++d.begin();
238
239 c.erase(da->first);
240
241 BOOST_TEST( c.size() == d.size()-1 );
242
243 BOOST_TEST( c.count(da->first) == 0 );
244 BOOST_TEST( c.count(db->first) == 1 );
245
246 BOOST_TEST( c.find(da->first) == c.end() );
247 BOOST_TEST( c.find(db->first) != c.end() );
248
249 BOOST_TEST( c.equal_range(db->first).first != c.end() );
250
251 c.clear();
252
253 BOOST_TEST( c.equal_range(da->first).first == c.end() );
254 }
255
256
257 template< class Container, class Data >
test_simple_ordered_associative_container_equality(Container & c,const Data & d)258 void test_simple_ordered_associative_container_equality(Container & c, const Data & d)
259 {
260 BOOST_TEST( std::equal( c. begin(), c. end(), d. begin() ) );
261 BOOST_TEST( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
262
263 BOOST_TEST( c.lower_bound( *d.begin() ) == c.begin() );
264 BOOST_TEST( c.upper_bound( *d.begin() ) == ++c.begin() );
265 }
266
267 template< class Container, class Data >
test_simple_ordered_associative_container(Container & c,const Data & d)268 void test_simple_ordered_associative_container(Container & c, const Data & d)
269 {
270 assert( d.size() > 2 );
271
272 c.clear();
273 c.insert(d.begin(),d.end());
274
275 for( typename Data::const_iterator di = d.begin(), de = d.end();
276 di != de; ++di )
277 {
278 typename Container::const_iterator ci = c.find(*di);
279 BOOST_TEST( ci != c.end() );
280
281 BOOST_TEST( ! c.key_comp()(*ci,*di) );
282 BOOST_TEST( ! c.value_comp()(*ci,*di) );
283 }
284
285 test_simple_ordered_associative_container_equality(c, d);
286
287 const Container & cr = c;
288
289 test_simple_ordered_associative_container_equality(cr, d);
290
291 BOOST_TEST( c == c );
292 BOOST_TEST( ! ( c != c ) );
293 BOOST_TEST( ! ( c < c ) );
294 BOOST_TEST( ( c <= c ) );
295 BOOST_TEST( ! ( c > c ) );
296 BOOST_TEST( ( c >= c ) );
297
298 /*
299 BOOST_TEST( c.range( *c.begin() <= ::boost::lambda::_1,
300 ::boost::lambda::_1 <= *(++c.begin()) ).
301 first == c.begin()
302 );
303 */
304 }
305
306 template< class Container, class Data >
test_simple_unordered_associative_container(Container & c,const Data & d)307 void test_simple_unordered_associative_container(Container & c, const Data & d)
308 {
309 c.clear();
310 c.insert( d.begin(), d.end() );
311
312 BOOST_TEST( c.bucket_count() * c.max_load_factor() >= d.size() );
313 BOOST_TEST( c.max_bucket_count() >= c.bucket_count() );
314
315 for( typename Data::const_iterator di = d.begin(), de = d.end() ;
316 di != de ; ++di )
317 {
318 // non const
319 {
320 typename Container::size_type nb = c.bucket(*c.find(*di));
321
322 BOOST_TEST( c.begin(nb) != c.end(nb) );
323 }
324
325 // const
326 {
327 const Container & const_c = c;
328
329 BOOST_TEST(
330 const_c.bucket_size(const_c.bucket(*di)) == 1
331 );
332
333 typename Container::size_type nb =
334 const_c.bucket(*const_c.find(*di));
335
336 BOOST_TEST(
337 const_c.begin(nb) != const_c.end(nb)
338 );
339 }
340 }
341
342
343 BOOST_TEST( c.load_factor() < c.max_load_factor() );
344
345 c.max_load_factor(0.75);
346
347 BOOST_TEST( c.max_load_factor() == 0.75 );
348
349 c.rehash(10);
350 }
351
352
353 template< class Container, class Data >
test_pair_ordered_associative_container_equality(Container & c,const Data & d)354 void test_pair_ordered_associative_container_equality(Container & c, const Data & d)
355 {
356 BOOST_TEST( std::equal( c. begin(), c. end(), d. begin() ) );
357 BOOST_TEST( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
358
359 BOOST_TEST( c.lower_bound( d.begin()->first ) == c.begin() );
360 BOOST_TEST( c.upper_bound( d.begin()->first ) == ++c.begin() );
361 }
362
363 template< class Container, class Data >
test_pair_ordered_associative_container(Container & c,const Data & d)364 void test_pair_ordered_associative_container(Container & c, const Data & d)
365 {
366 assert( d.size() > 2 );
367
368 c.clear();
369 c.insert(d.begin(),d.end());
370
371 for( typename Container::const_iterator ci = c.begin(), ce = c.end();
372 ci != ce; ++ci )
373 {
374 typename Data::const_iterator di = d.find(ci->first);
375 BOOST_TEST( di != d.end() );
376 BOOST_TEST( ! c.key_comp()(di->first,ci->first) );
377 BOOST_TEST( ! c.value_comp()(*ci,*di) );
378 }
379
380 test_pair_ordered_associative_container_equality(c, d);
381
382 const Container & cr = c;
383
384 test_pair_ordered_associative_container_equality(cr, d);
385
386 BOOST_TEST( c.range( c.begin()->first <= ::boost::lambda::_1,
387 ::boost::lambda::_1 <= (++c.begin())->first ).
388 first == c.begin()
389 );
390 }
391
392
393 template< class Container, class Data >
test_pair_unordered_associative_container(Container & c,const Data & d)394 void test_pair_unordered_associative_container(Container & c, const Data & d)
395 {
396 c.clear();
397 c.insert( d.begin(), d.end() );
398
399 BOOST_TEST( c.bucket_count() * c.max_load_factor() >= d.size() );
400 BOOST_TEST( c.max_bucket_count() >= c.bucket_count() );
401
402 for( typename Data::const_iterator di = d.begin(), de = d.end() ;
403 di != de ; ++di )
404 {
405 // non const
406 {
407 typename Container::size_type nb =
408 c.bucket(c.find(di->first)->first);
409
410 BOOST_TEST( c.begin(nb) != c.end(nb) );
411 }
412
413 // const
414 {
415 const Container & const_c = c;
416
417 BOOST_TEST( const_c.bucket_size(const_c.bucket(di->first)) == 1 );
418
419 typename Container::size_type nb =
420 const_c.bucket(const_c.find(di->first)->first);
421
422 BOOST_TEST( const_c.begin(nb) != const_c.end(nb) );
423 }
424 }
425
426
427 BOOST_TEST( c.load_factor() < c.max_load_factor() );
428
429 c.max_load_factor(0.75);
430
431 BOOST_TEST( c.max_load_factor() == 0.75 );
432
433 c.rehash(10);
434 }
435
436
437 template< class Container, class Data >
test_unique_container(Container & c,Data & d)438 void test_unique_container(Container & c, Data & d)
439 {
440 c.clear();
441 c.insert(d.begin(),d.end());
442 c.insert(*d.begin());
443 BOOST_TEST( c.size() == d.size() );
444 }
445
446 template< class Container, class Data >
test_non_unique_container(Container & c,Data & d)447 void test_non_unique_container(Container & c, Data & d)
448 {
449 c.clear();
450 c.insert(d.begin(),d.end());
451 c.insert(*d.begin());
452 BOOST_TEST( c.size() == (d.size()+1) );
453 }
454
455
456
457 template< class Bimap, class Data, class LeftData, class RightData >
test_basic_bimap(Bimap & b,const Data & d,const LeftData & ld,const RightData & rd)458 void test_basic_bimap( Bimap & b,
459 const Data & d,
460 const LeftData & ld, const RightData & rd)
461 {
462 using namespace boost::bimaps;
463
464 test_container(b,d);
465
466 BOOST_TEST( & b.left == & b.template by<member_at::left >() );
467 BOOST_TEST( & b.right == & b.template by<member_at::right>() );
468
469 test_container(b.left , ld);
470 test_container(b.right, rd);
471 }
472
473 template< class LeftTag, class RightTag, class Bimap, class Data >
test_tagged_bimap(Bimap & b,const Data & d)474 void test_tagged_bimap(Bimap & b,
475 const Data & d)
476 {
477 using namespace boost::bimaps;
478
479 BOOST_TEST( &b.left == & b.template by<LeftTag >() );
480 BOOST_TEST( &b.right == & b.template by<RightTag>() );
481
482 b.clear();
483 b.insert( *d.begin() );
484
485 BOOST_TEST(
486 b.begin()->template get<LeftTag>() ==
487 b.template by<RightTag>().begin()->template get<LeftTag>()
488 );
489
490 BOOST_TEST(
491 b.begin()->template get<RightTag>() ==
492 b.template by<LeftTag>().begin()->template get<RightTag>()
493 );
494
495 // const test
496 {
497
498 const Bimap & bc = b;
499
500 BOOST_TEST( &bc.left == & bc.template by<LeftTag>() );
501 BOOST_TEST( &bc.right == & bc.template by<RightTag>() );
502
503 BOOST_TEST( bc.begin()->template get<LeftTag>() ==
504 bc.template by<RightTag>().begin()->template get<LeftTag>() );
505
506 BOOST_TEST( bc.begin()->template get<RightTag>() ==
507 bc.template by<LeftTag>().begin()->template get<RightTag>() );
508 }
509 }
510
511
512 template< class Bimap, class Data, class LeftData, class RightData >
test_set_set_bimap(Bimap & b,const Data & d,const LeftData & ld,const RightData & rd)513 void test_set_set_bimap(Bimap & b,
514 const Data & d,
515 const LeftData & ld, const RightData & rd)
516 {
517 using namespace boost::bimaps;
518
519 test_basic_bimap(b,d,ld,rd);
520
521 test_associative_container(b,d);
522 test_simple_ordered_associative_container(b,d);
523
524 test_pair_associative_container(b.left, ld);
525 test_pair_ordered_associative_container(b.left, ld);
526 test_unique_container(b.left, ld);
527
528 test_pair_associative_container(b.right, rd);
529 test_pair_ordered_associative_container(b.right, rd);
530 test_unique_container(b.right, rd);
531
532 }
533
534
535 template< class Bimap, class Data, class LeftData, class RightData >
test_multiset_multiset_bimap(Bimap & b,const Data & d,const LeftData & ld,const RightData & rd)536 void test_multiset_multiset_bimap(Bimap & b,
537 const Data & d,
538 const LeftData & ld, const RightData & rd)
539 {
540 using namespace boost::bimaps;
541
542 test_basic_bimap(b,d,ld,rd);
543 test_associative_container(b,d);
544 test_simple_ordered_associative_container(b,d);
545
546 test_pair_associative_container(b.left, ld);
547 test_pair_ordered_associative_container(b.left, ld);
548 test_non_unique_container(b.left, ld);
549
550 test_pair_associative_container(b.right, rd);
551 test_pair_ordered_associative_container(b.right, rd);
552 test_non_unique_container(b.right, rd);
553 }
554
555 template< class Bimap, class Data, class LeftData, class RightData >
test_unordered_set_unordered_multiset_bimap(Bimap & b,const Data & d,const LeftData & ld,const RightData & rd)556 void test_unordered_set_unordered_multiset_bimap(Bimap & b,
557 const Data & d,
558 const LeftData & ld,
559 const RightData & rd)
560 {
561 using namespace boost::bimaps;
562
563 test_basic_bimap(b,d,ld,rd);
564 test_associative_container(b,d);
565 test_simple_unordered_associative_container(b,d);
566
567 test_pair_associative_container(b.left, ld);
568 test_pair_unordered_associative_container(b.left, ld);
569 test_unique_container(b.left, ld);
570
571 test_pair_associative_container(b.right, rd);
572 test_pair_unordered_associative_container(b.right, rd);
573
574 // Caution, this side is a non unique container, but the other side is a
575 // unique container so, the overall bimap is a unique one.
576 test_unique_container(b.right, rd);
577 }
578
579 template< class Bimap, class Data>
test_bimap_init_copy_swap(const Data & d)580 void test_bimap_init_copy_swap(const Data&d)
581 {
582 Bimap b1(d.begin(),d.end());
583 Bimap b2( b1 );
584 BOOST_TEST( b1 == b2 );
585
586 b2.clear();
587 b2 = b1;
588 BOOST_TEST( b2 == b1 );
589
590 b2.clear();
591 b2.left = b1.left;
592 BOOST_TEST( b2 == b1 );
593
594 b2.clear();
595 b2.right = b1.right;
596 BOOST_TEST( b2 == b1 );
597
598 b1.clear();
599 b2.swap(b1);
600 BOOST_TEST( b2.empty() && !b1.empty() );
601
602 b1.left.swap( b2.left );
603 BOOST_TEST( b1.empty() && !b2.empty() );
604
605 b1.right.swap( b2.right );
606 BOOST_TEST( b2.empty() && !b1.empty() );
607 }
608
609 #endif // LIBS_BIMAP_TEST_BIMAP_TEST_HPP
610
611