Orders

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

See also

Order

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

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.

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 [37] (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 [34].

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