1 /*! 2 @file 3 Forward declares `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_FWD_SORT_HPP 11 #define BOOST_HANA_FWD_SORT_HPP 12 13 #include <boost/hana/config.hpp> 14 #include <boost/hana/core/when.hpp> 15 #include <boost/hana/detail/nested_by_fwd.hpp> 16 17 18 BOOST_HANA_NAMESPACE_BEGIN 19 //! Sort a sequence, optionally based on a custom `predicate`. 20 //! @ingroup group-Sequence 21 //! 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. 27 //! 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. 32 //! 33 //! If no predicate is provided, the elements in the sequence must all be 34 //! compile-time `Orderable`. 35 //! 36 //! Signature 37 //! --------- 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, 41 //! \f[ 42 //! \mathtt{sort} : S(T) \times (T \times T \to Bool) \to S(T) 43 //! \f] 44 //! 45 //! for the variant without a custom predicate, `T` is required to be 46 //! `Orderable`. The signature is then 47 //! \f[ 48 //! \mathtt{sort} : S(T) \to S(T) 49 //! \f] 50 //! 51 //! @param xs 52 //! The sequence to sort. 53 //! 54 //! @param predicate 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`. 63 //! 64 //! 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: 69 //! @code 70 //! sort.by(predicate, xs) == sort(xs, predicate) 71 //! sort.by(predicate) == sort(-, predicate) 72 //! @endcode 73 //! 74 //! where `sort(-, predicate)` denotes the partial application of 75 //! `sort` to `predicate`. 76 //! 77 //! 78 //! Example 79 //! ------- 80 //! @include example/sort.cpp 81 //! 82 //! [1]: http://en.wikipedia.org/wiki/Strict_weak_ordering 83 #ifdef BOOST_HANA_DOXYGEN_INVOKED __anon983f9b9a0102(auto&& xs[, auto&& predicate]) 84 constexpr auto sort = [](auto&& xs[, auto&& predicate]) { 85 return tag-dispatched; 86 }; 87 #else 88 template <typename S, typename = void> 89 struct sort_impl : sort_impl<S, when<true>> { }; 90 91 struct sort_t : detail::nested_by<sort_t> { 92 template <typename Xs> 93 constexpr auto operator()(Xs&& xs) const; 94 95 template <typename Xs, typename Predicate> 96 constexpr auto operator()(Xs&& xs, Predicate&& pred) const; 97 }; 98 99 constexpr sort_t sort{}; 100 #endif 101 BOOST_HANA_NAMESPACE_END 102 103 #endif // !BOOST_HANA_FWD_SORT_HPP 104