]>
Commit | Line | Data |
---|---|---|
1 | /*! | |
2 | @file | |
3 | Forward declares `boost::hana::lexicographical_compare`. | |
4 | ||
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) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_FWD_LEXICOGRAPHICAL_COMPARE_HPP | |
11 | #define BOOST_HANA_FWD_LEXICOGRAPHICAL_COMPARE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | #include <boost/hana/core/when.hpp> | |
15 | ||
16 | ||
17 | BOOST_HANA_NAMESPACE_BEGIN | |
18 | //! Short-circuiting lexicographical comparison of two `Iterable`s with | |
19 | //! an optional custom predicate, by default `hana::less`. | |
20 | //! @ingroup group-Iterable | |
21 | //! | |
22 | //! Given two `Iterable`s `xs` and `ys` and a binary predicate `pred`, | |
23 | //! `lexicographical_compare` returns whether `xs` is to be considered | |
24 | //! less than `ys` in a lexicographical ordering. Specifically, let's | |
25 | //! denote the linearizations of `xs` and `ys` by `[x1, x2, ...]` and | |
26 | //! `[y1, y2, ...]`, respectively. If the first couple satisfying the | |
27 | //! predicate is of the form `xi, yi`, `lexicographical_compare` returns | |
28 | //! true. Otherwise, if the first couple to satisfy the predicate is of | |
29 | //! the form `yi, xi`, `lexicographical_compare` returns false. If no | |
30 | //! such couple can be found, `lexicographical_compare` returns whether | |
31 | //! `xs` has fewer elements than `ys`. | |
32 | //! | |
33 | //! @note | |
34 | //! This algorithm will short-circuit as soon as it can determine that one | |
35 | //! sequence is lexicographically less than the other. Hence, it can be | |
36 | //! used to compare infinite sequences. However, for the procedure to | |
37 | //! terminate on infinite sequences, the predicate has to be satisfied | |
38 | //! at a finite index. | |
39 | //! | |
40 | //! | |
41 | //! Signature | |
42 | //! --------- | |
43 | //! Given two `Iterable`s `It1(T)` and `It2(T)` and a predicate | |
44 | //! \f$ pred : T \times T \to Bool \f$ (where `Bool` is some `Logical`), | |
45 | //! `lexicographical_compare` has the following signatures. For the | |
46 | //! variant with a provided predicate, | |
47 | //! \f[ | |
48 | //! \mathtt{lexicographical\_compare} | |
49 | //! : It1(T) \times It2(T) \times (T \times T \to Bool) \to Bool | |
50 | //! \f] | |
51 | //! | |
52 | //! for the variant without a custom predicate, `T` is required to be | |
53 | //! `Orderable`. The signature is then | |
54 | //! \f[ | |
55 | //! \mathtt{lexicographical\_compare} : It1(T) \times It2(T) \to Bool | |
56 | //! \f] | |
57 | //! | |
58 | //! @param xs, ys | |
59 | //! Two `Iterable`s to compare lexicographically. | |
60 | //! | |
61 | //! @param pred | |
62 | //! A binary function called as `pred(x, y)` and `pred(y, x)`, where `x` | |
63 | //! and `y` are elements of `xs` and `ys`, respectively. `pred` must | |
64 | //! return a `Logical` representing whether its first argument is to be | |
65 | //! considered as less than its second argument. Also note that `pred` | |
66 | //! must define a total ordering as defined by the `Orderable` concept. | |
67 | //! When `pred` is not provided, it defaults to `less`. | |
68 | //! | |
69 | //! | |
70 | //! Example | |
71 | //! ------- | |
72 | //! @include example/lexicographical_compare.cpp | |
73 | #ifdef BOOST_HANA_DOXYGEN_INVOKED | |
74 | constexpr auto lexicographical_compare = [](auto const& xs, auto const& ys, auto const& pred = hana::less) { | |
75 | return tag-dispatched; | |
76 | }; | |
77 | #else | |
78 | template <typename T, typename = void> | |
79 | struct lexicographical_compare_impl : lexicographical_compare_impl<T, when<true>> { }; | |
80 | ||
81 | struct lexicographical_compare_t { | |
82 | template <typename Xs, typename Ys> | |
83 | constexpr auto operator()(Xs const& xs, Ys const& ys) const; | |
84 | ||
85 | template <typename Xs, typename Ys, typename Pred> | |
86 | constexpr auto operator()(Xs const& xs, Ys const& ys, Pred const& pred) const; | |
87 | }; | |
88 | ||
89 | constexpr lexicographical_compare_t lexicographical_compare{}; | |
90 | #endif | |
91 | BOOST_HANA_NAMESPACE_END | |
92 | ||
93 | #endif // !BOOST_HANA_FWD_LEXICOGRAPHICAL_COMPARE_HPP |