boost/hana/sort.hpp

   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>
  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 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>
 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;
 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>
 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