Quelle  todd-coxeter.cpp   Sprache: C

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

// This file contains an implementation of the Todd-Coxeter algorithm for
// semigroups.

////////////////////////////////////////////////////////////////////////////////
// TODO(later)
//
// * Make process_deductions_dfs non-recursive, this will likely only be an
//   issue for presentations with extremely long relations.
//
// * Wreath product standardize mem fn.
//
////////////////////////////////////////////////////////////////////////////////
//
// Notes
//
// 1. It's suggested in Sims' book in the implementation appendix that using
//    the actual index of the coset referenced rather than the "row", to
//    avoid multiplication in get. I implemented this in 2021 and it made no
//    difference whatsoever, so I backed the changes.
//
// 2. In 2021, I couldn't figure out a low-cost way of implementing the "fill"
//    factor. The idea is that we should check that a certain percentage of the
//    entries in the table are filled before we use preferred definitions.
//    This doesn't seem to be necessary in any of the examples or tests, i.e.
//    the resulting enumerations are valid and terminate if we just always use
//    the preferred definitions and don't try to keep a particular percentage
//    of the entries in the table filled. It's possible that not using the
//    preferred definitions when the table is not filled enough, would make the
//    enumeration terminate faster, but it didn't seem worth the extra cost or
//    complexity of implementing the fill factor.
//
// 3. In 2021, I tried in felsch_lookahead to default to hlt_lookahead if there
//    are more paths (nodes) in the Felsch tree than the number of active
//    cosets times the number of relations, but found no examples where this
//    was invoked. So, I scrapped this too.
//
// 4. In 2021, I tried putting the options save() + standardize() outside the
//    main loop (+ duplicating a lot of the code) in ToddCoxeter::hlt and this
//    produced no measurable difference to the performance, so I backed these
//    changes out too.

#include "libsemigroups/todd-coxeter.hpp"

#include <algorithm>      // for reverse
#include <array>          // for array
#include <chrono>         // for nanoseconds etc
#include <cstddef>        // for size_t
#include <iterator>       // for distance
#include <limits>         // for numeric_limits
#include <memory>         // for shared_ptr
#include <numeric>        // for iota, accumulate
#include <ostream>        // for operator<<
#include <queue>          // for queue
#include <random>         // for mt19937
#include <string>         // for operator+, basic_string
#include <tuple>          // for tie
#include <unordered_map>  // for unordered_map
#include <unordered_set>  // for unordered_set
#include <utility>        // for pair

#ifdef LIBSEMIGROUPS_DEBUG
#include <set>  // for set
#endif

#include "libsemigroups/config.hpp"  // for LIBSEMIGROUPS_DEBUG

#include "libsemigroups/adapters.hpp"           // for Hash
#include "libsemigroups/cong-intf.hpp"          // for CongruenceInterface
#include "libsemigroups/coset.hpp"              // for CosetManager
#include "libsemigroups/debug.hpp"              // for LIBSEMIGROUPS_ASSERT
#include "libsemigroups/digraph-helper.hpp"     // for follow_path_nc, last_...
#include "libsemigroups/exception.hpp"          // for LIBSEMIGROUPS_EXCEPTION
#include "libsemigroups/felsch-tree.hpp"        // for FelschTree
#include "libsemigroups/froidure-pin-base.hpp"  // for FroidurePinBase
#include "libsemigroups/froidure-pin.hpp"       // for FroidurePin
#include "libsemigroups/knuth-bendix.hpp"       // for fpsemigroup::KnuthBendix
#include "libsemigroups/obvinf.hpp"             // for IsObviouslyInfinite
#include "libsemigroups/report.hpp"             // for PrintTable, Reporter
#include "libsemigroups/string.hpp"             // for to_string
#include "libsemigroups/tce.hpp"                // for TCE
#include "libsemigroups/timer.hpp"              // for detail::Timer
#include "libsemigroups/types.hpp"              // for letter_type
#include "libsemigroups/uf.hpp"                 // for Duf
#include "libsemigroups/ukkonen.hpp"            // for Ukkonen

// This file is organised as follows:
//
// 1.  Helper functions, types etc in anonymous namespace
// 2.  ToddCoxeter - inner classes - private
// 3.  ToddCoxeter - constructors and destructor - public
// 4.  CongruenceInterface - non-pure virtual member functions - public
// 5.  CongruenceInterface - non-pure virtual member functions - private
// 6.  CongruenceInterface - pure virtual member functions - private
// 7.  ToddCoxeter - member functions (init + settings) - public
// 8.  ToddCoxeter - member functions (sorting gen. pairs etc) - public
// 9.  ToddCoxeter - member functions (container-like) - public
// 10. ToddCoxeter - member functions (state) - public
// 11. ToddCoxeter - member functions (standardization) - public
// 12. ToddCoxeter - member functions (attributes) - public
// 13. ToddCoxeter - member functions (reporting + stats) - public
// 14. ToddCoxeter - member functions (reporting + stats) - private
// 15. ToddCoxeter - member functions (validation) - private
// 16. ToddCoxeter - member functions (initialisation + settings) - private
// 17. ToddCoxeter - member functions (cosets) - private
// 18. ToddCoxeter - member functions (main strategies) - private
// 19. ToddCoxeter - member functions (deduction processing) - private
// 20. ToddCoxeter - member functions (lookahead) - private
// 21. ToddCoxeter - member functions (standardize) - private
// 22. ToddCoxeter - member functions (debug) - private

////////////////////////////////////////////////////////////////////////
// 1. Helper functions, types etc in anonymous namespace
////////////////////////////////////////////////////////////////////////

using coset_type = libsemigroups::detail::CosetManager::coset_type;

namespace {
  using class_index_type = libsemigroups::CongruenceInterface::class_index_type;
  using word_type        = libsemigroups::word_type;

  using Perm = typename libsemigroups::detail::CosetManager::Perm;
  template <typename T>
  using EqualTo = typename libsemigroups::EqualTo<T>;
  template <typename T>
  using Hash = typename libsemigroups::Hash<T>;

  void reverse_if_necessary_and_push_back(
      libsemigroups::congruence::ToddCoxeter const* tc,
      word_type                                     w,
      std::vector<word_type>&                       v) {
    if (tc->kind() == libsemigroups::congruence_kind::left) {
      std::reverse(w.begin(), w.end());
    }
    v.push_back(std::move(w));
  }

  void sort_generating_pairs(Perm& perm, std::vector<word_type>& vec) {
    // Apply the permutation (adapted from stl.hpp:apply_permutation)
    size_t const n = perm.size();
    for (size_t i = 0; i < n; ++i) {
      size_t current = i;
      while (i != perm[current]) {
        size_t next = perm[current];
        std::swap(vec[2 * current], vec[2 * next]);
        std::swap(vec[2 * current + 1], vec[2 * next + 1]);
        perm[current] = current;
        current       = next;
      }
      perm[current] = current;
    }
  }

  void sort_generating_pairs(
      std::function<bool(word_type const&, word_type const&)> func,
      Perm&                                                   perm,
      std::vector<word_type>&                                 vec) {
    // Sort each relation so that the lhs is greater than the rhs according
    // to func.
    for (auto it = vec.begin(); it < vec.end(); it += 2) {
      if (func(*it, *(it + 1))) {
        std::swap(*it, *(it + 1));
      }
    }

    // Create a permutation of the even indexed entries in vec
    perm.resize(vec.size() / 2);
    std::iota(perm.begin(), perm.end(), 0);
    std::sort(perm.begin(),
              perm.end(),
              [&func, &vec](class_index_type x, class_index_type y) -> bool {
                return func(vec[2 * x], vec[2 * y]);
              });
    sort_generating_pairs(perm, vec);
  }

  // Attempts to reduce the length of the words in "words" by finding the
  // equivalence relation on the union of "wrt" and "words" generated by the
  // pairs in "wrt".  If A = {u_1, u_2, ..., u_n} are the distinct words in an
  // equivalence class on "words" and u_1 is the short-lex minimum word in the
  // class, then the words in "words" involving the words in A are replaced by:
  // u_1 = u_2, u_1 = u_3, ..., u_1 = u_n.
  class PairsSimplifier {
   public:
    PairsSimplifier() = default;

