123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275 |
- /* Boost.MultiIndex test for standard list operations.
- *
- * Copyright 2003-2013 Joaquin M Lopez Munoz.
- * 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/multi_index for library home page.
- */
- #include "test_list_ops.hpp"
- #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
- #include <algorithm>
- #include <vector>
- #include <boost/detail/lightweight_test.hpp>
- #include "pre_multi_index.hpp"
- #include <boost/multi_index_container.hpp>
- #include <boost/multi_index/identity.hpp>
- #include <boost/multi_index/ordered_index.hpp>
- #include <boost/multi_index/sequenced_index.hpp>
- #include <boost/multi_index/random_access_index.hpp>
- #include <boost/preprocessor/seq/enum.hpp>
- using namespace boost::multi_index;
- #undef CHECK_EQUAL
- #define CHECK_EQUAL(p,check_seq) \
- {\
- int v[]={BOOST_PP_SEQ_ENUM(check_seq)};\
- std::size_t size_v=sizeof(v)/sizeof(int);\
- BOOST_TEST(std::size_t(std::distance((p).begin(),(p).end()))==size_v);\
- BOOST_TEST(std::equal((p).begin(),(p).end(),&v[0]));\
- }
- #undef CHECK_VOID_RANGE
- #define CHECK_VOID_RANGE(p) BOOST_TEST((p).first==(p).second)
- struct is_even
- {
- bool operator()(int x)const{return x%2==0;}
- };
- template <int m>
- struct same_integral_div
- {
- bool operator()(int x,int y)const{return (x/m)==(y/m);}
- };
- template <typename Container,typename Compare>
- bool is_sorted(
- const Container& c,const Compare& comp=Compare())
- {
- if(c.empty())return true;
- typedef typename Container::const_iterator const_iterator;
- for(const_iterator it(c.begin());;){
- const_iterator it2=it;
- ++it2;
- if(it2==c.end())return true;
- if(comp(*it2,*it))return false;
- it=it2;
- }
- }
- #if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
- /* The "ISO C++ Template Parser" option makes CW8.3 incorrectly fail at
- * expressions of the form sizeof(x) where x is an array local to a
- * template function.
- */
- #pragma parse_func_templ off
- #endif
- template<typename Sequence>
- static void test_list_ops_unique_seq()
- {
- typedef typename nth_index<Sequence,1>::type sequenced_index;
- Sequence ss,ss2;
- sequenced_index &si=get<1>(ss),&si2=get<1>(ss2);
- si.push_front(0); /* 0 */
- si.push_front(4); /* 40 */
- ss.insert(2); /* 402 */
- ss.insert(5); /* 4025 */
- si.push_front(3); /* 34025 */
- si.push_back(6); /* 340256 */
- si.push_back(1); /* 3402561 */
- si.insert(project<1>(ss,ss.find(2)),8); /* 34082561 */
- si2=si;
- CHECK_EQUAL(si,(3)(4)(0)(8)(2)(5)(6)(1));
- si.remove(8);
- CHECK_EQUAL(si,(3)(4)(0)(2)(5)(6)(1));
- si.remove_if(is_even());
- CHECK_EQUAL(si,(3)(5)(1));
- si.splice(si.end(),si2);
- CHECK_EQUAL(si,(3)(5)(1)(4)(0)(8)(2)(6));
- CHECK_EQUAL(si2,(3)(5)(1));
- si.splice(project<1>(ss,ss.find(4)),si,project<1>(ss,ss.find(8)));
- CHECK_EQUAL(si,(3)(5)(1)(8)(4)(0)(2)(6));
- si2.clear();
- si2.splice(si2.begin(),si,si.begin());
- si.splice(si.end(),si2,si2.begin());
- CHECK_EQUAL(si,(5)(1)(8)(4)(0)(2)(6)(3));
- BOOST_TEST(si2.empty());
- si2.splice(si2.end(),si,project<1>(ss,ss.find(0)),project<1>(ss,ss.find(6)));
- CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
- CHECK_EQUAL(si2,(0)(2));
- si.splice(si.begin(),si,si.begin(),si.begin());
- CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
- si.splice(project<1>(ss,ss.find(8)),si,project<1>(ss,ss.find(4)),si.end());
- CHECK_EQUAL(si,(5)(1)(4)(6)(3)(8));
- si.sort();
- si2.sort();
- BOOST_TEST(is_sorted(si,std::less<int>()));
- BOOST_TEST(is_sorted(si2,std::less<int>()));
- si.merge(si2);
- BOOST_TEST(is_sorted(si,std::less<int>()));
- BOOST_TEST(si2.empty());
- {
- Sequence ss3(ss);
- sequenced_index &si3=get<1>(ss3);
- si3.sort(std::greater<int>());
- si.reverse();
- BOOST_TEST(si==si3);
- }
- si2.splice(si2.end(),si,project<1>(ss,ss.find(6)),project<1>(ss,ss.find(3)));
- CHECK_EQUAL(si2,(6)(5)(4));
- si.merge(si2,std::greater<int>());
- BOOST_TEST(is_sorted(si,std::greater<int>()));
- BOOST_TEST(si2.empty());
- /* testcase for bug reported at
- * https://svn.boost.org/trac/boost/ticket/3076
- */
- {
- Sequence ss3;
- sequenced_index &si3=get<1>(ss3);
- si3.sort();
- }
- }
- template<typename Sequence>
- static void test_list_ops_non_unique_seq()
- {
- typedef typename Sequence::iterator iterator;
- Sequence ss;
- for(int i=0;i<10;++i){
- ss.push_back(i);
- ss.push_back(i);
- ss.push_front(i);
- ss.push_front(i);
- } /* 9988776655443322110000112233445566778899 */
- ss.unique();
- CHECK_EQUAL(
- ss,
- (9)(8)(7)(6)(5)(4)(3)(2)(1)(0)
- (1)(2)(3)(4)(5)(6)(7)(8)(9));
- iterator it=ss.begin();
- for(int j=0;j<9;++j,++it){} /* it points to o */
- Sequence ss2;
- ss2.splice(ss2.end(),ss,ss.begin(),it);
- ss2.reverse();
- ss.merge(ss2);
- CHECK_EQUAL(
- ss,
- (0)(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)
- (6)(6)(7)(7)(8)(8)(9)(9));
- ss.unique(same_integral_div<3>());
- CHECK_EQUAL(ss,(0)(3)(6)(9));
- ss.unique(same_integral_div<1>());
- CHECK_EQUAL(ss,(0)(3)(6)(9));
- /* testcases for bugs reported at
- * http://lists.boost.org/boost-users/2006/09/22604.php
- */
- {
- Sequence ss_,ss2_;
- ss_.push_back(0);
- ss2_.push_back(0);
- ss_.splice(ss_.end(),ss2_,ss2_.begin());
- CHECK_EQUAL(ss_,(0)(0));
- BOOST_TEST(ss2_.empty());
- ss_.clear();
- ss2_.clear();
- ss_.push_back(0);
- ss2_.push_back(0);
- ss_.splice(ss_.end(),ss2_,ss2_.begin(),ss2_.end());
- CHECK_EQUAL(ss_,(0)(0));
- BOOST_TEST(ss2_.empty());
- ss_.clear();
- ss2_.clear();
- ss_.push_back(0);
- ss2_.push_back(0);
- ss_.merge(ss2_);
- CHECK_EQUAL(ss_,(0)(0));
- BOOST_TEST(ss2_.empty());
- typedef typename Sequence::value_type value_type;
- ss_.clear();
- ss2_.clear();
- ss_.push_back(0);
- ss2_.push_back(0);
- ss_.merge(ss2_,std::less<value_type>());
- CHECK_EQUAL(ss_,(0)(0));
- BOOST_TEST(ss2_.empty());
- }
- }
- #if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
- #pragma parse_func_templ reset
- #endif
- void test_list_ops()
- {
- typedef multi_index_container<
- int,
- indexed_by<
- ordered_unique<identity<int> >,
- sequenced<>
- >
- > sequenced_set;
-
- test_list_ops_unique_seq<sequenced_set>();
- typedef multi_index_container<
- int,
- indexed_by<
- ordered_unique<identity<int> >,
- random_access<>
- >
- > random_access_set;
-
- test_list_ops_unique_seq<random_access_set>();
- typedef multi_index_container<
- int,
- indexed_by<sequenced<> >
- > int_list;
- test_list_ops_non_unique_seq<int_list>();
- typedef multi_index_container<
- int,
- indexed_by<random_access<> >
- > int_vector;
- test_list_ops_non_unique_seq<int_vector>();
- }
|