1 /*
2 Copyright (c) T. Zachary Laine 2018.
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
7 For more information, see http://www.boost.org
8 */
9 #include <iostream>
10
11 #include <boost/algorithm/find_backward.hpp>
12
13 #define BOOST_TEST_MAIN
14 #include <boost/test/unit_test.hpp>
15
16 #include <vector>
17 #include <list>
18
19
20 namespace ba = boost::algorithm;
21
22 template <typename Container>
23 struct dist_t
24 {
dist_tdist_t25 dist_t(Container & cont) : cont_(cont) {}
26 template<typename Iter>
operator ()dist_t27 std::ptrdiff_t operator()(Iter it) const
28 {
29 return std::distance(cont_.begin(), it);
30 }
31
32 Container & cont_;
33 };
34
check_constexpr_backward()35 BOOST_CXX14_CONSTEXPR bool check_constexpr_backward()
36 {
37 int in_data[] = {1, 2, 3, 4, 5};
38 bool res = true;
39
40 const int* from = in_data;
41 const int* to = in_data + 5;
42
43 const int* start = ba::find_backward(from, to, 1); // stops on first
44 res = (res && start == from);
45
46 start = ba::find_backward(in_data, 1); // stops on first
47 res = (res && start == from);
48
49 const int* end = ba::find_backward(from, to, 6); // stops on the end
50 res = (res && end == to);
51
52 end = ba::find_backward(in_data, 6); // stops on the end
53 res = (res && end == to);
54
55 const int* three = ba::find_backward(from, to, 3); // stops on third element
56 res = (res && three == in_data + 2);
57
58 three = ba::find_backward(in_data, 3); // stops on third element
59 res = (res && three == in_data + 2);
60
61 return res;
62 }
63
test_find_backward()64 void test_find_backward()
65 {
66 {
67 std::vector<int> v1;
68 const dist_t<std::vector<int> > dist(v1);
69
70 for (int i = 5; i < 15; ++i)
71 v1.push_back(i);
72 BOOST_CHECK_EQUAL(
73 dist(ba::find_backward(v1.begin(), v1.end(), 0)), v1.size());
74 BOOST_CHECK_EQUAL(
75 dist(ba::find_backward(v1.begin(), v1.end(), 100)), v1.size());
76 BOOST_CHECK_EQUAL(
77 dist(ba::find_backward(v1.begin(), v1.end(), v1.back())),
78 v1.size() - 1);
79 BOOST_CHECK_EQUAL(
80 dist(ba::find_backward(v1.begin(), v1.end(), v1.front())), 0);
81
82 BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 0)), v1.size());
83 BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, 100)), v1.size());
84 BOOST_CHECK_EQUAL(
85 dist(ba::find_backward(v1, v1.back())), v1.size() - 1);
86 BOOST_CHECK_EQUAL(dist(ba::find_backward(v1, v1.front())), 0);
87 }
88
89 // With bidirectional iterators.
90 {
91 std::list<int> l1;
92 const dist_t<std::list<int> > dist(l1);
93
94 for (int i = 5; i < 15; ++i)
95 l1.push_back(i);
96 BOOST_CHECK_EQUAL(
97 dist(ba::find_backward(l1.begin(), l1.end(), 0)), l1.size());
98 BOOST_CHECK_EQUAL(
99 dist(ba::find_backward(l1.begin(), l1.end(), 100)), l1.size());
100 BOOST_CHECK_EQUAL(
101 dist(ba::find_backward(l1.begin(), l1.end(), l1.back())),
102 l1.size() - 1);
103 BOOST_CHECK_EQUAL(
104 dist(ba::find_backward(l1.begin(), l1.end(), l1.front())), 0);
105
106 BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 0)), l1.size());
107 BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, 100)), l1.size());
108 BOOST_CHECK_EQUAL(
109 dist(ba::find_backward(l1, l1.back())), l1.size() - 1);
110 BOOST_CHECK_EQUAL(dist(ba::find_backward(l1, l1.front())), 0);
111 }
112
113 BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_backward();
114 BOOST_CHECK(ce_result);
115 }
116
117 struct equals
118 {
equalsequals119 BOOST_CXX14_CONSTEXPR equals(int n) : n_(n) {}
operator ()equals120 BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i == n_; }
121 int n_;
122 };
123
check_constexpr_if_backward()124 BOOST_CXX14_CONSTEXPR bool check_constexpr_if_backward()
125 {
126 int in_data[] = {1, 2, 3, 4, 5};
127 bool res = true;
128
129 const int* from = in_data;
130 const int* to = in_data + 5;
131
132 const int* start = ba::find_if_backward(from, to, equals(1)); // stops on first
133 res = (res && start == from);
134
135 start = ba::find_if_backward(in_data, equals(1)); // stops on first
136 res = (res && start == from);
137
138 const int* end = ba::find_if_backward(from, to, equals(6)); // stops on the end
139 res = (res && end == to);
140
141 end = ba::find_if_backward(in_data, equals(6)); // stops on the end
142 res = (res && end == to);
143
144 const int* three = ba::find_if_backward(from, to, equals(3)); // stops on third element
145 res = (res && three == in_data + 2);
146
147 three = ba::find_if_backward(in_data, equals(3)); // stops on third element
148 res = (res && three == in_data + 2);
149
150 return res;
151 }
152
test_find_if_backward()153 void test_find_if_backward()
154 {
155 {
156 std::vector<int> v1;
157 const dist_t<std::vector<int> > dist(v1);
158
159 for (int i = 5; i < 15; ++i)
160 v1.push_back(i);
161 BOOST_CHECK_EQUAL(
162 dist(ba::find_if_backward(v1.begin(), v1.end(), equals(0))),
163 v1.size());
164 BOOST_CHECK_EQUAL(
165 dist(ba::find_if_backward(v1.begin(), v1.end(), equals(100))),
166 v1.size());
167 BOOST_CHECK_EQUAL(
168 dist(ba::find_if_backward(v1.begin(), v1.end(), equals(v1.back()))),
169 v1.size() - 1);
170 BOOST_CHECK_EQUAL(
171 dist(
172 ba::find_if_backward(v1.begin(), v1.end(), equals(v1.front()))),
173 0);
174
175 BOOST_CHECK_EQUAL(dist(ba::find_if_backward(v1, equals(0))), v1.size());
176 BOOST_CHECK_EQUAL(
177 dist(ba::find_if_backward(v1, equals(100))), v1.size());
178 BOOST_CHECK_EQUAL(
179 dist(ba::find_if_backward(v1, equals(v1.back()))), v1.size() - 1);
180 BOOST_CHECK_EQUAL(
181 dist(ba::find_if_backward(v1, equals(v1.front()))), 0);
182 }
183
184 // With bidirectional iterators.
185 {
186 std::list<int> l1;
187 const dist_t<std::list<int> > dist(l1);
188
189 for (int i = 5; i < 15; ++i)
190 l1.push_back(i);
191 BOOST_CHECK_EQUAL(
192 dist(ba::find_if_backward(l1.begin(), l1.end(), equals(0))),
193 l1.size());
194 BOOST_CHECK_EQUAL(
195 dist(ba::find_if_backward(l1.begin(), l1.end(), equals(100))),
196 l1.size());
197 BOOST_CHECK_EQUAL(
198 dist(ba::find_if_backward(l1.begin(), l1.end(), equals(l1.back()))),
199 l1.size() - 1);
200 BOOST_CHECK_EQUAL(
201 dist(
202 ba::find_if_backward(l1.begin(), l1.end(), equals(l1.front()))),
203 0);
204
205 BOOST_CHECK_EQUAL(dist(ba::find_if_backward(l1, equals(0))), l1.size());
206 BOOST_CHECK_EQUAL(
207 dist(ba::find_if_backward(l1, equals(100))), l1.size());
208 BOOST_CHECK_EQUAL(
209 dist(ba::find_if_backward(l1, equals(l1.back()))), l1.size() - 1);
210 BOOST_CHECK_EQUAL(
211 dist(ba::find_if_backward(l1, equals(l1.front()))), 0);
212 }
213
214 BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_backward();
215 BOOST_CHECK(ce_result);
216 }
217
218 struct not_equals
219 {
not_equalsnot_equals220 BOOST_CXX14_CONSTEXPR not_equals(int n) : n_(n) {}
operator ()not_equals221 BOOST_CXX14_CONSTEXPR bool operator()(int i) { return i != n_; }
222 int n_;
223 };
224
check_constexpr_if_not_backward()225 BOOST_CXX14_CONSTEXPR bool check_constexpr_if_not_backward()
226 {
227 int in_data[] = {1, 2, 3, 4, 5};
228 bool res = true;
229
230 const int* from = in_data;
231 const int* to = in_data + 5;
232
233 const int* start = ba::find_if_not_backward(from, to, not_equals(1)); // stops on first
234 res = (res && start == from);
235
236 start = ba::find_if_not_backward(in_data, not_equals(1)); // stops on first
237 res = (res && start == from);
238
239 const int* end = ba::find_if_not_backward(from, to, not_equals(6)); // stops on the end
240 res = (res && end == to);
241
242 end = ba::find_if_not_backward(in_data, not_equals(6)); // stops on the end
243 res = (res && end == to);
244
245 const int* three = ba::find_if_not_backward(from, to, not_equals(3)); // stops on third element
246 res = (res && three == in_data + 2);
247
248 three = ba::find_if_not_backward(in_data, not_equals(3)); // stops on third element
249 res = (res && three == in_data + 2);
250
251 return res;
252 }
253
test_find_if_not_backward()254 void test_find_if_not_backward()
255 {
256 {
257 std::vector<int> v1;
258 const dist_t<std::vector<int> > dist(v1);
259
260 for (int i = 5; i < 15; ++i)
261 v1.push_back(i);
262 BOOST_CHECK_EQUAL(
263 dist(ba::find_if_not_backward(v1.begin(), v1.end(), not_equals(0))),
264 v1.size());
265 BOOST_CHECK_EQUAL(
266 dist(ba::find_if_not_backward(
267 v1.begin(), v1.end(), not_equals(100))),
268 v1.size());
269 BOOST_CHECK_EQUAL(
270 dist(ba::find_if_not_backward(
271 v1.begin(), v1.end(), not_equals(v1.back()))),
272 v1.size() - 1);
273 BOOST_CHECK_EQUAL(
274 dist(ba::find_if_not_backward(
275 v1.begin(), v1.end(), not_equals(v1.front()))),
276 0);
277
278 BOOST_CHECK_EQUAL(
279 dist(ba::find_if_not_backward(v1, not_equals(0))), v1.size());
280 BOOST_CHECK_EQUAL(
281 dist(ba::find_if_not_backward(v1, not_equals(100))), v1.size());
282 BOOST_CHECK_EQUAL(
283 dist(ba::find_if_not_backward(v1, not_equals(v1.back()))),
284 v1.size() - 1);
285 BOOST_CHECK_EQUAL(
286 dist(ba::find_if_not_backward(v1, not_equals(v1.front()))), 0);
287 }
288
289 // With bidirectional iterators.
290 {
291 std::list<int> l1;
292 const dist_t<std::list<int> > dist(l1);
293
294 for (int i = 5; i < 15; ++i)
295 l1.push_back(i);
296 BOOST_CHECK_EQUAL(
297 dist(ba::find_if_not_backward(l1.begin(), l1.end(), not_equals(0))),
298 l1.size());
299 BOOST_CHECK_EQUAL(
300 dist(ba::find_if_not_backward(
301 l1.begin(), l1.end(), not_equals(100))),
302 l1.size());
303 BOOST_CHECK_EQUAL(
304 dist(ba::find_if_not_backward(
305 l1.begin(), l1.end(), not_equals(l1.back()))),
306 l1.size() - 1);
307 BOOST_CHECK_EQUAL(
308 dist(ba::find_if_not_backward(
309 l1.begin(), l1.end(), not_equals(l1.front()))),
310 0);
311
312 BOOST_CHECK_EQUAL(
313 dist(ba::find_if_not_backward(l1, not_equals(0))), l1.size());
314 BOOST_CHECK_EQUAL(
315 dist(ba::find_if_not_backward(l1, not_equals(100))), l1.size());
316 BOOST_CHECK_EQUAL(
317 dist(ba::find_if_not_backward(l1, not_equals(l1.back()))),
318 l1.size() - 1);
319 BOOST_CHECK_EQUAL(
320 dist(ba::find_if_not_backward(l1, not_equals(l1.front()))), 0);
321 }
322
323 BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_if_not_backward();
324 BOOST_CHECK(ce_result);
325 }
326
check_constexpr_not_backward()327 BOOST_CXX14_CONSTEXPR bool check_constexpr_not_backward()
328 {
329 int in_data[] = {1, 5, 5, 5, 5};
330 bool res = true;
331
332 const int* from = in_data;
333 const int* to = in_data + 5;
334
335 const int* start = ba::find_not_backward(from, to, 5); // stops on first
336 res = (res && start == from);
337
338 start = ba::find_not_backward(in_data, 5); // stops on first
339 res = (res && start == from);
340
341 const int in_data_2[] = {6, 6, 6, 6, 6};
342 const int* end = ba::find_not_backward(in_data_2, in_data_2 + 5, 6); // stops on the end
343 res = (res && end == in_data_2 + 5);
344
345 end = ba::find_not_backward(in_data_2, 6); // stops on the end
346 res = (res && end == in_data_2 + 5);
347
348 return res;
349 }
350
test_find_not_backward()351 void test_find_not_backward()
352 {
353 {
354 std::vector<int> v1;
355 const dist_t<std::vector<int> > dist(v1);
356
357 for (int i = 0; i < 5; ++i)
358 v1.push_back(0);
359 for (int i = 0; i < 5; ++i)
360 v1.push_back(1);
361 BOOST_CHECK_EQUAL(
362 dist(ba::find_not_backward(v1.begin(), v1.end(), 1)), 4);
363 BOOST_CHECK_EQUAL(
364 dist(ba::find_not_backward(v1.begin(), v1.end(), 0)),
365 v1.size() - 1);
366 BOOST_CHECK_EQUAL(
367 dist(ba::find_not_backward(v1.begin(), v1.end(), 2)),
368 v1.size() - 1);
369
370 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 1)), 4);
371 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size() - 1);
372 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 2)), v1.size() - 1);
373
374 v1.resize(5);
375 BOOST_CHECK_EQUAL(
376 dist(ba::find_not_backward(v1.begin(), v1.end(), 0)), v1.size());
377
378 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(v1, 0)), v1.size());
379 }
380
381 // With bidirectional iterators.
382 {
383 std::list<int> l1;
384 const dist_t<std::list<int> > dist(l1);
385
386 for (int i = 0; i < 5; ++i)
387 l1.push_back(0);
388 for (int i = 0; i < 5; ++i)
389 l1.push_back(1);
390 BOOST_CHECK_EQUAL(
391 dist(ba::find_not_backward(l1.begin(), l1.end(), 1)), 4);
392 BOOST_CHECK_EQUAL(
393 dist(ba::find_not_backward(l1.begin(), l1.end(), 0)),
394 l1.size() - 1);
395 BOOST_CHECK_EQUAL(
396 dist(ba::find_not_backward(l1.begin(), l1.end(), 2)),
397 l1.size() - 1);
398
399 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 1)), 4);
400 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size() - 1);
401 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 2)), l1.size() - 1);
402
403 l1.resize(5);
404 BOOST_CHECK_EQUAL(
405 dist(ba::find_not_backward(l1.begin(), l1.end(), 0)), l1.size());
406
407 BOOST_CHECK_EQUAL(dist(ba::find_not_backward(l1, 0)), l1.size());
408 }
409
410 BOOST_CXX14_CONSTEXPR bool ce_result = check_constexpr_not_backward();
411 BOOST_CHECK(ce_result);
412 }
413
BOOST_AUTO_TEST_CASE(test_main)414 BOOST_AUTO_TEST_CASE(test_main)
415 {
416 test_find_backward();
417 test_find_if_backward();
418 test_find_if_not_backward();
419 test_find_not_backward();
420 }
421