1/* Copyright 2016-2020 Joaquin M Lopez Munoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
5 *
6 * See http://www.boost.org/libs/poly_collection for library home page.
7 */
8
9#ifndef BOOST_POLY_COLLECTION_TEST_TEST_ALGORITHM_IMPL_HPP
10#define BOOST_POLY_COLLECTION_TEST_TEST_ALGORITHM_IMPL_HPP
11
12#if defined(_MSC_VER)
13#pragma once
14#endif
15
16#include <algorithm>
17#include <boost/config.hpp>
18#include <boost/core/lightweight_test.hpp>
19#include <boost/detail/workaround.hpp>
20#include <boost/iterator/function_output_iterator.hpp>
21#include <boost/poly_collection/algorithm.hpp>
22#include <functional>
23#include <iterator>
24#include <random>
25#include <type_traits>
26#include <utility>
27#include <vector>
28#include "test_utilities.hpp"
29
30using namespace test_utilities;
31
32#if BOOST_WORKAROUND(BOOST_MSVC,>=1910)
33/* https://lists.boost.org/Archives/boost/2017/06/235687.php */
34
35#define DEFINE_ALGORITHM(name,f) \
36template<typename... Ts> \
37struct name \
38{ \
39 template<typename... Args> \
40 auto operator()(Args&&... args)const \
41 { \
42 return f<Ts...>(std::forward<Args>(args)...); \
43 } \
44};
45#elif BOOST_WORKAROUND(BOOST_GCC_VERSION,<50200)
46/* problem here is with return type containing <Ts...> */
47
48#define DEFINE_ALGORITHM(name,f) \
49template<typename... Ts> \
50struct name \
51{ \
52 template<typename... Args> \
53 auto operator()(Args&&... args)const-> \
54 decltype(f(std::forward<Args>(args)...)) \
55 { \
56 return f<Ts...>(std::forward<Args>(args)...); \
57 } \
58};
59#else
60#define DEFINE_ALGORITHM(name,f) \
61template<typename... Ts> \
62struct name \
63{ \
64 template<typename... Args> \
65 auto operator()(Args&&... args)const-> \
66 decltype(f<Ts...>(std::forward<Args>(args)...)) \
67 { \
68 return f<Ts...>(std::forward<Args>(args)...); \
69 } \
70};
71#endif
72
73DEFINE_ALGORITHM(std_all_of,std::all_of)
74DEFINE_ALGORITHM(poly_all_of,boost::poly_collection::all_of)
75DEFINE_ALGORITHM(std_any_of,std::any_of)
76DEFINE_ALGORITHM(poly_any_of,boost::poly_collection::any_of)
77DEFINE_ALGORITHM(std_none_of,std::none_of)
78DEFINE_ALGORITHM(poly_none_of,boost::poly_collection::none_of)
79DEFINE_ALGORITHM(std_for_each,std::for_each)
80DEFINE_ALGORITHM(poly_for_each,boost::poly_collection::for_each)
81DEFINE_ALGORITHM(poly_for_each_n,boost::poly_collection::for_each_n)
82DEFINE_ALGORITHM(std_find,std::find)
83DEFINE_ALGORITHM(poly_find,boost::poly_collection::find)
84DEFINE_ALGORITHM(std_find_if,std::find_if)
85DEFINE_ALGORITHM(poly_find_if,boost::poly_collection::find_if)
86DEFINE_ALGORITHM(std_find_if_not,std::find_if_not)
87DEFINE_ALGORITHM(poly_find_if_not,boost::poly_collection::find_if_not)
88DEFINE_ALGORITHM(std_find_end,std::find_end)
89DEFINE_ALGORITHM(poly_find_end,boost::poly_collection::find_end)
90DEFINE_ALGORITHM(std_find_first_of,std::find_first_of)
91DEFINE_ALGORITHM(poly_find_first_of,boost::poly_collection::find_first_of)
92DEFINE_ALGORITHM(std_adjacent_find,std::adjacent_find)
93DEFINE_ALGORITHM(poly_adjacent_find,boost::poly_collection::adjacent_find)
94DEFINE_ALGORITHM(std_count,std::count)
95DEFINE_ALGORITHM(poly_count,boost::poly_collection::count)
96DEFINE_ALGORITHM(std_count_if,std::count_if)
97DEFINE_ALGORITHM(poly_count_if,boost::poly_collection::count_if)
98DEFINE_ALGORITHM(std_cpp11_mismatch,std::mismatch) /* note std_cpp11 prefix */
99DEFINE_ALGORITHM(poly_mismatch,boost::poly_collection::mismatch)
100DEFINE_ALGORITHM(std_cpp11_equal,std::equal) /* note std_cpp11 prefix */
101DEFINE_ALGORITHM(poly_equal,boost::poly_collection::equal)
102DEFINE_ALGORITHM(std_cpp11_is_permutation,std::is_permutation) /* std_cpp11 */
103DEFINE_ALGORITHM(poly_is_permutation,boost::poly_collection::is_permutation)
104DEFINE_ALGORITHM(std_search,std::search)
105DEFINE_ALGORITHM(poly_search,boost::poly_collection::search)
106DEFINE_ALGORITHM(std_search_n,std::search_n)
107DEFINE_ALGORITHM(poly_search_n,boost::poly_collection::search_n)
108DEFINE_ALGORITHM(std_copy,std::copy)
109DEFINE_ALGORITHM(poly_copy,boost::poly_collection::copy)
110DEFINE_ALGORITHM(std_copy_n,std::copy_n)
111DEFINE_ALGORITHM(poly_copy_n,boost::poly_collection::copy_n)
112DEFINE_ALGORITHM(std_copy_if,std::copy_if)
113DEFINE_ALGORITHM(poly_copy_if,boost::poly_collection::copy_if)
114DEFINE_ALGORITHM(std_move,std::move)
115DEFINE_ALGORITHM(poly_move,boost::poly_collection::move)
116DEFINE_ALGORITHM(std_transform,std::transform)
117DEFINE_ALGORITHM(poly_transform,boost::poly_collection::transform)
118DEFINE_ALGORITHM(std_replace_copy,std::replace_copy)
119DEFINE_ALGORITHM(poly_replace_copy,boost::poly_collection::replace_copy)
120DEFINE_ALGORITHM(std_replace_copy_if,std::replace_copy_if)
121DEFINE_ALGORITHM(poly_replace_copy_if,boost::poly_collection::replace_copy_if)
122DEFINE_ALGORITHM(std_remove_copy,std::remove_copy)
123DEFINE_ALGORITHM(poly_remove_copy,boost::poly_collection::remove_copy)
124DEFINE_ALGORITHM(std_remove_copy_if,std::remove_copy_if)
125DEFINE_ALGORITHM(poly_remove_copy_if,boost::poly_collection::remove_copy_if)
126DEFINE_ALGORITHM(std_unique_copy,std::unique_copy)
127DEFINE_ALGORITHM(poly_unique_copy,boost::poly_collection::unique_copy)
128DEFINE_ALGORITHM(poly_sample,boost::poly_collection::sample)
129DEFINE_ALGORITHM(std_rotate_copy,std::rotate_copy)
130DEFINE_ALGORITHM(poly_rotate_copy,boost::poly_collection::rotate_copy)
131DEFINE_ALGORITHM(std_is_partitioned,std::is_partitioned)
132DEFINE_ALGORITHM(poly_is_partitioned,boost::poly_collection::is_partitioned)
133DEFINE_ALGORITHM(std_partition_copy,std::partition_copy)
134DEFINE_ALGORITHM(poly_partition_copy,boost::poly_collection::partition_copy)
135DEFINE_ALGORITHM(std_partition_point,std::partition_point)
136DEFINE_ALGORITHM(poly_partition_point,boost::poly_collection::partition_point)
137
138template<typename...>
139struct std_for_each_n
140{
141 /* implemented here as the algorithm is C++17 */
142
143 template<typename InputIterator,typename Size,typename Function>
144 InputIterator operator()(InputIterator first,Size n,Function f)const
145 {
146 for(;n>0;++first,(void)--n)f(*first);
147 return first;
148 }
149};
150
151template<typename... Ts>
152struct std_mismatch:std_cpp11_mismatch<Ts...>
153{
154 using std_cpp11_mismatch<Ts...>::operator();
155
156 /* C++14 variants */
157
158 template<typename InputIterator1,typename InputIterator2>
159 std::pair<InputIterator1,InputIterator2> operator()(
160 InputIterator1 first1,InputIterator1 last1,
161 InputIterator2 first2,InputIterator2 last2)const
162 {
163 while(first1!=last1&&first2!=last2&&*first1==*first2){
164 ++first1;
165 ++first2;
166 }
167 return {first1,first2};
168 }
169
170 template<typename InputIterator1,typename InputIterator2,typename Predicate>
171 std::pair<InputIterator1,InputIterator2> operator()(
172 InputIterator1 first1,InputIterator1 last1,
173 InputIterator2 first2,InputIterator2 last2,Predicate pred)const
174 {
175 while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){
176 ++first1;
177 ++first2;
178 }
179 return {first1,first2};
180 }
181};
182
183template<typename... Ts>
184struct std_equal:std_cpp11_equal<Ts...>
185{
186 using std_cpp11_equal<Ts...>::operator();
187
188 /* C++14 variants */
189
190 template<typename InputIterator1,typename InputIterator2>
191 bool operator()(
192 InputIterator1 first1,InputIterator1 last1,
193 InputIterator2 first2,InputIterator2 last2)const
194 {
195 for(;first1!=last1&&first2!=last2;++first1,++first2){
196 if(!(*first1==*first2))return false;
197 }
198 return first1==last1&&first2==last2;
199 }
200
201 template<typename InputIterator1,typename InputIterator2,typename Predicate>
202 bool operator()(
203 InputIterator1 first1,InputIterator1 last1,
204 InputIterator2 first2,InputIterator2 last2,Predicate pred)const
205 {
206 for(;first1!=last1&&first2!=last2;++first1,++first2){
207 if(!pred(*first1,*first2))return false;
208 }
209 return first1==last1&&first2==last2;
210 }
211};
212
213template<typename... Ts>
214struct std_is_permutation:std_cpp11_is_permutation<Ts...>
215{
216 using std_cpp11_is_permutation<Ts...>::operator();
217
218 /* The implementation of predicate-based std::is_permutation in GCC<=4.8
219 * version of libstdc++-v3 incorrectly triggers the instantiation of
220 * ForwardIterator2::value_type, which fails when this is an abstract class.
221 * The implementation below ripped from libc++ source code.
222 */
223
224 template<
225 typename ForwardIterator1,typename ForwardIterator2,typename Predicate
226 >
227 bool operator()(
228 ForwardIterator1 first1,ForwardIterator1 last1,
229 ForwardIterator2 first2,Predicate pred)const
230 {
231 using difference_type=
232 typename std::iterator_traits<ForwardIterator1>::difference_type;
233
234 for(;first1!=last1;++first1,(void)++first2){
235 if(!pred(*first1,*first2))goto not_done;
236 }
237 return true;
238
239 not_done:
240 difference_type l1=std::distance(first1,last1);
241 if(l1==difference_type(1))return false;
242
243 ForwardIterator2 last2=std::next(first2,l1);
244 for(ForwardIterator1 i=first1;i!= last1;++i){
245 for(ForwardIterator1 j=first1;j!=i;++j)if(pred(*j,*i))goto next_iter;
246 {
247 difference_type c2=0;
248 for(ForwardIterator2 j=first2;j!=last2;++j)if(pred(*i,*j))++c2;
249 if(c2==0)return false;
250 difference_type c1=1;
251 for(ForwardIterator1 j=std::next(i);j!=last1;++j)if(pred(*i,*j))++c1;
252 if(c1!=c2)return false;
253 }
254 next_iter:;
255 }
256 return true;
257 }
258
259 /* C++14 variants */
260
261 template<typename ForwardIterator1,typename ForwardIterator2>
262 bool operator()(
263 ForwardIterator1 first1,ForwardIterator1 last1,
264 ForwardIterator2 first2,ForwardIterator2 last2)const
265 {
266 if(std::distance(first1,last1)!=std::distance(first2,last2))return false;
267 return (*this)(first1,last1,first2);
268 }
269
270 template<
271 typename ForwardIterator1,typename ForwardIterator2,typename Predicate
272 >
273 bool operator()(
274 ForwardIterator1 first1,ForwardIterator1 last1,
275 ForwardIterator2 first2,ForwardIterator2 last2,Predicate pred)const
276 {
277 if(std::distance(first1,last1)!=std::distance(first2,last2))return false;
278 return (*this)(first1,last1,first2,pred);
279 }
280};
281
282template<typename...>
283struct std_sample
284{
285 /* Implemented here as the algorithm is C++17 and because we need to control
286 * the implementation to do white-box testing. Only the ForwardIterator
287 * version required.
288 */
289
290 template<
291 typename ForwardIterator,typename OutputIterator,
292 typename Distance, typename UniformRandomBitGenerator
293 >
294 OutputIterator operator()(
295 ForwardIterator first,ForwardIterator last,
296 OutputIterator res, Distance n,UniformRandomBitGenerator&& g)const
297 {
298 Distance m=std::distance(first,last);
299 for(n=(std::min)(n,m);n!=0;++first){
300 auto r=std::uniform_int_distribution<Distance>(0,--m)(g);
301 if (r<n){
302 *res++=*first;
303 --n;
304 }
305 }
306 return res;
307 }
308};
309
310template<
311 typename ControlAlgorithm,typename Algorithm,
312 typename PolyCollection,typename... Args
313>
314void test_algorithm(PolyCollection& p,Args&&... args)
315{
316 Algorithm alg;
317 ControlAlgorithm control;
318 for(auto first=p.begin(),end=p.end();;++first){
319 for(auto last=first;;++last){
320 BOOST_TEST(
321 alg(first,last,std::forward<Args>(args)...)==
322 control(first,last,std::forward<Args>(args)...));
323 if(last==end)break;
324 }
325 if(first==end)break;
326 }
327}
328
329template<
330 typename ControlAlgorithm,typename... Algorithms,
331 typename PolyCollection,typename... Args
332>
333void test_algorithms(PolyCollection& p,Args&&... args)
334{
335 do_((test_algorithm<ControlAlgorithm,Algorithms>(
336 p,std::forward<Args>(args)...),0)...);
337 do_((test_algorithm<ControlAlgorithm,Algorithms>(
338 const_cast<const PolyCollection&>(p),std::forward<Args>(args)...),0)...);
339}
340
341template<
342 typename ControlAlgorithm,typename... Algorithms,
343 typename PolyCollection,typename... Args
344>
345void test_algorithms_with_equality_impl(
346 std::true_type,PolyCollection& p,Args&&... args)
347{
348 test_algorithms<ControlAlgorithm,Algorithms...>(
349 p,std::forward<Args>(args)...);
350}
351
352template<
353 typename ControlAlgorithm,typename... Algorithm,
354 typename PolyCollection,typename... Args
355>
356void test_algorithms_with_equality_impl(
357 std::false_type,PolyCollection&,Args&&...)
358{
359}
360
361template<
362 typename ControlAlgorithm,typename... Algorithms,
363 typename PolyCollection,typename... Args
364>
365void test_algorithms_with_equality(PolyCollection& p,Args&&... args)
366{
367 test_algorithms_with_equality_impl<ControlAlgorithm,Algorithms...>(
368 is_equality_comparable<typename PolyCollection::value_type>{},
369 p,std::forward<Args>(args)...);
370}
371
372template<
373 typename ControlAlgorithm,typename Algorithm,
374 typename ToInt,typename PolyCollection
375>
376void test_for_each_n_algorithm(ToInt to_int,PolyCollection& p)
377{
378 Algorithm alg;
379 ControlAlgorithm control;
380 for(auto first=p.begin(),end=p.end();;++first){
381 for(auto n=std::distance(first,end);n>=0;--n){
382 int res1=0,res2=0;
383 auto acc1=compose(to_int,[&](int x){res1+=x;});
384 auto acc2=compose(to_int,[&](int x){res2+=x;});
385 auto it1=alg(first,n,acc1),
386 it2=control(first,n,acc2);
387 BOOST_TEST(it1==it2);
388 BOOST_TEST(res1==res2);
389 }
390 if(first==end)break;
391 }
392}
393
394template<
395 typename ControlAlgorithm,typename... Algorithms,
396 typename ToInt,typename PolyCollection
397>
398void test_for_each_n_algorithms(ToInt to_int,PolyCollection& p)
399{
400 do_((test_for_each_n_algorithm<ControlAlgorithm,Algorithms>(
401 to_int,p),0)...);
402 do_((test_for_each_n_algorithm<ControlAlgorithm,Algorithms>(
403 to_int,const_cast<const PolyCollection&>(p)),0)...);
404}
405
406template<
407 typename ControlAlgorithm,typename Algorithm,
408 typename ToInt,typename PolyCollection,typename... Args
409>
410void test_copy_algorithm(ToInt to_int,PolyCollection& p,Args&&... args)
411{
412 Algorithm alg;
413 ControlAlgorithm control;
414 for(auto first=p.begin(),end=p.end();;++first){
415 for(auto last=first;;++last){
416 using vector=std::vector<int>;
417
418 vector v1,v2;
419 auto insert1=compose(to_int,[&](int x){v1.push_back(x: x);});
420 auto insert2=compose(to_int,[&](int x){v2.push_back(x: x);});
421 auto out1=boost::make_function_output_iterator(std::ref(insert1));
422 auto out2=boost::make_function_output_iterator(std::ref(insert2));
423
424 out1=alg(first,last,out1,std::forward<Args>(args)...);
425 out2=control(first,last,out2,std::forward<Args>(args)...);
426 BOOST_TEST(v1==v2);
427 if(last==end)break;
428 }
429 if(first==end)break;
430 }
431}
432
433template<
434 typename ControlAlgorithm,typename... Algorithms,
435 typename ToInt,typename PolyCollection,typename... Args
436>
437void test_copy_algorithms(ToInt to_int,PolyCollection& p,Args&&... args)
438{
439 do_((test_copy_algorithm<ControlAlgorithm,Algorithms>(
440 to_int,p,std::forward<Args>(args)...),0)...);
441 do_((test_copy_algorithm<ControlAlgorithm,Algorithms>(
442 to_int,const_cast<const PolyCollection&>(p),
443 std::forward<Args>(args)...),0)...);
444}
445
446template<
447 typename ControlAlgorithm,typename... Algorithms,
448 typename ToInt,typename PolyCollection,typename... Args
449>
450void test_copy_algorithms_with_equality_impl(
451 std::true_type,ToInt to_int,PolyCollection& p,Args&&... args)
452{
453 test_copy_algorithms<ControlAlgorithm,Algorithms...>(
454 to_int,p,std::forward<Args>(args)...);
455}
456
457template<
458 typename ControlAlgorithm,typename... Algorithm,
459 typename ToInt,typename PolyCollection,typename... Args
460>
461void test_copy_algorithms_with_equality_impl(
462 std::false_type,ToInt,PolyCollection&,Args&&...)
463{
464}
465
466template<
467 typename ControlAlgorithm,typename... Algorithms,
468 typename ToInt,typename PolyCollection,typename... Args
469>
470void test_copy_algorithms_with_equality(
471 ToInt to_int,PolyCollection& p,Args&&... args)
472{
473 test_copy_algorithms_with_equality_impl<ControlAlgorithm,Algorithms...>(
474 is_equality_comparable<typename PolyCollection::value_type>{},
475 to_int,p,std::forward<Args>(args)...);
476}
477
478template<
479 typename ControlAlgorithm,typename Algorithm,
480 typename ToInt,typename PolyCollection,typename... Args
481>
482void test_copy_n_algorithm(ToInt to_int,PolyCollection& p,Args&&... args)
483{
484 Algorithm alg;
485 ControlAlgorithm control;
486 for(auto first=p.begin(),end=p.end();;++first){
487 for(std::ptrdiff_t n=0,m=std::distance(first,end);n<=m;++n){
488 using vector=std::vector<int>;
489
490 vector v1,v2;
491 auto insert1=compose(to_int,[&](int x){v1.push_back(x: x);});
492 auto insert2=compose(to_int,[&](int x){v2.push_back(x: x);});
493 auto out1=boost::make_function_output_iterator(std::ref(insert1));
494 auto out2=boost::make_function_output_iterator(std::ref(insert2));
495
496 alg(first,n,out1,std::forward<Args>(args)...);
497 control(first,n,out2,std::forward<Args>(args)...);
498 BOOST_TEST(v1==v2);
499 }
500 if(first==end)break;
501 }
502}
503
504template<
505 typename ControlAlgorithm,typename... Algorithms,
506 typename ToInt,typename PolyCollection,typename... Args
507>
508void test_copy_n_algorithms(ToInt to_int,PolyCollection& p,Args&&... args)
509{
510 do_((test_copy_n_algorithm<ControlAlgorithm,Algorithms>(
511 to_int,p,std::forward<Args>(args)...),0)...);
512 do_((test_copy_n_algorithm<ControlAlgorithm,Algorithms>(
513 to_int,const_cast<const PolyCollection&>(p),
514 std::forward<Args>(args)...),0)...);
515}
516
517template<
518 typename ControlAlgorithm,typename Algorithm,
519 typename ToInt,typename PolyCollection
520>
521void test_transform2_algorithm(ToInt to_int,PolyCollection& p)
522{
523 Algorithm alg;
524 ControlAlgorithm control;
525 for(auto first=p.begin(),end=p.end();;++first){
526 for(auto last=first;;++last){
527 using vector=std::vector<int>;
528
529 auto op=compose_all(to_int,[](int x,int y){return x+y;});
530 vector v1,v2;
531 auto insert1=[&](int x){v1.push_back(x: x);};
532 auto insert2=[&](int x){v2.push_back(x: x);};
533 auto out1=boost::make_function_output_iterator(std::ref(insert1));
534 auto out2=boost::make_function_output_iterator(std::ref(insert2));
535
536 out1=alg(first,last,p.begin(),out1,op);
537 out2=control(first,last,p.begin(),out2,op);
538 BOOST_TEST(v1==v2);
539 if(last==end)break;
540 }
541 if(first==end)break;
542 }
543}
544
545template<
546 typename ControlAlgorithm,typename... Algorithms,
547 typename ToInt,typename PolyCollection
548>
549void test_transform2_algorithms(ToInt to_int,PolyCollection& p)
550{
551 do_((test_transform2_algorithm<ControlAlgorithm,Algorithms>(
552 to_int,p),0)...);
553 do_((test_transform2_algorithm<ControlAlgorithm,Algorithms>(
554 to_int,const_cast<const PolyCollection&>(p)),0)...);
555}
556
557template<
558 typename ControlAlgorithm,typename Algorithm,
559 typename ToInt,typename PolyCollection
560>
561void test_rotate_copy_algorithm(ToInt to_int,PolyCollection& p)
562{
563 Algorithm alg;
564 ControlAlgorithm control;
565 for(auto first=p.begin(),end=p.end();;++first){
566 for(auto last=first;;++last){
567 for(auto middle=first;;++middle){
568 using vector=std::vector<int>;
569
570 vector v1,v2;
571 auto insert1=compose(to_int,[&](int x){v1.push_back(x: x);});
572 auto insert2=compose(to_int,[&](int x){v2.push_back(x: x);});
573 auto out1=boost::make_function_output_iterator(std::ref(insert1));
574 auto out2=boost::make_function_output_iterator(std::ref(insert2));
575
576 out1=alg(first,middle,last,out1);
577 out2=control(first,middle,last,out2);
578 BOOST_TEST(v1==v2);
579
580 if(middle==last)break;
581 }
582 if(last==end)break;
583 }
584 if(first==end)break;
585 }
586}
587
588template<
589 typename ControlAlgorithm,typename... Algorithms,
590 typename ToInt,typename PolyCollection
591>
592void test_rotate_copy_algorithms(ToInt to_int,PolyCollection& p)
593{
594 do_((test_rotate_copy_algorithm<ControlAlgorithm,Algorithms>(
595 to_int,p),0)...);
596 do_((test_rotate_copy_algorithm<ControlAlgorithm,Algorithms>(
597 to_int,const_cast<const PolyCollection&>(p)),0)...);
598}
599
600template<
601 typename ControlAlgorithm,typename Algorithm,
602 typename ToInt,typename PolyCollection,typename Predicate
603>
604void test_partition_copy_algorithm(
605 ToInt to_int,PolyCollection& p,Predicate pred)
606{
607 Algorithm alg;
608 ControlAlgorithm control;
609 for(auto first=p.begin(),end=p.end();;++first){
610 for(auto last=first;;++last){
611 using vector=std::vector<int>;
612
613 vector v11,v12,v21,v22;
614 auto insert11=compose(to_int,[&](int x){v11.push_back(x: x);});
615 auto insert12=compose(to_int,[&](int x){v12.push_back(x: x);});
616 auto insert21=compose(to_int,[&](int x){v21.push_back(x: x);});
617 auto insert22=compose(to_int,[&](int x){v22.push_back(x: x);});
618 auto out11=boost::make_function_output_iterator(std::ref(insert11));
619 auto out12=boost::make_function_output_iterator(std::ref(insert12));
620 auto out21=boost::make_function_output_iterator(std::ref(insert21));
621 auto out22=boost::make_function_output_iterator(std::ref(insert22));
622
623 std::tie(out11,out12)=alg(first,last,out11,out12,pred);
624 std::tie(out21,out22)=control(first,last,out21,out22,pred);
625 BOOST_TEST(v11==v21);
626 BOOST_TEST(v12==v22);
627 if(last==end)break;
628 }
629 if(first==end)break;
630 }
631}
632
633template<
634 typename ControlAlgorithm,typename... Algorithms,
635 typename ToInt,typename PolyCollection,typename Predicate
636>
637void test_partition_copy_algorithms(
638 ToInt to_int,PolyCollection& p,Predicate pred)
639{
640 do_((test_partition_copy_algorithm<ControlAlgorithm,Algorithms>(
641 to_int,p,pred),0)...);
642 do_((test_partition_copy_algorithm<ControlAlgorithm,Algorithms>(
643 to_int,const_cast<const PolyCollection&>(p),pred),0)...);
644}
645
646template<typename ToInt>
647struct poly_accumulator_class
648{
649 poly_accumulator_class(const ToInt& to_int):res{0},to_int(to_int){}
650 bool operator==(const poly_accumulator_class& x)const{return res==x.res;}
651
652 template<typename T> void operator()(const T& x){res+=to_int(x);}
653
654 int res;
655 ToInt to_int;
656};
657
658template<typename ToInt>
659poly_accumulator_class<ToInt> poly_accumulator(const ToInt& to_int)
660{
661 return to_int;
662}
663
664template<typename Algorithm>
665struct force_arg_copying
666{
667 Algorithm alg;
668
669 template<typename T>
670 static T copy(const T& x){return x;}
671
672 template<typename... Args>
673 auto operator()(Args&&... args)const
674 ->decltype(std::declval<Algorithm>()(copy(args)...))
675 {
676 return alg(copy(args)...);
677 }
678};
679
680template<
681 typename PolyCollection,typename ValueFactory,typename ToInt,
682 typename... Types
683>
684void test_algorithm()
685{
686 PolyCollection p;
687 ValueFactory v;
688 ToInt to_int;
689
690 fill<constraints<>,Types...>(p,v,2);
691
692 {
693 auto always_true=compose(to_int,[](int){return true;});
694 auto always_false=compose(to_int,[](int){return false;});
695 auto pred=compose(to_int,[](int x){return x%2==0;});
696
697 test_algorithms<std_all_of<>,poly_all_of<>,poly_all_of<Types...>>(
698 p,always_true);
699 test_algorithms<std_all_of<>,poly_all_of<>,poly_all_of<Types...>>(
700 p,always_false);
701 test_algorithms<std_all_of<>,poly_all_of<>,poly_all_of<Types...>>(
702 p,pred);
703
704 test_algorithms<std_any_of<>,poly_any_of<>,poly_any_of<Types...>>(
705 p,always_true);
706 test_algorithms<std_any_of<>,poly_any_of<>,poly_any_of<Types...>>(
707 p,always_false);
708 test_algorithms<std_any_of<>,poly_any_of<>,poly_any_of<Types...>>(
709 p,pred);
710
711 test_algorithms<std_none_of<>,poly_none_of<>,poly_none_of<Types...>>(
712 p,always_true);
713 test_algorithms<std_none_of<>,poly_none_of<>,poly_none_of<Types...>>(
714 p,always_false);
715 test_algorithms<std_none_of<>,poly_none_of<>,poly_none_of<Types...>>(
716 p,pred);
717 }
718 {
719 test_algorithms<std_for_each<>,poly_for_each<>,poly_for_each<Types...>>(
720 p,poly_accumulator(to_int));
721
722 test_for_each_n_algorithms<
723 std_for_each_n<>,poly_for_each_n<>,poly_for_each_n<Types...>
724 >(to_int,p);
725 }
726 {
727 for(const auto& x:p){
728 test_algorithms_with_equality<
729 std_find<>,poly_find<>,only_eq_comparable<poly_find,Types...>
730 >(p,x);
731 }
732 }
733 {
734 auto it=p.begin();
735 std::advance(it,p.size()/2);
736 int n=to_int(*it);
737 auto pred=compose(to_int,[=](int x){return x==n;});
738
739 test_algorithms<std_find_if<>,poly_find_if<>,poly_find_if<Types...>>(
740 p,pred);
741
742 test_algorithms<
743 std_find_if_not<>,poly_find_if_not<>,poly_find_if_not<Types...>
744 >(p,pred);
745 }
746 {
747 auto first=p.begin(),end=first;
748 std::advance(end,+p.size()/2);
749 for(;first!=end;++first){
750 test_algorithms_with_equality<
751 std_find_end<>,poly_find_end<>,
752 only_eq_comparable<poly_find_end,Types...>
753 >(p,first,end);
754
755 test_algorithms_with_equality<
756 std_search<>,poly_search<>,
757 only_eq_comparable<poly_search,Types...>
758 >(p,first,end);
759 }
760 }
761 {
762 std::vector<int> v;
763 for(const auto& x:p)v.push_back(to_int(x));
764 v.erase(first: v.begin()+v.size()/2,last: v.end());
765
766 for(auto first=v.begin(),end=v.begin()+v.size()/2;first!=end;++first){
767 for(int i=1;i<4;++i){
768 auto pred=compose(to_int,[&](int x,int y){return x%i==y%i;});
769
770 test_algorithms<
771 std_find_end<>,poly_find_end<>,poly_find_end<Types...>
772 >(p,first,end,pred);
773
774 test_algorithms<std_search<>,poly_search<>,poly_search<Types...>>(
775 p,first,end,pred);
776 }
777 }
778 }
779 {
780 using value_type=typename PolyCollection::value_type;
781 using vector=std::vector<std::reference_wrapper<const value_type>>;
782
783 vector v;
784 for(const auto& x:p){
785 switch(v.size()%3){
786 case 0:v.push_back(x);break;
787 case 1:v.push_back(*p.begin());break;
788 default:{}
789 }
790 }
791
792 for(auto first=v.begin(),end=v.end();;++first){
793 for(auto last=first;;++last){
794 test_algorithms_with_equality<
795 std_find_first_of<>,poly_find_first_of<>,
796 only_eq_comparable<poly_find_first_of,Types...>
797 >(p,first,last);
798 if(last==end)break;
799 }
800 if(first==end)break;
801 }
802 }
803 {
804 std::vector<int> v;
805 for(const auto& x:p){
806 switch(v.size()%3){
807 case 0:v.push_back(to_int(x));break;
808 case 1:v.push_back(x: -1);break;
809 default:{}
810 }
811 }
812
813 for(auto first=v.begin(),end=v.end();;++first){
814 for(auto last=first;;++last){
815 test_algorithms<
816 std_find_first_of<>,poly_find_first_of<>,poly_find_first_of<Types...>
817 >(p,first,last,compose(to_int,std::equal_to<int>{}));
818 if(last==end)break;
819 }
820 if(first==end)break;
821 }
822 }
823 {
824 test_algorithms_with_equality<
825 std_adjacent_find<>,poly_adjacent_find<>,
826 only_eq_comparable<poly_adjacent_find,Types...>
827 >(p);
828 }
829 {
830 std::vector<int> v;
831 for(const auto& x:p)v.push_back(to_int(x));
832 v.push_back(x: -1);
833
834 for(auto first=v.begin(),end=v.end()-1;first!=end;++first){
835 int n1=*first,n2=*(first+1);
836 test_algorithms<
837 std_adjacent_find<>,poly_adjacent_find<>,poly_adjacent_find<Types...>
838 >(p,compose_all(to_int,[=](int x,int y){return x==n1&&y==n2;}));
839 }
840 }
841 {
842 for(const auto& x:p){
843 test_algorithms_with_equality<
844 std_count<>,poly_count<>,only_eq_comparable<poly_count,Types...>
845 >(p,x);
846 }
847 }
848 {
849 for(int i=1;i<4;++i){
850 test_algorithms<std_count_if<>,poly_count_if<>,poly_count_if<Types...>>(
851 p,compose(to_int,[&](int x){return x%i==0;}));
852 }
853 }
854 {
855 using value_type=typename PolyCollection::value_type;
856 using vector=std::vector<std::reference_wrapper<const value_type>>;
857
858 vector v;
859 for(const auto& x:p)v.push_back(x);
860 v.back()=v.front();
861 auto w=v;
862 v.insert(v.end(),w.begin(),w.end());
863
864 for(auto first=v.begin(),end=v.begin()+v.size()/2;first!=end;++first){
865 test_algorithms_with_equality<
866 std_mismatch<>,poly_mismatch<>,
867 only_eq_comparable<poly_mismatch,Types...>
868 >(p,first);
869
870 test_algorithms_with_equality<
871 std_mismatch<>,poly_mismatch<>,
872 only_eq_comparable<poly_mismatch,Types...>
873 >(p,first,end);
874
875 test_algorithms_with_equality<
876 std_equal<>,poly_equal<>,only_eq_comparable<poly_equal,Types...>
877 >(p,first);
878
879 test_algorithms_with_equality<
880 std_equal<>,poly_equal<>,only_eq_comparable<poly_equal,Types...>
881 >(p,first,end);
882 }
883
884 test_algorithms_with_equality<
885 std_mismatch<>,poly_mismatch<>,only_eq_comparable<poly_mismatch,Types...>
886 >(p,v.end(),v.end());
887
888 test_algorithms_with_equality<
889 std_equal<>,poly_equal<>,only_eq_comparable<poly_equal,Types...>
890 >(p,v.end(),v.end());
891 }
892 {
893 std::vector<int> v;
894 for(const auto& x:p)v.push_back(to_int(x));
895 v.back()=-1;
896 auto w=v;
897 v.insert(position: v.end(),first: w.begin(),last: w.end());
898 auto pred=compose(to_int,std::equal_to<int>{});
899
900 for(auto first=v.begin(),end=v.begin()+v.size()/2;first!=end;++first){
901 test_algorithms<std_mismatch<>,poly_mismatch<>,poly_mismatch<Types...>>(
902 p,first,pred);
903
904 test_algorithms<std_mismatch<>,poly_mismatch<>,poly_mismatch<Types...>>(
905 p,first,end,pred);
906
907 test_algorithms<std_equal<>,poly_equal<>,poly_equal<Types...>>(
908 p,first,pred);
909
910 test_algorithms<std_equal<>,poly_equal<>,poly_equal<Types...>>(
911 p,first,end,pred);
912 }
913
914 test_algorithms<std_mismatch<>,poly_mismatch<>,poly_mismatch<Types...>>(
915 p,v.end(),v.end(),pred);
916
917 test_algorithms<std_equal<>,poly_equal<>,poly_equal<Types...>>(
918 p,v.end(),v.end(),pred);
919 }
920 {
921 using value_type=typename PolyCollection::value_type;
922 using vector=std::vector<std::reference_wrapper<const value_type>>;
923
924 vector v;
925 for(const auto& x:p)v.push_back(x);
926 auto w=v;
927 std::mt19937 gen{73642};
928 std::shuffle(w.begin(),w.end(),gen);
929 v.insert(v.end(),w.begin(),w.end());
930 auto pred=compose_all(to_int,std::equal_to<int>{});
931
932 for(auto first=unwrap_iterator(v.begin()),
933 end=unwrap_iterator(v.begin()+v.size()/2);first!=end;++first){
934 test_algorithms_with_equality<
935 std_is_permutation<>,
936 poly_is_permutation<>,
937 only_eq_comparable<poly_is_permutation,Types...>
938 >(p,first);
939
940 test_algorithms<
941 std_is_permutation<>,
942 poly_is_permutation<>,poly_is_permutation<Types...>
943 >(p,first,pred);
944
945 test_algorithms_with_equality<
946 std_is_permutation<>,
947 poly_is_permutation<>,
948 only_eq_comparable<poly_is_permutation,Types...>
949 >(p,first,end);
950
951 test_algorithms<
952 std_is_permutation<>,
953 poly_is_permutation<>,poly_is_permutation<Types...>
954 >(p,first,end,pred);
955 }
956
957 test_algorithms_with_equality<
958 std_is_permutation<>,
959 poly_is_permutation<>,
960 only_eq_comparable<poly_is_permutation,Types...>
961 >(p,unwrap_iterator(v.end()),unwrap_iterator(v.end()));
962
963 test_algorithms<
964 std_is_permutation<>,
965 poly_is_permutation<>,poly_is_permutation<Types...>
966 >(p,unwrap_iterator(v.end()),unwrap_iterator(v.end()),pred);
967 }
968 {
969 /* search tested above */
970 }
971 {
972 for(const auto&x: p){
973 for(int n=0;n<3;++n){
974 test_algorithms_with_equality<
975 std_search_n<>,poly_search_n<>,
976 only_eq_comparable<poly_search_n,Types...>
977 >(p,n,x);
978 }
979 }
980 }
981 {
982 for(int n=0;n<6;++n){
983 test_algorithms<std_search_n<>,poly_search_n<>,poly_search_n<Types...>>(
984 p,n,0,compose(to_int,[&](int x,int y){return x%(6-n)==y%(6-n);}));
985 }
986 }
987 {
988 test_copy_algorithms<std_copy<>,poly_copy<>,poly_copy<Types...>>(
989 to_int,p);
990 }
991 {
992 test_copy_n_algorithms<std_copy_n<>,poly_copy_n<>,poly_copy_n<Types...>>(
993 to_int,p);
994 }
995 {
996 auto always_true=compose(to_int,[](int){return true;});
997 auto always_false=compose(to_int,[](int){return false;});
998 auto pred=compose(to_int,[](int x){return x%2==0;});
999
1000 test_copy_algorithms<std_copy_if<>,poly_copy_if<>,poly_copy_if<Types...>>(
1001 to_int,p,always_true);
1002 test_copy_algorithms<std_copy_if<>,poly_copy_if<>,poly_copy_if<Types...>>(
1003 to_int,p,always_false);
1004 test_copy_algorithms<std_copy_if<>,poly_copy_if<>,poly_copy_if<Types...>>(
1005 to_int,p,pred);
1006 }
1007 {
1008 test_copy_algorithms<std_move<>,poly_move<>,poly_move<Types...>>(
1009 to_int,p); /* we're not checking std::move is properly used internally */
1010 }
1011 {
1012 auto f=compose(to_int,[](int x){return -x;});
1013 auto int_id=[](int x){return x;};
1014
1015 test_copy_algorithms<
1016 std_transform<>,poly_transform<>,poly_transform<Types...>
1017 >(int_id,p,f);
1018 }
1019 {
1020 test_transform2_algorithms<
1021 std_transform<>,poly_transform<>,poly_transform<Types...>
1022 >(to_int,p);
1023 }
1024 {
1025 const auto& y=*p.begin();
1026 for(const auto& x:p){
1027 test_copy_algorithms_with_equality<
1028 std_replace_copy<>,poly_replace_copy<>,
1029 only_eq_comparable<poly_replace_copy,Types...>
1030 >(to_int,p,x,y);
1031
1032 test_copy_algorithms_with_equality<
1033 std_remove_copy<>,poly_remove_copy<>,
1034 only_eq_comparable<poly_remove_copy,Types...>
1035 >(to_int,p,x);
1036 }
1037 }
1038 {
1039 auto always_true=compose(to_int,[](int){return true;});
1040 auto always_false=compose(to_int,[](int){return false;});
1041 auto pred=compose(to_int,[](int x){return x%2==0;});
1042 auto& x=*p.begin();
1043
1044 test_copy_algorithms<
1045 std_replace_copy_if<>,
1046 poly_replace_copy_if<>,poly_replace_copy_if<Types...>
1047 >(to_int,p,always_true,x);
1048 test_copy_algorithms<
1049 std_replace_copy_if<>,
1050 poly_replace_copy_if<>,poly_replace_copy_if<Types...>
1051 >(to_int,p,always_false,x);
1052 test_copy_algorithms<
1053 std_replace_copy_if<>,
1054 poly_replace_copy_if<>,poly_replace_copy_if<Types...>
1055 >(to_int,p,pred,x);
1056
1057 test_copy_algorithms<
1058 std_remove_copy_if<>,
1059 poly_remove_copy_if<>,poly_remove_copy_if<Types...>
1060 >(to_int,p,always_true);
1061 test_copy_algorithms<
1062 std_remove_copy_if<>,
1063 poly_remove_copy_if<>,poly_remove_copy_if<Types...>
1064 >(to_int,p,always_false);
1065 test_copy_algorithms<
1066 std_remove_copy_if<>,
1067 poly_remove_copy_if<>,poly_remove_copy_if<Types...>
1068 >(to_int,p,pred);
1069 }
1070 {
1071 test_copy_algorithms_with_equality<
1072 std_unique_copy<>,poly_unique_copy<>,
1073 only_eq_comparable<poly_unique_copy,Types...>
1074 >(to_int,p);
1075 }
1076 {
1077 for(int n=0;n<6;++n){
1078 test_copy_algorithms<
1079 std_unique_copy<>,poly_unique_copy<>,poly_unique_copy<Types...>
1080 >(to_int,p,
1081 compose_all(to_int,[&](int x,int y){return x%(6-n)==y%(6-n);}));
1082 }
1083 }
1084 {
1085 test_rotate_copy_algorithms<
1086 std_rotate_copy<>,poly_rotate_copy<>,poly_rotate_copy<Types...>
1087 >(to_int,p);
1088 }
1089 {
1090 /* force_arg_copying used to avoid sharing mt19937's state */
1091
1092 for(auto n=p.size()+1;n-->0;){
1093 test_copy_algorithms<
1094 force_arg_copying<std_sample<>>,
1095 force_arg_copying<poly_sample<>>,
1096 force_arg_copying<poly_sample<Types...>>
1097 >(to_int,p,n,std::mt19937{});
1098 }
1099 }
1100 {
1101 for(int n=0;n<6;++n){
1102 auto pred=compose(to_int,[&](int x){return x%(6-n)<=(6-n)/2;});
1103
1104 test_algorithms<
1105 std_is_partitioned<>,
1106 poly_is_partitioned<>,poly_is_partitioned<Types...>
1107 >(p,pred);
1108
1109 test_partition_copy_algorithms<
1110 std_partition_copy<>,
1111 poly_partition_copy<>,poly_partition_copy<Types...>
1112 >(to_int,p,pred);
1113
1114 test_algorithms<
1115 std_partition_point<>,
1116 poly_partition_point<>,poly_partition_point<Types...>
1117 >(p,pred);
1118 }
1119 }
1120}
1121
1122#endif
1123

source code of boost/libs/poly_collection/test/test_algorithm_impl.hpp