Orderable

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-2017
// 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-2017
// 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-2017
// 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-2017
// 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-2017
// 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-2017
// 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)));
        };
    }

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-2017
// 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() { }