    PairsSimplifier& add(std::vector<word_type> const& words) {
      LIBSEMIGROUPS_ASSERT(words.size() % 2 == 0);
      _duf.resize(_duf.size() + words.size());
      // Create equivalence relation of the equal relations
      for (size_t i = 0; i < words.size(); ++i) {
        if (i % 2 == 0) {
          _duf.unite(i, i + 1);
        }
        auto const&              current_word = words[i];
        decltype(_map)::iterator it;
        bool                     inserted;
        std::tie(it, inserted) = _map.emplace(current_word, i);
        if (!inserted) {
          _duf.unite(it->second, i);
        }
      }
      return *this;
    }

    bool trivial() const {
      return (_duf.number_of_blocks() == _map.size());
    }

    void apply(std::vector<word_type>& words) {
      using libsemigroups::shortlex_compare;
      LIBSEMIGROUPS_ASSERT(words.size() % 2 == 0);
      // Class index -> index of min. length words in wrt + words
      std::unordered_map<size_t, word_type> mins;
      if (words.empty()) {
        return;
      }

      // Find index of minimum length word in every class
      for (auto const& word : words) {
        auto                     i = _map.find(word)->second;
        auto                     j = _duf.find(i);
        decltype(mins)::iterator it;
        bool                     inserted;
        std::tie(it, inserted) = mins.emplace(j, word);
        auto const& min_word   = it->second;
        if (!inserted && shortlex_compare(word, min_word)) {
          it->second = word;
        }
      }

      std::vector<word_type> result;
      for (auto it = _map.cbegin(); it != _map.cend(); ++it) {
        auto const& word     = it->first;
        auto const& index    = it->second;
        auto const& min_word = mins.find(_duf.find(index))->second;
        if (min_word != word) {
          result.push_back(min_word);
          result.push_back(word);
        }
      }
      std::swap(words, result);
    }

   private:
    libsemigroups::detail::Duf<> _duf;
    std::unordered_map<word_type, size_t, Hash<word_type>, EqualTo<word_type>>
        _map;
  };

  struct Noop {
    template <typename... Args>
    void operator()(Args...) const noexcept {}

    template <typename T>
    void operator()(libsemigroups::congruence::ToddCoxeter*) const noexcept {}
  };

  using DoNotProcessCoincidences = Noop;
  using NoPreferredDefs          = Noop;
  using DoNotStackDeductions     = Noop;

}  // namespace

namespace libsemigroups {

  using detail::FelschTree;

  namespace congruence {

    ////////////////////////////////////////////////////////////////////////
    // 2. ToddCoxeter - inner classes - private
    ////////////////////////////////////////////////////////////////////////

    // A class for managing Deductions (recently changed or defined values of
    // the form std::pair(coset_type, letter_type).
    class ToddCoxeter::Deductions {
     public:
      explicit Deductions(ToddCoxeter* tc)
          : _any_skipped(false), _deduct(), _tc(tc) {}

      Deduction pop() {
        auto res = _deduct.top();
        _deduct.pop();
        return res;
      }

      void emplace(coset_type c, letter_type x) {
        using opt = options::deductions;
        if (_deduct.size() < _tc->max_deductions()) {
          _deduct.emplace(c, x);
#ifdef LIBSEMIGROUPS_ENABLE_STATS
          _tc->_stats.max_deduct = std::max(
              _tc->_stats.max_deduct, static_cast<uint64_t>(_deduct.size()));
#endif
        } else {
          _any_skipped = true;
          if (_tc->deduction_policy() & opt::purge_from_top) {
            while (!_deduct.empty()
                   && !_tc->is_active_coset(_deduct.top().first)) {
              _deduct.pop();
            }
          } else if (_tc->deduction_policy() & opt::purge_all) {
            std::stack<Deduction> copy;
            while (!_deduct.empty()) {
              auto d = pop();
              if (_tc->is_active_coset(d.first)) {
                copy.push(d);
              }
            }
            std::swap(copy, _deduct);
          } else if (_tc->deduction_policy() & opt::discard_all_if_no_space) {
            clear();
          }
        }
      }

      bool any_skipped() const noexcept {
        return _any_skipped;
      }

      // noexcept correct?
      bool empty() const noexcept {
        return _deduct.empty();
      }

      size_t size() const noexcept {
        return _deduct.size();
      }

      void clear() {
        if (!_deduct.empty()) {
          _any_skipped = true;
          std::stack<Deduction> copy;
          std::swap(copy, _deduct);
        }
      }

     private:
      bool                  _any_skipped;
      std::stack<Deduction> _deduct;
      ToddCoxeter*          _tc;
    };

    struct ToddCoxeter::Settings {
      bool                use_relations_in_extra = false;
      size_t              deduct_max             = 2'000;
      options::deductions deduct_policy
          = options::deductions::no_stack_if_no_space | options::deductions::v2;
      size_t                f_defs         = 100'000;
      options::froidure_pin froidure_pin   = options::froidure_pin::none;
      size_t                hlt_defs       = 200'000;
      size_t                large_collapse = 100'000;
      options::lookahead    lookahead
          = options::lookahead::partial | options::lookahead::hlt;
      float                   lookahead_growth_factor    = 2.0;
      size_t                  lookahead_growth_threshold = 4;
      size_t                  lower_bound                = UNDEFINED;
      size_t                  max_preferred_defs         = 256;
      size_t                  min_lookahead              = 10'000;
      size_t                  next_lookahead             = 5'000'000;
      options::preferred_defs preferred_defs
          = options::preferred_defs::deferred;
      std::chrono::nanoseconds random_interval = std::chrono::milliseconds(200);
      bool                     restandardize   = false;
      bool                     save            = false;
      bool                     standardize     = false;
      options::strategy        strategy        = options::strategy::hlt;
    };

    class ToddCoxeter::PreferredDefs {
     public:
      explicit PreferredDefs(ToddCoxeter* tc) : _defs(), _tc(tc) {}

      bool empty() const noexcept {
        return _defs.empty();
      }

      Deduction pop() {
        Deduction d = _defs.front();
        _defs.pop();
        return d;
      }

      void emplace(coset_type c, letter_type x) {
#ifdef LIBSEMIGROUPS_ENABLE_STATS
        _tc->_stats.total_preferred_defs++;
#endif
        _defs.emplace(c, x);
        if (_defs.size() > _tc->max_preferred_defs()) {
          _defs.pop();
        }
#ifdef LIBSEMIGROUPS_ENABLE_STATS
        _tc->_stats.max_preferred_defs
            = std::max(_tc->_stats.max_preferred_defs, uint64_t(_defs.size()));
#endif
      }

      void purge_from_top() {
        while (!_defs.empty()
               && (!_tc->is_active_coset(_defs.front().first)
                   || _tc->_word_graph.unsafe_neighbor(_defs.front().first,
                                                       _defs.front().second)
                          != UNDEFINED)) {
          _defs.pop();
        }
      }

     private:
      std::queue<Deduction> _defs;
      ToddCoxeter*          _tc;
    };

    struct ToddCoxeter::TreeNode {
      TreeNode() : parent(UNDEFINED), gen(UNDEFINED) {}
      TreeNode(coset_type p, letter_type g) : parent(p), gen(g) {}
      coset_type  parent;
      letter_type gen;
    };

    struct ToddCoxeter::QueuePreferredDefs {
      void operator()(ToddCoxeter* tc,
                      coset_type   x,
                      letter_type  a,
                      coset_type   y,
                      letter_type  b) {
        tc->_preferred_defs->emplace(x, a);
        tc->_preferred_defs->emplace(y, b);
      }
    };

    struct ToddCoxeter::StackDeductions {
      inline void operator()(ToddCoxeter::Deductions* stck,
                             coset_type               c,
                             letter_type              a) const noexcept {
        stck->emplace(c, a);
      }
    };

