3 Forward declares `boost::hana::sort`.
5 @copyright Louis Dionne 2013-2016
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)
10 #ifndef BOOST_HANA_FWD_SORT_HPP
11 #define BOOST_HANA_FWD_SORT_HPP
13 #include <boost/hana/config.hpp>
14 #include <boost/hana/core/when.hpp>
15 #include <boost/hana/detail/nested_by_fwd.hpp>
18 BOOST_HANA_NAMESPACE_BEGIN
19 //! Sort a sequence, optionally based on a custom `predicate`.
20 //! @ingroup group-Sequence
22 //! Given a Sequence and an optional predicate (by default `less`), `sort`
23 //! returns a new sequence containing the same elements as the original,
24 //! except they are ordered in such a way that if `x` comes before `y` in
25 //! the sequence, then either `predicate(x, y)` is true, or both
26 //! `predicate(x, y)` and `predicate(y, x)` are false.
28 //! Also note that the sort is guaranteed to be stable. Hence, if `x`
29 //! comes before `y` in the original sequence and both `predicate(x, y)`
30 //! and `predicate(y, x)` are false, then `x` will come before `y` in the
31 //! resulting sequence.
33 //! If no predicate is provided, the elements in the sequence must all be
34 //! compile-time `Orderable`.
38 //! Given a `Sequence` `S(T)`, a boolean `IntegralConstant` `Bool` and a
39 //! binary predicate \f$ T \times T \to Bool \f$, `sort` has the following
40 //! signatures. For the variant with a provided predicate,
42 //! \mathtt{sort} : S(T) \times (T \times T \to Bool) \to S(T)
45 //! for the variant without a custom predicate, `T` is required to be
46 //! `Orderable`. The signature is then
48 //! \mathtt{sort} : S(T) \to S(T)
52 //! The sequence to sort.
55 //! A function called as `predicate(x, y)` for two elements `x` and `y` of
56 //! the sequence, and returning a boolean `IntegralConstant` representing
57 //! whether `x` is to be considered _less_ than `y`, i.e. whether `x` should
58 //! appear _before_ `y` in the resulting sequence. More specifically,
59 //! `predicate` must define a [strict weak ordering][1] on the elements
60 //! of the sequence. When the predicate is not specified, this defaults
61 //! to `less`. In the current version of the library, the predicate has
62 //! to return an `IntegralConstant` holding a value convertible to a `bool`.
65 //! Syntactic sugar (`sort.by`)
66 //! ---------------------------
67 //! `sort` can be called in a third way, which provides a nice syntax
68 //! especially when working with the `ordering` combinator:
70 //! sort.by(predicate, xs) == sort(xs, predicate)
71 //! sort.by(predicate) == sort(-, predicate)
74 //! where `sort(-, predicate)` denotes the partial application of
75 //! `sort` to `predicate`.
80 //! @include example/sort.cpp
82 //! [1]: http://en.wikipedia.org/wiki/Strict_weak_ordering
83 #ifdef BOOST_HANA_DOXYGEN_INVOKED
84 constexpr auto sort = [](auto&& xs[, auto&& predicate]) {
85 return tag-dispatched;
88 template <typename S, typename = void>
89 struct sort_impl : sort_impl<S, when<true>> { };
91 struct sort_t : detail::nested_by<sort_t> {
92 template <typename Xs>
93 constexpr auto operator()(Xs&& xs) const;
95 template <typename Xs, typename Predicate>
96 constexpr auto operator()(Xs&& xs, Predicate&& pred) const;
99 constexpr sort_t sort{};
101 BOOST_HANA_NAMESPACE_END
103 #endif // !BOOST_HANA_FWD_SORT_HPP