recursive_path_compare (iterators)ΒΆ

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

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]((../biblio.html::Holt2019aa).

Return

A bool.

Exceptions

This function is noexcept and is guaranteed never to throw.

Warning

This function has signifcantly worse performance than all the variants of short_lex_compare(T const, T const, S const) 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.