]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |