Boost.Hana: Orderable

| Boost.Hana 1.0.0 Your standard library for metaprogramming |

Variables
Orderable
Concepts

## Description

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

a <= b = !(b < a)
a < b = !(b <= a)

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 `<=` on a set `S` is a binary predicate \( <= \;: S \times S \to bool \) such that for all `a`, `b`, `c` in `S`,

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

Additionally, the `less`, `greater` and `greater_equal` methods should have the following intuitive meanings:

a < b if and only if !(b <= a)
a > b if and only if b < a
a >= b if and only if !(a < b)

## Refined concept

1. `Comparable` (free model)
   Since `Orderable` requires `less_equal` to be a total order, a model of `Comparable` may always be obtained by setting
   equal(x, y) = less_equal(x, y) && less_equal(y, x)

## 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 C++ concept are automatically a model of `Orderable` by setting

less(x, y) = (x < y)

The cross-type version of the LessThanComparable concept is analogous to the cross-type version of the EqualityComparable concept presented in N3351, which is compatible with the usual single type definition. However, note that the LessThanComparable concept only requires `<` to be a strict weak ordering, 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 : A \to B\) 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`,

if less(x, y) then less(f(x), f(y))

Another important property is that of being order-reflecting, which can be stated as

if less(f(x), f(y)) then less(x, y)

We say that a function is an order-embedding if it is both order-preserving and order-reflecting, i.e. if

less(x, y) if and only if less(f(x), f(y))

## 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. \(\mathrm{to<C>} : A \to C\) and \(\mathrm{to<C>} : B \to C\) are both order-embeddings as determined by the `is_embedding` metafunction.

The method definitions for data types satisfying the above properties are

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))

## 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:

less(x, y)
greater(x, y)
less_equal(x, y)
greater_equal(x, y)

However, they may also be partially applied to an argument as follows:

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)

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.

## Variables

constexpr auto | boost::hana::greater
| Returns a `Logical` representing whether `x` is greater than `y`. More...
constexpr auto | boost::hana::greater_equal
| Returns a `Logical` representing whether `x` is greater than or equal to `y`. More...
constexpr auto | boost::hana::less
| Returns a `Logical` representing whether `x` is less than `y`. More...
constexpr auto | boost::hana::less_equal
| Returns a `Logical` representing whether `x` is less than or equal to `y`. More...
constexpr auto | boost::hana::max
| Returns the greatest of its arguments according to the `less` ordering. More...
constexpr auto | boost::hana::min
| Returns the smallest of its arguments according to the `less` ordering. More...
constexpr auto | boost::hana::ordering

Returns a function performing `less` after applying a transformation to both arguments.`ordering` creates a total order based on the result of applying a function to some objects, which is especially useful in conjunction with algorithms that accept a custom predicate that must represent a total order. More...

## Variable Documentation

constexpr auto boost::hana::greater

`#include <boost/hana/fwd/greater.hpp>`

Initial value:
= [](auto&& x, auto&& y) -> decltype(auto) {
return tag-dispatched;
}

Returns a `Logical` representing whether `x` is greater than `y`.

## Signature

Given a Logical `Bool` and two Orderables `A` and `B` with a common embedding, the signature is \( \mathrm{greater} : A \times B \to Bool \).

Parameters

  x,y | Two objects to compare.

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/greater.hpp>
#include <boost/hana/integral_constant.hpp>
namespace hana = boost::hana;
static_assert(hana::greater(4, 1), "");
BOOST_HANA_CONSTANT_CHECK(!hana::greater(hana::int_c<1>, hana::int_c<3>));
int main() { }

constexpr auto boost::hana::greater_equal

`#include <boost/hana/fwd/greater_equal.hpp>`

Initial value:
= [](auto&& x, auto&& y) -> decltype(auto) {
return tag-dispatched;
}

Returns a `Logical` representing whether `x` is greater than or equal to `y`.

## Signature

Given a Logical `Bool` and two Orderables `A` and `B` with a common embedding, the signature is \( \mathrm{greater\_equal} : A \times B \to Bool \).

Parameters

  x,y | Two objects to compare.

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/greater_equal.hpp>
#include <boost/hana/integral_constant.hpp>
namespace hana = boost::hana;
static_assert(hana::greater_equal(4, 1), "");
static_assert(hana::greater_equal(1, 1), "");
BOOST_HANA_CONSTANT_CHECK(!hana::greater_equal(hana::int_c<1>, hana::int_c<2>));
int main() { }

constexpr auto boost::hana::less

`#include <boost/hana/fwd/less.hpp>`

Initial value:
= [](auto&& x, auto&& y) {
return tag-dispatched;
}

Returns a `Logical` representing whether `x` is less than `y`.

## Signature

Given a Logical `Bool` and two Orderables `A` and `B` with a common embedding, the signature is \( \mathrm{less} : A \times B \to Bool \).

Parameters

  x,y | Two objects to compare.

