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 | |
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 | { |
41 | bool operator()(int x)const{return x%2==0;} |
42 | }; |
43 | |
44 | template <int m> |
45 | struct same_integral_div |
46 | { |
47 | bool operator()(int x,int y)const{return (x/m)==(y/m);} |
48 | }; |
49 | |
50 | template <typename Container,typename 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> |
76 | static 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 | |
173 | template<typename Sequence> |
174 | static 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 | |
252 | void 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 | |