    template <typename TStackDeduct>
    struct ToddCoxeter::ImmediateDef {
      void operator()(ToddCoxeter* tc,
                      coset_type   x,
                      letter_type  a,
                      coset_type   y,
                      letter_type  b) const {
        coset_type d = tc->new_coset();
        tc->def_edge<TStackDeduct>(x, a, d);
#ifdef LIBSEMIGROUPS_ENABLE_STATS
        tc->_stats.tc2_good_appl++;
        if (tc->strategy() == options::strategy::hlt) {
          tc->_stats.tc1_hlt_appl++;
        } else {
          tc->_stats.tc1_f_appl++;
        }
#endif

        if (a != b || x != y) {
          tc->def_edge<TStackDeduct>(y, b, d);
#ifdef LIBSEMIGROUPS_ENABLE_STATS
          tc->_stats.tc2_good_appl++;
#endif
        }
      }
    };

    ////////////////////////////////////////////////////////////////////////
    // 3. ToddCoxeter - constructors and destructor - public
    ////////////////////////////////////////////////////////////////////////

    ToddCoxeter::ToddCoxeter(congruence_kind type)
        : CongruenceInterface(type),
          CosetManager(),
          _coinc(),
          _deduct(new Deductions(this)),
          _extra(),
          _felsch_tree(nullptr),
          _nr_pairs_added_earlier(0),
          _prefilled(false),
          _preferred_defs(new PreferredDefs(this)),
          _relations(),
          _settings(new Settings()),
          _standard_max(0),
          _standardized(order::none),
          _state(state::constructed),
          _tree(nullptr),
          _word_graph() {}

    ToddCoxeter::ToddCoxeter(ToddCoxeter const& copy)
        : CongruenceInterface(copy),
          CosetManager(copy),
          _coinc(copy._coinc),
          _deduct(std::make_unique<Deductions>(*copy._deduct)),
          _extra(copy._extra),
          _felsch_tree(nullptr),
          _nr_pairs_added_earlier(copy._nr_pairs_added_earlier),
          _prefilled(copy._prefilled),
          _preferred_defs(
              std::make_unique<PreferredDefs>(*copy._preferred_defs)),
          _relations(copy._relations),
          _settings(std::make_unique<Settings>(*copy._settings)),
          _standard_max(copy._standard_max),
          _standardized(copy._standardized),
          _state(copy._state),
          _tree(nullptr),
          _word_graph(copy._word_graph) {
      if (copy._felsch_tree != nullptr) {
        _felsch_tree = std::make_unique<FelschTree>(*copy._felsch_tree);
      }
      if (copy._tree != nullptr) {
        _tree = std::make_unique<Tree>(*copy._tree);
      }
    }

    ToddCoxeter::ToddCoxeter(congruence_kind                  type,
                             std::shared_ptr<FroidurePinBase> S,
                             options::froidure_pin            p)
        : ToddCoxeter(type) {
      froidure_pin_policy(p);
      set_parent_froidure_pin(S);
      set_number_of_generators(S->number_of_generators());
    }

    // Construct a ToddCoxeter object representing a congruence over the
    // semigroup defined by copy (the quotient that is).
    ToddCoxeter::ToddCoxeter(congruence_kind typ, ToddCoxeter& copy)
        : ToddCoxeter(typ) {
      if (copy.kind() != congruence_kind::twosided && typ != copy.kind()) {
        LIBSEMIGROUPS_EXCEPTION("incompatible types of congruence, found ("
                                + congruence_kind_to_string(copy.kind()) + " / "
                                + congruence_kind_to_string(typ)
                                + ") but only (left / left), (right / "
                                  "right), (two-sided / *) are valid");
      }
      copy_relations_for_quotient(copy);
    }

    ToddCoxeter::ToddCoxeter(congruence_kind           typ,
                             fpsemigroup::ToddCoxeter& copy)
        : ToddCoxeter(typ) {
      set_parent_froidure_pin(copy);
      if (copy.finished()) {
        set_number_of_generators(copy.froidure_pin()->number_of_generators());
        froidure_pin_policy(options::froidure_pin::use_cayley_graph);
      } else {
        copy_relations_for_quotient(copy.congruence());
        froidure_pin_policy(options::froidure_pin::use_relations);
      }
    }

    ToddCoxeter::ToddCoxeter(congruence_kind typ, fpsemigroup::KnuthBendix& kb)
        : ToddCoxeter(typ) {
      set_number_of_generators(kb.alphabet().size());
      // TODO(later) use active rules when available
      for (auto it = kb.cbegin_rules(); it < kb.cend_rules(); ++it) {
        add_pair(kb.string_to_word(it->first), kb.string_to_word(it->second));
      }
      // Note that something goes horribly wrong if the next line is above the
      // for loop above.
      set_parent_froidure_pin(kb);
      if (kb.finished() && kb.is_obviously_finite()) {
        LIBSEMIGROUPS_ASSERT(froidure_pin_policy()
                             == options::froidure_pin::none);
        froidure_pin_policy(options::froidure_pin::use_cayley_graph);
      }
    }

    ToddCoxeter::~ToddCoxeter() {
      while (!_setting_stack.empty()) {
        pop_settings();
      }
    }

    ////////////////////////////////////////////////////////////////////////
    // 4. CongruenceInterface - non-pure virtual member functions - public
    ////////////////////////////////////////////////////////////////////////

    bool ToddCoxeter::contains(word_type const& lhs, word_type const& rhs) {
      validate_word(lhs);
      validate_word(rhs);
      init_generating_pairs();
      if (empty()) {
        // Note that it's possible to be not _prefilled, and have _relations,
        // and _extra empty, because shrink_to_fit clears _relations and
        // _extra. That's why we use empty() here instead of checking
        // _prefilled && _relations.empty() && _extra.empty(), as used to be
        // the case. This defines the free semigroup
        return lhs == rhs;
      }
      return CongruenceInterface::contains(lhs, rhs);
    }

    ////////////////////////////////////////////////////////////////////////
    // 5. CongruenceInterface - non-pure virtual member functions - private
    ////////////////////////////////////////////////////////////////////////

    class_index_type
    ToddCoxeter::const_word_to_class_index(word_type const& w) const {
      validate_word(w);
      coset_type c = _id_coset;

      if (kind() == congruence_kind::left) {
        c = action_digraph_helper::follow_path_nc(
            _word_graph, c, w.crbegin(), w.crend());
      } else {
        c = action_digraph_helper::follow_path_nc(
            _word_graph, c, w.cbegin(), w.cend());
      }
      return (c == UNDEFINED ? UNDEFINED
                             : static_cast<class_index_type>(c - 1));
    }

    bool ToddCoxeter::is_quotient_obviously_finite_impl() {
      if (finished()) {
        return true;
      }
      init_generating_pairs();
      return _prefilled;
      // _prefilled means that either we were created from a FroidurePinBase*
      // with froidure_pin_policy() == use_cayley_graph and we successfully
      // prefilled the table, or we manually prefilled the table.  In this
      // case the semigroup defined by _relations must be finite.
    }

    bool ToddCoxeter::is_quotient_obviously_infinite_impl() {
      if (finished()) {
        return false;
      }
      init_generating_pairs();
      if (_prefilled) {
        return false;
      } else if (number_of_generators() > _relations.size() + _extra.size()) {
        return true;
      }
      detail::IsObviouslyInfinite ioi(number_of_generators());
      ioi.add_rules(_relations.cbegin(), _relations.cend());
      ioi.add_rules(_extra.cbegin(), _extra.cend());
      return ioi.result();
    }

    void ToddCoxeter::set_number_of_generators_impl(size_t n) {
      LIBSEMIGROUPS_ASSERT(_word_graph.out_degree() == 0);
      LIBSEMIGROUPS_ASSERT(_word_graph.number_of_nodes() == 0);
      _word_graph.add_nodes(1);
      _word_graph.add_to_out_degree(n);
    }

    void ToddCoxeter::add_generators_impl(size_t n) {
      LIBSEMIGROUPS_ASSERT(_word_graph.out_degree() != 0);
      LIBSEMIGROUPS_ASSERT(_word_graph.number_of_nodes() == 1);
      _word_graph.add_to_out_degree(n);
    }

