1 /*! 2 @file 3 Defines `boost::hana::sort`. 4 5 @copyright Louis Dionne 2013-2017 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> operator ()(Xs && xs,Predicate && pred) const30 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> operator ()(Xs && xs) const46 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 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; 81 82 template < 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...> 94 > { 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 103 >::type; 104 }; 105 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...>; 118 }; 119 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; 142 }; 143 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 }; 157 158 template <typename Pred, typename Left, typename Right> 159 struct merge_helper; 160 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< 173 Pred, 174 (bool)Pred::template apply<r0, l0>::value, 175 std::index_sequence<l0, l...>, 176 std::index_sequence<r0, r...> 177 >::type; 178 }; 179 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; 212 }; 213 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...>; 218 }; 219 220 template <typename Pred, typename Sequence> 221 struct merge_sort_impl; 222 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 235 >::type; 236 }; 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 }; 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> apply_implsort_impl252 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> applysort_impl257 static constexpr auto apply(Xs&& xs, Pred const&) { 258 constexpr std::size_t Len = decltype(hana::length(xs))::value; 259 using Indices = typename detail::merge_sort_impl< 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> applysort_impl268 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 274