mpl/aux_/sort_impl.hpp

0001
0002 #ifndef BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED
0003 #define BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED
0004
0005 // Copyright Eric Friedman 2002-2003
0006 //
0007 // Distributed under the Boost Software License, Version 1.0.
0008 // (See accompanying file LICENSE_1_0.txt or copy at
0009 // http://www.boost.org/LICENSE_1_0.txt)
0010 //
0011 // See http://www.boost.org/libs/mpl for documentation.
0012
0013 // $Id$
0014 // $Date$
0015 // $Revision$
0016
0017 #include <boost/mpl/partition.hpp>
0018 #include <boost/mpl/copy.hpp>
0019 #include <boost/mpl/vector.hpp>
0020 #include <boost/mpl/back_inserter.hpp>
0021 #include <boost/mpl/front_inserter.hpp>
0022 #include <boost/mpl/iterator_range.hpp>
0023 #include <boost/mpl/joint_view.hpp>
0024 #include <boost/mpl/single_view.hpp>
0025 #include <boost/mpl/begin_end.hpp>
0026 #include <boost/mpl/empty.hpp>
0027 #include <boost/mpl/deref.hpp>
0028 #include <boost/mpl/eval_if.hpp>
0029 #include <boost/mpl/apply.hpp>
0030 #include <boost/mpl/identity.hpp>
0031 #include <boost/mpl/less.hpp>
0032 #include <boost/mpl/aux_/na.hpp>
0033
0034 namespace boost { namespace mpl { namespace aux {
0035
0036 template< typename Seq, typename Pred >
0037 struct quick_sort;
0038
0039 // agurt, 10/nov/04: for the sake of deficeint compilers
0040 template< typename Pred, typename Pivot >
0041 struct quick_sort_pred
0042 {
0043     template< typename T > struct apply
0044     {
0045         typedef typename apply2<Pred,T,Pivot>::type type;
0046     };
0047 };
0048
0049 template<
0050       typename Seq
0051     , typename Pred
0052     >
0053 struct quick_sort_impl
0054 {
0055     typedef typename begin<Seq>::type pivot;
0056     typedef typename partition<
0057           iterator_range<
0058               typename next<pivot>::type
0059             , typename end<Seq>::type
0060             >
0061         , protect< aux::quick_sort_pred< Pred, typename deref<pivot>::type > >
0062         , back_inserter< vector<> >
0063         , back_inserter< vector<> >
0064         >::type partitioned;
0065
0066     typedef typename quick_sort< typename partitioned::first, Pred >::type part1;
0067     typedef typename quick_sort< typename partitioned::second, Pred >::type part2;
0068
0069     typedef joint_view<
0070               joint_view< part1, single_view< typename deref<pivot>::type > >
0071             , part2
0072             > type;
0073 };
0074
0075 template<
0076       typename Seq
0077     , typename Pred
0078     >
0079 struct quick_sort
0080     : eval_if<
0081           empty<Seq>
0082         , identity<Seq>
0083         , quick_sort_impl<Seq,Pred>
0084         >
0085 {
0086 };
0087
0088
0089 template <
0090       typename Sequence
0091     , typename Pred
0092     , typename In
0093     >
0094 struct sort_impl
0095 {
0096     typedef typename quick_sort<
0097           Sequence
0098         , typename if_na<Pred,less<> >::type
0099         >::type result_;
0100
0101     typedef typename copy<result_,In>::type type;
0102 };
0103
0104 template <
0105       typename Sequence
0106     , typename Pred
0107     , typename In
0108     >
0109 struct reverse_sort_impl
0110 {
0111     typedef typename quick_sort<
0112           Sequence
0113         , typename if_na<Pred,less<> >::type
0114         >::type result_;
0115
0116     typedef typename reverse_copy<result_,In>::type type;
0117 };
0118
0119 }}}
0120
0121 #endif // BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED