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