## Example

// 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)
#include <boost/hana/all_of.hpp>
#include <boost/hana/assert.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/less.hpp>
#include <boost/hana/not.hpp>
#include <boost/hana/tuple.hpp>
namespace hana = boost::hana;
static_assert(hana::less(1, 4), "");
BOOST_HANA_CONSTANT_CHECK(!hana::less(hana::int_c<3>, hana::int_c<2>));
// less.than is syntactic sugar
static_assert(hana::all_of(hana::tuple_c<int, 1, 2, 3, 4>, hana::less.than(5)), "");
BOOST_HANA_CONSTANT_CHECK(hana::all_of(hana::tuple_c<int, 1, 2, 3, 4>, hana::less_equal.than(hana::int_c<4>)));
int main() { }

constexpr auto boost::hana::less_equal

`#include <boost/hana/fwd/less_equal.hpp>`

Initial value:
= [](auto&& x, auto&& y) {
return tag-dispatched;
}

Returns a `Logical` representing whether `x` is less than or equal to `y`.

## Signature

Given a Logical `Bool` and two Orderables `A` and `B` with a common embedding, the signature is \( \mathrm{less\_equal} : A \times B \to Bool \).

Parameters

  x,y | Two objects to compare.

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/less_equal.hpp>
#include <boost/hana/not.hpp>
namespace hana = boost::hana;
static_assert(hana::less_equal(1, 4), "");
static_assert(hana::less_equal(1, 1), "");
BOOST_HANA_CONSTANT_CHECK(!hana::less_equal(hana::int_c<3>, hana::int_c<2>));
int main() { }

constexpr auto boost::hana::max

`#include <boost/hana/fwd/max.hpp>`

Initial value:
= [](auto&& x, auto&& y) -> decltype(auto) {
return tag-dispatched;
}

Returns the greatest of its arguments according to the `less` ordering.

Todo:
  Can't specify the signature here either. See `min` for details.

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/max.hpp>
namespace hana = boost::hana;
static_assert(hana::max(1, 4) == 4, "");
BOOST_HANA_CONSTANT_CHECK(hana::max(hana::int_c<7>, hana::int_c<5>) == hana::int_c<7>);
int main() { }

constexpr auto boost::hana::min

`#include <boost/hana/fwd/min.hpp>`

Initial value:
= [](auto&& x, auto&& y) -> decltype(auto) {
return tag-dispatched;
}

Returns the smallest of its arguments according to the `less` ordering.

Todo:
  We can't specify the signature right now, because the tag of the returned object depends on whether `x < y` or not. If we wanted to be mathematically correct, we should probably ask that `if_(cond, x, y)` returns a common data type of `x` and `y`, and then the behavior of `min` would follow naturally. However, I'm unsure whether this is desirable because that's a big requirement.

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/integral_constant.hpp>
#include <boost/hana/min.hpp>
namespace hana = boost::hana;
static_assert(hana::min(1, 4) == 1, "");
BOOST_HANA_CONSTANT_CHECK(hana::min(hana::int_c<7>, hana::int_c<5>) == hana::int_c<5>);
int main() { }

constexpr auto boost::hana::ordering

`#include <boost/hana/fwd/ordering.hpp>`

Initial value:
= [](auto&& f) {
return [perfect-capture](auto&& x, auto&& y) -> decltype(auto) {
return less(f(forwarded(x)), f(forwarded(y)));
};
}
boost::hana::less
constexpr auto less
Returns a Logical representing whether x is less than y.
Definition: less.hpp:37
boost::hana::capture
constexpr auto capture
Create a function capturing the given variables.
Definition: capture.hpp:45

Returns a function performing `less` after applying a transformation to both arguments.`ordering` creates a total order based on the result of applying a function to some objects, which is especially useful in conjunction with algorithms that accept a custom predicate that must represent a total order.

Specifically, `ordering` is such that

ordering(f) == less ^on^ f

or, equivalently,

ordering(f)(x, y) == less(f(x), f(y))

Note
  This is not a tag-dispatched method (hence it can't be customized), but just a convenience function provided with the `Orderable` concept.

## Signature

Given a Logical `Bool` and an Orderable `B`, the signature is \( \mathrm{ordering} : (A \to B) \to (A \times A \to Bool) \).

## Example

// 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)
#include <boost/hana/assert.hpp>
#include <boost/hana/equal.hpp>
#include <boost/hana/ordering.hpp>
#include <boost/hana/sort.hpp>
#include <boost/hana/tuple.hpp>
#include <boost/hana/type.hpp>
namespace hana = boost::hana;
constexpr auto sorted = hana::sort.by(hana::ordering(hana::sizeof_),
hana::tuple_t<char[3], char[1], char[2], char[15]>
);
BOOST_HANA_CONSTANT_CHECK(sorted == hana::tuple_t<char[1], char[2], char[3], char[15]>);
int main() { }