    ////////////////////////////////////////////////////////////////////////
    // 5. CongruenceInterface - pure virtual member functions - private
    ////////////////////////////////////////////////////////////////////////

    word_type ToddCoxeter::class_index_to_word_impl(class_index_type i) {
      run();
      if (!is_standardized()) {
        standardize(order::shortlex);
      }
      LIBSEMIGROUPS_ASSERT(finished());
      word_type w;
      TreeNode  tn = (*_tree)[i + 1];
      while (tn.parent != UNDEFINED) {
        w.push_back(tn.gen);
        tn = (*_tree)[tn.parent];
      }
      if (kind() != congruence_kind::left) {
        std::reverse(w.begin(), w.end());
      }
      return w;
    }

    size_t ToddCoxeter::number_of_classes_impl() {
      run();
      LIBSEMIGROUPS_ASSERT(finished());
      return number_of_cosets_active() - 1;
    }

    std::shared_ptr<FroidurePinBase> ToddCoxeter::quotient_impl() {
      using detail::TCE;
      run();
      standardize(order::shortlex);
      shrink_to_fit();
      // Ensure class indices and letters are equal!
      auto   table = std::make_shared<table_type>(_word_graph.table());
      size_t n     = number_of_generators();
      for (letter_type a = 0; a < n;) {
        if (table->get(0, a) != a + 1) {
          table->erase_column(a);
          n--;
        } else {
          ++a;
        }
      }
      auto ptr = std::make_shared<
          FroidurePin<TCE, FroidurePinTraits<TCE, table_type>>>(table);
      for (size_t i = 0; i < number_of_generators(); ++i) {
        // We use table.get(0, i) instead of just i, because there might be
        // more generators than cosets.
        ptr->add_generator(TCE(_word_graph.unsafe_neighbor(0, i)));
      }
      return ptr;
    }

    void ToddCoxeter::run_impl() {
      if (is_quotient_obviously_infinite()) {
        LIBSEMIGROUPS_EXCEPTION(
            "there are infinitely many classes in the congruence and "
            "Todd-Coxeter will never terminate");
      }

      if (strategy() == options::strategy::felsch) {
        felsch();
      } else if (strategy() == options::strategy::hlt) {
        hlt();
      } else if (strategy() == options::strategy::random) {
        if (running_for()) {
          LIBSEMIGROUPS_EXCEPTION(
              "the strategy \"%s\" is incompatible with run_for!",
              detail::to_string(strategy()).c_str());
        }
        random();
      } else {
        if (running_until()) {
          LIBSEMIGROUPS_EXCEPTION(
              "the strategy \"%s\" is incompatible with run_until!",
              detail::to_string(strategy()).c_str());
        }

        if (strategy() == options::strategy::CR) {
          CR_style();
        } else if (strategy() == options::strategy::R_over_C) {
          R_over_C_style();
        } else if (strategy() == options::strategy::Cr) {
          Cr_style();
        } else if (strategy() == options::strategy::Rc) {
          Rc_style();
        }
      }
    }

    bool ToddCoxeter::finished_impl() const {
      return _state == state::finished;
    }

    class_index_type ToddCoxeter::word_to_class_index_impl(word_type const& w) {
      run();
      LIBSEMIGROUPS_ASSERT(finished());
      if (!is_standardized()) {
        standardize(order::shortlex);
      }
      return const_word_to_class_index(w);
      // c is in the range 1, ..., number_of_cosets_active() because 0
      // represents the identity coset, and does not correspond to an element.
    }

    ////////////////////////////////////////////////////////////////////////
    // 7. ToddCoxeter - member functions (init_generating_pairs + settings) -
    // public
    ////////////////////////////////////////////////////////////////////////

    // Settings
    ToddCoxeter&
    ToddCoxeter::froidure_pin_policy(options::froidure_pin x) noexcept {
      _settings->froidure_pin = x;
      return *this;
    }

    ToddCoxeter::options::froidure_pin
    ToddCoxeter::froidure_pin_policy() const noexcept {
      return _settings->froidure_pin;
    }

    ToddCoxeter& ToddCoxeter::lookahead(options::lookahead x) noexcept {
      if (!(x & options::lookahead::felsch) && !(x & options::lookahead::hlt)) {
        x = x | options::lookahead::hlt;
      }
      _settings->lookahead = x;
      return *this;
    }

    ToddCoxeter::options::lookahead ToddCoxeter::lookahead() const noexcept {
      return _settings->lookahead;
    }

    ToddCoxeter& ToddCoxeter::lower_bound(size_t n) noexcept {
      _settings->lower_bound = n;
      return *this;
    }

    size_t ToddCoxeter::lower_bound() const noexcept {
      return _settings->lower_bound;
    }

    ToddCoxeter& ToddCoxeter::next_lookahead(size_t n) noexcept {
      _settings->next_lookahead = n;
      return *this;
    }

    size_t ToddCoxeter::next_lookahead() const noexcept {
      return _settings->next_lookahead;
    }

    ToddCoxeter& ToddCoxeter::min_lookahead(size_t n) noexcept {
      _settings->min_lookahead = n;
      return *this;
    }

    size_t ToddCoxeter::min_lookahead() const noexcept {
      return _settings->min_lookahead;
    }

    ToddCoxeter& ToddCoxeter::standardize(bool x) noexcept {
      _settings->standardize = x;
      return *this;
    }

    bool ToddCoxeter::standardize() const noexcept {
      return _settings->standardize;
    }

    ToddCoxeter& ToddCoxeter::save(bool x) {
      if ((_prefilled
           || (has_parent_froidure_pin()
               && parent_froidure_pin()->is_finite() == tril::TRUE
               && (_settings->froidure_pin == options::froidure_pin::none
                   || _settings->froidure_pin
                          == options::froidure_pin::use_cayley_graph)))
          && x) {
        LIBSEMIGROUPS_EXCEPTION("cannot use the save setting with a "
                                "prefilled ToddCoxeter instance");
      }
      _settings->save = x;
      return *this;
    }

    bool ToddCoxeter::save() const noexcept {
      return _settings->save;
    }

    ToddCoxeter& ToddCoxeter::strategy(options::strategy x) {
      if ((_prefilled
           || (has_parent_froidure_pin()
               && parent_froidure_pin()->is_finite() == tril::TRUE
               && (_settings->froidure_pin == options::froidure_pin::none
                   || _settings->froidure_pin
                          == options::froidure_pin::use_cayley_graph)))
          && x == options::strategy::felsch) {
        LIBSEMIGROUPS_EXCEPTION("cannot use the Felsch strategy with a "
                                "prefilled ToddCoxeter instance");
      }
      _settings->strategy = x;
      return *this;
    }

    ToddCoxeter::options::strategy ToddCoxeter::strategy() const noexcept {
      return _settings->strategy;
    }

    ToddCoxeter&
    ToddCoxeter::random_interval(std::chrono::nanoseconds x) noexcept {
      _settings->random_interval = x;
      return *this;
    }

    std::chrono::nanoseconds ToddCoxeter::random_interval() const noexcept {
      return _settings->random_interval;
    }

    ToddCoxeter& ToddCoxeter::use_relations_in_extra(bool val) noexcept {
      _settings->use_relations_in_extra = val;
      return *this;
    }

    bool ToddCoxeter::use_relations_in_extra() const noexcept {
      return _settings->use_relations_in_extra;
    }

    ToddCoxeter& ToddCoxeter::deduction_policy(options::deductions val) {
      using int_type = std::underlying_type_t<ToddCoxeter::options::deductions>;
      if (static_cast<int_type>(val) % 2 == 0
          || static_cast<int_type>(val) < 4) {
        LIBSEMIGROUPS_EXCEPTION("invalid option %s!",
                                detail::to_string(val).c_str())
      }
      _settings->deduct_policy = val;
      if (val & options::deductions::unlimited) {
        _settings->deduct_max = POSITIVE_INFINITY;
      }
      return *this;
    }

    ToddCoxeter::options::deductions
    ToddCoxeter::deduction_policy() const noexcept {
      return _settings->deduct_policy;
    }

