diff options
Diffstat (limited to 'boost/poly_collection/algorithm.hpp')
-rw-r--r-- | boost/poly_collection/algorithm.hpp | 1065 |
1 files changed, 1065 insertions, 0 deletions
diff --git a/boost/poly_collection/algorithm.hpp b/boost/poly_collection/algorithm.hpp new file mode 100644 index 0000000000..ed59bf4ded --- /dev/null +++ b/boost/poly_collection/algorithm.hpp @@ -0,0 +1,1065 @@ +/* Copyright 2016-2017 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/poly_collection for library home page. + */ + +#ifndef BOOST_POLY_COLLECTION_ALGORITHM_HPP +#define BOOST_POLY_COLLECTION_ALGORITHM_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <algorithm> +#include <boost/poly_collection/detail/auto_iterator.hpp> +#include <boost/poly_collection/detail/functional.hpp> +#include <boost/poly_collection/detail/iterator_traits.hpp> +#include <boost/poly_collection/detail/segment_split.hpp> +#include <boost/poly_collection/detail/type_restitution.hpp> +#include <iterator> +#include <type_traits> +#include <utility> + +/* Improved performance versions of std algorithms over poly_collection. + * poly_collection::alg is expected to be faster than the homonym std::alg + * because the latter does a traversal over a segmented structured, where + * incrementing requires checking for segment change, whereas the former + * for-loops over flat segments. + * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when + * passing elements to f, i.e. if the concrete type of the element is Ti + * then f is invoked with a [const] Ti&, which can dramatically improve + * performance when f has specific overloads for Ti (like, for instance, + * generic lambdas) as static optimization can kick in (devirtualization + * being a particular example). + */ + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +namespace algorithm{ + +template<typename Iterator> +using enable_if_poly_collection_iterator=typename std::enable_if< + !std::is_void<typename poly_collection_of<Iterator>::type>::value +>::type*; + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool all_of(const Iterator& first,const Iterator& last,Predicate pred) +{ + auto alg=restitute_range<Ts...>(std_all_of{},pred); + for(auto i:detail::segment_split(first,last))if(!alg(i))return false; + return true; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool any_of(const Iterator& first,const Iterator& last,Predicate pred) +{ + auto alg=restitute_range<Ts...>(std_any_of{},pred); + for(auto i:detail::segment_split(first,last))if(alg(i))return true; + return false; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool none_of(const Iterator& first,const Iterator& last,Predicate pred) +{ + auto alg=restitute_range<Ts...>(std_none_of{},pred); + for(auto i:detail::segment_split(first,last))if(!alg(i))return false; + return true; +} + +struct for_each_alg +{ + template<typename InputIterator,typename Function> + void operator()( + InputIterator first,InputIterator last,Function& f)const /* note the & */ + { + for(;first!=last;++first)f(*first); + } +}; + +template< + typename... Ts,typename Iterator,typename Function, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Function for_each(const Iterator& first,const Iterator& last,Function f) +{ + for_each_segment(first,last,restitute_range<Ts...>(for_each_alg{},f)); + return std::move(f); +} + +template< + typename Algorithm,typename... Ts, + typename Iterator,typename... Args, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator generic_find( + const Iterator& first,const Iterator& last,Args&&... args) +{ + using traits=iterator_traits<Iterator>; + using local_base_iterator=typename traits::local_base_iterator; + + auto alg=restitute_range<Ts...>( + cast_return<local_base_iterator>(Algorithm{}), + std::forward<Args>(args)...); + for(auto i:detail::segment_split(first,last)){ + auto it=alg(i); + if(it!=i.end()) + return traits::iterator_from( + it,traits::end_base_segment_info_iterator_from(last)); + } + return last; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find) + +template< + typename... Ts,typename Iterator,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find(const Iterator& first,const Iterator& last,const T& x) +{ + return generic_find<std_find,Ts...>(first,last,x); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_if(const Iterator& first,const Iterator& last,Predicate pred) +{ + return generic_find<std_find_if,Ts...>(first,last,pred); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_if_not(const Iterator& first,const Iterator& last,Predicate pred) +{ + return generic_find<std_find_if_not,Ts...>(first,last,pred); +} + +/* find_end defined after search below */ + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of) + +template< + typename... Ts,typename Iterator,typename ForwardIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_first_of( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2) +{ + return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2); +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_first_of( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) +{ + return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred); +} + +template<typename... Ts> +struct adjacent_find_alg +{ + template< + typename LocalIterator,typename BinaryPredicate,typename LocalBaseIterator + > + LocalBaseIterator operator()( + LocalIterator first,LocalIterator last,BinaryPredicate pred, + bool& carry,const std::type_info* prev_info, /* note the &s */ + LocalBaseIterator& prev)const + { + if(first==last)return LocalBaseIterator{last}; + if(carry){ + auto p=restitute_iterator<Ts...>(deref_to(pred)); + if(p(*prev_info,prev,first))return prev; + } + auto res=std::adjacent_find(first,last,pred); + if(res==last){ + carry=true; + prev_info=&typeid( + typename std::iterator_traits<LocalIterator>::value_type); + prev=LocalBaseIterator{last-1}; + } + else carry=false; + return LocalBaseIterator{res}; + } +}; + +template< + typename... Ts,typename Iterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator adjacent_find( + const Iterator& first,const Iterator& last,BinaryPredicate pred) +{ + using traits=iterator_traits<Iterator>; + using local_base_iterator=typename traits::local_base_iterator; + + bool carry=false; + const std::type_info* prev_info{&typeid(void)}; + local_base_iterator prev; + return generic_find<adjacent_find_alg<Ts...>,Ts...>( + first,last,pred,carry,prev_info,prev); +} + +template< + typename... Ts,typename Iterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator adjacent_find(const Iterator& first,const Iterator& last) +{ + return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{}); +} + +template< + typename Algorithm,typename... Ts, + typename Iterator,typename... Args, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::ptrdiff_t generic_count( + const Iterator& first,const Iterator& last,Args&&... args) +{ + auto alg=restitute_range<Ts...>(Algorithm{},std::forward<Args>(args)...); + std::ptrdiff_t res=0; + for(auto i:detail::segment_split(first,last))res+=alg(i); + return res; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count) + +template< + typename... Ts,typename Iterator,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::ptrdiff_t count(const Iterator& first,const Iterator& last,const T& x) +{ + return generic_count<std_count,Ts...>(first,last,x); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if) + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::ptrdiff_t count_if( + const Iterator& first,const Iterator& last,Predicate pred) +{ + return generic_count<std_count_if,Ts...>(first,last,pred); +} + +struct mismatch_alg +{ + template< + typename InputIterator1, + typename InputIterator2,typename BinaryPredicate + > + InputIterator1 operator()( + InputIterator1 first1,InputIterator1 last1, + InputIterator2& first2,BinaryPredicate pred)const /* note the & */ + { + while(first1!=last1&&pred(*first1,*first2)){ + ++first1; + ++first2; + } + return first1; + } + + template< + typename InputIterator1, + typename InputIterator2,typename BinaryPredicate + > + InputIterator1 operator()( + InputIterator1 first1,InputIterator1 last1, + InputIterator2& first2,InputIterator2 last2, /* note the & */ + BinaryPredicate pred)const + { + while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){ + ++first1; + ++first2; + } + return first1; + } +}; + +template< + typename... Ts,typename Iterator, + typename InputIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::pair<Iterator,InputIterator> mismatch( + const Iterator& first1,const Iterator& last1, + InputIterator first2,BinaryPredicate pred) +{ + auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred); + return {it,first2}; +} + +template< + typename... Ts,typename Iterator,typename InputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::pair<Iterator,InputIterator> mismatch( + const Iterator& first1,const Iterator& last1,InputIterator first2) +{ + return algorithm::mismatch<Ts...>( + first1,last1,first2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename InputIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::pair<Iterator,InputIterator> mismatch( + const Iterator& first1,const Iterator& last1, + InputIterator first2,InputIterator last2,BinaryPredicate pred) +{ + auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred); + return {it,first2}; +} + +template< + typename... Ts,typename Iterator,typename InputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::pair<Iterator,InputIterator> mismatch( + const Iterator& first1,const Iterator& last1, + InputIterator first2,InputIterator last2) +{ + return algorithm::mismatch<Ts...>( + first1,last1,first2,last2,transparent_equal_to{}); +} + +struct equal_alg +{ + template< + typename InputIterator1, + typename InputIterator2,typename BinaryPredicate + > + bool operator()( + InputIterator1 first1,InputIterator1 last1, + InputIterator2& first2,BinaryPredicate pred)const /* note the & */ + { + for(;first1!=last1;++first1,++first2){ + if(!pred(*first1,*first2))return false; + } + return true; + } + + template< + typename InputIterator1, + typename InputIterator2,typename BinaryPredicate + > + bool operator()( + InputIterator1 first1,InputIterator1 last1, + InputIterator2& first2,InputIterator2 last2, /* note the & */ + BinaryPredicate pred)const + { + for(;first1!=last1&&first2!=last2;++first1,++first2){ + if(!pred(*first1,*first2))return false; + } + return first1==last1; /* don't check first2==last2 as op is partial */ + } +}; + +template< + typename... Ts,typename Iterator, + typename InputIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool equal( + const Iterator& first1,const Iterator& last1, + InputIterator first2,BinaryPredicate pred) +{ + auto alg=restitute_range<Ts...>(equal_alg{},first2,pred); + for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; + return true; +} + +template< + typename... Ts,typename Iterator,typename InputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool equal( + const Iterator& first1,const Iterator& last1,InputIterator first2) +{ + return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename InputIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool equal( + const Iterator& first1,const Iterator& last1, + InputIterator first2,InputIterator last2,BinaryPredicate pred) +{ + auto alg=restitute_range<Ts...>(equal_alg{},first2,last2,pred); + for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false; + return first2==last2; +} + +template< + typename... Ts,typename Iterator,typename InputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool equal( + const Iterator& first1,const Iterator& last1, + InputIterator first2,InputIterator last2) +{ + return algorithm::equal<Ts...>( + first1,last1,first2,last2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_permutation_suffix( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) +{ + using traits=iterator_traits<Iterator>; + + auto send=traits::end_base_segment_info_iterator_from(last1); + for(auto i:detail::segment_split(first1,last1)){ + for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){ + auto& info=i.type_info(); + auto p=head_closure( + restitute_iterator<Ts...>(deref_1st_to(pred)),info,lbscan); + auto scan=traits::iterator_from(lbscan,send); + if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue; + std::ptrdiff_t matches=std::count_if(first2,last2,p); + if(matches==0|| + matches!=algorithm::count_if<Ts...>(scan,last1,p))return false; + } + } + return true; +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_permutation( + Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred) +{ + std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred); + auto last2=std::next(first2,std::distance(first1,last1)); + return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); +} + +template< + typename... Ts,typename Iterator,typename ForwardIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_permutation( + const Iterator& first1,const Iterator& last1,ForwardIterator first2) +{ + return algorithm::is_permutation<Ts...>( + first1,last1,first2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_permutation( + Iterator first1,Iterator last1, + ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) +{ + std::tie(first1,first2)=algorithm::mismatch<Ts...>( + first1,last1,first2,last2,pred); + if(std::distance(first1,last1)!=std::distance(first2,last2))return false; + else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred); +} + +template< + typename... Ts,typename Iterator,typename ForwardIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_permutation( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2) +{ + return algorithm::is_permutation<Ts...>( + first1,last1,first2,last2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator search( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) +{ + using traits=iterator_traits<Iterator>; + + auto send=traits::end_base_segment_info_iterator_from(last1); + for(auto i:detail::segment_split(first1,last1)){ + for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){ + Iterator it=traits::iterator_from(lbit,send); + if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2) + return it; + } + } + return last1; +} + +template< + typename... Ts,typename Iterator,typename ForwardIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator search( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2) +{ + return algorithm::search<Ts...>( + first1,last1,first2,last2,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator, + typename ForwardIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_end( + Iterator first1,Iterator last1, + ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred) +{ + if(first2==last2)return last1; + + for(Iterator res=last1;;){ + Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred); + if(res1==last1)return res; + else{ + first1=res=res1; + ++first1; + } + } +} + +template< + typename... Ts,typename Iterator,typename ForwardIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator find_end( + const Iterator& first1,const Iterator& last1, + ForwardIterator first2,ForwardIterator last2) +{ + return algorithm::find_end<Ts...>( + first1,last1,first2,last2,transparent_equal_to{}); +} + +struct search_n_alg +{ + template< + typename ForwardIterator,typename Size, + typename T,typename BinaryPredicate + > + ForwardIterator operator()( + ForwardIterator first,ForwardIterator last, + Size count,bool& carry,Size& remain,const T& x, /* note the &s */ + BinaryPredicate pred)const + { + for(;first!=last;++first){ + if(!pred(*first,x)){carry=false;remain=count;continue;} + auto res=first; + for(;;){ + if(--remain==0||++first==last)return res; + if(!pred(*first,x)){carry=false;remain=count;break;} + } + } + return last; + } +}; + +template< + typename... Ts,typename Iterator, + typename Size,typename T,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator search_n( + const Iterator& first,const Iterator& last, + Size count,const T& x,BinaryPredicate pred) +{ + using traits=iterator_traits<Iterator>; + using local_base_iterator=typename traits::local_base_iterator; + + if(count<=0)return first; + + bool carry=false; + auto remain=count; + auto alg=restitute_range<Ts...>( + cast_return<local_base_iterator>(search_n_alg{}), + count,carry,remain,x,pred); + local_base_iterator prev; + for(auto i:detail::segment_split(first,last)){ + auto it=alg(i); + if(it!=i.end()){ + if(remain==0) + return traits::iterator_from( + carry?prev:it, + traits::end_base_segment_info_iterator_from(last)); + else if(!carry){prev=it;carry=true;} + } + } + return last; +} + +template< + typename... Ts,typename Iterator, + typename Size,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator search_n( + const Iterator& first,const Iterator& last,Size count,const T& x) +{ + return algorithm::search_n<Ts...>( + first,last,count,x,transparent_equal_to{}); +} + +template< + typename Algorithm,typename... Ts, + typename Iterator,typename OutputIterator,typename... Args, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator generic_copy( + const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args) +{ + for(auto i:detail::segment_split(first,last)){ + auto alg=restitute_range<Ts...>( + Algorithm{},res,std::forward<Args>(args)...); + res=alg(i); + } + return res; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy) + +template< + typename... Ts,typename Iterator,typename OutputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator copy( + const Iterator& first,const Iterator& last,OutputIterator res) +{ + return generic_copy<std_copy,Ts...>(first,last,res); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n) + +template< + typename... Ts,typename Iterator,typename Size,typename OutputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator copy_n(const Iterator& first,Size count,OutputIterator res) +{ + using traits=iterator_traits<Iterator>; + + if(count<=0)return res; + + auto lbit=traits::local_base_iterator_from(first); + auto sit=traits::base_segment_info_iterator_from(first); + for(;;){ + auto n=(std::min)(count,sit->end()-lbit); + auto alg=restitute_iterator<Ts...>(std_copy_n{},n,res); + res=alg(sit->type_info(),lbit); + if((count-=n)==0)break; + ++sit; + lbit=sit->begin(); + } + return res; +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if) + +template< + typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator copy_if( + const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) +{ + return generic_copy<std_copy_if,Ts...>(first,last,res,pred); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move) + +template< + typename... Ts,typename Iterator,typename OutputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator move( + const Iterator& first,const Iterator& last,OutputIterator res) +{ + return generic_copy<std_move,Ts...>(first,last,res); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform) + +template< + typename... Ts,typename Iterator, + typename OutputIterator,typename UnaryOperation, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator transform( + const Iterator& first,const Iterator& last, + OutputIterator res,UnaryOperation op) +{ + return generic_copy<std_transform,Ts...>(first,last,res,op); +} + +struct transform2_alg +{ + template< + typename InputIterator1,typename InputIterator2, + typename OutputIterator,typename BinaryOperation + > + OutputIterator operator()( + InputIterator1 first1,InputIterator1 last1, + OutputIterator res, /* third place for compatibility with generic_copy */ + InputIterator2& first2, BinaryOperation op)const /* note the & */ + { + while(first1!=last1)*res++=op(*first1++,*first2++); + return res; + } +}; + +template< + typename... Ts,typename Iterator,typename InputIterator, + typename OutputIterator,typename BinaryOperation, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator transform( + const Iterator& first1,const Iterator& last1,InputIterator first2, + OutputIterator res,BinaryOperation op) +{ + return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op); +} + +struct replace_copy_alg +{ + /* std::replace_copy broken in VS2015, internal ticket VSO#279818 + * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the + * conditional operator". + */ + + template<typename InputIterator,typename OutputIterator,typename T> + OutputIterator operator()( + InputIterator first,InputIterator last,OutputIterator res, + const T& old_x,const T& new_x) + { + for(;first!=last;++first,++res){ + if(*first==old_x)*res=new_x; + else *res=*first; + } + return res; + } +}; + +template< + typename... Ts,typename Iterator,typename OutputIterator,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator replace_copy( + const Iterator& first,const Iterator& last,OutputIterator res, + const T& old_x,const T& new_x) +{ + return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x); +} + +struct replace_copy_if_alg +{ + /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818 + * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the + * conditional operator". + */ + + template< + typename InputIterator,typename OutputIterator, + typename Predicate,typename T + > + OutputIterator operator()( + InputIterator first,InputIterator last,OutputIterator res, + Predicate pred,const T& new_x) + { + for(;first!=last;++first,++res){ + if(pred(*first))*res=new_x; + else *res=*first; + } + return res; + } +}; + +template< + typename... Ts,typename Iterator,typename OutputIterator, + typename Predicate,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator replace_copy_if( + const Iterator& first,const Iterator& last,OutputIterator res, + Predicate pred,const T& new_x) +{ + return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy) + +template< + typename... Ts,typename Iterator,typename OutputIterator,typename T, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator remove_copy( + const Iterator& first,const Iterator& last,OutputIterator res,const T& x) +{ + return generic_copy<std_remove_copy,Ts...>(first,last,res,x); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( + std_remove_copy_if,std::remove_copy_if) + +template< + typename... Ts,typename Iterator,typename OutputIterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator remove_copy_if( + const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred) +{ + return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred); +} + +template<typename... Ts> +struct unique_copy_alg +{ + template< + typename LocalIterator,typename OutputIterator, + typename BinaryPredicate,typename LocalBaseIterator + > + OutputIterator operator()( + LocalIterator first,LocalIterator last, + OutputIterator res, BinaryPredicate pred, + bool& carry,const std::type_info* prev_info, /* note the &s */ + LocalBaseIterator& prev)const + { + if(carry){ + auto p=restitute_iterator<Ts...>(deref_to(pred)); + for(;first!=last;++first)if(!p(*prev_info,prev,first))break; + } + if(first==last)return res; + res=std::unique_copy(first,last,res,pred); + carry=true; + prev_info=&typeid( + typename std::iterator_traits<LocalIterator>::value_type); + prev=LocalBaseIterator{last-1}; + return res; + } +}; + +template< + typename... Ts,typename Iterator, + typename OutputIterator,typename BinaryPredicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator unique_copy( + const Iterator& first,const Iterator& last, + OutputIterator res,BinaryPredicate pred) +{ + using traits=iterator_traits<Iterator>; + using local_base_iterator=typename traits::local_base_iterator; + + bool carry=false; + const std::type_info* prev_info{&typeid(void)}; + local_base_iterator prev; + return generic_copy<unique_copy_alg<Ts...>,Ts...>( + first,last,res,pred,carry,prev_info,prev); +} + +template< + typename... Ts,typename Iterator,typename OutputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator unique_copy( + const Iterator& first,const Iterator& last,OutputIterator res) +{ + return algorithm::unique_copy<Ts...>(first,last,res,transparent_equal_to{}); +} + +template< + typename... Ts,typename Iterator,typename OutputIterator, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +OutputIterator rotate_copy( + const Iterator& first,const Iterator& middle,const Iterator& last, + OutputIterator res) +{ + res=algorithm::copy<Ts...>(middle,last,res); + return algorithm::copy<Ts...>(first,middle,res); +} + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +bool is_partitioned(const Iterator& first,const Iterator& last,Predicate pred) +{ + auto it=algorithm::find_if_not<Ts...>(first,last,pred); + if(it==last)return true; + return algorithm::none_of<Ts...>(++it,last,pred); +} + +BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET( + std_partition_copy,std::partition_copy) + +template< + typename... Ts,typename Iterator, + typename OutputIterator1,typename OutputIterator2,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +std::pair<OutputIterator1,OutputIterator2> partition_copy( + const Iterator& first,const Iterator& last, + OutputIterator1 rest,OutputIterator2 resf,Predicate pred) +{ + for(auto i:detail::segment_split(first,last)){ + auto alg=restitute_range<Ts...>(std_partition_copy{},rest,resf,pred); + std::tie(rest,resf)=alg(i); + } + return {rest,resf}; +} + +template<typename Predicate,typename... Ts> +struct partition_point_pred +{ + template<typename Iterator> + bool operator()(const Iterator& it)const + { + using traits=iterator_traits<Iterator>; + auto p=restitute_iterator<Ts...>(deref_to(pred)); + return p( + traits::base_segment_info_iterator_from(it)->type_info(), + traits::local_base_iterator_from(it)); + } + + Predicate pred; +}; + +template< + typename... Ts,typename Iterator,typename Predicate, + enable_if_poly_collection_iterator<Iterator> =nullptr +> +Iterator partition_point( + const Iterator& first,const Iterator& last,Predicate pred) +{ + auto_iterator<Iterator> afirst{first},alast{last}; + partition_point_pred<Predicate,Ts...> p{pred}; + return *std::partition_point(afirst,alast,p); +} + +} /* namespace poly_collection::detail::algorithm */ + +} /* namespace poly_collection::detail */ + +/* non-modifying sequence operations */ + +using detail::algorithm::all_of; +using detail::algorithm::any_of; +using detail::algorithm::none_of; +using detail::algorithm::for_each; +using detail::algorithm::find; +using detail::algorithm::find_if; +using detail::algorithm::find_if_not; +using detail::algorithm::find_end; +using detail::algorithm::find_first_of; +using detail::algorithm::adjacent_find; +using detail::algorithm::count; +using detail::algorithm::count_if; +using detail::algorithm::mismatch; +using detail::algorithm::equal; +using detail::algorithm::is_permutation; +using detail::algorithm::search; +using detail::algorithm::search_n; + +/* modifying sequence operations */ + +using detail::algorithm::copy; +using detail::algorithm::copy_n; +using detail::algorithm::copy_if; + /* copy_backwards requires BidirectionalIterator */ +using detail::algorithm::move; + /* move_backwards requires BidirectionalIterator */ + /* swap_ranges requires Swappable */ + /* iter_swap requires Swappable */ +using detail::algorithm::transform; + /* replace requires Assignable */ + /* replace_if requires Assignable */ +using detail::algorithm::replace_copy; +using detail::algorithm::replace_copy_if; + /* fill requires Assignable */ + /* fill_n requires Assignable */ + /* generate requires Assignable */ + /* generate_n requires Assignable */ + /* remove requires MoveAssignable */ + /* remove_if requires MoveAssignable */ +using detail::algorithm::remove_copy; +using detail::algorithm::remove_copy_if; + /* unique requires MoveAssignable */ +using detail::algorithm::unique_copy; + /* reverse requires BidirectionalIterator */ + /* reverse_copy requires BidirectionalIterator */ + /* rotate requires MoveAssignable */ +using detail::algorithm::rotate_copy; + /* shuffle requires RandomAccessIterator */ +using detail::algorithm::is_partitioned; + /* partition requires Swappable */ + /* stable_partition requires Swappable */ +using detail::algorithm::partition_copy; +using detail::algorithm::partition_point; + +/* sorting and related operations not provided */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif |