1 2 #ifndef BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED 3 #define BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED 4 5 // Copyright Eric Friedman 2002-2003 6 // 7 // Distributed under the Boost Software License, Version 1.0. 8 // (See accompanying file LICENSE_1_0.txt or copy at 9 // http://www.boost.org/LICENSE_1_0.txt) 10 // 11 // See http://www.boost.org/libs/mpl for documentation. 12 13 // $Id$ 14 // $Date$ 15 // $Revision$ 16 17 #include <boost/mpl/partition.hpp> 18 #include <boost/mpl/copy.hpp> 19 #include <boost/mpl/vector.hpp> 20 #include <boost/mpl/back_inserter.hpp> 21 #include <boost/mpl/front_inserter.hpp> 22 #include <boost/mpl/iterator_range.hpp> 23 #include <boost/mpl/joint_view.hpp> 24 #include <boost/mpl/single_view.hpp> 25 #include <boost/mpl/begin_end.hpp> 26 #include <boost/mpl/empty.hpp> 27 #include <boost/mpl/deref.hpp> 28 #include <boost/mpl/eval_if.hpp> 29 #include <boost/mpl/apply.hpp> 30 #include <boost/mpl/identity.hpp> 31 #include <boost/mpl/less.hpp> 32 #include <boost/mpl/aux_/na.hpp> 33 34 namespace boost { namespace mpl { namespace aux { 35 36 template< typename Seq, typename Pred > 37 struct quick_sort; 38 39 // agurt, 10/nov/04: for the sake of deficeint compilers 40 template< typename Pred, typename Pivot > 41 struct quick_sort_pred 42 { 43 template< typename T > struct apply 44 { 45 typedef typename apply2<Pred,T,Pivot>::type type; 46 }; 47 }; 48 49 template< 50 typename Seq 51 , typename Pred 52 > 53 struct quick_sort_impl 54 { 55 typedef typename begin<Seq>::type pivot; 56 typedef typename partition< 57 iterator_range< 58 typename next<pivot>::type 59 , typename end<Seq>::type 60 > 61 , protect< aux::quick_sort_pred< Pred, typename deref<pivot>::type > > 62 , back_inserter< vector<> > 63 , back_inserter< vector<> > 64 >::type partitioned; 65 66 typedef typename quick_sort< typename partitioned::first, Pred >::type part1; 67 typedef typename quick_sort< typename partitioned::second, Pred >::type part2; 68 69 typedef joint_view< 70 joint_view< part1, single_view< typename deref<pivot>::type > > 71 , part2 72 > type; 73 }; 74 75 template< 76 typename Seq 77 , typename Pred 78 > 79 struct quick_sort 80 : eval_if< 81 empty<Seq> 82 , identity<Seq> 83 , quick_sort_impl<Seq,Pred> 84 > 85 { 86 }; 87 88 89 template < 90 typename Sequence 91 , typename Pred 92 , typename In 93 > 94 struct sort_impl 95 { 96 typedef typename quick_sort< 97 Sequence 98 , typename if_na<Pred,less<> >::type 99 >::type result_; 100 101 typedef typename copy<result_,In>::type type; 102 }; 103 104 template < 105 typename Sequence 106 , typename Pred 107 , typename In 108 > 109 struct reverse_sort_impl 110 { 111 typedef typename quick_sort< 112 Sequence 113 , typename if_na<Pred,less<> >::type 114 >::type result_; 115 116 typedef typename reverse_copy<result_,In>::type type; 117 }; 118 119 }}} 120 121 #endif // BOOST_MPL_AUX_SORT_IMPL_HPP_INCLUDED 122