ceph/src/boost/libs/bimap/test/test_bimap.hpp

   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 >
  30 void test_container(Container & c, const Data & d)
  31 {
  32     assert( d.size() > 2 );
  33
  34     c.clear();
  35
  36     BOOST_CHECK( c.size() == 0 );
  37     BOOST_CHECK( c.empty() );
  38
  39     c.insert( *d.begin() );
  40
  41     c.insert( ++d.begin(),d.end() );
  42
  43     BOOST_CHECK( c.size() == d.size() );
  44
  45     BOOST_CHECK( c.size() <= c.max_size() );
  46     BOOST_CHECK( ! c.empty() );
  47
  48     c.erase( c.begin() );
  49
  50     BOOST_CHECK( c.size() == d.size() - 1 );
  51
  52     c.erase( c.begin(), c.end() );
  53
  54     BOOST_CHECK( c.empty() );
  55
  56     c.insert( *d.begin() );
  57
  58     BOOST_CHECK( c.size() == 1 );
  59
  60     c.insert( c.begin(), *(++d.begin()) );
  61
  62     BOOST_CHECK( c.size() == 2 );
  63
  64     BOOST_CHECK( c.begin() != c.end() );
  65 }
  66
  67 template< class Container, class Data >
  68 void test_sequence_container(Container & c, const Data & d)
  69 {
  70     assert( d.size() > 2 );
  71
  72     c.clear();
  73
  74     BOOST_CHECK( c.size() == 0 );
  75     BOOST_CHECK( c.empty() );
  76
  77     c.push_front( *   d.begin()  );
  78     c.push_back ( *(++d.begin()) );
  79
  80     BOOST_CHECK( c.front() == *   c.begin()  );
  81     BOOST_CHECK( c.back () == *(++c.begin()) );
  82
  83     BOOST_CHECK( c.size() == 2 );
  84
  85     BOOST_CHECK( c.size() <= c.max_size() );
  86     BOOST_CHECK( ! c.empty() );
  87
  88     c.erase( c.begin() );
  89
  90     BOOST_CHECK( c.size() == 1 );
  91
  92     c.insert( c.begin(), *(++d.begin()) );
  93
  94     c.erase( c.begin(), c.end() );
  95
  96     BOOST_CHECK( c.empty() );
  97
  98     c.push_front( *d.begin() );
  99
 100     BOOST_CHECK( c.size() == 1 );
 101
 102     BOOST_CHECK( c.begin() != c.end() );
 103
 104     c.clear();
 105     BOOST_CHECK( c.empty() );
 106
 107     // assign
 108
 109     c.assign(d.begin(),d.end());
 110     BOOST_CHECK( c.size() == d.size() );
 111     BOOST_CHECK( std::equal( c.begin(), c.end(), d.begin() ) );
 112
 113     c.assign(d.size(),*d.begin());
 114     BOOST_CHECK( c.size() == d.size() );
 115     BOOST_CHECK( *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_CHECK( 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_CHECK( c.size() == 4 );
 131     BOOST_CHECK( *c.begin() == *d.begin() ) ;
 132
 133     BOOST_CHECK(     c == c   );
 134     BOOST_CHECK( ! ( c != c ) );
 135     BOOST_CHECK( ! ( c  < c ) );
 136     BOOST_CHECK(   ( c <= c ) );
 137     BOOST_CHECK( ! ( c  > c ) );
 138     BOOST_CHECK(   ( c >= c ) );
 139 }
 140
 141 template< class Container, class Data >
 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_CHECK( c.capacity() >= 2 ) ;
 149     c.assign(d.begin(),d.end());
 150     BOOST_CHECK( c.capacity() >= c.size() ) ;
 151
 152     BOOST_CHECK( c[0] == *d.begin() ) ;
 153     BOOST_CHECK( c.at(1) == *boost::next(d.begin()) );
 154
 155     test_sequence_container(c,d) ;
 156 }
 157
 158 template< class Container, class Data >
 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_CHECK( 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_CHECK( c.size() == d.size()-1 );
 178
 179     BOOST_CHECK( c.count(*da) == 0 );
 180     BOOST_CHECK( c.count(*db) == 1 );
 181
 182     BOOST_CHECK( c.find(*da) == c.end() );
 183     BOOST_CHECK( c.find(*db) != c.end() );
 184
 185     BOOST_CHECK( c.equal_range(*db).first != c.end() );
 186
 187     c.clear();
 188
 189     BOOST_CHECK( c.equal_range(*da).first == c.end() );
 190 }
 191
 192
 193 template< class 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 >
 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_CHECK( 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_CHECK( c.size() == d.size()-1 );
 242
 243     BOOST_CHECK( c.count(da->first) == 0 );
 244     BOOST_CHECK( c.count(db->first) == 1 );
 245
 246     BOOST_CHECK( c.find(da->first) == c.end() );
 247     BOOST_CHECK( c.find(db->first) != c.end() );
 248
 249     BOOST_CHECK( c.equal_range(db->first).first != c.end() );
 250
 251     c.clear();
 252
 253     BOOST_CHECK( c.equal_range(da->first).first == c.end() );
 254 }
 255
 256
 257 template< class Container, class Data >
 258 void test_simple_ordered_associative_container_equality(Container & c, const Data & d)
 259 {
 260     BOOST_CHECK( std::equal( c. begin(), c. end(), d. begin() ) );
 261     BOOST_CHECK( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
 262
 263     BOOST_CHECK( c.lower_bound( *d.begin() ) ==   c.begin() );
 264     BOOST_CHECK( c.upper_bound( *d.begin() ) == ++c.begin() );
 265 }
 266
 267 template< class Container, class Data >
 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_CHECK( ci != c.end() );
 280
 281         BOOST_CHECK( ! c.key_comp()(*ci,*di) );
 282         BOOST_CHECK( ! 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_CHECK(     c == c   );
 292     BOOST_CHECK( ! ( c != c ) );
 293     BOOST_CHECK( ! ( c  < c ) );
 294     BOOST_CHECK(   ( c <= c ) );
 295     BOOST_CHECK( ! ( c  > c ) );
 296     BOOST_CHECK(   ( c >= c ) );
 297
 298     /*
 299     BOOST_CHECK( 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 >
 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_CHECK( c.bucket_count() * c.max_load_factor() >= d.size() );
 313     BOOST_CHECK( 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_CHECK( c.begin(nb) != c.end(nb) );
 323         }
 324
 325         // const
 326         {
 327             const Container & const_c = c;
 328
 329             BOOST_CHECK(
 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_CHECK(
 337                 const_c.begin(nb) != const_c.end(nb)
 338             );
 339         }
 340     }
 341
 342
 343     BOOST_CHECK( c.load_factor() < c.max_load_factor() );
 344
 345     c.max_load_factor(0.75);
 346
 347     BOOST_CHECK( c.max_load_factor() == 0.75 );
 348
 349     c.rehash(10);
 350 }
 351
 352
 353 template< class Container, class Data >
 354 void test_pair_ordered_associative_container_equality(Container & c, const Data & d)
 355 {
 356     BOOST_CHECK( std::equal( c. begin(), c. end(), d. begin() ) );
 357     BOOST_CHECK( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
 358
 359     BOOST_CHECK( c.lower_bound( d.begin()->first ) ==   c.begin() );
 360     BOOST_CHECK( c.upper_bound( d.begin()->first ) == ++c.begin() );
 361 }
 362
 363 template< class Container, class Data >
 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_CHECK( di != d.end() );
 376         BOOST_CHECK( ! c.key_comp()(di->first,ci->first) );
 377         BOOST_CHECK( ! 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_CHECK( 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 >
 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_CHECK( c.bucket_count() * c.max_load_factor() >= d.size() );
 400     BOOST_CHECK( 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_CHECK( c.begin(nb) != c.end(nb) );
 411         }
 412
 413         // const
 414         {
 415             const Container & const_c = c;
 416
 417             BOOST_CHECK( 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_CHECK( const_c.begin(nb) != const_c.end(nb) );
 423         }
 424     }
 425
 426
 427     BOOST_CHECK( c.load_factor() < c.max_load_factor() );
 428
 429     c.max_load_factor(0.75);
 430
 431     BOOST_CHECK( c.max_load_factor() == 0.75 );
 432
 433     c.rehash(10);
 434 }
 435
 436
 437 template< class Container, class Data >
 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_CHECK( c.size() == d.size() );
 444 }
 445
 446 template< class Container, class Data >
 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_CHECK( c.size() == (d.size()+1) );
 453 }
 454
 455
 456
 457 template< class Bimap, class Data, class LeftData, class RightData >
 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_CHECK( & b.left  == & b.template by<member_at::left >() );
 467     BOOST_CHECK( & 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 >
 474 void test_tagged_bimap(Bimap & b,
 475                        const Data & d)
 476 {
 477     using namespace boost::bimaps;
 478
 479     BOOST_CHECK( &b.left  == & b.template by<LeftTag >() );
 480     BOOST_CHECK( &b.right == & b.template by<RightTag>() );
 481
 482     b.clear();
 483     b.insert( *d.begin() );
 484
 485     BOOST_CHECK(
 486         b.begin()->template get<LeftTag>() ==
 487             b.template by<RightTag>().begin()->template get<LeftTag>()
 488     );
 489
 490     BOOST_CHECK(
 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_CHECK( &bc.left  == & bc.template by<LeftTag>() );
 501     BOOST_CHECK( &bc.right == & bc.template by<RightTag>() );
 502
 503     BOOST_CHECK( bc.begin()->template get<LeftTag>() ==
 504                     bc.template by<RightTag>().begin()->template get<LeftTag>() );
 505
 506     BOOST_CHECK( 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 >
 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 >
 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 >
 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>
 580 void test_bimap_init_copy_swap(const Data&d)
 581 {
 582     Bimap b1(d.begin(),d.end());
 583     Bimap b2( b1 );
 584     BOOST_CHECK( b1 == b2 );
 585
 586     b2.clear();
 587     b2 = b1;
 588     BOOST_CHECK( b2 == b1 );
 589
 590     b2.clear();
 591     b2.left = b1.left;
 592     BOOST_CHECK( b2 == b1 );
 593
 594     b2.clear();
 595     b2.right = b1.right;
 596     BOOST_CHECK( b2 == b1 );
 597
 598     b1.clear();
 599     b2.swap(b1);
 600     BOOST_CHECK( b2.empty() && !b1.empty() );
 601
 602     b1.left.swap( b2.left );
 603     BOOST_CHECK( b1.empty() && !b2.empty() );
 604
 605     b1.right.swap( b2.right );
 606     BOOST_CHECK( b2.empty() && !b1.empty() );
 607 }
 608
 609 #endif // LIBS_BIMAP_TEST_BIMAP_TEST_HPP
 610