]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Forward declares `boost::hana::Orderable`. | |
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_CONCEPT_ORDERABLE_HPP | |
11 | #define BOOST_HANA_FWD_CONCEPT_ORDERABLE_HPP | |
12 | ||
13 | #include <boost/hana/config.hpp> | |
14 | ||
15 | ||
16 | BOOST_HANA_NAMESPACE_BEGIN | |
17 | //! @ingroup group-concepts | |
18 | //! @defgroup group-Orderable Orderable | |
19 | //! The `Orderable` concept represents totally ordered data types. | |
20 | //! | |
21 | //! Intuitively, `Orderable` objects must define a binary predicate named | |
22 | //! `less` returning whether the first argument is to be considered less | |
23 | //! than the second argument. The word "total" means that _distinct_ | |
24 | //! objects must always be ordered; if `a` and `b` are not equal, then | |
25 | //! exactly one of `less(a, b)` and `less(b, a)` must be true. This is | |
26 | //! a contrast with weaker kinds of orders that would allow some objects | |
27 | //! to be incomparable (neither less than nor greater than). Also note | |
28 | //! that a non-strict total order may always be obtained from a strict | |
29 | //! total order (and vice-versa) by setting | |
30 | //! @code | |
31 | //! a <= b = !(b < a) | |
32 | //! a < b = !(b <= a) | |
33 | //! @endcode | |
34 | //! The non-strict version is used in the description of the laws because | |
35 | //! it makes them easier to parse for humans, but they could be formulated | |
36 | //! equivalently using the strict order. | |
37 | //! | |
38 | //! | |
39 | //! Minimal complete definition | |
40 | //! --------------------------- | |
41 | //! `less` | |
42 | //! | |
43 | //! When `less` is defined, the other methods are defined from it using | |
44 | //! the same definition as mandated in the laws below. | |
45 | //! | |
46 | //! | |
47 | //! Laws | |
48 | //! ---- | |
49 | //! Rigorously speaking, a [total order][1] `<=` on a set `S` is a binary | |
50 | //! predicate @f$ <= \;: S \times S \to bool @f$ such that for all | |
51 | //! `a`, `b`, `c` in `S`, | |
52 | //! @code | |
53 | //! if a <= b and b <= a then a == b // Antisymmetry | |
54 | //! if a <= b and b <= c then a <= c // Transitivity | |
55 | //! either a <= b or b <= a // Totality | |
56 | //! @endcode | |
57 | //! Additionally, the `less`, `greater` and `greater_equal` methods should | |
58 | //! have the following intuitive meanings: | |
59 | //! @code | |
60 | //! a < b if and only if !(b <= a) | |
61 | //! a > b if and only if b < a | |
62 | //! a >= b if and only if !(a < b) | |
63 | //! @endcode | |
64 | //! | |
65 | //! | |
66 | //! Refined concept | |
67 | //! --------------- | |
68 | //! 1. `Comparable` (free model)\n | |
69 | //! Since `Orderable` requires `less_equal` to be a total order, a model | |
70 | //! of `Comparable` may always be obtained by setting | |
71 | //! @code | |
72 | //! equal(x, y) = less_equal(x, y) && less_equal(y, x) | |
73 | //! @endcode | |
74 | //! | |
75 | //! | |
76 | //! Concrete models | |
77 | //! --------------- | |
78 | //! `hana::integral_constant`, `hana::optional`, `hana::pair`, | |
79 | //! `hana::string`, `hana::tuple` | |
80 | //! | |
81 | //! | |
82 | //! Free model for `LessThanComparable` data types | |
83 | //! ---------------------------------------------- | |
84 | //! Two data types `T` and `U` that model the cross-type version of the | |
85 | //! usual [LessThanComparable][2] C++ concept are automatically a model | |
86 | //! of `Orderable` by setting | |
87 | //! @code | |
88 | //! less(x, y) = (x < y) | |
89 | //! @endcode | |
90 | //! The cross-type version of the LessThanComparable concept is analogous | |
91 | //! to the cross-type version of the EqualityComparable concept presented | |
92 | //! in [N3351][3], which is compatible with the usual single type | |
93 | //! definition. | |
94 | //! However, note that the LessThanComparable concept only requires `<` | |
95 | //! to be a [strict weak ordering][4], which is a weaker requirement | |
96 | //! than being a total order. Hence, if `less` is used with objects | |
97 | //! of a LessThanComparable data type that do not define a total order, | |
98 | //! some algorithms may have an unexpected behavior. It is the author's | |
99 | //! opinion that defining `operator<` as a non-total order is a bad idea, | |
100 | //! but this is debatable and so the design choice of providing a model | |
101 | //! for LessThanComparable data types is open to debate. Waiting for | |
102 | //! some user input. | |
103 | //! | |
104 | //! | |
105 | //! Order-preserving functions | |
106 | //! -------------------------- | |
107 | //! Let `A` and `B` be two `Orderable` data types. A function | |
108 | //! @f$ f : A \to B@f$ is said to be order-preserving (also called | |
109 | //! monotone) if it preserves the structure of the `Orderable` concept, | |
110 | //! which can be rigorously stated as follows. For all objects `x`, `y` | |
111 | //! of data type `A`, | |
112 | //! @code | |
113 | //! if less(x, y) then less(f(x), f(y)) | |
114 | //! @endcode | |
115 | //! Another important property is that of being order-reflecting, which | |
116 | //! can be stated as | |
117 | //! @code | |
118 | //! if less(f(x), f(y)) then less(x, y) | |
119 | //! @endcode | |
120 | //! We say that a function is an order-embedding if it is both | |
121 | //! order-preserving and order-reflecting, i.e. if | |
122 | //! @code | |
123 | //! less(x, y) if and only if less(f(x), f(y)) | |
124 | //! @endcode | |
125 | //! | |
126 | //! | |
127 | //! Cross-type version of the methods | |
128 | //! --------------------------------- | |
129 | //! The comparison methods (`less`, `less_equal`, `greater` and | |
130 | //! `greater_equal`) are "overloaded" to handle distinct data types | |
131 | //! with certain properties. Specifically, they are defined for | |
132 | //! _distinct_ data types `A` and `B` such that | |
133 | //! 1. `A` and `B` share a common data type `C`, as determined by the | |
134 | //! `common` metafunction | |
135 | //! 2. `A`, `B` and `C` are all `Orderable` when taken individually | |
136 | //! 3. @f$\mathrm{to<C>} : A \to C@f$ and @f$\mathrm{to<C>} : B \to C@f$ | |
137 | //! are both order-embeddings as determined by the `is_embedding` | |
138 | //! metafunction. | |
139 | //! | |
140 | //! The method definitions for data types satisfying the above | |
141 | //! properties are | |
142 | //! @code | |
143 | //! less(x, y) = less(to<C>(x), to<C>(y)) | |
144 | //! less_equal(x, y) = less_equal(to<C>(x), to<C>(y)) | |
145 | //! greater_equal(x, y) = greater_equal(to<C>(x), to<C>(y)) | |
146 | //! greater(x, y) = greater(to<C>(x), to<C>(y)) | |
147 | //! @endcode | |
148 | //! | |
149 | //! | |
150 | //! Partial application of the methods | |
151 | //! ---------------------------------- | |
152 | //! The `less`, `greater`, `less_equal` and `greater_equal` methods can | |
153 | //! be called in two different ways. First, they can be called like | |
154 | //! normal functions: | |
155 | //! @code | |
156 | //! less(x, y) | |
157 | //! greater(x, y) | |
158 | //! | |
159 | //! less_equal(x, y) | |
160 | //! greater_equal(x, y) | |
161 | //! @endcode | |
162 | //! | |
163 | //! However, they may also be partially applied to an argument as follows: | |
164 | //! @code | |
165 | //! less.than(x)(y) == less(y, x) | |
166 | //! greater.than(x)(y) == greater(y, x) | |
167 | //! | |
168 | //! less_equal.than(x)(y) == less_equal(y, x) | |
169 | //! greater_equal.than(x)(y) == greater_equal(y, x) | |
170 | //! @endcode | |
171 | //! | |
172 | //! Take good note that the order of the arguments is reversed, so | |
173 | //! for example `less.than(x)(y)` is equivalent to `less(y, x)`, not | |
174 | //! `less(x, y)`. This is because those variants are meant to be used | |
175 | //! with higher order algorithms, where the chosen application order | |
176 | //! makes sense. | |
177 | //! | |
178 | //! | |
179 | //! [1]: http://en.wikipedia.org/wiki/Total_order | |
180 | //! [2]: http://en.cppreference.com/w/cpp/concept/LessThanComparable | |
181 | //! [3]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf | |
182 | //! [4]: http://en.wikipedia.org/wiki/Strict_weak_ordering | |
183 | template <typename Ord> | |
184 | struct Orderable; | |
185 | BOOST_HANA_NAMESPACE_END | |
186 | ||
187 | #endif // !BOOST_HANA_FWD_CONCEPT_ORDERABLE_HPP |