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...
struct	WtLexCompare
	A stateful struct with binary call operator using wt_lex_compare or wt_lex_compare_no_checks. More...
struct	WtShortLexCompare
	A stateful struct with binary call operator using wt_shortlex_compare or wt_shortlex_compare_no_checks. More...

Functions
template<typename Thing>
bool	lexicographical_compare (Thing *const x, Thing *const y)
	Compare two objects via their pointers using std::lexicographical_compare.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	lexicographical_compare (Thing const &x, Thing const &y)
	Compare two objects of the same type using std::lexicographical_compare.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	recursive_path_compare (Iterator first1, Iterator last1, Iterator first2, Iterator last2) noexcept
	Compare two objects of the same type using the recursive path comparison.
template<typename Thing>
bool	recursive_path_compare (Thing *const x, Thing *const y) noexcept
	Compare two objects via their pointers using recursive_path_compare.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	recursive_path_compare (Thing const &x, Thing const &y) noexcept
	Compare two objects of the same type using recursive_path_compare.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	shortlex_compare (Iterator first1, Iterator last1, Iterator first2, Iterator last2)
	Compare two objects of the same type using the short-lex reduction ordering.
template<typename Thing>
bool	shortlex_compare (Thing *const x, Thing *const y)
	Compare two objects via their pointers using shortlex_compare.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	shortlex_compare (Thing const &x, Thing const &y)
	Compare two objects of the same type using shortlex_compare.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	wt_lex_compare (Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const &weights)
	Compare two objects of the same type using the weighted lex ordering and check validity.
template<typename Thing>
bool	wt_lex_compare (Thing *const x, Thing *const y, std::vector< size_t > const &weights)
	Compare two objects via their pointers using wt_lex_compare and check validity.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	wt_lex_compare (Thing const &x, Thing const &y, std::vector< size_t > const &weights)
	Compare two objects of the same type using wt_lex_compare and check validity.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	wt_lex_compare_no_checks (Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const &weights)
	Compare two objects of the same type using the weighted lex ordering without checks.
template<typename Thing>
bool	wt_lex_compare_no_checks (Thing *const x, Thing *const y, std::vector< size_t > const &weights)
	Compare two objects via their pointers using wt_lex_compare_no_checks without checks.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	wt_lex_compare_no_checks (Thing const &x, Thing const &y, std::vector< size_t > const &weights)
	Compare two objects of the same type using wt_lex_compare_no_checks without checks.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	wt_shortlex_compare (Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const &weights)
	Compare two objects of the same type using the weighted short-lex ordering and check validity.
template<typename Thing>
bool	wt_shortlex_compare (Thing *const x, Thing *const y, std::vector< size_t > const &weights)
	Compare two objects via their pointers using wt_shortlex_compare and check validity.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	wt_shortlex_compare (Thing const &x, Thing const &y, std::vector< size_t > const &weights)
	Compare two objects of the same type using wt_shortlex_compare and check validity.
template<typename Iterator, typename = std::enable_if_t<!rx::is_input_or_sink_v<Iterator>>>
bool	wt_shortlex_compare_no_checks (Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const &weights)
	Compare two objects of the same type using the weighted short-lex ordering without checks.
template<typename Thing>
bool	wt_shortlex_compare_no_checks (Thing *const x, Thing *const y, std::vector< size_t > const &weights)
	Compare two objects via their pointers using wt_shortlex_compare_no_checks without checks.
template<typename Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>
bool	wt_shortlex_compare_no_checks (Thing const &x, Thing const &y, std::vector< size_t > const &weights)
	Compare two objects of the same type using wt_shortlex_compare_no_checks without checks.

Function Documentation

lexicographical_compare() [1/2]

template<typename Thing>

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

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using std::lexicographical_compare.

Template Parameters

Thing

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 Thing, typename = std::enable_if_t<!rx::is_input_or_sink_v<Thing>>>

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

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using std::lexicographical_compare.

Template Parameters

Thing

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

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

recursive_path_compare() [1/3]

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

bool recursive_path_compare ( Iterator first1, Iterator last1, Iterator first2, Iterator last2 )

