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