]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Defines `boost::hana::sort`. | |
4 | ||
b32b8144 | 5 | @copyright Louis Dionne 2013-2017 |
7c673cae FG |
6 | Distributed under the Boost Software License, Version 1.0. |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_SORT_HPP | |
11 | #define BOOST_HANA_SORT_HPP | |
12 | ||
13 | #include <boost/hana/fwd/sort.hpp> | |
14 | ||
15 | #include <boost/hana/at.hpp> | |
16 | #include <boost/hana/concept/sequence.hpp> | |
17 | #include <boost/hana/config.hpp> | |
18 | #include <boost/hana/core/dispatch.hpp> | |
19 | #include <boost/hana/core/make.hpp> | |
20 | #include <boost/hana/detail/nested_by.hpp> // required by fwd decl | |
21 | #include <boost/hana/length.hpp> | |
22 | #include <boost/hana/less.hpp> | |
23 | ||
24 | #include <utility> // std::declval, std::index_sequence | |
25 | ||
26 | ||
27 | BOOST_HANA_NAMESPACE_BEGIN | |
28 | //! @cond | |
29 | template <typename Xs, typename Predicate> | |
30 | constexpr auto sort_t::operator()(Xs&& xs, Predicate&& pred) const { | |
31 | using S = typename hana::tag_of<Xs>::type; | |
32 | using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>, | |
33 | hana::Sequence<S>::value | |
34 | ); | |
35 | ||
36 | #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS | |
37 | static_assert(hana::Sequence<S>::value, | |
38 | "hana::sort(xs, predicate) requires 'xs' to be a Sequence"); | |
39 | #endif | |
40 | ||
41 | return Sort::apply(static_cast<Xs&&>(xs), | |
42 | static_cast<Predicate&&>(pred)); | |
43 | } | |
44 | ||
45 | template <typename Xs> | |
46 | constexpr auto sort_t::operator()(Xs&& xs) const { | |
47 | using S = typename hana::tag_of<Xs>::type; | |
48 | using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>, | |
49 | hana::Sequence<S>::value | |
50 | ); | |
51 | ||
52 | #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS | |
53 | static_assert(hana::Sequence<S>::value, | |
54 | "hana::sort(xs) requires 'xs' to be a Sequence"); | |
55 | #endif | |
56 | ||
57 | return Sort::apply(static_cast<Xs&&>(xs)); | |
58 | } | |
59 | //! @endcond | |
60 | ||
61 | namespace detail { | |
62 | template <typename Xs, typename Pred> | |
63 | struct sort_predicate { | |
64 | template <std::size_t I, std::size_t J> | |
65 | using apply = decltype(std::declval<Pred>()( | |
66 | hana::at_c<I>(std::declval<Xs>()), | |
67 | hana::at_c<J>(std::declval<Xs>()) | |
68 | )); | |
69 | }; | |
70 | ||
92f5a8d4 TL |
71 | template <typename Left, typename Right> |
72 | struct concat; | |
73 | ||
74 | template <std::size_t ...l, std::size_t ...r> | |
75 | struct concat<std::index_sequence<l...>, std::index_sequence<r...>> { | |
76 | using type = std::index_sequence<l..., r...>; | |
77 | }; | |
78 | ||
79 | template <typename Pred, bool PickRight, typename Left, typename Right> | |
80 | struct merge; | |
7c673cae | 81 | |
7c673cae | 82 | template < |
92f5a8d4 TL |
83 | typename Pred, |
84 | std::size_t l0, | |
85 | std::size_t l1, | |
86 | std::size_t ...l, | |
87 | std::size_t r0, | |
88 | std::size_t ...r> | |
89 | struct merge< | |
90 | Pred, | |
91 | false, | |
92 | std::index_sequence<l0, l1, l...>, | |
93 | std::index_sequence<r0, r...> | |
7c673cae | 94 | > { |
92f5a8d4 TL |
95 | using type = typename concat< |
96 | std::index_sequence<l0>, | |
97 | typename merge< | |
98 | Pred, | |
99 | (bool)Pred::template apply<r0, l1>::value, | |
100 | std::index_sequence<l1, l...>, | |
101 | std::index_sequence<r0, r...> | |
102 | >::type | |
7c673cae FG |
103 | >::type; |
104 | }; | |
105 | ||
92f5a8d4 TL |
106 | template < |
107 | typename Pred, | |
108 | std::size_t l0, | |
109 | std::size_t r0, | |
110 | std::size_t ...r> | |
111 | struct merge< | |
112 | Pred, | |
113 | false, | |
114 | std::index_sequence<l0>, | |
115 | std::index_sequence<r0, r...> | |
116 | > { | |
117 | using type = std::index_sequence<l0, r0, r...>; | |
7c673cae FG |
118 | }; |
119 | ||
92f5a8d4 TL |
120 | template < |
121 | typename Pred, | |
122 | std::size_t l0, | |
123 | std::size_t ...l, | |
124 | std::size_t r0, | |
125 | std::size_t r1, | |
126 | std::size_t ...r> | |
127 | struct merge< | |
128 | Pred, | |
129 | true, | |
130 | std::index_sequence<l0, l...>, | |
131 | std::index_sequence<r0, r1, r...> | |
132 | > { | |
133 | using type = typename concat< | |
134 | std::index_sequence<r0>, | |
135 | typename merge< | |
136 | Pred, | |
137 | (bool)Pred::template apply<r1, l0>::value, | |
138 | std::index_sequence<l0, l...>, | |
139 | std::index_sequence<r1, r...> | |
140 | >::type | |
141 | >::type; | |
7c673cae FG |
142 | }; |
143 | ||
92f5a8d4 TL |
144 | template < |
145 | typename Pred, | |
146 | std::size_t l0, | |
147 | std::size_t ...l, | |
148 | std::size_t r0> | |
149 | struct merge< | |
150 | Pred, | |
151 | true, | |
152 | std::index_sequence<l0, l...>, | |
153 | std::index_sequence<r0> | |
154 | > { | |
155 | using type = std::index_sequence<r0, l0, l...>; | |
156 | }; | |
7c673cae | 157 | |
92f5a8d4 TL |
158 | template <typename Pred, typename Left, typename Right> |
159 | struct merge_helper; | |
7c673cae | 160 | |
92f5a8d4 TL |
161 | template < |
162 | typename Pred, | |
163 | std::size_t l0, | |
164 | std::size_t ...l, | |
165 | std::size_t r0, | |
166 | std::size_t ...r> | |
167 | struct merge_helper< | |
168 | Pred, | |
169 | std::index_sequence<l0, l...>, | |
170 | std::index_sequence<r0, r...> | |
171 | > { | |
172 | using type = typename merge< | |
7c673cae | 173 | Pred, |
92f5a8d4 TL |
174 | (bool)Pred::template apply<r0, l0>::value, |
175 | std::index_sequence<l0, l...>, | |
176 | std::index_sequence<r0, r...> | |
7c673cae FG |
177 | >::type; |
178 | }; | |
179 | ||
92f5a8d4 TL |
180 | // split templated structure, Nr represents the number of elements |
181 | // from Right to move to Left | |
182 | // There are two specializations: | |
183 | // The first handles the generic case (Nr > 0) | |
184 | // The second handles the stop condition (Nr == 0) | |
185 | // These two specializations are not strictly ordered as | |
186 | // the first cannot match Nr==0 && empty Right | |
187 | // the second cannot match Nr!=0 | |
188 | // std::enable_if<Nr!=0> is therefore required to make sure these two | |
189 | // specializations will never both be candidates during an overload | |
190 | // resolution (otherwise ambiguity occurs for Nr==0 and non-empty Right) | |
191 | template <std::size_t Nr, typename Left, typename Right, typename=void> | |
192 | struct split; | |
193 | ||
194 | template < | |
195 | std::size_t Nr, | |
196 | std::size_t ...l, | |
197 | std::size_t ...r, | |
198 | std::size_t r0> | |
199 | struct split< | |
200 | Nr, | |
201 | std::index_sequence<l...>, | |
202 | std::index_sequence<r0, r...>, | |
203 | typename std::enable_if<Nr!=0>::type | |
204 | > { | |
205 | using sp = split< | |
206 | Nr-1, | |
207 | std::index_sequence<l..., r0>, | |
208 | std::index_sequence<r...> | |
209 | >; | |
210 | using left = typename sp::left; | |
211 | using right = typename sp::right; | |
7c673cae FG |
212 | }; |
213 | ||
92f5a8d4 TL |
214 | template <std::size_t ...l, std::size_t ...r> |
215 | struct split<0, std::index_sequence<l...>, std::index_sequence<r...>> { | |
216 | using left = std::index_sequence<l...>; | |
217 | using right = std::index_sequence<r...>; | |
7c673cae FG |
218 | }; |
219 | ||
92f5a8d4 TL |
220 | template <typename Pred, typename Sequence> |
221 | struct merge_sort_impl; | |
7c673cae | 222 | |
92f5a8d4 TL |
223 | template <typename Pred, std::size_t ...seq> |
224 | struct merge_sort_impl<Pred, std::index_sequence<seq...>> { | |
225 | using sequence = std::index_sequence<seq...>; | |
226 | using sp = split< | |
227 | sequence::size() / 2, | |
228 | std::index_sequence<>, | |
229 | sequence | |
230 | >; | |
231 | using type = typename merge_helper< | |
232 | Pred, | |
233 | typename merge_sort_impl<Pred, typename sp::left>::type, | |
234 | typename merge_sort_impl<Pred, typename sp::right>::type | |
7c673cae FG |
235 | >::type; |
236 | }; | |
92f5a8d4 TL |
237 | |
238 | template <typename Pred, std::size_t x> | |
239 | struct merge_sort_impl<Pred, std::index_sequence<x>> { | |
240 | using type = std::index_sequence<x>; | |
241 | }; | |
242 | ||
243 | template <typename Pred> | |
244 | struct merge_sort_impl<Pred, std::index_sequence<>> { | |
245 | using type = std::index_sequence<>; | |
246 | }; | |
7c673cae FG |
247 | } // end namespace detail |
248 | ||
249 | template <typename S, bool condition> | |
250 | struct sort_impl<S, when<condition>> : default_ { | |
251 | template <typename Xs, std::size_t ...i> | |
252 | static constexpr auto apply_impl(Xs&& xs, std::index_sequence<i...>) { | |
253 | return hana::make<S>(hana::at_c<i>(static_cast<Xs&&>(xs))...); | |
254 | } | |
255 | ||
256 | template <typename Xs, typename Pred> | |
257 | static constexpr auto apply(Xs&& xs, Pred const&) { | |
258 | constexpr std::size_t Len = decltype(hana::length(xs))::value; | |
92f5a8d4 | 259 | using Indices = typename detail::merge_sort_impl< |
7c673cae FG |
260 | detail::sort_predicate<Xs&&, Pred>, |
261 | std::make_index_sequence<Len> | |
262 | >::type; | |
263 | ||
264 | return apply_impl(static_cast<Xs&&>(xs), Indices{}); | |
265 | } | |
266 | ||
267 | template <typename Xs> | |
268 | static constexpr auto apply(Xs&& xs) | |
269 | { return sort_impl::apply(static_cast<Xs&&>(xs), hana::less); } | |
270 | }; | |
271 | BOOST_HANA_NAMESPACE_END | |
272 | ||
273 | #endif // !BOOST_HANA_SORT_HPP |