1/* Boost.MultiIndex test for standard list operations.
2 *
3 * Copyright 2003-2021 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
25using 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
39struct is_even
40{
41 bool operator()(int x)const{return x%2==0;}
42};
43
44template <int m>
45struct same_integral_div
46{
47 bool operator()(int x,int y)const{return (x/m)==(y/m);}
48};
49
50template <typename Container,typename Compare>
51bool 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
75template<typename Sequence>
76static void test_list_ops_unique_seq()
77{
78 typedef typename nth_index<Sequence,1>::type sequenced_index;
79 typedef typename sequenced_index::iterator sequenced_index_iterator;
80
81 Sequence ss,ss2;
82 sequenced_index &si=get<1>(ss),&si2=get<1>(ss2);
83
84 si.push_front(0); /* 0 */
85 si.push_front(4); /* 40 */
86 ss.insert(2); /* 402 */
87 ss.insert(5); /* 4025 */
88 si.push_front(3); /* 34025 */
89 si.push_back(6); /* 340256 */
90 si.push_back(1); /* 3402561 */
91 si.insert(project<1>(ss,ss.find(2)),8); /* 34082561 */
92 si2=si;
93
94 CHECK_EQUAL(si,(3)(4)(0)(8)(2)(5)(6)(1));
95
96 si.remove(8);
97 CHECK_EQUAL(si,(3)(4)(0)(2)(5)(6)(1));
98
99 si.remove_if(is_even());
100
101 CHECK_EQUAL(si,(3)(5)(1));
102
103 si.splice(si.end(),si2,project<1>(ss2,ss2.find(2)),si2.end());
104 CHECK_EQUAL(si,(3)(5)(1)(2)(6));
105 CHECK_EQUAL(si2,(3)(4)(0)(8)(5)(1));
106
107 si.splice(project<1>(ss,ss.find(2)),si2);
108 CHECK_EQUAL(si,(3)(5)(1)(4)(0)(8)(2)(6));
109 CHECK_EQUAL(si2,(3)(5)(1));
110
111 si.splice(project<1>(ss,ss.find(4)),si,project<1>(ss,ss.find(8)));
112 CHECK_EQUAL(si,(3)(5)(1)(8)(4)(0)(2)(6));
113
114 si2.clear();
115 std::pair<sequenced_index_iterator,bool> p=
116 si2.splice(si2.begin(),si,si.begin());
117 BOOST_TEST(*(p.first)==3&&p.second);
118
119 p=si.splice(si.end(),si2,si2.begin());
120 BOOST_TEST(*(p.first)==3&&p.second);
121 CHECK_EQUAL(si,(5)(1)(8)(4)(0)(2)(6)(3));
122 BOOST_TEST(si2.empty());
123
124 si2.splice(si2.end(),si,project<1>(ss,ss.find(2)),project<1>(ss,ss.find(6)));
125 CHECK_EQUAL(si,(5)(1)(8)(4)(0)(6)(3));
126 CHECK_EQUAL(si2,(2));
127
128 si2.splice(si2.begin(),si,project<1>(ss,ss.find(0)),project<1>(ss,ss.find(6)));
129 CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
130 CHECK_EQUAL(si2,(0)(2));
131
132 si.splice(si.begin(),si,si.begin(),si.begin());
133 CHECK_EQUAL(si,(5)(1)(8)(4)(6)(3));
134
135 si.splice(project<1>(ss,ss.find(8)),si,project<1>(ss,ss.find(4)),si.end());
136 CHECK_EQUAL(si,(5)(1)(4)(6)(3)(8));
137
138 si.sort();
139 si2.sort();
140 BOOST_TEST(is_sorted(si,std::less<int>()));
141 BOOST_TEST(is_sorted(si2,std::less<int>()));
142
143 si.merge(si2);
144 BOOST_TEST(is_sorted(si,std::less<int>()));
145 BOOST_TEST(si2.empty());
146
147 {
148 Sequence ss3(ss);
149 sequenced_index &si3=get<1>(ss3);
150
151 si3.sort(std::greater<int>());
152 si.reverse();
153 BOOST_TEST(si==si3);
154 }
155
156 si2.splice(si2.end(),si,project<1>(ss,ss.find(6)),project<1>(ss,ss.find(3)));
157 CHECK_EQUAL(si2,(6)(5)(4));
158
159 si.merge(si2,std::greater<int>());
160 BOOST_TEST(is_sorted(si,std::greater<int>()));
161 BOOST_TEST(si2.empty());
162
163 /* testcase for bug reported at
164 * https://svn.boost.org/trac/boost/ticket/3076
165 */
166 {
167 Sequence ss3;
168 sequenced_index &si3=get<1>(ss3);
169 si3.sort();
170 }
171}
172
173template<typename Sequence>
174static void test_list_ops_non_unique_seq()
175{
176 typedef typename Sequence::iterator iterator;
177
178 Sequence ss;
179 for(int i=0;i<10;++i){
180 ss.push_back(i);
181 ss.push_back(i);
182 ss.push_front(i);
183 ss.push_front(i);
184 } /* 9988776655443322110000112233445566778899 */
185
186 ss.unique();
187 CHECK_EQUAL(
188 ss,
189 (9)(8)(7)(6)(5)(4)(3)(2)(1)(0)
190 (1)(2)(3)(4)(5)(6)(7)(8)(9));
191
192 iterator it=ss.begin();
193 for(int j=0;j<9;++j,++it){} /* it points to o */
194
195 Sequence ss2;
196 ss2.splice(ss2.end(),ss,ss.begin(),it);
197 ss2.reverse();
198 ss.merge(ss2);
199 CHECK_EQUAL(
200 ss,
201 (0)(1)(1)(2)(2)(3)(3)(4)(4)(5)(5)
202 (6)(6)(7)(7)(8)(8)(9)(9));
203
204 ss.unique(same_integral_div<3>());
205 CHECK_EQUAL(ss,(0)(3)(6)(9));
206
207 ss.unique(same_integral_div<1>());
208 CHECK_EQUAL(ss,(0)(3)(6)(9));
209
210 /* testcases for bugs reported at
211 * http://lists.boost.org/boost-users/2006/09/22604.php
212 */
213 {
214 Sequence ss_,ss2_;
215 ss_.push_back(0);
216 ss2_.push_back(0);
217 ss_.splice(ss_.end(),ss2_,ss2_.begin());
218 CHECK_EQUAL(ss_,(0)(0));
219 BOOST_TEST(ss2_.empty());
220
221 ss_.clear();
222 ss2_.clear();
223 ss_.push_back(0);
224 ss2_.push_back(0);
225 ss_.splice(ss_.end(),ss2_,ss2_.begin(),ss2_.end());
226 CHECK_EQUAL(ss_,(0)(0));
227 BOOST_TEST(ss2_.empty());
228
229 ss_.clear();
230 ss2_.clear();
231 ss_.push_back(0);
232 ss2_.push_back(0);
233 ss_.merge(ss2_);
234 CHECK_EQUAL(ss_,(0)(0));
235 BOOST_TEST(ss2_.empty());
236
237 typedef typename Sequence::value_type value_type;
238 ss_.clear();
239 ss2_.clear();
240 ss_.push_back(0);
241 ss2_.push_back(0);
242 ss_.merge(ss2_,std::less<value_type>());
243 CHECK_EQUAL(ss_,(0)(0));
244 BOOST_TEST(ss2_.empty());
245 }
246}
247
248#if BOOST_WORKAROUND(__MWERKS__,<=0x3003)
249#pragma parse_func_templ reset
250#endif
251
252void test_list_ops()
253{
254 typedef multi_index_container<
255 int,
256 indexed_by<
257 ordered_unique<identity<int> >,
258 sequenced<>
259 >
260 > sequenced_set;
261
262 test_list_ops_unique_seq<sequenced_set>();
263
264
265 typedef multi_index_container<
266 int,
267 indexed_by<
268 ordered_unique<identity<int> >,
269 random_access<>
270 >
271 > random_access_set;
272
273 test_list_ops_unique_seq<random_access_set>();
274
275 typedef multi_index_container<
276 int,
277 indexed_by<sequenced<> >
278 > int_list;
279
280 test_list_ops_non_unique_seq<int_list>();
281
282 typedef multi_index_container<
283 int,
284 indexed_by<random_access<> >
285 > int_vector;
286
287 test_list_ops_non_unique_seq<int_vector>();
288}
289

source code of boost/libs/multi_index/test/test_list_ops.cpp