boost/mpl/aux_/sort_impl.hpp

   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