nodiscardnoexcept

Defined in order.hpp.

This function compares two objects of the same type using the recursive path comparison described in [38] (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 [35].

Template Parameters

Iterator

the type of iterators that are the arguments.

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() [2/3]

template<typename Thing>

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

nodiscardnoexcept

Defined in order.hpp.

This function compares two objects via their pointers using recursive_path_compare.

Template Parameters

Thing

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 r 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(Iterator, Iterator, Iterator, Iterator)

recursive_path_compare() [3/3]

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

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

nodiscardnoexcept

Defined in order.hpp.

This function compares two objects of the same type using recursive_path_compare.

Template Parameters

Thing

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(Iterator, Iterator, Iterator, Iterator)

shortlex_compare() [1/3]

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

bool shortlex_compare ( Iterator first1, Iterator last1, Iterator first2, Iterator last2 )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using the short-lex reduction ordering.

Template Parameters

Iterator

the type of iterators that are the parameters.

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 Iterator>
bool shortlex_compare(Iterator first1,
                      Iterator last1,
                      Iterator first2,
                      Iterator last2) {
  return (last1 - first1) < (last2 - first2)
         || ((last1 - first1) == (last2 - first2)
             && std::lexicographical_compare
                  (first1, last1, first2, last2));
}

shortlex_compare() [2/3]

template<typename Thing>

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

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using shortlex_compare.

Template Parameters

Thing

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(Iterator, Iterator, Iterator, Iterator).

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(Iterator, Iterator, Iterator, Iterator).

shortlex_compare() [3/3]

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

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

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using shortlex_compare.

Template Parameters

Thing

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(Iterator, Iterator, Iterator, Iterator).

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(Iterator, Iterator, Iterator, Iterator).

wt_lex_compare() [1/3]

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

bool wt_lex_compare ( Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using the weighted lex ordering. The weight of a word is computed by adding up the weights of the letters in the word, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet. Heavier words come later in the ordering than all lighter words. Amongst words of equal weight, lexicographic ordering is used.

After checking that all letters in both ranges are valid indices into the weights vector, this function performs the same as wt_lex_compare_no_checks(first1, last1, first2, last2, weights).

Template Parameters

Iterator

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter in either range is not a valid index into the weights vector (i.e., if any letter is greater than or equal to weights.size()).

Complexity

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

See also

wt_lex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&)

wt_lex_compare() [2/3]

template<typename Thing>

bool wt_lex_compare ( Thing *const x, Thing *const y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using wt_lex_compare, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

After checking that all letters are valid indices into the weights vector, this function performs the same as wt_lex_compare_no_checks(*x, *y, weights).

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter is not a valid index into the weights vector.

Complexity

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

Possible Implementation

wt_lex_compare(
  x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);

See also

wt_lex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_lex_compare() [3/3]

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

bool wt_lex_compare ( Thing const & x, Thing const & y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using wt_lex_compare, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

After checking that all letters in both objects are valid indices into the weights vector, this function performs the same as wt_lex_compare_no_checks(x, y, weights).

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter in x or y is not a valid index into the weights vector.

Complexity

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

Possible Implementation

wt_lex_compare(
  x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);

See also

wt_lex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_lex_compare_no_checks() [1/3]

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

bool wt_lex_compare_no_checks ( Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using the weighted lex ordering. The weight of a word is computed by adding up the weights of the letters in the word, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet. Heavier words come later in the ordering than all lighter words. Amongst words of equal weight, lexicographic ordering is used.

Template Parameters

Iterator

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.
weights	the weights vector.

Returns

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

Exceptions

Throws if std::lexicographical_compare does.

Complexity

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

Warning

It is not checked that the letters in the ranges are valid indices into the weights vector.

See also

wt_lex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_lex_compare_no_checks() [2/3]

template<typename Thing>

bool wt_lex_compare_no_checks ( Thing *const x, Thing *const y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using wt_lex_compare_no_checks, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

See vector<size_t> const&).

Complexity

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

Possible Implementation

wt_lex_compare_no_checks(
  x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);

Warning

It is not checked that the letters are valid indices into the weights vector.

See also

wt_lex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_lex_compare_no_checks() [3/3]

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

bool wt_lex_compare_no_checks ( Thing const & x, Thing const & y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using wt_lex_compare_no_checks, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

See vector<size_t> const&).

Complexity

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

Possible Implementation

wt_lex_compare_no_checks(
  x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);

Warning

It is not checked that the letters in x and y are valid indices into the weights vector.

See also

wt_lex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare() [1/3]

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

bool wt_shortlex_compare ( Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using the weighted short-lex ordering. The weight of a word is computed by adding up the weights of the letters in the word, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet. Heavier words come later in the ordering than all lighter words. Amongst words of equal weight, short-lex ordering is used.

After checking that all letters in both ranges are valid indices into the weights vector, this function performs the same as wt_shortlex_compare_no_checks(first1, last1, first2, last2, weights).

Template Parameters

Iterator

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter in either range is not a valid index into the weights vector (i.e., if any letter is greater than or equal to weights.size()).

Complexity

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

See also

wt_shortlex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare() [2/3]

template<typename Thing>

bool wt_shortlex_compare ( Thing *const x, Thing *const y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using wt_shortlex_compare, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

After checking that all letters are valid indices into the weights vector, this function performs the same as wt_shortlex_compare_no_checks(*x, *y, weights).

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter is not a valid index into the weights vector.

Complexity

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

Possible Implementation

wt_shortlex_compare(
  x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);

See also

wt_shortlex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare() [3/3]

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

bool wt_shortlex_compare ( Thing const & x, Thing const & y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using wt_shortlex_compare, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

After checking that all letters in both objects are valid indices into the weights vector, this function performs the same as wt_shortlex_compare_no_checks(x, y, weights).

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

LibsemigroupsException

if any letter in x or y is not a valid index into the weights vector.

Complexity

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

Possible Implementation

wt_shortlex_compare(
  x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);

See also

wt_shortlex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare_no_checks() [1/3]

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

bool wt_shortlex_compare_no_checks ( Iterator first1, Iterator last1, Iterator first2, Iterator last2, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using the weighted short-lex ordering. The weight of a word is computed by adding up the weights of the letters in the word, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet. Heavier words come later in the ordering than all lighter words. Amongst words of equal weight, short-lex ordering is used.

Template Parameters

Iterator

the type of iterators that are the arguments.

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.
weights	the weights vector.

Returns

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

Exceptions

Throws if std::lexicographical_compare does.

Complexity

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

Warning

It is not checked that the letters in the ranges are valid indices into the weights vector.

See also

wt_shortlex_compare(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare_no_checks() [2/3]

template<typename Thing>

bool wt_shortlex_compare_no_checks ( Thing *const x, Thing *const y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects via their pointers using wt_shortlex_compare_no_checks, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

See vector<size_t> const&).

Complexity

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

Possible Implementation

wt_shortlex_compare_no_checks(
  x->cbegin(), x->cend(), y->cbegin(), y->cend(), weights);

Warning

It is not checked that the letters are valid indices into the weights vector.

See also

wt_shortlex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).

wt_shortlex_compare_no_checks() [3/3]

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

bool wt_shortlex_compare_no_checks ( Thing const & x, Thing const & y, std::vector< size_t > const & weights )

nodiscard

Defined in order.hpp.

This function compares two objects of the same type using wt_shortlex_compare_no_checks, where the ith index of the weights vector corresponds to the weight of the ith letter in the alphabet.

Template Parameters

Thing

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.
weights	the weights vector.

Returns

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

Exceptions

See vector<size_t> const&).

Complexity

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

Possible Implementation

wt_shortlex_compare_no_checks(
  x.cbegin(), x.cend(), y.cbegin(), y.cend(), weights);

Warning

It is not checked that the letters in x and y are valid indices into the weights vector.

See also

wt_shortlex_compare_no_checks(Iterator, Iterator, Iterator, Iterator, std::vector<size_t> const&).