boost/hana/sort.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::sort`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_SORT_HPP
0011 #define BOOST_HANA_SORT_HPP
0012
0013 #include <boost/hana/fwd/sort.hpp>
0014
0015 #include <boost/hana/at.hpp>
0016 #include <boost/hana/concept/sequence.hpp>
0017 #include <boost/hana/config.hpp>
0018 #include <boost/hana/core/dispatch.hpp>
0019 #include <boost/hana/core/make.hpp>
0020 #include <boost/hana/detail/nested_by.hpp> // required by fwd decl
0021 #include <boost/hana/length.hpp>
0022 #include <boost/hana/less.hpp>
0023
0024 #include <utility> // std::declval, std::index_sequence
0025
0026
0027 namespace boost { namespace hana {
0028     //! @cond
0029     template <typename Xs, typename Predicate>
0030     constexpr auto sort_t::operator()(Xs&& xs, Predicate&& pred) const {
0031         using S = typename hana::tag_of<Xs>::type;
0032         using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
0033             hana::Sequence<S>::value
0034         );
0035
0036     #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
0037         static_assert(hana::Sequence<S>::value,
0038         "hana::sort(xs, predicate) requires 'xs' to be a Sequence");
0039     #endif
0040
0041         return Sort::apply(static_cast<Xs&&>(xs),
0042                            static_cast<Predicate&&>(pred));
0043     }
0044
0045     template <typename Xs>
0046     constexpr auto sort_t::operator()(Xs&& xs) const {
0047         using S = typename hana::tag_of<Xs>::type;
0048         using Sort = BOOST_HANA_DISPATCH_IF(sort_impl<S>,
0049             hana::Sequence<S>::value
0050         );
0051
0052     #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
0053         static_assert(hana::Sequence<S>::value,
0054         "hana::sort(xs) requires 'xs' to be a Sequence");
0055     #endif
0056
0057         return Sort::apply(static_cast<Xs&&>(xs));
0058     }
0059     //! @endcond
0060
0061     namespace detail {
0062         template <typename Xs, typename Pred>
0063         struct sort_predicate {
0064             template <std::size_t I, std::size_t J>
0065             using apply = decltype(std::declval<Pred>()(
0066                 hana::at_c<I>(std::declval<Xs>()),
0067                 hana::at_c<J>(std::declval<Xs>())
0068             ));
0069         };
0070
0071         template <typename Left, typename Right>
0072         struct concat;
0073
0074         template <std::size_t ...l, std::size_t ...r>
0075         struct concat<std::index_sequence<l...>, std::index_sequence<r...>> {
0076             using type = std::index_sequence<l..., r...>;
0077         };
0078
0079         template <typename Pred, bool PickRight, typename Left, typename Right>
0080         struct merge;
0081
0082         template <
0083             typename Pred,
0084             std::size_t l0,
0085             std::size_t l1,
0086             std::size_t ...l,
0087             std::size_t r0,
0088             std::size_t ...r>
0089         struct merge<
0090             Pred,
0091             false,
0092             std::index_sequence<l0, l1, l...>,
0093             std::index_sequence<r0, r...>
0094         > {
0095             using type = typename concat<
0096                 std::index_sequence<l0>,
0097                 typename merge<
0098                     Pred,
0099                     (bool)Pred::template apply<r0, l1>::value,
0100                     std::index_sequence<l1, l...>,
0101                     std::index_sequence<r0, r...>
0102                 >::type
0103             >::type;
0104         };
0105
0106         template <
0107             typename Pred,
0108             std::size_t l0,
0109             std::size_t r0,
0110             std::size_t ...r>
0111         struct merge<
0112             Pred,
0113             false,
0114             std::index_sequence<l0>,
0115             std::index_sequence<r0, r...>
0116         > {
0117             using type = std::index_sequence<l0, r0, r...>;
0118         };
0119
0120         template <
0121             typename Pred,
0122             std::size_t l0,
0123             std::size_t ...l,
0124             std::size_t r0,
0125             std::size_t r1,
0126             std::size_t ...r>
0127         struct merge<
0128             Pred,
0129             true,
0130             std::index_sequence<l0, l...>,
0131             std::index_sequence<r0, r1, r...>
0132         > {
0133             using type = typename concat<
0134                 std::index_sequence<r0>,
0135                 typename merge<
0136                     Pred,
0137                     (bool)Pred::template apply<r1, l0>::value,
0138                     std::index_sequence<l0, l...>,
0139                     std::index_sequence<r1, r...>
0140                 >::type
0141             >::type;
0142         };
0143
0144         template <
0145             typename Pred,
0146             std::size_t l0,
0147             std::size_t ...l,
0148             std::size_t r0>
0149         struct merge<
0150             Pred,
0151             true,
0152             std::index_sequence<l0, l...>,
0153             std::index_sequence<r0>
0154         > {
0155             using type = std::index_sequence<r0, l0, l...>;
0156         };
0157
0158         template <typename Pred, typename Left, typename Right>
0159         struct merge_helper;
0160
0161         template <
0162             typename Pred,
0163             std::size_t l0,
0164             std::size_t ...l,
0165             std::size_t r0,
0166             std::size_t ...r>
0167         struct merge_helper<
0168             Pred,
0169             std::index_sequence<l0, l...>,
0170             std::index_sequence<r0, r...>
0171         > {
0172             using type = typename merge<
0173                 Pred,
0174                 (bool)Pred::template apply<r0, l0>::value,
0175                 std::index_sequence<l0, l...>,
0176                 std::index_sequence<r0, r...>
0177             >::type;
0178         };
0179
0180         // split templated structure, Nr represents the number of elements
0181         // from Right to move to Left
0182         // There are two specializations:
0183         // The first handles the generic case (Nr > 0)
0184         // The second handles the stop condition (Nr == 0)
0185         // These two specializations are not strictly ordered as
0186         //   the first cannot match Nr==0 && empty Right
0187         //   the second cannot match Nr!=0
0188         // std::enable_if<Nr!=0> is therefore required to make sure these two
0189         // specializations will never both be candidates during an overload
0190         // resolution (otherwise ambiguity occurs for Nr==0 and non-empty Right)
0191         template <std::size_t Nr, typename Left, typename Right, typename=void>
0192         struct split;
0193
0194         template <
0195             std::size_t Nr,
0196             std::size_t ...l,
0197             std::size_t ...r,
0198             std::size_t r0>
0199         struct split<
0200             Nr,
0201             std::index_sequence<l...>,
0202             std::index_sequence<r0, r...>,
0203             typename std::enable_if<Nr!=0>::type
0204         > {
0205             using sp = split<
0206                 Nr-1,
0207                 std::index_sequence<l..., r0>,
0208                 std::index_sequence<r...>
0209             >;
0210             using left = typename sp::left;
0211             using right = typename sp::right;
0212         };
0213
0214         template <std::size_t ...l, std::size_t ...r>
0215         struct split<0, std::index_sequence<l...>, std::index_sequence<r...>> {
0216             using left = std::index_sequence<l...>;
0217             using right = std::index_sequence<r...>;
0218         };
0219
0220         template <typename Pred, typename Sequence>
0221         struct merge_sort_impl;
0222
0223         template <typename Pred, std::size_t ...seq>
0224         struct merge_sort_impl<Pred, std::index_sequence<seq...>> {
0225             using sequence = std::index_sequence<seq...>;
0226             using sp = split<
0227                 sequence::size() / 2,
0228                 std::index_sequence<>,
0229                 sequence
0230             >;
0231             using type = typename merge_helper<
0232                 Pred,
0233                 typename merge_sort_impl<Pred, typename sp::left>::type,
0234                 typename merge_sort_impl<Pred, typename sp::right>::type
0235             >::type;
0236         };
0237
0238         template <typename Pred, std::size_t x>
0239         struct merge_sort_impl<Pred, std::index_sequence<x>> {
0240             using type = std::index_sequence<x>;
0241         };
0242
0243         template <typename Pred>
0244         struct merge_sort_impl<Pred, std::index_sequence<>> {
0245             using type = std::index_sequence<>;
0246         };
0247     } // end namespace detail
0248
0249     template <typename S, bool condition>
0250     struct sort_impl<S, when<condition>> : default_ {
0251         template <typename Xs, std::size_t ...i>
0252         static constexpr auto apply_impl(Xs&& xs, std::index_sequence<i...>) {
0253             return hana::make<S>(hana::at_c<i>(static_cast<Xs&&>(xs))...);
0254         }
0255
0256         template <typename Xs, typename Pred>
0257         static constexpr auto apply(Xs&& xs, Pred const&) {
0258             constexpr std::size_t Len = decltype(hana::length(xs))::value;
0259             using Indices = typename detail::merge_sort_impl<
0260                 detail::sort_predicate<Xs&&, Pred>,
0261                 std::make_index_sequence<Len>
0262             >::type;
0263
0264             return apply_impl(static_cast<Xs&&>(xs), Indices{});
0265         }
0266
0267         template <typename Xs>
0268         static constexpr auto apply(Xs&& xs)
0269         { return sort_impl::apply(static_cast<Xs&&>(xs), hana::less); }
0270     };
0271 }} // end namespace boost::hana
0272
0273 #endif // !BOOST_HANA_SORT_HPP