    ToddCoxeter& ToddCoxeter::max_deductions(size_t val) noexcept {
      _settings->deduct_max = val;
      return *this;
    }

    size_t ToddCoxeter::max_deductions() const noexcept {
      return _settings->deduct_max;
    }

    ToddCoxeter&
    ToddCoxeter::preferred_defs(options::preferred_defs val) noexcept {
      if (val == options::preferred_defs::none) {
        // Don't call preferred_defs() here because ends up in infinite loop.
        _settings->max_preferred_defs = 0;
      }
      _settings->preferred_defs = val;
      return *this;
    }

    ToddCoxeter::options::preferred_defs
    ToddCoxeter::preferred_defs() const noexcept {
      return _settings->preferred_defs;
    }

    ToddCoxeter& ToddCoxeter::restandardize(bool val) noexcept {
      _settings->restandardize = val;
      return *this;
    }

    bool ToddCoxeter::restandardize() const noexcept {
      return _settings->restandardize;
    }

    ToddCoxeter& ToddCoxeter::max_preferred_defs(size_t val) noexcept {
      if (val == 0) {
        // Don't call preferred_defs() here because ends up in infinite loop.
        _settings->preferred_defs = options::preferred_defs::none;
      }
      _settings->max_preferred_defs = val;
      return *this;
    }

    size_t ToddCoxeter::max_preferred_defs() const noexcept {
      return _settings->max_preferred_defs;
    }

    ToddCoxeter& ToddCoxeter::hlt_defs(size_t val) {
      if (val < length_of_generating_pairs()) {
        LIBSEMIGROUPS_EXCEPTION("Expected a value >= %llu, found %llu!",
                                uint64_t(length_of_generating_pairs()),
                                uint64_t(val));
      }
      _settings->hlt_defs = val;
      return *this;
    }

    size_t ToddCoxeter::hlt_defs() const noexcept {
      return _settings->hlt_defs;
    }

    ToddCoxeter& ToddCoxeter::f_defs(size_t val) {
      if (val == 0) {
        LIBSEMIGROUPS_EXCEPTION("Expected a value != 0!");
      }
      _settings->f_defs = val;
      return *this;
    }

    size_t ToddCoxeter::f_defs() const noexcept {
      return _settings->f_defs;
    }

    ToddCoxeter& ToddCoxeter::lookahead_growth_factor(float val) {
      if (val < 1.0) {
        LIBSEMIGROUPS_EXCEPTION("Expected a value >= 1.0, found %f", val);
      }
      _settings->lookahead_growth_factor = val;
      return *this;
    }

    float ToddCoxeter::lookahead_growth_factor() const noexcept {
      return _settings->lookahead_growth_factor;
    }

    ToddCoxeter& ToddCoxeter::lookahead_growth_threshold(size_t val) noexcept {
      _settings->lookahead_growth_threshold = val;
      return *this;
    }

    size_t ToddCoxeter::lookahead_growth_threshold() const noexcept {
      return _settings->lookahead_growth_threshold;
    }

    ToddCoxeter& ToddCoxeter::large_collapse(size_t val) noexcept {
      _settings->large_collapse = val;
      return *this;
    }

    size_t ToddCoxeter::large_collapse() const noexcept {
      return _settings->large_collapse;
    }

    // Private settings!

    void ToddCoxeter::push_settings() {
      Settings* prev_settings = _settings.get();
      _settings.release();
      _setting_stack.push(prev_settings);
      _settings = std::make_unique<Settings>(*prev_settings);
    }

    void ToddCoxeter::pop_settings() {
      if (!_setting_stack.empty()) {
        _settings.reset(_setting_stack.top());
        _setting_stack.pop();
      }
    }

    ////////////////////////////////////////////////////////////////////////
    // 8. ToddCoxeter - member functions (sorting gen. pairs etc) - public
    ////////////////////////////////////////////////////////////////////////

    ToddCoxeter& ToddCoxeter::sort_generating_pairs(
        std::function<bool(word_type const&, word_type const&)> func) {
      if (started()) {
        LIBSEMIGROUPS_EXCEPTION(
            "Cannot sort relations, the enumeration has started!")
      }
      init_generating_pairs();
      Perm perm;
      ::sort_generating_pairs(func, perm, _relations);
      ::sort_generating_pairs(func, perm, _extra);
      return *this;
    }

    ToddCoxeter& ToddCoxeter::random_shuffle_generating_pairs() {
      if (started()) {
        LIBSEMIGROUPS_EXCEPTION("Cannot shuffle the generating pairs, the "
                                "enumeration has started!")
      }
      init_generating_pairs();
      Perm perm(0, _relations.size());
      std::iota(perm.begin(), perm.end(), 0);
      std::random_device rd;
      std::mt19937       g(rd());
      std::shuffle(perm.begin(), perm.end(), g);
      ::sort_generating_pairs(perm, _relations);
      ::sort_generating_pairs(perm, _extra);
      return *this;
    }

    ToddCoxeter& ToddCoxeter::remove_duplicate_generating_pairs() {
      if (started()) {
        LIBSEMIGROUPS_EXCEPTION("Cannot remove duplicate generating pairs, the "
                                "enumeration has started!")
      }
      init_generating_pairs();
      std::unordered_set<relation_type, Hash<relation_type>> relations_set;
      for (size_t i = 0; i < _relations.size(); i += 2) {
        if (shortlex_compare(_relations[i], _relations[i + 1])) {
          relations_set.emplace(_relations[i], _relations[i + 1]);
        } else {
          relations_set.emplace(_relations[i + 1], _relations[i]);
        }
      }
      _relations.clear();
      for (auto const& p : relations_set) {
        _relations.push_back(p.first);
        _relations.push_back(p.second);
      }
      std::unordered_set<relation_type, Hash<relation_type>> extra_set;

      for (size_t i = 0; i < _extra.size(); i += 2) {
        if (shortlex_compare(_extra[i], _extra[i + 1])) {
          if (relations_set.emplace(_extra[i], _extra[i + 1]).second) {
            extra_set.emplace(_extra[i], _extra[i + 1]);
          }
        } else {
          if (relations_set.emplace(_extra[i + 1], _extra[i]).second) {
            extra_set.emplace(_extra[i + 1], _extra[i]);
          }
        }
      }
      _extra.clear();
      for (auto const& p : extra_set) {
        _extra.push_back(p.first);
        _extra.push_back(p.second);
      }
      return *this;
    }

    ToddCoxeter& ToddCoxeter::simplify(size_t n) {
      init_generating_pairs();
      if (started()) {
        LIBSEMIGROUPS_EXCEPTION("the enumeration has started, it is no longer "
                                "possible to change the generating pairs!");
      } else if (_prefilled) {
        // There's no actual reason that we cannot do this here, just reducing
        // complexity of introducing this feature. But it would mean making a
        // fundamental change away from assuming that _relations is empty if
        // _prefilled is true. So, I am opting not to do this now.
        LIBSEMIGROUPS_EXCEPTION("the table has been prefilled, it is no longer "
                                "possible to change the generating pairs!");
      }
      if (_felsch_tree != nullptr) {
        _felsch_tree = nullptr;
      }
      PairsSimplifier p;
      // Replace words in _relations with min. equiv. word in _relations
      p.add(_relations).apply(_relations);
      p.add(_extra).apply(_extra);
      remove_duplicate_generating_pairs();
      // Reduce the length of the presentation by introducing new generators,
      // until either we reach n, or we cannot reduce the presentation any
      // further
      for (size_t i = 0; i < n; ++i) {
        if (!reduce_length_once()) {
          return *this;
        }
      }
      return *this;
    }

