recursive_path_compare (iterators)

template<typename T, typename S>
bool libsemigroups::recursive_path_compare(T const &first1, T last1, S const &first2, S last2) noexcept

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

Defined in order.hpp.

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

Exceptions

This function is noexcept and is guaranteed never to throw.

Warning

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

Template Parameters
  • T – the type of iterators to the first object to be compared.

  • S – the type of iterators to the second 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

A bool.