shortlex_compare (iterators)

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

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

Defined in order.hpp.

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));
}

Complexity

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

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.

Throws

(None) – Throws if std::lexicographical_compare does.

Returns

A bool.