123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610 |
- // Boost.Bimap
- //
- // Copyright (c) 2006-2007 Matias Capeletto
- //
- // Distributed under the Boost Software License, Version 1.0.
- // (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- #ifndef LIBS_BIMAP_TEST_BIMAP_TEST_HPP
- #define LIBS_BIMAP_TEST_BIMAP_TEST_HPP
- #if defined(_MSC_VER)
- #pragma once
- #endif
- #include <boost/config.hpp>
- // std
- #include <cassert>
- #include <algorithm>
- #include <iterator>
- #include <boost/lambda/lambda.hpp>
- #include <boost/static_assert.hpp>
- #include <boost/type_traits/is_same.hpp>
- #include <boost/utility.hpp>
- #include <boost/next_prior.hpp>
- template< class Container, class Data >
- void test_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear();
- BOOST_CHECK( c.size() == 0 );
- BOOST_CHECK( c.empty() );
- c.insert( *d.begin() );
- c.insert( ++d.begin(),d.end() );
- BOOST_CHECK( c.size() == d.size() );
- BOOST_CHECK( c.size() <= c.max_size() );
- BOOST_CHECK( ! c.empty() );
- c.erase( c.begin() );
- BOOST_CHECK( c.size() == d.size() - 1 );
- c.erase( c.begin(), c.end() );
- BOOST_CHECK( c.empty() );
- c.insert( *d.begin() );
- BOOST_CHECK( c.size() == 1 );
- c.insert( c.begin(), *(++d.begin()) );
- BOOST_CHECK( c.size() == 2 );
- BOOST_CHECK( c.begin() != c.end() );
- }
- template< class Container, class Data >
- void test_sequence_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear();
- BOOST_CHECK( c.size() == 0 );
- BOOST_CHECK( c.empty() );
- c.push_front( * d.begin() );
- c.push_back ( *(++d.begin()) );
- BOOST_CHECK( c.front() == * c.begin() );
- BOOST_CHECK( c.back () == *(++c.begin()) );
- BOOST_CHECK( c.size() == 2 );
- BOOST_CHECK( c.size() <= c.max_size() );
- BOOST_CHECK( ! c.empty() );
- c.erase( c.begin() );
- BOOST_CHECK( c.size() == 1 );
- c.insert( c.begin(), *(++d.begin()) );
- c.erase( c.begin(), c.end() );
- BOOST_CHECK( c.empty() );
- c.push_front( *d.begin() );
- BOOST_CHECK( c.size() == 1 );
- BOOST_CHECK( c.begin() != c.end() );
- c.clear();
- BOOST_CHECK( c.empty() );
- // assign
-
- c.assign(d.begin(),d.end());
- BOOST_CHECK( c.size() == d.size() );
- BOOST_CHECK( std::equal( c.begin(), c.end(), d.begin() ) );
- c.assign(d.size(),*d.begin());
- BOOST_CHECK( c.size() == d.size() );
- BOOST_CHECK( *c.begin() == *d.begin() );
-
- // Check insert(IterPos,InputIter,InputIter)
-
- c.clear();
- c.insert( c.begin(), d.begin(), d.end() );
- c.insert( boost::next(c.begin(),2), d.begin(), d.end() );
-
- BOOST_CHECK( std::equal( boost::next(c.begin(),2)
- , boost::next(c.begin(),2+d.size()) , d.begin() ) );
- // Check resize
-
- c.clear() ;
- c.resize(4,*d.begin());
- BOOST_CHECK( c.size() == 4 );
- BOOST_CHECK( *c.begin() == *d.begin() ) ;
- BOOST_CHECK( c == c );
- BOOST_CHECK( ! ( c != c ) );
- BOOST_CHECK( ! ( c < c ) );
- BOOST_CHECK( ( c <= c ) );
- BOOST_CHECK( ! ( c > c ) );
- BOOST_CHECK( ( c >= c ) );
- }
- template< class Container, class Data >
- void test_vector_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear() ;
- c.reserve(2) ;
- BOOST_CHECK( c.capacity() >= 2 ) ;
- c.assign(d.begin(),d.end());
- BOOST_CHECK( c.capacity() >= c.size() ) ;
-
- BOOST_CHECK( c[0] == *d.begin() ) ;
- BOOST_CHECK( c.at(1) == *boost::next(d.begin()) );
-
- test_sequence_container(c,d) ;
- }
- template< class Container, class Data >
- void test_associative_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear();
- c.insert(d.begin(),d.end());
- for( typename Data::const_iterator di = d.begin(), de = d.end();
- di != de; ++di )
- {
- BOOST_CHECK( c.find(*di) != c.end() );
- }
- typename Data::const_iterator da = d.begin();
- typename Data::const_iterator db = ++d.begin();
- c.erase(*da);
- BOOST_CHECK( c.size() == d.size()-1 );
- BOOST_CHECK( c.count(*da) == 0 );
- BOOST_CHECK( c.count(*db) == 1 );
- BOOST_CHECK( c.find(*da) == c.end() );
- BOOST_CHECK( c.find(*db) != c.end() );
- BOOST_CHECK( c.equal_range(*db).first != c.end() );
- c.clear();
- BOOST_CHECK( c.equal_range(*da).first == c.end() );
- }
- template< class Container >
- void test_mapped_container(Container &)
- {
- typedef BOOST_DEDUCED_TYPENAME Container:: value_type value_type ;
- typedef BOOST_DEDUCED_TYPENAME Container:: key_type key_type ;
- typedef BOOST_DEDUCED_TYPENAME Container:: data_type data_type ;
- typedef BOOST_DEDUCED_TYPENAME Container::mapped_type mapped_type ;
- typedef BOOST_DEDUCED_TYPENAME
- boost::is_same< key_type
- , BOOST_DEDUCED_TYPENAME value_type::first_type
- >::type test_key_type;
- BOOST_STATIC_ASSERT(test_key_type::value);
- typedef BOOST_DEDUCED_TYPENAME
- boost::is_same< data_type
- , BOOST_DEDUCED_TYPENAME value_type::second_type
- >::type test_data_type;
- BOOST_STATIC_ASSERT(test_data_type::value);
- typedef BOOST_DEDUCED_TYPENAME
- boost::is_same< mapped_type
- , BOOST_DEDUCED_TYPENAME value_type::second_type
- >::type test_mapped_type;
- BOOST_STATIC_ASSERT(test_mapped_type::value);
- }
- template< class Container, class Data >
- void test_pair_associative_container(Container & c, const Data & d)
- {
- test_mapped_container(c);
- assert( d.size() > 2 );
- c.clear();
- c.insert(d.begin(),d.end());
- for( typename Data::const_iterator di = d.begin(), de = d.end();
- di != de; ++di )
- {
- BOOST_CHECK( c.find(di->first) != c.end() );
- }
- typename Data::const_iterator da = d.begin();
- typename Data::const_iterator db = ++d.begin();
- c.erase(da->first);
- BOOST_CHECK( c.size() == d.size()-1 );
- BOOST_CHECK( c.count(da->first) == 0 );
- BOOST_CHECK( c.count(db->first) == 1 );
- BOOST_CHECK( c.find(da->first) == c.end() );
- BOOST_CHECK( c.find(db->first) != c.end() );
- BOOST_CHECK( c.equal_range(db->first).first != c.end() );
- c.clear();
- BOOST_CHECK( c.equal_range(da->first).first == c.end() );
- }
- template< class Container, class Data >
- void test_simple_ordered_associative_container_equality(Container & c, const Data & d)
- {
- BOOST_CHECK( std::equal( c. begin(), c. end(), d. begin() ) );
- BOOST_CHECK( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
- BOOST_CHECK( c.lower_bound( *d.begin() ) == c.begin() );
- BOOST_CHECK( c.upper_bound( *d.begin() ) == ++c.begin() );
- }
- template< class Container, class Data >
- void test_simple_ordered_associative_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear();
- c.insert(d.begin(),d.end());
- for( typename Data::const_iterator di = d.begin(), de = d.end();
- di != de; ++di )
- {
- typename Container::const_iterator ci = c.find(*di);
- BOOST_CHECK( ci != c.end() );
- BOOST_CHECK( ! c.key_comp()(*ci,*di) );
- BOOST_CHECK( ! c.value_comp()(*ci,*di) );
- }
- test_simple_ordered_associative_container_equality(c, d);
- const Container & cr = c;
- test_simple_ordered_associative_container_equality(cr, d);
- BOOST_CHECK( c == c );
- BOOST_CHECK( ! ( c != c ) );
- BOOST_CHECK( ! ( c < c ) );
- BOOST_CHECK( ( c <= c ) );
- BOOST_CHECK( ! ( c > c ) );
- BOOST_CHECK( ( c >= c ) );
-
- /*
- BOOST_CHECK( c.range( *c.begin() <= ::boost::lambda::_1,
- ::boost::lambda::_1 <= *(++c.begin()) ).
- first == c.begin()
- );
- */
- }
- template< class Container, class Data >
- void test_simple_unordered_associative_container(Container & c, const Data & d)
- {
- c.clear();
- c.insert( d.begin(), d.end() );
- BOOST_CHECK( c.bucket_count() * c.max_load_factor() >= d.size() );
- BOOST_CHECK( c.max_bucket_count() >= c.bucket_count() );
- for( typename Data::const_iterator di = d.begin(), de = d.end() ;
- di != de ; ++di )
- {
- // non const
- {
- typename Container::size_type nb = c.bucket(*c.find(*di));
- BOOST_CHECK( c.begin(nb) != c.end(nb) );
- }
- // const
- {
- const Container & const_c = c;
- BOOST_CHECK(
- const_c.bucket_size(const_c.bucket(*di)) == 1
- );
- typename Container::size_type nb =
- const_c.bucket(*const_c.find(*di));
- BOOST_CHECK(
- const_c.begin(nb) != const_c.end(nb)
- );
- }
- }
- BOOST_CHECK( c.load_factor() < c.max_load_factor() );
- c.max_load_factor(0.75);
- BOOST_CHECK( c.max_load_factor() == 0.75 );
- c.rehash(10);
- }
- template< class Container, class Data >
- void test_pair_ordered_associative_container_equality(Container & c, const Data & d)
- {
- BOOST_CHECK( std::equal( c. begin(), c. end(), d. begin() ) );
- BOOST_CHECK( std::equal( c.rbegin(), c.rend(), d.rbegin() ) );
- BOOST_CHECK( c.lower_bound( d.begin()->first ) == c.begin() );
- BOOST_CHECK( c.upper_bound( d.begin()->first ) == ++c.begin() );
- }
- template< class Container, class Data >
- void test_pair_ordered_associative_container(Container & c, const Data & d)
- {
- assert( d.size() > 2 );
- c.clear();
- c.insert(d.begin(),d.end());
- for( typename Container::const_iterator ci = c.begin(), ce = c.end();
- ci != ce; ++ci )
- {
- typename Data::const_iterator di = d.find(ci->first);
- BOOST_CHECK( di != d.end() );
- BOOST_CHECK( ! c.key_comp()(di->first,ci->first) );
- BOOST_CHECK( ! c.value_comp()(*ci,*di) );
- }
- test_pair_ordered_associative_container_equality(c, d);
- const Container & cr = c;
- test_pair_ordered_associative_container_equality(cr, d);
- BOOST_CHECK( c.range( c.begin()->first <= ::boost::lambda::_1,
- ::boost::lambda::_1 <= (++c.begin())->first ).
- first == c.begin()
- );
- }
- template< class Container, class Data >
- void test_pair_unordered_associative_container(Container & c, const Data & d)
- {
- c.clear();
- c.insert( d.begin(), d.end() );
- BOOST_CHECK( c.bucket_count() * c.max_load_factor() >= d.size() );
- BOOST_CHECK( c.max_bucket_count() >= c.bucket_count() );
- for( typename Data::const_iterator di = d.begin(), de = d.end() ;
- di != de ; ++di )
- {
- // non const
- {
- typename Container::size_type nb =
- c.bucket(c.find(di->first)->first);
- BOOST_CHECK( c.begin(nb) != c.end(nb) );
- }
- // const
- {
- const Container & const_c = c;
- BOOST_CHECK( const_c.bucket_size(const_c.bucket(di->first)) == 1 );
- typename Container::size_type nb =
- const_c.bucket(const_c.find(di->first)->first);
- BOOST_CHECK( const_c.begin(nb) != const_c.end(nb) );
- }
- }
- BOOST_CHECK( c.load_factor() < c.max_load_factor() );
- c.max_load_factor(0.75);
- BOOST_CHECK( c.max_load_factor() == 0.75 );
- c.rehash(10);
- }
- template< class Container, class Data >
- void test_unique_container(Container & c, Data & d)
- {
- c.clear();
- c.insert(d.begin(),d.end());
- c.insert(*d.begin());
- BOOST_CHECK( c.size() == d.size() );
- }
- template< class Container, class Data >
- void test_non_unique_container(Container & c, Data & d)
- {
- c.clear();
- c.insert(d.begin(),d.end());
- c.insert(*d.begin());
- BOOST_CHECK( c.size() == (d.size()+1) );
- }
- template< class Bimap, class Data, class LeftData, class RightData >
- void test_basic_bimap( Bimap & b,
- const Data & d,
- const LeftData & ld, const RightData & rd)
- {
- using namespace boost::bimaps;
- test_container(b,d);
- BOOST_CHECK( & b.left == & b.template by<member_at::left >() );
- BOOST_CHECK( & b.right == & b.template by<member_at::right>() );
- test_container(b.left , ld);
- test_container(b.right, rd);
- }
- template< class LeftTag, class RightTag, class Bimap, class Data >
- void test_tagged_bimap(Bimap & b,
- const Data & d)
- {
- using namespace boost::bimaps;
- BOOST_CHECK( &b.left == & b.template by<LeftTag >() );
- BOOST_CHECK( &b.right == & b.template by<RightTag>() );
- b.clear();
- b.insert( *d.begin() );
- BOOST_CHECK(
- b.begin()->template get<LeftTag>() ==
- b.template by<RightTag>().begin()->template get<LeftTag>()
- );
- BOOST_CHECK(
- b.begin()->template get<RightTag>() ==
- b.template by<LeftTag>().begin()->template get<RightTag>()
- );
- // const test
- {
- const Bimap & bc = b;
- BOOST_CHECK( &bc.left == & bc.template by<LeftTag>() );
- BOOST_CHECK( &bc.right == & bc.template by<RightTag>() );
- BOOST_CHECK( bc.begin()->template get<LeftTag>() ==
- bc.template by<RightTag>().begin()->template get<LeftTag>() );
- BOOST_CHECK( bc.begin()->template get<RightTag>() ==
- bc.template by<LeftTag>().begin()->template get<RightTag>() );
- }
- }
- template< class Bimap, class Data, class LeftData, class RightData >
- void test_set_set_bimap(Bimap & b,
- const Data & d,
- const LeftData & ld, const RightData & rd)
- {
- using namespace boost::bimaps;
- test_basic_bimap(b,d,ld,rd);
- test_associative_container(b,d);
- test_simple_ordered_associative_container(b,d);
- test_pair_associative_container(b.left, ld);
- test_pair_ordered_associative_container(b.left, ld);
- test_unique_container(b.left, ld);
- test_pair_associative_container(b.right, rd);
- test_pair_ordered_associative_container(b.right, rd);
- test_unique_container(b.right, rd);
- }
- template< class Bimap, class Data, class LeftData, class RightData >
- void test_multiset_multiset_bimap(Bimap & b,
- const Data & d,
- const LeftData & ld, const RightData & rd)
- {
- using namespace boost::bimaps;
- test_basic_bimap(b,d,ld,rd);
- test_associative_container(b,d);
- test_simple_ordered_associative_container(b,d);
- test_pair_associative_container(b.left, ld);
- test_pair_ordered_associative_container(b.left, ld);
- test_non_unique_container(b.left, ld);
- test_pair_associative_container(b.right, rd);
- test_pair_ordered_associative_container(b.right, rd);
- test_non_unique_container(b.right, rd);
- }
- template< class Bimap, class Data, class LeftData, class RightData >
- void test_unordered_set_unordered_multiset_bimap(Bimap & b,
- const Data & d,
- const LeftData & ld,
- const RightData & rd)
- {
- using namespace boost::bimaps;
- test_basic_bimap(b,d,ld,rd);
- test_associative_container(b,d);
- test_simple_unordered_associative_container(b,d);
- test_pair_associative_container(b.left, ld);
- test_pair_unordered_associative_container(b.left, ld);
- test_unique_container(b.left, ld);
- test_pair_associative_container(b.right, rd);
- test_pair_unordered_associative_container(b.right, rd);
- // Caution, this side is a non unique container, but the other side is a
- // unique container so, the overall bimap is a unique one.
- test_unique_container(b.right, rd);
- }
- template< class Bimap, class Data>
- void test_bimap_init_copy_swap(const Data&d)
- {
- Bimap b1(d.begin(),d.end());
- Bimap b2( b1 );
- BOOST_CHECK( b1 == b2 );
-
- b2.clear();
- b2 = b1;
- BOOST_CHECK( b2 == b1 );
- b2.clear();
- b2.left = b1.left;
- BOOST_CHECK( b2 == b1 );
- b2.clear();
- b2.right = b1.right;
- BOOST_CHECK( b2 == b1 );
- b1.clear();
- b2.swap(b1);
- BOOST_CHECK( b2.empty() && !b1.empty() );
- b1.left.swap( b2.left );
- BOOST_CHECK( b1.empty() && !b2.empty() );
- b1.right.swap( b2.right );
- BOOST_CHECK( b2.empty() && !b1.empty() );
- }
- #endif // LIBS_BIMAP_TEST_BIMAP_TEST_HPP
|