ceph/src/boost/boost/poly_collection/algorithm.hpp

   1 /* Copyright 2016-2018 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_ALGORITHM_HPP
  10 #define BOOST_POLY_COLLECTION_ALGORITHM_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <algorithm>
  17 #include <boost/poly_collection/detail/auto_iterator.hpp>
  18 #include <boost/poly_collection/detail/functional.hpp>
  19 #include <boost/poly_collection/detail/iterator_traits.hpp>
  20 #include <boost/poly_collection/detail/segment_split.hpp>
  21 #include <boost/poly_collection/detail/type_restitution.hpp>
  22 #include <iterator>
  23 #include <random>
  24 #include <type_traits>
  25 #include <utility>
  26
  27 /* Improved performance versions of std algorithms over poly_collection.
  28  * poly_collection::alg is expected to be faster than the homonym std::alg
  29  * because the latter does a traversal over a segmented structured, where
  30  * incrementing requires checking for segment change, whereas the former
  31  * for-loops over flat segments.
  32  * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when
  33  * passing elements to f, i.e. if the concrete type of the element is Ti
  34  * then f is invoked with a [const] Ti&, which can dramatically improve
  35  * performance when f has specific overloads for Ti (like, for instance,
  36  * generic lambdas) as static optimization can kick in (devirtualization
  37  * being a particular example).
  38  */
  39
  40 namespace boost{
  41
  42 namespace poly_collection{
  43
  44 namespace detail{
  45
  46 namespace algorithm{
  47
  48 template<typename Iterator>
  49 using enable_if_poly_collection_iterator=typename std::enable_if<
  50   !std::is_void<typename poly_collection_of<Iterator>::type>::value
  51 >::type*;
  52
  53 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of)
  54
  55 template<
  56   typename... Ts,typename Iterator,typename Predicate,
  57   enable_if_poly_collection_iterator<Iterator> =nullptr
  58 >
  59 bool all_of(const Iterator& first,const Iterator& last,Predicate pred)
  60 {
  61   auto alg=restitute_range<Ts...>(std_all_of{},pred);
  62   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
  63   return true;
  64 }
  65
  66 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of)
  67
  68 template<
  69   typename... Ts,typename Iterator,typename Predicate,
  70   enable_if_poly_collection_iterator<Iterator> =nullptr
  71 >
  72 bool any_of(const Iterator& first,const Iterator& last,Predicate pred)
  73 {
  74   auto alg=restitute_range<Ts...>(std_any_of{},pred);
  75   for(auto i:detail::segment_split(first,last))if(alg(i))return true;
  76   return false;
  77 }
  78
  79 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of)
  80
  81 template<
  82   typename... Ts,typename Iterator,typename Predicate,
  83   enable_if_poly_collection_iterator<Iterator> =nullptr
  84 >
  85 bool none_of(const Iterator& first,const Iterator& last,Predicate pred)
  86 {
  87   auto alg=restitute_range<Ts...>(std_none_of{},pred);
  88   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
  89   return true;
  90 }
  91
  92 struct for_each_alg
  93 {
  94   template<typename InputIterator,typename Function>
  95   void operator()(
  96     InputIterator first,InputIterator last,Function& f)const /* note the & */
  97   {
  98     for(;first!=last;++first)f(*first);
  99   }
 100 };
 101
 102 template<
 103   typename... Ts,typename Iterator,typename Function,
 104   enable_if_poly_collection_iterator<Iterator> =nullptr
 105 >
 106 Function for_each(const Iterator& first,const Iterator& last,Function f)
 107 {
 108   for_each_segment(first,last,restitute_range<Ts...>(for_each_alg{},f));
 109   return std::move(f);
 110 }
 111
 112 struct for_each_n_alg
 113 {
 114   template<
 115     typename InputIterator,typename Size,typename Function
 116   >
 117   InputIterator operator()(
 118     InputIterator first,Size n,Function& f)const /* note the & */
 119   {
 120     for(;n>0;++first,(void)--n)f(*first);
 121     return first;
 122   }
 123 };
 124
 125 template<
 126   typename... Ts,typename Iterator,typename Size,typename Function,
 127   enable_if_poly_collection_iterator<Iterator> =nullptr
 128 >
 129 Iterator for_each_n(const Iterator& first,Size n,Function f)
 130 {
 131   using traits=iterator_traits<Iterator>;
 132   using local_base_iterator=typename traits::local_base_iterator;
 133
 134   if(n<=0)return first;
 135
 136   auto alg=restitute_iterator<Ts...>(
 137          cast_return<local_base_iterator>(for_each_n_alg{}));
 138   auto lbit=traits::local_base_iterator_from(first);
 139   auto sit=traits::base_segment_info_iterator_from(first);
 140   for(;;){
 141     auto m=sit->end()-lbit;
 142     if(n<=m){
 143       auto it=alg(sit->type_info(),lbit,n,f);
 144       return traits::iterator_from(
 145         it,traits::end_base_segment_info_iterator_from(first));
 146     }
 147     else{
 148       alg(sit->type_info(),lbit,m,f);
 149       n-=m;
 150     }
 151     ++sit;
 152     lbit=sit->begin();
 153   }
 154 }
 155
 156 template<
 157   typename Algorithm,typename... Ts,
 158   typename Iterator,typename... Args,
 159   enable_if_poly_collection_iterator<Iterator> =nullptr
 160 >
 161 Iterator generic_find(
 162   const Iterator& first,const Iterator& last,Args&&... args)
 163 {
 164   using traits=iterator_traits<Iterator>;
 165   using local_base_iterator=typename traits::local_base_iterator;
 166
 167   auto alg=restitute_range<Ts...>(
 168     cast_return<local_base_iterator>(Algorithm{}),
 169     std::forward<Args>(args)...);
 170   for(auto i:detail::segment_split(first,last)){
 171     auto it=alg(i);
 172     if(it!=i.end())
 173       return traits::iterator_from(
 174         it,traits::end_base_segment_info_iterator_from(last));
 175   }
 176   return last;
 177 }
 178
 179 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find)
 180
 181 template<
 182   typename... Ts,typename Iterator,typename T,
 183   enable_if_poly_collection_iterator<Iterator> =nullptr
 184 >
 185 Iterator find(const Iterator& first,const Iterator& last,const T& x)
 186 {
 187   return generic_find<std_find,Ts...>(first,last,x);
 188 }
 189
 190 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if)
 191
 192 template<
 193   typename... Ts,typename Iterator,typename Predicate,
 194   enable_if_poly_collection_iterator<Iterator> =nullptr
 195 >
 196 Iterator find_if(const Iterator& first,const Iterator& last,Predicate pred)
 197 {
 198   return generic_find<std_find_if,Ts...>(first,last,pred);
 199 }
 200
 201 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not)
 202
 203 template<
 204   typename... Ts,typename Iterator,typename Predicate,
 205   enable_if_poly_collection_iterator<Iterator> =nullptr
 206 >
 207 Iterator find_if_not(const Iterator& first,const Iterator& last,Predicate pred)
 208 {
 209   return generic_find<std_find_if_not,Ts...>(first,last,pred);
 210 }
 211
 212 /* find_end defined after search below */
 213
 214 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of)
 215
 216 template<
 217   typename... Ts,typename Iterator,typename ForwardIterator,
 218   enable_if_poly_collection_iterator<Iterator> =nullptr
 219 >
 220 Iterator find_first_of(
 221   const Iterator& first1,const Iterator& last1,
 222   ForwardIterator first2,ForwardIterator last2)
 223 {
 224   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2);
 225 }
 226
 227 template<
 228   typename... Ts,typename Iterator,
 229   typename ForwardIterator,typename BinaryPredicate,
 230   enable_if_poly_collection_iterator<Iterator> =nullptr
 231 >
 232 Iterator find_first_of(
 233   const Iterator& first1,const Iterator& last1,
 234   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
 235 {
 236   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred);
 237 }
 238
 239 template<typename... Ts>
 240 struct adjacent_find_alg
 241 {
 242   template<
 243     typename LocalIterator,typename BinaryPredicate,typename LocalBaseIterator
 244   >
 245   LocalBaseIterator operator()(
 246     LocalIterator first,LocalIterator last,BinaryPredicate pred,
 247     bool& carry,const std::type_info* prev_info, /* note the &s */
 248     LocalBaseIterator& prev)const
 249   {
 250     if(first==last)return LocalBaseIterator{last};
 251     if(carry){
 252       auto p=restitute_iterator<Ts...>(deref_to(pred));
 253       if(p(*prev_info,prev,first))return prev;
 254     }
 255     auto res=std::adjacent_find(first,last,pred);
 256     if(res==last){
 257       carry=true;
 258       prev_info=&typeid(
 259         typename std::iterator_traits<LocalIterator>::value_type);
 260       prev=LocalBaseIterator{last-1};
 261     }
 262     else carry=false;
 263     return LocalBaseIterator{res};
 264   }
 265 };
 266
 267 template<
 268   typename... Ts,typename Iterator,typename BinaryPredicate,
 269   enable_if_poly_collection_iterator<Iterator> =nullptr
 270 >
 271 Iterator adjacent_find(
 272   const Iterator& first,const Iterator& last,BinaryPredicate pred)
 273 {
 274   using traits=iterator_traits<Iterator>;
 275   using local_base_iterator=typename traits::local_base_iterator;
 276
 277   bool                  carry=false;
 278   const std::type_info* prev_info{&typeid(void)};
 279   local_base_iterator   prev;
 280   return generic_find<adjacent_find_alg<Ts...>,Ts...>(
 281     first,last,pred,carry,prev_info,prev);
 282 }
 283
 284 template<
 285   typename... Ts,typename Iterator,
 286   enable_if_poly_collection_iterator<Iterator> =nullptr
 287 >
 288 Iterator adjacent_find(const Iterator& first,const Iterator& last)
 289 {
 290   return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{});
 291 }
 292
 293 template<
 294   typename Algorithm,typename... Ts,
 295   typename Iterator,typename... Args,
 296   enable_if_poly_collection_iterator<Iterator> =nullptr
 297 >
 298 std::ptrdiff_t generic_count(
 299   const Iterator& first,const Iterator& last,Args&&... args)
 300 {
 301   auto alg=restitute_range<Ts...>(Algorithm{},std::forward<Args>(args)...);
 302   std::ptrdiff_t res=0;
 303   for(auto i:detail::segment_split(first,last))res+=alg(i);
 304   return res;
 305 }
 306
 307 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count)
 308
 309 template<
 310   typename... Ts,typename Iterator,typename T,
 311   enable_if_poly_collection_iterator<Iterator> =nullptr
 312 >
 313 std::ptrdiff_t count(const Iterator& first,const Iterator& last,const T& x)
 314 {
 315   return generic_count<std_count,Ts...>(first,last,x);
 316 }
 317
 318 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if)
 319
 320 template<
 321   typename... Ts,typename Iterator,typename Predicate,
 322   enable_if_poly_collection_iterator<Iterator> =nullptr
 323 >
 324 std::ptrdiff_t count_if(
 325   const Iterator& first,const Iterator& last,Predicate pred)
 326 {
 327   return generic_count<std_count_if,Ts...>(first,last,pred);
 328 }
 329
 330 struct mismatch_alg
 331 {
 332   template<
 333     typename InputIterator1,
 334     typename InputIterator2,typename BinaryPredicate
 335   >
 336   InputIterator1 operator()(
 337     InputIterator1 first1,InputIterator1 last1,
 338     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
 339   {
 340     while(first1!=last1&&pred(*first1,*first2)){
 341       ++first1;
 342       ++first2;
 343     }
 344     return first1;
 345   }
 346
 347   template<
 348     typename InputIterator1,
 349     typename InputIterator2,typename BinaryPredicate
 350   >
 351   InputIterator1 operator()(
 352     InputIterator1 first1,InputIterator1 last1,
 353     InputIterator2& first2,InputIterator2 last2, /* note the & */
 354     BinaryPredicate pred)const
 355   {
 356     while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){
 357       ++first1;
 358       ++first2;
 359     }
 360     return first1;
 361   }
 362 };
 363
 364 template<
 365   typename... Ts,typename Iterator,
 366   typename InputIterator,typename BinaryPredicate,
 367   enable_if_poly_collection_iterator<Iterator> =nullptr
 368 >
 369 std::pair<Iterator,InputIterator> mismatch(
 370   const Iterator& first1,const Iterator& last1,
 371   InputIterator first2,BinaryPredicate pred)
 372 {
 373   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred);
 374   return {it,first2};
 375 }
 376
 377 template<
 378   typename... Ts,typename Iterator,typename InputIterator,
 379   enable_if_poly_collection_iterator<Iterator> =nullptr
 380 >
 381 std::pair<Iterator,InputIterator> mismatch(
 382   const Iterator& first1,const Iterator& last1,InputIterator first2)
 383 {
 384   return algorithm::mismatch<Ts...>(
 385     first1,last1,first2,transparent_equal_to{});
 386 }
 387
 388 template<
 389   typename... Ts,typename Iterator,
 390   typename InputIterator,typename BinaryPredicate,
 391   enable_if_poly_collection_iterator<Iterator> =nullptr
 392 >
 393 std::pair<Iterator,InputIterator> mismatch(
 394   const Iterator& first1,const Iterator& last1,
 395   InputIterator first2,InputIterator last2,BinaryPredicate pred)
 396 {
 397   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred);
 398   return {it,first2};
 399 }
 400
 401 template<
 402   typename... Ts,typename Iterator,typename InputIterator,
 403   enable_if_poly_collection_iterator<Iterator> =nullptr
 404 >
 405 std::pair<Iterator,InputIterator> mismatch(
 406   const Iterator& first1,const Iterator& last1,
 407   InputIterator first2,InputIterator last2)
 408 {
 409   return algorithm::mismatch<Ts...>(
 410     first1,last1,first2,last2,transparent_equal_to{});
 411 }
 412
 413 struct equal_alg
 414 {
 415   template<
 416     typename InputIterator1,
 417     typename InputIterator2,typename BinaryPredicate
 418   >
 419   bool operator()(
 420     InputIterator1 first1,InputIterator1 last1,
 421     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
 422   {
 423     for(;first1!=last1;++first1,++first2){
 424       if(!pred(*first1,*first2))return false;
 425     }
 426     return true;
 427   }
 428
 429   template<
 430     typename InputIterator1,
 431     typename InputIterator2,typename BinaryPredicate
 432   >
 433   bool operator()(
 434     InputIterator1 first1,InputIterator1 last1,
 435     InputIterator2& first2,InputIterator2 last2, /* note the & */
 436     BinaryPredicate pred)const
 437   {
 438     for(;first1!=last1&&first2!=last2;++first1,++first2){
 439       if(!pred(*first1,*first2))return false;
 440     }
 441     return first1==last1; /* don't check first2==last2 as op is partial */
 442   }
 443 };
 444
 445 template<
 446   typename... Ts,typename Iterator,
 447   typename InputIterator,typename BinaryPredicate,
 448   enable_if_poly_collection_iterator<Iterator> =nullptr
 449 >
 450 bool equal(
 451   const Iterator& first1,const Iterator& last1,
 452   InputIterator first2,BinaryPredicate pred)
 453 {
 454   auto alg=restitute_range<Ts...>(equal_alg{},first2,pred);
 455   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
 456   return true;
 457 }
 458
 459 template<
 460   typename... Ts,typename Iterator,typename InputIterator,
 461   enable_if_poly_collection_iterator<Iterator> =nullptr
 462 >
 463 bool equal(
 464   const Iterator& first1,const Iterator& last1,InputIterator first2)
 465 {
 466   return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{});
 467 }
 468
 469 template<
 470   typename... Ts,typename Iterator,
 471   typename InputIterator,typename BinaryPredicate,
 472   enable_if_poly_collection_iterator<Iterator> =nullptr
 473 >
 474 bool equal(
 475   const Iterator& first1,const Iterator& last1,
 476   InputIterator first2,InputIterator last2,BinaryPredicate pred)
 477 {
 478   auto alg=restitute_range<Ts...>(equal_alg{},first2,last2,pred);
 479   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
 480   return first2==last2;
 481 }
 482
 483 template<
 484   typename... Ts,typename Iterator,typename InputIterator,
 485   enable_if_poly_collection_iterator<Iterator> =nullptr
 486 >
 487 bool equal(
 488   const Iterator& first1,const Iterator& last1,
 489   InputIterator first2,InputIterator last2)
 490 {
 491   return algorithm::equal<Ts...>(
 492     first1,last1,first2,last2,transparent_equal_to{});
 493 }
 494
 495 template<
 496   typename Iterator,
 497   enable_if_poly_collection_iterator<Iterator> =nullptr
 498 >
 499 std::ptrdiff_t fast_distance(const Iterator& first,const Iterator& last)
 500 {
 501   using traits=iterator_traits<Iterator>;
 502
 503   if(first==last)return 0;
 504
 505   auto sfirst=traits::base_segment_info_iterator_from(first),
 506        slast=traits::base_segment_info_iterator_from(last);
 507   if(sfirst==slast){
 508     return std::distance(
 509       traits::local_base_iterator_from(first),
 510       traits::local_base_iterator_from(last));
 511   }
 512   else{
 513     std::ptrdiff_t m=std::distance(
 514       traits::local_base_iterator_from(first),sfirst->end());
 515     while(++sfirst!=slast)m+=std::distance(sfirst->begin(),sfirst->end());
 516     if(slast!=traits::end_base_segment_info_iterator_from(last)){
 517       m+=std::distance(
 518         slast->begin(),traits::local_base_iterator_from(last));
 519     }
 520     return m;
 521   }
 522 }
 523
 524 template<
 525   typename... Ts,typename Iterator,
 526   typename ForwardIterator,typename BinaryPredicate,
 527   enable_if_poly_collection_iterator<Iterator> =nullptr
 528 >
 529 bool is_permutation_suffix(
 530   const Iterator& first1,const Iterator& last1,
 531   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
 532 {
 533   using traits=iterator_traits<Iterator>;
 534
 535   auto send=traits::end_base_segment_info_iterator_from(last1);
 536   for(auto i:detail::segment_split(first1,last1)){
 537     for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){
 538       auto& info=i.type_info();
 539       auto p=head_closure(
 540         restitute_iterator<Ts...>(deref_1st_to(pred)),info,lbscan);
 541       auto scan=traits::iterator_from(lbscan,send);
 542       if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue;
 543       std::ptrdiff_t matches=std::count_if(first2,last2,p);
 544       if(matches==0||
 545          matches!=algorithm::count_if<Ts...>(scan,last1,p))return false;
 546     }
 547   }
 548   return true;
 549 }
 550
 551 template<
 552   typename... Ts,typename Iterator,
 553   typename ForwardIterator,typename BinaryPredicate,
 554   enable_if_poly_collection_iterator<Iterator> =nullptr
 555 >
 556 bool is_permutation(
 557   Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred)
 558 {
 559   std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred);
 560   auto last2=std::next(first2,algorithm::fast_distance(first1,last1));
 561   return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
 562 }
 563
 564 template<
 565   typename... Ts,typename Iterator,typename ForwardIterator,
 566   enable_if_poly_collection_iterator<Iterator> =nullptr
 567 >
 568 bool is_permutation(
 569   const Iterator& first1,const Iterator& last1,ForwardIterator first2)
 570 {
 571   return algorithm::is_permutation<Ts...>(
 572     first1,last1,first2,transparent_equal_to{});
 573 }
 574
 575 template<
 576   typename... Ts,typename Iterator,
 577   typename ForwardIterator,typename BinaryPredicate,
 578   enable_if_poly_collection_iterator<Iterator> =nullptr
 579 >
 580 bool is_permutation(
 581   Iterator first1,Iterator last1,
 582   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
 583 {
 584   std::tie(first1,first2)=algorithm::mismatch<Ts...>(
 585     first1,last1,first2,last2,pred);
 586   if(algorithm::fast_distance(first1,last1)!=std::distance(first2,last2))
 587     return false;
 588   else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
 589 }
 590
 591 template<
 592   typename... Ts,typename Iterator,typename ForwardIterator,
 593   enable_if_poly_collection_iterator<Iterator> =nullptr
 594 >
 595 bool is_permutation(
 596   const Iterator& first1,const Iterator& last1,
 597   ForwardIterator first2,ForwardIterator last2)
 598 {
 599   return algorithm::is_permutation<Ts...>(
 600     first1,last1,first2,last2,transparent_equal_to{});
 601 }
 602
 603 template<
 604   typename... Ts,typename Iterator,
 605   typename ForwardIterator,typename BinaryPredicate,
 606   enable_if_poly_collection_iterator<Iterator> =nullptr
 607 >
 608 Iterator search(
 609   const Iterator& first1,const Iterator& last1,
 610   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
 611 {
 612   using traits=iterator_traits<Iterator>;
 613
 614   auto send=traits::end_base_segment_info_iterator_from(last1);
 615   for(auto i:detail::segment_split(first1,last1)){
 616     for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){
 617       Iterator it=traits::iterator_from(lbit,send);
 618       if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2)
 619         return it;
 620     }
 621   }
 622   return last1;
 623 }
 624
 625 template<
 626   typename... Ts,typename Iterator,typename ForwardIterator,
 627   enable_if_poly_collection_iterator<Iterator> =nullptr
 628 >
 629 Iterator search(
 630   const Iterator& first1,const Iterator& last1,
 631   ForwardIterator first2,ForwardIterator last2)
 632 {
 633   return algorithm::search<Ts...>(
 634     first1,last1,first2,last2,transparent_equal_to{});
 635 }
 636
 637 template<
 638   typename... Ts,typename Iterator,
 639   typename ForwardIterator,typename BinaryPredicate,
 640   enable_if_poly_collection_iterator<Iterator> =nullptr
 641 >
 642 Iterator find_end(
 643   Iterator first1,Iterator last1,
 644   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
 645 {
 646   if(first2==last2)return last1;
 647
 648   for(Iterator res=last1;;){
 649     Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred);
 650     if(res1==last1)return res;
 651     else{
 652       first1=res=res1;
 653       ++first1;
 654     }
 655   }
 656 }
 657
 658 template<
 659   typename... Ts,typename Iterator,typename ForwardIterator,
 660   enable_if_poly_collection_iterator<Iterator> =nullptr
 661 >
 662 Iterator find_end(
 663   const Iterator& first1,const Iterator& last1,
 664   ForwardIterator first2,ForwardIterator last2)
 665 {
 666   return algorithm::find_end<Ts...>(
 667     first1,last1,first2,last2,transparent_equal_to{});
 668 }
 669
 670 struct search_n_alg
 671 {
 672   template<
 673     typename ForwardIterator,typename Size,
 674     typename T,typename BinaryPredicate
 675   >
 676   ForwardIterator operator()(
 677     ForwardIterator first,ForwardIterator last,
 678     Size count,bool& carry,Size& remain,const T& x, /* note the &s */
 679     BinaryPredicate pred)const
 680   {
 681     for(;first!=last;++first){
 682       if(!pred(*first,x)){carry=false;remain=count;continue;}
 683       auto res=first;
 684       for(;;){
 685         if(--remain==0||++first==last)return res;
 686         if(!pred(*first,x)){carry=false;remain=count;break;}
 687       }
 688     }
 689     return last;
 690   }
 691 };
 692
 693 template<
 694   typename... Ts,typename Iterator,
 695   typename Size,typename T,typename BinaryPredicate,
 696   enable_if_poly_collection_iterator<Iterator> =nullptr
 697 >
 698 Iterator search_n(
 699   const Iterator& first,const Iterator& last,
 700   Size count,const T& x,BinaryPredicate pred)
 701 {
 702   using traits=iterator_traits<Iterator>;
 703   using local_base_iterator=typename traits::local_base_iterator;
 704
 705   if(count<=0)return first;
 706
 707   bool                carry=false;
 708   auto                remain=count;
 709   auto                alg=restitute_range<Ts...>(
 710                         cast_return<local_base_iterator>(search_n_alg{}),
 711                         count,carry,remain,x,pred);
 712   local_base_iterator prev;
 713   for(auto i:detail::segment_split(first,last)){
 714     auto it=alg(i);
 715     if(it!=i.end()){
 716       if(remain==0)
 717         return traits::iterator_from(
 718           carry?prev:it,
 719           traits::end_base_segment_info_iterator_from(last));
 720       else if(!carry){prev=it;carry=true;}
 721     }
 722   }
 723   return last;
 724 }
 725
 726 template<
 727   typename... Ts,typename Iterator,
 728   typename Size,typename T,
 729   enable_if_poly_collection_iterator<Iterator> =nullptr
 730 >
 731 Iterator search_n(
 732   const Iterator& first,const Iterator& last,Size count,const T& x)
 733 {
 734   return algorithm::search_n<Ts...>(
 735     first,last,count,x,transparent_equal_to{});
 736 }
 737
 738 template<
 739   typename Algorithm,typename... Ts,
 740   typename Iterator,typename OutputIterator,typename... Args,
 741   enable_if_poly_collection_iterator<Iterator> =nullptr
 742 >
 743 OutputIterator generic_copy(
 744   const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args)
 745 {
 746   for(auto i:detail::segment_split(first,last)){
 747     auto alg=restitute_range<Ts...>(
 748       Algorithm{},res,std::forward<Args>(args)...);
 749     res=alg(i);
 750   }
 751   return res;
 752 }
 753
 754 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy)
 755
 756 template<
 757   typename... Ts,typename Iterator,typename OutputIterator,
 758   enable_if_poly_collection_iterator<Iterator> =nullptr
 759 >
 760 OutputIterator copy(
 761   const Iterator& first,const Iterator& last,OutputIterator res)
 762 {
 763   return generic_copy<std_copy,Ts...>(first,last,res);
 764 }
 765
 766 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n)
 767
 768 template<
 769   typename... Ts,typename Iterator,typename Size,typename OutputIterator,
 770   enable_if_poly_collection_iterator<Iterator> =nullptr
 771 >
 772 OutputIterator copy_n(const Iterator& first,Size count,OutputIterator res)
 773 {
 774   using traits=iterator_traits<Iterator>;
 775
 776   if(count<=0)return res;
 777
 778   auto lbit=traits::local_base_iterator_from(first);
 779   auto sit=traits::base_segment_info_iterator_from(first);
 780   for(;;){
 781     auto n=(std::min)(count,sit->end()-lbit);
 782     auto alg=restitute_iterator<Ts...>(std_copy_n{},n,res);
 783     res=alg(sit->type_info(),lbit);
 784     if((count-=n)==0)break;
 785     ++sit;
 786     lbit=sit->begin();
 787   }
 788   return res;
 789 }
 790
 791 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if)
 792
 793 template<
 794   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
 795   enable_if_poly_collection_iterator<Iterator> =nullptr
 796 >
 797 OutputIterator copy_if(
 798   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
 799 {
 800   return generic_copy<std_copy_if,Ts...>(first,last,res,pred);
 801 }
 802
 803 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move)
 804
 805 template<
 806   typename... Ts,typename Iterator,typename OutputIterator,
 807   enable_if_poly_collection_iterator<Iterator> =nullptr
 808 >
 809 OutputIterator move(
 810   const Iterator& first,const Iterator& last,OutputIterator res)
 811 {
 812   return generic_copy<std_move,Ts...>(first,last,res);
 813 }
 814
 815 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform)
 816
 817 template<
 818   typename... Ts,typename Iterator,
 819   typename OutputIterator,typename UnaryOperation,
 820   enable_if_poly_collection_iterator<Iterator> =nullptr
 821 >
 822 OutputIterator transform(
 823   const Iterator& first,const Iterator& last,
 824   OutputIterator res,UnaryOperation op)
 825 {
 826   return generic_copy<std_transform,Ts...>(first,last,res,op);
 827 }
 828
 829 struct transform2_alg
 830 {
 831   template<
 832     typename InputIterator1,typename InputIterator2,
 833     typename OutputIterator,typename BinaryOperation
 834   >
 835   OutputIterator operator()(
 836     InputIterator1 first1,InputIterator1 last1,
 837     OutputIterator res, /* third place for compatibility with generic_copy */
 838     InputIterator2& first2, BinaryOperation op)const         /* note the & */
 839   {
 840     while(first1!=last1)*res++=op(*first1++,*first2++);
 841     return res;
 842   }
 843 };
 844
 845 template<
 846   typename... Ts,typename Iterator,typename InputIterator,
 847   typename OutputIterator,typename BinaryOperation,
 848   enable_if_poly_collection_iterator<Iterator> =nullptr
 849 >
 850 OutputIterator transform(
 851   const Iterator& first1,const Iterator& last1,InputIterator first2,
 852   OutputIterator res,BinaryOperation op)
 853 {
 854   return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op);
 855 }
 856
 857 struct replace_copy_alg
 858 {
 859   /* std::replace_copy broken in VS2015, internal ticket VSO#279818
 860    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
 861    * conditional operator".
 862    */
 863
 864   template<typename InputIterator,typename OutputIterator,typename T>
 865   OutputIterator operator()(
 866     InputIterator first,InputIterator last,OutputIterator res,
 867     const T& old_x,const T& new_x)
 868   {
 869     for(;first!=last;++first,++res){
 870       if(*first==old_x)*res=new_x;
 871       else             *res=*first;
 872     }
 873     return res;
 874   }
 875 };
 876
 877 template<
 878   typename... Ts,typename Iterator,typename OutputIterator,typename T,
 879   enable_if_poly_collection_iterator<Iterator> =nullptr
 880 >
 881 OutputIterator replace_copy(
 882   const Iterator& first,const Iterator& last,OutputIterator res,
 883   const T& old_x,const T& new_x)
 884 {
 885   return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x);
 886 }
 887
 888 struct replace_copy_if_alg
 889 {
 890   /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818
 891    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
 892    * conditional operator".
 893    */
 894
 895   template<
 896     typename InputIterator,typename OutputIterator,
 897     typename Predicate,typename T
 898   >
 899   OutputIterator operator()(
 900     InputIterator first,InputIterator last,OutputIterator res,
 901     Predicate pred,const T& new_x)
 902   {
 903     for(;first!=last;++first,++res){
 904       if(pred(*first))*res=new_x;
 905       else            *res=*first;
 906     }
 907     return res;
 908   }
 909 };
 910
 911 template<
 912   typename... Ts,typename Iterator,typename OutputIterator,
 913   typename Predicate,typename T,
 914   enable_if_poly_collection_iterator<Iterator> =nullptr
 915 >
 916 OutputIterator replace_copy_if(
 917   const Iterator& first,const Iterator& last,OutputIterator res,
 918   Predicate pred,const T& new_x)
 919 {
 920   return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x);
 921 }
 922
 923 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy)
 924
 925 template<
 926   typename... Ts,typename Iterator,typename OutputIterator,typename T,
 927   enable_if_poly_collection_iterator<Iterator> =nullptr
 928 >
 929 OutputIterator remove_copy(
 930   const Iterator& first,const Iterator& last,OutputIterator res,const T& x)
 931 {
 932   return generic_copy<std_remove_copy,Ts...>(first,last,res,x);
 933 }
 934
 935 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(
 936   std_remove_copy_if,std::remove_copy_if)
 937
 938 template<
 939   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
 940   enable_if_poly_collection_iterator<Iterator> =nullptr
 941 >
 942 OutputIterator remove_copy_if(
 943   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
 944 {
 945   return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred);
 946 }
 947
 948 template<typename... Ts>
 949 struct unique_copy_alg
 950 {
 951   template<
 952     typename LocalIterator,typename OutputIterator,
 953     typename BinaryPredicate,typename LocalBaseIterator
 954   >
 955   OutputIterator operator()(
 956     LocalIterator first,LocalIterator last,
 957     OutputIterator res, BinaryPredicate pred,
 958     bool& carry,const std::type_info* prev_info, /* note the &s */
 959     LocalBaseIterator& prev)const
 960   {
 961     if(carry){
 962       auto p=restitute_iterator<Ts...>(deref_to(pred));
 963       for(;first!=last;++first)if(!p(*prev_info,prev,first))break;
 964     }
 965     if(first==last)return res;
 966     res=std::unique_copy(first,last,res,pred);
 967     carry=true;
 968     prev_info=&typeid(
 969       typename std::iterator_traits<LocalIterator>::value_type);
 970     prev=LocalBaseIterator{last-1};
 971     return res;
 972   }
 973 };
 974
 975 template<
 976   typename... Ts,typename Iterator,
 977   typename OutputIterator,typename BinaryPredicate,
 978   enable_if_poly_collection_iterator<Iterator> =nullptr
 979 >
 980 OutputIterator unique_copy(
 981   const Iterator& first,const Iterator& last,
 982   OutputIterator res,BinaryPredicate pred)
 983 {
 984   using traits=iterator_traits<Iterator>;
 985   using local_base_iterator=typename traits::local_base_iterator;
 986
 987   bool                  carry=false;
 988   const std::type_info* prev_info{&typeid(void)};
 989   local_base_iterator   prev;
 990   return generic_copy<unique_copy_alg<Ts...>,Ts...>(
 991     first,last,res,pred,carry,prev_info,prev);
 992 }
 993
 994 template<
 995   typename... Ts,typename Iterator,typename OutputIterator,
 996   enable_if_poly_collection_iterator<Iterator> =nullptr
 997 >
 998 OutputIterator unique_copy(
 999   const Iterator& first,const Iterator& last,OutputIterator res)
