Orders

This page contains the documentation for several class and function templates for comparing words or strings with respect to certain reduction orderings.

Classes
struct	LexicographicalCompare
	A stateless struct with binary call operator using std::lexicographical_compare. More...
struct	RecursivePathCompare
	A stateless struct with binary call operator using recursive_path_compare. More...
struct	ShortLexCompare
	A stateless struct with binary call operator using shortlex_compare. More...

Enumerations
enum class	Order : uint8_t { none = 0 , shortlex , lex , recursive }
	The possible orderings of words and strings. More...

Functions
template<typename T>
bool	lexicographical_compare (T *const x, T *const y)
	Compare two objects via their pointers using std::lexicographical_compare.
template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
bool	lexicographical_compare (T const &x, T const &y)
	Compare two objects of the same type using std::lexicographical_compare.
template<typename T>
bool	recursive_path_compare (T *const x, T *const y) noexcept
	Compare two objects via their pointers using recursive_path_compare.
template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
bool	recursive_path_compare (T const &first1, T last1, T const &first2, T last2) noexcept
	Compare two objects of the same type using the recursive path comparison.
template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
bool	recursive_path_compare (T const &x, T const &y) noexcept
	Compare two objects of the same type using recursive_path_compare.
template<typename T>
bool	shortlex_compare (T *const x, T *const y)
	Compare two objects via their pointers using shortlex_compare.
template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
bool	shortlex_compare (T const &first1, T const &last1, T const &first2, T const &last2)
	Compare two objects of the same type using the short-lex reduction ordering.
template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>
bool	shortlex_compare (T const &x, T const &y)
	Compare two objects of the same type using shortlex_compare.

Enumeration Type Documentation

Order

enum class Order : uint8_t

strong

The values in this enum can be used as the arguments for functions such as standardize(Order) or order(Order) to specify which ordering should be used. The normal forms for congruence classes are given with respect to one of the orders specified by the values in this enum.

Enumerator
none	No ordering.
shortlex	The short-lex ordering. Words are first ordered by length, and then lexicographically.
lex	The lexicographic ordering. Note that this is not a well-order, so there may not be a lexicographically least word in a given congruence class of words.
recursive	The recursive-path ordering, as described in [35] (Definition 1.2.14, page 24).

Function Documentation

lexicographical_compare() [1/2]

template<typename T>

bool lexicographical_compare	(	T *const	x,
		T *const	y )

Defined in order.hpp.

Compare two objects via their pointers using std::lexicographical_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	pointer to the first object for comparison.
y	pointer to the second object for comparison.

Returns

The boolean value true if x is lexicographically less than y, and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException. See std::lexicographical_compare.

Complexity

See std::lexicographical_compare.

Possible Implementation

lexicographical_compare(
  x->cbegin(), x->cend(), y->cbegin(), y->cend());

lexicographical_compare() [2/2]

template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>

bool lexicographical_compare	(	T const &	x,
		T const &	y )

Defined in order.hpp.

Compare two objects of the same type using std::lexicographical_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	const reference to the first object for comparison.
y	const reference to the second object for comparison.

Returns

The boolean value true if x is lexicographically less than y, and false otherwise.

Exceptions

This function guarantees not to throw a LibsemigroupsException. See std::lexicographical_compare.

Complexity

See std::lexicographical_compare.

Possible Implementation

std::lexicographical_compare(
  x.cbegin(), x.cend(), y.cbegin(), y.cend());

recursive_path_compare() [1/3]

template<typename T>

bool recursive_path_compare ( T *const x, T *const y )

noexcept

Defined in order.hpp.

Compare two objects via their pointers using recursive_path_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	pointer to the first object for comparison.
y	pointer to the second object for comparison.

Returns

The boolean value true if the value pointed to by x is less than the value pointed to by y with respect to the recursive path ordering, and false otherwise.

Exceptions

This function is noexcept and is guaranteed never to throw.

Possible Implementation

recursive_path_compare(
  x->cbegin(), x->cend(), y->cbegin(), y->cend());

See also

recursive_path_compare(T const&, T, T const&, T)

recursive_path_compare() [2/3]

template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>

bool recursive_path_compare ( T const & first1, T last1, T const & first2, T last2 )

noexcept

Defined in order.hpp.

Compare two objects of the same type using the recursive path comparison described in [35] (Definition 1.2.14, page 24).

