boost/poly_collection/algorithm.hpp

0001 /* Copyright 2016-2020 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/poly_collection for library home page.
0007  */
0008
0009 #ifndef BOOST_POLY_COLLECTION_ALGORITHM_HPP
0010 #define BOOST_POLY_COLLECTION_ALGORITHM_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <algorithm>
0017 #include <boost/poly_collection/detail/auto_iterator.hpp>
0018 #include <boost/poly_collection/detail/functional.hpp>
0019 #include <boost/poly_collection/detail/iterator_traits.hpp>
0020 #include <boost/poly_collection/detail/segment_split.hpp>
0021 #include <boost/poly_collection/detail/type_restitution.hpp>
0022 #include <iterator>
0023 #include <random>
0024 #include <type_traits>
0025 #include <utility>
0026
0027 /* Improved performance versions of std algorithms over poly_collection.
0028  * poly_collection::alg is expected to be faster than the homonym std::alg
0029  * because the latter does a traversal over a segmented structured, where
0030  * incrementing requires checking for segment change, whereas the former
0031  * for-loops over flat segments.
0032  * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when
0033  * passing elements to f, i.e. if the concrete type of the element is Ti
0034  * then f is invoked with a [const] Ti&, which can dramatically improve
0035  * performance when f has specific overloads for Ti (like, for instance,
0036  * generic lambdas) as static optimization can kick in (devirtualization
0037  * being a particular example).
0038  */
0039
0040 namespace boost{
0041
0042 namespace poly_collection{
0043
0044 namespace detail{
0045
0046 namespace algorithm{
0047
0048 template<typename Iterator>
0049 using enable_if_poly_collection_iterator=typename std::enable_if<
0050   !std::is_void<typename poly_collection_of<Iterator>::type>::value
0051 >::type*;
0052
0053 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of)
0054
0055 template<
0056   typename... Ts,typename Iterator,typename Predicate,
0057   enable_if_poly_collection_iterator<Iterator> =nullptr
0058 >
0059 bool all_of(const Iterator& first,const Iterator& last,Predicate pred)
0060 {
0061   auto alg=restitute_range<Ts...>(std_all_of{},pred);
0062   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
0063   return true;
0064 }
0065
0066 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of)
0067
0068 template<
0069   typename... Ts,typename Iterator,typename Predicate,
0070   enable_if_poly_collection_iterator<Iterator> =nullptr
0071 >
0072 bool any_of(const Iterator& first,const Iterator& last,Predicate pred)
0073 {
0074   auto alg=restitute_range<Ts...>(std_any_of{},pred);
0075   for(auto i:detail::segment_split(first,last))if(alg(i))return true;
0076   return false;
0077 }
0078
0079 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of)
0080
0081 template<
0082   typename... Ts,typename Iterator,typename Predicate,
0083   enable_if_poly_collection_iterator<Iterator> =nullptr
0084 >
0085 bool none_of(const Iterator& first,const Iterator& last,Predicate pred)
0086 {
0087   auto alg=restitute_range<Ts...>(std_none_of{},pred);
0088   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
0089   return true;
0090 }
0091
0092 struct for_each_alg
0093 {
0094   template<typename InputIterator,typename Function>
0095   void operator()(
0096     InputIterator first,InputIterator last,Function& f)const /* note the & */
0097   {
0098     for(;first!=last;++first)f(*first);
0099   }
0100 };
0101
0102 template<
0103   typename... Ts,typename Iterator,typename Function,
0104   enable_if_poly_collection_iterator<Iterator> =nullptr
0105 >
0106 Function for_each(const Iterator& first,const Iterator& last,Function f)
0107 {
0108   for_each_segment(first,last,restitute_range<Ts...>(for_each_alg{},f));
0109   return f;
0110 }
0111
0112 struct for_each_n_alg
0113 {
0114   template<
0115     typename InputIterator,typename Size,typename Function
0116   >
0117   InputIterator operator()(
0118     InputIterator first,Size n,Function& f)const /* note the & */
0119   {
0120     for(;n>0;++first,(void)--n)f(*first);
0121     return first;
0122   }
0123 };
0124
0125 template<
0126   typename... Ts,typename Iterator,typename Size,typename Function,
0127   enable_if_poly_collection_iterator<Iterator> =nullptr
0128 >
0129 Iterator for_each_n(const Iterator& first,Size n,Function f)
0130 {
0131   using traits=iterator_traits<Iterator>;
0132   using local_base_iterator=typename traits::local_base_iterator;
0133
0134   if(n<=0)return first;
0135
0136   auto alg=restitute_iterator<Ts...>(
0137          cast_return<local_base_iterator>(for_each_n_alg{}));
0138   auto lbit=traits::local_base_iterator_from(first);
0139   auto sit=traits::base_segment_info_iterator_from(first);
0140   for(;;){
0141     auto m=sit->end()-lbit;
0142     if(n<=m){
0143       auto it=alg(sit->type_info(),lbit,n,f);
0144       return traits::iterator_from(
0145         it,traits::end_base_segment_info_iterator_from(first));
0146     }
0147     else{
0148       alg(sit->type_info(),lbit,m,f);
0149       n-=m;
0150     }
0151     ++sit;
0152     lbit=sit->begin();
0153   }
0154 }
0155
0156 template<
0157   typename Algorithm,typename... Ts,
0158   typename Iterator,typename... Args,
0159   enable_if_poly_collection_iterator<Iterator> =nullptr
0160 >
0161 Iterator generic_find(
0162   const Iterator& first,const Iterator& last,Args&&... args)
0163 {
0164   using traits=iterator_traits<Iterator>;
0165   using local_base_iterator=typename traits::local_base_iterator;
0166
0167   auto alg=restitute_range<Ts...>(
0168     cast_return<local_base_iterator>(Algorithm{}),
0169     std::forward<Args>(args)...);
0170   for(auto i:detail::segment_split(first,last)){
0171     auto it=alg(i);
0172     if(it!=i.end())
0173       return traits::iterator_from(
0174         it,traits::end_base_segment_info_iterator_from(last));
0175   }
0176   return last;
0177 }
0178
0179 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find)
0180
0181 template<
0182   typename... Ts,typename Iterator,typename T,
0183   enable_if_poly_collection_iterator<Iterator> =nullptr
0184 >
0185 Iterator find(const Iterator& first,const Iterator& last,const T& x)
0186 {
0187   return generic_find<std_find,Ts...>(first,last,x);
0188 }
0189
0190 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if)
0191
0192 template<
0193   typename... Ts,typename Iterator,typename Predicate,
0194   enable_if_poly_collection_iterator<Iterator> =nullptr
0195 >
0196 Iterator find_if(const Iterator& first,const Iterator& last,Predicate pred)
0197 {
0198   return generic_find<std_find_if,Ts...>(first,last,pred);
0199 }
0200
0201 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not)
0202
0203 template<
0204   typename... Ts,typename Iterator,typename Predicate,
0205   enable_if_poly_collection_iterator<Iterator> =nullptr
0206 >
0207 Iterator find_if_not(const Iterator& first,const Iterator& last,Predicate pred)
0208 {
0209   return generic_find<std_find_if_not,Ts...>(first,last,pred);
0210 }
0211
0212 /* find_end defined after search below */
0213
0214 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of)
0215
0216 template<
0217   typename... Ts,typename Iterator,typename ForwardIterator,
0218   enable_if_poly_collection_iterator<Iterator> =nullptr
0219 >
0220 Iterator find_first_of(
0221   const Iterator& first1,const Iterator& last1,
0222   ForwardIterator first2,ForwardIterator last2)
0223 {
0224   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2);
0225 }
0226
0227 template<
0228   typename... Ts,typename Iterator,
0229   typename ForwardIterator,typename BinaryPredicate,
0230   enable_if_poly_collection_iterator<Iterator> =nullptr
0231 >
0232 Iterator find_first_of(
0233   const Iterator& first1,const Iterator& last1,
0234   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0235 {
0236   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred);
0237 }
0238
0239 template<typename... Ts>
0240 struct adjacent_find_alg
0241 {
0242   template<
0243     typename LocalIterator,typename BinaryPredicate,typename LocalBaseIterator
0244   >
0245   LocalBaseIterator operator()(
0246     LocalIterator first,LocalIterator last,BinaryPredicate pred,
0247     bool& carry,const std::type_info* prev_info, /* note the &s */
0248     LocalBaseIterator& prev)const
0249   {
0250     if(first==last)return LocalBaseIterator{last};
0251     if(carry){
0252       auto p=restitute_iterator<Ts...>(deref_to(pred));
0253       if(p(*prev_info,prev,first))return prev;
0254     }
0255     auto res=std::adjacent_find(first,last,pred);
0256     if(res==last){
0257       carry=true;
0258       prev_info=&typeid(
0259         typename std::iterator_traits<LocalIterator>::value_type);
0260       prev=LocalBaseIterator{last-1};
0261     }
0262     else carry=false;
0263     return LocalBaseIterator{res};
0264   }
0265 };
0266
0267 template<
0268   typename... Ts,typename Iterator,typename BinaryPredicate,
0269   enable_if_poly_collection_iterator<Iterator> =nullptr
0270 >
0271 Iterator adjacent_find(
0272   const Iterator& first,const Iterator& last,BinaryPredicate pred)
0273 {
0274   using traits=iterator_traits<Iterator>;
0275   using local_base_iterator=typename traits::local_base_iterator;
0276
0277   bool                  carry=false;
0278   const std::type_info* prev_info{&typeid(void)};
0279   local_base_iterator   prev;
0280   return generic_find<adjacent_find_alg<Ts...>,Ts...>(
0281     first,last,pred,carry,prev_info,prev);
0282 }
0283
0284 template<
0285   typename... Ts,typename Iterator,
0286   enable_if_poly_collection_iterator<Iterator> =nullptr
0287 >
0288 Iterator adjacent_find(const Iterator& first,const Iterator& last)
0289 {
0290   return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{});
0291 }
0292
0293 template<
0294   typename Algorithm,typename... Ts,
0295   typename Iterator,typename... Args,
0296   enable_if_poly_collection_iterator<Iterator> =nullptr
0297 >
0298 std::ptrdiff_t generic_count(
0299   const Iterator& first,const Iterator& last,Args&&... args)
0300 {
0301   auto alg=restitute_range<Ts...>(Algorithm{},std::forward<Args>(args)...);
0302   std::ptrdiff_t res=0;
0303   for(auto i:detail::segment_split(first,last))res+=alg(i);
0304   return res;
0305 }
0306
0307 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count)
0308
0309 template<
0310   typename... Ts,typename Iterator,typename T,
0311   enable_if_poly_collection_iterator<Iterator> =nullptr
0312 >
0313 std::ptrdiff_t count(const Iterator& first,const Iterator& last,const T& x)
0314 {
0315   return generic_count<std_count,Ts...>(first,last,x);
0316 }
0317
0318 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if)
0319
0320 template<
0321   typename... Ts,typename Iterator,typename Predicate,
0322   enable_if_poly_collection_iterator<Iterator> =nullptr
0323 >
0324 std::ptrdiff_t count_if(
0325   const Iterator& first,const Iterator& last,Predicate pred)
0326 {
0327   return generic_count<std_count_if,Ts...>(first,last,pred);
0328 }
0329
0330 struct mismatch_alg
0331 {
0332   template<
0333     typename InputIterator1,
0334     typename InputIterator2,typename BinaryPredicate
0335   >
0336   InputIterator1 operator()(
0337     InputIterator1 first1,InputIterator1 last1,
0338     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
0339   {
0340     while(first1!=last1&&pred(*first1,*first2)){
0341       ++first1;
0342       ++first2;
0343     }
0344     return first1;
0345   }
0346
0347   template<
0348     typename InputIterator1,
0349     typename InputIterator2,typename BinaryPredicate
0350   >
0351   InputIterator1 operator()(
0352     InputIterator1 first1,InputIterator1 last1,
0353     InputIterator2& first2,InputIterator2 last2, /* note the & */
0354     BinaryPredicate pred)const
0355   {
0356     while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){
0357       ++first1;
0358       ++first2;
0359     }
0360     return first1;
0361   }
0362 };
0363
0364 template<
0365   typename... Ts,typename Iterator,
0366   typename InputIterator,typename BinaryPredicate,
0367   enable_if_poly_collection_iterator<Iterator> =nullptr
0368 >
0369 std::pair<Iterator,InputIterator> mismatch(
0370   const Iterator& first1,const Iterator& last1,
0371   InputIterator first2,BinaryPredicate pred)
0372 {
0373   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred);
0374   return {it,first2};
0375 }
0376
0377 template<
0378   typename... Ts,typename Iterator,typename InputIterator,
0379   enable_if_poly_collection_iterator<Iterator> =nullptr
0380 >
0381 std::pair<Iterator,InputIterator> mismatch(
0382   const Iterator& first1,const Iterator& last1,InputIterator first2)
0383 {
0384   return algorithm::mismatch<Ts...>(
0385     first1,last1,first2,transparent_equal_to{});
0386 }
0387
0388 template<
0389   typename... Ts,typename Iterator,
0390   typename InputIterator,typename BinaryPredicate,
0391   enable_if_poly_collection_iterator<Iterator> =nullptr
0392 >
0393 std::pair<Iterator,InputIterator> mismatch(
0394   const Iterator& first1,const Iterator& last1,
0395   InputIterator first2,InputIterator last2,BinaryPredicate pred)
0396 {
0397   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred);
0398   return {it,first2};
0399 }
0400
0401 template<
0402   typename... Ts,typename Iterator,typename InputIterator,
0403   enable_if_poly_collection_iterator<Iterator> =nullptr
0404 >
0405 std::pair<Iterator,InputIterator> mismatch(
0406   const Iterator& first1,const Iterator& last1,
0407   InputIterator first2,InputIterator last2)
0408 {
0409   return algorithm::mismatch<Ts...>(
0410     first1,last1,first2,last2,transparent_equal_to{});
0411 }
0412
0413 struct equal_alg
0414 {
0415   template<
0416     typename InputIterator1,
0417     typename InputIterator2,typename BinaryPredicate
0418   >
0419   bool operator()(
0420     InputIterator1 first1,InputIterator1 last1,
0421     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
0422   {
0423     for(;first1!=last1;++first1,++first2){
0424       if(!pred(*first1,*first2))return false;
0425     }
0426     return true;
0427   }
0428
0429   template<
0430     typename InputIterator1,
0431     typename InputIterator2,typename BinaryPredicate
0432   >
0433   bool operator()(
0434     InputIterator1 first1,InputIterator1 last1,
0435     InputIterator2& first2,InputIterator2 last2, /* note the & */
0436     BinaryPredicate pred)const
0437   {
0438     for(;first1!=last1&&first2!=last2;++first1,++first2){
0439       if(!pred(*first1,*first2))return false;
0440     }
0441     return first1==last1; /* don't check first2==last2 as op is partial */
0442   }
0443 };
0444
0445 template<
0446   typename... Ts,typename Iterator,
0447   typename InputIterator,typename BinaryPredicate,
0448   enable_if_poly_collection_iterator<Iterator> =nullptr
0449 >
0450 bool equal(
0451   const Iterator& first1,const Iterator& last1,
0452   InputIterator first2,BinaryPredicate pred)
0453 {
0454   auto alg=restitute_range<Ts...>(equal_alg{},first2,pred);
0455   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
0456   return true;
0457 }
0458
0459 template<
0460   typename... Ts,typename Iterator,typename InputIterator,
0461   enable_if_poly_collection_iterator<Iterator> =nullptr
0462 >
0463 bool equal(
0464   const Iterator& first1,const Iterator& last1,InputIterator first2)
0465 {
0466   return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{});
0467 }
0468
0469 template<
0470   typename... Ts,typename Iterator,
0471   typename InputIterator,typename BinaryPredicate,
0472   enable_if_poly_collection_iterator<Iterator> =nullptr
0473 >
0474 bool equal(
0475   const Iterator& first1,const Iterator& last1,
0476   InputIterator first2,InputIterator last2,BinaryPredicate pred)
0477 {
0478   auto alg=restitute_range<Ts...>(equal_alg{},first2,last2,pred);
0479   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
0480   return first2==last2;
0481 }
0482
0483 template<
0484   typename... Ts,typename Iterator,typename InputIterator,
0485   enable_if_poly_collection_iterator<Iterator> =nullptr
0486 >
0487 bool equal(
0488   const Iterator& first1,const Iterator& last1,
0489   InputIterator first2,InputIterator last2)
0490 {
0491   return algorithm::equal<Ts...>(
0492     first1,last1,first2,last2,transparent_equal_to{});
0493 }
0494
0495 template<
0496   typename Iterator,
0497   enable_if_poly_collection_iterator<Iterator> =nullptr
0498 >
0499 std::ptrdiff_t fast_distance(const Iterator& first,const Iterator& last)
0500 {
0501   using traits=iterator_traits<Iterator>;
0502
0503   if(first==last)return 0;
0504
0505   auto sfirst=traits::base_segment_info_iterator_from(first),
0506        slast=traits::base_segment_info_iterator_from(last);
0507   if(sfirst==slast){
0508     return std::distance(
0509       traits::local_base_iterator_from(first),
0510       traits::local_base_iterator_from(last));
0511   }
0512   else{
0513     std::ptrdiff_t m=std::distance(
0514       traits::local_base_iterator_from(first),sfirst->end());
0515     while(++sfirst!=slast)m+=std::distance(sfirst->begin(),sfirst->end());
0516     if(slast!=traits::end_base_segment_info_iterator_from(last)){
0517       m+=std::distance(
0518         slast->begin(),traits::local_base_iterator_from(last));
0519     }
0520     return m;
0521   }
0522 }
0523
0524 template<
0525   typename... Ts,typename Iterator,
0526   typename ForwardIterator,typename BinaryPredicate,
0527   enable_if_poly_collection_iterator<Iterator> =nullptr
0528 >
0529 bool is_permutation_suffix(
0530   const Iterator& first1,const Iterator& last1,
0531   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0532 {
0533   using traits=iterator_traits<Iterator>;
0534
0535   auto send=traits::end_base_segment_info_iterator_from(last1);
0536   for(auto i:detail::segment_split(first1,last1)){
0537     for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){
0538       auto& info=i.type_info();
0539       auto p=head_closure(
0540         restitute_iterator<Ts...>(deref_1st_to(pred)),info,lbscan);
0541       auto scan=traits::iterator_from(lbscan,send);
0542       if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue;
0543       std::ptrdiff_t matches=std::count_if(first2,last2,p);
0544       if(matches==0||
0545          matches!=algorithm::count_if<Ts...>(scan,last1,p))return false;
0546     }
0547   }
0548   return true;
0549 }
0550
0551 template<
0552   typename... Ts,typename Iterator,
0553   typename ForwardIterator,typename BinaryPredicate,
0554   enable_if_poly_collection_iterator<Iterator> =nullptr
0555 >
0556 bool is_permutation(
0557   Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred)
0558 {
0559   std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred);
0560   auto last2=std::next(first2,algorithm::fast_distance(first1,last1));
0561   return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
0562 }
0563
0564 template<
0565   typename... Ts,typename Iterator,typename ForwardIterator,
0566   enable_if_poly_collection_iterator<Iterator> =nullptr
0567 >
0568 bool is_permutation(
0569   const Iterator& first1,const Iterator& last1,ForwardIterator first2)
0570 {
0571   return algorithm::is_permutation<Ts...>(
0572     first1,last1,first2,transparent_equal_to{});
0573 }
0574
0575 template<
0576   typename... Ts,typename Iterator,
0577   typename ForwardIterator,typename BinaryPredicate,
0578   enable_if_poly_collection_iterator<Iterator> =nullptr
0579 >
0580 bool is_permutation(
0581   Iterator first1,Iterator last1,
0582   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0583 {
0584   std::tie(first1,first2)=algorithm::mismatch<Ts...>(
0585     first1,last1,first2,last2,pred);
0586   if(algorithm::fast_distance(first1,last1)!=std::distance(first2,last2))
0587     return false;
0588   else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
0589 }
0590
0591 template<
0592   typename... Ts,typename Iterator,typename ForwardIterator,
0593   enable_if_poly_collection_iterator<Iterator> =nullptr
0594 >
0595 bool is_permutation(
0596   const Iterator& first1,const Iterator& last1,
0597   ForwardIterator first2,ForwardIterator last2)
0598 {
0599   return algorithm::is_permutation<Ts...>(
0600     first1,last1,first2,last2,transparent_equal_to{});
0601 }
0602
0603 template<
0604   typename... Ts,typename Iterator,
0605   typename ForwardIterator,typename BinaryPredicate,
0606   enable_if_poly_collection_iterator<Iterator> =nullptr
0607 >
0608 Iterator search(
0609   const Iterator& first1,const Iterator& last1,
0610   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0611 {
0612   using traits=iterator_traits<Iterator>;
0613
0614   auto send=traits::end_base_segment_info_iterator_from(last1);
0615   for(auto i:detail::segment_split(first1,last1)){
0616     for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){
0617       Iterator it=traits::iterator_from(lbit,send);
0618       if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2)
0619         return it;
0620     }
0621   }
0622   return last1;
0623 }
0624
0625 template<
0626   typename... Ts,typename Iterator,typename ForwardIterator,
0627   enable_if_poly_collection_iterator<Iterator> =nullptr
0628 >
0629 Iterator search(
0630   const Iterator& first1,const Iterator& last1,
0631   ForwardIterator first2,ForwardIterator last2)
0632 {
0633   return algorithm::search<Ts...>(
0634     first1,last1,first2,last2,transparent_equal_to{});
0635 }
0636
0637 template<
0638   typename... Ts,typename Iterator,
0639   typename ForwardIterator,typename BinaryPredicate,
0640   enable_if_poly_collection_iterator<Iterator> =nullptr
0641 >
0642 Iterator find_end(
0643   Iterator first1,Iterator last1,
0644   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0645 {
0646   if(first2==last2)return last1;
0647
0648   for(Iterator res=last1;;){
0649     Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred);
0650     if(res1==last1)return res;
0651     else{
0652       first1=res=res1;
0653       ++first1;
0654     }
0655   }
0656 }
0657
0658 template<
0659   typename... Ts,typename Iterator,typename ForwardIterator,
0660   enable_if_poly_collection_iterator<Iterator> =nullptr
0661 >
0662 Iterator find_end(
0663   const Iterator& first1,const Iterator& last1,
0664   ForwardIterator first2,ForwardIterator last2)
0665 {
0666   return algorithm::find_end<Ts...>(
0667     first1,last1,first2,last2,transparent_equal_to{});
0668 }
0669
0670 struct search_n_alg
0671 {
0672   template<
0673     typename ForwardIterator,typename Size,
0674     typename T,typename BinaryPredicate
0675   >
0676   ForwardIterator operator()(
0677     ForwardIterator first,ForwardIterator last,
0678     Size count,bool& carry,Size& remain,const T& x, /* note the &s */
0679     BinaryPredicate pred)const
0680   {
0681     for(;first!=last;++first){
0682       if(!pred(*first,x)){carry=false;remain=count;continue;}
0683       auto res=first;
0684       for(;;){
0685         if(--remain==0||++first==last)return res;
0686         if(!pred(*first,x)){carry=false;remain=count;break;}
0687       }
0688     }
0689     return last;
0690   }
0691 };
0692
0693 template<
0694   typename... Ts,typename Iterator,
0695   typename Size,typename T,typename BinaryPredicate,
0696   enable_if_poly_collection_iterator<Iterator> =nullptr
0697 >
0698 Iterator search_n(
0699   const Iterator& first,const Iterator& last,
0700   Size count,const T& x,BinaryPredicate pred)
0701 {
0702   using traits=iterator_traits<Iterator>;
0703   using local_base_iterator=typename traits::local_base_iterator;
0704
0705   if(count<=0)return first;
0706
0707   bool                carry=false;
0708   auto                remain=count;
0709   auto                alg=restitute_range<Ts...>(
0710                         cast_return<local_base_iterator>(search_n_alg{}),
0711                         count,carry,remain,x,pred);
0712   local_base_iterator prev;
0713   for(auto i:detail::segment_split(first,last)){
0714     auto it=alg(i);
0715     if(it!=i.end()){
0716       if(remain==0)
0717         return traits::iterator_from(
0718           carry?prev:it,
0719           traits::end_base_segment_info_iterator_from(last));
0720       else if(!carry){prev=it;carry=true;}
0721     }
0722   }
0723   return last;
0724 }
0725
0726 template<
0727   typename... Ts,typename Iterator,
0728   typename Size,typename T,
0729   enable_if_poly_collection_iterator<Iterator> =nullptr
0730 >
0731 Iterator search_n(
0732   const Iterator& first,const Iterator& last,Size count,const T& x)
0733 {
0734   return algorithm::search_n<Ts...>(
0735     first,last,count,x,transparent_equal_to{});
0736 }
0737
0738 template<
0739   typename Algorithm,typename... Ts,
0740   typename Iterator,typename OutputIterator,typename... Args,
0741   enable_if_poly_collection_iterator<Iterator> =nullptr
0742 >
0743 OutputIterator generic_copy(
0744   const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args)
0745 {
0746   for(auto i:detail::segment_split(first,last)){
0747     auto alg=restitute_range<Ts...>(
0748       Algorithm{},res,std::forward<Args>(args)...);
0749     res=alg(i);
0750   }
0751   return res;
0752 }
0753
0754 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy)
0755
0756 template<
0757   typename... Ts,typename Iterator,typename OutputIterator,
0758   enable_if_poly_collection_iterator<Iterator> =nullptr
0759 >
0760 OutputIterator copy(
0761   const Iterator& first,const Iterator& last,OutputIterator res)
0762 {
0763   return generic_copy<std_copy,Ts...>(first,last,res);
0764 }
0765
0766 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n)
0767
0768 template<
0769   typename... Ts,typename Iterator,typename Size,typename OutputIterator,
0770   enable_if_poly_collection_iterator<Iterator> =nullptr
0771 >
0772 OutputIterator copy_n(const Iterator& first,Size count,OutputIterator res)
0773 {
0774   using traits=iterator_traits<Iterator>;
0775
0776   if(count<=0)return res;
0777
0778   auto lbit=traits::local_base_iterator_from(first);
0779   auto sit=traits::base_segment_info_iterator_from(first);
0780   for(;;){
0781     auto n=(std::min)(count,sit->end()-lbit);
0782     auto alg=restitute_iterator<Ts...>(std_copy_n{},n,res);
0783     res=alg(sit->type_info(),lbit);
0784     if((count-=n)==0)break;
0785     ++sit;
0786     lbit=sit->begin();
0787   }
0788   return res;
0789 }
0790
0791 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if)
0792
0793 template<
0794   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
0795   enable_if_poly_collection_iterator<Iterator> =nullptr
0796 >
0797 OutputIterator copy_if(
0798   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
0799 {
0800   return generic_copy<std_copy_if,Ts...>(first,last,res,pred);
0801 }
0802
0803 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move)
0804
0805 template<
0806   typename... Ts,typename Iterator,typename OutputIterator,
0807   enable_if_poly_collection_iterator<Iterator> =nullptr
0808 >
0809 OutputIterator move(
0810   const Iterator& first,const Iterator& last,OutputIterator res)
0811 {
0812   return generic_copy<std_move,Ts...>(first,last,res);
0813 }
0814
0815 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform)
0816
0817 template<
0818   typename... Ts,typename Iterator,
0819   typename OutputIterator,typename UnaryOperation,
0820   enable_if_poly_collection_iterator<Iterator> =nullptr
0821 >
0822 OutputIterator transform(
0823   const Iterator& first,const Iterator& last,
0824   OutputIterator res,UnaryOperation op)
0825 {
0826   return generic_copy<std_transform,Ts...>(first,last,res,op);
0827 }
0828
0829 struct transform2_alg
0830 {
0831   template<
0832     typename InputIterator1,typename InputIterator2,
0833     typename OutputIterator,typename BinaryOperation
0834   >
0835   OutputIterator operator()(
0836     InputIterator1 first1,InputIterator1 last1,
0837     OutputIterator res, /* third place for compatibility with generic_copy */
0838     InputIterator2& first2, BinaryOperation op)const         /* note the & */
0839   {
0840     while(first1!=last1)*res++=op(*first1++,*first2++);
0841     return res;
0842   }
0843 };
0844
0845 template<
0846   typename... Ts,typename Iterator,typename InputIterator,
0847   typename OutputIterator,typename BinaryOperation,
0848   enable_if_poly_collection_iterator<Iterator> =nullptr
0849 >
0850 OutputIterator transform(
0851   const Iterator& first1,const Iterator& last1,InputIterator first2,
0852   OutputIterator res,BinaryOperation op)
0853 {
0854   return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op);
0855 }
0856
0857 struct replace_copy_alg
0858 {
0859   /* std::replace_copy broken in VS2015, internal ticket VSO#279818
0860    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
0861    * conditional operator".
0862    */
0863
0864   template<typename InputIterator,typename OutputIterator,typename T>
0865   OutputIterator operator()(
0866     InputIterator first,InputIterator last,OutputIterator res,
0867     const T& old_x,const T& new_x)
0868   {
0869     for(;first!=last;++first,++res){
0870       if(*first==old_x)*res=new_x;
0871       else             *res=*first;
0872     }
0873     return res;
0874   }
0875 };
0876
0877 template<
0878   typename... Ts,typename Iterator,typename OutputIterator,typename T,
0879   enable_if_poly_collection_iterator<Iterator> =nullptr
0880 >
0881 OutputIterator replace_copy(
0882   const Iterator& first,const Iterator& last,OutputIterator res,
0883   const T& old_x,const T& new_x)
0884 {
0885   return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x);
0886 }
0887
0888 struct replace_copy_if_alg
0889 {
0890   /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818
0891    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
0892    * conditional operator".
0893    */
0894
0895   template<
0896     typename InputIterator,typename OutputIterator,
0897     typename Predicate,typename T
0898   >
0899   OutputIterator operator()(
0900     InputIterator first,InputIterator last,OutputIterator res,
0901     Predicate pred,const T& new_x)
0902   {
0903     for(;first!=last;++first,++res){
0904       if(pred(*first))*res=new_x;
0905       else            *res=*first;
0906     }
0907     return res;
0908   }
0909 };
0910
0911 template<
0912   typename... Ts,typename Iterator,typename OutputIterator,
0913   typename Predicate,typename T,
0914   enable_if_poly_collection_iterator<Iterator> =nullptr
0915 >
0916 OutputIterator replace_copy_if(
0917   const Iterator& first,const Iterator& last,OutputIterator res,
0918   Predicate pred,const T& new_x)
0919 {
0920   return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x);
0921 }
0922
0923 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy)
0924
0925 template<
0926   typename... Ts,typename Iterator,typename OutputIterator,typename T,
0927   enable_if_poly_collection_iterator<Iterator> =nullptr
0928 >
0929 OutputIterator remove_copy(
0930   const Iterator& first,const Iterator& last,OutputIterator res,const T& x)
0931 {
0932   return generic_copy<std_remove_copy,Ts...>(first,last,res,x);
0933 }
0934
0935 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(
0936   std_remove_copy_if,std::remove_copy_if)
0937
0938 template<
0939   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
0940   enable_if_poly_collection_iterator<Iterator> =nullptr
0941 >
0942 OutputIterator remove_copy_if(
0943   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
0944 {
0945   return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred);
0946 }
0947
0948 template<typename... Ts>
0949 struct unique_copy_alg
0950 {
0951   template<
0952     typename LocalIterator,typename OutputIterator,
0953     typename BinaryPredicate,typename LocalBaseIterator
0954   >
0955   OutputIterator operator()(
0956     LocalIterator first,LocalIterator last,
0957     OutputIterator res, BinaryPredicate pred,
0958     bool& carry,const std::type_info* prev_info, /* note the &s */
0959     LocalBaseIterator& prev)const
0960   {
0961     if(carry){
0962       auto p=restitute_iterator<Ts...>(deref_to(pred));
0963       for(;first!=last;++first)if(!p(*prev_info,prev,first))break;
0964     }
0965     if(first==last)return res;
0966     res=std::unique_copy(first,last,res,pred);
0967     carry=true;
0968     prev_info=&typeid(
0969       typename std::iterator_traits<LocalIterator>::value_type);
0970     prev=LocalBaseIterator{last-1};
0971     return res;
0972   }
0973 };
0974
0975 template<
0976   typename... Ts,typename Iterator,
0977   typename OutputIterator,typename BinaryPredicate,
0978   enable_if_poly_collection_iterator<Iterator> =nullptr
0979 >
0980 OutputIterator unique_copy(
0981   const Iterator& first,const Iterator& last,
0982   OutputIterator res,BinaryPredicate pred)
0983 {
0984   using traits=iterator_traits<Iterator>;
0985   using local_base_iterator=typename traits::local_base_iterator;
0986
0987   bool                  carry=false;
0988   const std::type_info* prev_info{&typeid(void)};
0989   local_base_iterator   prev;
0990   return generic_copy<unique_copy_alg<Ts...>,Ts...>(
0991     first,last,res,pred,carry,prev_info,prev);
0992 }
0993
0994 template<
0995   typename... Ts,typename Iterator,typename OutputIterator,
0996   enable_if_poly_collection_iterator<Iterator> =nullptr
0997 >
0998 OutputIterator unique_copy(
0999   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