present.cpp

//
// libsemigroups_pybind11
// Copyright (C) 2024 Joseph Edwards, James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

// C std headers....
#include <cstddef>  // for size_t

// C++ stl headers....
#include <string>  // for string, basic_string, oper...

// libsemigroups....
#include <libsemigroups/constants.hpp>     // for operator==, UNDEFINED
#include <libsemigroups/exception.hpp>     // for LibsemigroupsException
#include <libsemigroups/order.hpp>         // for shortlex_compare
#include <libsemigroups/presentation.hpp>  // for Presentation
#include <libsemigroups/ranges.hpp>        // for is_sorted
#include <libsemigroups/types.hpp>         // for word_type

// pybind11....
#include <pybind11/cast.h>        // for arg
#include <pybind11/functional.h>  // for std::function conversion
#include <pybind11/pybind11.h>    // for class_, init, module
#include <pybind11/pytypes.h>     // for sequence, str_attr_accessor
#include <pybind11/stl.h>         // for std::vector conversion

// libsemigroups_pybind11....
#include "main.hpp"  // for init_present

namespace libsemigroups {
  namespace py = pybind11;

  namespace {
    template <typename Word>
    void bind_present(py::module& m, std::string const& name) {
      using Presentation_ = Presentation<Word>;
      using size_type     = typename Presentation_::size_type;

      py::class_<Presentation_> thing(m,
                                      name.c_str(),
                                      R"pbdoc(
Presentations for semigroups and monoids.

This class can be used to construct presentations for semigroups or monoids
and is intended to be used as the input to other algorithms in
``libsemigroups_pybind11``. The idea is to provide a shallow wrapper around a
collection of words of type :ref:`Word<pseudo_word_type_class>`. We refer to
this list of words as the *rules* of the presentation. The :any:`Presentation`
class also provides some checks that the rules really define a presentation,
(i.e. it's consistent with its alphabet), and some related functionality is
available in the module :any:`libsemigroups_pybind11.presentation`.)pbdoc");
      thing.def("__repr__", [](Presentation_ const& p) -> std::string {
        return to_human_readable_repr(p);
      });
      thing.def("__eq__",
                [](Presentation_ const& lhop, Presentation_ rhop) -> bool {
                  return lhop == rhop;
                });
      thing.def_readwrite("rules",
                          &Presentation_::rules,
                          R"pbdoc(
Data member holding the rules of the presentation.

The rules can be altered using the member functions of ``list``, and the
presentation can be checked for validity using :any:`throw_if_bad_alphabet_or_rules`.)pbdoc");
      thing.def(py::init<>(), R"pbdoc(
:sig=(self: Presentation) -> None:
Default constructor.

Constructs an empty presentation with no rules and no alphabet.)pbdoc");
      thing.def(
          "copy",
          [](Presentation_ const& self) { return Presentation_(self); },
          R"pbdoc(
:sig=(self: Presentation) -> Presentation:

Copy a :any:`Presentation` object.

:returns: A copy.
:rtype: Presentation
)pbdoc");
      thing.def("__copy__",
                [](Presentation_ const& that) { return Presentation_(that); });
      thing.def(
          "alphabet",
          [](Presentation_ const& self) { return self.alphabet(); },
          R"pbdoc(
:sig=(self: Presentation) -> Word:
Return the alphabet of the presentation.

:returns: The alphabet of the presentation.
:rtype: :ref:`Word<pseudo_word_type_class>`

:complexity: Constant.
)pbdoc");
      thing.def(
          "alphabet",
          [](Presentation_& self, size_type n) -> Presentation_& {
            return self.alphabet(n);
          },
          py::arg("n"),
          R"pbdoc(
:sig=(self: Presentation, n: int) -> Presentation:
Set the alphabet by size.

Sets the alphabet to the first :math:`n` values with type
:ref:`Letter<pseudo_letter_type_class>`. For :any:`str`-types, we assume the
order of letters to be ``a-zA-Z0-9``.

:param n: the size of the alphabet.
:type n: int

:returns: *self*.
:rtype: Presentation

:raises LibsemigroupsError:  if the value of *n* is greater than the
  maximum number of letters supported by :ref:`Letter<pseudo_letter_type_class>`.

.. seealso::
      * :any:`throw_if_alphabet_has_duplicates`
      * :any:`throw_if_bad_rules`
      * :any:`throw_if_bad_alphabet_or_rules`
)pbdoc");
      thing.def(
          "alphabet",
          [](Presentation_&                           self,
             typename Presentation_::word_type const& lphbt) -> Presentation_& {
            return self.alphabet(lphbt);
          },
          py::arg("lphbt"),
          R"pbdoc(
:sig=(self: Presentation, lphbt: Word) -> Presentation:
Set the alphabet.

Sets the alphabet to be the letters in *lphbt*.

:param lphbt: the alphabet.
:type lphbt: :ref:`Word<pseudo_word_type_class>`

:returns: *self*.
:rtype: Presentation

:raises LibsemigroupsError:  if there are duplicate letters in *lphbt*.

.. seealso::
      * :any:`throw_if_bad_rules`
      * :any:`throw_if_bad_alphabet_or_rules`

)pbdoc");
      thing.def("alphabet_from_rules",
                &Presentation_::alphabet_from_rules,
                R"pbdoc(
:sig=(self: Presentation) -> Presentation:

Set the alphabet to be the letters in the rules.

:returns: *self*.
:rtype: Presentation

:complexity: At most :math:`O(mn)` where :math:`m` is the number of rules,
  and :math:`n` is the length of the longest rule.

.. seealso::
      * :any:`throw_if_bad_rules`
      * :any:`throw_if_bad_alphabet_or_rules`

)pbdoc");
      thing.def(
          "contains_empty_word",
          [](Presentation_ const& self) { return self.contains_empty_word(); },
          R"pbdoc(
:sig=(self: Presentation) -> bool:

Return whether the empty word is a valid relation word.

Returns ``True`` if the empty word is a valid relation word, and ``False`` if
the empty word is not a valid relation word.

If the presentation is not allowed to contain the empty word (according
to this function), the presentation may still be isomorphic to a monoid,
but is not given as a quotient of a free monoid.

:returns: Whether the presentation can contain the empty word.
:rtype: bool

:complexity: Constant.

)pbdoc");
      thing.def(
          "contains_empty_word",
          [](Presentation_& self, bool val) -> Presentation_& {
            return self.contains_empty_word(val);
          },
          py::arg("val"),
          R"pbdoc(
:sig=(self: Presentation, val: bool) -> Presentation:

Set whether the empty word is a valid relation word.

Specify whether the empty word should be a valid relation word (corresponding
to *val* being ``True``), or not (corresponding to *val* being ``False``).

If the presentation is not allowed to contain the empty word (according to
the value specified here), the presentation may still be isomorphic to a
monoid, but is not given as a quotient of a free monoid.

:param val: whether the presentation can contain the empty word.
:type val: bool

:returns: *self*.
:rtype: Presentation

:complexity: Constant.
)pbdoc");
      thing.def("in_alphabet",
                &Presentation_::in_alphabet,
                py::arg("val"),
                R"pbdoc(
:sig=(self: Presentation, val: Letter) -> bool:

Check if a letter belongs to the alphabet or not.

:param val: the letter to check.
:type val: :ref:`Letter<pseudo_letter_type_class>`

:returns: Whether the letter belongs to the alphabet.
:rtype: bool

:complexity: Constant on average, worst case linear in the size of the
  alphabet.
)pbdoc");
      thing.def("index",
                &Presentation_::index,
                py::arg("val"),
                R"pbdoc(
:sig=(self: Presentation, val: Letter) -> int:

Return the index of a letter in the alphabet.

After checking that *val* is in the alphabet, get the index of a letter in
the alphabet.

:param val: the letter.
:type val: :ref:`Letter<pseudo_letter_type_class>`

:returns: The index.
:rtype: int

:raises LibsemigroupsError:  if *val* does not belong to the alphabet.

:complexity: Constant.

)pbdoc");
      thing.def("init",
                &Presentation_::init,
                R"pbdoc(
:sig=(self: Presentation) -> Presentation:

Remove the alphabet and all rules.

This function clears the alphabet and all rules from the presentation,
putting it back into the state it would be in if it was newly constructed.

:returns: *self*.
:rtype: Presentation
)pbdoc");
      thing.def("letter",
                &Presentation_::letter,
                py::arg("i"),
                R"pbdoc(
:sig=(self: Presentation, i: int) -> Letter:
Get a letter in the alphabet by index.

After checking that *i* is in the range :math:`[0, n)`, where :math:`n` is
the length of the alphabet, this function returns the letter of the alphabet in
position *i*.

:param i: the index.
:type i: int

:returns: The letter.
:rtype: :ref:`Letter<pseudo_letter_type_class>`

:raises LibsemigroupsError:  if *i* is not in the range :math:`[0, n)`.)pbdoc");
      thing.def("throw_if_bad_alphabet_or_rules",
                &Presentation_::throw_if_bad_alphabet_or_rules,
                R"pbdoc(
:sig=(self: Presentation) -> None:

Check if the alphabet and rules are valid.

:raises LibsemigroupsError:  if :any:`throw_if_alphabet_has_duplicates` or
      :any:`throw_if_bad_rules` does.

:complexity:
   Worst case :math:`O(mnp)` where :math:`m` is the length of the longest
   word, :math:`n` is the size of the alphabet and :math:`p` is the number of
   rules.)pbdoc");
      thing.def(
          "throw_if_alphabet_has_duplicates",
          [](Presentation_ const& self) {
            return self.throw_if_alphabet_has_duplicates();
          },
          R"pbdoc(
:sig=(self: Presentation) -> None:

Check if the alphabet is valid.

:raises LibsemigroupsError:  if there are duplicate letters in the alphabet.

:complexity: Linear in the length of the alphabet.)pbdoc");
      thing.def(
          "throw_if_letter_not_in_alphabet",
          [](Presentation_ const& self, typename Word::value_type c) {
            return self.throw_if_letter_not_in_alphabet(c);
          },
          py::arg("c"),
          R"pbdoc(
:sig=(self: Presentation, c: Letter) -> None:

Check if a letter belongs to the alphabet or not.

:param c: the letter to check.
:type c: :ref:`Letter<pseudo_letter_type_class>`

:raises LibsemigroupsError:  if *c* does not belong to the alphabet.

:complexity: Constant on average, worst case linear in the size of the
      alphabet.)pbdoc");

      thing.def(
          "throw_if_letter_not_in_alphabet",
          [](Presentation_ const& self, Word const& w) {
            self.throw_if_letter_not_in_alphabet(w.begin(), w.end());
          },
          py::arg("w"),
          R"pbdoc(
:sig=(self: Presentation, w: Word) -> None:

Check if every letter in a word belongs to the alphabet or not.

:param w: the word to check.
:type w: :ref:`Word<pseudo_word_type_class>`

:raises LibsemigroupsError:  if any letter in *w* does not belong to the alphabet.
)pbdoc");
      thing.def("throw_if_bad_rules",
                &Presentation_::throw_if_bad_rules,
                R"pbdoc(
:sig=(self: Presentation) -> None:

Check if every rule consists of letters belonging to the alphabet.

:raises LibsemigroupsError:  if any word contains a letter not in the
      alphabet.

:complexity: Worst case :math:`O(mnt)` where :math:`m` is the length of the
      longest word, :math:`n` is the size of the alphabet and :math:`t` is the
      number of rules.)pbdoc");
      thing.def(
          "add_generator",
          [](Presentation_& self) { return self.add_generator(); },
          R"pbdoc(
:sig=(self: Presentation) -> Letter:
Add a generator.

Add the first letter not in the alphabet as a generator, and return this letter.

:returns: The letter added to the alphabet.
:rtype: :ref:`Letter<pseudo_letter_type_class>`

)pbdoc");
      thing.def(
          "add_generator",
          [](Presentation_& self, typename Presentation_::letter_type x)
              -> Presentation_& { return self.add_generator(x); },
          py::arg("x"),
          R"pbdoc(
:sig=(self: Presentation, x: Letter) -> Presentation:
Add the letter *x* as a generator.

:param x: the letter to add as a generator.
:type x: :ref:`Letter<pseudo_letter_type_class>`

:returns: *self*.
:rtype: Presentation

:raises LibsemigroupsError:  if *x* is in ``alphabet()``.)pbdoc");
      thing.def(
          "remove_generator",
          [](Presentation_& self, typename Presentation_::letter_type x)
              -> Presentation_& { return self.remove_generator(x); },
          py::arg("x"),
          R"pbdoc(
:sig=(self: Presentation, x: Letter) -> Presentation:

Remove the letter *x* as a generator.

:param x: the letter to remove as a generator.
:type x: :ref:`Letter<pseudo_letter_type_class>`

:returns: *self*.
:rtype: Presentation

:raises LibsemigroupsError: if *x* is not in ``p.alphabet()``.

:complexity: Average case: linear in the length of the alphabet, worst case:
      quadratic in the length of the alphabet.
)pbdoc");

      ////////////////////////////////////////////////////////////////////////
      // Helper functions
      ////////////////////////////////////////////////////////////////////////

      m.def("presentation_add_identity_rules",
            &presentation::add_identity_rules<Word>,
            py::arg("p"),
            py::arg("e"),
            R"pbdoc(
:sig=(p: Presentation, e: Letter) -> None:
:only-document-once:

Add rules for an identity element.

Adds rules of the form :math:`ae = ea = a` for every letter :math:`a` in the
alphabet of *p*, and where :math:`e` is the second parameter.

:param p: the presentation to add rules to.
:type p: Presentation

:param e: the identity element.
:type e: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:  if *e* is not a letter in ``p.alphabet()``.

:complexity: Linear in the number of rules.)pbdoc");

      m.def(
          "presentation_add_inverse_rules",
          [](Presentation_&                      p,
             Word const&                         vals,
             typename Presentation_::letter_type e) {
            presentation::add_inverse_rules(p, vals, e);
          },
          py::arg("p"),
          py::arg("vals"),
          py::arg("e")
          = static_cast<typename Presentation_::letter_type>(UNDEFINED),
          R"pbdoc(
:sig=(p: Presentation, vals: Word, e: Letter = UNDEFINED) -> None:
:only-document-once:

Add rules for inverses.

The letter *a* with index ``i`` in *vals* is the inverse of the letter in
``alphabet()`` with index ``i``. The rules added are :math:`a_ib_i = e` where
the alphabet is :math:`\{a_1, \ldots, a_n\}`; the 2nd parameter *vals* is
:math:`\{b_1, \ldots, b_n\}`; and :math:`e` is the 3rd parameter.

:param p: the presentation to add rules to.
:type p: Presentation

:param vals: the inverses.
:type vals: :ref:`Word<pseudo_word_type_helper>`

:param e: the identity element (defaults to :any:`UNDEFINED`, meaning use the empty word).
:type e: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:
    if the length of *vals* is not equal to ``alphabet().size()``.
:raises LibsemigroupsError:
    if the letters in *vals* are not exactly those in ``alphabet()`` (perhaps in a different order).
:raises LibsemigroupsError:
    if :math:`(a_i ^ {-1}) ^ {-1} = a_i` does not hold for some :math:`i`.
:raises LibsemigroupsError:
    if :math:`e ^ {-1} = e` does not hold.

:complexity:  :math:`O(n)` where :math:`n` is ``p.alphabet().size()``.)pbdoc");
      m.def("presentation_add_involution_rules",
            &presentation::add_involution_rules<Word>,
            py::arg("p"),
            py::arg("letters"),
            R"pbdoc(
:sig=(p: Presentation, letters: Word) -> None:
:only-document-once:

Add rules that define involutions.

Adds rules to *p* of the form :math:`a^2 = \varepsilon` for every letter
:math:`a` in *letters*.

:param p: the presentation to add rules to.
:type p: Presentation

:param letters: the letters to add involution rules for.
:type letters: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if any letter in *letters* is not in ``p.alphabet()``, or if
  ``p.contains_empty_word()`` returns ``False``.
)pbdoc");
      m.def(
          "presentation_add_rule",
          [](Presentation_& p, Word const& lhop, Word const& rhop) {
            presentation::add_rule(p, lhop, rhop);
          },
          py::arg("p"),
          py::arg("lhop"),
          py::arg("rhop"),
          R"pbdoc(
:sig=(p: Presentation, lhop: Word, rhop: Word) -> None:
:only-document-once:

Check and add a rule to the presentation.

Adds the rule with left-hand side *lhop* and right-hand side *rhop* to the
rules, after checking that *lhop* and *rhop* consist entirely of letters in the
alphabet of *p*.

:param p: the presentation.
:type p: Presentation

:param lhop: the left-hand side of the rule.
:type lhop: :ref:`Word<pseudo_word_type_helper>`

:param rhop: the right-hand side of the rule.
:type rhop: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:  if *lhop* or *rhop* contains any letters not
  belonging to ``p.alphabet()``.)pbdoc");
      m.def(
          "presentation_add_rules",
          [](Presentation_& p, Presentation_ const& q) {
            presentation::add_rules(p, q);
          },
          R"pbdoc(
:sig=(p: Presentation, q: Presentation) -> None:
:only-document-once:
Add the rules of *q* to *p*.

Before it is added, each rule is validated to check it contains only letters of
the alphabet of *p*. If the :math:`n`th rule causes this function to throw, the
first :math:`n-1` rules will still be added to *p*.

:param p: the presentation to add rules to.
:type p: Presentation

:param q: the presentation to add words from.
:type q: Presentation

:raises LibsemigroupsError:
  if any rule contains any letters not belonging to
  ``p.alphabet()``.)pbdoc");
      m.def("presentation_add_zero_rules",
            &presentation::add_zero_rules<Word>,
            py::arg("p"),
            py::arg("z"),
            R"pbdoc(
:sig=(p: Presentation, z: Letter) -> None:
:only-document-once:
Add rules for a zero element.

Adds rules of the form :math:`az = za = z` for every letter :math:`a` in the
alphabet of *p*, and where :math:`z` is the second parameter.

:param p: the presentation to add rules to.
:type p: Presentation

:param z: the zero element.
:type z: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:  if *z* is not a letter in ``p.alphabet()``.

:complexity: Linear in the number of rules.)pbdoc");
      m.def(
          "presentation_commutator",
          [](Presentation<Word> const& p, Word const& x, Word const& y) {
            return presentation::commutator(p, x, y);
          },
          py::arg("p"),
          py::arg("x"),
          py::arg("y"),
          R"pbdoc(
:sig=(p: Presentation, x: Word, y: Word) -> Word:
:only-document-once:

Return the commutator of two words.

Returns the word :math:`x^{-1}y^{-1}xy`, after attempting to detect inverses
from the rules in *p*, using :any:`try_detect_inverses`.

:param p: the presentation.
:type p: Presentation

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:returns: The commutator :math:`x^{-1}y^{-1}xy`.
:rtype: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if *x* or *y* contains a letter not belonging to ``p.alphabet()``, if
  :any:`try_detect_inverses` throws, or if *x* or *y* contains a letter for
  which no inverse was detected.
)pbdoc");
      m.def(
          "presentation_commutator",
          [](Presentation<Word> const& p,
             Word const&               x,
             Word const&               y,
             Word const&               inverses) {
            return presentation::commutator(p, x, y, inverses);
          },
          py::arg("p"),
          py::arg("x"),
          py::arg("y"),
          py::arg("inverses"),
          R"pbdoc(
:sig=(p: Presentation, x: Word, y: Word, inverses: Word) -> Word:
:only-document-once:

Return the commutator of two words.

Returns the word :math:`x^{-1}y^{-1}xy`. The letter ``a`` with index ``i`` in
*inverses* is the inverse of the letter in ``p.alphabet()`` with index ``i``.

:param p: the presentation.
:type p: Presentation

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:param inverses: the inverses of the letters in p.alphabet().
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:returns: The commutator :math:`x^{-1}y^{-1}xy`.
:rtype: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if *inverses* are not valid inverses for ``p.alphabet()``, or if *x* or
  *y* contains a letter not belonging to ``p.alphabet()``.
)pbdoc");
      m.def(
          "presentation_commutator",
          [](Word const& x,
             Word const& y,
             Word const& alphabet,
             Word const& inverses) {
            return presentation::commutator(x, y, alphabet, inverses);
          },
          py::arg("x"),
          py::arg("y"),
          py::arg("alphabet"),
          py::arg("inverses"),
          R"pbdoc(
:sig=(x: Word, y: Word, alphabet: Word, inverses: Word) -> Word:
:only-document-once:

Return the commutator of two words.

Returns the word :math:`x^{-1}y^{-1}xy`. The letter ``a`` with index ``i`` in
*inverses* is the inverse of the letter in *alphabet* with index ``i``.

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:param alphabet:
  the alphabet, which should be a superset of the letters in x and y.
:type alphabet: :ref:`Word<pseudo_word_type_helper>`

:param inverses: the inverses of the letters in alphabet.
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:returns: The commutator :math:`x^{-1}y^{-1}xy`.
:rtype: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if *alphabet* contains duplicates, if *inverses* are not valid inverses
  for *alphabet*, or if *x* or *y* contains a letter not belonging to
  *alphabet*.
)pbdoc");
      m.def(
          "presentation_add_commutator_rule",
          [](Presentation_&                      p,
             Word const&                         x,
             Word const&                         y,
             Word const&                         alphabet,
             Word const&                         inverses,
             typename Presentation_::letter_type id) {
            presentation::add_commutator_rule(p, x, y, alphabet, inverses, id);
          },
          py::arg("p"),
          py::arg("x"),
          py::arg("y"),
          py::arg("alphabet"),
          py::arg("inverses"),
          py::kw_only(),  // This is so id must be specified by a key-word
          py::arg("id")
          = static_cast<typename Presentation_::letter_type>(UNDEFINED),
          R"pbdoc(
:sig=(p: Presentation, x: Word, y: Word, alphabet: Word, inverses: Word, *, id: Letter = UNDEFINED) -> None:
:only-document-once:

Add a commutator rule.

Adds the rule :math:`x^{-1}y^{-1}xy = id` to *p*. The letter ``a`` with index
``i`` in *inverses* is the inverse of the letter in *alphabet* with index
``i``. If *id* is :any:`UNDEFINED`, then the right-hand side is the empty
word.

:param p: the presentation.
:type p: Presentation

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:param alphabet:
  the alphabet, which should be a superset of the letters in *x* and *y*.
:type alphabet: :ref:`Word<pseudo_word_type_helper>`

:param inverses: the inverses of the letters in alphabet.
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:param id:
  the identity letter, or :any:`UNDEFINED` for the empty word. This is a
  keyword-only argument.
:type id: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:
  if *alphabet*, *inverses*, *x*, *y*, or *id* contains a letter not
  belonging to ``p.alphabet()``; if *alphabet* contains duplicates; if
  *inverses* are not valid inverses for *alphabet*; or if *x* or *y*
  contains a letter not belonging to *alphabet*.
)pbdoc");
      m.def(
          "presentation_add_commutator_rule",
          [](Presentation_&                      p,
             Word const&                         x,
             Word const&                         y,
             Word const&                         inverses,
             typename Presentation_::letter_type id) {
            presentation::add_commutator_rule(p, x, y, inverses, id);
          },
          py::arg("p"),
          py::arg("x"),
          py::arg("y"),
          py::arg("inverses"),
          py::kw_only(),  // This is so id must be specified by a key-word
          py::arg("id")
          = static_cast<typename Presentation_::letter_type>(UNDEFINED),
          R"pbdoc(
:sig=(p: Presentation, x: Word, y: Word, inverses: Word, *, id: Letter = UNDEFINED) -> None:
:only-document-once:

Add a commutator rule.

Adds the rule :math:`x^{-1}y^{-1}xy = id` to *p*. The letter ``a`` with index
``i`` in *inverses* is the inverse of the letter in ``p.alphabet()`` with
index ``i``. If *id* is :any:`UNDEFINED`, then the right-hand side is the
empty word.

:param p: the presentation.
:type p: Presentation

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:param inverses: the inverses of the letters in p.alphabet().
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:param id:
  the identity letter, or :any:`UNDEFINED` for the empty word. This is a
  keyword-only argument.
:type id: :ref:`Letter<pseudo_letter_type_helper>`


:raises LibsemigroupsError:
  if *inverses*, *x*, *y*, or *id* contains a letter not belonging to
  ``p.alphabet()``, or if *inverses* are not valid inverses for
  ``p.alphabet()``.
)pbdoc");
      m.def(
          "presentation_add_commutator_rule",
          [](Presentation_&                      p,
             Word const&                         x,
             Word const&                         y,
             typename Presentation_::letter_type id) {
            presentation::add_commutator_rule(p, x, y, id);
          },
          py::arg("p"),
          py::arg("x"),
          py::arg("y"),
          py::kw_only(),  // This is so id must be specified by a key-word
          py::arg("id")
          = static_cast<typename Presentation_::letter_type>(UNDEFINED),
          R"pbdoc(
:sig=(p: Presentation, x: Word, y: Word, *, id: Letter = UNDEFINED) -> None:
:only-document-once:

Add a commutator rule.

Adds the rule :math:`x^{-1}y^{-1}xy = id` to *p*, after attempting to detect
inverses from the rules in *p*, using :any:`try_detect_inverses`. If
*id* is :any:`UNDEFINED`, then the right-hand side is the empty word.

:param p: the presentation.
:type p: Presentation

:param x: the first word in the commutator.
:type x: :ref:`Word<pseudo_word_type_helper>`

:param y: the second word in the commutator.
:type y: :ref:`Word<pseudo_word_type_helper>`

:param id:
  the identity letter, or :any:`UNDEFINED` for the empty word. This is a
  keyword-only argument.
:type id: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:
  if *x*, *y*, or *id* contains a letter not belonging to
  ``p.alphabet()``, if :any:`try_detect_inverses` throws, or if *x* or
  *y* contains a letter for which no inverse was detected.
)pbdoc");
      m.def(
          "presentation_add_commutes_rules",
          [](Presentation_& p, Word const& letters) {
            presentation::add_commutes_rules(p, letters);
          },
          py::arg("p"),
          py::arg("letters"),
          R"pbdoc(
:sig=(p: Presentation, letters: Word) -> None:
:only-document-once:

Add rules so specific letters commute.

Adds rules to *p* of the form :math:`uv = vu` for every pair of letters
:math:`u, v` in *letters*.

:param p: the presentation to add rules to.
:type p: Presentation

:param letters: the collection of letters to add rules for.
:type letters: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if any letter in *letters* is not in ``p.alphabet()``.
)pbdoc");
      m.def(
          "presentation_add_commutes_rules",
          [](Presentation_& p, Word const& letters1, Word const& letters2) {
            presentation::add_commutes_rules(p, letters1, letters2);
          },
          py::arg("p"),
          py::arg("letters1"),
          py::arg("letters2"),
          R"pbdoc(
:sig=(p: Presentation, letters1: Word, letters2: Word) -> None:
:only-document-once:

Add rules so specific letters commute.

Adds rules to *p* of the form :math:`uv = vu` for every letter :math:`u` in
*letters1* and :math:`v` in *letters2*.

:param p: the presentation to add rules to.
:type p: Presentation

:param letters1: the first collection of letters to add rules for.
:type letters1: :ref:`Word<pseudo_word_type_helper>`

:param letters2: the second collection of letters to add rules for.
:type letters2: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if any letter in *letters1* or *letters2* is not in ``p.alphabet()``.
)pbdoc");
      m.def(
          "presentation_add_commutes_rules",
          [](Presentation_& p, Word const& letters, std::vector<Word> words) {
            presentation::add_commutes_rules(p, letters, words);
          },
          py::arg("p"),
          py::arg("letters"),
          py::arg("words"),
          R"pbdoc(
:sig=(p: Presentation, letters: Word, words: list[Word]) -> None:
:only-document-once:

Add rules so specific letters commute.

Adds rules to *p* of the form :math:`uv = vu` for every letter :math:`u` in
*letters* and word :math:`v` in *words*.

:param p: the presentation to add rules to.
:type p: Presentation

:param letters: the collection of letters to add rules for.
:type letters: :ref:`Word<pseudo_word_type_helper>`

:param words: the collection of words to add rules for.
:type words: list[:ref:`Word<pseudo_word_type_helper>`]


:raises LibsemigroupsError:
  if any letter in *letters*, or any letter in any word in *words* is not in
  ``p.alphabet()``.
)pbdoc");
      m.def(
          "presentation_are_rules_sorted",
          [](Presentation_ const& p) {
            return presentation::are_rules_sorted(p);
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> bool:
:only-document-once:
Check the rules are sorted relative to shortlex.

Check if the rules :math:`u_1 = v_1, \ldots, u_n = v_n` satisfy
:math:`u_1v_1 < \cdots < u_nv_n` where :math:`<` is shortlex order.

:param p: the presentation to check.
:type p: Presentation

:returns: Whether the rules are sorted.
:rtype: bool

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.

.. seealso::
      * :any:`sort_rules`.
)pbdoc");
      m.def(
          "presentation_change_alphabet",
          [](Presentation_& p, Word const& new_alphabet) {
            presentation::change_alphabet(p, new_alphabet);
          },
          py::arg("p"),
          py::arg("new_alphabet"),
          R"pbdoc(
:sig=(p: Presentation, new_alphabet: Word) -> None:
:only-document-once:
Change or re-order the alphabet.

This function replaces ``p.alphabet()`` with ``new_alphabet``, where possible,
and re-writes the rules in the presentation using the new alphabet.

:param p: the presentation.
:type p: Presentation

:param new_alphabet: the replacement alphabet.
:type new_alphabet: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:  if the size of ``p.alphabet()`` and
  ``new_alphabet`` do not agree.)pbdoc");
      m.def("presentation_contains_rule",
            &presentation::contains_rule<Word>,
            py::arg("p"),
            py::arg("lhs"),
            py::arg("rhs"),
            R"pbdoc(
:sig=(p: Presentation, lhs: Word, rhs: Word) -> bool:
:only-document-once:
Check if a presentation contains a rule.

Checks if the rule with left-hand side *lhs* and right-hand side *rhs* is
contained in *p*.

:param p: the presentation.
:type p: Presentation

:param lhs: the left-hand side of the rule.
:type lhs: :ref:`Word<pseudo_word_type_helper>`

:param rhs: the right-hand side of the rule.
:type rhs: :ref:`Word<pseudo_word_type_helper>`

:returns: Whether the presentation contains the rule.
:rtype: bool

:complexity: Linear in the number of rules.
)pbdoc");
      m.def("presentation_first_unused_letter",
            &presentation::first_unused_letter<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> Letter:
:only-document-once:
Return the first letter not in the alphabet of a presentation.

This function returns ``letter(p, i)`` when ``i`` is the least possible value
such that ``!p.in_alphabet(letter(p, i))`` if such a letter exists.

:param p: the presentation.
:type p: Presentation

:returns: The letter.
:rtype: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:  if *p* already has an alphabet of the maximum
  possible size.

)pbdoc");
      m.def("presentation_greedy_reduce_length",
            &presentation::greedy_reduce_length<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Greedily reduce the length of the presentation using
:any:`longest_subword_reducing_length`.

This function repeatedly calls :any:`longest_subword_reducing_length` and
:any:`replace_subword` to introduce a new generator and reduce the length of the
presentation *p* until :any:`longest_subword_reducing_length` returns the empty
word.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:
  if :any:`longest_subword_reducing_length` or :any:`replace_subword` does.
  )pbdoc");
      m.def("presentation_greedy_reduce_length_and_number_of_gens",
            &presentation::greedy_reduce_length_and_number_of_gens<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Greedily reduce the length and number of generators of the presentation.

This function repeatedly calls :any:`longest_subword_reducing_length` and
:any:`replace_subword` to introduce a new generator to try to reduce the
length of the presentation *p* and the number of generators. This is
done until either :any:`longest_subword_reducing_length` returns the empty
word, or the new length and number of generators is greater than or
equal to that of the presentation in the previous iteration.

In the latter case, the presentation *p* gets restored to the state it
was in after the previous iteration.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:
  if :any:`longest_subword_reducing_length` or :any:`replace_subword` does.
)pbdoc");
      m.def("presentation_is_strongly_compressible",
            &presentation::is_strongly_compressible<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> bool:
:only-document-once:
Return true if the :math:`1`-relation presentation can be strongly compressed.

A :math:`1`-relation presentation is *strongly compressible* if both relation
words start with the same letter and end with the same letter. In other words,
if the alphabet of the presentation *p* is :math:`A` and the relation words are
of the form :math:`aub = avb` where :math:`a, b\in A` (possibly :math:` a = b` )
and :math:`u, v\in A ^ *`, then *p* is strongly compressible.
See `Section 3.2 <https://doi.org/10.1007/s00233-021-10216-8>`_ for details.

:param p: the presentation.
:type p: Presentation

:returns: Whether the presentation is strongly compressible.
:rtype: bool

.. seealso::
      * :any:`strongly_compress`

)pbdoc");
      m.def(
          "presentation_length",
          [](Presentation_ const& p) { return presentation::length(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> int:
:only-document-once:
Return the sum of the lengths of the rules.

:param p: the presentation.
:type p: Presentation

:returns: The length of the presentation.
:rtype: int

)pbdoc");
      m.def(
          "presentation_longest_rule",
          [](Presentation_ const& p) {
            if (p.rules.empty()) {
              LIBSEMIGROUPS_EXCEPTION("expected non-zero number of rules.");
            }
            return std::distance(p.rules.cbegin(),
                                 presentation::longest_rule(p));
          },
          R"pbdoc(
:sig=(p: Presentation) -> int:
:only-document-once:
Return the index of the left-hand side of the longest rule.

Returns the index of the left-hand side of the first rule in the presentation
with maximal length. The *length* of a rule is defined to be the sum of the
lengths of its left-hand and right-hand sides.

:param p: the presentation.
:type p: Presentation

:returns: The index of the rule.
:rtype: int

:raises LibsemigroupsError:  if the length of ``p.rules`` is odd.
)pbdoc");
      m.def(
          "presentation_longest_rule_length",
          [](Presentation_ const& p) {
            if (p.rules.empty()) {
              LIBSEMIGROUPS_EXCEPTION("expected non-zero number of rules.");
            }
            return presentation::longest_rule_length(p);
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> int:
:only-document-once:
Return the maximum length of a rule in the presentation.

Returns the maximum length of a rule in the presentation. The *length* of a rule
is defined to be the sum of the lengths of its left-hand and right-hand sides.

:param p: the presentation.
:type p: Presentation

:returns: The maximum length.
:rtype: int

:raises LibsemigroupsError:  if the length of ``p.rules`` is odd.
)pbdoc");
      m.def("presentation_longest_subword_reducing_length",
            &presentation::longest_subword_reducing_length<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> Word:
:only-document-once:
Return the longest common subword of the rules.

If it is possible to find a subword :math:`w` of the rules :math:`u_1 = v_1,
\ldots, u_n = v_n` such that the introduction of a new generator :math:`z` and
the relation :math:`z = w` reduces the :any:`presentation.length` of the
presentation, then this function returns the longest such word :math:`w`.
If no such word can be found, then a word of length :math:`0` is returned.

:param p: the presentation.
:type p: Presentation

:returns: The longest common subword, if it exists.
:rtype: :ref:`Word<pseudo_word_type_helper>`

)pbdoc");
      m.def(
          "presentation_make_semigroup",
          [](Presentation_& p) {
            return from_int(presentation::make_semigroup<Word>(p));
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> Letter | Undefined:
:only-document-once:

Convert a monoid presentation to a semigroup presentation.

This function modifies its argument in-place by replacing the empty word in all
relations by a new generator, and the identity rules for that new generator.
If ``p.contains_empty_word()`` is ``False``, then the presentation is not
modified and :any:`UNDEFINED` is returned. If a new generator is added as the
identity, then this generator is returned.

:param p: the presentation.
:type p: Presentation

:returns: The new generator added, if any, and :any:`UNDEFINED` if not.
:rtype: :ref:`Letter<pseudo_letter_type_helper>` | Undefined

:raises LibsemigroupsError:  if :any:`replace_word` or
  :any:`add_identity_rules` does.
)pbdoc");
      m.def("presentation_normalize_alphabet",
            &presentation::normalize_alphabet<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Normalize the alphabet to :math:`\{0, \ldots, n - 1\}`.

Modify the presentation in-place so that the alphabet is :math:`\{0, \ldots,
n - 1\}` (or equivalent) and rewrites the rules to use this alphabet. If the
alphabet is already normalized, then no changes are made to the presentation.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:
  if :any:`Presentation.throw_if_bad_alphabet_or_rules` raises an exception on
  the initial presentation.)pbdoc");
      m.def("presentation_reduce_complements",
            &presentation::reduce_complements<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
If there are rules :math:`u = v` and :math:`v = w` where :math:`|w| < |v|`,
then replace :math:`u = v` by :math:`u = w`.

Attempts to reduce the length of the words by finding the equivalence relation
on the relation words generated by the pairs of identical relation words. If
:math:`\{u_1, u_2, \ldots, u_n\}` are the distinct words in an equivalence class
and :math:`u_1` is the short-lex minimum word in the class, then the relation
words are replaced by :math:`u_1 = u_2, u_1 = u_3, \cdots, u_1 = u_n`.
The rules may be reordered by this function even if there are no reductions
found.

:param p: the presentation to add rules to.
:type p: Presentation

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.)pbdoc");

      m.def("presentation_reduce_to_2_generators",
            &presentation::reduce_to_2_generators<Word>,
            py::arg("p"),
            py::arg("index") = 0,
            R"pbdoc(
:sig=(p: Presentation, index: int) -> bool:
:only-document-once:
Reduce the number of generators in a one relation presentation to 2.

Reduce the number of generators in a one relation presentation to ``2``.
Returns ``True`` if the one relation presentation *p* has been modified
and ``False`` if not. A one relation presentation is *left cycle-free*
if the relation words start with distinct letters. In other words, if the
alphabet of the presentation *p* is :math:`A` and the relation words are of the
form :math:`au = bv` where :math:`a, b\in A` with :math:`a \neq b` and
:math:`u, v \in A ^ *`, then *p* is left cycle-free.

The word problem for a left cycle-free one relation monoid is solvable if
the word problem for the modified version obtained from this function is
solvable.

:param p: the presentation.
:type p: Presentation

:param index:
  determines the choice of letter to use, ``0`` uses
  ``p.rules[0][0]`` and ``1`` uses ``p.rules[1][0]`` (defaults to: ``0``).
:type index: int

:returns: Whether or not the presentation has been modified.
:rtype: bool

:raises LibsemigroupsError:  if *index* is not ``0`` or ``1``.
)pbdoc");
      m.def("presentation_remove_duplicate_rules",
            &presentation::remove_duplicate_rules<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Remove duplicate rules.

Removes all but one instance of any duplicate rules (if any). Note that rules of
the form :math:`u = v` and :math:`v = u` (if any) are considered duplicates.
Also note that the rules may be reordered by this function even if there are no
duplicate rules.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.

:complexity: Linear in the number of rules.)pbdoc");
      m.def("presentation_remove_redundant_generators",
            &presentation::remove_redundant_generators<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Remove any trivially redundant generators.

If one side of any of the rules in the presentation *p* is a letter ``a`` and
the other side of the rule does not contain ``a``, then this function replaces
every occurrence of ``a`` in every rule by the other side of the rule. This
substitution is performed for every such rule in the presentation; and the
trivial rules (with both sides being identical) are removed. If both sides of a
rule are letters, then the greater letter is replaced by the lesser one.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.)pbdoc");
      m.def("presentation_remove_trivial_rules",
            &presentation::remove_trivial_rules<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Remove rules consisting of identical words.

Removes all instances of rules (if any) where the left-hand side and the
right-hand side are identical.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.

:complexity: Linear in the number of rules.)pbdoc");
      m.def(
          "presentation_replace_subword",
          [](Presentation_& p, Word const& existing, Word const& replacement) {
            return presentation::replace_subword(p, existing, replacement);
          },
          py::arg("p"),
          py::arg("existing"),
          py::arg("replacement"),
          R"pbdoc(
:sig=(p: Presentation, existing: Word, replacement: Word) -> None:
:only-document-once:
Replace non-overlapping instances of a subword by another word.

If *existing* and *replacement* are words, then this function replaces every
non-overlapping instance of *existing* in every rule by *replacement*. The
presentation *p* is changed in-place.

:param p: the presentation.
:type p: Presentation

:param existing: the word to be replaced.
:type existing: :ref:`Word<pseudo_word_type_helper>`

:param replacement: the replacement word.
:type replacement: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:  if *existing* is empty.)pbdoc");
      m.def("presentation_replace_word",
            &presentation::replace_word<Word>,
            py::arg("p"),
            py::arg("existing"),
            py::arg("replacement"),
            R"pbdoc(
:sig=(p: Presentation, existing: Word, replacement: Word) -> None:
:only-document-once:
Replace instances of a word on either side of a rule by another word.

If *existing* and *replacement* are words, then this function replaces every
instance of *existing* in every rule of the form *existing* :math:`= w` or :math:`w =`
*existing*, with the word *replacement*. The presentation *p* is changed in-place.

:param p: the presentation.
:type p: Presentation

:param existing: the word to be replaced.
:type existing: :ref:`Word<pseudo_word_type_helper>`

:param replacement: the replacement word.
:type replacement: :ref:`Word<pseudo_word_type_helper>`

)pbdoc");
      m.def(
          "presentation_replace_word_with_new_generator",
          [](Presentation_& p, Word const& w) {
            return presentation::replace_word_with_new_generator(p, w);
          },
          py::arg("p"),
          py::arg("w"),
          R"pbdoc(
:sig=(p: Presentation, w: Word) -> Letter:
:only-document-once:
Replace non-overlapping instances of a word with a new generator.

This function replaces every non-overlapping instance (from left to right) of
*w* in every rule, adds a new generator :math:`z`, and the rule :math:`w = z`.
The new generator and rule are added even if *w* is not a subword of any rule.

:param p: the presentation.
:type p: Presentation

:param w: the subword to replace.
:type w: :ref:`Word<pseudo_word_type_helper>`

:returns: The new generator added.
:rtype: :ref:`Letter<pseudo_letter_type_helper>`

:raises LibsemigroupsError:  if *w* is empty.)pbdoc");
      m.def(
          "presentation_reverse",
          [](Presentation<Word>& p) { presentation::reverse(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Reverse every rule.

:param p: the presentation.
:type p: Presentation
)pbdoc");
      m.def(
          "presentation_shortest_rule",
          [](Presentation_ const& p) {
            if (p.rules.empty()) {
              LIBSEMIGROUPS_EXCEPTION("expected non-zero number of rules.");
            }
            return std::distance(p.rules.cbegin(),
                                 presentation::shortest_rule(p));
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> int:
:only-document-once:
Return the index of the left-hand side of the shortest rule.

Returns the index of the left-hand side of the first rule in the presentation
with minimal length. The *length* of a rule is defined to be the sum of the
lengths of its left-hand and right-hand sides.

:param p: the presentation.
:type p: Presentation

:returns: The index of the rule.
:rtype: int

:raises LibsemigroupsError:  if the length of ``p.rules`` is odd.
)pbdoc");
      m.def(
          "presentation_shortest_rule_length",
          [](Presentation_ const& p) {
            if (p.rules.empty()) {
              LIBSEMIGROUPS_EXCEPTION("expected non-zero number of rules.");
            }
            return presentation::shortest_rule_length(p);
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> int:
:only-document-once:
Return the minimum length of a rule in the presentation.

Returns the minimum length of a rule in the presentation. The *length* of a rule
is defined to be the sum of the lengths of its left-hand and right-hand sides.

:param p: the presentation.
:type p: Presentation

:returns: The length of the shortest rule.
:rtype: int

:raises LibsemigroupsError:  if the length of ``p.rules`` is odd.
)pbdoc");
      // TODO add functionality for different comparison functions when they've
      // been bound
      m.def(
          "presentation_sort_each_rule",
          [](Presentation_& p) { return presentation::sort_each_rule(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> bool:
:only-document-once:
Sort the left-hand and right-hand side of each rule by shortlex.

Sort each rule :math:`u = v` so that the left-hand side is shortlex greater than
the right-hand side, and return :any:`True` if any of the rules are changed.

:param p: the presentation whose rules should be sorted.
:type p: Presentation

:returns: Whether any of the rules were changed.
:rtype: bool

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.

:complexity: Linear in the number of rules.)pbdoc");
      m.def(
          "presentation_sort_each_rule",
          [](Presentation<Word>&                            p,
             std::function<bool(Word const&, Word const&)>& cmp) {
            return presentation::sort_each_rule(p, cmp);
          },
          py::arg("p"),
          py::arg("cmp"),
          R"pbdoc(
:sig=(p: Presentation, cmp: collections.abc.Callable[[Word, Word], bool]) -> bool:
:only-document-once:
Sort the left-hand and right-hand side of each rule relative to cmp.

Sort each rule :math:`u = v` so that the left-hand side is greater than the
right-hand side with respect to ``cmp``, and return :any:`True` if any of the
rules are changed.


:param p: the presentation whose rules should be sorted.
:type p: Presentation

:param cmp: the comparison function.
:type cmp: collections.abc.Callable[[:ref:`Word<pseudo_word_type_helper>`, :ref:`Word<pseudo_word_type_helper>`], bool]

:returns: Whether any of the rules were changed.
:rtype: bool

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.

:complexity: Linear in the number of rules.
)pbdoc");
      m.def(
          "presentation_sort_rules",
          [](Presentation_& p) { presentation::sort_rules(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:
Sort all of the rules by shortlex.

Sort the rules :math:`u_1 = v_1, \ldots, u_n = v_n` so that :math:`u_1v_1 <
\cdots < u_nv_n` where :math:`<` is the shortlex order.

:param p: the presentation to sort.
:type p: Presentation

:raises LibsemigroupsError:  if ``p.rules.size()`` is odd.)pbdoc");
      m.def("presentation_strongly_compress",
            &presentation::strongly_compress<Word>,
            py::arg("p"),
            R"pbdoc(
:sig=(p: Presentation) -> bool:
:only-document-once:

Strongly compress a one relation presentation.

Strongly compress a one relation presentation. Returns ``True`` if the
one relation presentation *p* has been modified and ``False`` if not. The
word problem is solvable for the input presentation if it is solvable for the
modified version.

:param p: the presentation.
:type p: Presentation

:returns: Whether or not the presentation has been modified.
:rtype: bool

.. seealso::
      * :any:`is_strongly_compressible`

)pbdoc");
      m.def(
          "presentation_to_gap_string",
          [](Presentation_ const& p, std::string const& var_name) {
            return presentation::to_gap_string(p, var_name);
          },
          py::arg("p"),
          py::arg("var_name"),
          R"pbdoc(
:sig=(p: Presentation, var_name: str) -> str:
:only-document-once:
Return the code that would create *p* in GAP.

This function returns the string of GAP code that could be used to create an
object with the same alphabet and rules as *p* in GAP. Presentations in GAP
are created by taking quotients of free semigroups or monoids.

:param p: the presentation.
:type p: Presentation

:param var_name: the name of the variable to be used in GAP.
:type var_name: str

:returns: The GAP string.
:rtype: str
)pbdoc");
      m.def(
          "presentation_to_ace_string",
          [](Presentation_ const& p) { return presentation::to_ace_string(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> str:
:only-document-once:
Returns a string containing the content of an ACE input file.

This function returns the string of ACE :cite:`Havas1999iy` input that could be
used to create an object with the same alphabet and rules as *p*.

:param p: the presentation.
:type p: Presentation

:returns: The ACE string.
:rtype: str

:raises LibsemigroupsError: if ``p.alphabet()`` contains any duplicate letters.
:raises LibsemigroupsError: if any of the letters in the alphabet of
  *p* are not lowercase, or do not correspond to a lowercase letter when
  transformed to a string using :any:`words.human_readable_letter`.

.. note::

  ACE assumes that presentations are group presentations, where the the alphabet
  consists of lowercase letters, and inverses correspond to the equivalent
  uppercase letters. Therefore, a valid ACE presentation may not be a valid
  ``libsemigroups_pybdind11`` :any:`Presentation`; for example, it is possible
  for relations in an ACE presentation to contain uppercase letters that are not
  explicitly named as generators, as long as their lowercase counterparts are
  listed as generators.
)pbdoc");
      m.def(
          "presentation_throw_if_bad_inverses",
          [](Presentation_ const& p, Word const& inverses) {
            presentation::throw_if_bad_inverses(p, inverses);
          },
          py::arg("p"),
          py::arg("vals"),
          R"pbdoc(
:sig=(p: Presentation, vals: Word) -> None:
:only-document-once:

Validate if *vals* act as semigroup inverses in *p*.

Check if the values in *vals* act as semigroup inverses for the letters of the
alphabet of *p*. Specifically, it checks that the :math:`i`-th value in *vals*
acts as an inverse for the :math:`i`-th value in ``p.alphabet()``.

Let :math:`x_i` be the :math:`i`-th letter in ``p.alphabet()``, and suppose
that :math:`x_i=v_j` is in the :math:`j`-th position of *vals*. This function
checks that :math:`v_i = x_j`, and therefore that :math:`(x_i^{-1})^{-1} = x_i`.

:param p: the presentation.
:type p: Presentation

:param vals: the values to check if they act as inverses.
:type vals: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
      if the length of *vals* is not the same as the length of
      ``p.alphabet()``.
:raises LibsemigroupsError:
      if *vals* contains letters not in the alphabet.
:raises LibsemigroupsError:
      if *vals* contains duplicate letters.
:raises LibsemigroupsError:
      if the values in *vals* do not serve as semigroup inverses.
)pbdoc");

      m.def(
          "presentation_balance",
          [](Presentation<Word>& p) { presentation::balance(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> None:
:only-document-once:

Detect inverses and balance the length of the left-hand and right-hand sides.

This function calls the 3-argument version of ``balance`` where the 2nd and 3rd
arguments are deduced from the rules in the presentation if possible as
follows: the rules of the presentation where one side has length
``2`` and the other has length ``0`` are detected. For any such rule we remember
that the first letter is the inverse of the second and vice versa. If there
are no such rules, then no changes are made. If there are multiple different
such rules and we deduce conflicting values for the inverse of a letter, then
an exception is thrown.

:param p: the presentation.
:type p: Presentation

:raises LibsemigroupsError:
  if :any:`throw_if_bad_alphabet_or_rules` raises an exception.
:raises LibsemigroupsError:
  if conflicting inverses for any letter are detected.)pbdoc");

      m.def(
          "presentation_balance",
          [](Presentation<Word>& p, Word const& inverses) {
            presentation::balance(p, inverses);
          },
          py::arg("p"),
          py::arg("inverses"),
          R"pbdoc(
:sig=(p: Presentation, inverses: Word) -> None:
:only-document-once:

Balance the length of the left-hand and right-hand sides.

This function calls the 3-argument version of :any:`balance` where the 2nd
parameter is defined to be ``p.alphabet()``.

:param p: the presentation.
:type p: Presentation

:param inverses: the inverses of the letters.
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if :any:`throw_if_bad_alphabet_or_rules` raises an exception.

:raises LibsemigroupsError:
  if :any:`throw_if_bad_inverses` raises an exception when called with
  ``p.alphabet()`` and ``inverses``. This function does not check that the
  values in ``inverses`` are actually inverses for the values in
  ``p.alphabet()``, and balances the relations as described in :any:`balance`
  assuming that this is the case.
)pbdoc");

      m.def(
          "presentation_balance",
          [](Presentation<Word>& p, Word const& letters, Word const& inverses) {
            presentation::balance(p, letters, inverses);
          },
          py::arg("p"),
          py::arg("letters"),
          py::arg("inverses"),
          R"pbdoc(
:sig=(p: Presentation, letters: Word, inverses: Word) -> None:
:only-document-once:

Balance the length of the left-hand and right-hand sides.

This function first sorts the sides of each rule so that the larger
side of the rule is on the left. Then for each rule, while the last
letter of the left-hand side is in *letters*, the last letter of the
left-hand side is removed and the corresponding value in *inverses* is
appended to the end of the right-hand side. Next, while the first
letter of the left-hand side is in *letters*, the first letter of the
left-hand side is removed and the corresponding value in *inverses* is
appended to the front of the right-hand side.

:param p: the presentation.
:type p: Presentation

:param letters: the letters that can be replaced in the left-hand side.
:type letters: :ref:`Word<pseudo_word_type_helper>`

:param inverses: the inverses of the letters.
:type inverses: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if :any:`throw_if_bad_alphabet_or_rules` raises an exception.

:raises LibsemigroupsError:
  if :any:`throw_if_bad_inverses` raises an exception when called with
  *letters* and *inverses*. This does not check that the values in *inverses*
  are actually inverses for the values in *letters*, and balances the relations
  as described above.
)pbdoc");

      m.def(
          "presentation_add_cyclic_conjugates",
          [](Presentation<Word>& p, Word const& relator) {
            presentation::add_cyclic_conjugates(p, relator);
          },
          py::arg("p"),
          py::arg("relator"),
          R"pbdoc(
:sig=(p: Presentation, relator: Word) -> None:
:only-document-once:

Add all cyclic permutations of a word as relators in a presentation.

This function adds one rule with left-hand side ``w`` and right-hand side the
empty word to the presentation *p*, for every cyclic permutation ``w`` of
*relator*.

:param p: the presentation.
:type p: Presentation

:param relator: the word.
:type relator: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if *relator* contains any letters not belonging to ``p.alphabet()``.

:raises LibsemigroupsError:  if *p* does not contain the empty word.)pbdoc");
      m.def("presentation_add_idempotent_rules",
            &presentation::add_idempotent_rules<Word>,
            py::arg("p"),
            py::arg("letters"),
            R"pbdoc(
:sig=(p: Presentation, letters: Word) -> None:
:only-document-once:
Add rules that define idempotents.

Adds rules to *p* of the form :math:`a^2 = a` for every letter :math:`a` in
*letters*.

:param p: the presentation to add rules to.
:type p: Presentation

:param letters: the letters to make idempotent.
:type letters: :ref:`Word<pseudo_word_type_helper>`

:raises LibsemigroupsError:
  if any letter in *letters* is not in ``p.alphabet()``.
)pbdoc");

      // We do not bind presentation::find_rule because it returns an iterator
      //
      m.def(
          "presentation_index_rule",
          [](Presentation<Word>& p, Word const& lhs, Word const& rhs) {
            return from_int(presentation::index_rule(p, lhs, rhs));
          },
          py::arg("p"),
          py::arg("lhs"),
          py::arg("rhs"),
          R"pbdoc(
:sig=(p: Presentation, lhs: Word, rhs: Word) -> int | Undefined:
:only-document-once:

Returns the index of a rule or :any:`UNDEFINED`.

This function returns the minimum index ``i`` of *lhs* such that ``p.rules[i +
1]`` equals *rhs*; or :any:`UNDEFINED` if there is no such rule.

:param p: the presentation.
:type p: Presentation

:param lhs: the left-hand side of the rule.
:type lhs: :ref:`Word<pseudo_word_type_helper>`

:param rhs: the right-hand side of the rule.
:type rhs: :ref:`Word<pseudo_word_type_helper>`

:returns: The index of the rule or :any:`UNDEFINED`.
:rtype: int | Undefined

:raises LibsemigroupsError:
  if ``p.throw_if_bad_alphabet_or_rules()`` raises an exception.
)pbdoc");

      m.def(
          "presentation_is_normalized",
          [](Presentation<Word>& p) { return presentation::is_normalized(p); },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> bool:
:only-document-once:

Check if the presentation is normalized.

This function returns ``True`` if the :any:`Presentation.alphabet` of *p* is
``0`` to ``p.alphabet().size() - 1`` and ``False`` otherwise.

:param p: the presentation to check.
:type p: Presentation

:returns: Whether or not the presentation *p* is normalized.
:rtype: bool
)pbdoc");

      m.def("presentation_is_rule",
            &presentation::is_rule<Word>,
            py::arg("p"),
            py::arg("lhs"),
            py::arg("rhs"),
            R"pbdoc(
:sig=(p: Presentation, lhs: Word, rhs: Word) -> bool:
:only-document-once:

Check whether a rule belongs to a presentation.

This function returns ``True`` if *lhs* and *rhs* form a rule in *p*.
That is, if *lhs* occurs in an even index position in ``p.rules``
and *rhs* is the next item in ``p.rules``.

:param p: the presentation.
:type p: Presentation

:param lhs: the left-hand side of the rule.
:type lhs: :ref:`Word<pseudo_word_type_helper>`

:param rhs: the right-hand side of the rule.
:type rhs: :ref:`Word<pseudo_word_type_helper>`

:returns: Whether or not *lhs* and *rhs* form a rule in *p*.
:rtype: bool

:raises LibsemigroupsError:
  if :any:`Presentation.throw_if_bad_alphabet_or_rules` raises an exception.
)pbdoc");

      m.def(
          "presentation_try_detect_inverses",
          [](Presentation<Word>& p) {
            return presentation::try_detect_inverses(p);
          },
          py::arg("p"),
          R"pbdoc(
:sig=(p: Presentation) -> tuple[str | list[int], str | list[int]]:
:only-document-once:

Try to detect group inverses.

This function tries to deduce group theoretic inverses defined by the rules of
the presentation *p* as follows: the rules of the presentation where one
side has length 2 and the other has length 0 are detected. For any such rule we
remember that the first letter is a possible inverse of the second. If rules of
the form ``ab=1`` and ``ba=1`` are detected, then ``a`` has inverse ``b`` and
vice versa. If there are multiple different such rules and we deduce
conflicting values for the inverse of a letter, then an exception is
raised.

:param p: the presentation.
:type p: Presentation

:returns:
  A tuple where the first item consists of letters such that an inverse was
  detected; and the second item consists of the inverses such that the item in
  position ``i`` is the inverse of the letter in position ``i``.
:rtype: tuple[str | list[int], str | list[int]]

:raises LibsemigroupsError:
  if :any:`throw_if_bad_alphabet_or_rules` raises an exception.
:raises LibsemigroupsError:
  if conflicting inverses for any letter are detected.)pbdoc");
    }  // bind_present

    template <typename Word>
    void bind_inverse_present(py::module& m, std::string const& name) {
      using InversePresentation_ = InversePresentation<Word>;

      py::class_<InversePresentation_, Presentation<Word>> thing(m,
                                                                 name.c_str(),
                                                                 R"pbdoc(
An implementation of inverse presentations for semigroups or monoids.

This class can be used to construct inverse presentations for semigroups or
monoids and is intended to be used as the input to other algorithms in
``libsemigroups_pybind11``.

This class inherits from :any:`Presentation`.)pbdoc");
      thing.def("__repr__", [](InversePresentation_ const& p) -> std::string {
        return to_human_readable_repr(p);
      });
      thing.def(py::init<Presentation<Word> const&>(), R"pbdoc(
:sig=(self: InversePresentation, p: Presentation) -> None:
Construct an InversePresentation from a Presentation.

Construct an :any:`InversePresentation`, initially with empty inverses,
from a :any:`Presentation`.

:param p: the presentation to construct from.
:type p: Presentation
)pbdoc");
      thing.def(py::init<>(), R"pbdoc(
:sig=(self: InversePresentation) -> None:
Default constructor.

Constructs an empty :any:`InversePresentation` with no rules, no alphabet, and
no inverses.)pbdoc");
      thing.def(
          "copy",
          [](InversePresentation_ const& self) {
            return InversePresentation_(self);
          },
          R"pbdoc(
:sig=(self: InversePresentation) -> InversePresentation:

Copy a :any:`InversePresentation` object.

:returns: A copy.
:rtype: InversePresentation
)pbdoc");
      thing.def("__copy__", [](InversePresentation_ const& that) {
        return InversePresentation_(that);
      });

      thing.def("inverse",
                &InversePresentation_::inverse,
                py::arg("x"),
                R"pbdoc(
:sig=(self: InversePresentation, x: Letter) -> Letter:
Return the inverse of a letter in the alphabet.

Returns the inverse of the letter *x*.

:param x: the letter whose inverse is sought.
:type x: :ref:`Letter<pseudo_letter_type_inv_class>`

:returns: The inverse of *x*.
:rtype: :ref:`Letter<pseudo_letter_type_inv_class>`

:raises LibsemigroupsError:
  if no inverses have been set, or if ``index(x)`` raises an exception.
)pbdoc");
      thing.def(
          "inverses",
          [](InversePresentation_& self) { return self.inverses(); },
          R"pbdoc(
:sig=(self: InversePresentation) -> Word:
Return the inverse of each letter in the alphabet.

Returns the inverse of each letter in the alphabet.

:returns: The inverses.
:rtype: :ref:`Word<pseudo_word_type_inv_class>`
)pbdoc");
      thing.def(
          "inverses",
          [](InversePresentation_&                           self,
             typename InversePresentation_::word_type const& w) {
            return self.inverses(w);
          },
          py::arg("w"),
          R"pbdoc(
:sig=(self: InversePresentation, w: Word) -> InversePresentation:
Set the inverse of each letter in the alphabet.

:param w: a word containing the inverses.
:type w: :ref:`Word<pseudo_word_type_inv_class>`

:returns: *self*.
:rtype: InversePresentation

:raises LibsemigroupsError:
  if the alphabet contains duplicate letters.
:raises LibsemigroupsError:
  if the inverses do not act as semigroup inverses.

.. note::

      Whilst the alphabet is not specified as an argument to this function, it
      is necessary to validate the alphabet here; a specification of inverses
      cannot make sense if the alphabet contains duplicate letters.

.. seealso::

      * :any:`Presentation.throw_if_alphabet_has_duplicates`
      * :any:`presentation.throw_if_bad_inverses`
)pbdoc");
      thing.def("throw_if_bad_alphabet_rules_or_inverses",
                &InversePresentation_::throw_if_bad_alphabet_rules_or_inverses,
                R"pbdoc(
:sig=(self: InversePresentation) -> None:

Check if the :any:`InversePresentation` is valid.

Check if the :any:`InversePresentation` is valid. Specifically, check that the
alphabet does not contain duplicate letters, that all rules only contain letters
defined in the alphabet, and that the inverses act as semigroup inverses.

:raises LibsemigroupsError:
      if the alphabet contains duplicate letters.
:raises LibsemigroupsError:
      if the rules contain letters not defined in the alphabet.
:raises LibsemigroupsError:
      if the inverses do not act as semigroup inverses.

.. seealso::

      * :any:`Presentation.throw_if_bad_alphabet_or_rules`
      * :any:`presentation.throw_if_bad_inverses`
)pbdoc");
    }  // bind_inverse_present
  }  // namespace

  void init_present(py::module& m) {
    bind_present<word_type>(m, "PresentationWord");
    bind_present<std::string>(m, "PresentationString");
  }

  void init_inverse_present(py::module& m) {
    bind_inverse_present<word_type>(m, "InversePresentationWord");
    bind_inverse_present<std::string>(m, "InversePresentationString");
  }
}  // namespace libsemigroups