Quelle  test-present.cpp   Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2022 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/>.
//

#define CATCH_CONFIG_ENABLE_PAIR_STRINGMAKER

#include <cstddef>  // for size_t

#include "catch.hpp"      // for REQUIRE, REQUIRE_THROWS_AS, REQUI...
#include "test-main.hpp"  // for LIBSEMIGROUPS_TEST_CASE

#include "libsemigroups/bipart.hpp"        // for Bipartition
#include "libsemigroups/containers.hpp"    // for StaticVector1
#include "libsemigroups/froidure-pin.hpp"  // for FroidurePin
#include "libsemigroups/int-range.hpp"     // for IntegralRange
#include "libsemigroups/knuth-bendix.hpp"  // for redundant_rule
#include "libsemigroups/make-present.hpp"  // for make
#include "libsemigroups/present.hpp"       // for Presentation
#include "libsemigroups/siso.hpp"          // for Sislo
#include "libsemigroups/types.hpp"         // for word_type

namespace libsemigroups {

  struct LibsemigroupsException;  // forward decl

  namespace {
    template <typename W>
    void check_constructors(Presentation<W>& p) {
      p.validate();
      Presentation<W> pp(p);
      pp.validate();
      REQUIRE(pp.alphabet() == p.alphabet());
      REQUIRE(pp.rules == p.rules);

      Presentation<W> q(std::move(p));
      q.validate();
      REQUIRE(q.alphabet() == pp.alphabet());
      REQUIRE(q.rules == pp.rules);

      p = q;
      p.validate();
      REQUIRE(q.alphabet() == p.alphabet());
      REQUIRE(q.rules == p.rules);

      p = std::move(q);
      p.validate();
      REQUIRE(pp.alphabet() == p.alphabet());
      REQUIRE(pp.rules == p.rules);
    }

    template <typename W>
    void check_alphabet_letters() {
      Presentation<W> p;
      p.alphabet({0, 1, 2});
      REQUIRE(p.alphabet() == W({0, 1, 2}));
      REQUIRE(p.letter(0) == 0);
      REQUIRE(p.letter(1) == 1);
      REQUIRE(p.letter(2) == 2);
      p.alphabet(4);
      REQUIRE(p.alphabet() == W({0, 1, 2, 3}));
      p.validate();
      REQUIRE_THROWS_AS(p.alphabet({0, 1, 1}), LibsemigroupsException);

      presentation::add_rule(p, {0, 1, 2, 1}, {0, 0});
      presentation::add_rule(p, {4, 1}, {0, 5});
      presentation::add_rule(p, {4, 1}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1});
      p.alphabet_from_rules();
      REQUIRE(p.alphabet() == W({0, 1, 2, 4, 5}));
      REQUIRE(p.index(0) == 0);
      REQUIRE(p.index(1) == 1);
      REQUIRE(p.index(2) == 2);
      REQUIRE(p.index(4) == 3);
      REQUIRE(p.index(5) == 4);

      REQUIRE(!p.contains_empty_word());
      presentation::add_rule(p, {4, 1}, {});
      p.alphabet_from_rules();
      REQUIRE(p.contains_empty_word());

      p.alphabet({0, 1, 2, 3});
      REQUIRE(p.alphabet() == W({0, 1, 2, 3}));
    }

    template <typename W>
    void check_contains_empty_word() {
      Presentation<W> p;
      REQUIRE(!p.contains_empty_word());
      p.contains_empty_word(true);
      REQUIRE(p.contains_empty_word());
      p.contains_empty_word(false);
      REQUIRE(!p.contains_empty_word());
    }

    template <typename W>
    void check_validate_rules_throws() {
      Presentation<W> p;
      p.rules.emplace_back();
      REQUIRE_THROWS_AS(p.validate_rules(), LibsemigroupsException);
    }