    bool ToddCoxeter::reduce_length_once() {
      LIBSEMIGROUPS_ASSERT(_felsch_tree == nullptr);
      using const_iterator_word =
          typename ukkonen::detail::GreedyReduceHelper::const_iterator;

      if (_relations.empty() && _extra.empty()) {
        return false;
      }
      Ukkonen u;
      ukkonen::add_words(u, _relations);
      ukkonen::add_words(u, _extra);

      ukkonen::detail::GreedyReduceHelper helper(u);
      const_iterator_word                 first, last;
      // Get the best word [first, last) so that replacing every
      // non-overlapping occurrence of [first, last) in _relations and
      // _extra with a new generator "x", and adding "x = [first, last)" as
      // a relation reduces the length of the presentation as much as
      // possible.
      std::tie(first, last) = ukkonen::dfs(u, helper);
      if (first == last) {
        return false;  // no change
      }
      letter_type const x = number_of_generators();
      add_generators(1);
      auto replace_subword = [&first, &last, &x](word_type& word) {
        auto it = std::search(word.begin(), word.end(), first, last);
        while (it != word.end()) {
          // found [first, last)
          *it      = x;
          auto pos = it - word.begin();
          word.erase(it + 1, it + (last - first));  // it not valid
          it = std::search(word.begin() + pos + 1, word.end(), first, last);
        }
      };
      std::for_each(_relations.begin(), _relations.end(), replace_subword);
      _relations.emplace_back(word_type({x}));
      _relations.emplace_back(first, last);
      std::for_each(_extra.begin(), _extra.end(), replace_subword);
      return true;
    }

    ////////////////////////////////////////////////////////////////////////
    // 9. ToddCoxeter - member functions (container-like) - public
    ////////////////////////////////////////////////////////////////////////

    bool ToddCoxeter::empty() const {
      return _relations.empty() && _extra.empty()
             && number_of_cosets_active() == 1;
    }

    void ToddCoxeter::reserve(size_t n) {
      size_t m = coset_capacity();
      if (n > m) {
        m = n - m;
        _word_graph.add_nodes(m);
        add_free_cosets(m);
      }
    }

    void ToddCoxeter::shrink_to_fit() {
      if (!finished()) {
        return;
      }
      if (!is_standardized()) {
        standardize(order::shortlex);
      }

      _word_graph.shrink_to_fit(number_of_cosets_active());
      _relations.clear();
      _relations.shrink_to_fit();
      _extra.clear();
      _extra.shrink_to_fit();
      erase_free_cosets();
    }

    ////////////////////////////////////////////////////////////////////////
    // 10. ToddCoxeter - member functions (state) - public
    ////////////////////////////////////////////////////////////////////////

    bool ToddCoxeter::complete() const noexcept {
      size_t const n = number_of_generators();
      coset_type   c = _id_coset;
      while (c != first_free_coset()) {
        for (size_t a = 0; a < n; ++a) {
          if (_word_graph.unsafe_neighbor(c, a) == UNDEFINED) {
            return false;
          }
        }
        c = next_active_coset(c);
      }
      return true;
    }

    template <typename T>
    bool ToddCoxeter::compatible(coset_type c, T first, T last) const {
      for (auto it = first; it < last; it += 2) {
        coset_type x = action_digraph_helper::follow_path_nc(
            _word_graph, c, (*it).cbegin(), (*it).cend());
        LIBSEMIGROUPS_ASSERT(is_active_coset(x) || x == UNDEFINED);
        coset_type y = action_digraph_helper::follow_path_nc(
            _word_graph, c, (*(it + 1)).cbegin(), (*(it + 1)).cend());
        LIBSEMIGROUPS_ASSERT(is_active_coset(y) || y == UNDEFINED);
        if (x != y || x == UNDEFINED) {
          return false;
        }
      }
      return true;
    }

    bool ToddCoxeter::compatible() const noexcept {
      coset_type c = _id_coset;
      if (!compatible(c, _extra.cbegin(), _extra.cend())) {
        return false;
      }
      while (c != first_free_coset()) {
        if (!compatible(c, _relations.cbegin(), _relations.cend())) {
          return false;
        }
        c = next_active_coset(c);
      }
      return true;
    }

    size_t ToddCoxeter::length_of_generating_pairs() {
      init_generating_pairs();
      auto   op = [](size_t val, word_type const& x) { return val + x.size(); };
      size_t N  = std::accumulate(
          _relations.cbegin(), _relations.cend(), size_t(0), op);
      N += std::accumulate(_extra.cbegin(), _extra.cend(), size_t(0), op);
      return N;
    }

    size_t ToddCoxeter::felsch_tree_height() {
      init_generating_pairs();
      init_run();
      init_felsch_tree();
      return _felsch_tree->height();
    }

    size_t ToddCoxeter::felsch_tree_number_of_nodes() {
      init_generating_pairs();
      init_run();
      init_felsch_tree();
      return _felsch_tree->number_of_nodes();
    }

    ////////////////////////////////////////////////////////////////////////
    // 11. ToddCoxeter - member functions (standardization) - public
    ////////////////////////////////////////////////////////////////////////

    bool ToddCoxeter::is_standardized() const noexcept {
      return _standardized != order::none;
    }

    ToddCoxeter::order ToddCoxeter::standardization_order() const noexcept {
      return _standardized;
    }

    bool ToddCoxeter::standardize(order rdr) {
      if (_standardized == rdr || empty()) {
        return false;
      }
      LIBSEMIGROUPS_ASSERT(_coinc.empty());
      LIBSEMIGROUPS_ASSERT(_deduct->empty());
      bool result = false;
      switch (rdr) {
        case order::shortlex:
          init_standardize();
          result = shortlex_standardize();
          break;
        case order::lex:
          init_standardize();
          result = lex_standardize();
          break;
        case order::recursive:
          init_standardize();
          result = recursive_standardize();
          break;
        case order::none:
        default:
          break;
      }
      if (finished()) {
        _standardized = rdr;
      } else {
        _standard_max = number_of_cosets_active();
      }
      return result;
    }

    ////////////////////////////////////////////////////////////////////////
    // 12. ToddCoxeter - member functions (attributes) - public
    ////////////////////////////////////////////////////////////////////////

    tril ToddCoxeter::is_non_trivial(size_t                    tries,
                                     std::chrono::milliseconds try_for,
                                     float                     threshold) {
      if (is_quotient_obviously_infinite()) {
        return tril::TRUE;
      } else if (finished()) {
        return number_of_classes() == 1 ? tril::FALSE : tril::TRUE;
      }

      detail::Timer             tmr;
      static std::random_device rd;
      static std::mt19937       g(rd());
      for (size_t try_ = 0; try_ < tries; ++try_) {
        REPORT_DEFAULT(
            "trying to show non-triviality: %d / %d\n", try_ + 1, tries);
        ToddCoxeter tc(*this);
        tc.init_felsch_tree();
        tc.standardize(true);
        tc.save(true);
        while (!tc.finished()) {
          tc.run_for(try_for);
          size_t limit = tc.number_of_cosets_active();
          while (tc.number_of_cosets_active() >= threshold * limit
                 && !tc.finished()) {
            std::uniform_int_distribution<> d(0,
                                              tc.number_of_cosets_active() - 1);
            size_t                          N  = d(g);
            auto                            c1 = tc._id_coset;
            for (size_t i = 0; i < N; ++i) {
              c1 = tc.next_active_coset(c1);
            }
            N       = d(g);
            auto c2 = tc._id_coset;
            for (size_t i = 0; i < N; ++i) {
              c2 = tc.next_active_coset(c2);
            }
            tc._coinc.emplace(c1, c2);
            tc.process_coincidences(stack_deductions::yes);
            tc.process_deductions();
            tc.run_for(try_for);
          }
        }
        if (tc.number_of_classes() > 1) {
          REPORT_DEFAULT("successfully showed non-triviality!\n");
          report_time(__func__, tmr);
          return tril::TRUE;
        }
      }
      REPORT_DEFAULT("failed to show non-triviality!\n");
      report_time(__func__, tmr);
      return tril::unknown;
    }

    ////////////////////////////////////////////////////////////////////////
    // 13. ToddCoxeter - member functions (reporting + stats) - public
    ////////////////////////////////////////////////////////////////////////

