123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372 |
- /////////////////////////////////////////////////////////////////////////////
- //
- // (C) Copyright Olaf Krzikalla 2004-2006.
- // (C) Copyright Ion Gaztanaga 2006-2013.
- //
- // 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)
- //
- // See http://www.boost.org/libs/intrusive for documentation.
- //
- /////////////////////////////////////////////////////////////////////////////
- #include <boost/container/vector.hpp> //vector
- #include <boost/intrusive/detail/config_begin.hpp>
- #include "common_functors.hpp"
- #include <boost/intrusive/options.hpp>
- #include <boost/intrusive/detail/mpl.hpp>
- #include <boost/detail/lightweight_test.hpp>
- #include "test_macros.hpp"
- #include "test_container.hpp"
- namespace boost{
- namespace intrusive{
- namespace test{
- BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_splay, splay)
- BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_rebalance, rebalance)
- BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(has_insert_before, insert_before)
- BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_treap, priority_comp)
- template<class ContainerDefiner>
- struct test_generic_assoc
- {
- typedef typename ContainerDefiner::value_cont_type value_cont_type;
- static void test_all(value_cont_type&);
- static void test_root(value_cont_type&);
- static void test_clone(value_cont_type&);
- static void test_insert_erase_burst();
- static void test_container_from_end(value_cont_type&, detail::true_type);
- static void test_container_from_end(value_cont_type&, detail::false_type) {}
- static void test_splay_up(value_cont_type&, detail::true_type);
- static void test_splay_up(value_cont_type&, detail::false_type) {}
- static void test_splay_down(value_cont_type&, detail::true_type);
- static void test_splay_down(value_cont_type&, detail::false_type) {}
- static void test_rebalance(value_cont_type&, detail::true_type);
- static void test_rebalance(value_cont_type&, detail::false_type) {}
- static void test_insert_before(value_cont_type&, detail::true_type);
- static void test_insert_before(value_cont_type&, detail::false_type) {}
- static void test_container_from_iterator(value_cont_type&, detail::true_type);
- static void test_container_from_iterator(value_cont_type&, detail::false_type) {}
- };
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::
- test_container_from_iterator(value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- assoc_type testset(values.begin(), values.end());
- typedef typename assoc_type::iterator it_type;
- typedef typename assoc_type::const_iterator cit_type;
- typedef typename assoc_type::size_type sz_type;
- sz_type sz = testset.size();
- for(it_type b(testset.begin()), e(testset.end()); b != e; ++b)
- {
- assoc_type &s = assoc_type::container_from_iterator(b);
- const assoc_type &cs = assoc_type::container_from_iterator(cit_type(b));
- BOOST_TEST(&s == &cs);
- BOOST_TEST(&s == &testset);
- s.erase(b);
- BOOST_TEST(testset.size() == (sz-1));
- s.insert(*b);
- BOOST_TEST(testset.size() == sz);
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_insert_erase_burst()
- {
- //value_cont_type values;
- const std::size_t MaxValues = 200;
- value_cont_type values(MaxValues);
- for(std::size_t i = 0; i != MaxValues; ++i){
- (&values[i])->value_ = i;
- }
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- typedef typename assoc_type::iterator iterator;
- { //Ordered insertion + erasure
- assoc_type testset (values.begin(), values.begin() + values.size());
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
- testset.check();
- iterator it(testset.begin()), itend(testset.end());
- for(std::size_t i = 0; it != itend; ++i){
- BOOST_TEST(&*it == &values[i]);
- it = testset.erase(it);
- testset.check();
- }
- BOOST_TEST(testset.empty());
- }
- { //Now random insertions + erasure
- assoc_type testset;
- typedef typename value_cont_type::iterator vec_iterator;
- boost::container::vector<vec_iterator> it_vector;
- //Random insertion
- for(vec_iterator it(values.begin()), itend(values.end())
- ; it != itend
- ; ++it){
- it_vector.push_back(it);
- }
- for(std::size_t i = 0; i != MaxValues; ++i){
- testset.insert(*it_vector[i]);
- testset.check();
- }
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
- //Random erasure
- random_shuffle(it_vector.begin(), it_vector.end());
- for(std::size_t i = 0; i != MaxValues; ++i){
- testset.erase(testset.iterator_to(*it_vector[i]));
- testset.check();
- }
- BOOST_TEST(testset.empty());
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_all(value_cont_type& values)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- test_root(values);
- test_clone(values);
- test_container_from_end(values, detail::bool_< assoc_type::has_container_from_iterator >());
- test_splay_up(values, detail::bool_< has_splay< assoc_type >::value >());
- test_splay_down(values, detail::bool_< has_splay< assoc_type >::value >());
- test_rebalance(values, detail::bool_< has_rebalance< assoc_type >::value >());
- test_insert_before(values, detail::bool_< has_insert_before< assoc_type >::value >());
- test_insert_erase_burst();
- test_container_from_iterator(values, detail::bool_< assoc_type::has_container_from_iterator >());
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_root(value_cont_type& values)
- {
- typedef typename ContainerDefiner::template container<>::type assoc_type;
- typedef typename assoc_type::iterator iterator;
- typedef typename assoc_type::const_iterator const_iterator;
- assoc_type testset1;
- const assoc_type &ctestset1 = testset1;;
- BOOST_TEST( testset1.root() == testset1.end());
- BOOST_TEST(ctestset1.root() == ctestset1.cend());
- BOOST_TEST( testset1.croot() == ctestset1.cend());
- testset1.insert(values.begin(), values.begin() + values.size());
- iterator i = testset1.root();
- iterator i2(i);
- BOOST_TEST( i.go_parent().go_parent() == i2);
- const_iterator ci = ctestset1.root();
- const_iterator ci2(ci);
- BOOST_TEST( ci.go_parent().go_parent() == ci2);
- ci = testset1.croot();
- ci2 = ci;
- BOOST_TEST( ci.go_parent().go_parent() == ci2);
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_clone(value_cont_type& values)
- {
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- typedef typename assoc_type::value_type value_type;
- typedef typename assoc_type::size_type size_type;
- assoc_type testset1 (values.begin(), values.begin() + values.size());
- assoc_type testset2;
- size_type const testset1_oldsize = testset1.size();
- testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
- BOOST_TEST (testset1.size() == testset1_oldsize);
- BOOST_TEST (testset2 == testset1);
- testset2.clear_and_dispose(test::delete_disposer<value_type>());
- BOOST_TEST (testset2.empty());
- //Now test move clone
- testset2.clone_from(boost::move(testset1), test::new_nonconst_cloner<value_type>(), test::delete_disposer<value_type>());
- BOOST_TEST (testset2 == testset1);
- testset2.clear_and_dispose(test::delete_disposer<value_type>());
- BOOST_TEST (testset2.empty());
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>
- ::test_container_from_end(value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- assoc_type testset (values.begin(), values.begin() + values.size());
- BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.end()));
- BOOST_TEST (testset == assoc_type::container_from_end_iterator(testset.cend()));
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_splay_up
- (value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- typedef typename assoc_type::iterator iterator;
- typedef value_cont_type orig_set_t;
- std::size_t num_values;
- orig_set_t original_testset;
- {
- assoc_type testset (values.begin(), values.end());
- num_values = testset.size();
- original_testset = value_cont_type(testset.begin(), testset.end());
- }
- for(std::size_t i = 0; i != num_values; ++i){
- assoc_type testset (values.begin(), values.end());
- {
- iterator it = testset.begin();
- for(std::size_t j = 0; j != i; ++j, ++it){}
- testset.splay_up(it);
- }
- BOOST_TEST (testset.size() == num_values);
- iterator it = testset.begin();
- for( typename orig_set_t::const_iterator origit = original_testset.begin()
- , origitend = original_testset.end()
- ; origit != origitend
- ; ++origit, ++it){
- BOOST_TEST(*origit == *it);
- }
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_splay_down
- (value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- typedef typename assoc_type::iterator iterator;
- typedef value_cont_type orig_set_t;
- std::size_t num_values;
- orig_set_t original_testset;
- {
- assoc_type testset (values.begin(), values.end());
- num_values = testset.size();
- original_testset = value_cont_type(testset.begin(), testset.end());
- }
- for(std::size_t i = 0; i != num_values; ++i){
- assoc_type testset (values.begin(), values.end());
- BOOST_TEST(testset.size() == num_values);
- {
- iterator it = testset.begin();
- for(std::size_t j = 0; j != i; ++j, ++it){}
- BOOST_TEST(*it == *testset.splay_down(*it));
- }
- BOOST_TEST (testset.size() == num_values);
- iterator it = testset.begin();
- for( typename orig_set_t::const_iterator origit = original_testset.begin()
- , origitend = original_testset.end()
- ; origit != origitend
- ; ++origit, ++it){
- BOOST_TEST(*origit == *it);
- }
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_rebalance
- (value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- typedef value_cont_type orig_set_t;
- orig_set_t original_testset;
- {
- assoc_type testset (values.begin(), values.end());
- original_testset.assign(testset.begin(), testset.end());
- }
- {
- assoc_type testset(values.begin(), values.end());
- testset.rebalance();
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
- }
- {
- std::size_t numdata;
- {
- assoc_type testset(values.begin(), values.end());
- numdata = testset.size();
- }
- for(int i = 0; i != (int)numdata; ++i){
- assoc_type testset(values.begin(), values.end());
- typename assoc_type::iterator it = testset.begin();
- for(int j = 0; j != i; ++j) ++it;
- testset.rebalance_subtree(it);
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(original_testset, testset.begin());
- }
- }
- }
- template<class ContainerDefiner>
- void test_generic_assoc<ContainerDefiner>::test_insert_before
- (value_cont_type& values, detail::true_type)
- {
- typedef typename ContainerDefiner::template container
- <>::type assoc_type;
- {
- assoc_type testset;
- typedef typename value_cont_type::iterator vec_iterator;
- for(vec_iterator it(values.begin()), itend(values.end())
- ; it != itend
- ; ++it){
- testset.push_back(*it);
- }
- BOOST_TEST(testset.size() == values.size());
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
- }
- {
- assoc_type testset;
- typedef typename value_cont_type::iterator vec_iterator;
- for(vec_iterator it(--values.end()); true; --it){
- testset.push_front(*it);
- if(it == values.begin()){
- break;
- }
- }
- BOOST_TEST(testset.size() == values.size());
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
- }
- {
- assoc_type testset;
- typedef typename value_cont_type::iterator vec_iterator;
- typename assoc_type::iterator it_pos =
- testset.insert_before(testset.end(), *values.rbegin());
- testset.insert_before(testset.begin(), *values.begin());
- for(vec_iterator it(++values.begin()), itend(--values.end())
- ; it != itend
- ; ++it){
- testset.insert_before(it_pos, *it);
- }
- BOOST_TEST(testset.size() == values.size());
- TEST_INTRUSIVE_SEQUENCE_EXPECTED(values, testset.begin());
- }
- }
- }}} //namespace boost::intrusive::test
- #include <boost/intrusive/detail/config_end.hpp>
|