Edit: /usr/include/boost/hana/sort.hpp (8855B)
/*!
@file
Defines `boost::hana::sort`.
@copyright Louis Dionne 2013-2017
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
*/
#ifndef BOOST_HANA_SORT_HPP
#define BOOST_HANA_SORT_HPP
#include
#include
#include
#include
#include
#include
#include // required by fwd decl
#include
#include
#include // std::declval, std::index_sequence
BOOST_HANA_NAMESPACE_BEGIN
//! @cond
template
constexpr auto sort_t::operator()(Xs&& xs, Predicate&& pred) const {
using S = typename hana::tag_of::type;
using Sort = BOOST_HANA_DISPATCH_IF(sort_impl,
hana::Sequence::value
);
#ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
static_assert(hana::Sequence::value,
"hana::sort(xs, predicate) requires 'xs' to be a Sequence");
#endif
return Sort::apply(static_cast(xs),
static_cast(pred));
}
template
constexpr auto sort_t::operator()(Xs&& xs) const {
using S = typename hana::tag_of::type;
using Sort = BOOST_HANA_DISPATCH_IF(sort_impl,
hana::Sequence::value
);
#ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
static_assert(hana::Sequence::value,
"hana::sort(xs) requires 'xs' to be a Sequence");
#endif
return Sort::apply(static_cast(xs));
}
//! @endcond
namespace detail {
template
struct sort_predicate {
template
using apply = decltype(std::declval()(
hana::at_c(std::declval()),
hana::at_c(std::declval())
));
};
template
struct concat;
template
struct concat, std::index_sequence> {
using type = std::index_sequence;
};
template
struct merge;
template <
typename Pred,
std::size_t l0,
std::size_t l1,
std::size_t ...l,
std::size_t r0,
std::size_t ...r>
struct merge<
Pred,
false,
std::index_sequence,
std::index_sequence
> {
using type = typename concat<
std::index_sequence,
typename merge<
Pred,
(bool)Pred::template apply::value,
std::index_sequence,
std::index_sequence
>::type
>::type;
};
template <
typename Pred,
std::size_t l0,
std::size_t r0,
std::size_t ...r>
struct merge<
Pred,
false,
std::index_sequence,
std::index_sequence
> {
using type = std::index_sequence;
};
template <
typename Pred,
std::size_t l0,
std::size_t ...l,
std::size_t r0,
std::size_t r1,
std::size_t ...r>
struct merge<
Pred,
true,
std::index_sequence,
std::index_sequence
> {
using type = typename concat<
std::index_sequence,
typename merge<
Pred,
(bool)Pred::template apply::value,
std::index_sequence,
std::index_sequence
>::type
>::type;
};
template <
typename Pred,
std::size_t l0,
std::size_t ...l,
std::size_t r0>
struct merge<
Pred,
true,
std::index_sequence,
std::index_sequence
> {
using type = std::index_sequence;
};
template
struct merge_helper;
template <
typename Pred,
std::size_t l0,
std::size_t ...l,
std::size_t r0,
std::size_t ...r>
struct merge_helper<
Pred,
std::index_sequence,
std::index_sequence
> {
using type = typename merge<
Pred,
(bool)Pred::template apply::value,
std::index_sequence,
std::index_sequence
>::type;
};
// split templated structure, Nr represents the number of elements
// from Right to move to Left
// There are two specializations:
// The first handles the generic case (Nr > 0)
// The second handles the stop condition (Nr == 0)
// These two specializations are not strictly ordered as
// the first cannot match Nr==0 && empty Right
// the second cannot match Nr!=0
// std::enable_if is therefore required to make sure these two
// specializations will never both be candidates during an overload
// resolution (otherwise ambiguity occurs for Nr==0 and non-empty Right)
template
struct split;
template <
std::size_t Nr,
std::size_t ...l,
std::size_t ...r,
std::size_t r0>
struct split<
Nr,
std::index_sequence,
std::index_sequence,
typename std::enable_if::type
> {
using sp = split<
Nr-1,
std::index_sequence,
std::index_sequence
>;
using left = typename sp::left;
using right = typename sp::right;
};
template
struct split<0, std::index_sequence, std::index_sequence> {
using left = std::index_sequence;
using right = std::index_sequence;
};
template
struct merge_sort_impl;
template
struct merge_sort_impl> {
using sequence = std::index_sequence;
using sp = split<
sequence::size() / 2,
std::index_sequence<>,
sequence
>;
using type = typename merge_helper<
Pred,
typename merge_sort_impl::type,
typename merge_sort_impl::type
>::type;
};
template
struct merge_sort_impl> {
using type = std::index_sequence;
};
template
struct merge_sort_impl> {
using type = std::index_sequence<>;
};
} // end namespace detail
template
struct sort_impl> : default_ {
template
static constexpr auto apply_impl(Xs&& xs, std::index_sequence) {
return hana::make(hana::at_c(static_cast(xs))...);
}
template
static constexpr auto apply(Xs&& xs, Pred const&) {
constexpr std::size_t Len = decltype(hana::length(xs))::value;
using Indices = typename detail::merge_sort_impl<
detail::sort_predicate,
std::make_index_sequence
>::type;
return apply_impl(static_cast(xs), Indices{});
}
template
static constexpr auto apply(Xs&& xs)
{ return sort_impl::apply(static_cast(xs), hana::less); }
};
BOOST_HANA_NAMESPACE_END
#endif // !BOOST_HANA_SORT_HPP