    std::string ToddCoxeter::stats_string() const {
      detail::PrintTable pt;
      pt.header("Summary of statistics");
      pt("Number of generators:", "%'14llu", uint64_t(number_of_generators()));
      pt("Number of relations:", "%'14llu", uint64_t(_relations.size() / 2));
      pt("Number of generating pairs:", "%'14llu", uint64_t(_extra.size() / 2));
      pt("Total length of generating pairs:",
         "%'14llu",
         uint64_t(
             const_cast<ToddCoxeter*>(this)->length_of_generating_pairs()));
      pt.divider();

      pt("cosets defined (hlt)", "%'14llu", uint64_t(_stats.tc1_hlt_appl));
      pt("cosets defined (felsch)", "%'14llu", uint64_t(_stats.tc1_f_appl));
      pt("total cosets defined",
         "%'14llu",
         uint64_t(number_of_cosets_defined() - 2));
      pt("coset capacity", "%'14llu", uint64_t(coset_capacity()));
      pt("cosets killed", "%'14llu", uint64_t(number_of_cosets_killed()));
      pt("killed / defined",
         "%13f%%",
         static_cast<float>(100 * number_of_cosets_killed())
             / number_of_cosets_defined());
      pt("defined / capacity",
         "%13f%%",
         static_cast<float>(100 * number_of_cosets_defined())
             / coset_capacity());

#ifdef LIBSEMIGROUPS_ENABLE_STATS
      pt.divider();
      pt("relations pushed (good)", "%'14llu", uint64_t(_stats.tc2_good_appl));
      pt("relations pushed (total)", "%'14llu", uint64_t(_stats.tc2_appl));
      pt("relations pushed (% good)",
         "%13f%%",
         static_cast<double>(100 * _stats.tc2_good_appl) / _stats.tc2_appl);

      pt.divider();
      pt("calls to process_coincidences", "%'14llu", uint64_t(_stats.tc3_appl));
      pt("maximum coincidences", "%'14llu", uint64_t(_stats.max_coinc));
      pt("total active coincidences",
         "%'14llu",
         uint64_t(_stats.nr_active_coinc));
      pt("total coincidences", "%'14llu", uint64_t(_stats.total_coinc));

      pt.divider();
      pt("calls to process_deductions",
         "%'14llu",
         uint64_t(_stats.total_deduct));
      pt("maximum deductions", "%'14llu", uint64_t(_stats.max_deduct));
      pt("total active deductions",
         "%'14llu",
         uint64_t(_stats.nr_active_deduct));
      pt("total deductions", "%'14llu", uint64_t(_stats.total_deduct));

      pt.divider();
      pt("maximum preferred defs",
         "%'14llu",
         uint64_t(_stats.max_preferred_defs));
      pt("total active preferred defs",
         "%'14llu",
         uint64_t(_stats.nr_active_preferred_defs));
      pt("total preferred defs",
         "%'14llu",
         uint64_t(_stats.total_preferred_defs));

      pt.divider();
      pt("calls to lookahead (hlt)",
         "%'14llu",
         uint64_t(_stats.hlt_lookahead_calls));
      pt("calls to lookahead (felsch)",
         "%'14llu",
         uint64_t(_stats.f_lookahead_calls));
#endif
      pt.footer("End of summary");
      return pt.emit();
    }

    std::string ToddCoxeter::settings_string() const {
      detail::PrintTable pt;
      pt.header("Summary of settings (Todd-Coxeter algorithm)");
      pt("deduction_policy:", deduction_policy());
      pt("f_defs:", "%'14llu", uint64_t(f_defs()));
      pt("froidure_pin_policy:", froidure_pin_policy());
      pt("hlt_defs:", "%'14llu", uint64_t(hlt_defs()));
      pt("lookahead:", lookahead());
      pt("lookahead_growth_factor:", "%14f", lookahead_growth_factor());
      pt("lookahead_growth_threshold:",
         "%14llu",
         uint64_t(lookahead_growth_threshold()));

      if (lower_bound() == UNDEFINED) {
        pt("lower_bound:", "\u221E");
      } else {
        pt("lower_bound:", "%'14llu", uint64_t(lower_bound()));
      }
      pt("max_deductions:", "%'14llu", uint64_t(max_deductions()));
      pt("max_preferred_defs:", "%'14llu", uint64_t(max_preferred_defs()));
      pt("next_lookahead:", "%'14llu", uint64_t(next_lookahead()));
      pt("preferred_defs:", preferred_defs());
      pt("random_interval:", detail::Timer::string(random_interval()));
      pt("save: ", save() ? "true" : "false");
      pt("standardize:", standardize() ? "true" : "false");
      pt("strategy: ", strategy());
      pt("use_relations_in_extra:",
         use_relations_in_extra() ? "true" : "false");
      pt.footer("End of summary");
      return pt.emit();
    }

    std::string ToddCoxeter::to_gap_string() {
      std::string const alphabet
          = "abcdefghijklmnopqrstuvwxyzABCDFGHIJKLMNOPQRSTUVWY";
      if (kind() != congruence_kind::twosided) {
        LIBSEMIGROUPS_EXCEPTION(
            "expected congruence kind to be twosided, found "
            + congruence_kind_to_string(kind()));
      }
      if (number_of_generators() > 49) {
        LIBSEMIGROUPS_EXCEPTION("expected at most 49 generators, found %llu!",
                                uint64_t(number_of_generators()));
      }
      init_generating_pairs();

      auto to_gap_word = [&alphabet](word_type const& w) -> std::string {
        std::string out;
        for (auto it = w.cbegin(); it < w.cend() - 1; ++it) {
          out += alphabet[*it];
          out += " * ";
        }
        out += alphabet[w.back()];
        return out;
      };

      std::string out = "free := FreeSemigroup(";
      for (size_t i = 0; i < number_of_generators(); ++i) {
        out += std::string("\"") + alphabet[i] + "\"";
        if (i != number_of_generators() - 1) {
          out += ", ";
        }
      }
      out += ");\n";
      out += "DoAssignGenVars(GeneratorsOfSemigroup(free));\n";
      out += "rules := [\n";
      for (auto it = _relations.cbegin(); it < _relations.cend(); it += 2) {
        out += " [";
        out += to_gap_word(*it);
        out += ", ";
        out += to_gap_word(*(it + 1));
        if (it != _relations.cend() - 2) {
          out += "],\n";
        } else {
          out += "]\n";
        }
      }
      for (auto it = _extra.cbegin(); it < _extra.cend(); it += 2) {
        out += " [";
        out += to_gap_word(*it);
        out += ", ";
        out += to_gap_word(*(it + 1));
        if (it != _extra.cend() - 2) {
          out += "],\n";
        } else {
          out += "]\n";
        }
      }
      out += " ];\n";
      out += "S := free / rules;\n";
      return out;
    }

    ////////////////////////////////////////////////////////////////////////
    // 14. ToddCoxeter - member functions (reporting + stats) - private
    ////////////////////////////////////////////////////////////////////////

    namespace {
      std::string fmt_line() {
#if defined(LIBSEMIGROUPS_FMT_ENABLED) && defined(LIBSEMIGROUPS_ENABLE_STATS)
        return "\t{:12L} {:+12L} ({})\n";
#elif defined(LIBSEMIGROUPS_FMT_ENABLED) && !defined(LIBSEMIGROUPS_ENABLE_STATS)
        return "\t{:12L} {:>12} ({})\n";
#elif !defined(LIBSEMIGROUPS_FMT_ENABLED) && defined(LIBSEMIGROUPS_ENABLE_STATS)
        return "\t%'12llu %+'12lld (%s)\n";
#elif !defined(LIBSEMIGROUPS_FMT_ENABLED) \
    && !defined(LIBSEMIGROUPS_ENABLE_STATS)
        return "\t%'12llu %12s (%s)\n";
#endif
      }
    }  // namespace

#ifdef LIBSEMIGROUPS_ENABLE_STATS
    void ToddCoxeter::report_coincidences(char const* fnam) {
      if (report::should_report()) {
        REPORT_DEFAULT(FORMAT("coincidences:" + fmt_line(),
                              _coinc.size(),
                              int64_t(_coinc.size() - _stats.prev_coincidences),
                              fnam));
        _stats.prev_coincidences = _coinc.size();
      }
    }
#else
    void ToddCoxeter::report_coincidences(char const* fnam) {
      REPORT_DEFAULT(
          FORMAT("coincidences:" + fmt_line(), _coinc.size(), "", fnam));
    }
#endif

#ifdef LIBSEMIGROUPS_ENABLE_STATS
    void ToddCoxeter::report_active_cosets(char const* fnam) {
      if (report::should_report()) {
        REPORT_DEFAULT(FORMAT(
            "active cosets:" + fmt_line(),
            number_of_cosets_active(),
            int64_t(number_of_cosets_active() - _stats.prev_active_cosets),
            fnam));
        _stats.prev_active_cosets = number_of_cosets_active();
      }
    }
#else
    void ToddCoxeter::report_active_cosets(char const* fnam) {
      REPORT_DEFAULT(FORMAT(
          "active cosets:" + fmt_line(), number_of_cosets_active(), "", fnam));
    }
#endif

