]>
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 | ||
71 | template <typename Pred, std::size_t Insert, bool IsInsertionPoint, | |
72 | typename Left, | |
73 | std::size_t ...Right> | |
74 | struct insert; | |
75 | ||
76 | // We did not find the insertion point; continue processing elements | |
77 | // recursively. | |
78 | template < | |
79 | typename Pred, std::size_t Insert, | |
80 | std::size_t ...Left, | |
81 | std::size_t Right1, std::size_t Right2, std::size_t ...Right | |
82 | > | |
83 | struct insert<Pred, Insert, false, | |
84 | std::index_sequence<Left...>, | |
85 | Right1, Right2, Right... | |
86 | > { | |
87 | using type = typename insert< | |
88 | Pred, Insert, (bool)Pred::template apply<Insert, Right2>::value, | |
89 | std::index_sequence<Left..., Right1>, | |
90 | Right2, Right... | |
91 | >::type; | |
92 | }; | |
93 | ||
94 | // We did not find the insertion point, but there is only one element | |
95 | // left. We insert at the end of the list, and we're done. | |
96 | template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t Last> | |
97 | struct insert<Pred, Insert, false, std::index_sequence<Left...>, Last> { | |
98 | using type = std::index_sequence<Left..., Last, Insert>; | |
99 | }; | |
100 | ||
101 | // We found the insertion point, we're done. | |
102 | template <typename Pred, std::size_t Insert, std::size_t ...Left, std::size_t ...Right> | |
103 | struct insert<Pred, Insert, true, std::index_sequence<Left...>, Right...> { | |
104 | using type = std::index_sequence<Left..., Insert, Right...>; | |
105 | }; | |
106 | ||
107 | ||
108 | template <typename Pred, typename Result, std::size_t ...T> | |
109 | struct insertion_sort_impl; | |
110 | ||
111 | template <typename Pred, | |
112 | std::size_t Result1, std::size_t ...Result, | |
113 | std::size_t T, std::size_t ...Ts> | |
114 | struct insertion_sort_impl<Pred, std::index_sequence<Result1, Result...>, T, Ts...> { | |
115 | using type = typename insertion_sort_impl< | |
116 | Pred, | |
117 | typename insert< | |
118 | Pred, T, (bool)Pred::template apply<T, Result1>::value, | |
119 | std::index_sequence<>, | |
120 | Result1, Result... | |
121 | >::type, | |
122 | Ts... | |
123 | >::type; | |
124 | }; | |
125 | ||
126 | template <typename Pred, std::size_t T, std::size_t ...Ts> | |
127 | struct insertion_sort_impl<Pred, std::index_sequence<>, T, Ts...> { | |
128 | using type = typename insertion_sort_impl< | |
129 | Pred, std::index_sequence<T>, Ts... | |
130 | >::type; | |
131 | }; | |
132 | ||
133 | template <typename Pred, typename Result> | |
134 | struct insertion_sort_impl<Pred, Result> { | |
135 | using type = Result; | |
136 | }; | |
137 | ||
138 | template <typename Pred, typename Indices> | |
139 | struct sort_helper; | |
140 | ||
141 | template <typename Pred, std::size_t ...i> | |
142 | struct sort_helper<Pred, std::index_sequence<i...>> { | |
143 | using type = typename insertion_sort_impl< | |
144 | Pred, std::index_sequence<>, i... | |
145 | >::type; | |
146 | }; | |
147 | } // end namespace detail | |
148 | ||
149 | template <typename S, bool condition> | |
150 | struct sort_impl<S, when<condition>> : default_ { | |
151 | template <typename Xs, std::size_t ...i> | |
152 | static constexpr auto apply_impl(Xs&& xs, std::index_sequence<i...>) { | |
153 | return hana::make<S>(hana::at_c<i>(static_cast<Xs&&>(xs))...); | |
154 | } | |
155 | ||
156 | template <typename Xs, typename Pred> | |
157 | static constexpr auto apply(Xs&& xs, Pred const&) { | |
158 | constexpr std::size_t Len = decltype(hana::length(xs))::value; | |
159 | using Indices = typename detail::sort_helper< | |
160 | detail::sort_predicate<Xs&&, Pred>, | |
161 | std::make_index_sequence<Len> | |
162 | >::type; | |
163 | ||
164 | return apply_impl(static_cast<Xs&&>(xs), Indices{}); | |
165 | } | |
166 | ||
167 | template <typename Xs> | |
168 | static constexpr auto apply(Xs&& xs) | |
169 | { return sort_impl::apply(static_cast<Xs&&>(xs), hana::less); } | |
170 | }; | |
171 | BOOST_HANA_NAMESPACE_END | |
172 | ||
173 | #endif // !BOOST_HANA_SORT_HPP |