1000 {
1001   return algorithm::unique_copy<Ts...>(first,last,res,transparent_equal_to{});
1002 }
1003
1004 template<
1005   typename... Ts,typename Iterator,typename OutputIterator,
1006   enable_if_poly_collection_iterator<Iterator> =nullptr
1007 >
1008 OutputIterator rotate_copy(
1009   const Iterator& first,const Iterator& middle,const Iterator& last,
1010   OutputIterator res)
1011 {
1012   res=algorithm::copy<Ts...>(middle,last,res);
1013   return algorithm::copy<Ts...>(first,middle,res);
1014 }
1015
1016 struct sample_alg
1017 {
1018   template<
1019     typename InputIterator,typename OutputIterator,
1020     typename Distance,typename UniformRandomBitGenerator
1021   >
1022   OutputIterator operator()(
1023     InputIterator first,InputIterator last,
1024     OutputIterator res,Distance& n,Distance& m, /* note the &s */
1025     UniformRandomBitGenerator& g)const
1026   {
1027     for(;first!=last&&n!=0;++first){
1028       auto r=std::uniform_int_distribution<Distance>(0,--m)(g);
1029       if (r<n){
1030         *res++=*first;
1031         --n;
1032       }
1033     }
1034     return res;
1035   }
1036 };
1037
1038 template<
1039   typename... Ts,typename Iterator,typename OutputIterator,
1040   typename Distance,typename UniformRandomBitGenerator,
1041   enable_if_poly_collection_iterator<Iterator> =nullptr
1042 >
1043 OutputIterator sample(
1044   const Iterator& first,const Iterator& last,
1045   OutputIterator res,Distance n,UniformRandomBitGenerator&& g)
1046 {
1047   Distance m=algorithm::fast_distance(first,last);
1048   n=(std::min)(n,m);
1049
1050   for(auto i:detail::segment_split(first,last)){
1051     auto alg=restitute_range<Ts...>(sample_alg{},res,n,m,g);
1052     res=alg(i);
1053     if(n==0)return res;
1054   }
1055   return res; /* never reached */
1056 }
1057
1058 template<
1059   typename... Ts,typename Iterator,typename Predicate,
1060   enable_if_poly_collection_iterator<Iterator> =nullptr
1061 >
1062 bool is_partitioned(const Iterator& first,const Iterator& last,Predicate pred)
1063 {
1064   auto it=algorithm::find_if_not<Ts...>(first,last,pred);
1065   if(it==last)return true;
1066   return algorithm::none_of<Ts...>(++it,last,pred);
1067 }
1068
1069 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(
1070   std_partition_copy,std::partition_copy)
1071
1072 template<
1073   typename... Ts,typename Iterator,
1074   typename OutputIterator1,typename OutputIterator2,typename Predicate,
1075   enable_if_poly_collection_iterator<Iterator> =nullptr
1076 >
1077 std::pair<OutputIterator1,OutputIterator2> partition_copy(
1078   const Iterator& first,const Iterator& last,
1079   OutputIterator1 rest,OutputIterator2 resf,Predicate pred)
1080 {
1081   for(auto i:detail::segment_split(first,last)){
1082     auto alg=restitute_range<Ts...>(std_partition_copy{},rest,resf,pred);
1083     std::tie(rest,resf)=alg(i);
1084   }
1085   return {rest,resf};
1086 }
1087
1088 template<typename Predicate,typename... Ts>
1089 struct partition_point_pred
1090 {
1091   partition_point_pred(const Predicate& pred):pred(pred){}
1092
1093   template<typename Iterator>
1094   bool operator()(const Iterator& it)const
1095   {
1096     using traits=iterator_traits<Iterator>;
1097     auto p=restitute_iterator<Ts...>(deref_to(pred));
1098     return p(
1099       traits::base_segment_info_iterator_from(it)->type_info(),
1100       traits::local_base_iterator_from(it));
1101   }
1102
1103   Predicate pred;
1104 };
1105
1106 template<
1107   typename... Ts,typename Iterator,typename Predicate,
1108   enable_if_poly_collection_iterator<Iterator> =nullptr
1109 >
1110 Iterator partition_point(
1111   const Iterator& first,const Iterator& last,Predicate pred)
1112 {
1113   auto_iterator<Iterator>               afirst{first},alast{last};
1114   partition_point_pred<Predicate,Ts...> p{pred};
1115   return *std::partition_point(afirst,alast,p);
1116 }
1117
1118 } /* namespace poly_collection::detail::algorithm */
1119
1120 } /* namespace poly_collection::detail */
1121
1122 /* non-modifying sequence operations */
1123
1124 using detail::algorithm::all_of;
1125 using detail::algorithm::any_of;
1126 using detail::algorithm::none_of;
1127 using detail::algorithm::for_each;
1128 using detail::algorithm::for_each_n;
1129 using detail::algorithm::find;
1130 using detail::algorithm::find_if;
1131 using detail::algorithm::find_if_not;
1132 using detail::algorithm::find_end;
1133 using detail::algorithm::find_first_of;
1134 using detail::algorithm::adjacent_find;
1135 using detail::algorithm::count;
1136 using detail::algorithm::count_if;
1137 using detail::algorithm::mismatch;
1138 using detail::algorithm::equal;
1139 using detail::algorithm::is_permutation;
1140 using detail::algorithm::search;
1141 using detail::algorithm::search_n;
1142
1143 /* modifying sequence operations */
1144
1145 using detail::algorithm::copy;
1146 using detail::algorithm::copy_n;
1147 using detail::algorithm::copy_if;
1148                       /* copy_backward requires BidirectionalIterator */
1149 using detail::algorithm::move;
1150                       /* move_backward requires BidirectionalIterator */
1151                       /* swap_ranges requires Swappable */
1152                       /* iter_swap requires Swappable */
1153 using detail::algorithm::transform;
1154                       /* replace requires Assignable */
1155                       /* replace_if requires Assignable */
1156 using detail::algorithm::replace_copy;
1157 using detail::algorithm::replace_copy_if;
1158                       /* fill requires Assignable */
1159                       /* fill_n requires Assignable */
1160                       /* generate requires Assignable */
1161                       /* generate_n requires Assignable */
1162                       /* remove requires MoveAssignable */
1163                       /* remove_if requires MoveAssignable */
1164 using detail::algorithm::remove_copy;
1165 using detail::algorithm::remove_copy_if;
1166                       /* unique requires MoveAssignable */
1167 using detail::algorithm::unique_copy;
1168                       /* reverse requires BidirectionalIterator */
1169                       /* reverse_copy requires BidirectionalIterator */
1170                       /* rotate requires MoveAssignable */
1171 using detail::algorithm::rotate_copy;
1172 using detail::algorithm::sample;
1173                       /* shuffle requires RandomAccessIterator */
1174 using detail::algorithm::is_partitioned;
1175                       /* partition requires Swappable */
1176                       /* stable_partition requires Swappable */
1177 using detail::algorithm::partition_copy;
1178 using detail::algorithm::partition_point;
1179
1180 /* sorting and related operations not provided */
1181
1182 } /* namespace poly_collection */
1183
1184 } /* namespace boost */
1185
1186 #endif