    void ToddCoxeter::report_cosets_killed(char const* fnam, int64_t N) const {
      if (report::should_report()) {
#ifdef LIBSEMIGROUPS_FMT_ENABLED
        std::string fmt = "\t{:>12} {:+12L} ({})\n";
#else
        std::string fmt = "\t%12s %+'12lld (%s)\n";
#endif
        REPORT_DEFAULT(FORMAT("cosets killed:" + fmt, "", -1 * N, fnam));
      }
    }

    void ToddCoxeter::report_inc_lookahead(char const* fnam,
                                           size_t      new_value) const {
      if (report::should_report()) {
#if defined(LIBSEMIGROUPS_FMT_ENABLED)
        std::string fmt = "\t{:12L} {:+12L} ({})\n";
#else
        std::string fmt = "\t%'12llu %+'12lld (%s)\n";
#endif
        REPORT_DEFAULT(FORMAT("lookahead at:" + fmt,
                              new_value,
                              int64_t(new_value - next_lookahead()),
                              fnam));
      }
    }

    void ToddCoxeter::report_time(char const* fnam, detail::Timer& t) const {
      if (report::should_report()) {
        auto   tt    = t.string();
        size_t width = 12;
        // Check if we contain a \mu
        if (tt.find("\u03BC") != std::string::npos) {
          width = 13;
        }
#ifdef LIBSEMIGROUPS_FMT_ENABLED
        std::string fmt = "\t{:>" + std::to_string(width) + "} {:>{}} ({})\n";
        REPORT_DEFAULT(FORMAT("elapsed time:" + fmt, tt.c_str(), "", 12, fnam));
#else
        std::string fmt = "\t%" + std::to_string(width) + "s %*s (%s)\n";
        REPORT_DEFAULT(FORMAT("elapsed time:" + fmt, tt.c_str(), 12, "", fnam));
#endif
      }
    }

    // Cannot test this
    void ToddCoxeter::report_at_coset(char const* fnam, size_t N) const {
      if (report::should_report()) {
#ifdef LIBSEMIGROUPS_FMT_ENABLED
        std::string fmt = "\t{:12L} {:12L} ({})\n";
#else
        std::string fmt = "\t%'12llu %'12lld (%s)\n";
#endif
        REPORT_DEFAULT(
            FORMAT("at coset:" + fmt, N, number_of_cosets_active(), fnam));
      }
    }

    ////////////////////////////////////////////////////////////////////////
    // 15. ToddCoxeter - member functions (validation) - private
    ////////////////////////////////////////////////////////////////////////

    void ToddCoxeter::validate_table(table_type const& table,
                                     size_t const      first,
                                     size_t const      last) const {
      REPORT_DEBUG_DEFAULT("validating coset table...\n");
      if (number_of_generators() == UNDEFINED) {
        LIBSEMIGROUPS_EXCEPTION("no generators have been defined");
      } else if (table.number_of_cols() != number_of_generators()) {
        LIBSEMIGROUPS_EXCEPTION("invalid table, expected %d columns, found %d",
                                number_of_generators(),
                                table.number_of_cols());
      } else if (last - first == 0) {
        LIBSEMIGROUPS_EXCEPTION(
            "invalid table, expected at least 1 rows, found 0!");
      }
      for (size_t i = first; i < last; ++i) {
        for (size_t j = 0; j < table.number_of_cols(); ++j) {
          coset_type c = table.get(i, j);
          if (c < first || c >= last) {
            LIBSEMIGROUPS_EXCEPTION("invalid table, expected entries in the "
                                    "range [%d, %d), found "
                                    "%d in row %d, column %d",
                                    i,
                                    j,
                                    first,
                                    last,
                                    c);
          }
        }
      }
      REPORT_DEBUG_DEFAULT("...coset table ok\n");
    }

    ////////////////////////////////////////////////////////////////////////
    // 16. ToddCoxeter - member functions (initialisation) - private
    ////////////////////////////////////////////////////////////////////////

    //! Copy all _relations and _extra from copy into _relations of this
    void ToddCoxeter::copy_relations_for_quotient(ToddCoxeter& copy) {
      REPORT_DEBUG_DEFAULT("copying relations for quotient...\n");
      LIBSEMIGROUPS_ASSERT(empty());
      copy.init_generating_pairs();
      if (copy.number_of_generators() == UNDEFINED) {
        return;
      }
      set_number_of_generators(copy.number_of_generators());
      _state     = state::relation_extra_initialized;
      _relations = copy._relations;
      _relations.insert(
          _relations.end(), copy._extra.cbegin(), copy._extra.cend());
      if (kind() == congruence_kind::left
          && copy.kind() != congruence_kind::left) {
        for (auto& w : _relations) {
          std::reverse(w.begin(), w.end());
        }
      }
      _nr_pairs_added_earlier = 0;
    }

    void ToddCoxeter::init_generating_pairs() {
      if (_state == state::constructed) {
        REPORT_DEBUG_DEFAULT("initializing...\n");
        // Add the relations/Cayley graph from parent() if any.
        if (has_parent_froidure_pin()
            && parent_froidure_pin()->is_finite() == tril::TRUE) {
          if (froidure_pin_policy() == options::froidure_pin::use_cayley_graph
              || froidure_pin_policy() == options::froidure_pin::none) {
            REPORT_DEBUG_DEFAULT("using Cayley graph...\n");
            LIBSEMIGROUPS_ASSERT(_relations.empty());
            prefill(*parent_froidure_pin());
#ifdef LIBSEMIGROUPS_DEBUG
            // This is a check of program logic, since we use parent() to fill
            // the table, so we only validate in debug mode.
            validate_table(
                _word_graph.table(), 1, parent_froidure_pin()->size() + 1);
#endif
          } else {
            REPORT_DEBUG_DEFAULT("using presentation...\n");
            LIBSEMIGROUPS_ASSERT(froidure_pin_policy()
                                 == options::froidure_pin::use_relations);
            auto fp = parent_froidure_pin();
            fp->run();
            for (auto it = fp->cbegin_rules(); it != fp->cend_rules(); ++it) {
              reverse_if_necessary_and_push_back(this, it->first, _relations);
              reverse_if_necessary_and_push_back(this, it->second, _relations);
            }
#ifdef LIBSEMIGROUPS_DEBUG
            // This is a check of program logic, since we use parent() to
            // obtain the relations, so we only validate in debug mode.
            for (auto const& rel : _relations) {
              validate_word(rel);
            }
            // We don't add anything to _extra here so no need to check.
#endif
          }
        }
        _state = state::relation_extra_initialized;
      }

      // Get new generating pairs (if any) from CongruenceInterface (if any)
      auto it = cbegin_generating_pairs() + _nr_pairs_added_earlier;
      if (kind() != congruence_kind::twosided) {
        for (; it < cend_generating_pairs(); ++it) {
          reverse_if_necessary_and_push_back(this, it->first, _extra);
          reverse_if_necessary_and_push_back(this, it->second, _extra);
        }
      } else {
        for (; it < cend_generating_pairs(); ++it) {
          reverse_if_necessary_and_push_back(this, it->first, _relations);
          reverse_if_necessary_and_push_back(this, it->second, _relations);
        }
      }
      _nr_pairs_added_earlier
          = cend_generating_pairs() - cbegin_generating_pairs();
    }

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

--> maximum size reached

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