ceph/src/boost/libs/poly_collection/test/test_algorithm_impl.hpp

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