If \(u, v\in X ^ {*}\), \(u \neq v\), and \(u = a'u\), \(v = bv'\) for some \(a,b \in X\), \(u',v'\in X ^ {*}\), then \(u > v\) if one of the following conditions holds:

1. \(a = b\) and \(u' \geq v'\);
2. \(a > b\) and \(u > v'\);
3. \(b > a\) and \(u' > v\).

This documentation and the implementation of recursive_path_compare is based on the source code of [32].

Template Parameters

T	the type of iterators to the first object to be compared.

Parameters

first1	beginning iterator of first object for comparison.
last1	ending iterator of first object for comparison.
first2	beginning iterator of second object for comparison.
last2	ending iterator of second object for comparison.

Returns

The boolean value true if the range [first1, last1) is less than the range [first2, last2) with respect to the recursive path ordering, and false otherwise.

Exceptions

This function is noexcept and is guaranteed never to throw.

Warning

This function has significantly worse performance than all the variants of shortlex_compare and std::lexicographical_compare.

recursive_path_compare() [3/3]

template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>

bool recursive_path_compare ( T const & x, T const & y )

noexcept

Defined in order.hpp.

Compare two objects of the same type using recursive_path_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	const reference to the first object for comparison.
y	const reference to the second object for comparison.

Returns

The boolean value true if x is less than y with respect to the recursive path ordering, and false otherwise.

Exceptions

This function is noexcept and is guaranteed never to throw.

Possible Implementation

recursive_path_compare(
  x.cbegin(), x.cend(), y.cbegin(), y.cend());

See also

recursive_path_compare(T const&, T, T const&, T)

shortlex_compare() [1/3]

template<typename T>

bool shortlex_compare	(	T *const	x,
		T *const	y )

Defined in order.hpp.

Compare two objects via their pointers using shortlex_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	pointer to the first object for comparison.
y	pointer to the second object for comparison.

Returns

The boolean value true if x points to a word short-lex less than the word pointed to by y, and false otherwise.

Exceptions

See shortlex_compare(T const&, T const&, T const&, T const&).

Complexity

At most \(O(n)\) where \(n\) is the minimum of the length of the word pointed to by x and the length of word pointed to by y.

Possible Implementation

shortlex_compare(
  x->cbegin(), x->cend(), y->cbegin(), y->cend());

See also

shortlex_compare(T const&, T const&, T const&, T const&).

shortlex_compare() [2/3]

template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>

bool shortlex_compare	(	T const &	first1,
		T const &	last1,
		T const &	first2,
		T const &	last2 )

Defined in order.hpp.

Compare two objects of the same type using the short-lex reduction ordering.

Template Parameters

T	the type of iterators to the first object to be compared.

Parameters

first1	beginning iterator of first object for comparison.
last1	ending iterator of first object for comparison.
first2	beginning iterator of second object for comparison.
last2	ending iterator of second object for comparison.

Returns

The boolean value true if the range [first1, last1) is short-lex less than the range [first2, last2), and false otherwise.

Exceptions

Throws if std::lexicographical_compare does.

Complexity

At most \(O(n)\) where \(n\) is the minimum of the distance between last1 and first1, and the distance between last2 and first2.

Possible Implementation

template <typename T, typename S>
bool shortlex_compare(T const& first1,
                      T const& last1,
                      S const& first2,
                      S const& last2) {
  return (last1 - first1) < (last2 - first2)
         || ((last1 - first1) == (last2 - first2)
             && std::lexicographical_compare
                  (first1, last1, first2, last2));
}

shortlex_compare() [3/3]

template<typename T, typename = std::enable_if_t<!rx::is_input_or_sink_v<T>>>

bool shortlex_compare	(	T const &	x,
		T const &	y )

Defined in order.hpp.

Compare two objects of the same type using shortlex_compare.

Template Parameters

T	the type of the objects to be compared.

Parameters

x	const reference to the first object for comparison.
y	const reference to the second object for comparison.

Returns

The boolean value true if x is short-lex less than y, and false otherwise.

Exceptions

See shortlex_compare(T const&, T const&, T const&, T const&).

Complexity

At most \(O(n)\) where \(n\) is the minimum of the length of x and the length of y.

Possible Implementation

shortlex_compare(
  x.cbegin(), x.cend(), y.cbegin(), y.cend());

See also

shortlex_compare(T const&, T const&, T const&, T const&).