    template <typename W>
    void check_add_rules() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {0, 0});
      Presentation<W> q;
      presentation::add_rule(q, {4, 1}, {0, 5});
      presentation::add_rule(q, {4, 1}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1});
      presentation::add_rules(p, q);
      REQUIRE(p.rules
              == std::vector<W>({{0, 1, 2, 1},
                                 {0, 0},
                                 {4, 1},
                                 {0, 5},
                                 {4, 1},
                                 {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}}));
      REQUIRE(q.rules
              == std::vector<W>(
                  {{4, 1}, {0, 5}, {4, 1}, {0, 1, 1, 1, 1, 1, 1, 1, 1, 1}}));
      REQUIRE_THROWS_AS(p.validate(), LibsemigroupsException);
      REQUIRE_THROWS_AS(q.validate(), LibsemigroupsException);
    }

    template <typename W>
    void check_add_identity_rules() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {0, 0});
      REQUIRE_THROWS_AS(presentation::add_identity_rules(p, 0),
                        LibsemigroupsException);
      p.alphabet_from_rules();
      presentation::add_identity_rules(p, 0);
      REQUIRE(p.rules
              == std::vector<W>({{0, 1, 2, 1},
                                 {0, 0},
                                 {0, 0},
                                 {0},
                                 {1, 0},
                                 {1},
                                 {0, 1},
                                 {1},
                                 {2, 0},
                                 {2},
                                 {0, 2},
                                 {2}}));
    }

    template <typename W>
    void check_add_zero_rules() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {0, 0});
      REQUIRE_THROWS_AS(presentation::add_zero_rules(p, 0),
                        LibsemigroupsException);
      p.alphabet_from_rules();
      presentation::add_zero_rules(p, 0);
      REQUIRE(p.rules
              == std::vector<W>({{0, 1, 2, 1},
                                 {0, 0},
                                 {0, 0},
                                 {0},
                                 {1, 0},
                                 {0},
                                 {0, 1},
                                 {0},
                                 {2, 0},
                                 {0},
                                 {0, 2},
                                 {0}}));
    }

    template <typename W>
    void check_add_inverse_rules() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {0, 0});
      p.alphabet_from_rules();

      REQUIRE_THROWS_AS(presentation::add_inverse_rules(p, {0, 1, 1}, 0),
                        LibsemigroupsException);
      REQUIRE_THROWS_AS(presentation::add_inverse_rules(p, {1, 2, 0}, 0),
                        LibsemigroupsException);
      p.alphabet({0, 1, 2, 3});
      REQUIRE_THROWS_AS(presentation::add_inverse_rules(p, {0, 2, 3, 1}, 0),
                        LibsemigroupsException);
      REQUIRE_THROWS_AS(presentation::add_inverse_rules(p, {0, 2, 1}, 0),
                        LibsemigroupsException);
      p.alphabet({0, 1, 2});
      presentation::add_inverse_rules(p, {0, 2, 1}, 0);

      REQUIRE(
          p.rules
          == std::vector<W>({{0, 1, 2, 1}, {0, 0}, {1, 2}, {0}, {2, 1}, {0}}));
      // When id is UNDEFINED
      presentation::add_inverse_rules(p, {0, 2, 1});
      REQUIRE(p.rules
              == std::vector<W>({{0, 1, 2, 1},
                                 {0, 0},
                                 {1, 2},
                                 {0},
                                 {2, 1},
                                 {0},
                                 {0, 0},
                                 {},
                                 {1, 2},
                                 {},
                                 {2, 1},
                                 {}}));
    }

    template <typename W>
    void check_remove_duplicate_rules() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::remove_duplicate_rules(p),
                        LibsemigroupsException);
      p.rules.push_back(W({0, 0}));
      presentation::add_rule(p, {0, 0}, {0, 1, 2, 1});
      p.alphabet_from_rules();
      REQUIRE(p.rules.size() == 4);
      presentation::remove_duplicate_rules(p);
      REQUIRE(p.rules.size() == 2);
    }

    template <typename W>
    void check_reduce_complements() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::reduce_complements(p),
                        LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));

      presentation::add_rule(p, {1, 2, 1}, {1, 1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      p.alphabet_from_rules();
      presentation::reduce_complements(p);
      presentation::sort_each_rule(p);
      presentation::sort_rules(p);
      REQUIRE(p.rules
              == std::vector<W>({{1, 1},
                                 {0},
                                 {1, 2, 1},
                                 {0},
                                 {0, 1, 2, 1},
                                 {0},
                                 {1, 1, 2, 1},
                                 {0}}));
    }

    template <typename W>
    void check_sort_each_rule() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::sort_each_rule(p),
                        LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));

      presentation::add_rule(p, {1, 2, 1}, {1, 1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      p.alphabet_from_rules();
      presentation::sort_each_rule(p);
      REQUIRE(p.rules
              == std::vector<W>({{0, 1, 2, 1},
                                 {1, 2, 1},
                                 {1, 1, 2, 1},
                                 {1, 2, 1},
                                 {1, 1, 2, 1},
                                 {1, 1},
                                 {1, 2, 1},
                                 {1, 1},
                                 {1, 2, 1},
                                 {0}}));
    }

    template <typename W>
    void check_sort_rules() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::sort_rules(p), LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));
      presentation::add_rule(p, {1, 2, 1}, {1, 1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      p.alphabet_from_rules();
      presentation::sort_rules(p);
      REQUIRE(p.rules
              == std::vector<W>({{1, 2, 1},
                                 {0},
                                 {1, 1},
                                 {1, 2, 1},
                                 {1, 1, 2, 1},
                                 {1, 1},
                                 {0, 1, 2, 1},
                                 {1, 2, 1},
                                 {1, 2, 1},
                                 {1, 1, 2, 1}}));
      REQUIRE(presentation::are_rules_sorted(p));
    }

    template <typename W>
    void check_longest_common_subword() {
      {
        // Normalized alphabet
        Presentation<W> p;
        p.rules.push_back(W({0, 1, 2, 1}));
        REQUIRE_NOTHROW(presentation::longest_common_subword(p));
        p.rules.push_back(W({1, 2, 1}));
        presentation::add_rule(p, {1, 2, 1}, {1, 1, 2, 1});
        presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
        presentation::add_rule(p, {1, 1}, {1, 2, 1});
        presentation::add_rule(p, {1, 2, 1}, {0});
        p.alphabet_from_rules();
        REQUIRE(presentation::longest_common_subword(p) == W({1, 2, 1}));
        presentation::replace_subword(p, W({1, 2, 1}), W({3}));
        presentation::add_rule(p, {3}, {1, 2, 1});
        REQUIRE(p.rules
                == std::vector<W>({{0, 3},
                                   {3},
                                   {3},
                                   {1, 3},
                                   {1, 3},
                                   {1, 1},
                                   {1, 1},
                                   {3},
                                   {3},
                                   {0},
                                   {3},
                                   {1, 2, 1}}));
      }
      {
        // Non-normalized alphabet
        Presentation<W> p;
        presentation::add_rule(p, {1, 2, 4, 2}, {2, 4, 2});
        presentation::add_rule(p, {2, 4, 2}, {2, 2, 4, 2});
        presentation::add_rule(p, {2, 2, 4, 2}, {2, 2});
        presentation::add_rule(p, {2, 2}, {2, 4, 2});
        presentation::add_rule(p, {2, 4, 2}, {1});
        p.alphabet_from_rules();
        REQUIRE(presentation::longest_common_subword(p) == W({2, 4, 2}));
        presentation::replace_subword(p, W({2, 4, 2}), W({0}));
        presentation::add_rule(p, W({0}), W({2, 4, 2}));
        REQUIRE(p.rules
                == std::vector<W>({{1, 0},
                                   {0},
                                   {0},
                                   {2, 0},
                                   {2, 0},
                                   {2, 2},
                                   {2, 2},
                                   {0},
                                   {0},
                                   {1},
                                   {0},
                                   {2, 4, 2}}));
      }
    }

    template <typename W>
    void check_redundant_rule() {
      FroidurePin<Bipartition> S;
      S.add_generator(Bipartition({{1, -1}, {2, -2}, {3, -3}, {4, -4}}));
      S.add_generator(Bipartition({{1, -2}, {2, -3}, {3, -4}, {4, -1}}));
      S.add_generator(Bipartition({{1, -2}, {2, -1}, {3, -3}, {4, -4}}));
      S.add_generator(Bipartition({{1, 2}, {3, -3}, {4, -4}, {-1, -2}}));
      REQUIRE(S.size() == 105);

      auto p = make<Presentation<W>>(S);
      REQUIRE(presentation::length(p) == 359);
      presentation::remove_duplicate_rules(p);
      REQUIRE(presentation::length(p) == 359);
      presentation::reduce_complements(p);
      REQUIRE(presentation::length(p) == 359);
      presentation::sort_each_rule(p);
      presentation::sort_rules(p);

      REQUIRE(presentation::length(p) == 359);
      REQUIRE(p.rules.size() == 86);

      p.alphabet_from_rules();
      auto it = presentation::redundant_rule(p, std::chrono::milliseconds(100));
      REQUIRE(*it == W({2, 1, 3, 1, 1, 2, 1, 2}));
      REQUIRE(*(it + 1) == W({1, 1, 2, 1, 3, 1, 2, 1}));
      p.rules.erase(it, it + 2);
      p.validate();
      // while (it != p.rules.cend()) { // Too time consuming and indeterminant
      //   REQUIRE(std::distance(it, p.rules.cend()) % 2 == 0);
      //   p.rules.erase(it, it + 2);
      //   p.validate();
      //   it = presentation::redundant_rule(p, std::chrono::milliseconds(8));
      // }
      REQUIRE(presentation::length(p) == 343);
      REQUIRE(p.rules.size() == 84);
    }

    template <typename W>
    void check_shortlex_compare_concat() {
      REQUIRE(detail::shortlex_compare_concat(
          W({0, 1, 2, 1}), W({0}), W({1, 1, 2, 1}), W({0})));
    }

    template <typename W>
    void check_remove_trivial_rules() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::remove_trivial_rules(p),
                        LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));
      presentation::add_rule(p, {1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      presentation::add_rule(p, {0}, {0});
      presentation::add_rule(p, {1}, {1});
      presentation::add_rule(p, {2}, {2});

      presentation::remove_trivial_rules(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}, {1, 2, 1}, {0}}));
      presentation::remove_trivial_rules(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}, {1, 2, 1}, {0}}));
    }

    template <typename W>
    void check_replace_subword() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_NOTHROW(presentation::replace_subword(p, W({0}), W({1})));
      p.rules.push_back(W({1, 2, 1}));
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});

      presentation::replace_subword(p, W({0}), W({1}));
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{1, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}, {1, 2, 1}, {1}}));

      presentation::replace_subword(p, W({0}), W({1}));
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{1, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}, {1, 2, 1}, {1}}));

      presentation::replace_subword(p, W({1, 2, 1}), W({0}));
      REQUIRE(p.rules
              == std::vector<W>({{1, 0}, {0}, {1, 0}, {1, 1}, {0}, {1}}));

      presentation::replace_subword(p, W({42, 42}), W({0}));
      REQUIRE(p.rules
              == std::vector<W>({{1, 0}, {0}, {1, 0}, {1, 1}, {0}, {1}}));

      p.rules.clear();
      presentation::add_rule(
          p, {1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1}, {1, 2, 1, 1, 2, 1, 2, 1});
      presentation::replace_subword(p, W({1, 2, 1}), W({1}));
      REQUIRE(p.rules == std::vector<W>({{1, 2, 1, 1, 2, 1, 1}, {1, 1, 2, 1}}));
      presentation::replace_subword(p, W({1, 2, 1}), W({1}));
      REQUIRE(p.rules == std::vector<W>({{1, 1, 1}, {1, 1}}));
      // Test for when existing is a suffix of replacement
      p.rules.clear();
      presentation::add_rule(
          p, {1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1}, {1, 2, 1, 1, 2, 1, 2, 1});
      presentation::replace_subword(p, W({1, 2}), W({1, 1, 2}));
      REQUIRE(p.rules
              == std::vector<W>(
                  {{1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1},
                   {1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 1}}));
    }

    template <typename W>
    void check_replace_word() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 0}, {});
      p.alphabet_from_rules();
      presentation::replace_word(p, W({}), W({2}));
      REQUIRE(p.rules == std::vector<W>{{0, 1, 0}, {2}});

      p.rules.clear();
      presentation::add_rule(p, {0, 1, 0}, {2, 1});
      presentation::add_rule(p, {1, 1, 2}, {1, 2, 1});
      presentation::add_rule(p, {2, 1, 2, 1}, {2, 2});
      presentation::add_rule(p, {2, 1}, {0, 1, 1});
      p.alphabet_from_rules();
      presentation::replace_word(p, W({2, 1}), W({1, 2}));
      REQUIRE(p.rules
              == std::vector<W>{{0, 1, 0},
                                {1, 2},
                                {1, 1, 2},
                                {1, 2, 1},
                                {2, 1, 2, 1},
                                {2, 2},
                                {1, 2},
                                {0, 1, 1}});

      p.rules.clear();
      presentation::add_rule(p, {0, 1, 0}, {1, 0, 1});
      presentation::add_rule(p, {0, 1, 1}, {1, 0, 1, 0});
      p.alphabet_from_rules();
      presentation::replace_word(p, W({1, 0, 1}), W({}));
      REQUIRE(p.rules
              == std::vector<W>{{0, 1, 0}, {}, {0, 1, 1}, {1, 0, 1, 0}});
    }

    template <typename W>
    void check_longest_rule() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::longest_rule(p), LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      REQUIRE(*presentation::longest_rule(p) == W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(*presentation::longest_rule(
                            presentation::longest_rule(p) + 1, p.rules.cend()),
                        LibsemigroupsException);
      REQUIRE(*presentation::longest_rule(presentation::longest_rule(p) + 2,
                                          p.rules.cend())
              == W({1, 1, 2, 1}));
      REQUIRE(*presentation::shortest_rule(p) == W({1, 2, 1}));
      REQUIRE(*presentation::shortest_rule(p.rules.cbegin(),
                                           presentation::shortest_rule(p))
              == W({1, 1, 2, 1}));
      REQUIRE_THROWS_AS(
          *presentation::shortest_rule(p.rules.cbegin(),
                                       presentation::shortest_rule(p) - 1),
          LibsemigroupsException);
    }

    template <typename W>
    void check_longest_rule_length() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::longest_rule_length(p),
                        LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      REQUIRE(presentation::longest_rule_length(p) == 7);
      REQUIRE_THROWS_AS(presentation::longest_rule_length(
                            presentation::longest_rule(p) + 1, p.rules.cend()),
                        LibsemigroupsException);
      REQUIRE(presentation::longest_rule_length(
                  presentation::longest_rule(p) + 2, p.rules.cend())
              == 6);

      REQUIRE(presentation::shortest_rule_length(p) == 4);
      REQUIRE_THROWS_AS(presentation::shortest_rule_length(
                            presentation::shortest_rule(p) + 1, p.rules.cend()),
                        LibsemigroupsException);
      REQUIRE(presentation::shortest_rule_length(p.rules.cbegin(),
                                                 p.rules.cend() - 2)
              == 6);
    }

    template <typename W>
    void check_remove_redundant_generators() {
      Presentation<W> p;
      p.rules.push_back(W({0, 1, 2, 1}));
      REQUIRE_THROWS_AS(presentation::remove_redundant_generators(p),
                        LibsemigroupsException);
      p.rules.push_back(W({1, 2, 1}));

      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});

      presentation::remove_redundant_generators(p);
      REQUIRE(p.rules
              == std::vector<W>(
                  {{1, 2, 1, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}}));
      presentation::remove_redundant_generators(p);
      REQUIRE(p.rules
              == std::vector<W>(
                  {{1, 2, 1, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}}));

      p.rules.clear();
      presentation::add_rule(p, {0, 1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1}, {0});
      presentation::add_rule(p, {1, 2, 1}, {0});
      presentation::remove_redundant_generators(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 0, 2, 0}, {0, 2, 0}, {0, 0, 2, 0}, {0, 0}, {0, 2, 0}, {0}}));

      p.rules.clear();
      presentation::add_rule(p, {0, 1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {0}, {1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      presentation::remove_redundant_generators(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 0, 2, 0}, {0, 2, 0}, {0, 0, 2, 0}, {0, 0}, {0, 2, 0}, {0}}));

      p.rules.clear();
      presentation::add_rule(p, {0, 1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1}, {0});
      presentation::add_rule(p, {1, 2, 1}, {0});
      presentation::remove_redundant_generators(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 0, 2, 0}, {0, 2, 0}, {0, 0, 2, 0}, {0, 0}, {0, 2, 0}, {0}}));
    }

    template <typename W>
    void check_reverse() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});

      presentation::reverse(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{1, 2, 1, 0}, {1, 2, 1}, {1, 2, 1, 1}, {1, 1}, {1, 2, 1}, {0}}));

      presentation::reverse(p);
      REQUIRE(
          p.rules
          == std::vector<W>(
              {{0, 1, 2, 1}, {1, 2, 1}, {1, 1, 2, 1}, {1, 1}, {1, 2, 1}, {0}}));
    }

    template <typename W>
    void check_in_alphabet() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 1, 2, 1}, {1, 2, 1});
      presentation::add_rule(p, {1, 1, 2, 1}, {1, 1});
      presentation::add_rule(p, {1, 2, 1}, {0});
      // Alphabet not set, so everything false
      REQUIRE(!p.in_alphabet(0));
      REQUIRE(!p.in_alphabet(1));
      REQUIRE(!p.in_alphabet(2));
      REQUIRE(!p.in_alphabet(3));
      REQUIRE(!p.in_alphabet(42));

      p.alphabet_from_rules();
      REQUIRE(p.in_alphabet(0));
      REQUIRE(p.in_alphabet(1));
      REQUIRE(p.in_alphabet(2));
      REQUIRE(!p.in_alphabet(3));
      REQUIRE(!p.in_alphabet(42));
    }

    template <typename W>
    void check_make_semigroup() {
      Presentation<W> p;
      presentation::add_rule(p, {0, 0}, {});
      presentation::add_rule(p, {1, 1}, {});
      presentation::add_rule(p, {2, 2}, {});
      presentation::add_rule(p, {0, 1, 0, 1, 0, 1}, {});
      presentation::add_rule(p, {1, 2, 1, 0, 1, 2, 1, 0}, {});
      presentation::add_rule(p, {2, 0, 2, 1, 2, 0, 2, 1}, {0, 3});

      p.alphabet_from_rules();
      auto e = presentation::make_semigroup(p);
      REQUIRE(p.rules
              == std::vector<W>({{0, 0},
                                 {e},
                                 {1, 1},
                                 {e},
                                 {2, 2},
                                 {e},
                                 {0, 1, 0, 1, 0, 1},
                                 {e},
                                 {1, 2, 1, 0, 1, 2, 1, 0},
                                 {e},
                                 {2, 0, 2, 1, 2, 0, 2, 1},
                                 {0, 3},
                                 {0, e},
                                 {0},
                                 {e, 0},
                                 {0},
                                 {1, e},
                                 {1},
                                 {e, 1},
                                 {1},
                                 {2, e},
                                 {2},
                                 {e, 2},
                                 {2},
                                 {3, e},
                                 {3},
                                 {e, 3},
                                 {3},
                                 {e, e},
                                 {e}}));
      REQUIRE(presentation::make_semigroup(p) == UNDEFINED);
    }

  }  // namespace

  using detail::StaticVector1;

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "000",
                          "vectors of ints",
                          "[quick][presentation]") {
    auto                    rg = ReportGuard(false);
    Presentation<word_type> p;
    p.alphabet({0, 1, 2});
    REQUIRE(p.alphabet() == word_type({0, 1, 2}));
    REQUIRE_THROWS_AS(p.alphabet({0, 0}), LibsemigroupsException);
    REQUIRE(p.alphabet() == word_type({0, 1, 2}));
    presentation::add_rule(p, {0, 0, 0}, {0});
    REQUIRE(std::distance(p.rules.cbegin(), p.rules.cend()) == 2);
    REQUIRE(std::vector<word_type>(p.rules.cbegin(), p.rules.cend())
            == std::vector<word_type>({{0, 0, 0}, {0}}));
    presentation::add_rule_and_check(p, {0, 0, 0}, {0});
    REQUIRE_THROWS_AS(presentation::add_rule_and_check(p, {0, 5, 0}, {0}),
                      LibsemigroupsException);
    REQUIRE_THROWS_AS(presentation::add_rule_and_check(p, {}, {0}),
                      LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "001",
                          "strings",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.alphabet("abc");
    REQUIRE(p.alphabet() == "abc");
    REQUIRE_THROWS_AS(p.alphabet("aa"), LibsemigroupsException);
    REQUIRE(p.alphabet() == "abc");
    presentation::add_rule(p, "aaa", "a");
    REQUIRE(std::distance(p.rules.cbegin(), p.rules.cend()) == 2);
    REQUIRE(std::vector<std::string>(p.rules.cbegin(), p.rules.cend())
            == std::vector<std::string>({"aaa", "a"}));
    REQUIRE_THROWS_AS(presentation::add_rule_and_check(p, "abz", "a"),
                      LibsemigroupsException);
    REQUIRE_THROWS_AS(presentation::add_rule_and_check(p, "", "a"),
                      LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "002",
                          "constructors (word_type)",
                          "[quick][presentation]") {
    auto                    rg = ReportGuard(false);
    Presentation<word_type> p;
    p.alphabet({0, 1, 2});
    presentation::add_rule(p, {0, 0, 0}, {0});
    REQUIRE(p.rules.size() == 2);
    presentation::add_rule_and_check(p, {0, 0, 0}, {0});
    p.validate();
    check_constructors(p);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "003",
                          "constructors (StaticVector1)",
                          "[quick][presentation]") {
    auto                                      rg = ReportGuard(false);
    Presentation<StaticVector1<uint16_t, 16>> p;
    p.alphabet({0, 1, 2});
    presentation::add_rule(p, {0, 0, 0}, {0});
    REQUIRE(p.rules.size() == 2);
    presentation::add_rule_and_check(p, {0, 0, 0}, {0});
    p.validate();
    check_constructors(p);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "004",
                          "constructors (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.alphabet("abc");
    presentation::add_rule(p, "aaaa", "aa");
    REQUIRE(p.rules.size() == 2);
    presentation::add_rule_and_check(p, "aaa", "aa");
    p.validate();
    check_constructors(p);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "005",
                          "alphabet + letters (word_type)",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_alphabet_letters<word_type>();
    check_alphabet_letters<StaticVector1<uint16_t, 16>>();
    check_alphabet_letters<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "006",
                          "alphabet + letters (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.alphabet("abc");
    REQUIRE(p.alphabet() == "abc");
    REQUIRE(p.letter(0) == 'a');
    REQUIRE(p.letter(1) == 'b');
    REQUIRE(p.letter(2) == 'c');
    p.alphabet(4);
    REQUIRE(p.alphabet().size() == 4);
    p.validate();
    REQUIRE_THROWS_AS(p.alphabet("abb"), LibsemigroupsException);

    presentation::add_rule(p, "abca", "aa");
    presentation::add_rule(p, "eb", "af");
    presentation::add_rule(p, "eb", "abbbbbb");
    p.alphabet_from_rules();
    REQUIRE(p.alphabet() == "abcef");
    REQUIRE(p.index('a') == 0);
    REQUIRE(p.index('b') == 1);
    REQUIRE(p.index('c') == 2);
    REQUIRE(p.index('e') == 3);
    REQUIRE(p.index('f') == 4);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "007",
                          "contains_empty_word",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_contains_empty_word<word_type>();
    check_contains_empty_word<StaticVector1<uint16_t, 16>>();
    check_contains_empty_word<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "008",
                          "validate_rules throws",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_validate_rules_throws<word_type>();
    check_validate_rules_throws<StaticVector1<uint16_t, 16>>();
    check_validate_rules_throws<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "009",
                          "helpers add_rule(s)",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_add_rules<word_type>();
    check_add_rules<StaticVector1<uint16_t, 10>>();
    check_add_rules<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "010",
                          "helpers add_rule(s) (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    presentation::add_rule(p, "abcb", "aa");
    Presentation<std::string> q;
    presentation::add_rule(q, "eb", "af");
    presentation::add_rule(q, "eb", "abbbbbbbbb");
    presentation::add_rules(p, q);
    REQUIRE(p.rules
            == std::vector<std::string>(
                {"abcb", "aa", "eb", "af", "eb", "abbbbbbbbb"}));
    REQUIRE(q.rules
            == std::vector<std::string>({"eb", "af", "eb", "abbbbbbbbb"}));
    REQUIRE_THROWS_AS(p.validate(), LibsemigroupsException);
    REQUIRE_THROWS_AS(q.validate(), LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE(
      "Presentation",
      "011",
      "helpers add_identity_rules (std::vector/StaticVector1)",
      "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_add_identity_rules<word_type>();
    check_add_identity_rules<StaticVector1<uint16_t, 10>>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "035",
                          "helpers add_zero_rules (std::vector/StaticVector1)",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_add_zero_rules<word_type>();
    check_add_zero_rules<StaticVector1<uint16_t, 10>>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "012",
                          "helpers add_identity_rules (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    presentation::add_rule(p, "abcb", "aa");
    REQUIRE_THROWS_AS(presentation::add_identity_rules(p, 'a'),
                      LibsemigroupsException);
    p.alphabet_from_rules();
    presentation::add_identity_rules(p, 'a');
    REQUIRE(p.rules
            == std::vector<std::string>({"abcb",
                                         "aa",
                                         "aa",
                                         "a",
                                         "ba",
                                         "b",
                                         "ab",
                                         "b",
                                         "ca",
                                         "c",
                                         "ac",
                                         "c"}));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "036",
                          "helpers add_zero_rules (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    presentation::add_rule(p, "abcb", "aa");
    REQUIRE_THROWS_AS(presentation::add_zero_rules(p, '0'),
                      LibsemigroupsException);
    p.alphabet("abc0");
    presentation::add_zero_rules(p, '0');
    REQUIRE(p.rules
            == std::vector<std::string>({"abcb",
                                         "aa",
                                         "a0",
                                         "0",
                                         "0a",
                                         "0",
                                         "b0",
                                         "0",
                                         "0b",
                                         "0",
                                         "c0",
                                         "0",
                                         "0c",
                                         "0",
                                         "00",
                                         "0"}));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "013",
                          "helpers add_inverse_rules (all)",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_add_inverse_rules<word_type>();
    check_add_inverse_rules<StaticVector1<uint16_t, 10>>();
    check_add_inverse_rules<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "014",
                          "helpers add_inverse_rules (std::string)",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.contains_empty_word(false);

    p.alphabet("aAbBcCe");
    presentation::add_identity_rules(p, 'e');

    presentation::add_inverse_rules(p, "AaBbCce", 'e');
    presentation::add_rule_and_check(p, "aaCac", "e");
    presentation::add_rule_and_check(p, "acbbACb", "e");
    presentation::add_rule_and_check(p, "ABabccc", "e");
    REQUIRE(
        p.rules
        == std::vector<std::string>(
            {"ae", "a",  "ea",    "a",  "Ae",      "A",  "eA",      "A",  "be",
             "b",  "eb", "b",     "Be", "B",       "eB", "B",       "ce", "c",
             "ec", "c",  "Ce",    "C",  "eC",      "C",  "ee",      "e",  "aA",
             "e",  "Aa", "e",     "bB", "e",       "Bb", "e",       "cC", "e",
             "Cc", "e",  "aaCac", "e",  "acbbACb", "e",  "ABabccc", "e"}));
    REQUIRE(!presentation::are_rules_sorted(p));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "015",
                          "helpers remove_duplicate_rules",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_remove_duplicate_rules<word_type>();
    check_remove_duplicate_rules<StaticVector1<uint16_t, 10>>();
    check_remove_duplicate_rules<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "016",
                          "helpers reduce_complements",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_reduce_complements<word_type>();
    check_reduce_complements<StaticVector1<uint16_t, 10>>();
    Presentation<std::string> p;
    presentation::add_rule(p, "abcb", "bcb");
    presentation::add_rule(p, "bcb", "bbcb");
    presentation::add_rule(p, "bbcb", "bb");
    presentation::add_rule(p, "bb", "bcb");
    presentation::add_rule(p, "bcb", "a");
    p.alphabet_from_rules();
    presentation::reduce_complements(p);
    presentation::sort_each_rule(p);
    presentation::sort_rules(p);
    REQUIRE(p.rules
            == std::vector<std::string>(
                {"bb", "a", "bcb", "a", "abcb", "a", "bbcb", "a"}));
    REQUIRE(p.alphabet() == "abc");
    presentation::normalize_alphabet(p);
    REQUIRE(p.letter(0) == presentation::letter(p, 0));
    REQUIRE(p.letter(1) == presentation::letter(p, 1));
    REQUIRE(p.letter(2) == presentation::letter(p, 2));
    p.validate();

    presentation::add_rule(p, "abcb", "ecb");
    REQUIRE(!p.in_alphabet('e'));
    // Not valid
    REQUIRE_THROWS_AS(presentation::normalize_alphabet(p),
                      LibsemigroupsException);
    p.alphabet_from_rules();
    presentation::add_rule(p, "abcd", "bcb");
    REQUIRE_THROWS_AS(presentation::normalize_alphabet(p),
                      LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "017",
                          "helpers sort_each_rule",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_sort_each_rule<word_type>();
    check_sort_each_rule<StaticVector1<uint16_t, 10>>();
    check_sort_each_rule<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "018",
                          "helpers sort_rules",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_sort_rules<word_type>();
    check_sort_rules<StaticVector1<uint16_t, 10>>();
    check_sort_rules<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "019",
                          "helpers longest_common_subword/replace_subword",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_longest_common_subword<word_type>();
    check_longest_common_subword<StaticVector1<uint16_t, 10>>();
    check_longest_common_subword<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "020",
                          "helpers redundant_rule",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_redundant_rule<word_type>();
    check_redundant_rule<StaticVector1<uint16_t, 10>>();
    check_redundant_rule<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "021",
                          "helpers shortlex_compare_concat",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_shortlex_compare_concat<word_type>();
    check_shortlex_compare_concat<StaticVector1<uint16_t, 10>>();
    check_shortlex_compare_concat<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "022",
                          "helpers remove_trivial_rules",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_remove_trivial_rules<word_type>();
    check_remove_trivial_rules<StaticVector1<uint16_t, 10>>();
    check_remove_trivial_rules<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "023",
                          "helpers replace_subword (existing, replacement)",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_replace_subword<word_type>();
    check_replace_subword<StaticVector1<uint16_t, 64>>();
    check_replace_subword<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "030",
                          "helpers replace_word",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_replace_word<word_type>();
    check_replace_word<StaticVector1<uint16_t, 10>>();
    check_replace_word<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "024",
                          "helpers longest_rule",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_longest_rule<word_type>();
    check_longest_rule<StaticVector1<uint16_t, 10>>();
    check_longest_rule<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "025",
                          "helpers longest_rule_length",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_longest_rule_length<word_type>();
    check_longest_rule_length<StaticVector1<uint16_t, 10>>();
    check_longest_rule_length<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "026",
                          "helpers remove_redundant_generators",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_remove_redundant_generators<word_type>();
    check_remove_redundant_generators<StaticVector1<uint16_t, 64>>();
    check_remove_redundant_generators<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "027",
                          "helpers reverse",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_reverse<word_type>();
    check_reverse<StaticVector1<uint16_t, 10>>();
    check_reverse<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "028",
                          "in_alphabet",
                          "[quick][presentation]") {
    auto rg = ReportGuard(false);
    check_in_alphabet<word_type>();
    check_in_alphabet<StaticVector1<uint16_t, 10>>();
    check_in_alphabet<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "029",
                          "replace_subword with empty word",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.alphabet(2);
    p.contains_empty_word(true);
    presentation::add_rule(p, {0, 0, 0}, {});
    p.validate();
    REQUIRE_THROWS_AS(presentation::replace_subword(p, {}, {2}),
                      LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "031",
                          "clear",
                          "[quick][presentation]") {
    auto                      rg = ReportGuard(false);
    Presentation<std::string> p;
    p.alphabet(2);
    p.contains_empty_word(true);
    presentation::add_rule(p, {0, 0, 0}, {});
    p.validate();
    p.clear();
    REQUIRE(p.alphabet().empty());
    REQUIRE(p.rules.empty());
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "040",
                          "change_alphabet",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    presentation::add_rule_and_check(p, "ba", "abaaabaa");
    presentation::replace_subword(p, "ba");
    presentation::change_alphabet(p, "abc");
    REQUIRE(p.rules == std::vector<std::string>({"c", "acaaca", "c", "ba"}));
    REQUIRE(p.alphabet() == "abc");
    REQUIRE_NOTHROW(p.validate());
    // Alphabet wrong size
    REQUIRE_THROWS_AS(presentation::change_alphabet(p, "ab"),
                      LibsemigroupsException);
    REQUIRE_THROWS_AS(presentation::change_alphabet(p, "aab"),
                      LibsemigroupsException);
    REQUIRE(p.alphabet() == "abc");
    REQUIRE(p.rules == std::vector<std::string>({"c", "acaaca", "c", "ba"}));
    presentation::change_alphabet(p, "bac");
    REQUIRE(p.rules == std::vector<std::string>({"c", "bcbbcb", "c", "ab"}));
    REQUIRE(p.alphabet() == "bac");

    presentation::change_alphabet(p, "xyz");
    REQUIRE(p.rules == std::vector<std::string>({"z", "xzxxzx", "z", "yx"}));
    REQUIRE(p.alphabet() == "xyz");

    presentation::change_alphabet(p, "xyt");
    REQUIRE(p.rules == std::vector<std::string>({"t", "xtxxtx", "t", "yx"}));
    REQUIRE(p.alphabet() == "xyt");
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "032",
                          "letter",
                          "[quick][presentation]") {
    Presentation<std::vector<uint16_t>> p;
    REQUIRE_THROWS_AS(presentation::letter(p, 65536), LibsemigroupsException);
    REQUIRE(presentation::letter(p, 10) == 10);
    REQUIRE_THROWS_AS(presentation::character(65536), LibsemigroupsException);
    REQUIRE(presentation::character(0) == 'a');
    REQUIRE(presentation::character(10) == 'k');

    IntegralRange<size_t>     ir(0, 255);
    Presentation<std::string> q;

    REQUIRE(std::all_of(ir.cbegin(), ir.cend(), [&q](size_t i) {
      return presentation::character(i) == presentation::letter(q, i);
    }));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "033",
                          "normalize_alphabet",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("axy");
    presentation::normalize_alphabet(p);
    REQUIRE(p.alphabet() == "abc");
    Presentation<word_type> q;
    q.alphabet({0, 10, 12});
    presentation::normalize_alphabet(q);
    REQUIRE(q.alphabet() == word_type({0, 1, 2}));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "042",
                          "first_unused_letter/letter",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");

    presentation::add_rule_and_check(p, "baabaa", "ababa");
    REQUIRE(presentation::first_unused_letter(p) == 'c');
    p.alphabet("abcdefghijklmnopq");
    REQUIRE(presentation::first_unused_letter(p) == 'r');
    p.alphabet("abcdefghijklmnopqrstuvwxyz");
    REQUIRE(presentation::first_unused_letter(p) == 'A');
    p.alphabet("abcdefgijklmnopqrstuvwxyz");
    REQUIRE(presentation::first_unused_letter(p) == 'h');
    p.alphabet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
    REQUIRE(presentation::first_unused_letter(p) == '0');
    p.alphabet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ02");
    REQUIRE(presentation::first_unused_letter(p) == '1');
    std::string const letters
        = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    std::unordered_set<letter_type> set;
    for (size_t i = 0; i < letters.size(); ++i) {
      REQUIRE(letters[i] == presentation::letter(p, i));
      REQUIRE(set.insert(letters[i]).second);
    }
    for (size_t i = letters.size(); i < 255; ++i) {
      REQUIRE(set.insert(presentation::letter(p, i)).second);
    }
    REQUIRE_THROWS_AS(presentation::letter(p, 255), LibsemigroupsException);
    p.alphabet(255);
    REQUIRE_THROWS_AS(presentation::first_unused_letter(p),
                      LibsemigroupsException);
    REQUIRE_THROWS_AS(p.alphabet(256), LibsemigroupsException);
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "034",
                          "longest_common_subword issue",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("a");
    presentation::add_rule_and_check(p, "aaaaaaaaaaaaaaaaaaa", "a");
    REQUIRE(presentation::longest_common_subword(p) == "aaaaaa");
    presentation::replace_subword(p, "aaaaaa");
    REQUIRE(presentation::longest_common_subword(p) == "");
    REQUIRE(p.rules == std::vector<std::string>({"bbba", "a", "b", "aaaaaa"}));
    REQUIRE(presentation::length(p) == 12);
    p.rules = std::vector<std::string>({"bba", "a", "b", "aaaaaaaa"});
    REQUIRE(presentation::length(p) == 13);

    p.alphabet("ab");
    presentation::add_rule_and_check(p, "baaaaaaaaaaaaaaaaaaa", "a");
    REQUIRE(presentation::longest_common_subword(p) == "aaaaaa");

    p.alphabet("ab");
    p.rules.clear();
    presentation::add_rule_and_check(p, "aaaaaaaaaaaaaaaa", "a");
    presentation::add_rule_and_check(p, "bbbbbbbbbbbbbbbb", "b");
    presentation::add_rule_and_check(p, "abb", "baa");
    REQUIRE(presentation::length(p) == 40);
    auto w = presentation::longest_common_subword(p);
    REQUIRE(w == "bbbb");
    presentation::replace_subword(p, w);
    REQUIRE(presentation::length(p) == 33);
    REQUIRE(
        p.rules
        == std::vector<std::string>(
            {"aaaaaaaaaaaaaaaa", "a", "cccc", "b", "abb", "baa", "c", "bbbb"}));
    w = presentation::longest_common_subword(p);
    REQUIRE(w == "aaaa");
    presentation::replace_subword(p, w);
    REQUIRE(presentation::length(p) == 26);
    REQUIRE(p.rules
            == std::vector<std::string>({"dddd",
                                         "a",
                                         "cccc",
                                         "b",
                                         "abb",
                                         "baa",
                                         "c",
                                         "bbbb",
                                         "d",
                                         "aaaa"}));
    w = presentation::longest_common_subword(p);
    REQUIRE(w == "");
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "037",
                          "make_semigroup",
                          "[quick][presentation]") {
    check_make_semigroup<word_type>();
    check_make_semigroup<StaticVector1<uint16_t, 10>>();
    check_make_semigroup<std::string>();
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "038",
                          "greedy_reduce_length",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    p.rules.clear();
    presentation::add_rule_and_check(p, "aaaaaaaaaaaaaaaa", "a");
    presentation::add_rule_and_check(p, "bbbbbbbbbbbbbbbb", "b");
    presentation::add_rule_and_check(p, "abb", "baa");
    REQUIRE(presentation::length(p) == 40);
    presentation::greedy_reduce_length(p);
    REQUIRE(presentation::length(p) == 26);
    REQUIRE(p.rules
            == std::vector<std::string>({"dddd",
                                         "a",
                                         "cccc",
                                         "b",
                                         "abb",
                                         "baa",
                                         "c",
                                         "bbbb",
                                         "d",
                                         "aaaa"}));
    REQUIRE(presentation::longest_common_subword(p) == "");
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "039",
                          "aaaaaaaab = aaaaaaaaab strong compression",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    presentation::add_rule_and_check(p, "aaaaaaaab", "aaaaaaaaab");
    REQUIRE(presentation::strongly_compress(p));
    REQUIRE(p.rules == decltype(p.rules)({"a", "aa"}));

    p.rules = {"adadnadnasnamdnamdna", "akdjskadjksajdaldja"};
    p.alphabet_from_rules();

    REQUIRE(presentation::strongly_compress(p));
    REQUIRE(presentation::reduce_to_2_generators(p));
    REQUIRE(
        p.rules
        == decltype(p.rules)({"aaaaaaaaaaaaaaaaaaa", "baaaaaaaaaaaaaaaaa"}));

    // Only works for 1-relation monoids at present
    p.alphabet("ab");
    presentation::add_rule_and_check(p, "aaaaaaaab", "aaaaaaaaab");
    presentation::add_rule_and_check(p, "aaaaaaaab", "aaaaaaaaab");
    REQUIRE(!presentation::strongly_compress(p));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "043",
                          "case where strong compression doesn't work",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    presentation::add_rule_and_check(p, "abaaaabab", "abbabaaaab");
    REQUIRE(presentation::strongly_compress(p));
    REQUIRE(p.rules == decltype(p.rules)({"abccdae", "fgeabccd"}));

    auto q = p;
    REQUIRE(presentation::reduce_to_2_generators(q));
    REQUIRE(q.rules == decltype(q.rules)({"aaaaaaa", "baaaaaaa"}));

    q = p;
    REQUIRE(presentation::reduce_to_2_generators(q, 1));
    REQUIRE(q.rules == decltype(q.rules)({"abbbbab", "bbbabbbb"}));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "044",
                          "proof that",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    presentation::add_rule_and_check(p, "aabb", "aaabaaab");
    REQUIRE(presentation::strongly_compress(p));
    presentation::reverse(p);
    REQUIRE(p.rules == decltype(p.rules)({"cba", "baadbaa"}));

    auto q = p;
    REQUIRE(presentation::reduce_to_2_generators(q));
    REQUIRE(q.rules == decltype(q.rules)({"aba", "baaabaa"}));

    q = p;
    REQUIRE(presentation::reduce_to_2_generators(q, 1));
    REQUIRE(q.rules == decltype(q.rules)({"abb", "bbbbbbb"}));

    // Wrong index
    REQUIRE_THROWS_AS(presentation::reduce_to_2_generators(q, 2),
                      LibsemigroupsException);
    q = p;
    presentation::add_rule_and_check(q, "aabb", "aaabaaab");
    // not 1-relation
    REQUIRE(!presentation::reduce_to_2_generators(q, 1));

    q.rules = {"aaaaa", "a"};
    REQUIRE(!presentation::reduce_to_2_generators(q));

    q.rules = {"aaaaa", ""};
    REQUIRE(!presentation::reduce_to_2_generators(q));

    q.rules = {"abcacbabab", ""};
    REQUIRE(!presentation::reduce_to_2_generators(q));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "045",
                          "decompression",
                          "[quick][presentation]") {
    Presentation<std::string> p;
    p.alphabet("ab");
    p.rules = {"aabb", "aaabaab"};
    REQUIRE(presentation::strongly_compress(p));
    REQUIRE(p.rules == decltype(p.rules)({"abc", "aabdab"}));
    REQUIRE(!presentation::reduce_to_2_generators(p));
    presentation::reverse(p);
    REQUIRE(presentation::reduce_to_2_generators(p));
    REQUIRE(p.rules == decltype(p.rules)({"aba", "baabaa"}));
  }

  LIBSEMIGROUPS_TEST_CASE("Presentation",
                          "041",
                          "sort_rules bug",
                          "[quick][presentation]") {
    std::string prefix1 = "dabd", suffix1 = "cbb", prefix2 = "abbaba",
                suffix2 = "c";

    REQUIRE(
        !detail::shortlex_compare_concat(prefix1, suffix1, prefix2, suffix2));

    Presentation<std::string> p;
    p.alphabet("bacd");
    p.rules = {"baabbabaa",
               "abaaba",
               "abbaba",
               "c",
               "abb",
               "d",
               "daba",
               "c",
               "dabd",
               "cbb",
               "dbaca",
               "caba",
               "dbacc",
               "cabc",
               "dbacd",
               "cabd",
               "abaaba",
               "baca",
               "abaabc",
               "bacc",
               "abaabd",
               "bacd",
               "cbaaba",
               "ddaca",
               "cbaabc",
               "ddacc",
               "cbaabd",
               "ddacd",
               "cbbaba",
               "dabc",
               "dabcbb",
               "cbbabd",
               "bacaaba",
               "ababaca",
               "bacaabc",
               "ababacc",
               "bacaabd",
               "ababacd",
               "bacbaca",
               "abadaca",
               "bacbacc",
               "abadacc",
               "bacbacd",
               "abadacd",
               "dabcaba",
               "cbbbaca",
               "dabcabc",
               "cbbbacc",
               "dabcabd",
               "cbbbacd",
               "ddacaaba",
               "cbabaca",
               "ddacaabc",
               "cbabacc",
               "ddacaabd",
               "cbabacd",
               "ddacbaca",
               "cbadaca",
               "ddacbacc",
               "cbadacc",
               "ddacbacd",
               "cbadacd",
               "abababaca",
               "dacaaba",
               "abababacc",
               "dacaabc",
               "abababacd",
               "dacaabd",
               "ababadaca",
               "dacbaca",
               "ababadacc",
               "dacbacc",
               "ababadacd",
               "dacbacd",
               "daababaca",
               "ccaaba",
               "daababacc",
               "ccaabc",
               "daababacd",
               "ccaabd",
               "daabadaca",
               "ccbaca",
               "daabadacc",
               "ccbacc",
               "daabadacd",
               "ccbacd",
               "bacababaca",
               "abadacaaba",
               "bacababacc",
               "abadacaabc",
               "bacababacd",
               "abadacaabd",
               "bacabadaca",
               "abadacbaca",
               "bacabadacc",
               "abadacbacc",
               "bacabadacd",
               "abadacbacd",
               "dabcbabaca",
               "cbbdacaaba",
               "dabcbabacc",
               "cbbdacaabc",
               "dabcbabacd",
               "cbbdacaabd",
               "dabcbadaca",
               "cbbdacbaca",
               "dabcbadacc",
               "cbbdacbacc",
               "dabcbadacd",
               "cbbdacbacd",
               "abaaababaca",
               "bacacaaba",
               "abaaababacc",
               "bacacaabc",
               "abaaababacd",
               "bacacaabd",
               "abaaabadaca",
               "bacacbaca",
               "abaaabadacc",
               "bacacbacc",
               "abaaabadacd",
               "bacacbacd",
               "cbaaababaca",
               "ddacacaaba",
               "cbaaababacc",
               "ddacacaabc",
               "cbaaababacd",
               "ddacacaabd",
               "cbaaabadaca",
               "ddacacbaca",
               "cbaaabadacc",
               "ddacacbacc",
               "cbaaabadacd",
               "ddacacbacd",
               "cbbaababaca",
               "dabccaaba",
               "cbbaababacc",
               "dabccaabc",
               "cbbaababacd",
               "dabccaabd",
               "cbbaabadaca",
               "dabccbaca",
               "cbbaabadacc",
               "dabccbacc",
               "cbbaabadacd",
               "dabccbacd",
               "ddacababaca",
               "cbadacaaba",
               "ddacababacc",
               "cbadacaabc",
               "ddacababacd",
               "cbadacaabd",
               "ddacabadaca",
               "cbadacbaca",
               "ddacabadacc",
               "cbadacbacc",
               "ddacabadacd",
               "cbadacbacd",
               "ababadacbaca",
               "dacabadaca",
               "ababadacbacc",
               "dacabadacc",
               "ababadacbacd",
               "dacabadacd",
               "bacaaababaca",
               "ababacacaaba",
               "bacaaababacc",
               "ababacacaabc",
               "bacaaababacd",
               "ababacacaabd",
               "bacaaabadaca",
               "ababacacbaca",
               "bacaaabadacc",
               "ababacacbacc",
               "bacaaabadacd",
               "ababacacbacd",
               "daabadacbaca",
               "ccabadaca",
               "daabadacbacc",
               "ccabadacc",
               "daabadacbacd",
               "ccabadacd",
               "bacabadacbaca",
               "abadacabadaca",
               "bacabadacbacc",
               "abadacabadacc",
               "bacabadacbacd",
               "abadacabadacd",
               "dabcbadacaaba",
               "cbbdacababaca",
               "dabcbadacaabc",
               "cbbdacababacc",
               "dabcbadacaabd",
               "cbbdacababacd",
               "dabcbadacbaca",
               "cbbdacabadaca",
               "dabcbadacbacc",
               "cbbdacabadacc",
               "dabcbadacbacd",
               "cbbdacabadacd",
               "ddacaaababaca",
               "cbabacacaaba",
               "ddacaaababacc",
               "cbabacacaabc",
               "ddacaaababacd",
               "cbabacacaabd",
               "ddacaaabadaca",
               "cbabacacbaca",
               "ddacaaabadacc",
               "cbabacacbacc",
               "ddacaaabadacd",
               "cbabacacbacd",
               "abaaabadacbaca",
               "bacacabadaca",
               "abaaabadacbacc",
               "bacacabadacc",
               "abaaabadacbacd",
               "bacacabadacd",
               "cbaaabadacbaca",
               "ddacacabadaca",
               "cbaaabadacbacc",
               "ddacacabadacc",
               "cbaaabadacbacd",
               "ddacacabadacd",
               "cbbaabadacbaca",
               "dabccabadaca",
               "cbbaabadacbacc",
               "dabccabadacc",
               "cbbaabadacbacd",
               "dabccabadacd",
               "ddacabadacbaca",
               "cbadacabadaca",
               "ddacabadacbacc",
               "cbadacabadacc",
               "ddacabadacbacd",
               "cbadacabadacd",
               "bacaaabadacbaca",
               "ababacacabadaca",
               "bacaaabadacbacc",
               "ababacacabadacc",
               "bacaaabadacbacd",
               "ababacacabadacd",
               "dabcbabacacaaba",
               "cbbdacaaababaca",
               "dabcbabacacaabc",
               "cbbdacaaababacc",
               "dabcbabacacaabd",
               "cbbdacaaababacd",
               "dabcbabacacbaca",
               "cbbdacaaabadaca",
               "dabcbabacacbacc",
               "cbbdacaaabadacc",
               "dabcbabacacbacd",
               "cbbdacaaabadacd",
               "dabcbadacabadaca",
               "cbbdacabadacbaca",
               "dabcbadacabadacc",
               "cbbdacabadacbacc"};
    REQUIRE(p.rules.size() == 258);

    p.validate();
    presentation::sort_each_rule(p);
    presentation::sort_rules(p);
    REQUIRE(presentation::are_rules_sorted(p));
--> --------------------

--> maximum size reached

--> --------------------