diff options
Diffstat (limited to 'boost/poly_collection')
37 files changed, 6859 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 diff --git a/boost/poly_collection/any_collection.hpp b/boost/poly_collection/any_collection.hpp new file mode 100644 index 0000000000..8f9f3739af --- /dev/null +++ b/boost/poly_collection/any_collection.hpp @@ -0,0 +1,80 @@ +/* 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_ANY_COLLECTION_HPP +#define BOOST_POLY_COLLECTION_ANY_COLLECTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/any_collection_fwd.hpp> +#include <boost/poly_collection/detail/any_model.hpp> +#include <boost/poly_collection/detail/poly_collection.hpp> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +template<typename Concept,typename Allocator> +class any_collection: + public detail::poly_collection_impl::poly_collection< + detail::any_model<Concept>,Allocator + > +{ + using base_type=detail::poly_collection_impl::poly_collection< + detail::any_model<Concept>,Allocator>; + + base_type& base()noexcept{return *this;} + const base_type& base()const noexcept{return *this;} + +public: + using base_type::base_type; + + any_collection()=default; + any_collection(const any_collection& x)=default; + any_collection(any_collection&& x)=default; + any_collection& operator=(const any_collection& x)=default; + any_collection& operator=(any_collection&& x)=default; + + template<typename C,typename A> + friend bool operator==( + const any_collection<C,A>&,const any_collection<C,A>&); +}; + +template<typename Concept,typename Allocator> +bool operator==( + const any_collection<Concept,Allocator>& x, + const any_collection<Concept,Allocator>& y) +{ + return x.base()==y.base(); +} + +template<typename Concept,typename Allocator> +bool operator!=( + const any_collection<Concept,Allocator>& x, + const any_collection<Concept,Allocator>& y) +{ + return !(x==y); +} + +template<typename Concept,typename Allocator> +void swap( + any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace */ + +using poly_collection::any_collection; + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/any_collection_fwd.hpp b/boost/poly_collection/any_collection_fwd.hpp new file mode 100644 index 0000000000..e457035432 --- /dev/null +++ b/boost/poly_collection/any_collection_fwd.hpp @@ -0,0 +1,56 @@ +/* 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_ANY_COLLECTION_FWD_HPP +#define BOOST_POLY_COLLECTION_ANY_COLLECTION_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <memory> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ +template<typename Concept> struct any_model; +} + +template<typename Concept> +using any_collection_value_type= + typename detail::any_model<Concept>::value_type; + +template< + typename Concept, + typename Allocator=std::allocator<any_collection_value_type<Concept>> +> +class any_collection; + +template<typename Concept,typename Allocator> +bool operator==( + const any_collection<Concept,Allocator>& x, + const any_collection<Concept,Allocator>& y); + +template<typename Concept,typename Allocator> +bool operator!=( + const any_collection<Concept,Allocator>& x, + const any_collection<Concept,Allocator>& y); + +template<typename Concept,typename Allocator> +void swap( + any_collection<Concept,Allocator>& x,any_collection<Concept,Allocator>& y); + +} /* namespace poly_collection */ + +using poly_collection::any_collection; + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/base_collection.hpp b/boost/poly_collection/base_collection.hpp new file mode 100644 index 0000000000..e904f9f020 --- /dev/null +++ b/boost/poly_collection/base_collection.hpp @@ -0,0 +1,79 @@ +/* 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_BASE_COLLECTION_HPP +#define BOOST_POLY_COLLECTION_BASE_COLLECTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/base_collection_fwd.hpp> +#include <boost/poly_collection/detail/base_model.hpp> +#include <boost/poly_collection/detail/poly_collection.hpp> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +template<typename Base,typename Allocator> +class base_collection: + public detail::poly_collection_impl::poly_collection< + detail::base_model<Base>,Allocator> +{ + using base_type=detail::poly_collection_impl::poly_collection< + detail::base_model<Base>,Allocator>; + + base_type& base()noexcept{return *this;} + const base_type& base()const noexcept{return *this;} + +public: + using base_type::base_type; + + base_collection()=default; + base_collection(const base_collection& x)=default; + base_collection(base_collection&& x)=default; + base_collection& operator=(const base_collection& x)=default; + base_collection& operator=(base_collection&& x)=default; + + template<typename B,typename A> + friend bool operator==( + const base_collection<B,A>&,const base_collection<B,A>&); +}; + +template<typename Base,typename Allocator> +bool operator==( + const base_collection<Base,Allocator>& x, + const base_collection<Base,Allocator>& y) +{ + return x.base()==y.base(); +} + +template<typename Base,typename Allocator> +bool operator!=( + const base_collection<Base,Allocator>& x, + const base_collection<Base,Allocator>& y) +{ + return !(x==y); +} + +template<typename Base,typename Allocator> +void swap( + base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace */ + +using poly_collection::base_collection; + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/base_collection_fwd.hpp b/boost/poly_collection/base_collection_fwd.hpp new file mode 100644 index 0000000000..ef4efab1dc --- /dev/null +++ b/boost/poly_collection/base_collection_fwd.hpp @@ -0,0 +1,45 @@ +/* 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_BASE_COLLECTION_FWD_HPP +#define BOOST_POLY_COLLECTION_BASE_COLLECTION_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <memory> + +namespace boost{ + +namespace poly_collection{ + +template<typename Base,typename Allocator=std::allocator<Base>> +class base_collection; + +template<typename Base,typename Allocator> +bool operator==( + const base_collection<Base,Allocator>& x, + const base_collection<Base,Allocator>& y); + +template<typename Base,typename Allocator> +bool operator!=( + const base_collection<Base,Allocator>& x, + const base_collection<Base,Allocator>& y); + +template<typename Base,typename Allocator> +void swap( + base_collection<Base,Allocator>& x,base_collection<Base,Allocator>& y); + +} /* namespace poly_collection */ + +using poly_collection::base_collection; + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/any_iterator.hpp b/boost/poly_collection/detail/any_iterator.hpp new file mode 100644 index 0000000000..a51ae86b61 --- /dev/null +++ b/boost/poly_collection/detail/any_iterator.hpp @@ -0,0 +1,92 @@ +/* Copyright 2016 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_DETAIL_ANY_ITERATOR_HPP +#define BOOST_POLY_COLLECTION_DETAIL_ANY_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_adaptor.hpp> +#include <boost/type_erasure/any_cast.hpp> +#include <type_traits> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* type_erasure::any<Concept>* adaptor convertible to pointer to wrapped + * entity. + */ + +template<typename Any> +class any_iterator:public boost::iterator_adaptor<any_iterator<Any>,Any*> +{ +public: + any_iterator()=default; + explicit any_iterator(Any* p)noexcept:any_iterator::iterator_adaptor_{p}{} + any_iterator(const any_iterator&)=default; + any_iterator& operator=(const any_iterator&)=default; + + template< + typename NonConstAny, + typename std::enable_if< + std::is_same<Any,const NonConstAny>::value>::type* =nullptr + > + any_iterator(const any_iterator<NonConstAny>& x)noexcept: + any_iterator::iterator_adaptor_{x.base()}{} + + template< + typename NonConstAny, + typename std::enable_if< + std::is_same<Any,const NonConstAny>::value>::type* =nullptr + > + any_iterator& operator=(const any_iterator<NonConstAny>& x)noexcept + { + this->base_reference()=x.base(); + return *this; + } + + /* interoperability with Any* */ + + any_iterator& operator=(Any* p)noexcept + {this->base_reference()=p;return *this;} + operator Any*()const noexcept{return this->base();} + + /* interoperability with Concrete* */ + + template< + typename Concrete, + typename std::enable_if< + /* can't compile-time check concept compliance */ + !std::is_const<Any>::value||std::is_const<Concrete>::value + >::type* =nullptr + > + explicit operator Concrete*()const noexcept + { + return const_cast<Concrete*>( + static_cast<typename std::remove_const<Concrete>::type*>( + type_erasure::any_cast<void*>(this->base()))); + } + +private: + template<typename> + friend class any_iterator; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/any_model.hpp b/boost/poly_collection/detail/any_model.hpp new file mode 100644 index 0000000000..d38bf0e4a3 --- /dev/null +++ b/boost/poly_collection/detail/any_model.hpp @@ -0,0 +1,214 @@ +/* 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_DETAIL_ANY_MODEL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_ANY_MODEL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/core/addressof.hpp> +#include <boost/mpl/map/map10.hpp> +#include <boost/mpl/pair.hpp> +#include <boost/mpl/vector/vector10.hpp> +#include <boost/poly_collection/detail/any_iterator.hpp> +#include <boost/poly_collection/detail/is_acceptable.hpp> +#include <boost/poly_collection/detail/segment_backend.hpp> +#include <boost/poly_collection/detail/split_segment.hpp> +#include <boost/type_erasure/any.hpp> +#include <boost/type_erasure/any_cast.hpp> +#include <boost/type_erasure/binding.hpp> +#include <boost/type_erasure/builtin.hpp> +#include <boost/type_erasure/concept_of.hpp> +#include <boost/type_erasure/is_subconcept.hpp> +#include <boost/type_erasure/relaxed.hpp> +#include <boost/type_erasure/static_binding.hpp> +#include <boost/type_erasure/typeid_of.hpp> +#include <memory> +#include <type_traits> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* model for any_collection */ + +template<typename Concept> +struct any_model; + +/* Refine is_acceptable to cover type_erasure::any classes whose assignment + * operator won't compile. + */ + +template<typename Concept,typename Concept2,typename T> +struct is_acceptable< + type_erasure::any<Concept2,T>,any_model<Concept>, + typename std::enable_if< + !type_erasure::is_relaxed<Concept2>::value&& + !type_erasure::is_subconcept<type_erasure::assignable<>,Concept2>::value&& + !type_erasure::is_subconcept< + type_erasure::assignable<type_erasure::_self,type_erasure::_self&&>, + Concept2>::value + >::type +>:std::false_type{}; + +/* is_terminal defined out-class to allow for partial specialization */ + +template<typename Concept,typename T> +using any_model_enable_if_has_typeid_=typename std::enable_if< + type_erasure::is_subconcept< + type_erasure::typeid_<typename std::decay<T>::type>, + Concept + >::value +>::type*; + +template<typename T,typename=void*> +struct any_model_is_terminal:std::true_type{}; + +template<typename Concept,typename T> +struct any_model_is_terminal< + type_erasure::any<Concept,T>,any_model_enable_if_has_typeid_<Concept,T> +>:std::false_type{}; + +/* used for make_value_type */ + +template<typename T,typename Q> +struct any_model_make_reference +{ + static T& apply(Q& x){return x;} +}; + +template<typename Concept> +struct any_model +{ + using value_type=type_erasure::any< + typename std::conditional< + type_erasure::is_subconcept<type_erasure::typeid_<>,Concept>::value, + Concept, + mpl::vector2<Concept,type_erasure::typeid_<>> + >::type, + type_erasure::_self& + >; + + template<typename Concrete> + using is_subtype=std::true_type; /* can't compile-time check concept + * compliance */ + template<typename T> + using is_terminal=any_model_is_terminal<T>; + + template<typename T> + static const std::type_info& subtypeid(const T&){return typeid(T);} + + template< + typename Concept2,typename T, + any_model_enable_if_has_typeid_<Concept2,T> =nullptr + > + static const std::type_info& subtypeid( + const type_erasure::any<Concept2,T>& a) + { + return type_erasure::typeid_of(a); + } + + template<typename T> + static void* subaddress(T& x){return boost::addressof(x);} + + template<typename T> + static const void* subaddress(const T& x){return boost::addressof(x);} + + template< + typename Concept2,typename T, + any_model_enable_if_has_typeid_<Concept2,T> =nullptr + > + static void* subaddress(type_erasure::any<Concept2,T>& a) + { + return type_erasure::any_cast<void*>(&a); + } + + template< + typename Concept2,typename T, + any_model_enable_if_has_typeid_<Concept2,T> =nullptr + > + static const void* subaddress(const type_erasure::any<Concept2,T>& a) + { + return type_erasure::any_cast<const void*>(&a); + } + + using base_iterator=any_iterator<value_type>; + using const_base_iterator=any_iterator<const value_type>; + using base_sentinel=value_type*; + using const_base_sentinel=const value_type*; + template<typename Concrete> + using iterator=Concrete*; + template<typename Concrete> + using const_iterator=const Concrete*; + using segment_backend=detail::segment_backend<any_model>; + template<typename Concrete,typename Allocator> + using segment_backend_implementation=split_segment< + any_model, + Concrete, + typename std::allocator_traits<Allocator>:: + template rebind_alloc<Concrete> + >; + using segment_backend_unique_ptr= + typename segment_backend::segment_backend_unique_ptr; + + static base_iterator nonconst_iterator(const_base_iterator it) + { + return base_iterator{ + const_cast<value_type*>(static_cast<const value_type*>(it))}; + } + + template<typename T> + static iterator<T> nonconst_iterator(const_iterator<T> it) + { + return const_cast<iterator<T>>(it); + } + + template<typename Concrete,typename Allocator> + static segment_backend_unique_ptr make(const Allocator& al) + { + return segment_backend_implementation<Concrete,Allocator>::new_(al,al); + } + +private: + template<typename,typename,typename> + friend class split_segment; + + template<typename Concrete> + static value_type make_value_type(Concrete& x){return value_type{x};} + + template<typename Concept2,typename T> + static value_type make_value_type(type_erasure::any<Concept2,T>& x) + { + /* I don't pretend to understand what's going on here, see + * https://lists.boost.org/boost-users/2017/05/87556.php + */ + + using namespace boost::type_erasure; + using ref_type=any<Concept2,T>; + using make_ref=any_model_make_reference<_self,ref_type>; + using concept_=typename concept_of<value_type>::type; + + auto b=make_binding<mpl::map1<mpl::pair<_self,ref_type>>>(); + + return {call(binding<make_ref>{b},make_ref{},x),binding<concept_>{b}}; + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/auto_iterator.hpp b/boost/poly_collection/detail/auto_iterator.hpp new file mode 100644 index 0000000000..397329b91b --- /dev/null +++ b/boost/poly_collection/detail/auto_iterator.hpp @@ -0,0 +1,56 @@ +/* Copyright 2016 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_DETAIL_AUTO_ITERATOR_HPP +#define BOOST_POLY_COLLECTION_DETAIL_AUTO_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_adaptor.hpp> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* auto_iterator<Iterator> (for want of a better name) behaves like Iterator + * save for the fact that it derefs to Iterator& rather than + * Iterator::reference. This is useful to "lift" std algorithms so that + * user-defined predicates are passed iterators that can then be dereferenced + * internally. + */ + +template<typename Iterator> +class auto_iterator: + public boost::iterator_adaptor<auto_iterator<Iterator>,Iterator,Iterator> +{ +public: + auto_iterator()=default; + auto_iterator(const Iterator& it):auto_iterator::iterator_adaptor_{it}{} + auto_iterator(const auto_iterator&)=default; + auto_iterator& operator=(const auto_iterator&)=default; + +private: + friend class boost::iterator_core_access; + + Iterator& dereference()const noexcept + { + return const_cast<auto_iterator*>(this)->base_reference(); + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/base_model.hpp b/boost/poly_collection/detail/base_model.hpp new file mode 100644 index 0000000000..db6126d2e3 --- /dev/null +++ b/boost/poly_collection/detail/base_model.hpp @@ -0,0 +1,130 @@ +/* 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_DETAIL_BASE_MODEL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_BASE_MODEL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/core/addressof.hpp> +#include <boost/poly_collection/detail/is_final.hpp> +#include <boost/poly_collection/detail/packed_segment.hpp> +#include <boost/poly_collection/detail/stride_iterator.hpp> +#include <memory> +#include <type_traits> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* model for base_collection */ + +template<typename Base> +struct base_model +{ + using value_type=Base; + template<typename Derived> + using is_subtype=std::is_base_of<Base,Derived>; + template<typename T> + using is_terminal=is_final<T>; //TODO: should we say !is_polymorhpic||is_final? + +private: + template<typename T> + using enable_if_not_terminal= + typename std::enable_if<!is_terminal<T>::value>::type*; + template<typename T> + using enable_if_terminal= + typename std::enable_if<is_terminal<T>::value>::type*; + +public: + template<typename T,enable_if_not_terminal<T> =nullptr> + static const std::type_info& subtypeid(const T& x){return typeid(x);} + + template<typename T,enable_if_terminal<T> =nullptr> + static const std::type_info& subtypeid(const T&){return typeid(T);} + + template<typename T,enable_if_not_terminal<T> =nullptr> + static void* subaddress(T& x) + { + return dynamic_cast<void*>(boost::addressof(x)); + } + + template<typename T,enable_if_not_terminal<T> =nullptr> + static const void* subaddress(const T& x) + { + return dynamic_cast<const void*>(boost::addressof(x)); + } + + template<typename T,enable_if_terminal<T> =nullptr> + static void* subaddress(T& x){return boost::addressof(x);} + + template<typename T,enable_if_terminal<T> =nullptr> + static const void* subaddress(const T& x){return boost::addressof(x);} + + using base_iterator=stride_iterator<Base>; + using const_base_iterator=stride_iterator<const Base>; + using base_sentinel=Base*; + using const_base_sentinel=const Base*; + template<typename Derived> + using iterator=Derived*; + template<typename Derived> + using const_iterator=const Derived*; + using segment_backend=detail::segment_backend<base_model>; + template<typename Derived,typename Allocator> + using segment_backend_implementation=packed_segment< + base_model, + Derived, + typename std::allocator_traits<Allocator>::template rebind_alloc<Derived> + >; + using segment_backend_unique_ptr= + typename segment_backend::segment_backend_unique_ptr; + + static base_iterator nonconst_iterator(const_base_iterator it) + { + return { + const_cast<value_type*>(static_cast<const value_type*>(it)), + it.stride() + }; + } + + template<typename T> + static iterator<T> nonconst_iterator(const_iterator<T> it) + { + return const_cast<iterator<T>>(it); + } + + template<typename Derived,typename Allocator> + static segment_backend_unique_ptr make(const Allocator& al) + { + return segment_backend_implementation<Derived,Allocator>::new_(al,al); + } + +private: + template<typename,typename,typename> + friend class packed_segment; + + template<typename Derived> + static const Base* value_ptr(const Derived* p)noexcept + { + return p; + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/callable_wrapper.hpp b/boost/poly_collection/detail/callable_wrapper.hpp new file mode 100644 index 0000000000..9b339db8f2 --- /dev/null +++ b/boost/poly_collection/detail/callable_wrapper.hpp @@ -0,0 +1,104 @@ +/* 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_DETAIL_CALLABLE_WRAPPER_HPP +#define BOOST_POLY_COLLECTION_DETAIL_CALLABLE_WRAPPER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/is_invocable.hpp> +#include <functional> +#include <type_traits> +#include <typeinfo> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* lightweight std::function look-alike over non-owned callable entities */ + +template<typename Signature> +class callable_wrapper; + +template<typename R,typename... Args> +class callable_wrapper<R(Args...)> +{ +public: + // TODO: we should prevent assignment by user code + template< + typename Callable, + typename std::enable_if< + !std::is_same<Callable,callable_wrapper>::value&& + is_invocable_r<R,Callable,Args...>::value + >::type* =nullptr + > + explicit callable_wrapper(Callable& x)noexcept:pt{info(x)},px{&x}{} + callable_wrapper(const callable_wrapper&)=default; + callable_wrapper& operator=(const callable_wrapper&)=default; + + explicit operator bool()const noexcept{return true;} + + R operator()(Args... args)const + {return pt->call(px,std::forward<Args>(args)...);} + + const std::type_info& target_type()const noexcept{return pt->info;} + + template<typename T> + T* target()noexcept + {return typeid(T)==pt->info?static_cast<T*>(px):nullptr;} + template<typename T> + const T* target()const noexcept + {return typeid(T)==pt->info?static_cast<const T*>(px):nullptr;} + + /* not in std::function interface */ + + operator std::function<R(Args...)>()const noexcept{return pt->convert(px);} + + void* data()noexcept{return px;} + const void* data()const noexcept{return px;} + +private: + struct table + { + R(*call)(void*,Args...); + const std::type_info& info; + std::function<R(Args...)> (*convert)(void*); + }; + + template<typename Callable> + static table* info(Callable&)noexcept + { + static table t={ + [](void* p,Args... args){ + auto r=std::ref(*static_cast<Callable*>(p)); + return static_cast<R>(r(std::forward<Args>(args)...)); + }, + typeid(Callable), + [](void* p){ + auto r=std::ref(*static_cast<Callable*>(p)); + return std::function<R(Args...)>{r}; + } + }; + return &t; + } + + table* pt; + void* px; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/callable_wrapper_iterator.hpp b/boost/poly_collection/detail/callable_wrapper_iterator.hpp new file mode 100644 index 0000000000..fb3ca2338d --- /dev/null +++ b/boost/poly_collection/detail/callable_wrapper_iterator.hpp @@ -0,0 +1,95 @@ +/* Copyright 2016 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_DETAIL_CALLABLE_WRAPPER_ITERATOR_HPP +#define BOOST_POLY_COLLECTION_DETAIL_CALLABLE_WRAPPER_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_adaptor.hpp> +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* callable_wrapper<Sig>* adaptor convertible to pointer to wrapped entity */ + +template<typename CWrapper> +class callable_wrapper_iterator:public boost::iterator_adaptor< + callable_wrapper_iterator<CWrapper>,CWrapper* +> +{ +public: + callable_wrapper_iterator()=default; + explicit callable_wrapper_iterator(CWrapper* p)noexcept: + callable_wrapper_iterator::iterator_adaptor_{p}{} + callable_wrapper_iterator(const callable_wrapper_iterator&)=default; + callable_wrapper_iterator& operator=( + const callable_wrapper_iterator&)=default; + + template< + typename NonConstCWrapper, + typename std::enable_if< + std::is_same<CWrapper,const NonConstCWrapper>::value>::type* =nullptr + > + callable_wrapper_iterator( + const callable_wrapper_iterator<NonConstCWrapper>& x)noexcept: + callable_wrapper_iterator::iterator_adaptor_{x.base()}{} + + template< + typename NonConstCWrapper, + typename std::enable_if< + std::is_same<CWrapper,const NonConstCWrapper>::value>::type* =nullptr + > + callable_wrapper_iterator& operator=( + const callable_wrapper_iterator<NonConstCWrapper>& x)noexcept + { + this->base_reference()=x.base(); + return *this; + } + + /* interoperability with CWrapper* */ + + callable_wrapper_iterator& operator=(CWrapper* p)noexcept + {this->base_reference()=p;return *this;} + operator CWrapper*()const noexcept{return this->base();} + + /* interoperability with Callable* */ + + template< + typename Callable, + typename std::enable_if< + std::is_constructible<CWrapper,Callable&>::value&& + (!std::is_const<CWrapper>::value||std::is_const<Callable>::value) + >::type* =nullptr + > + explicit operator Callable*()const noexcept + { + return const_cast<Callable*>( + static_cast<const Callable*>( + const_cast<const void*>( + this->base()->data()))); + } + +private: + template<typename> + friend class callable_wrapper_iterator; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/function_model.hpp b/boost/poly_collection/detail/function_model.hpp new file mode 100644 index 0000000000..bc2f9b6846 --- /dev/null +++ b/boost/poly_collection/detail/function_model.hpp @@ -0,0 +1,137 @@ +/* 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_DETAIL_FUNCTION_MODEL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_FUNCTION_MODEL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/core/addressof.hpp> +#include <boost/poly_collection/detail/callable_wrapper.hpp> +#include <boost/poly_collection/detail/callable_wrapper_iterator.hpp> +#include <boost/poly_collection/detail/is_invocable.hpp> +#include <boost/poly_collection/detail/segment_backend.hpp> +#include <boost/poly_collection/detail/split_segment.hpp> +#include <memory> +#include <type_traits> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* model for function_collection */ + +template<typename Signature> +struct function_model; + +/* is_terminal defined out-class to allow for partial specialization */ + +template<typename T> +struct function_model_is_terminal:std::true_type{}; + +template<typename Signature> +struct function_model_is_terminal<callable_wrapper<Signature>>: + std::false_type{}; + +template<typename R,typename... Args> +struct function_model<R(Args...)> +{ + using value_type=callable_wrapper<R(Args...)>; + + template<typename Callable> + using is_subtype=is_invocable_r<R,Callable&,Args...>; + + template<typename T> + using is_terminal=function_model_is_terminal<T>; + + template<typename T> + static const std::type_info& subtypeid(const T&){return typeid(T);} + + template<typename Signature> + static const std::type_info& subtypeid( + const callable_wrapper<Signature>& f) + { + return f.target_type(); + } + + template<typename T> + static void* subaddress(T& x){return boost::addressof(x);} + + template<typename T> + static const void* subaddress(const T& x){return boost::addressof(x);} + + template<typename Signature> + static void* subaddress(callable_wrapper<Signature>& f) + { + return f.data(); + } + + template<typename Signature> + static const void* subaddress(const callable_wrapper<Signature>& f) + { + return f.data(); + } + + using base_iterator=callable_wrapper_iterator<value_type>; + using const_base_iterator=callable_wrapper_iterator<const value_type>; + using base_sentinel=value_type*; + using const_base_sentinel=const value_type*; + template<typename Callable> + using iterator=Callable*; + template<typename Callable> + using const_iterator=const Callable*; + using segment_backend=detail::segment_backend<function_model>; + template<typename Callable,typename Allocator> + using segment_backend_implementation=split_segment< + function_model, + Callable, + typename std::allocator_traits<Allocator>:: + template rebind_alloc<Callable> + >; + using segment_backend_unique_ptr= + typename segment_backend::segment_backend_unique_ptr; + + static base_iterator nonconst_iterator(const_base_iterator it) + { + return base_iterator{ + const_cast<value_type*>(static_cast<const value_type*>(it))}; + } + + template<typename T> + static iterator<T> nonconst_iterator(const_iterator<T> it) + { + return const_cast<iterator<T>>(it); + } + + template<typename Callable,typename Allocator> + static segment_backend_unique_ptr make(const Allocator& al) + { + return segment_backend_implementation<Callable,Allocator>::new_(al,al); + } + +private: + template<typename,typename,typename> + friend class split_segment; + + template<typename Callable> + static value_type make_value_type(Callable& x){return value_type{x};} +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/functional.hpp b/boost/poly_collection/detail/functional.hpp new file mode 100644 index 0000000000..26e1bcb394 --- /dev/null +++ b/boost/poly_collection/detail/functional.hpp @@ -0,0 +1,196 @@ +/* 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_DETAIL_FUNCTIONAL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_FUNCTIONAL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/poly_collection/detail/integer_sequence.hpp> +#include <tuple> +#include <utility> + +/* Assorted functional utilities. Much of this would be almost trivial with + * C++14 generic lambdas. + */ + +#if BOOST_WORKAROUND(BOOST_MSVC,>=1910) +/* https://lists.boost.org/Archives/boost/2017/06/235687.php */ + +#define BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(name,f) \ +struct name \ +{ \ + template<typename... Args> \ + auto operator()(Args&&... args)const \ + { \ + return f(std::forward<Args>(args)...); \ + } \ +}; +#else +#define BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(name,f) \ +struct name \ +{ \ + template<typename... Args> \ + auto operator()(Args&&... args)const-> \ + decltype(f(std::forward<Args>(args)...)) \ + { \ + return f(std::forward<Args>(args)...); \ + } \ +}; +#endif + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename F,typename Tuple> +struct tail_closure_class +{ + template<typename... Args,std::size_t... I> + auto call(index_sequence<I...>,Args&&... args) + ->decltype(std::declval<F>()( + std::forward<Args>(args)..., + std::get<I>(std::declval<Tuple>())...)) + { + return f(std::forward<Args>(args)...,std::get<I>(t)...); + } + + template<typename... Args> + auto operator()(Args&&... args) + ->decltype(this->call( + make_index_sequence<std::tuple_size<Tuple>::value>{}, + std::forward<Args>(args)...)) + { + return call( + make_index_sequence<std::tuple_size<Tuple>::value>{}, + std::forward<Args>(args)...); + } + + F f; + Tuple t; +}; + +template<typename F,typename... Args> +auto tail_closure(const F& f,Args&&... args) + ->tail_closure_class<F,std::tuple<Args&&...>> +{ + return {f,std::forward_as_tuple(std::forward<Args>(args)...)}; +} + +template<typename F,typename Tuple> +struct head_closure_class +{ + template<typename... Args,std::size_t... I> + auto call(index_sequence<I...>,Args&&... args) + ->decltype(std::declval<F>()( + std::get<I>(std::declval<Tuple>())...,std::forward<Args>(args)...)) + { + return f(std::get<I>(t)...,std::forward<Args>(args)...); + } + + template<typename... Args> + auto operator()(Args&&... args) + ->decltype(this->call( + make_index_sequence<std::tuple_size<Tuple>::value>{}, + std::forward<Args>(args)...)) + { + return call( + make_index_sequence<std::tuple_size<Tuple>::value>{}, + std::forward<Args>(args)...); + } + + F f; + Tuple t; +}; + +template<typename F,typename... Args> +auto head_closure(const F& f,Args&&... args) + ->head_closure_class<F,std::tuple<Args&&...>> +{ + return {f,std::forward_as_tuple(std::forward<Args>(args)...)}; +} + +template<typename ReturnType,typename F> +struct cast_return_class +{ + template<typename... Args> + ReturnType operator()(Args&&... args)const + { + return static_cast<ReturnType>(f(std::forward<Args>(args)...)); + } + + F f; +}; + +template<typename ReturnType,typename F> +cast_return_class<ReturnType,F> cast_return(const F& f) +{ + return {f}; +} + +template<typename F> +struct deref_to_class +{ + template<typename... Args> + auto operator()(Args&&... args)->decltype(std::declval<F>()(*args...)) + { + return f(*args...); + } + + F f; +}; + +template<typename F> +deref_to_class<F> deref_to(const F& f) +{ + return {f}; +} + +template<typename F> +struct deref_1st_to_class +{ + template<typename Arg,typename... Args> + auto operator()(Arg&& arg,Args&&... args) + ->decltype(std::declval<F>()(*arg,std::forward<Args>(args)...)) + { + return f(*arg,std::forward<Args>(args)...); + } + + F f; +}; + +template<typename F> +deref_1st_to_class<F> deref_1st_to(const F& f) +{ + return {f}; +} + +struct transparent_equal_to +{ + template<typename T,typename U> + auto operator()(T&& x,U&& y)const + noexcept(noexcept(std::forward<T>(x)==std::forward<U>(y))) + ->decltype(std::forward<T>(x)==std::forward<U>(y)) + { + return std::forward<T>(x)==std::forward<U>(y); + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/integer_sequence.hpp b/boost/poly_collection/detail/integer_sequence.hpp new file mode 100644 index 0000000000..d88e833f99 --- /dev/null +++ b/boost/poly_collection/detail/integer_sequence.hpp @@ -0,0 +1,64 @@ +/* Copyright 2016 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_DETAIL_INTEGER_SEQUENCE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_INTEGER_SEQUENCE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <cstddef> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* ripped from http://pdimov.com/cpp2/simple_cxx11_metaprogramming.html */ + +template<typename T,T... Ints> struct integer_sequence{}; + +template<typename S> struct next_integer_sequence; + +template<typename T,T... Ints> +struct next_integer_sequence<integer_sequence<T,Ints...>> +{ + using type=integer_sequence<T,Ints...,sizeof...(Ints)>; +}; + +template<typename T,T I,T N> struct make_int_seq_impl; + +template<typename T,T N> +using make_integer_sequence=typename make_int_seq_impl<T,0,N>::type; + +template<typename T,T I,T N> struct make_int_seq_impl +{ + using type=typename next_integer_sequence< + typename make_int_seq_impl<T,I+1,N>::type>::type; +}; + +template<typename T,T N> struct make_int_seq_impl<T,N,N> +{ + using type=integer_sequence<T>; +}; + +template<std::size_t... Ints> +using index_sequence=integer_sequence<std::size_t,Ints...>; + +template<std::size_t N> +using make_index_sequence=make_integer_sequence<std::size_t,N>; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_acceptable.hpp b/boost/poly_collection/detail/is_acceptable.hpp new file mode 100644 index 0000000000..c578b8e92e --- /dev/null +++ b/boost/poly_collection/detail/is_acceptable.hpp @@ -0,0 +1,44 @@ +/* Copyright 2016 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_DETAIL_IS_ACCEPTABLE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_ACCEPTABLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* This can be further specialized by Model when the std type trait classes + * fail to give the right info (as it can happen with class templates whose + * nominally existing operators do not compile for certain instantiations). + */ + +template<typename T,typename Model,typename=void> +struct is_acceptable:std::integral_constant< + bool, + Model::template is_subtype<T>::value&& + std::is_move_constructible<typename std::decay<T>::type>::value&& + (std::is_move_assignable<typename std::decay<T>::type>::value|| + std::is_nothrow_move_constructible<typename std::decay<T>::type>::value) +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_constructible.hpp b/boost/poly_collection/detail/is_constructible.hpp new file mode 100644 index 0000000000..5770fab537 --- /dev/null +++ b/boost/poly_collection/detail/is_constructible.hpp @@ -0,0 +1,61 @@ +/* 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_DETAIL_IS_CONSTRUCIBLE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_CONSTRUCIBLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> +#include <boost/detail/workaround.hpp> + +#if BOOST_WORKAROUND(BOOST_MSVC,BOOST_TESTED_AT(1900)) +/* https://connect.microsoft.com/VisualStudio/Feedback/Details/2118677 */ + +#include <boost/type_traits/is_constructible.hpp> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename T,typename... Args> +struct is_constructible:std::integral_constant< + bool, + boost::is_constructible<T,Args...>::value +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#else +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename T,typename... Args> +using is_constructible=std::is_constructible<T,Args...>; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif +#endif diff --git a/boost/poly_collection/detail/is_equality_comparable.hpp b/boost/poly_collection/detail/is_equality_comparable.hpp new file mode 100644 index 0000000000..898dd55f14 --- /dev/null +++ b/boost/poly_collection/detail/is_equality_comparable.hpp @@ -0,0 +1,89 @@ +/* Copyright 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_DETAIL_IS_EQUALITY_COMPARABLE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_EQUALITY_COMPARABLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/config.hpp> +#include <type_traits> + +#if !defined(BOOST_NO_SFINAE_EXPR) +#include <utility> +#else +#include <boost/poly_collection/detail/is_likely_stateless_lambda.hpp> +#include <boost/type_traits/has_equal_to.hpp> +#endif + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +#if !defined(BOOST_NO_SFINAE_EXPR) + +/* trivial, expression SFINAE-based implementation */ + +template<typename T,typename=void> +struct is_equality_comparable:std::false_type{}; + +template<typename T> +struct is_equality_comparable< + T, + typename std::enable_if< + std::is_convertible< + decltype(std::declval<T>()==std::declval<T>()),bool + >::value + >::type +>:std::true_type{}; + +#else +/* boost::has_equal_to does a decent job without using expression SFINAE, + * but it produces a compile error when the type T being checked is + * convertible to an equality-comparable type Q. Exotic as it may seem, + * this is exactly the situation with the very important case of stateless + * lambda expressions, which are convertible to an equality-comparable + * function pointer with the same signature. We take explicit care of + * stateless lambdas then. + */ + +template<typename T,typename=void> +struct is_equality_comparable:std::integral_constant< + bool, + has_equal_to<T,T,bool>::value +>{}; + +template<typename T> +struct is_equality_comparable< + T, + typename std::enable_if<is_likely_stateless_lambda<T>::value>::type +>: +#if !defined(BOOST_MSVC) + std::true_type{}; +#else + /* To complicate things further, in VS stateless lambdas are convertible not + * only to regular function pointers, but also to other call conventions + * such as __stdcall, __fastcall, etc., which makes equality comparison + * ambiguous. + */ + + std::false_type{}; +#endif +#endif + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_final.hpp b/boost/poly_collection/detail/is_final.hpp new file mode 100644 index 0000000000..b9d91fcf8f --- /dev/null +++ b/boost/poly_collection/detail/is_final.hpp @@ -0,0 +1,68 @@ +/* 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_DETAIL_IS_FINAL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_FINAL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/type_traits/is_final.hpp> +#include <type_traits> + +/* technique explained at + * http://bannalia.blogspot.com/2016/09/compile-time-checking-existence-of.html + */ + +namespace boost{ +namespace poly_collection{ +namespace detail{ +namespace is_final_fallback{ + +template<typename T> using is_final=boost::is_final<T>; + +struct hook{}; + +}}}} + +namespace std{ + +template<> +struct is_void< ::boost::poly_collection::detail::is_final_fallback::hook>: + std::false_type +{ + template<typename T> + static constexpr bool is_final_f() + { + using namespace ::boost::poly_collection::detail::is_final_fallback; + return is_final<T>::value; + } +}; + +} /* namespace std */ + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename T> +struct is_final:std::integral_constant< + bool, + std::is_void<is_final_fallback::hook>::template is_final_f<T>() +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_invocable.hpp b/boost/poly_collection/detail/is_invocable.hpp new file mode 100644 index 0000000000..c93ba476b7 --- /dev/null +++ b/boost/poly_collection/detail/is_invocable.hpp @@ -0,0 +1,97 @@ +/* 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_DETAIL_IS_INVOCABLE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_INVOCABLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <functional> +#include <type_traits> + +/* technique explained at + * http://bannalia.blogspot.com/2016/09/compile-time-checking-existence-of.html + */ + +namespace boost{ +namespace poly_collection{ +namespace detail{ +namespace is_invocable_fallback{ + +template <typename F,typename... Args> +struct is_invocable: + std::is_constructible< + std::function<void(Args...)>, + std::reference_wrapper<typename std::remove_reference<F>::type> + > +{}; + +template <typename R,typename F,typename... Args> +struct is_invocable_r: + std::is_constructible< + std::function<R(Args...)>, + std::reference_wrapper<typename std::remove_reference<F>::type> + > +{}; + +struct hook{}; + +}}}} + +namespace std{ + +template<> +struct is_void< ::boost::poly_collection::detail::is_invocable_fallback::hook>: + std::false_type +{ + template<typename F,typename... Args> + static constexpr bool is_invocable_f() + { + using namespace ::boost::poly_collection::detail::is_invocable_fallback; + return is_invocable<F,Args...>::value; + } + + template<typename R,typename F,typename... Args> + static constexpr bool is_invocable_r_f() + { + using namespace ::boost::poly_collection::detail::is_invocable_fallback; + return is_invocable_r<R,F,Args...>::value; + } +}; + +} /* namespace std */ + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename F,typename... Args> +struct is_invocable:std::integral_constant< + bool, + std::is_void<is_invocable_fallback::hook>::template + is_invocable_f<F,Args...>() +>{}; + +template<typename R,typename F,typename... Args> +struct is_invocable_r:std::integral_constant< + bool, + std::is_void<is_invocable_fallback::hook>::template + is_invocable_r_f<R,F,Args...>() +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_likely_stateless_lambda.hpp b/boost/poly_collection/detail/is_likely_stateless_lambda.hpp new file mode 100644 index 0000000000..d8469c0dd3 --- /dev/null +++ b/boost/poly_collection/detail/is_likely_stateless_lambda.hpp @@ -0,0 +1,70 @@ +/* Copyright 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_DETAIL_IS_LIKELY_STATELESS_LAMBDA_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_LIKELY_STATELESS_LAMBDA_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* Stateless lambda expressions have one (and only one) call operator and are + * convertible to a function pointer with the same signature. Non-lambda types + * could satisfy this too, hence the "likely" qualifier. + */ + +template<typename T> +struct has_one_operator_call_helper +{ + template<typename Q> static std::true_type test(decltype(&Q::operator())*); + template<typename> static std::false_type test(...); + + using type=decltype(test<T>(nullptr)); +}; + +template<typename T> +using has_one_operator_call=typename has_one_operator_call_helper<T>::type; + +template<typename T> +struct equivalent_function_pointer +{ + template<typename Q,typename R,typename... Args> + static auto helper(R (Q::*)(Args...)const)->R(*)(Args...); + template<typename Q,typename R,typename... Args> + static auto helper(R (Q::*)(Args...))->R(*)(Args...); + + using type=decltype(helper(&T::operator())); +}; + +template<typename T,typename=void> +struct is_likely_stateless_lambda:std::false_type{}; + +template<typename T> +struct is_likely_stateless_lambda< + T, + typename std::enable_if<has_one_operator_call<T>::value>::type +>:std::is_convertible< + T, + typename equivalent_function_pointer<T>::type +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/is_nothrow_eq_comparable.hpp b/boost/poly_collection/detail/is_nothrow_eq_comparable.hpp new file mode 100644 index 0000000000..7448b65e54 --- /dev/null +++ b/boost/poly_collection/detail/is_nothrow_eq_comparable.hpp @@ -0,0 +1,46 @@ +/* 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_DETAIL_IS_NOTHROW_EQ_COMPARABLE_HPP +#define BOOST_POLY_COLLECTION_DETAIL_IS_NOTHROW_EQ_COMPARABLE_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/is_equality_comparable.hpp> +#include <type_traits> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +template<typename T,typename=void> +struct is_nothrow_equality_comparable:std::false_type{}; + +template<typename T> +struct is_nothrow_equality_comparable< + T, + typename std::enable_if< + is_equality_comparable<T>::value + >::type +>:std::integral_constant< + bool, + noexcept(std::declval<T>()==std::declval<T>()) +>{}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/iterator_impl.hpp b/boost/poly_collection/detail/iterator_impl.hpp new file mode 100644 index 0000000000..e1893527d1 --- /dev/null +++ b/boost/poly_collection/detail/iterator_impl.hpp @@ -0,0 +1,242 @@ +/* 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_DETAIL_ITERATOR_IMPL_HPP +#define BOOST_POLY_COLLECTION_DETAIL_ITERATOR_IMPL_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_adaptor.hpp> +#include <boost/iterator/iterator_facade.hpp> +#include <boost/poly_collection/detail/is_constructible.hpp> +#include <boost/poly_collection/detail/iterator_traits.hpp> +#include <type_traits> +#include <typeinfo> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* Implementations of poly_collection::[const_][local_[base_]]iterator moved + * out of class to allow for use in deduced contexts. + */ + +template<typename PolyCollection,bool Const> +using iterator_impl_value_type=typename std::conditional< + Const, + const typename PolyCollection::value_type, + typename PolyCollection::value_type +>::type; + +template<typename PolyCollection,bool Const> +class iterator_impl: + public boost::iterator_facade< + iterator_impl<PolyCollection,Const>, + iterator_impl_value_type<PolyCollection,Const>, + boost::forward_traversal_tag + > +{ + using segment_type=typename PolyCollection::segment_type; + using const_segment_base_iterator= + typename PolyCollection::const_segment_base_iterator; + using const_segment_base_sentinel= + typename PolyCollection::const_segment_base_sentinel; + using const_segment_map_iterator= + typename PolyCollection::const_segment_map_iterator; + +public: + using value_type=iterator_impl_value_type<PolyCollection,Const>; + +private: + iterator_impl( + const_segment_map_iterator mapit, + const_segment_map_iterator mapend)noexcept: + mapit{mapit},mapend{mapend} + { + next_segment_position(); + } + + iterator_impl( + const_segment_map_iterator mapit_,const_segment_map_iterator mapend_, + const_segment_base_iterator segpos_)noexcept: + mapit{mapit_},mapend{mapend_},segpos{segpos_} + { + if(mapit!=mapend&&segpos==sentinel()){ + ++mapit; + next_segment_position(); + } + } + +public: + iterator_impl()=default; + iterator_impl(const iterator_impl&)=default; + iterator_impl& operator=(const iterator_impl&)=default; + + template<bool Const2,typename std::enable_if<!Const2>::type* =nullptr> + iterator_impl(const iterator_impl<PolyCollection,Const2>& x): + mapit{x.mapit},mapend{x.mapend},segpos{x.segpos}{} + +private: + template<typename,bool> + friend class iterator_impl; + friend PolyCollection; + friend class boost::iterator_core_access; + template<typename> + friend struct iterator_traits; + + value_type& dereference()const noexcept + {return const_cast<value_type&>(*segpos);} + bool equal(const iterator_impl& x)const noexcept{return segpos==x.segpos;} + + void increment()noexcept + { + if(++segpos==sentinel()){ + ++mapit; + next_segment_position(); + } + } + + void next_segment_position()noexcept + { + for(;mapit!=mapend;++mapit){ + segpos=segment().begin(); + if(segpos!=sentinel())return; + } + segpos=nullptr; + } + + segment_type& segment()noexcept + {return const_cast<segment_type&>(mapit->second);} + const segment_type& segment()const noexcept{return mapit->second;} + + const_segment_base_sentinel sentinel()const noexcept + {return segment().sentinel();} + + const_segment_map_iterator mapit,mapend; + const_segment_base_iterator segpos; +}; + +template<typename PolyCollection,bool Const> +struct poly_collection_of<iterator_impl<PolyCollection,Const>> +{ + using type=PolyCollection; +}; + +template<typename PolyCollection,typename BaseIterator> +class local_iterator_impl: + public boost::iterator_adaptor< + local_iterator_impl<PolyCollection,BaseIterator>, + BaseIterator + > +{ + using segment_type=typename PolyCollection::segment_type; + using segment_base_iterator=typename PolyCollection::segment_base_iterator; + using const_segment_map_iterator= + typename PolyCollection::const_segment_map_iterator; + + template<typename Iterator> + local_iterator_impl( + const_segment_map_iterator mapit, + Iterator it): + local_iterator_impl::iterator_adaptor_{BaseIterator(it)}, + mapit{mapit} + {} + +public: + using base_iterator=BaseIterator; + + local_iterator_impl()=default; + local_iterator_impl(const local_iterator_impl&)=default; + local_iterator_impl& operator=(const local_iterator_impl&)=default; + + template< + typename BaseIterator2, + typename std::enable_if< + std::is_convertible<BaseIterator2,BaseIterator>::value + >::type* =nullptr + > + local_iterator_impl( + const local_iterator_impl<PolyCollection,BaseIterator2>& x): + local_iterator_impl::iterator_adaptor_{x.base()}, + mapit{x.mapit}{} + + template< + typename BaseIterator2, + typename std::enable_if< + !std::is_convertible<BaseIterator2,BaseIterator>::value&& + is_constructible<BaseIterator,BaseIterator2>::value + >::type* =nullptr + > + explicit local_iterator_impl( + const local_iterator_impl<PolyCollection,BaseIterator2>& x): + local_iterator_impl::iterator_adaptor_{BaseIterator(x.base())}, + mapit{x.mapit}{} + + template< + typename BaseIterator2, + typename std::enable_if< + !is_constructible<BaseIterator,BaseIterator2>::value&& + is_constructible<BaseIterator,segment_base_iterator>::value&& + is_constructible<BaseIterator2,segment_base_iterator>::value + >::type* =nullptr + > + explicit local_iterator_impl( + const local_iterator_impl<PolyCollection,BaseIterator2>& x): + local_iterator_impl::iterator_adaptor_{ + base_iterator_from(x.segment(),x.base())}, + mapit{x.mapit}{} + + /* define [] to avoid Boost.Iterator operator_brackets_proxy mess */ + + template<typename DifferenceType> + typename std::iterator_traits<BaseIterator>::reference + operator[](DifferenceType n)const{return *(*this+n);} + +private: + template<typename,typename> + friend class local_iterator_impl; + friend PolyCollection; + template<typename> + friend struct iterator_traits; + + template<typename BaseIterator2> + static BaseIterator base_iterator_from( + const segment_type& s,BaseIterator2 it) + { + segment_base_iterator bit=s.begin(); + return BaseIterator{bit+(it-static_cast<BaseIterator2>(bit))}; + } + + base_iterator base()const noexcept + {return local_iterator_impl::iterator_adaptor_::base();} + const std::type_info& type_info()const{return *mapit->first;} + segment_type& segment()noexcept + {return const_cast<segment_type&>(mapit->second);} + const segment_type& segment()const noexcept{return mapit->second;} + + const_segment_map_iterator mapit; +}; + +template<typename PolyCollection,typename BaseIterator> +struct poly_collection_of<local_iterator_impl<PolyCollection,BaseIterator>> +{ + using type=PolyCollection; +}; + + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/iterator_traits.hpp b/boost/poly_collection/detail/iterator_traits.hpp new file mode 100644 index 0000000000..732535a8b4 --- /dev/null +++ b/boost/poly_collection/detail/iterator_traits.hpp @@ -0,0 +1,116 @@ +/* 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_DETAIL_ITERATOR_TRAITS_HPP +#define BOOST_POLY_COLLECTION_DETAIL_ITERATOR_TRAITS_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <iterator> +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* (Internal) bunch of traits-grouped functions for const-preserving + * interoperatibility between iterators and local iterators of a + * poly_collection. + */ + +template<typename Iterator> +struct poly_collection_of /* to be specialized for iterator impls */ +{ + using type=void; +}; + +namespace poly_collection_impl{ + +template<typename Model,typename Allocator> +class poly_collection; + +} + +template<typename PolyCollection> +struct model_of; + +template<typename Model,typename Allocator> +struct model_of<poly_collection_impl::poly_collection<Model,Allocator>> +{ + using type=Model; +}; + +template<typename Iterator> +struct iterator_traits +{ + using container_type=typename poly_collection_of<Iterator>::type; + using is_const_iterator=typename std::is_const< + typename std::remove_reference< + typename std::iterator_traits<Iterator>::reference + >::type + >::type; + using iterator=typename std::conditional< + is_const_iterator::value, + typename container_type::const_iterator, + typename container_type::iterator + >::type; + using base_segment_info_iterator=typename std::conditional< + is_const_iterator::value, + typename container_type::const_base_segment_info_iterator, + typename container_type::base_segment_info_iterator + >::type; + using local_base_iterator=typename std::conditional< + is_const_iterator::value, + typename container_type::const_local_base_iterator, + typename container_type::local_base_iterator + >::type; + template<typename T> + using local_iterator=typename std::conditional< + is_const_iterator::value, + typename container_type::template const_local_iterator<T>, + typename container_type::template local_iterator<T> + >::type; + + static base_segment_info_iterator + base_segment_info_iterator_from(iterator it)noexcept{return it.mapit;} + + static base_segment_info_iterator + base_segment_info_iterator_from(local_base_iterator it)noexcept + {return it.mapit;} + + static base_segment_info_iterator + end_base_segment_info_iterator_from(iterator it)noexcept{return it.mapend;} + + static local_base_iterator + local_base_iterator_from(iterator it)noexcept + { + return { + it.mapit, + model_of<container_type>::type::nonconst_iterator(it.segpos) + }; + } + + static iterator + iterator_from( + local_base_iterator lbit,base_segment_info_iterator mapend)noexcept + { + return {lbit.mapit,mapend.base(),lbit.base()}; + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/newdelete_allocator.hpp b/boost/poly_collection/detail/newdelete_allocator.hpp new file mode 100644 index 0000000000..1c66db3b7a --- /dev/null +++ b/boost/poly_collection/detail/newdelete_allocator.hpp @@ -0,0 +1,102 @@ +/* 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_DETAIL_NEWDELETE_ALLOCATOR_HPP +#define BOOST_POLY_COLLECTION_DETAIL_NEWDELETE_ALLOCATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/is_constructible.hpp> +#include <memory> +#include <new> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* In order to comply with [container.requirements.general]/3, + * newdelete_allocator_adaptor<Allocator> overrides + * Allocator::construct/destroy with vanilla new/delete implementations. + * Used therefore in all auxiliary internal structures. + */ + +template<typename Allocator> +struct newdelete_allocator_adaptor:Allocator +{ + using traits=std::allocator_traits<Allocator>; + + using value_type=typename traits::value_type; + using size_type=typename traits::size_type; + using difference_type=typename traits::difference_type; + using pointer=typename traits::pointer; + using const_pointer=typename traits::const_pointer; + using void_pointer=typename traits::void_pointer; + using const_void_pointer=typename traits::const_void_pointer; + using propagate_on_container_copy_assignment= + typename traits::propagate_on_container_copy_assignment; + using propagate_on_container_move_assignment= + typename traits::propagate_on_container_move_assignment; + using propagate_on_container_swap= + typename traits::propagate_on_container_swap; + + template<typename U> + struct rebind + { + using other=newdelete_allocator_adaptor< + typename traits::template rebind_alloc<U>>; + }; + + newdelete_allocator_adaptor()=default; + newdelete_allocator_adaptor(const newdelete_allocator_adaptor&)=default; + + template< + typename Allocator2, + typename std::enable_if< + is_constructible<Allocator,Allocator2>::value + >::type* =nullptr + > + newdelete_allocator_adaptor(const Allocator2& x)noexcept:Allocator{x}{} + + template< + typename Allocator2, + typename std::enable_if< + is_constructible<Allocator,Allocator2>::value + >::type* =nullptr + > + newdelete_allocator_adaptor( + const newdelete_allocator_adaptor<Allocator2>& x)noexcept: + Allocator{static_cast<const Allocator2&>(x)}{} + + newdelete_allocator_adaptor& operator=( + const newdelete_allocator_adaptor&)=default; + + template<typename T,typename... Args> + void construct(T* p,Args&&... args) + { + ::new ((void*)p) T(std::forward<Args>(args)...); + } + + template<typename T> + void destroy(T* p) + { + p->~T(); + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/packed_segment.hpp b/boost/poly_collection/detail/packed_segment.hpp new file mode 100644 index 0000000000..5500a2d5fc --- /dev/null +++ b/boost/poly_collection/detail/packed_segment.hpp @@ -0,0 +1,318 @@ +/* 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_DETAIL_PACKED_SEGMENT_HPP +#define BOOST_POLY_COLLECTION_DETAIL_PACKED_SEGMENT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/newdelete_allocator.hpp> +#include <boost/poly_collection/detail/segment_backend.hpp> +#include <boost/poly_collection/detail/value_holder.hpp> +#include <memory> +#include <new> +#include <vector> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* segment_backend implementation where value_type& and Concrete& actually refer + * to the same stored entity. + * + * Requires: + * - [const_]base_iterator is a stride iterator constructible from + * {value_type*,sizeof(store_value_type)}. + * - Model provides a function value_ptr for + * const Concrete* -> const value_type* conversion. + */ + +template<typename Model,typename Concrete,typename Allocator> +class packed_segment:public segment_backend<Model> +{ + using value_type=typename Model::value_type; + using store_value_type=value_holder<Concrete>; + using store=std::vector< + store_value_type, + value_holder_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<store_value_type> + > + >; + using store_iterator=typename store::iterator; + using const_store_iterator=typename store::const_iterator; + using segment_backend=detail::segment_backend<Model>; + using typename segment_backend::segment_backend_unique_ptr; + using typename segment_backend::value_pointer; + using typename segment_backend::const_value_pointer; + using typename segment_backend::base_iterator; + using typename segment_backend::const_base_iterator; + using const_iterator= + typename segment_backend::template const_iterator<Concrete>; + using typename segment_backend::base_sentinel; + using typename segment_backend::range; + using segment_allocator_type=newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<packed_segment> + >; +public: + virtual ~packed_segment()=default; + + virtual segment_backend_unique_ptr copy()const + { + return new_(s.get_allocator(),store{s}); + } + + virtual segment_backend_unique_ptr empty_copy()const + { + return new_(s.get_allocator(),s.get_allocator()); + } + + virtual bool equal(const segment_backend& x)const + { + return s==static_cast<const packed_segment&>(x).s; + } + + virtual base_iterator begin()const noexcept{return nv_begin();} + + base_iterator nv_begin()const noexcept + { + return {value_ptr(s.data()),sizeof(store_value_type)}; + } + + virtual base_iterator end()const noexcept{return nv_end();} + + base_iterator nv_end()const noexcept + { + return {value_ptr(s.data()+s.size()),sizeof(store_value_type)}; + } + + virtual bool empty()const noexcept{return nv_empty();} + bool nv_empty()const noexcept{return s.empty();} + virtual std::size_t size()const noexcept{return nv_size();} + std::size_t nv_size()const noexcept{return s.size();} + virtual std::size_t max_size()const noexcept{return nv_max_size();} + std::size_t nv_max_size()const noexcept{return s.max_size();} + virtual std::size_t capacity()const noexcept{return nv_capacity();} + std::size_t nv_capacity()const noexcept{return s.capacity();} + virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);} + base_sentinel nv_reserve(std::size_t n) + {s.reserve(n);return sentinel();} + virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();} + base_sentinel nv_shrink_to_fit() + {s.shrink_to_fit();return sentinel();} + + template<typename Iterator,typename... Args> + range nv_emplace(Iterator p,Args&&... args) + { + return range_from( + s.emplace( + iterator_from(p), + value_holder_emplacing_ctor,std::forward<Args>(args)...)); + } + + template<typename... Args> + range nv_emplace_back(Args&&... args) + { + s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...); + return range_from(s.size()-1); + } + + virtual range push_back(const_value_pointer x) + {return nv_push_back(const_concrete_ref(x));} + + range nv_push_back(const Concrete& x) + { + s.emplace_back(x); + return range_from(s.size()-1); + } + + virtual range push_back_move(value_pointer x) + {return nv_push_back(std::move(concrete_ref(x)));} + + range nv_push_back(Concrete&& x) + { + s.emplace_back(std::move(x)); + return range_from(s.size()-1); + } + + virtual range insert(const_base_iterator p,const_value_pointer x) + {return nv_insert(const_iterator(p),const_concrete_ref(x));} + + range nv_insert(const_iterator p,const Concrete& x) + { + return range_from(s.emplace(iterator_from(p),x)); + } + + virtual range insert_move(const_base_iterator p,value_pointer x) + {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));} + + range nv_insert(const_iterator p,Concrete&& x) + { + return range_from(s.emplace(iterator_from(p),std::move(x))); + } + + template<typename InputIterator> + range nv_insert(InputIterator first,InputIterator last) + { + return nv_insert( + const_iterator(concrete_ptr(s.data()+s.size())),first,last); + } + + template<typename InputIterator> + range nv_insert(const_iterator p,InputIterator first,InputIterator last) + { + return range_from(s.insert(iterator_from(p),first,last)); + } + + virtual range erase(const_base_iterator p) + {return nv_erase(const_iterator(p));} + + range nv_erase(const_iterator p) + { + return range_from(s.erase(iterator_from(p))); + } + + virtual range erase(const_base_iterator first,const_base_iterator last) + {return nv_erase(const_iterator(first),const_iterator(last));} + + range nv_erase(const_iterator first,const_iterator last) + { + return range_from(s.erase(iterator_from(first),iterator_from(last))); + } + + virtual range erase_till_end(const_base_iterator first) + { + return range_from(s.erase(iterator_from(first),s.end())); + } + + virtual range erase_from_begin(const_base_iterator last) + { + return range_from(s.erase(s.begin(),iterator_from(last))); + } + + virtual base_sentinel clear()noexcept{return nv_clear();} + base_sentinel nv_clear()noexcept{s.clear();return sentinel();} + +private: + friend Model; + + template<typename... Args> + static segment_backend_unique_ptr new_( + segment_allocator_type al,Args&&... args) + { + auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1); + try{ + ::new ((void*)p) packed_segment{std::forward<Args>(args)...}; + } + catch(...){ + std::allocator_traits<segment_allocator_type>::deallocate(al,p,1); + throw; + } + return {p,&delete_}; + } + + static void delete_(segment_backend* p) + { + auto q=static_cast<packed_segment*>(p); + auto al=segment_allocator_type{q->s.get_allocator()}; + q->~packed_segment(); + std::allocator_traits<segment_allocator_type>::deallocate(al,q,1); + } + + packed_segment(const Allocator& al):s{typename store::allocator_type{al}}{} + packed_segment(store&& s):s{std::move(s)}{} + + static Concrete& concrete_ref(value_pointer p)noexcept + { + return *static_cast<Concrete*>(p); + } + + static const Concrete& const_concrete_ref(const_value_pointer p)noexcept + { + return *static_cast<const Concrete*>(p); + } + + static Concrete* concrete_ptr(store_value_type* p)noexcept + { + return reinterpret_cast<Concrete*>( + static_cast<value_holder_base<Concrete>*>(p)); + } + + static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept + { + return concrete_ptr(const_cast<store_value_type*>(p)); + } + + static value_type* value_ptr(const store_value_type* p)noexcept + { + return const_cast<value_type*>(Model::value_ptr(const_concrete_ptr(p))); + } + + static const store_value_type* const_store_value_type_ptr( + const Concrete* p)noexcept + { + return static_cast<const value_holder<Concrete>*>( + reinterpret_cast<const value_holder_base<Concrete>*>(p)); + } + + /* It would have sufficed if iterator_from returned const_store_iterator + * except for the fact that some old versions of libstdc++ claiming to be + * C++11 compliant do not however provide std::vector modifier ops taking + * const_iterator's. + */ + + store_iterator iterator_from(const_base_iterator p) + { + return iterator_from(static_cast<const_iterator>(p)); + } + + store_iterator iterator_from(const_iterator p) + { + return s.begin()+(const_store_value_type_ptr(p)-s.data()); + } + + base_sentinel sentinel()const noexcept + { + return base_iterator{ + value_ptr(s.data()+s.size()), + sizeof(store_value_type) + }; + } + + range range_from(const_store_iterator it)const + { + return { + {value_ptr(s.data()+(it-s.begin())),sizeof(store_value_type)}, + sentinel() + }; + } + + range range_from(std::size_t n)const + { + return { + {value_ptr(s.data()+n),sizeof(store_value_type)}, + sentinel() + }; + } + + store s; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/poly_collection.hpp b/boost/poly_collection/detail/poly_collection.hpp new file mode 100644 index 0000000000..eebd75ca89 --- /dev/null +++ b/boost/poly_collection/detail/poly_collection.hpp @@ -0,0 +1,1176 @@ +/* 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_DETAIL_POLY_COLLECTION_HPP +#define BOOST_POLY_COLLECTION_DETAIL_POLY_COLLECTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <algorithm> +#include <boost/assert.hpp> +#include <boost/iterator/iterator_adaptor.hpp> +#include <boost/poly_collection/detail/iterator_impl.hpp> +#include <boost/poly_collection/detail/is_acceptable.hpp> +#include <boost/poly_collection/detail/is_constructible.hpp> +#include <boost/poly_collection/detail/is_final.hpp> +#include <boost/poly_collection/detail/newdelete_allocator.hpp> +#include <boost/poly_collection/detail/segment.hpp> +#include <boost/poly_collection/detail/type_info_map.hpp> +#include <boost/poly_collection/exception.hpp> +#include <iterator> +#include <type_traits> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +namespace poly_collection_impl{ + +/* common implementation for all polymorphic collections */ + +template<typename Model,typename Allocator> +class poly_collection +{ + template<typename T> + static const std::type_info& subtypeid(const T& x) + {return Model::subtypeid(x);} + template<typename...> + struct for_all_types{using type=void*;}; + template<typename... T> + using for_all=typename for_all_types<T...>::type; + template<typename T> + struct is_subtype: /* using makes VS2015 choke, hence we derive */ + Model::template is_subtype<typename std::decay<T>::type>{}; + template<typename T> + using enable_if_subtype= + typename std::enable_if<is_subtype<T>::value>::type*; + template<typename T> + using enable_if_not_subtype= + typename std::enable_if<!is_subtype<T>::value>::type*; + template<typename T> + using is_acceptable= + detail::is_acceptable<typename std::decay<T>::type,Model>; + template<typename T> + using enable_if_acceptable= + typename std::enable_if<is_acceptable<T>::value>::type*; + template<typename T> + using enable_if_not_acceptable= + typename std::enable_if<!is_acceptable<T>::value>::type*; + template<typename InputIterator> + using enable_if_derefs_to_subtype=enable_if_subtype< + typename std::iterator_traits<InputIterator>::value_type + >; + template<typename T> + using is_terminal= + typename Model::template is_terminal<typename std::decay<T>::type>; + template<typename T> + using enable_if_terminal= + typename std::enable_if<is_terminal<T>::value>::type*; + template<typename T> + using enable_if_not_terminal= + typename std::enable_if<!is_terminal<T>::value>::type*; + template<typename InputIterator> + using derefs_to_terminal=is_terminal< + typename std::iterator_traits<InputIterator>::value_type + >; + template<typename InputIterator> + using enable_if_derefs_to_terminal= + typename std::enable_if<derefs_to_terminal<InputIterator>::value>::type*; + template<typename InputIterator> + using enable_if_derefs_to_not_terminal= + typename std::enable_if<!derefs_to_terminal<InputIterator>::value>::type*; + template<typename T,typename U> + using enable_if_not_same=typename std::enable_if< + !std::is_same< + typename std::decay<T>::type,typename std::decay<U>::type + >::value + >::type*; + template<typename T,typename U> + using enable_if_constructible= + typename std::enable_if<is_constructible<T,U>::value>::type*; + template<typename T,typename U> + using enable_if_not_constructible= + typename std::enable_if<!is_constructible<T,U>::value>::type*; + + using segment_type=detail::segment<Model,Allocator>; + using segment_base_iterator=typename segment_type::base_iterator; + using const_segment_base_iterator= + typename segment_type::const_base_iterator; + using segment_base_sentinel=typename segment_type::base_sentinel; + using const_segment_base_sentinel= + typename segment_type::const_base_sentinel; + template<typename T> + using segment_iterator=typename segment_type::template iterator<T>; + template<typename T> + using const_segment_iterator= + typename segment_type::template const_iterator<T>; + using segment_map=type_info_map< + segment_type, + newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>::template + rebind_alloc<segment_type> + > + >; + using segment_map_allocator_type=typename segment_map::allocator_type; + using segment_map_iterator=typename segment_map::iterator; + using const_segment_map_iterator=typename segment_map::const_iterator; + +public: + /* types */ + + using value_type=typename segment_type::value_type; + using allocator_type=Allocator; + using size_type=std::size_t; + using difference_type=std::ptrdiff_t; + using reference=value_type&; + using const_reference=const value_type&; + using pointer=typename std::allocator_traits<Allocator>::pointer; + using const_pointer=typename std::allocator_traits<Allocator>::const_pointer; + +private: + template<typename,bool> + friend class detail::iterator_impl; + template<typename,typename> + friend class detail::local_iterator_impl; + template<bool Const> + using iterator_impl=detail::iterator_impl<poly_collection,Const>; + template<typename BaseIterator> + using local_iterator_impl= + detail::local_iterator_impl<poly_collection,BaseIterator>; + +public: + using iterator=iterator_impl<false>; + using const_iterator=iterator_impl<true>; + using local_base_iterator=local_iterator_impl<segment_base_iterator>; + using const_local_base_iterator= + local_iterator_impl<const_segment_base_iterator>; + template<typename T> + using local_iterator=local_iterator_impl<segment_iterator<T>>; + template<typename T> + using const_local_iterator=local_iterator_impl<const_segment_iterator<T>>; + + class const_base_segment_info + { + public: + const_base_segment_info(const const_base_segment_info&)=default; + const_base_segment_info& operator=(const const_base_segment_info&)=default; + + const_local_base_iterator begin()const noexcept + {return {it,it->second.begin()};} + const_local_base_iterator end()const noexcept + {return {it,it->second.end()};} + const_local_base_iterator cbegin()const noexcept{return begin();} + const_local_base_iterator cend()const noexcept{return end();} + + template<typename T> + const_local_iterator<T> begin()const noexcept + {return const_local_iterator<T>{begin()};} + template<typename T> + const_local_iterator<T> end()const noexcept + {return const_local_iterator<T>{end()};} + template<typename T> + const_local_iterator<T> cbegin()const noexcept{return begin<T>();} + template<typename T> + const_local_iterator<T> cend()const noexcept{return end<T>();} + + const std::type_info& type_info()const{return *it->first;} + + protected: + friend class poly_collection; + + const_base_segment_info(const_segment_map_iterator it)noexcept:it{it}{} + + const_segment_map_iterator it; + }; + + class base_segment_info:public const_base_segment_info + { + public: + base_segment_info(const base_segment_info&)=default; + base_segment_info& operator=(const base_segment_info&)=default; + + using const_base_segment_info::begin; + using const_base_segment_info::end; + + local_base_iterator begin()noexcept + {return {this->it,this->it->second.begin()};} + local_base_iterator end()noexcept + {return {this->it,this->it->second.end()};} + + template<typename T> + local_iterator<T> begin()noexcept{return local_iterator<T>{begin()};} + template<typename T> + local_iterator<T> end()noexcept{return local_iterator<T>{end()};} + + private: + friend class poly_collection; + + using const_base_segment_info::const_base_segment_info; + }; + + template<typename T> + class const_segment_info + { + public: + const_segment_info(const const_segment_info&)=default; + const_segment_info& operator=(const const_segment_info&)=default; + + const_local_iterator<T> begin()const noexcept + {return {it,it->second.begin()};} + const_local_iterator<T> end()const noexcept + {return {it,it->second.end()};} + const_local_iterator<T> cbegin()const noexcept{return begin();} + const_local_iterator<T> cend()const noexcept{return end();} + + protected: + friend class poly_collection; + + const_segment_info(const_segment_map_iterator it)noexcept:it{it}{} + + const_segment_map_iterator it; + }; + + template<typename T> + class segment_info:public const_segment_info<T> + { + public: + segment_info(const segment_info&)=default; + segment_info& operator=(const segment_info&)=default; + + using const_segment_info<T>::begin; + using const_segment_info<T>::end; + + local_iterator<T> begin()noexcept + {return {this->it,this->it->second.begin()};} + local_iterator<T> end()noexcept + {return {this->it,this->it->second.end()};} + + private: + friend class poly_collection; + + using const_segment_info<T>::const_segment_info; + }; + +private: + template<typename SegmentInfo> + class segment_info_iterator_impl: + public boost::iterator_adaptor< + segment_info_iterator_impl<SegmentInfo>, + const_segment_map_iterator, + SegmentInfo, + std::input_iterator_tag, + SegmentInfo + > + { + segment_info_iterator_impl(const_segment_map_iterator it): + segment_info_iterator_impl::iterator_adaptor_{it}{} + + public: + segment_info_iterator_impl()=default; + segment_info_iterator_impl(const segment_info_iterator_impl&)=default; + segment_info_iterator_impl& operator=( + const segment_info_iterator_impl&)=default; + + template< + typename SegmentInfo2, + typename std::enable_if< + std::is_base_of<SegmentInfo,SegmentInfo2>::value + >::type* =nullptr + > + segment_info_iterator_impl( + const segment_info_iterator_impl<SegmentInfo2>& x): + segment_info_iterator_impl::iterator_adaptor_{x.base()}{} + + template< + typename SegmentInfo2, + typename std::enable_if< + std::is_base_of<SegmentInfo,SegmentInfo2>::value + >::type* =nullptr + > + segment_info_iterator_impl& operator=( + const segment_info_iterator_impl<SegmentInfo2>& x) + { + this->base_reference()=x.base(); + return *this; + } + + private: + template<typename> + friend class segment_info_iterator_impl; + friend class poly_collection; + friend class boost::iterator_core_access; + template<typename> + friend struct detail::iterator_traits; + + SegmentInfo dereference()const noexcept{return this->base();} + }; + +public: + using base_segment_info_iterator= + segment_info_iterator_impl<base_segment_info>; + using const_base_segment_info_iterator= + segment_info_iterator_impl<const_base_segment_info>; + +private: + template<typename Iterator> + static Iterator nonconst_hlp(Iterator); + static iterator nonconst_hlp(const_iterator); + static local_base_iterator nonconst_hlp(const_local_base_iterator); + template<typename T> + static local_iterator<T> nonconst_hlp(const_local_iterator<T>); + static base_segment_info_iterator nonconst_hlp( + const_base_segment_info_iterator); + + template<typename Iterator> + using nonconst_version=decltype(nonconst_hlp(std::declval<Iterator>())); + +public: + class const_segment_traversal_info + { + public: + const_segment_traversal_info(const const_segment_traversal_info&)=default; + const_segment_traversal_info& operator=( + const const_segment_traversal_info&)=default; + + const_base_segment_info_iterator begin()const noexcept + {return pmap->cbegin();} + const_base_segment_info_iterator end()const noexcept{return pmap->cend();} + const_base_segment_info_iterator cbegin()const noexcept{return begin();} + const_base_segment_info_iterator cend()const noexcept{return end();} + + protected: + friend class poly_collection; + + const_segment_traversal_info(const segment_map& map)noexcept: + pmap{const_cast<segment_map*>(&map)}{} + + segment_map* pmap; + }; + + class segment_traversal_info:public const_segment_traversal_info + { + public: + segment_traversal_info(const segment_traversal_info&)=default; + segment_traversal_info& operator=(const segment_traversal_info&)=default; + + using const_segment_traversal_info::begin; + using const_segment_traversal_info::end; + + base_segment_info_iterator begin()noexcept{return this->pmap->cbegin();} + base_segment_info_iterator end()noexcept{return this->pmap->cend();} + + private: + friend class poly_collection; + + using const_segment_traversal_info::const_segment_traversal_info; + }; + + /* construct/destroy/copy */ + + poly_collection()=default; + poly_collection(const poly_collection&)=default; + poly_collection(poly_collection&&)=default; + explicit poly_collection(const allocator_type& al): + map{segment_map_allocator_type{al}}{} + poly_collection(const poly_collection& x,const allocator_type& al): + map{x.map,segment_map_allocator_type{al}}{} + poly_collection(poly_collection&& x,const allocator_type& al): + map{std::move(x.map),segment_map_allocator_type{al}}{} + + template<typename InputIterator> + poly_collection( + InputIterator first,InputIterator last, + const allocator_type& al=allocator_type{}): + map{segment_map_allocator_type{al}} + { + this->insert(first,last); + } + + // TODO: what to do with initializer_list? + + poly_collection& operator=(const poly_collection&)=default; + poly_collection& operator=(poly_collection&&)=default; + + allocator_type get_allocator()const noexcept{return map.get_allocator();} + + /* type registration */ + + template< + typename... T, + for_all<enable_if_acceptable<T>...> =nullptr + > + void register_types() + { + /* http://twitter.com/SeanParent/status/558765089294020609 */ + + using seq=int[1+sizeof...(T)]; + (void)seq{ + 0, + (map.insert( + typeid(T),segment_type::template make<T>(get_allocator())),0)... + }; + } + + bool is_registered(const std::type_info& info)const + { + return map.find(info)!=map.end(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + bool is_registered()const + { + return is_registered(typeid(T)); + } + + /* iterators */ + + iterator begin()noexcept{return {map.begin(),map.end()};} + iterator end()noexcept{return {map.end(),map.end()};} + const_iterator begin()const noexcept{return {map.begin(),map.end()};} + const_iterator end()const noexcept{return {map.end(),map.end()};} + const_iterator cbegin()const noexcept{return begin();} + const_iterator cend()const noexcept{return end();} + + local_base_iterator begin(const std::type_info& info) + { + auto it=get_map_iterator_for(info); + return {it,segment(it).begin()}; + } + + local_base_iterator end(const std::type_info& info) + { + auto it=get_map_iterator_for(info); + return {it,segment(it).end()}; + } + + const_local_base_iterator begin(const std::type_info& info)const + { + auto it=get_map_iterator_for(info); + return {it,segment(it).begin()}; + } + + const_local_base_iterator end(const std::type_info& info)const + { + auto it=get_map_iterator_for(info); + return {it,segment(it).end()}; + } + + const_local_base_iterator cbegin(const std::type_info& info)const + {return begin(info);} + const_local_base_iterator cend(const std::type_info& info)const + {return end(info);} + + template<typename T,enable_if_acceptable<T> =nullptr> + local_iterator<T> begin() + { + auto it=get_map_iterator_for(typeid(T)); + return {it,segment(it).template begin<T>()}; + } + + template<typename T,enable_if_acceptable<T> =nullptr> + local_iterator<T> end() + { + auto it=get_map_iterator_for(typeid(T)); + return {it,segment(it).template end<T>()}; + } + + template<typename T,enable_if_acceptable<T> =nullptr> + const_local_iterator<T> begin()const + { + auto it=get_map_iterator_for(typeid(T)); + return {it,segment(it).template begin<T>()}; + } + + template<typename T,enable_if_acceptable<T> =nullptr> + const_local_iterator<T> end()const + { + auto it=get_map_iterator_for(typeid(T)); + return {it,segment(it).template end<T>()}; + } + + template<typename T,enable_if_acceptable<T> =nullptr> + const_local_iterator<T> cbegin()const{return begin<T>();} + + template<typename T,enable_if_acceptable<T> =nullptr> + const_local_iterator<T> cend()const{return end<T>();} + + base_segment_info segment(const std::type_info& info) + { + return get_map_iterator_for(info); + } + + const_base_segment_info segment(const std::type_info& info)const + { + return get_map_iterator_for(info); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + segment_info<T> segment(){return get_map_iterator_for(typeid(T));} + + template<typename T,enable_if_acceptable<T> =nullptr> + const_segment_info<T> segment()const{return get_map_iterator_for(typeid(T));} + + segment_traversal_info segment_traversal()noexcept{return map;} + const_segment_traversal_info segment_traversal()const noexcept{return map;} + + /* capacity */ + + bool empty()const noexcept + { + for(const auto& x:map)if(!x.second.empty())return false; + return true; + } + + bool empty(const std::type_info& info)const + { + return segment(get_map_iterator_for(info)).empty(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + bool empty()const + { + return segment(get_map_iterator_for(typeid(T))).template empty<T>(); + } + + size_type size()const noexcept + { + size_type res=0; + for(const auto& x:map)res+=x.second.size(); + return res; + } + + size_type size(const std::type_info& info)const + { + return segment(get_map_iterator_for(info)).size(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + size_type size()const + { + return segment(get_map_iterator_for(typeid(T))).template size<T>(); + } + + size_type max_size(const std::type_info& info)const + { + return segment(get_map_iterator_for(info)).max_size(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + size_type max_size()const + { + return segment(get_map_iterator_for(typeid(T))).template max_size<T>(); + } + + size_type capacity(const std::type_info& info)const + { + return segment(get_map_iterator_for(info)).capacity(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + size_type capacity()const + { + return segment(get_map_iterator_for(typeid(T))).template capacity<T>(); + } + + void reserve(size_type n) + { + for(auto& x:map)x.second.reserve(n); + } + + void reserve(const std::type_info& info,size_type n) + { + segment(get_map_iterator_for(info)).reserve(n); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + void reserve(size_type n) + { + /* note this creates the segment if it didn't previously exist */ + + segment(get_map_iterator_for<T>()).template reserve<T>(n); + } + + void shrink_to_fit() + { + for(auto& x:map)x.second.shrink_to_fit(); + } + + void shrink_to_fit(const std::type_info& info) + { + segment(get_map_iterator_for(info)).shrink_to_fit(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + void shrink_to_fit() + { + segment(get_map_iterator_for(typeid(T))).template shrink_to_fit<T>(); + } + + /* modifiers */ + + template<typename T,typename... Args,enable_if_acceptable<T> =nullptr> + iterator emplace(Args&&... args) + { + auto it=get_map_iterator_for<T>(); + return { + it,map.end(), + segment(it).template emplace_back<T>(std::forward<Args>(args)...) + }; + } + + template<typename T,typename... Args,enable_if_acceptable<T> =nullptr> + iterator emplace_hint(const_iterator hint,Args&&... args) + { + auto it=get_map_iterator_for<T>(); + return { + it,map.end(), + hint.mapit==it? /* hint in segment */ + segment(it).template emplace<T>( + hint.segpos,std::forward<Args>(args)...): + segment(it).template emplace_back<T>(std::forward<Args>(args)...) + }; + } + + template<typename T,typename... Args,enable_if_acceptable<T> =nullptr> + local_base_iterator + emplace_pos(local_base_iterator pos,Args&&... args) + { + return emplace_pos<T>( + const_local_base_iterator{pos},std::forward<Args>(args)...); + } + + template<typename T,typename... Args,enable_if_acceptable<T> =nullptr> + local_base_iterator + emplace_pos(const_local_base_iterator pos,Args&&... args) + { + BOOST_ASSERT(pos.type_info()==typeid(T)); + return { + pos.mapit, + pos.segment().template emplace<T>(pos.base(),std::forward<Args>(args)...) + }; + } + + template<typename T,typename... Args> + local_iterator<T> + emplace_pos(local_iterator<T> pos,Args&&... args) + { + return emplace_pos( + const_local_iterator<T>{pos},std::forward<Args>(args)...); + } + + template<typename T,typename... Args> + local_iterator<T> + emplace_pos(const_local_iterator<T> pos,Args&&... args) + { + return { + pos.mapit, + pos.segment().template emplace<T>(pos.base(),std::forward<Args>(args)...) + }; + } + + template<typename T,enable_if_subtype<T> =nullptr> + iterator insert(T&& x) + { + auto it=get_map_iterator_for(x); + return {it,map.end(),push_back(segment(it),std::forward<T>(x))}; + } + + template< + typename T, + enable_if_not_same<const_iterator,T> =nullptr, + enable_if_subtype<T> =nullptr + > + iterator insert(const_iterator hint,T&& x) + { + auto it=get_map_iterator_for(x); + return { + it,map.end(), + hint.mapit==it? /* hint in segment */ + segment(it).insert(hint.segpos,std::forward<T>(x)): + push_back(segment(it),std::forward<T>(x)) + }; + } + + template< + typename BaseIterator,typename T, + enable_if_not_same<local_iterator_impl<BaseIterator>,T> =nullptr, + enable_if_subtype<T> =nullptr + > + nonconst_version<local_iterator_impl<BaseIterator>> + insert(local_iterator_impl<BaseIterator> pos,T&& x) + { + BOOST_ASSERT(pos.type_info()==subtypeid(x)); + return { + pos.mapit, + pos.segment().insert(pos.base(),std::forward<T>(x)) + }; + } + + template< + typename InputIterator, + enable_if_derefs_to_subtype<InputIterator> =nullptr, + enable_if_derefs_to_not_terminal<InputIterator> =nullptr + > + void insert(InputIterator first,InputIterator last) + { + for(;first!=last;++first)insert(*first); + } + + template< + typename InputIterator, + enable_if_derefs_to_subtype<InputIterator> =nullptr, + enable_if_derefs_to_terminal<InputIterator> =nullptr + > + void insert(InputIterator first,InputIterator last) + { + if(first==last)return; + + /* same segment for all (type is terminal) */ + + auto& seg=segment(get_map_iterator_for(*first)); + seg.insert(first,last); + } + + template<bool Const> + void insert(iterator_impl<Const> first,iterator_impl<Const> last) + { + for(;first!=last;++first){ + auto& seg=segment(get_map_iterator_for(*first,first.segment())); + push_back(seg,*first); + } + } + + template<typename BaseIterator> + void insert( + local_iterator_impl<BaseIterator> first, + local_iterator_impl<BaseIterator> last) + { + if(first==last)return; + + /* same segment for all (iterator is local) */ + + auto& seg=segment(get_map_iterator_for(*first,first.segment())); + do seg.push_back(*first); while(++first!=last); + } + + template< + typename InputIterator, + enable_if_derefs_to_subtype<InputIterator> =nullptr, + enable_if_derefs_to_not_terminal<InputIterator> =nullptr + > + void insert(const_iterator hint,InputIterator first,InputIterator last) + { + for(;first!=last;++first){ + auto it=get_map_iterator_for(*first); + if(hint.mapit==it){ /* hint in segment */ + hint={it,map.end(),segment(it).insert(hint.segpos,*first)}; + ++hint; + } + else push_back(segment(it),*first); + } + } + + template< + typename InputIterator, + enable_if_derefs_to_subtype<InputIterator> =nullptr, + enable_if_derefs_to_terminal<InputIterator> =nullptr + > + void insert(const_iterator hint,InputIterator first,InputIterator last) + { + if(first==last)return; + + /* same segment for all (type is terminal) */ + + auto it=get_map_iterator_for(*first); + auto& seg=segment(it); + if(hint.mapit==it)seg.insert(hint.segpos,first,last); /* hint in segment */ + else seg.insert(first,last); + } + + template<bool Const> + void insert( + const_iterator hint,iterator_impl<Const> first,iterator_impl<Const> last) + { + for(;first!=last;++first){ + auto it=get_map_iterator_for(*first,first.segment()); + if(hint.mapit==it){ /* hint in segment */ + hint={it,map.end(),segment(it).insert(hint.segpos,*first)}; + ++hint; + } + else push_back(segment(it),*first); + } + } + + template<typename BaseIterator> + void insert( + const_iterator hint, + local_iterator_impl<BaseIterator> first, + local_iterator_impl<BaseIterator> last) + { + if(first==last)return; + + /* same segment for all (iterator is local) */ + + auto it=get_map_iterator_for(*first,first.segment()); + auto& seg=segment(it); + if(hint.mapit==it){ /* hint in segment */ + do{ + hint={it,map.end(),seg.insert(hint.segpos,*first)}; + ++hint; + }while(++first!=last); + } + else{ + do push_back(seg,*first); while(++first!=last); + } + } + + template< + typename InputIterator, + enable_if_derefs_to_subtype<InputIterator> =nullptr + > + local_base_iterator insert( + const_local_base_iterator pos,InputIterator first,InputIterator last) + { + auto& seg=pos.segment(); + auto it=Model::nonconst_iterator(pos.base()); + size_type n=0; + + for(;first!=last;++first){ + BOOST_ASSERT(pos.type_info()==subtypeid(*first)); + it=std::next(seg.insert(it,*first)); + ++n; + } + return {pos.mapit,it-n}; + } + + template<typename T,typename InputIterator> + local_iterator<T> insert( + const_local_iterator<T> pos,InputIterator first,InputIterator last) + { + auto& seg=pos.segment(); + segment_iterator<T> it=Model::nonconst_iterator(pos.base()); + size_type n=0; + + for(;first!=last;++first){ + it=std::next( + static_cast<segment_iterator<T>>(local_insert<T>(seg,it,*first))); + ++n; + } + return {pos.mapit,it-n}; + } + + template<typename T,typename InputIterator> + local_iterator<T> insert( + local_iterator<T> pos,InputIterator first,InputIterator last) + { + return insert(const_local_iterator<T>{pos},first,last); + } + + iterator erase(const_iterator pos) + { + return {pos.mapit,pos.mapend,pos.segment().erase(pos.segpos)}; + } + + template<typename BaseIterator> + nonconst_version<local_iterator_impl<BaseIterator>> + erase(local_iterator_impl<BaseIterator> pos) + { + return {pos.mapit,pos.segment().erase(pos.base())}; + } + + iterator erase(const_iterator first, const_iterator last) + { + const_segment_map_iterator fseg=first.mapit, + lseg=last.mapit, + end=first.mapend; + + if(fseg!=lseg){ /* [first,last] spans over more than one segment */ + /* from 1st elem to end of 1st segment */ + + segment(fseg).erase_till_end(first.segpos); + + /* entire segments till last one */ + + while(++fseg!=lseg)segment(fseg).clear(); + + /* remaining elements of last segment */ + + if(fseg==end){ /* except if at end of container */ + return {end,end}; + } + else{ + return {fseg,end,segment(fseg).erase_from_begin(last.segpos)}; + } + } + else{ /* range is included in one segment only */ + if(first==last){ /* to avoid segment(fseg) when fseg==end */ + return {fseg,end,first.segpos}; + } + else{ + return {fseg,end,segment(fseg).erase(first.segpos,last.segpos)}; + } + } + } + + template<typename BaseIterator> + nonconst_version<local_iterator_impl<BaseIterator>> + erase( + local_iterator_impl<BaseIterator> first, + local_iterator_impl<BaseIterator> last) + { + BOOST_ASSERT(first.mapit==last.mapit); + return{ + first.mapit, + first.segment().erase(first.base(),last.base()) + }; + } + + void clear()noexcept + { + for(auto& x:map)x.second.clear(); + } + + void clear(const std::type_info& info) + { + segment(get_map_iterator_for(info)).clear(); + } + + template<typename T,enable_if_acceptable<T> =nullptr> + void clear() + { + segment(get_map_iterator_for(typeid(T))).template clear<T>(); + } + + void swap(poly_collection& x){map.swap(x.map);} + +private: + template<typename M,typename A> + friend bool operator==( + const poly_collection<M,A>&,const poly_collection<M,A>&); + + template< + typename T, + enable_if_acceptable<T> =nullptr, + enable_if_not_terminal<T> =nullptr + > + const_segment_map_iterator get_map_iterator_for(const T& x) + { + const auto& id=subtypeid(x); + auto it=map.find(id); + if(it!=map.end())return it; + else if(id!=typeid(T))throw unregistered_type{id}; + else return map.insert( + typeid(T),segment_type::template make<T>(get_allocator())).first; + } + + template< + typename T, + enable_if_acceptable<T> =nullptr, + enable_if_terminal<T> =nullptr + > + const_segment_map_iterator get_map_iterator_for(const T&) + { + auto it=map.find(typeid(T)); + if(it!=map.end())return it; + else return map.insert( + typeid(T),segment_type::template make<T>(get_allocator())).first; + } + + template< + typename T, + enable_if_not_acceptable<T> =nullptr, + enable_if_not_terminal<T> =nullptr + > + const_segment_map_iterator get_map_iterator_for(const T& x)const + { + const auto& id=subtypeid(x); + auto it=map.find(id); + if(it!=map.end())return it; + else throw unregistered_type{id}; + } + + template< + typename T, + enable_if_not_acceptable<T> =nullptr, + enable_if_terminal<T> =nullptr + > + const_segment_map_iterator get_map_iterator_for(const T&)const + { + static_assert( + is_acceptable<T>::value, + "type must be move constructible and move assignable"); + return {}; /* never executed */ + } + + template<typename T> + const_segment_map_iterator get_map_iterator_for( + const T& x,const segment_type& seg) + { + const auto& id=subtypeid(x); + auto it=map.find(id); + if(it!=map.end())return it; + else return map.insert(id,segment_type::make_from_prototype(seg)).first; + } + + template<typename T> + const_segment_map_iterator get_map_iterator_for() + { + auto it=map.find(typeid(T)); + if(it!=map.end())return it; + else return map.insert( + typeid(T),segment_type::template make<T>(get_allocator())).first; + } + + const_segment_map_iterator get_map_iterator_for(const std::type_info& info) + { + return const_cast<const poly_collection*>(this)-> + get_map_iterator_for(info); + } + + const_segment_map_iterator get_map_iterator_for( + const std::type_info& info)const + { + auto it=map.find(info); + if(it!=map.end())return it; + else throw unregistered_type{info}; + } + + static segment_type& segment(const_segment_map_iterator pos) + { + return const_cast<segment_type&>(pos->second); + } + + template< + typename T, + enable_if_not_acceptable<T> =nullptr + > + segment_base_iterator push_back(segment_type& seg,T&& x) + { + return seg.push_back(std::forward<T>(x)); + } + + template< + typename T, + enable_if_acceptable<T> =nullptr, + enable_if_not_terminal<T> =nullptr + > + segment_base_iterator push_back(segment_type& seg,T&& x) + { + return subtypeid(x)==typeid(T)? + seg.push_back_terminal(std::forward<T>(x)): + seg.push_back(std::forward<T>(x)); + } + + template< + typename T, + enable_if_acceptable<T> =nullptr, + enable_if_terminal<T> =nullptr + > + segment_base_iterator push_back(segment_type& seg,T&& x) + { + return seg.push_back_terminal(std::forward<T>(x)); + } + + template< + typename T,typename BaseIterator,typename U, + enable_if_subtype<U> =nullptr, + enable_if_not_constructible<T,U&&> =nullptr + > + static segment_base_iterator local_insert( + segment_type& seg,BaseIterator pos,U&& x) + { + BOOST_ASSERT(subtypeid(x)==typeid(T)); + return seg.insert(pos,std::forward<U>(x)); + } + + template< + typename T,typename BaseIterator,typename U, + enable_if_subtype<U> =nullptr, + enable_if_constructible<T,U&&> =nullptr + > + static segment_base_iterator local_insert( + segment_type& seg,BaseIterator pos,U&& x) + { + if(subtypeid(x)==typeid(T))return seg.insert(pos,std::forward<U>(x)); + else return seg.template emplace<T>(pos,std::forward<U>(x)); + } + + template< + typename T,typename BaseIterator,typename U, + enable_if_not_subtype<U> =nullptr, + enable_if_constructible<T,U&&> =nullptr + > + static segment_base_iterator local_insert( + segment_type& seg,BaseIterator pos,U&& x) + { + return seg.template emplace<T>(pos,std::forward<U>(x)); + } + + template< + typename T,typename BaseIterator,typename U, + enable_if_not_subtype<U> =nullptr, + enable_if_not_constructible<T,U&&> =nullptr + > + static segment_base_iterator local_insert( + segment_type&,BaseIterator,U&&) + { + static_assert( + is_constructible<T,U&&>::value, + "element must be constructible from type"); + return {}; /* never executed */ + } + + segment_map map; +}; + +template<typename Model,typename Allocator> +bool operator==( + const poly_collection<Model,Allocator>& x, + const poly_collection<Model,Allocator>& y) +{ + typename poly_collection<Model,Allocator>::size_type s=0; + const auto &mapx=x.map,&mapy=y.map; + for(const auto& p:mapx){ + auto ss=p.second.size(); + auto it=mapy.find(*p.first); + if(it==mapy.end()?ss!=0:p.second!=it->second)return false; + s+=ss; + } + return s==y.size(); +} + +template<typename Model,typename Allocator> +bool operator!=( + const poly_collection<Model,Allocator>& x, + const poly_collection<Model,Allocator>& y) +{ + return !(x==y); +} + +template<typename Model,typename Allocator> +void swap( + poly_collection<Model,Allocator>& x,poly_collection<Model,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace poly_collection::detail::poly_collection_impl */ + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/segment.hpp b/boost/poly_collection/detail/segment.hpp new file mode 100644 index 0000000000..52aa4d4a66 --- /dev/null +++ b/boost/poly_collection/detail/segment.hpp @@ -0,0 +1,296 @@ +/* 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_DETAIL_SEGMENT_HPP +#define BOOST_POLY_COLLECTION_DETAIL_SEGMENT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <iterator> +#include <memory> +#include <type_traits> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* segment<Model,Allocator> encapsulates implementations of + * Model::segment_backend virtual interface under a value-semantics type for + * use by poly_collection. The techique is described by Sean Parent at slides + * 157-205 of + * https://github.com/sean-parent/sean-parent.github.com/wiki/ + * presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf + * with one twist: when the type of the implementation can be known at compile + * time, a downcast is done and non-virtual member functions (named with a nv_ + * prefix) are used: this increases the performance of some operations. + */ + +template<typename Model,typename Allocator> +class segment +{ +public: + using value_type=typename Model::value_type; + using base_iterator=typename Model::base_iterator; + using const_base_iterator=typename Model::const_base_iterator; + using base_sentinel=typename Model::base_sentinel; + using const_base_sentinel=typename Model::const_base_sentinel; + template<typename T> + using iterator=typename Model::template iterator<T>; + template<typename T> + using const_iterator=typename Model::template const_iterator<T>; + + template<typename T> + static segment make(const Allocator& al) + { + return Model::template make<T>(al); + } + + /* clones the implementation of x with no elements */ + + static segment make_from_prototype(const segment& x) + { + return {from_prototype{},x}; + } + + segment(const segment& x):pimpl{x.impl().copy()}{set_sentinel();} + segment(segment&& x)=default; + segment& operator=(segment x) // TODO: Why do we need this? + { + pimpl=std::move(x.pimpl); + snt=x.snt; + return *this; + } + + friend bool operator==(const segment& x,const segment& y) + { + if(typeid(*(x.pimpl))!=typeid(*(y.pimpl)))return false; + else return x.impl().equal(y.impl()); + } + + friend bool operator!=(const segment& x,const segment& y){return !(x==y);} + + base_iterator begin()const noexcept{return impl().begin();} + template<typename U> + base_iterator begin()const noexcept{return impl<U>().nv_begin();} + base_iterator end()const noexcept{return impl().end();} + template<typename U> + base_iterator end()const noexcept{return impl<U>().nv_end();} + base_sentinel sentinel()const noexcept{return snt;} + bool empty()const noexcept{return impl().empty();} + template<typename U> + bool empty()const noexcept{return impl<U>().nv_empty();} + std::size_t size()const noexcept{return impl().size();} + template<typename U> + std::size_t size()const noexcept{return impl<U>().nv_size();} + std::size_t max_size()const noexcept{return impl().max_size();} + template<typename U> + std::size_t max_size()const noexcept + {return impl<U>().nv_max_size();} + void reserve(std::size_t n){filter(impl().reserve(n));} + template<typename U> + void reserve(std::size_t n){filter(impl<U>().nv_reserve(n));} + std::size_t capacity()const noexcept{return impl().capacity();} + template<typename U> + std::size_t capacity()const noexcept + {return impl<U>().nv_capacity();} + void shrink_to_fit(){filter(impl().shrink_to_fit());} + template<typename U> + void shrink_to_fit(){filter(impl<U>().nv_shrink_to_fit());} + + template<typename U,typename Iterator,typename... Args> + base_iterator emplace(Iterator it,Args&&... args) + { + return filter(impl<U>().nv_emplace(it,std::forward<Args>(args)...)); + } + + template<typename U,typename... Args> + base_iterator emplace_back(Args&&... args) + { + return filter(impl<U>().nv_emplace_back(std::forward<Args>(args)...)); + } + + template<typename T> + base_iterator push_back(const T& x) + { + return filter(impl().push_back(subaddress(x))); + } + + template< + typename T, + typename std::enable_if< + !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value + >::type* =nullptr + > + base_iterator push_back(T&& x) + { + return filter(impl().push_back_move(subaddress(x))); + } + + template<typename U> + base_iterator push_back_terminal(U&& x) + { + return filter( + impl<typename std::decay<U>::type>().nv_push_back(std::forward<U>(x))); + } + + template<typename T> + base_iterator insert(const_base_iterator it,const T& x) + { + return filter(impl().insert(it,subaddress(x))); + } + + template<typename U,typename T> + base_iterator insert(const_iterator<U> it,const T& x) + { + return filter( + impl<U>().nv_insert(it,*static_cast<const U*>(subaddress(x)))); + } + + template< + typename T, + typename std::enable_if< + !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value + >::type* =nullptr + > + base_iterator insert(const_base_iterator it,T&& x) + { + return filter(impl().insert_move(it,subaddress(x))); + } + + template< + typename U,typename T, + typename std::enable_if< + !std::is_lvalue_reference<T>::value&&!std::is_const<T>::value + >::type* =nullptr + > + base_iterator insert(const_iterator<U> it,T&& x) + { + return filter( + impl<U>().nv_insert(it,std::move(*static_cast<U*>(subaddress(x))))); + } + + template<typename InputIterator> + base_iterator insert(InputIterator first,InputIterator last) + { + return filter( + impl<typename std::iterator_traits<InputIterator>::value_type>(). + nv_insert(first,last)); + } + + template<typename InputIterator> + base_iterator insert( + const_base_iterator it,InputIterator first,InputIterator last) + { + return insert( + const_iterator< + typename std::iterator_traits<InputIterator>::value_type>(it), + first,last); + } + + template<typename U,typename InputIterator> + base_iterator insert( + const_iterator<U> it,InputIterator first,InputIterator last) + { + return filter(impl<U>().nv_insert(it,first,last)); + } + + base_iterator erase(const_base_iterator it) + { + return filter(impl().erase(it)); + } + + template<typename U> + base_iterator erase(const_iterator<U> it) + { + return filter(impl<U>().nv_erase(it)); + } + + base_iterator erase(const_base_iterator f,const_base_iterator l) + { + return filter(impl().erase(f,l)); + } + + template<typename U> + base_iterator erase(const_iterator<U> f,const_iterator<U> l) + { + return filter(impl<U>().nv_erase(f,l)); + } + + template<typename Iterator> + base_iterator erase_till_end(Iterator f) + { + return filter(impl().erase_till_end(f)); + } + + template<typename Iterator> + base_iterator erase_from_begin(Iterator l) + { + return filter(impl().erase_from_begin(l)); + } + + void clear()noexcept{filter(impl().clear());} + template<typename U> + void clear()noexcept{filter(impl<U>().nv_clear());} + +private: + using segment_backend=typename Model::segment_backend; + template<typename Concrete> + using segment_backend_implementation=typename Model:: + template segment_backend_implementation<Concrete,Allocator>; + using segment_backend_unique_ptr= + typename segment_backend::segment_backend_unique_ptr; + using range=typename segment_backend::range; + + struct from_prototype{}; + + segment(segment_backend_unique_ptr&& pimpl): + pimpl{std::move(pimpl)}{set_sentinel();} + segment(from_prototype,const segment& x): + pimpl{x.impl().empty_copy()}{set_sentinel();} + + segment_backend& impl()noexcept{return *pimpl;} + const segment_backend& impl()const noexcept{return *pimpl;} + + template<typename Concrete> + segment_backend_implementation<Concrete>& impl()noexcept + { + return static_cast<segment_backend_implementation<Concrete>&>(impl()); + } + + template<typename Concrete> + const segment_backend_implementation<Concrete>& impl()const noexcept + { + return + static_cast<const segment_backend_implementation<Concrete>&>(impl()); + } + + template<typename T> + static void* subaddress(T& x){return Model::subaddress(x);} + template<typename T> + static const void* subaddress(const T& x){return Model::subaddress(x);} + + void set_sentinel(){filter(impl().end());} + void filter(base_sentinel x){snt=x;} + base_iterator filter(const range& x){snt=x.second;return x.first;} + + segment_backend_unique_ptr pimpl; + base_sentinel snt; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/segment_backend.hpp b/boost/poly_collection/detail/segment_backend.hpp new file mode 100644 index 0000000000..f097ac2edc --- /dev/null +++ b/boost/poly_collection/detail/segment_backend.hpp @@ -0,0 +1,82 @@ +/* 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_DETAIL_SEGMENT_BACKEND_HPP +#define BOOST_POLY_COLLECTION_DETAIL_SEGMENT_BACKEND_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <cstddef> +#include <memory> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* Internal *virtual* interface of segment<Model,Allocator> (please note that + * a non-virtual interface exists accessible thrown downcasting). Member + * functions have been defined to minimize virtual function calls according to + * usage patterns by poly_collection. For instance, ranges are returned rather + * than iterators to allow for caching of and end sentinel at a higher level. + * Passed elements are type erased with [const_]value_pointer. + */ + +template<typename Model> +struct segment_backend +{ + using segment_backend_unique_ptr= + std::unique_ptr<segment_backend,void(*)(segment_backend*)>; + using value_pointer=void*; + using const_value_pointer=const void*; + using base_iterator=typename Model::base_iterator; + using const_base_iterator=typename Model::const_base_iterator; + template<typename T> + using const_iterator=typename Model::template const_iterator<T>; + using base_sentinel=typename Model::base_sentinel; + using range=std::pair<base_iterator,base_sentinel>; + + segment_backend()=default; + segment_backend(const segment_backend&)=delete; + segment_backend& operator=(const segment_backend&)=delete; + + virtual ~segment_backend()=default; + virtual segment_backend_unique_ptr copy()const=0; + virtual segment_backend_unique_ptr empty_copy()const=0; + virtual bool equal(const segment_backend&)const=0; + + virtual base_iterator begin()const noexcept=0; + virtual base_iterator end()const noexcept=0; + virtual bool empty()const noexcept=0; + virtual std::size_t size()const noexcept=0; + virtual std::size_t max_size()const noexcept=0; + virtual std::size_t capacity()const noexcept=0; + virtual base_sentinel reserve(std::size_t)=0; + virtual base_sentinel shrink_to_fit()=0; + virtual range push_back(const_value_pointer)=0; + virtual range push_back_move(value_pointer)=0; + virtual range insert(const_base_iterator,const_value_pointer)=0; + virtual range insert_move(const_base_iterator,value_pointer)=0; + virtual range erase(const_base_iterator)=0; + virtual range erase(const_base_iterator,const_base_iterator)=0; + virtual range erase_till_end(const_base_iterator)=0; + virtual range erase_from_begin(const_base_iterator)=0; + virtual base_sentinel clear()noexcept=0; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/segment_split.hpp b/boost/poly_collection/detail/segment_split.hpp new file mode 100644 index 0000000000..8c8efb19b1 --- /dev/null +++ b/boost/poly_collection/detail/segment_split.hpp @@ -0,0 +1,154 @@ +/* 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_DETAIL_SEGMENT_SPLIT_HPP +#define BOOST_POLY_COLLECTION_DETAIL_SEGMENT_SPLIT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_facade.hpp> +#include <boost/poly_collection/detail/iterator_traits.hpp> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* breakdown of an iterator range into local_base_iterator segments */ + +template<typename PolyCollectionIterator> +class segment_splitter +{ + using traits=iterator_traits<PolyCollectionIterator>; + using local_base_iterator=typename traits::local_base_iterator; + using base_segment_info_iterator=typename traits::base_segment_info_iterator; + +public: + struct info + { + const std::type_info& type_info()const noexcept{return *pinfo_;} + local_base_iterator begin()const noexcept{return begin_;} + local_base_iterator end()const noexcept{return end_;} + + const std::type_info* pinfo_; + local_base_iterator begin_,end_; + }; + + struct iterator:iterator_facade<iterator,info,std::input_iterator_tag,info> + { + iterator()=default; + + private: + friend class segment_splitter; + friend class boost::iterator_core_access; + + iterator( + base_segment_info_iterator it, + const PolyCollectionIterator& first,const PolyCollectionIterator& last): + it{it},first{&first},last{&last}{} + iterator( + const PolyCollectionIterator& first,const PolyCollectionIterator& last): + it{traits::base_segment_info_iterator_from(first)}, + first{&first},last{&last} + {} + + info dereference()const noexcept + { + return { + &it->type_info(), + it==traits::base_segment_info_iterator_from(*first)? + traits::local_base_iterator_from(*first):it->begin(), + it==traits::base_segment_info_iterator_from(*last)? + traits::local_base_iterator_from(*last):it->end() + }; + } + + bool equal(const iterator& x)const noexcept{return it==x.it;} + void increment()noexcept{++it;} + + base_segment_info_iterator it; + const PolyCollectionIterator* first; + const PolyCollectionIterator* last; + }; + + segment_splitter( + const PolyCollectionIterator& first,const PolyCollectionIterator& last): + first{first},last{last}{} + + iterator begin()const noexcept{return {first,last};} + + iterator end()const noexcept + { + auto slast=traits::base_segment_info_iterator_from(last); + if(slast!=traits::end_base_segment_info_iterator_from(last))++slast; + return {slast,last,last}; + } + +private: + const PolyCollectionIterator& first; + const PolyCollectionIterator& last; +}; + +template<typename PolyCollectionIterator> +segment_splitter<PolyCollectionIterator> +segment_split( + const PolyCollectionIterator& first,const PolyCollectionIterator& last) +{ + return {first,last}; +} + +#if 1 +/* equivalent to for(auto i:segment_split(first,last))f(i) */ + +template<typename PolyCollectionIterator,typename F> +void for_each_segment( + const PolyCollectionIterator& first,const PolyCollectionIterator& last,F&& f) +{ + using traits=iterator_traits<PolyCollectionIterator>; + using info=typename segment_splitter<PolyCollectionIterator>::info; + + auto sfirst=traits::base_segment_info_iterator_from(first), + slast=traits::base_segment_info_iterator_from(last), + send=traits::end_base_segment_info_iterator_from(last); + auto lbfirst=traits::local_base_iterator_from(first), + lblast=traits::local_base_iterator_from(last); + + if(sfirst!=slast){ + for(;;){ + f(info{&sfirst->type_info(),lbfirst,sfirst->end()}); + ++sfirst; + if(sfirst==slast)break; + lbfirst=sfirst->begin(); + } + if(sfirst!=send)f(info{&sfirst->type_info(),sfirst->begin(),lblast}); + } + else if(sfirst!=send){ + f(info{&sfirst->type_info(),lbfirst,lblast}); + } +} +#else +template<typename PolyCollectionIterator,typename F> +void for_each_segment( + const PolyCollectionIterator& first,const PolyCollectionIterator& last,F&& f) +{ + for(auto i:segment_split(first,last))f(i); +} +#endif + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/split_segment.hpp b/boost/poly_collection/detail/split_segment.hpp new file mode 100644 index 0000000000..5fc9e11e20 --- /dev/null +++ b/boost/poly_collection/detail/split_segment.hpp @@ -0,0 +1,487 @@ +/* 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_DETAIL_SPLIT_SEGMENT_HPP +#define BOOST_POLY_COLLECTION_DETAIL_SPLIT_SEGMENT_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/newdelete_allocator.hpp> +#include <boost/poly_collection/detail/segment_backend.hpp> +#include <boost/poly_collection/detail/value_holder.hpp> +#include <iterator> +#include <memory> +#include <new> +#include <utility> +#include <vector> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* segment_backend implementation that maintains two internal vectors, one for + * value_type's (the index) and another for the concrete elements those refer + * to (the store). + * + * Requires: + * - [const_]base_iterator is constructible from value_type*. + * - value_type is copy constructible. + * - Model::make_value_type(x) returns a value_type created from a reference + * to the concrete type. + * + * Conversion from base_iterator to local_iterator<Concrete> requires accesing + * value_type internal info, so the end() base_iterator has to be made to point + * to a valid element of index, which implies size(index)=size(store)+1. This + * slightly complicates the memory management. + */ + +template<typename Model,typename Concrete,typename Allocator> +class split_segment:public segment_backend<Model> +{ + using value_type=typename Model::value_type; + using store_value_type=value_holder<Concrete>; + using store=std::vector< + store_value_type, + value_holder_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<store_value_type> + > + >; + using store_iterator=typename store::iterator; + using const_store_iterator=typename store::const_iterator; + using index=std::vector< + value_type, + newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<value_type> + > + >; + using const_index_iterator=typename index::const_iterator; + using segment_backend=detail::segment_backend<Model>; + using typename segment_backend::segment_backend_unique_ptr; + using typename segment_backend::value_pointer; + using typename segment_backend::const_value_pointer; + using typename segment_backend::base_iterator; + using typename segment_backend::const_base_iterator; + using const_iterator= + typename segment_backend::template const_iterator<Concrete>; + using typename segment_backend::base_sentinel; + using typename segment_backend::range; + using segment_allocator_type=newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>:: + template rebind_alloc<split_segment> + >; + +public: + virtual ~split_segment()=default; + + virtual segment_backend_unique_ptr copy()const + { + return new_(s.get_allocator(),store{s}); + } + + virtual segment_backend_unique_ptr empty_copy()const + { + return new_(s.get_allocator(),s.get_allocator()); + } + + virtual bool equal(const segment_backend& x)const + { + return s==static_cast<const split_segment&>(x).s; + } + + virtual base_iterator begin()const noexcept{return nv_begin();} + base_iterator nv_begin()const noexcept + {return base_iterator{value_ptr(i.data())};} + virtual base_iterator end()const noexcept{return nv_end();} + base_iterator nv_end()const noexcept + {return base_iterator{value_ptr(i.data()+s.size())};} + virtual bool empty()const noexcept{return nv_empty();} + bool nv_empty()const noexcept{return s.empty();} + virtual std::size_t size()const noexcept{return nv_size();} + std::size_t nv_size()const noexcept{return s.size();} + virtual std::size_t max_size()const noexcept{return nv_max_size();} + std::size_t nv_max_size()const noexcept{return s.max_size()-1;} + virtual std::size_t capacity()const noexcept{return nv_capacity();} + std::size_t nv_capacity()const noexcept{return s.capacity();} + + virtual base_sentinel reserve(std::size_t n){return nv_reserve(n);} + + base_sentinel nv_reserve(std::size_t n) + { + bool rebuild=n>s.capacity(); + i.reserve(n+1); + s.reserve(n); + if(rebuild)rebuild_index(); + return sentinel(); + }; + + virtual base_sentinel shrink_to_fit(){return nv_shrink_to_fit();} + + base_sentinel nv_shrink_to_fit() + { + auto p=s.data(); + s.shrink_to_fit(); + if(p!=s.data())try{ + index ii{{},i.get_allocator()}; + ii.reserve(s.capacity()+1); + i.swap(ii); + build_index(); + } + catch(...){ + rebuild_index(); + throw; + } + return sentinel(); + } + + template<typename Iterator,typename... Args> + range nv_emplace(Iterator p,Args&&... args) + { + auto q=prereserve(p); + auto it=s.emplace( + iterator_from(q), + value_holder_emplacing_ctor,std::forward<Args>(args)...); + push_index_entry(); + return range_from(it); + } + + template<typename... Args> + range nv_emplace_back(Args&&... args) + { + prereserve(); + s.emplace_back(value_holder_emplacing_ctor,std::forward<Args>(args)...); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range push_back(const_value_pointer x) + {return nv_push_back(const_concrete_ref(x));} + + range nv_push_back(const Concrete& x) + { + prereserve(); + s.emplace_back(x); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range push_back_move(value_pointer x) + {return nv_push_back(std::move(concrete_ref(x)));} + + range nv_push_back(Concrete&& x) + { + prereserve(); + s.emplace_back(std::move(x)); + push_index_entry(); + return range_from(s.size()-1); + } + + virtual range insert(const_base_iterator p,const_value_pointer x) + {return nv_insert(const_iterator(p),const_concrete_ref(x));} + + range nv_insert(const_iterator p,const Concrete& x) + { + p=prereserve(p); + auto it=s.emplace(iterator_from(p),x); + push_index_entry(); + return range_from(it); + } + + virtual range insert_move(const_base_iterator p,value_pointer x) + {return nv_insert(const_iterator(p),std::move(concrete_ref(x)));} + + range nv_insert(const_iterator p,Concrete&& x) + { + p=prereserve(p); + auto it=s.emplace(iterator_from(p),std::move(x)); + push_index_entry(); + return range_from(it); + } + + template<typename InputIterator> + range nv_insert(InputIterator first,InputIterator last) + { + return nv_insert( + const_iterator(concrete_ptr(s.data()+s.size())),first,last); + } + + template<typename InputIterator> + range nv_insert(const_iterator p,InputIterator first,InputIterator last) + { + return insert( + p,first,last, + typename std::iterator_traits<InputIterator>::iterator_category{}); + } + + virtual range erase(const_base_iterator p) + {return nv_erase(const_iterator(p));} + + range nv_erase(const_iterator p) + { + pop_index_entry(); + return range_from(s.erase(iterator_from(p))); + } + + virtual range erase(const_base_iterator first,const_base_iterator last) + {return nv_erase(const_iterator(first),const_iterator(last));} + + range nv_erase(const_iterator first,const_iterator last) + { + std::size_t n=s.size(); + auto it=s.erase(iterator_from(first),iterator_from(last)); + pop_index_entry(n-s.size()); + return range_from(it); + } + + virtual range erase_till_end(const_base_iterator first) + { + std::size_t n=s.size(); + auto it=s.erase(iterator_from(first),s.end()); + pop_index_entry(n-s.size()); + return range_from(it); + } + + virtual range erase_from_begin(const_base_iterator last) + { + std::size_t n=s.size(); + auto it=s.erase(s.begin(),iterator_from(last)); + pop_index_entry(n-s.size()); + return range_from(it); + } + + base_sentinel clear()noexcept{return nv_clear();} + + base_sentinel nv_clear()noexcept + { + s.clear(); + for(std::size_t n=i.size()-1;n--;)i.pop_back(); + return sentinel(); + } + +private: + friend Model; + + template<typename... Args> + static segment_backend_unique_ptr new_( + segment_allocator_type al,Args&&... args) + { + auto p=std::allocator_traits<segment_allocator_type>::allocate(al,1); + try{ + ::new ((void*)p) split_segment{std::forward<Args>(args)...}; + } + catch(...){ + std::allocator_traits<segment_allocator_type>::deallocate(al,p,1); + throw; + } + return {p,&delete_}; + } + + static void delete_(segment_backend* p) + { + auto q=static_cast<split_segment*>(p); + auto al=segment_allocator_type{q->s.get_allocator()}; + q->~split_segment(); + std::allocator_traits<segment_allocator_type>::deallocate(al,q,1); + } + + split_segment(const Allocator& al): + s{typename store::allocator_type{al}}, + i{{},typename index::allocator_type{al}}{build_index();} + split_segment(store&& s_): + s{std::move(s_)},i{{},typename index::allocator_type{s.get_allocator()}} + {build_index();} + + void prereserve() + { + if(s.size()==s.capacity())expand(); + } + + const_base_iterator prereserve(const_base_iterator p) + { + if(s.size()==s.capacity()){ + auto n=p-i.data(); + expand(); + return const_base_iterator{i.data()+n}; + } + else return p; + } + + const_iterator prereserve(const_iterator p) + { + if(s.size()==s.capacity()){ + auto n=p-const_concrete_ptr(s.data()); + expand(); + return const_concrete_ptr(s.data())+n; + } + else return p; + } + + const_iterator prereserve(const_iterator p,std::size_t m) + { + if(s.size()+m>s.capacity()){ + auto n=p-const_concrete_ptr(s.data()); + expand(m); + return const_concrete_ptr(s.data())+n; + } + else return p; + } + + void expand() + { + std::size_t c= + s.size()<=1||(s.max_size()-1-s.size())/2<s.size()? + s.size()+1: + s.size()+s.size()/2; + i.reserve(c+1); + s.reserve(c); + rebuild_index(); + } + + void expand(std::size_t m) + { + i.reserve(s.size()+m+1); + s.reserve(s.size()+m); + rebuild_index(); + } + + void build_index(std::size_t start=0) + { + for(std::size_t n=start,m=s.size();n<=m;++n){ + i.push_back(Model::make_value_type(concrete_ref(s.data()[n]))); + }; + } + + void rebuild_index() + { + i.clear(); + build_index(); + } + + void push_index_entry() + { + build_index(s.size()); + } + + void pop_index_entry(std::size_t n=1) + { + while(n--)i.pop_back(); + } + + static Concrete& concrete_ref(value_pointer p)noexcept + { + return *static_cast<Concrete*>(p); + } + + static Concrete& concrete_ref(store_value_type& r)noexcept + { + return *concrete_ptr(&r); + } + + static const Concrete& const_concrete_ref(const_value_pointer p)noexcept + { + return *static_cast<const Concrete*>(p); + } + + static Concrete* concrete_ptr(store_value_type* p)noexcept + { + return reinterpret_cast<Concrete*>( + static_cast<value_holder_base<Concrete>*>(p)); + } + + static const Concrete* const_concrete_ptr(const store_value_type* p)noexcept + { + return concrete_ptr(const_cast<store_value_type*>(p)); + } + + static value_type* value_ptr(const value_type* p)noexcept + { + return const_cast<value_type*>(p); + } + + /* It would have sufficed if iterator_from returned const_store_iterator + * except for the fact that some old versions of libstdc++ claiming to be + * C++11 compliant do not however provide std::vector modifier ops taking + * const_iterator's. + */ + + store_iterator iterator_from(const_base_iterator p) + { + return s.begin()+(p-i.data()); + } + + store_iterator iterator_from(const_iterator p) + { + return s.begin()+(p-const_concrete_ptr(s.data())); + } + + base_sentinel sentinel()const noexcept + { + return base_iterator{value_ptr(i.data()+s.size())}; + } + + range range_from(const_store_iterator it)const + { + return {base_iterator{value_ptr(i.data()+(it-s.begin()))},sentinel()}; + } + + range range_from(std::size_t n)const + { + return {base_iterator{value_ptr(i.data()+n)},sentinel()}; + } + + template<typename InputIterator> + range insert( + const_iterator p,InputIterator first,InputIterator last, + std::input_iterator_tag) + { + std::size_t n=0; + for(;first!=last;++first,++n,++p){ + p=prereserve(p); + s.emplace(iterator_from(p),*first); + push_index_entry(); + } + return range_from(iterator_from(p-n)); + } + + template<typename InputIterator> + range insert( + const_iterator p,InputIterator first,InputIterator last, + std::forward_iterator_tag) + { + auto n=s.size(); + auto m=static_cast<std::size_t>(std::distance(first,last)); + if(m){ + p=prereserve(p,m); + try{ + s.insert(iterator_from(p),first,last); + } + catch(...){ + build_index(n+1); + throw; + } + build_index(n+1); + } + return range_from(iterator_from(p)); + } + + store s; + index i; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/stride_iterator.hpp b/boost/poly_collection/detail/stride_iterator.hpp new file mode 100644 index 0000000000..7312e66675 --- /dev/null +++ b/boost/poly_collection/detail/stride_iterator.hpp @@ -0,0 +1,123 @@ +/* Copyright 2016 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_DETAIL_STRIDE_ITERATOR_HPP +#define BOOST_POLY_COLLECTION_DETAIL_STRIDE_ITERATOR_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/iterator/iterator_facade.hpp> +#include <type_traits> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* random-access iterator to Value elements laid out stride *chars* apart */ + +template<typename Value> +class stride_iterator: + public boost::iterator_facade< + stride_iterator<Value>, + Value, + boost::random_access_traversal_tag + > +{ +public: + stride_iterator()=default; + stride_iterator(Value* p,std::size_t stride)noexcept:p{p},stride_{stride}{} + stride_iterator(const stride_iterator&)=default; + stride_iterator& operator=(const stride_iterator&)=default; + + template< + typename NonConstValue, + typename std::enable_if< + std::is_same<Value,const NonConstValue>::value>::type* =nullptr + > + stride_iterator(const stride_iterator<NonConstValue>& x)noexcept: + p{x.p},stride_{x.stride_}{} + + template< + typename NonConstValue, + typename std::enable_if< + std::is_same<Value,const NonConstValue>::value>::type* =nullptr + > + stride_iterator& operator=(const stride_iterator<NonConstValue>& x)noexcept + { + p=x.p;stride_=x.stride_; + return *this; + } + + /* interoperability with [Derived]Value* */ + + stride_iterator& operator=(Value* p_)noexcept{p=p_;return *this;} + operator Value*()const noexcept{return p;} + + template< + typename DerivedValue, + typename std::enable_if< + std::is_base_of<Value,DerivedValue>::value&& + (std::is_const<Value>::value||!std::is_const<DerivedValue>::value) + >::type* =nullptr + > + explicit stride_iterator(DerivedValue* x)noexcept: + p{x},stride_{sizeof(DerivedValue)}{} + + template< + typename DerivedValue, + typename std::enable_if< + std::is_base_of<Value,DerivedValue>::value&& + (!std::is_const<Value>::value||std::is_const<DerivedValue>::value) + >::type* =nullptr + > + explicit operator DerivedValue*()const noexcept + {return static_cast<DerivedValue*>(p);} + + std::size_t stride()const noexcept{return stride_;} + +private: + template<typename> + friend class stride_iterator; + + using char_pointer=typename std::conditional< + std::is_const<Value>::value, + const char*, + char* + >::type; + + static char_pointer char_ptr(Value* p)noexcept + {return reinterpret_cast<char_pointer>(p);} + static Value* value_ptr(char_pointer p)noexcept + {return reinterpret_cast<Value*>(p);} + + friend class boost::iterator_core_access; + + Value& dereference()const noexcept{return *p;} + bool equal(const stride_iterator& x)const noexcept{return p==x.p;} + void increment()noexcept{p=value_ptr(char_ptr(p)+stride_);} + void decrement()noexcept{p=value_ptr(char_ptr(p)-stride_);} + template<typename Integral> + void advance(Integral n)noexcept{p=value_ptr(char_ptr(p)+n*stride_);} + std::ptrdiff_t distance_to(const stride_iterator& x)const noexcept + {return (char_ptr(x.p)-char_ptr(p))/stride_;} + + Value* p; + std::size_t stride_; +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/type_info_map.hpp b/boost/poly_collection/detail/type_info_map.hpp new file mode 100644 index 0000000000..289af10adb --- /dev/null +++ b/boost/poly_collection/detail/type_info_map.hpp @@ -0,0 +1,169 @@ +/* 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_DETAIL_TYPE_INFO_MAP_HPP +#define BOOST_POLY_COLLECTION_DETAIL_TYPE_INFO_MAP_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/newdelete_allocator.hpp> +#include <functional> +#include <typeinfo> +#include <unordered_map> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* To cope with dynamic modules/libs, the standard allows for different + * std::type_info instances to describe the same type, which implies that + * std::type_info::operator== and std::type_info::hash_code are costly + * operations typically relying on the stored type name. + * type_info_ptr_hash<T> behaves roughly as a + * std::unordered_map<std::type_index,T> but maintains an internal cache of + * passed std::type_info instances so that lookup is performed (when there's a + * cache hit) without invoking std::type_info equality and hashing ops. + */ + +struct type_info_ptr_hash +{ + std::size_t operator()(const std::type_info* p)const noexcept + {return p->hash_code();} +}; + +struct type_info_ptr_equal_to +{ + bool operator()( + const std::type_info* p,const std::type_info* q)const noexcept + {return *p==*q;} +}; + + +template<typename T,typename Allocator> +class type_info_map +{ + using map_type=std::unordered_map< + const std::type_info*,T, + type_info_ptr_hash,type_info_ptr_equal_to, + typename std::allocator_traits<Allocator>::template + rebind_alloc<std::pair<const std::type_info* const,T>> + >; + +public: + using key_type=std::type_info; + using mapped_type=T; + using value_type=typename map_type::value_type; + using allocator_type=typename map_type::allocator_type; + using iterator=typename map_type::iterator; + using const_iterator=typename map_type::const_iterator; + + type_info_map()=default; + type_info_map(const type_info_map& x): + map{x.map},cache{x.cache.get_allocator()}{build_cache(x.cache);} + type_info_map(type_info_map&& x)=default; + type_info_map(const allocator_type& al): + map{al},cache{cache_allocator_type{al}}{} + type_info_map(const type_info_map& x,const allocator_type& al): + map{x.map,al},cache{cache_allocator_type{al}}{build_cache(x.cache);} + type_info_map(type_info_map&& x,const allocator_type& al): + map{std::move(x.map),al},cache{cache_allocator_type{al}} + { + if(al==x.map.get_allocator()&& + cache_allocator_type{al}==x.cache.get_allocator()){ + cache=std::move(x.cache); + } + else{ + build_cache(x.cache); + x.cache.clear(); + } + } + + type_info_map& operator=(const type_info_map& x) + { + if(this!=&x){ + type_info_map c{x}; + swap(c); + } + return *this; + } + + type_info_map& operator=(type_info_map&& x)=default; + + allocator_type get_allocator()const noexcept{return map.get_allocator();} + + iterator begin()noexcept{return map.begin();} + iterator end()noexcept{return map.end();} + const_iterator begin()const noexcept{return map.begin();} + const_iterator end()const noexcept{return map.end();} + const_iterator cbegin()const noexcept{return map.cbegin();} + const_iterator cend()const noexcept{return map.cend();} + + iterator find(const key_type& key) + { + auto cit=cache.find(&key); + if(cit!=cache.end())return cit->second; + auto mit=map.find(&key); + if(mit!=map.end())cache.insert({&key,mit}); + return mit; + } + + const_iterator find(const key_type& key)const + { + auto cit=cache.find(&key); + if(cit!=cache.end())return cit->second; + return map.find(&key); + } + + template<typename P> + std::pair<iterator,bool> insert(const key_type& key,P&& x) + { + auto p=map.insert({&key,std::forward<P>(x)}); + cache.insert({&key,p.first}); + return p; + } + + void swap(type_info_map& x){map.swap(x.map);cache.swap(x.cache);} + +private: + using cache_type=std::unordered_map< + const std::type_info*,iterator, + std::hash<const std::type_info*>,std::equal_to<const std::type_info*>, + newdelete_allocator_adaptor< + typename std::allocator_traits<Allocator>::template + rebind_alloc<std::pair<const std::type_info* const,iterator>> + > + >; + using cache_allocator_type=typename cache_type::allocator_type; + + void build_cache(const cache_type& x) + { + for(const auto& p:x)cache.insert({p.first,map.find(p.first)}); + } + + map_type map; + cache_type cache; +}; + +template<typename T,typename Allocator> +void swap(type_info_map<T,Allocator>& x,type_info_map<T,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/type_restitution.hpp b/boost/poly_collection/detail/type_restitution.hpp new file mode 100644 index 0000000000..dadd96507b --- /dev/null +++ b/boost/poly_collection/detail/type_restitution.hpp @@ -0,0 +1,199 @@ +/* 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_DETAIL_TYPE_RESTITUTION_HPP +#define BOOST_POLY_COLLECTION_DETAIL_TYPE_RESTITUTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/detail/functional.hpp> +#include <boost/poly_collection/detail/iterator_traits.hpp> +#include <typeinfo> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* Given types Ts..., a const std::type_info& info and a local_base_iterator + * it, we denote by restitute<Ts...>(info,it): + * - a local_iterator<Ti> from it, if info==typeid(Ti) for some Ti in Ts... + * - it otherwise. + * + * Using this notation, restitute_range<Ts...>(f,args...)(s) resolves to + * f(restitute<Ts...>(info,begin),restitute<Ts...>(info,end),args...) where + * info=s.type_info(), begin=s.begin(), end=s.end(). + */ + +template<typename F,typename... Ts> +struct restitute_range_class; + +template<typename F,typename T,typename... Ts> +struct restitute_range_class<F,T,Ts...>: + restitute_range_class<F,Ts...> +{ + using super=restitute_range_class<F,Ts...>; + using super::super; + + template<typename SegmentInfo> + auto operator()(SegmentInfo&& s) + ->decltype(std::declval<F>()(s.begin(),s.end())) + { + using traits=iterator_traits<decltype(s.begin())>; + using local_iterator=typename traits::template local_iterator<T>; + + if(s.type_info()==typeid(T)) + return (this->f)( + local_iterator{s.begin()},local_iterator{s.end()}); + else + return super::operator()(std::forward<SegmentInfo>(s)); + } +}; + +template<typename F> +struct restitute_range_class<F> +{ + restitute_range_class(const F& f):f{f}{} + + template<typename SegmentInfo> + auto operator()(SegmentInfo&& s) + ->decltype(std::declval<F>()(s.begin(),s.end())) + { + return f(s.begin(),s.end()); + } + + F f; +}; + +template<typename... Ts,typename F,typename... Args> +auto restitute_range(const F& f,Args&&... args) + ->restitute_range_class< + decltype(tail_closure(f,std::forward<Args>(args)...)), + Ts... + > +{ + return tail_closure(f,std::forward<Args>(args)...); +} + +/* restitute_iterator<Ts...>(f,args2...)(index,it,args1...) resolves to + * f(restitute<Ts...>(index,it),args1...,args2...). + */ + +template<typename F,typename... Ts> +struct restitute_iterator_class; + +template<typename F,typename T,typename... Ts> +struct restitute_iterator_class<F,T,Ts...>: + restitute_iterator_class<F,Ts...> +{ + using super=restitute_iterator_class<F,Ts...>; + using super::super; + + template<typename Iterator,typename... Args> + auto operator()( + const std::type_info& info,Iterator&& it,Args&&... args) + ->decltype( + std::declval<F>() + (std::forward<Iterator>(it),std::forward<Args>(args)...)) + { + using traits=iterator_traits<typename std::decay<Iterator>::type>; + using local_iterator=typename traits::template local_iterator<T>; + + if(info==typeid(T)) + return (this->f)( + local_iterator{it},std::forward<Args>(args)...); + else + return super::operator()( + info,std::forward<Iterator>(it),std::forward<Args>(args)...); + } +}; + +template<typename F> +struct restitute_iterator_class<F> +{ + restitute_iterator_class(const F& f):f{f}{} + + template<typename Iterator,typename... Args> + auto operator()( + const std::type_info&,Iterator&& it,Args&&... args) + ->decltype( + std::declval<F>() + (std::forward<Iterator>(it),std::forward<Args>(args)...)) + { + return f(std::forward<Iterator>(it),std::forward<Args>(args)...); + } + + F f; +}; + +template<typename... Ts,typename F,typename... Args> +auto restitute_iterator(const F& f,Args&&... args) + ->restitute_iterator_class< + decltype(tail_closure(f,std::forward<Args>(args)...)), + Ts... + > +{ + return tail_closure(f,std::forward<Args>(args)...); +} + +/* binary_restitute_iterator<Ts...>(f,args...)(index1,it1,index2,it2) resolves + * to f(restitute<Ts...>(index1,it1),restitute<Ts...>(index2,it2),args...). + */ + +template<typename F,typename... Ts> +struct binary_restitute_iterator_class +{ + binary_restitute_iterator_class(const F& f):f{f}{} + + template<typename Iterator1,typename Iterator2> + auto operator()( + const std::type_info& info1,Iterator1&& it1, + const std::type_info& info2,Iterator2&& it2) + ->decltype( + std::declval<F>() + (std::forward<Iterator1>(it1),std::forward<Iterator2>(it2))) + { + return restitute_iterator<Ts...>(*this)( + info2,std::forward<Iterator2>(it2),info1,std::forward<Iterator1>(it1)); + } + + template<typename Iterator2,typename Iterator1> + auto operator()( + Iterator2&& it2,const std::type_info& info1,Iterator1&& it1) + ->decltype( + std::declval<F>() + (std::forward<Iterator1>(it1),std::forward<Iterator2>(it2))) + { + return restitute_iterator<Ts...>(f)( + info1,std::forward<Iterator1>(it1),std::forward<Iterator2>(it2)); + } + + F f; +}; + +template<typename... Ts,typename F,typename... Args> +auto binary_restitute_iterator(const F& f,Args&&... args) + ->binary_restitute_iterator_class< + decltype(tail_closure(f,std::forward<Args>(args)...)), + Ts... + > +{ + return tail_closure(f,std::forward<Args>(args)...); +} + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/detail/value_holder.hpp b/boost/poly_collection/detail/value_holder.hpp new file mode 100644 index 0000000000..bd2f25c6f8 --- /dev/null +++ b/boost/poly_collection/detail/value_holder.hpp @@ -0,0 +1,313 @@ +/* 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_DETAIL_VALUE_HOLDER_HPP +#define BOOST_POLY_COLLECTION_DETAIL_VALUE_HOLDER_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/core/addressof.hpp> +#include <boost/poly_collection/detail/is_constructible.hpp> +#include <boost/poly_collection/detail/is_equality_comparable.hpp> +#include <boost/poly_collection/detail/is_nothrow_eq_comparable.hpp> +#include <boost/poly_collection/exception.hpp> +#include <new> +#include <memory> +#include <type_traits> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ + +/* Segments of a poly_collection maintain vectors of value_holder<T> + * rather than directly T. This serves several purposes: + * - value_holder<T> is copy constructible and equality comparable even if T + * is not: executing the corresponding op results in a reporting exception + * being thrown. This allows the segment to offer its full virtual + * interface regardless of the properties of the concrete class contained. + * - value_holder<T> emulates move assignment when T is not move assignable + * (nothrow move constructibility required); this happens most notably with + * lambda functions, whose assignment operator is deleted by standard + * mandate [expr.prim.lambda]/20 even if the compiler generated one would + * work (capture by value). + * - To comply with [container.requirements.general]/3 (or, more precisely, + * its natural extension to polymorphic containers), value_holder ctors + * accept a first allocator arg passed by value_holder_allocator_adaptor, + * which must therefore be used in the vectors of value_holder's. + * + * A pointer to value_holder_base<T> can be reinterpret_cast'ed to T*. + * Emplacing is explicitly signalled with value_holder_emplacing_ctor to + * protect us from greedy T's constructible from anything (like + * boost::type_erasure::any). + */ + +struct value_holder_emplacing_ctor_t{}; +constexpr value_holder_emplacing_ctor_t value_holder_emplacing_ctor= + value_holder_emplacing_ctor_t(); + +template<typename T> +class value_holder_base +{ +protected: + typename std::aligned_storage<sizeof(T),alignof(T)>::type s; +}; + +template<typename T> +class value_holder:public value_holder_base<T> +{ + template<typename U> + using enable_if_not_emplacing_ctor_t=typename std::enable_if< + !std::is_same< + typename std::decay<U>::type,value_holder_emplacing_ctor_t + >::value + >::type*; + + using is_nothrow_move_constructible=std::is_nothrow_move_constructible<T>; + using is_copy_constructible=std::is_copy_constructible<T>; + using is_nothrow_copy_constructible=std::is_nothrow_copy_constructible<T>; + using is_move_assignable=std::is_move_assignable<T>; + using is_nothrow_move_assignable=std::is_nothrow_move_assignable<T>; + using is_equality_comparable=detail::is_equality_comparable<T>; + using is_nothrow_equality_comparable= + detail::is_nothrow_equality_comparable<T>; + + T* data()noexcept{return reinterpret_cast<T*>(&this->s);} + const T* data()const noexcept + {return reinterpret_cast<const T*>(&this->s);} + + T& value()noexcept{return *static_cast<T*>(data());} + const T& value()const noexcept{return *static_cast<const T*>(data());} + +public: + template< + typename Allocator, + enable_if_not_emplacing_ctor_t<Allocator> =nullptr + > + value_holder(Allocator& al,const T& x) + noexcept(is_nothrow_copy_constructible::value) + {copy(al,x);} + template< + typename Allocator, + enable_if_not_emplacing_ctor_t<Allocator> =nullptr + > + value_holder(Allocator& al,T&& x) + noexcept(is_nothrow_move_constructible::value) + {std::allocator_traits<Allocator>::construct(al,data(),std::move(x));} + template< + typename Allocator,typename... Args, + enable_if_not_emplacing_ctor_t<Allocator> =nullptr + > + value_holder(Allocator& al,value_holder_emplacing_ctor_t,Args&&... args) + {std::allocator_traits<Allocator>::construct( + al,data(),std::forward<Args>(args)...);} + template< + typename Allocator, + enable_if_not_emplacing_ctor_t<Allocator> =nullptr + > + value_holder(Allocator& al,const value_holder& x) + noexcept(is_nothrow_copy_constructible::value) + {copy(al,x.value());} + template< + typename Allocator, + enable_if_not_emplacing_ctor_t<Allocator> =nullptr + > + value_holder(Allocator& al,value_holder&& x) + noexcept(is_nothrow_move_constructible::value) + {std::allocator_traits<Allocator>::construct( + al,data(),std::move(x.value()));} + + /* stdlib implementations in current use are notoriously lacking at + * complying with [container.requirements.general]/3, so we keep the + * following to make their life easier. + */ + + value_holder(const T& x) + noexcept(is_nothrow_copy_constructible::value) + {copy(x);} + value_holder(T&& x) + noexcept(is_nothrow_move_constructible::value) + {::new ((void*)data()) T(std::move(x));} + template<typename... Args> + value_holder(value_holder_emplacing_ctor_t,Args&&... args) + {::new ((void*)data()) T(std::forward<Args>(args)...);} + value_holder(const value_holder& x) + noexcept(is_nothrow_copy_constructible::value) + {copy(x.value());} + value_holder(value_holder&& x) + noexcept(is_nothrow_move_constructible::value) + {::new ((void*)data()) T(std::move(x.value()));} + + value_holder& operator=(const value_holder& x)=delete; + value_holder& operator=(value_holder&& x) + noexcept(is_nothrow_move_assignable::value||!is_move_assignable::value) + /* if 2nd clause: nothrow move constructibility required */ + { + move_assign(std::move(x.value())); + return *this; + } + + ~value_holder()noexcept{value().~T();} + + friend bool operator==(const value_holder& x,const value_holder& y) + noexcept(is_nothrow_equality_comparable::value) + { + return x.equal(y.value()); + } + +private: + template<typename Allocator> + void copy(Allocator& al,const T& x){copy(al,x,is_copy_constructible{});} + + template<typename Allocator> + void copy(Allocator& al,const T& x,std::true_type) + { + std::allocator_traits<Allocator>::construct(al,data(),x); + } + + template<typename Allocator> + void copy(Allocator&,const T&,std::false_type) + { + throw not_copy_constructible{typeid(T)}; + } + + void copy(const T& x){copy(x,is_copy_constructible{});} + + void copy(const T& x,std::true_type) + { + ::new (data()) T(x); + } + + void copy(const T&,std::false_type) + { + throw not_copy_constructible{typeid(T)}; + } + + void move_assign(T&& x){move_assign(std::move(x),is_move_assignable{});} + + void move_assign(T&& x,std::true_type) + { + value()=std::move(x); + } + + void move_assign(T&& x,std::false_type) + { + /* emulated assignment */ + + static_assert(is_nothrow_move_constructible::value, + "type should be move assignable or nothrow move constructible"); + + if(data()!=boost::addressof(x)){ + value().~T(); + ::new (data()) T(std::move(x)); + } + } + + bool equal(const T& x)const{return equal(x,is_equality_comparable{});} + + bool equal(const T& x,std::true_type)const + { + return value()==x; + } + + bool equal(const T&,std::false_type)const + { + throw not_equality_comparable{typeid(T)}; + } +}; + +template<typename Allocator> +struct value_holder_allocator_adaptor:Allocator +{ + using traits=std::allocator_traits<Allocator>; + + using value_type=typename traits::value_type; + using size_type=typename traits::size_type; + using difference_type=typename traits::difference_type; + using pointer=typename traits::pointer; + using const_pointer=typename traits::const_pointer; + using void_pointer=typename traits::void_pointer; + using const_void_pointer=typename traits::const_void_pointer; + using propagate_on_container_copy_assignment= + typename traits::propagate_on_container_copy_assignment; + using propagate_on_container_move_assignment= + typename traits::propagate_on_container_move_assignment; + using propagate_on_container_swap= + typename traits::propagate_on_container_swap; + + template<typename U> + struct rebind + { + using other=value_holder_allocator_adaptor< + typename traits::template rebind_alloc<U>>; + }; + + value_holder_allocator_adaptor()=default; + value_holder_allocator_adaptor( + const value_holder_allocator_adaptor&)=default; + + template< + typename Allocator2, + typename std::enable_if< + is_constructible<Allocator,Allocator2>::value + >::type* =nullptr + > + value_holder_allocator_adaptor(const Allocator2& x)noexcept:Allocator{x}{} + + template< + typename Allocator2, + typename std::enable_if< + is_constructible<Allocator,Allocator2>::value + >::type* =nullptr + > + value_holder_allocator_adaptor( + const value_holder_allocator_adaptor<Allocator2>& x)noexcept: + Allocator{static_cast<const Allocator2&>(x)}{} + + value_holder_allocator_adaptor& operator=( + const value_holder_allocator_adaptor&)=default; + + template<typename T,typename... Args> + void construct(T* p,Args&&... args) + { + ::new ((void*)p) T(std::forward<Args>(args)...); + } + + template<typename T,typename... Args> + void construct(value_holder<T>* p,Args&&... args) + { + ::new ((void*)p) value_holder<T>( + static_cast<Allocator&>(*this),std::forward<Args>(args)...); + } + + template<typename T> + void destroy(T* p) + { + p->~T(); + } + + template<typename T> + void destroy(value_holder<T>* p) + { + traits::destroy( + static_cast<Allocator&>(*this), + reinterpret_cast<T*>(static_cast<value_holder_base<T>*>(p))); + } +}; + +} /* namespace poly_collection::detail */ + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/exception.hpp b/boost/poly_collection/exception.hpp new file mode 100644 index 0000000000..ca2c4da0bb --- /dev/null +++ b/boost/poly_collection/exception.hpp @@ -0,0 +1,57 @@ +/* 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_EXCEPTION_HPP +#define BOOST_POLY_COLLECTION_EXCEPTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <stdexcept> +#include <typeinfo> + +namespace boost{ + +namespace poly_collection{ + +struct unregistered_type:std::logic_error +{ + unregistered_type(const std::type_info& info): + std::logic_error{"type not registered"}, + pinfo{&info} + {} + + const std::type_info* pinfo; +}; + +struct not_copy_constructible:std::logic_error +{ + not_copy_constructible(const std::type_info& info): + std::logic_error{"type is not copy constructible"}, + pinfo{&info} + {} + + const std::type_info* pinfo; +}; + +struct not_equality_comparable:std::logic_error +{ + not_equality_comparable(const std::type_info& info): + std::logic_error{"type does not support equality comparison"}, + pinfo{&info} + {} + + const std::type_info* pinfo; +}; + +} /* namespace poly_collection */ + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/function_collection.hpp b/boost/poly_collection/function_collection.hpp new file mode 100644 index 0000000000..b828197a9b --- /dev/null +++ b/boost/poly_collection/function_collection.hpp @@ -0,0 +1,80 @@ +/* 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_FUNCTION_COLLECTION_HPP +#define BOOST_POLY_COLLECTION_FUNCTION_COLLECTION_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <boost/poly_collection/function_collection_fwd.hpp> +#include <boost/poly_collection/detail/function_model.hpp> +#include <boost/poly_collection/detail/poly_collection.hpp> +#include <utility> + +namespace boost{ + +namespace poly_collection{ + +template<typename Signature,typename Allocator> +class function_collection: + public detail::poly_collection_impl::poly_collection< + detail::function_model<Signature>,Allocator> +{ + using base_type=detail::poly_collection_impl::poly_collection< + detail::function_model<Signature>,Allocator>; + + base_type& base()noexcept{return *this;} + const base_type& base()const noexcept{return *this;} + +public: + using base_type::base_type; + + function_collection()=default; + function_collection(const function_collection& x)=default; + function_collection(function_collection&& x)=default; + function_collection& operator=(const function_collection& x)=default; + function_collection& operator=(function_collection&& x)=default; + + template<typename S,typename A> + friend bool operator==( + const function_collection<S,A>&,const function_collection<S,A>&); +}; + +template<typename Signature,typename Allocator> +bool operator==( + const function_collection<Signature,Allocator>& x, + const function_collection<Signature,Allocator>& y) +{ + return x.base()==y.base(); +} + +template<typename Signature,typename Allocator> +bool operator!=( + const function_collection<Signature,Allocator>& x, + const function_collection<Signature,Allocator>& y) +{ + return !(x==y); +} + +template<typename Signature,typename Allocator> +void swap( + function_collection<Signature,Allocator>& x, + function_collection<Signature,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace */ + +using poly_collection::function_collection; + +} /* namespace boost */ + +#endif diff --git a/boost/poly_collection/function_collection_fwd.hpp b/boost/poly_collection/function_collection_fwd.hpp new file mode 100644 index 0000000000..9ea0a0f5ff --- /dev/null +++ b/boost/poly_collection/function_collection_fwd.hpp @@ -0,0 +1,57 @@ +/* Copyright 2016 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_FUNCTION_COLLECTION_FWD_HPP +#define BOOST_POLY_COLLECTION_FUNCTION_COLLECTION_FWD_HPP + +#if defined(_MSC_VER) +#pragma once +#endif + +#include <memory> + +namespace boost{ + +namespace poly_collection{ + +namespace detail{ +template<typename Signature> struct function_model; +} + +template<typename Signature> +using function_collection_value_type= + typename detail::function_model<Signature>::value_type; + +template< + typename Signature, + typename Allocator=std::allocator<function_collection_value_type<Signature>> +> +class function_collection; + +template<typename Signature,typename Allocator> +bool operator==( + const function_collection<Signature,Allocator>& x, + const function_collection<Signature,Allocator>& y); + +template<typename Signature,typename Allocator> +bool operator!=( + const function_collection<Signature,Allocator>& x, + const function_collection<Signature,Allocator>& y); + +template<typename Signature,typename Allocator> +void swap( + function_collection<Signature,Allocator>& x, + function_collection<Signature,Allocator>& y); + +} /* namespace poly_collection */ + +using poly_collection::function_collection; + +} /* namespace boost */ + +#endif |