Back to home page

EIC code displayed by LXR
 
 

    

Warning, file /include/boost/poly_collection/algorithm.hpp was not indexed or was modified since last indexation (in which case cross-reference links may be missing, inaccurate or erroneous).

0001 /* Copyright 2016-2024 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/poly_collection for library home page.
0007  */
0008 
0009 #ifndef BOOST_POLY_COLLECTION_ALGORITHM_HPP
0010 #define BOOST_POLY_COLLECTION_ALGORITHM_HPP
0011 
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015 
0016 #include <algorithm>
0017 #include <boost/config.hpp>
0018 #include <boost/poly_collection/detail/auto_iterator.hpp>
0019 #include <boost/poly_collection/detail/copyable.hpp>
0020 #include <boost/poly_collection/detail/functional.hpp>
0021 #include <boost/poly_collection/detail/iterator_traits.hpp>
0022 #include <boost/poly_collection/detail/segment_split.hpp>
0023 #include <boost/poly_collection/detail/type_restitution.hpp>
0024 #include <iterator>
0025 #include <random>
0026 #include <type_traits>
0027 #include <utility>
0028 
0029 /* Improved performance versions of std algorithms over poly_collection.
0030  * poly_collection::alg is expected to be faster than the homonym std::alg
0031  * because the latter does a traversal over a segmented structured, where
0032  * incrementing requires checking for segment change, whereas the former
0033  * for-loops over flat segments.
0034  * Additionally, poly_collection::alg<Ti...>(...,f) *restitutes* Ti when
0035  * passing elements to f, i.e. if the concrete type of the element is Ti
0036  * then f is invoked with a [const] Ti&, which can dramatically improve
0037  * performance when f has specific overloads for Ti (like, for instance,
0038  * generic lambdas) as static optimization can kick in (devirtualization
0039  * being a particular example).
0040  */
0041 
0042 #if defined(BOOST_MSVC)
0043 #pragma warning(push)
0044 #pragma warning(disable:4714) /* marked as __forceinline not inlined */
0045 #endif
0046 
0047 namespace boost{
0048 
0049 namespace poly_collection{
0050 
0051 namespace detail{
0052 
0053 namespace algorithm{
0054 
0055 template<typename Iterator>
0056 using enable_if_poly_collection_iterator=typename std::enable_if<
0057   !std::is_void<typename poly_collection_of<Iterator>::type>::value
0058 >::type*;
0059 
0060 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_all_of,std::all_of)
0061 
0062 template<
0063   typename... Ts,typename Iterator,typename Predicate,
0064   enable_if_poly_collection_iterator<Iterator> =nullptr
0065 >
0066 BOOST_FORCEINLINE
0067 bool all_of(const Iterator& first,const Iterator& last,Predicate pred)
0068 {
0069   using model_type=typename iterator_traits<Iterator>::model_type;
0070 
0071   auto alg=restitute_range<model_type,Ts...>(std_all_of{},pred);
0072   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
0073   return true;
0074 }
0075 
0076 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_any_of,std::any_of)
0077 
0078 template<
0079   typename... Ts,typename Iterator,typename Predicate,
0080   enable_if_poly_collection_iterator<Iterator> =nullptr
0081 >
0082 BOOST_FORCEINLINE bool any_of(
0083   const Iterator& first,const Iterator& last,Predicate pred)
0084 {
0085   using model_type=typename iterator_traits<Iterator>::model_type;
0086 
0087   auto alg=restitute_range<model_type,Ts...>(std_any_of{},pred);
0088   for(auto i:detail::segment_split(first,last))if(alg(i))return true;
0089   return false;
0090 }
0091 
0092 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_none_of,std::none_of)
0093 
0094 template<
0095   typename... Ts,typename Iterator,typename Predicate,
0096   enable_if_poly_collection_iterator<Iterator> =nullptr
0097 >
0098 BOOST_FORCEINLINE bool none_of(
0099   const Iterator& first,const Iterator& last,Predicate pred)
0100 {
0101   using model_type=typename iterator_traits<Iterator>::model_type;
0102 
0103   auto alg=restitute_range<model_type,Ts...>(std_none_of{},pred);
0104   for(auto i:detail::segment_split(first,last))if(!alg(i))return false;
0105   return true;
0106 }
0107 
0108 struct for_each_alg
0109 {
0110   template<typename InputIterator,typename Function>
0111   void operator()(
0112     InputIterator first,InputIterator last,Function& f)const /* note the & */
0113   {
0114     for(;first!=last;++first)f(*first);
0115   }
0116 };
0117 
0118 template<typename... Ts,typename Iterator,typename Function,
0119   enable_if_poly_collection_iterator<Iterator> =nullptr
0120 >
0121 BOOST_FORCEINLINE Function for_each(
0122   const Iterator& first,const Iterator& last,Function f)
0123 {
0124   using model_type=typename iterator_traits<Iterator>::model_type;
0125 
0126   for_each_segment(
0127     first,last,restitute_range<model_type,Ts...>(for_each_alg{},f));
0128   return f;
0129 }
0130 
0131 struct for_each_n_alg
0132 {
0133   template<
0134     typename InputIterator,typename Size,typename Function
0135   >
0136   InputIterator operator()(
0137     InputIterator first,Size n,Function& f)const /* note the & */
0138   {
0139     for(;n>0;++first,(void)--n)f(*first);
0140     return first;
0141   }
0142 };
0143 
0144 template<
0145   typename... Ts,typename Iterator,typename Size,typename Function,
0146   enable_if_poly_collection_iterator<Iterator> =nullptr
0147 >
0148 BOOST_FORCEINLINE Iterator for_each_n(const Iterator& first,Size n,Function f)
0149 {
0150   using traits=iterator_traits<Iterator>;
0151   using model_type=typename traits::model_type;
0152   using local_base_iterator=typename traits::local_base_iterator;
0153 
0154   if(n<=0)return first;
0155 
0156   auto alg=restitute_iterator<model_type,Ts...>(
0157          cast_return<local_base_iterator>(for_each_n_alg{}));
0158   auto lbit=traits::local_base_iterator_from(first);
0159   auto sit=traits::base_segment_info_iterator_from(first);
0160   for(;;){
0161     Size m=static_cast<Size>(sit->end()-lbit);
0162     if(n<=m){
0163       auto it=alg(sit->type_info(),lbit,n,f);
0164       return traits::iterator_from(
0165         it,traits::end_base_segment_info_iterator_from(first));
0166     }
0167     else{
0168       alg(sit->type_info(),lbit,m,f);
0169       n-=m;
0170     }
0171     ++sit;
0172     lbit=sit->begin();
0173   }
0174 }
0175 
0176 template<
0177   typename Algorithm,typename... Ts,
0178   typename Iterator,typename... Args,
0179   enable_if_poly_collection_iterator<Iterator> =nullptr
0180 >
0181 BOOST_FORCEINLINE Iterator generic_find(
0182   const Iterator& first,const Iterator& last,Args&&... args)
0183 {
0184   using traits=iterator_traits<Iterator>;
0185   using model_type=typename traits::model_type;
0186   using local_base_iterator=typename traits::local_base_iterator;
0187 
0188   auto alg=restitute_range<model_type,Ts...>(
0189     cast_return<local_base_iterator>(Algorithm{}),
0190     std::forward<Args>(args)...);
0191   for(auto i:detail::segment_split(first,last)){
0192     auto it=alg(i);
0193     if(it!=i.end())
0194       return traits::iterator_from(
0195         it,traits::end_base_segment_info_iterator_from(last));
0196   }
0197   return last;
0198 }
0199 
0200 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find,std::find)
0201 
0202 template<
0203   typename... Ts,typename Iterator,typename T,
0204   enable_if_poly_collection_iterator<Iterator> =nullptr
0205 >
0206 BOOST_FORCEINLINE Iterator find(
0207   const Iterator& first,const Iterator& last,const T& x)
0208 {
0209   return generic_find<std_find,Ts...>(first,last,x);
0210 }
0211 
0212 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if,std::find_if)
0213 
0214 template<
0215   typename... Ts,typename Iterator,typename Predicate,
0216   enable_if_poly_collection_iterator<Iterator> =nullptr
0217 >
0218 BOOST_FORCEINLINE Iterator find_if(
0219   const Iterator& first,const Iterator& last,Predicate pred)
0220 {
0221   return generic_find<std_find_if,Ts...>(first,last,pred);
0222 }
0223 
0224 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_if_not,std::find_if_not)
0225 
0226 template<
0227   typename... Ts,typename Iterator,typename Predicate,
0228   enable_if_poly_collection_iterator<Iterator> =nullptr
0229 >
0230 BOOST_FORCEINLINE Iterator find_if_not(
0231   const Iterator& first,const Iterator& last,Predicate pred)
0232 {
0233   return generic_find<std_find_if_not,Ts...>(first,last,pred);
0234 }
0235 
0236 /* find_end defined after search below */
0237 
0238 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_find_first_of,std::find_first_of)
0239 
0240 template<
0241   typename... Ts,typename Iterator,typename ForwardIterator,
0242   enable_if_poly_collection_iterator<Iterator> =nullptr
0243 >
0244 BOOST_FORCEINLINE Iterator find_first_of(
0245   const Iterator& first1,const Iterator& last1,
0246   ForwardIterator first2,ForwardIterator last2)
0247 {
0248   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2);
0249 }
0250 
0251 template<
0252   typename... Ts,typename Iterator,
0253   typename ForwardIterator,typename BinaryPredicate,
0254   enable_if_poly_collection_iterator<Iterator> =nullptr
0255 >
0256 BOOST_FORCEINLINE Iterator find_first_of(
0257   const Iterator& first1,const Iterator& last1,
0258   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0259 {
0260   return generic_find<std_find_first_of,Ts...>(first1,last1,first2,last2,pred);
0261 }
0262 
0263 template<typename... Ts>
0264 struct adjacent_find_alg
0265 {
0266   template<
0267     typename LocalIterator,typename BinaryPredicate,
0268     typename TypeIndex,typename LocalBaseIterator
0269   >
0270   LocalBaseIterator operator()(
0271     LocalIterator first,LocalIterator last,BinaryPredicate pred,
0272     bool& carry,TypeIndex& prev_info, /* note the &s */
0273     LocalBaseIterator& prev)const
0274   {
0275     using traits=iterator_traits<LocalIterator>;
0276     using model_type=typename traits::model_type;
0277 
0278     if(first==last)return LocalBaseIterator{last};
0279     if(carry){
0280       auto p=restitute_iterator<model_type,Ts...>(deref_to(pred));
0281       if(p(prev_info,prev,first))return prev;
0282     }
0283     auto res=std::adjacent_find(first,last,pred);
0284     if(res==last){
0285       carry=true;
0286       prev_info=traits::template index<
0287         typename std::iterator_traits<LocalIterator>::value_type>();
0288       prev=LocalBaseIterator{last-1};
0289     }
0290     else carry=false;
0291     return LocalBaseIterator{res};
0292   }
0293 };
0294 
0295 template<
0296   typename... Ts,typename Iterator,typename BinaryPredicate,
0297   enable_if_poly_collection_iterator<Iterator> =nullptr
0298 >
0299 BOOST_FORCEINLINE Iterator adjacent_find(
0300   const Iterator& first,const Iterator& last,BinaryPredicate pred)
0301 {
0302   using traits=iterator_traits<Iterator>;
0303   using local_base_iterator=typename traits::local_base_iterator;
0304 
0305   bool                  carry=false;
0306   auto                  prev_info=
0307                           make_copyable(traits::template index<void>());
0308   local_base_iterator   prev;
0309   return generic_find<adjacent_find_alg<Ts...>,Ts...>(
0310     first,last,pred,carry,prev_info,prev);  
0311 }
0312 
0313 template<
0314   typename... Ts,typename Iterator,
0315   enable_if_poly_collection_iterator<Iterator> =nullptr
0316 >
0317 BOOST_FORCEINLINE Iterator adjacent_find(
0318   const Iterator& first,const Iterator& last)
0319 {
0320   return algorithm::adjacent_find<Ts...>(first,last,transparent_equal_to{});
0321 }
0322 
0323 template<
0324   typename Algorithm,typename... Ts,
0325   typename Iterator,typename... Args,
0326   enable_if_poly_collection_iterator<Iterator> =nullptr
0327 >
0328 BOOST_FORCEINLINE std::ptrdiff_t generic_count(
0329   const Iterator& first,const Iterator& last,Args&&... args)
0330 {
0331   using model_type=typename iterator_traits<Iterator>::model_type;
0332 
0333   auto alg=restitute_range<model_type,Ts...>(
0334     Algorithm{},std::forward<Args>(args)...);
0335   std::ptrdiff_t res=0;
0336   for(auto i:detail::segment_split(first,last))res+=alg(i);
0337   return res;
0338 }
0339 
0340 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count,std::count)
0341 
0342 template<
0343   typename... Ts,typename Iterator,typename T,
0344   enable_if_poly_collection_iterator<Iterator> =nullptr
0345 >
0346 BOOST_FORCEINLINE std::ptrdiff_t count(
0347   const Iterator& first,const Iterator& last,const T& x)
0348 {
0349   return generic_count<std_count,Ts...>(first,last,x);
0350 }
0351 
0352 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_count_if,std::count_if)
0353 
0354 template<
0355   typename... Ts,typename Iterator,typename Predicate,
0356   enable_if_poly_collection_iterator<Iterator> =nullptr
0357 >
0358 BOOST_FORCEINLINE std::ptrdiff_t count_if(
0359   const Iterator& first,const Iterator& last,Predicate pred)
0360 {
0361   return generic_count<std_count_if,Ts...>(first,last,pred);
0362 }
0363 
0364 struct mismatch_alg
0365 {
0366   template<
0367     typename InputIterator1,
0368     typename InputIterator2,typename BinaryPredicate
0369   >
0370   InputIterator1 operator()(
0371     InputIterator1 first1,InputIterator1 last1,
0372     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
0373   {
0374     while(first1!=last1&&pred(*first1,*first2)){
0375       ++first1;
0376       ++first2;
0377     }
0378     return first1;
0379   }
0380 
0381   template<
0382     typename InputIterator1,
0383     typename InputIterator2,typename BinaryPredicate
0384   >
0385   InputIterator1 operator()(
0386     InputIterator1 first1,InputIterator1 last1,
0387     InputIterator2& first2,InputIterator2 last2, /* note the & */
0388     BinaryPredicate pred)const
0389   {
0390     while(first1!=last1&&first2!=last2&&pred(*first1,*first2)){
0391       ++first1;
0392       ++first2;
0393     }
0394     return first1;
0395   }
0396 };
0397 
0398 template<
0399   typename... Ts,typename Iterator,
0400   typename InputIterator,typename BinaryPredicate,
0401   enable_if_poly_collection_iterator<Iterator> =nullptr
0402 >
0403 BOOST_FORCEINLINE std::pair<Iterator,InputIterator> mismatch(
0404   const Iterator& first1,const Iterator& last1,
0405   InputIterator first2,BinaryPredicate pred)
0406 {
0407   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,pred);
0408   return {it,first2};
0409 }
0410 
0411 template<
0412   typename... Ts,typename Iterator,typename InputIterator,
0413   enable_if_poly_collection_iterator<Iterator> =nullptr
0414 >
0415 BOOST_FORCEINLINE std::pair<Iterator,InputIterator> mismatch(
0416   const Iterator& first1,const Iterator& last1,InputIterator first2)
0417 {
0418   return algorithm::mismatch<Ts...>(
0419     first1,last1,first2,transparent_equal_to{});
0420 }
0421 
0422 template<
0423   typename... Ts,typename Iterator,
0424   typename InputIterator,typename BinaryPredicate,
0425   enable_if_poly_collection_iterator<Iterator> =nullptr
0426 >
0427 BOOST_FORCEINLINE std::pair<Iterator,InputIterator> mismatch(
0428   const Iterator& first1,const Iterator& last1,
0429   InputIterator first2,InputIterator last2,BinaryPredicate pred)
0430 {
0431   auto it=generic_find<mismatch_alg,Ts...>(first1,last1,first2,last2,pred);
0432   return {it,first2};
0433 }
0434 
0435 template<
0436   typename... Ts,typename Iterator,typename InputIterator,
0437   enable_if_poly_collection_iterator<Iterator> =nullptr
0438 >
0439 BOOST_FORCEINLINE std::pair<Iterator,InputIterator> mismatch(
0440   const Iterator& first1,const Iterator& last1,
0441   InputIterator first2,InputIterator last2)
0442 {
0443   return algorithm::mismatch<Ts...>(
0444     first1,last1,first2,last2,transparent_equal_to{});
0445 }
0446 
0447 struct equal_alg
0448 {
0449   template<
0450     typename InputIterator1,
0451     typename InputIterator2,typename BinaryPredicate
0452   >
0453   bool operator()(
0454     InputIterator1 first1,InputIterator1 last1,
0455     InputIterator2& first2,BinaryPredicate pred)const /* note the & */
0456   {
0457     for(;first1!=last1;++first1,++first2){
0458       if(!pred(*first1,*first2))return false;
0459     }
0460     return true;
0461   }
0462 
0463   template<
0464     typename InputIterator1,
0465     typename InputIterator2,typename BinaryPredicate
0466   >
0467   bool operator()(
0468     InputIterator1 first1,InputIterator1 last1,
0469     InputIterator2& first2,InputIterator2 last2, /* note the & */
0470     BinaryPredicate pred)const
0471   {
0472     for(;first1!=last1&&first2!=last2;++first1,++first2){
0473       if(!pred(*first1,*first2))return false;
0474     }
0475     return first1==last1; /* don't check first2==last2 as op is partial */
0476   }
0477 };
0478 
0479 template<
0480   typename... Ts,typename Iterator,
0481   typename InputIterator,typename BinaryPredicate,
0482   enable_if_poly_collection_iterator<Iterator> =nullptr
0483 >
0484 BOOST_FORCEINLINE bool equal(
0485   const Iterator& first1,const Iterator& last1,
0486   InputIterator first2,BinaryPredicate pred)
0487 {
0488   using model_type=typename iterator_traits<Iterator>::model_type;
0489 
0490   auto alg=restitute_range<model_type,Ts...>(equal_alg{},first2,pred);
0491   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
0492   return true;
0493 }
0494 
0495 template<
0496   typename... Ts,typename Iterator,typename InputIterator,
0497   enable_if_poly_collection_iterator<Iterator> =nullptr
0498 >
0499 BOOST_FORCEINLINE bool equal(
0500   const Iterator& first1,const Iterator& last1,InputIterator first2)
0501 {
0502   return algorithm::equal<Ts...>(first1,last1,first2,transparent_equal_to{});
0503 }
0504 
0505 template<
0506   typename... Ts,typename Iterator,
0507   typename InputIterator,typename BinaryPredicate,
0508   enable_if_poly_collection_iterator<Iterator> =nullptr
0509 >
0510 BOOST_FORCEINLINE bool equal(
0511   const Iterator& first1,const Iterator& last1,
0512   InputIterator first2,InputIterator last2,BinaryPredicate pred)
0513 {
0514   using model_type=typename iterator_traits<Iterator>::model_type;
0515 
0516   auto alg=restitute_range<model_type,Ts...>(equal_alg{},first2,last2,pred);
0517   for(auto i:detail::segment_split(first1,last1))if(!alg(i))return false;
0518   return first2==last2;
0519 }
0520 
0521 template<
0522   typename... Ts,typename Iterator,typename InputIterator,
0523   enable_if_poly_collection_iterator<Iterator> =nullptr
0524 >
0525 BOOST_FORCEINLINE bool equal(
0526   const Iterator& first1,const Iterator& last1,
0527   InputIterator first2,InputIterator last2)
0528 {
0529   return algorithm::equal<Ts...>(
0530     first1,last1,first2,last2,transparent_equal_to{});
0531 }
0532 
0533 template<
0534   typename Iterator,
0535   enable_if_poly_collection_iterator<Iterator> =nullptr
0536 >
0537 BOOST_FORCEINLINE std::ptrdiff_t fast_distance(
0538   const Iterator& first,const Iterator& last)
0539 {
0540   using traits=iterator_traits<Iterator>;
0541 
0542   if(first==last)return 0;
0543 
0544   auto sfirst=traits::base_segment_info_iterator_from(first),
0545        slast=traits::base_segment_info_iterator_from(last);
0546   if(sfirst==slast){
0547     return std::distance(
0548       traits::local_base_iterator_from(first),
0549       traits::local_base_iterator_from(last));
0550   }
0551   else{
0552     std::ptrdiff_t m=std::distance(
0553       traits::local_base_iterator_from(first),sfirst->end());
0554     while(++sfirst!=slast)m+=std::distance(sfirst->begin(),sfirst->end());
0555     if(slast!=traits::end_base_segment_info_iterator_from(last)){
0556       m+=std::distance(
0557         slast->begin(),traits::local_base_iterator_from(last));
0558     }
0559     return m;
0560   }
0561 }
0562 
0563 template<
0564   typename... Ts,typename Iterator,
0565   typename ForwardIterator,typename BinaryPredicate,
0566   enable_if_poly_collection_iterator<Iterator> =nullptr
0567 >
0568 BOOST_FORCEINLINE bool is_permutation_suffix(
0569   const Iterator& first1,const Iterator& last1,
0570   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0571 {
0572   using traits=iterator_traits<Iterator>;
0573   using model_type=typename traits::model_type;
0574 
0575   auto send=traits::end_base_segment_info_iterator_from(last1);
0576   for(auto i:detail::segment_split(first1,last1)){
0577     for(auto lbscan=i.begin();lbscan!=i.end();++lbscan){
0578       auto& info=i.type_info();
0579       auto p=head_closure(
0580         restitute_iterator<model_type,Ts...>(deref_1st_to(pred)),info,lbscan);
0581       auto scan=traits::iterator_from(lbscan,send);
0582       if(algorithm::find_if<Ts...>(first1,scan,p)!=scan)continue;
0583       std::ptrdiff_t matches=std::count_if(first2,last2,p);
0584       if(matches==0||
0585          matches!=algorithm::count_if<Ts...>(scan,last1,p))return false;
0586     }
0587   }
0588   return true;
0589 }
0590 
0591 template<
0592   typename... Ts,typename Iterator,
0593   typename ForwardIterator,typename BinaryPredicate,
0594   enable_if_poly_collection_iterator<Iterator> =nullptr
0595 >
0596 BOOST_FORCEINLINE bool is_permutation(
0597   Iterator first1,Iterator last1,ForwardIterator first2,BinaryPredicate pred)
0598 {
0599   std::tie(first1,first2)=algorithm::mismatch<Ts...>(first1,last1,first2,pred);
0600   auto last2=std::next(first2,algorithm::fast_distance(first1,last1));
0601   return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
0602 }
0603 
0604 template<
0605   typename... Ts,typename Iterator,typename ForwardIterator,
0606   enable_if_poly_collection_iterator<Iterator> =nullptr
0607 >
0608 BOOST_FORCEINLINE bool is_permutation(
0609   const Iterator& first1,const Iterator& last1,ForwardIterator first2)
0610 {
0611   return algorithm::is_permutation<Ts...>(
0612     first1,last1,first2,transparent_equal_to{});
0613 }
0614 
0615 template<
0616   typename... Ts,typename Iterator,
0617   typename ForwardIterator,typename BinaryPredicate,
0618   enable_if_poly_collection_iterator<Iterator> =nullptr
0619 >
0620 BOOST_FORCEINLINE bool is_permutation(
0621   Iterator first1,Iterator last1,
0622   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0623 {
0624   std::tie(first1,first2)=algorithm::mismatch<Ts...>(
0625     first1,last1,first2,last2,pred);
0626   if(algorithm::fast_distance(first1,last1)!=std::distance(first2,last2))
0627     return false;
0628   else return is_permutation_suffix<Ts...>(first1,last1,first2,last2,pred);
0629 }
0630 
0631 template<
0632   typename... Ts,typename Iterator,typename ForwardIterator,
0633   enable_if_poly_collection_iterator<Iterator> =nullptr
0634 >
0635 BOOST_FORCEINLINE bool is_permutation(
0636   const Iterator& first1,const Iterator& last1,
0637   ForwardIterator first2,ForwardIterator last2)
0638 {
0639   return algorithm::is_permutation<Ts...>(
0640     first1,last1,first2,last2,transparent_equal_to{});
0641 }
0642 
0643 template<
0644   typename... Ts,typename Iterator,
0645   typename ForwardIterator,typename BinaryPredicate,
0646   enable_if_poly_collection_iterator<Iterator> =nullptr
0647 >
0648 BOOST_FORCEINLINE Iterator search(
0649   const Iterator& first1,const Iterator& last1,
0650   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0651 {
0652   using traits=iterator_traits<Iterator>;
0653 
0654   auto send=traits::end_base_segment_info_iterator_from(last1);
0655   for(auto i:detail::segment_split(first1,last1)){
0656     for(auto lbit=i.begin(),lbend=i.end();lbit!=lbend;++lbit){
0657       Iterator it=traits::iterator_from(lbit,send);
0658       if(algorithm::mismatch<Ts...>(it,last1,first2,last2,pred).second==last2)
0659         return it;
0660     }
0661   }
0662   return last1;
0663 }
0664 
0665 template<
0666   typename... Ts,typename Iterator,typename ForwardIterator,
0667   enable_if_poly_collection_iterator<Iterator> =nullptr
0668 >
0669 BOOST_FORCEINLINE Iterator search(
0670   const Iterator& first1,const Iterator& last1,
0671   ForwardIterator first2,ForwardIterator last2)
0672 {
0673   return algorithm::search<Ts...>(
0674     first1,last1,first2,last2,transparent_equal_to{});
0675 }
0676 
0677 template<
0678   typename... Ts,typename Iterator,
0679   typename ForwardIterator,typename BinaryPredicate,
0680   enable_if_poly_collection_iterator<Iterator> =nullptr
0681 >
0682 BOOST_FORCEINLINE Iterator find_end(
0683   Iterator first1,Iterator last1,
0684   ForwardIterator first2,ForwardIterator last2,BinaryPredicate pred)
0685 {
0686   if(first2==last2)return last1;
0687 
0688   for(Iterator res=last1;;){
0689     Iterator res1=algorithm::search<Ts...>(first1,last1,first2,last2,pred);
0690     if(res1==last1)return res;
0691     else{
0692       first1=res=res1;
0693       ++first1;
0694     }
0695   }
0696 }
0697 
0698 template<
0699   typename... Ts,typename Iterator,typename ForwardIterator,
0700   enable_if_poly_collection_iterator<Iterator> =nullptr
0701 >
0702 BOOST_FORCEINLINE Iterator find_end(
0703   const Iterator& first1,const Iterator& last1,
0704   ForwardIterator first2,ForwardIterator last2)
0705 {
0706   return algorithm::find_end<Ts...>(
0707     first1,last1,first2,last2,transparent_equal_to{});
0708 }
0709 
0710 struct search_n_alg
0711 {
0712   template<
0713     typename ForwardIterator,typename Size,
0714     typename T,typename BinaryPredicate
0715   >
0716   ForwardIterator operator()(
0717     ForwardIterator first,ForwardIterator last,
0718     Size count,bool& carry,Size& remain,const T& x, /* note the &s */
0719     BinaryPredicate pred)const
0720   {
0721     for(;first!=last;++first){
0722       if(!pred(*first,x)){carry=false;remain=count;continue;}
0723       auto res=first;
0724       for(;;){
0725         if(--remain==0||++first==last)return res;
0726         if(!pred(*first,x)){carry=false;remain=count;break;}
0727       } 
0728     }
0729     return last;
0730   }
0731 };
0732 
0733 template<
0734   typename... Ts,typename Iterator,
0735   typename Size,typename T,typename BinaryPredicate,
0736   enable_if_poly_collection_iterator<Iterator> =nullptr
0737 >
0738 BOOST_FORCEINLINE Iterator search_n(
0739   const Iterator& first,const Iterator& last,
0740   Size count,const T& x,BinaryPredicate pred)
0741 {
0742   using traits=iterator_traits<Iterator>;
0743   using model_type=typename traits::model_type;
0744   using local_base_iterator=typename traits::local_base_iterator;
0745 
0746   if(count<=0)return first;
0747 
0748   bool                carry=false;
0749   auto                remain=count;
0750   auto                alg=restitute_range<model_type,Ts...>(
0751                         cast_return<local_base_iterator>(search_n_alg{}),
0752                         count,carry,remain,x,pred);
0753   local_base_iterator prev;
0754   for(auto i:detail::segment_split(first,last)){
0755     auto it=alg(i);
0756     if(it!=i.end()){
0757       if(remain==0)
0758         return traits::iterator_from(
0759           carry?prev:it,
0760           traits::end_base_segment_info_iterator_from(last));
0761       else if(!carry){prev=it;carry=true;}
0762     }
0763   }
0764   return last;
0765 }
0766 
0767 template<
0768   typename... Ts,typename Iterator,
0769   typename Size,typename T,
0770   enable_if_poly_collection_iterator<Iterator> =nullptr
0771 >
0772 BOOST_FORCEINLINE Iterator search_n(
0773   const Iterator& first,const Iterator& last,Size count,const T& x)
0774 {
0775   return algorithm::search_n<Ts...>(
0776     first,last,count,x,transparent_equal_to{});
0777 }
0778 
0779 template<
0780   typename Algorithm,typename... Ts,
0781   typename Iterator,typename OutputIterator,typename... Args,
0782   enable_if_poly_collection_iterator<Iterator> =nullptr
0783 >
0784 BOOST_FORCEINLINE OutputIterator generic_copy(
0785   const Iterator& first,const Iterator& last,OutputIterator res,Args&&... args)
0786 {
0787   using model_type=typename iterator_traits<Iterator>::model_type;
0788 
0789   for(auto i:detail::segment_split(first,last)){
0790     auto alg=restitute_range<model_type,Ts...>(
0791       Algorithm{},res,std::forward<Args>(args)...);
0792     res=alg(i);
0793   }
0794   return res;
0795 }
0796 
0797 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy,std::copy)
0798 
0799 template<
0800   typename... Ts,typename Iterator,typename OutputIterator,
0801   enable_if_poly_collection_iterator<Iterator> =nullptr
0802 >
0803 BOOST_FORCEINLINE OutputIterator copy(
0804   const Iterator& first,const Iterator& last,OutputIterator res)
0805 {
0806   return generic_copy<std_copy,Ts...>(first,last,res);
0807 }
0808 
0809 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_n,std::copy_n)
0810 
0811 template<
0812   typename... Ts,typename Iterator,typename Size,typename OutputIterator,
0813   enable_if_poly_collection_iterator<Iterator> =nullptr
0814 >
0815 BOOST_FORCEINLINE OutputIterator copy_n(
0816   const Iterator& first,Size count,OutputIterator res)
0817 {
0818   using traits=iterator_traits<Iterator>;
0819   using model_type=typename traits::model_type;
0820 
0821   if(count<=0)return res;
0822 
0823   auto lbit=traits::local_base_iterator_from(first);
0824   auto sit=traits::base_segment_info_iterator_from(first);
0825   for(;;){
0826     auto n=(std::min)(count,static_cast<Size>(sit->end()-lbit));
0827     auto alg=restitute_iterator<model_type,Ts...>(std_copy_n{},n,res);
0828     res=alg(sit->type_info(),lbit);
0829     if((count-=n)==0)break;
0830     ++sit;
0831     lbit=sit->begin();
0832   }
0833   return res;
0834 }
0835 
0836 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_copy_if,std::copy_if)
0837 
0838 template<
0839   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
0840   enable_if_poly_collection_iterator<Iterator> =nullptr
0841 >
0842 BOOST_FORCEINLINE OutputIterator copy_if(
0843   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
0844 {
0845   return generic_copy<std_copy_if,Ts...>(first,last,res,pred);
0846 }
0847 
0848 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_move,std::move)
0849 
0850 template<
0851   typename... Ts,typename Iterator,typename OutputIterator,
0852   enable_if_poly_collection_iterator<Iterator> =nullptr
0853 >
0854 BOOST_FORCEINLINE OutputIterator move(
0855   const Iterator& first,const Iterator& last,OutputIterator res)
0856 {
0857   return generic_copy<std_move,Ts...>(first,last,res);
0858 }
0859 
0860 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_transform,std::transform)
0861 
0862 template<
0863   typename... Ts,typename Iterator,
0864   typename OutputIterator,typename UnaryOperation,
0865   enable_if_poly_collection_iterator<Iterator> =nullptr
0866 >
0867 BOOST_FORCEINLINE OutputIterator transform(
0868   const Iterator& first,const Iterator& last,
0869   OutputIterator res,UnaryOperation op)
0870 {
0871   return generic_copy<std_transform,Ts...>(first,last,res,op);
0872 }
0873 
0874 struct transform2_alg
0875 {
0876   template<
0877     typename InputIterator1,typename InputIterator2,
0878     typename OutputIterator,typename BinaryOperation
0879   >
0880   OutputIterator operator()(
0881     InputIterator1 first1,InputIterator1 last1,
0882     OutputIterator res, /* third place for compatibility with generic_copy */
0883     InputIterator2& first2, BinaryOperation op)const         /* note the & */
0884   {
0885     while(first1!=last1)*res++=op(*first1++,*first2++);
0886     return res;
0887   }
0888 };
0889 
0890 template<
0891   typename... Ts,typename Iterator,typename InputIterator,
0892   typename OutputIterator,typename BinaryOperation,
0893   enable_if_poly_collection_iterator<Iterator> =nullptr
0894 >
0895 BOOST_FORCEINLINE OutputIterator transform(
0896   const Iterator& first1,const Iterator& last1,InputIterator first2,
0897   OutputIterator res,BinaryOperation op)
0898 {
0899   return generic_copy<transform2_alg,Ts...>(first1,last1,res,first2,op);  
0900 }
0901 
0902 struct replace_copy_alg
0903 {
0904   /* std::replace_copy broken in VS2015, internal ticket VSO#279818 
0905    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
0906    * conditional operator".
0907    */
0908 
0909   template<typename InputIterator,typename OutputIterator,typename T>
0910   OutputIterator operator()(
0911     InputIterator first,InputIterator last,OutputIterator res,
0912     const T& old_x,const T& new_x)
0913   {
0914     for(;first!=last;++first,++res){
0915       if(*first==old_x)*res=new_x;
0916       else             *res=*first;
0917     }
0918     return res;
0919   }
0920 };
0921 
0922 template<
0923   typename... Ts,typename Iterator,typename OutputIterator,typename T,
0924   enable_if_poly_collection_iterator<Iterator> =nullptr
0925 >
0926 BOOST_FORCEINLINE OutputIterator replace_copy(
0927   const Iterator& first,const Iterator& last,OutputIterator res,
0928   const T& old_x,const T& new_x)
0929 {
0930   return generic_copy<replace_copy_alg,Ts...>(first,last,res,old_x,new_x);
0931 }
0932 
0933 struct replace_copy_if_alg
0934 {
0935   /* std::replace_copy_if broken in VS2015, internal ticket VSO#279818 
0936    * "<algorithm>: replace_copy() and replace_copy_if() shouldn't use the
0937    * conditional operator".
0938    */
0939 
0940   template<
0941     typename InputIterator,typename OutputIterator,
0942     typename Predicate,typename T
0943   >
0944   OutputIterator operator()(
0945     InputIterator first,InputIterator last,OutputIterator res,
0946     Predicate pred,const T& new_x)
0947   {
0948     for(;first!=last;++first,++res){
0949       if(pred(*first))*res=new_x;
0950       else            *res=*first;
0951     }
0952     return res;
0953   }
0954 };
0955 
0956 template<
0957   typename... Ts,typename Iterator,typename OutputIterator,
0958   typename Predicate,typename T,
0959   enable_if_poly_collection_iterator<Iterator> =nullptr
0960 >
0961 BOOST_FORCEINLINE OutputIterator replace_copy_if(
0962   const Iterator& first,const Iterator& last,OutputIterator res,
0963   Predicate pred,const T& new_x)
0964 {
0965   return generic_copy<replace_copy_if_alg,Ts...>(first,last,res,pred,new_x);  
0966 }
0967 
0968 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(std_remove_copy,std::remove_copy)
0969 
0970 template<
0971   typename... Ts,typename Iterator,typename OutputIterator,typename T,
0972   enable_if_poly_collection_iterator<Iterator> =nullptr
0973 >
0974 BOOST_FORCEINLINE OutputIterator remove_copy(
0975   const Iterator& first,const Iterator& last,OutputIterator res,const T& x)
0976 {
0977   return generic_copy<std_remove_copy,Ts...>(first,last,res,x);  
0978 }
0979 
0980 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(
0981   std_remove_copy_if,std::remove_copy_if)
0982 
0983 template<
0984   typename... Ts,typename Iterator,typename OutputIterator,typename Predicate,
0985   enable_if_poly_collection_iterator<Iterator> =nullptr
0986 >
0987 BOOST_FORCEINLINE OutputIterator remove_copy_if(
0988   const Iterator& first,const Iterator& last,OutputIterator res,Predicate pred)
0989 {
0990   return generic_copy<std_remove_copy_if,Ts...>(first,last,res,pred);  
0991 }
0992 
0993 template<typename... Ts>
0994 struct unique_copy_alg
0995 {
0996   template<
0997     typename LocalIterator,typename OutputIterator,
0998     typename BinaryPredicate,typename TypeIndex,typename LocalBaseIterator
0999   >
1000   OutputIterator operator()(
1001     LocalIterator first,LocalIterator last,
1002     OutputIterator res, BinaryPredicate pred,
1003     bool& carry,TypeIndex& prev_info, /* note the &s */
1004     LocalBaseIterator& prev)const
1005   {
1006     using traits=iterator_traits<LocalIterator>;
1007     using model_type=typename traits::model_type;
1008 
1009     if(carry){
1010       auto p=restitute_iterator<model_type,Ts...>(deref_to(pred));
1011       for(;first!=last;++first)if(!p(prev_info,prev,first))break;
1012     }
1013     if(first==last)return res;
1014     res=std::unique_copy(first,last,res,pred);
1015     carry=true;
1016     prev_info=traits::template index<
1017       typename std::iterator_traits<LocalIterator>::value_type>();
1018     prev=LocalBaseIterator{last-1};
1019     return res;
1020   }
1021 };
1022 
1023 template<
1024   typename... Ts,typename Iterator,
1025   typename OutputIterator,typename BinaryPredicate,
1026   enable_if_poly_collection_iterator<Iterator> =nullptr
1027 >
1028 BOOST_FORCEINLINE OutputIterator unique_copy(
1029   const Iterator& first,const Iterator& last,
1030   OutputIterator res,BinaryPredicate pred)
1031 {
1032   using traits=iterator_traits<Iterator>;
1033   using local_base_iterator=typename traits::local_base_iterator;
1034 
1035   bool                  carry=false;
1036   auto                  prev_info=
1037                           make_copyable(traits::template index<void>());
1038   local_base_iterator   prev;
1039   return generic_copy<unique_copy_alg<Ts...>,Ts...>(
1040     first,last,res,pred,carry,prev_info,prev);  
1041 }
1042 
1043 template<
1044   typename... Ts,typename Iterator,typename OutputIterator,
1045   enable_if_poly_collection_iterator<Iterator> =nullptr
1046 >
1047 BOOST_FORCEINLINE OutputIterator unique_copy(
1048   const Iterator& first,const Iterator& last,OutputIterator res)
1049 {
1050   return algorithm::unique_copy<Ts...>(first,last,res,transparent_equal_to{});
1051 }
1052 
1053 template<
1054   typename... Ts,typename Iterator,typename OutputIterator,
1055   enable_if_poly_collection_iterator<Iterator> =nullptr
1056 >
1057 BOOST_FORCEINLINE OutputIterator rotate_copy(
1058   const Iterator& first,const Iterator& middle,const Iterator& last,
1059   OutputIterator res)
1060 {
1061   res=algorithm::copy<Ts...>(middle,last,res);
1062   return algorithm::copy<Ts...>(first,middle,res);
1063 }
1064 
1065 struct sample_alg
1066 {
1067   template<
1068     typename InputIterator,typename OutputIterator,
1069     typename Distance,typename UniformRandomBitGenerator
1070   >
1071   OutputIterator operator()(
1072     InputIterator first,InputIterator last,
1073     OutputIterator res,Distance& n,Distance& m, /* note the &s */
1074     UniformRandomBitGenerator& g)const 
1075   {
1076     for(;first!=last&&n!=0;++first){
1077       auto r=std::uniform_int_distribution<Distance>(0,--m)(g);
1078       if (r<n){
1079         *res++=*first;
1080         --n;
1081       }
1082     }
1083     return res;
1084   }
1085 };
1086 
1087 template<
1088   typename... Ts,typename Iterator,typename OutputIterator,
1089   typename Distance,typename UniformRandomBitGenerator,
1090   enable_if_poly_collection_iterator<Iterator> =nullptr
1091 >
1092 BOOST_FORCEINLINE OutputIterator sample(
1093   const Iterator& first,const Iterator& last,
1094   OutputIterator res,Distance n,UniformRandomBitGenerator&& g)
1095 {
1096   using model_type=typename iterator_traits<Iterator>::model_type;
1097 
1098   Distance m=static_cast<Distance>(algorithm::fast_distance(first,last));
1099   n=(std::min)(n,m);
1100 
1101   for(auto i:detail::segment_split(first,last)){
1102     auto alg=restitute_range<model_type,Ts...>(sample_alg{},res,n,m,g);
1103     res=alg(i);
1104     if(n==0)return res;
1105   }
1106   return res; /* never reached */
1107 }
1108 
1109 template<
1110   typename... Ts,typename Iterator,typename Predicate,
1111   enable_if_poly_collection_iterator<Iterator> =nullptr
1112 >
1113 BOOST_FORCEINLINE bool is_partitioned(
1114   const Iterator& first,const Iterator& last,Predicate pred)
1115 {
1116   auto it=algorithm::find_if_not<Ts...>(first,last,pred);
1117   if(it==last)return true;
1118   return algorithm::none_of<Ts...>(++it,last,pred);
1119 }
1120 
1121 BOOST_POLY_COLLECTION_DEFINE_OVERLOAD_SET(
1122   std_partition_copy,std::partition_copy)
1123 
1124 template<
1125   typename... Ts,typename Iterator,
1126   typename OutputIterator1,typename OutputIterator2,typename Predicate,
1127   enable_if_poly_collection_iterator<Iterator> =nullptr
1128 >
1129 BOOST_FORCEINLINE std::pair<OutputIterator1,OutputIterator2> partition_copy(
1130   const Iterator& first,const Iterator& last,
1131   OutputIterator1 rest,OutputIterator2 resf,Predicate pred)
1132 {
1133   using model_type=typename iterator_traits<Iterator>::model_type;
1134 
1135   for(auto i:detail::segment_split(first,last)){
1136     auto alg=restitute_range<model_type,Ts...>(
1137       std_partition_copy{},rest,resf,pred);
1138     std::tie(rest,resf)=alg(i);
1139   }
1140   return {rest,resf};
1141 }
1142 
1143 template<typename Predicate,typename... Ts>
1144 struct partition_point_pred
1145 {
1146   partition_point_pred(const Predicate& pred):pred(pred){}
1147 
1148   template<typename Iterator>
1149   bool operator()(const Iterator& it)const
1150   {
1151     using traits=iterator_traits<Iterator>;
1152     using model_type=typename traits::model_type;
1153 
1154     auto p=restitute_iterator<model_type,Ts...>(deref_to(pred));
1155     return p(
1156       traits::base_segment_info_iterator_from(it)->type_info(),
1157       traits::local_base_iterator_from(it));
1158   }
1159 
1160   Predicate pred;
1161 };
1162 
1163 template<
1164   typename... Ts,typename Iterator,typename Predicate,
1165   enable_if_poly_collection_iterator<Iterator> =nullptr
1166 >
1167 BOOST_FORCEINLINE Iterator partition_point(
1168   const Iterator& first,const Iterator& last,Predicate pred)
1169 {
1170   auto_iterator<Iterator>               afirst{first},alast{last};
1171   partition_point_pred<Predicate,Ts...> p{pred};
1172   return *std::partition_point(afirst,alast,p);
1173 }
1174 
1175 } /* namespace poly_collection::detail::algorithm */
1176 
1177 } /* namespace poly_collection::detail */
1178 
1179 /* non-modifying sequence operations */
1180 
1181 using detail::algorithm::all_of;
1182 using detail::algorithm::any_of;
1183 using detail::algorithm::none_of;
1184 using detail::algorithm::for_each;
1185 using detail::algorithm::for_each_n;
1186 using detail::algorithm::find;
1187 using detail::algorithm::find_if;
1188 using detail::algorithm::find_if_not;
1189 using detail::algorithm::find_end;
1190 using detail::algorithm::find_first_of;
1191 using detail::algorithm::adjacent_find;
1192 using detail::algorithm::count;
1193 using detail::algorithm::count_if;
1194 using detail::algorithm::mismatch;
1195 using detail::algorithm::equal;
1196 using detail::algorithm::is_permutation;
1197 using detail::algorithm::search;
1198 using detail::algorithm::search_n;
1199 
1200 /* modifying sequence operations */
1201 
1202 using detail::algorithm::copy;
1203 using detail::algorithm::copy_n;
1204 using detail::algorithm::copy_if;
1205                       /* copy_backward requires BidirectionalIterator */
1206 using detail::algorithm::move;
1207                       /* move_backward requires BidirectionalIterator */
1208                       /* swap_ranges requires Swappable */
1209                       /* iter_swap requires Swappable */
1210 using detail::algorithm::transform;
1211                       /* replace requires Assignable */
1212                       /* replace_if requires Assignable */
1213 using detail::algorithm::replace_copy;
1214 using detail::algorithm::replace_copy_if;
1215                       /* fill requires Assignable */
1216                       /* fill_n requires Assignable */
1217                       /* generate requires Assignable */
1218                       /* generate_n requires Assignable */
1219                       /* remove requires MoveAssignable */
1220                       /* remove_if requires MoveAssignable */
1221 using detail::algorithm::remove_copy;
1222 using detail::algorithm::remove_copy_if;
1223                       /* unique requires MoveAssignable */
1224 using detail::algorithm::unique_copy;
1225                       /* reverse requires BidirectionalIterator */
1226                       /* reverse_copy requires BidirectionalIterator */
1227                       /* rotate requires MoveAssignable */
1228 using detail::algorithm::rotate_copy;
1229 using detail::algorithm::sample;
1230                       /* shuffle requires RandomAccessIterator */
1231 using detail::algorithm::is_partitioned;
1232                       /* partition requires Swappable */
1233                       /* stable_partition requires Swappable */
1234 using detail::algorithm::partition_copy;
1235 using detail::algorithm::partition_point;
1236 
1237 /* sorting and related operations not provided */
1238 
1239 } /* namespace poly_collection */
1240 
1241 } /* namespace boost */
1242 
1243 #if defined(BOOST_MSVC)
1244 #pragma warning(pop) /* C4714 */
1245 #endif
1246 
1247 #endif
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!