summaryrefslogtreecommitdiff
path: root/boost/hana/fwd/concept/orderable.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/hana/fwd/concept/orderable.hpp')
-rw-r--r--boost/hana/fwd/concept/orderable.hpp187
1 files changed, 187 insertions, 0 deletions
diff --git a/boost/hana/fwd/concept/orderable.hpp b/boost/hana/fwd/concept/orderable.hpp
new file mode 100644
index 0000000000..ed381de94a
--- /dev/null
+++ b/boost/hana/fwd/concept/orderable.hpp
@@ -0,0 +1,187 @@
+/*!
+@file
+Forward declares `boost::hana::Orderable`.
+
+@copyright Louis Dionne 2013-2016
+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_FWD_CONCEPT_ORDERABLE_HPP
+#define BOOST_HANA_FWD_CONCEPT_ORDERABLE_HPP
+
+#include <boost/hana/config.hpp>
+
+
+BOOST_HANA_NAMESPACE_BEGIN
+ //! @ingroup group-concepts
+ //! @defgroup group-Orderable Orderable
+ //! The `Orderable` concept represents totally ordered data types.
+ //!
+ //! Intuitively, `Orderable` objects must define a binary predicate named
+ //! `less` returning whether the first argument is to be considered less
+ //! than the second argument. The word "total" means that _distinct_
+ //! objects must always be ordered; if `a` and `b` are not equal, then
+ //! exactly one of `less(a, b)` and `less(b, a)` must be true. This is
+ //! a contrast with weaker kinds of orders that would allow some objects
+ //! to be incomparable (neither less than nor greater than). Also note
+ //! that a non-strict total order may always be obtained from a strict
+ //! total order (and vice-versa) by setting
+ //! @code
+ //! a <= b = !(b < a)
+ //! a < b = !(b <= a)
+ //! @endcode
+ //! The non-strict version is used in the description of the laws because
+ //! it makes them easier to parse for humans, but they could be formulated
+ //! equivalently using the strict order.
+ //!
+ //!
+ //! Minimal complete definition
+ //! ---------------------------
+ //! `less`
+ //!
+ //! When `less` is defined, the other methods are defined from it using
+ //! the same definition as mandated in the laws below.
+ //!
+ //!
+ //! Laws
+ //! ----
+ //! Rigorously speaking, a [total order][1] `<=` on a set `S` is a binary
+ //! predicate @f$ <= \;: S \times S \to bool @f$ such that for all
+ //! `a`, `b`, `c` in `S`,
+ //! @code
+ //! if a <= b and b <= a then a == b // Antisymmetry
+ //! if a <= b and b <= c then a <= c // Transitivity
+ //! either a <= b or b <= a // Totality
+ //! @endcode
+ //! Additionally, the `less`, `greater` and `greater_equal` methods should
+ //! have the following intuitive meanings:
+ //! @code
+ //! a < b if and only if !(b <= a)
+ //! a > b if and only if b < a
+ //! a >= b if and only if !(a < b)
+ //! @endcode
+ //!
+ //!
+ //! Refined concept
+ //! ---------------
+ //! 1. `Comparable` (free model)\n
+ //! Since `Orderable` requires `less_equal` to be a total order, a model
+ //! of `Comparable` may always be obtained by setting
+ //! @code
+ //! equal(x, y) = less_equal(x, y) && less_equal(y, x)
+ //! @endcode
+ //!
+ //!
+ //! Concrete models
+ //! ---------------
+ //! `hana::integral_constant`, `hana::optional`, `hana::pair`,
+ //! `hana::string`, `hana::tuple`
+ //!
+ //!
+ //! Free model for `LessThanComparable` data types
+ //! ----------------------------------------------
+ //! Two data types `T` and `U` that model the cross-type version of the
+ //! usual [LessThanComparable][2] C++ concept are automatically a model
+ //! of `Orderable` by setting
+ //! @code
+ //! less(x, y) = (x < y)
+ //! @endcode
+ //! The cross-type version of the LessThanComparable concept is analogous
+ //! to the cross-type version of the EqualityComparable concept presented
+ //! in [N3351][3], which is compatible with the usual single type
+ //! definition.
+ //! However, note that the LessThanComparable concept only requires `<`
+ //! to be a [strict weak ordering][4], which is a weaker requirement
+ //! than being a total order. Hence, if `less` is used with objects
+ //! of a LessThanComparable data type that do not define a total order,
+ //! some algorithms may have an unexpected behavior. It is the author's
+ //! opinion that defining `operator<` as a non-total order is a bad idea,
+ //! but this is debatable and so the design choice of providing a model
+ //! for LessThanComparable data types is open to debate. Waiting for
+ //! some user input.
+ //!
+ //!
+ //! Order-preserving functions
+ //! --------------------------
+ //! Let `A` and `B` be two `Orderable` data types. A function
+ //! @f$ f : A \to B@f$ is said to be order-preserving (also called
+ //! monotone) if it preserves the structure of the `Orderable` concept,
+ //! which can be rigorously stated as follows. For all objects `x`, `y`
+ //! of data type `A`,
+ //! @code
+ //! if less(x, y) then less(f(x), f(y))
+ //! @endcode
+ //! Another important property is that of being order-reflecting, which
+ //! can be stated as
+ //! @code
+ //! if less(f(x), f(y)) then less(x, y)
+ //! @endcode
+ //! We say that a function is an order-embedding if it is both
+ //! order-preserving and order-reflecting, i.e. if
+ //! @code
+ //! less(x, y) if and only if less(f(x), f(y))
+ //! @endcode
+ //!
+ //!
+ //! Cross-type version of the methods
+ //! ---------------------------------
+ //! The comparison methods (`less`, `less_equal`, `greater` and
+ //! `greater_equal`) are "overloaded" to handle distinct data types
+ //! with certain properties. Specifically, they are defined for
+ //! _distinct_ data types `A` and `B` such that
+ //! 1. `A` and `B` share a common data type `C`, as determined by the
+ //! `common` metafunction
+ //! 2. `A`, `B` and `C` are all `Orderable` when taken individually
+ //! 3. @f$\mathrm{to<C>} : A \to C@f$ and @f$\mathrm{to<C>} : B \to C@f$
+ //! are both order-embeddings as determined by the `is_embedding`
+ //! metafunction.
+ //!
+ //! The method definitions for data types satisfying the above
+ //! properties are
+ //! @code
+ //! less(x, y) = less(to<C>(x), to<C>(y))
+ //! less_equal(x, y) = less_equal(to<C>(x), to<C>(y))
+ //! greater_equal(x, y) = greater_equal(to<C>(x), to<C>(y))
+ //! greater(x, y) = greater(to<C>(x), to<C>(y))
+ //! @endcode
+ //!
+ //!
+ //! Partial application of the methods
+ //! ----------------------------------
+ //! The `less`, `greater`, `less_equal` and `greater_equal` methods can
+ //! be called in two different ways. First, they can be called like
+ //! normal functions:
+ //! @code
+ //! less(x, y)
+ //! greater(x, y)
+ //!
+ //! less_equal(x, y)
+ //! greater_equal(x, y)
+ //! @endcode
+ //!
+ //! However, they may also be partially applied to an argument as follows:
+ //! @code
+ //! less.than(x)(y) == less(y, x)
+ //! greater.than(x)(y) == greater(y, x)
+ //!
+ //! less_equal.than(x)(y) == less_equal(y, x)
+ //! greater_equal.than(x)(y) == greater_equal(y, x)
+ //! @endcode
+ //!
+ //! Take good note that the order of the arguments is reversed, so
+ //! for example `less.than(x)(y)` is equivalent to `less(y, x)`, not
+ //! `less(x, y)`. This is because those variants are meant to be used
+ //! with higher order algorithms, where the chosen application order
+ //! makes sense.
+ //!
+ //!
+ //! [1]: http://en.wikipedia.org/wiki/Total_order
+ //! [2]: http://en.cppreference.com/w/cpp/concept/LessThanComparable
+ //! [3]: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3351.pdf
+ //! [4]: http://en.wikipedia.org/wiki/Strict_weak_ordering
+ template <typename Ord>
+ struct Orderable;
+BOOST_HANA_NAMESPACE_END
+
+#endif // !BOOST_HANA_FWD_CONCEPT_ORDERABLE_HPP