1 /* Boost.MultiIndex test for standard list operations.
2 *
3 * Copyright 2003-2013 Joaquin M Lopez Munoz.
4 * Distributed under the Boost Software License, Version 1.0.
5 * (See accompanying file LICENSE_1_0.txt or copy at
6 * http://www.boost.org/LICENSE_1_0.txt)
7 *
8 * See http://www.boost.org/libs/multi_index for library home page.
9 */
10
11 #include "test_list_ops.hpp"
12
13 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
14 #include <algorithm>
15 #include <vector>
16 #include <boost/detail/lightweight_test.hpp>
17 #include "pre_multi_index.hpp"
18 #include <boost/multi_index_container.hpp>
19 #include <boost/multi_index/identity.hpp>
20 #include <boost/multi_index/ordered_index.hpp>
21 #include <boost/multi_index/sequenced_index.hpp>
22 #include <boost/multi_index/random_access_index.hpp>
23 #include <boost/preprocessor/seq/enum.hpp>
24
25 using namespace boost::multi_index;
26
27 #undef CHECK_EQUAL
28 #define CHECK_EQUAL(p,check_seq) \
29 {\
30 int v[]={BOOST_PP_SEQ_ENUM(check_seq)};\
31 std::size_t size_v=sizeof(v)/sizeof(int);\
32 BOOST_TEST(std::size_t(std::distance((p).begin(),(p).end()))==size_v);\
33 BOOST_TEST(std::equal((p).begin(),(p).end(),&v[0]));\
34 }
35
36 #undef CHECK_VOID_RANGE
37 #define CHECK_VOID_RANGE(p) BOOST_TEST((p).first==(p).second)
38
39 struct is_even
40 {
operator ()is_even41 bool operator()(int x)const{return x%2==0;}
42 };
43
44 template <int m>
45 struct same_integral_div
46 {
operator ()same_integral_div47 bool operator()(int x,int y)const{return (x/m)==(y/m);}
48 };
49
50 template <typename Container,typename Compare>
is_sorted(const Container & c,const Compare & comp=Compare ())51 bool is_sorted(
52 const Container& c,const Compare& comp=Compare())
53 {
54 if(c.empty())return true;
55
56 typedef typename Container::const_iterator const_iterator;
57 for(const_iterator it(c.begin());;){
58 const_iterator it2=it;
59 ++it2;
60 if(it2==c.end())return true;
61 if(comp(*it2,*it))return false;
62 it=it2;
63 }
64 }
65
66 #if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
67 /* The "ISO C++ Template Parser" option makes CW8.3 incorrectly fail at
68 * expressions of the form sizeof(x) where x is an array local to a
69 * template function.
70 */
71
72 #pragma parse_func_templ off
73 #endif
74
75 template<typename Sequence>
test_list_ops_unique_seq()76 static void test_list_ops_unique_seq()
77 {
78 typedef typename nth_index<Sequence,1>::type sequenced_index;
79
80 Sequence ss,ss2;
81 sequenced_index &si=get<1>(ss),&si2=get<1>(ss2);
82
83 si.push_front(0); /* 0 */
84 si.push_front(4); /* 40 */
85 ss.insert(2); /* 402 */
86 ss.insert(5); /* 4025 */
87 si.push_front(3); /* 34025 */
88 si.push_back(6); /* 340256 */
89 si.push_back(1); /* 3402561 */
90 si.insert(project<1>(ss,ss.find(2)),8); /* 34082561 */
91 si2=si;
92
93 CHECK_EQUAL(si,(3)(4)(0)(8)(2)(5)(6)(1));
94
95 si.remove(8);
96 CHECK_EQUAL(si,(3)(4)(0)(2)(5)(6)(1));
97
98 si.remove_if(is_even());
99
100 CHECK_EQUAL(si,(3)(5)(1));
101
102 si.splice(si.end(),si2);
103 CHECK_EQUAL(si,(3)(5)(1)(4)(0)(8)(2)(6));
104 CHECK_EQUAL(si2,(3)(5)(1));
105
106 si.splice(project<1>(ss,ss.find(4)),si,project<1>(ss,ss.find(8)));
107 CHECK_EQUAL(si,(3)(5)(1)(8)(4)(0)(2)(6));
108 si2.clear();
109 si2.splice(si2.begin(),si,si.begin());
110
111 si.splice(si.end(),si2,si2.begin());
112 CHECK_EQUAL(si,(5)(1)(8)(4)(0)(2)(6)(3));
113 BOOST_TEST(si2.empty());
114
115 si2.splice(si2.end(),si,project<1>(ss,ss.find(0)),project<1>(ss,ss.find(6)));
116 CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
117 CHECK_EQUAL(si2,(0)(2));
118
119 si.splice(si.begin(),si,si.begin(),si.begin());
120 CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
121
122 si.splice(project<1>(ss,ss.find(8)),si,project<1>(ss,ss.find(4)),si.end());
123 CHECK_EQUAL(si,(5)(1)(4)(6)(3)(8));
124
125 si.sort();
126 si2.sort();
127 BOOST_TEST(is_sorted(si,std::less<int>()));
128 BOOST_TEST(is_sorted(si2,std::less<int>()));
129
130 si.merge(si2);
131 BOOST_TEST(is_sorted(si,std::less<int>()));
132 BOOST_TEST(si2.empty());
133
134 {
135 Sequence ss3(ss);
136 sequenced_index &si3=get<1>(ss3);
137
138 si3.sort(std::greater<int>());
139 si.reverse();
140 BOOST_TEST(si==si3);
141 }
142
143 si2.splice(si2.end(),si,project<1>(ss,ss.find(6)),project<1>(ss,ss.find(3)));
144 CHECK_EQUAL(si2,(6)(5)(4));
145
146 si.merge(si2,std::greater<int>());
147 BOOST_TEST(is_sorted(si,std::greater<int>()));
148 BOOST_TEST(si2.empty());
149
150 /* testcase for bug reported at
151 * https://svn.boost.org/trac/boost/ticket/3076
152 */
153 {
154 Sequence ss3;
155 sequenced_index &si3=get<1>(ss3);
156 si3.sort();
157 }
158 }
159
160 template<typename Sequence>
test_list_ops_non_unique_seq()161 static void test_list_ops_non_unique_seq()
162 {
163 typedef typename Sequence::iterator iterator;
164
165 Sequence ss;
166 for(int i=0;i<10;++i){
167 ss.push_back(i);
168 ss.push_back(i);
169 ss.push_front(i);
170 ss.push_front(i);
171 } /* 9988776655443322110000112233445566778899 */
172
173 ss.unique();
174 CHECK_EQUAL(
175 ss,
176 (9)(8)(7)(6)(5)(4)(3)(2)(1)(0)
177 (1)(2)(3)(4)(5)(6)(7)(8)(9));
178
179 iterator it=ss.begin();
180 for(int j=0;j<9;++j,++it){} /* it points to o */
181
182 Sequence ss2;
183 ss2.splice(ss2.end(),ss,ss.begin(),it);
184 ss2.reverse();
185 ss.merge(ss2);
186 CHECK_EQUAL(
187 ss,
188 (0)(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)
189 (6)(6)(7)(7)(8)(8)(9)(9));
190
191 ss.unique(same_integral_div<3>());
192 CHECK_EQUAL(ss,(0)(3)(6)(9));
193
194 ss.unique(same_integral_div<1>());
195 CHECK_EQUAL(ss,(0)(3)(6)(9));
196
197 /* testcases for bugs reported at
198 * http://lists.boost.org/boost-users/2006/09/22604.php
199 */
200 {
201 Sequence ss_,ss2_;
202 ss_.push_back(0);
203 ss2_.push_back(0);
204 ss_.splice(ss_.end(),ss2_,ss2_.begin());
205 CHECK_EQUAL(ss_,(0)(0));
206 BOOST_TEST(ss2_.empty());
207
208 ss_.clear();
209 ss2_.clear();
210 ss_.push_back(0);
211 ss2_.push_back(0);
212 ss_.splice(ss_.end(),ss2_,ss2_.begin(),ss2_.end());
213 CHECK_EQUAL(ss_,(0)(0));
214 BOOST_TEST(ss2_.empty());
215
216 ss_.clear();
217 ss2_.clear();
218 ss_.push_back(0);
219 ss2_.push_back(0);
220 ss_.merge(ss2_);
221 CHECK_EQUAL(ss_,(0)(0));
222 BOOST_TEST(ss2_.empty());
223
224 typedef typename Sequence::value_type value_type;
225 ss_.clear();
226 ss2_.clear();
227 ss_.push_back(0);
228 ss2_.push_back(0);
229 ss_.merge(ss2_,std::less<value_type>());
230 CHECK_EQUAL(ss_,(0)(0));
231 BOOST_TEST(ss2_.empty());
232 }
233 }
234
235 #if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
236 #pragma parse_func_templ reset
237 #endif
238
test_list_ops()239 void test_list_ops()
240 {
241 typedef multi_index_container<
242 int,
243 indexed_by<
244 ordered_unique<identity<int> >,
245 sequenced<>
246 >
247 > sequenced_set;
248
249 test_list_ops_unique_seq<sequenced_set>();
250
251
252 typedef multi_index_container<
253 int,
254 indexed_by<
255 ordered_unique<identity<int> >,
256 random_access<>
257 >
258 > random_access_set;
259
260 test_list_ops_unique_seq<random_access_set>();
261
262 typedef multi_index_container<
263 int,
264 indexed_by<sequenced<> >
265 > int_list;
266
267 test_list_ops_non_unique_seq<int_list>();
268
269 typedef multi_index_container<
270 int,
271 indexed_by<random_access<> >
272 > int_vector;
273
274 test_list_ops_non_unique_seq<int_vector>();
275 }
276