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