sims.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2022-2025 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 a declaration of a class for performing the "low-index
// congruence" algorithm for 1-sided or 2-sided congruences of semigroups and
// monoids.
 
// TODO(2) (later):
// * use SimsRefinerFaithful in RepOrc + MinimalRepOrc
// * a version which allows specifying the word_graph to Sims1 too
// * implement maximum_2_sided_congruence_contained to compute the kernel of the
//   associated homomorphism, which is the largest 2-sided congruence contained
//   in the right congruence.
// * change RepOrc and MinimalRepOrc to compute minimal 2-sided congruences
//   first (by using generating pairs), and then to try and find a right
//   congruence not containing any of the minimal 2-sided congruences.
//
// TODO(3) (far future):
// * Figure out a way of making refining functions possible. A refining function
// differs from a pruner in that it is also allowed to modify the word graph.
// * Implement one and two sided compatibility checking as refiners, following
// the theoretical description in the paper.
// * Modify SimsBase to perform the backtrack on all standard word graphs
// (without explicitly checking compatibility).
// * Make SimsBase -> Sims, i.e. implement all the relevant functions and
// settings of Sims1, Sims2, RepOrc, MinimalRepOrc into a single unified
// class.
// * Implement Sims1, Sim2, RepOrc, MinimalRepOrc just particular constructors
// of the Sims object, which automatically set the relevant pruners etc.
 
#ifndef LIBSEMIGROUPS_SIMS_HPP_
#define LIBSEMIGROUPS_SIMS_HPP_
 
#include <algorithm>    // for max, fill, count, for_each
#include <atomic>       // for atomic_uint64_t, __atomic_base
#include <chrono>       // for operator-
#include <cstddef>      // for size_t
#include <cstdint>      // for uint64_t, uint32_t
#include <functional>   // for function
#include <iterator>     // for distance, forward_iterator_tag, pair
#include <list>         // for operator!=
#include <memory>       // for unique_ptr
#include <mutex>        // for mutex
#include <string>       // for operator+, basic_string, string, to_string
#include <thread>       // for thread
#include <type_traits>  // for decay_t
#include <utility>      // for move, pair, swap
#include <vector>       // for vector
 
#include "constants.hpp"     // for operator!=, operator==, Max, UNDEFINED
#include "debug.hpp"         // for LIBSEMIGROUPS_ASSERT
#include "dot.hpp"           // for Dot
#include "exception.hpp"     // for LIBSEMIGROUPS_EXCEPTION
#include "forest.hpp"        // for Forest
#include "knuth-bendix.hpp"  // for KnuthBendix, to<Presentation>
#include "matrix.hpp"        // for DynamicMatrix, MatrixCommon, BMat
#include "presentation.hpp"  // for Presentation, longest_rule_length, short...
#include "ranges.hpp"        // for operator|, iterator_range
#include "runner.hpp"        // for delta, Reporter
#include "todd-coxeter.hpp"  // for ToddCoxeter
#include "types.hpp"         // for word_type, relation_type, congruence_kind
#include "word-graph.hpp"    // for Joiner, WordGraph
 
#include "detail/felsch-graph.hpp"    // for FelschGraph
#include "detail/fmt.hpp"             // for format, print
#include "detail/iterator.hpp"        // for detail/default_postfix_increment
#include "detail/path-iterators.hpp"  // for const_pstilo_iterator
#include "detail/report.hpp"          // for ReportCell
#include "detail/rewriters.hpp"       // for RewriteTrie
#include "detail/word-graph-with-sources.hpp"  // for WordGraphWithSources

namespace libsemigroups {

  class SimsStats {
   public:
    // TODO(2) might be better to have a mutex here and just lock it in
    // check_point below
    std::atomic_uint64_t count_last;

    // Atomic so as to avoid races between report_progress_from_thread and the
    // threads modifying count_last
    std::atomic_uint64_t count_now;

    std::atomic_uint64_t max_pending;

    std::atomic_uint64_t total_pending_last;

    // Atomic so as to avoid races between report_progress_from_thread and the
    // threads modifying total_pending_now
    std::atomic_uint64_t total_pending_now;

    SimsStats();

    SimsStats& init() {
      stats_zero();
      return *this;
    }

    SimsStats(SimsStats const& that) : SimsStats() {
      init(that);
    }

    SimsStats& operator=(SimsStats const& that) {
      return init(that);
    }

    SimsStats(SimsStats&& that) : SimsStats() {
      init(that);
    }

    SimsStats& operator=(SimsStats&& that) {
      return init(that);
    }

    SimsStats& init(SimsStats const& that);

    SimsStats& stats_zero();

    SimsStats& stats_check_point() {
      count_last         = count_now.load();
      total_pending_last = total_pending_now.load();
      return *this;
    }
  };

  template <typename Subclass>
  class SimsSettings {
   public:
    // We use WordGraph, even though the iterators produced by this class
    // hold FelschGraph's, none of the features of FelschGraph are useful
    // for the output, only for the implementation
    using word_graph_type = WordGraph<uint32_t>;

    using node_type = typename word_graph_type::node_type;

    using label_type = typename word_graph_type::label_type;

    using size_type = typename word_graph_type::size_type;

    using letter_type = typename word_type::value_type;
 
   private:
    std::vector<word_type>                 _exclude;
    size_t                                 _exclude_pruner_index;
    size_t                                 _idle_thread_restarts;
    std::vector<word_type>                 _include;
    std::vector<word_type>::const_iterator _longs_begin;
    size_t                                 _num_threads;
    Presentation<word_type>                _presentation;
    std::vector<std::function<bool(word_graph_type const&)>> _pruners;
    mutable SimsStats                                        _stats;
 
   public:
    SimsSettings();

    Subclass& init();

    // Copy constructor is explicitly required, the constructor template is not
    // a substitute. If no copy constructor is implemented, then _longs_begin
    // is not properly initialised, and leads to badness.
    SimsSettings(SimsSettings const& that) {
      init(that);
    }

    SimsSettings& operator=(SimsSettings const& that) {
      init(that);
      return *this;
    }

    SimsSettings(SimsSettings&& that) {
      init(that);
    }

    SimsSettings& operator=(SimsSettings&& that) {
      init(that);
      return *this;
    }

    template <typename OtherSubclass>
    SimsSettings(SimsSettings<OtherSubclass> const& that) {
      init(that);
    }

    template <typename OtherSubclass>
    Subclass& init(SimsSettings<OtherSubclass> const& that);
 
    ~SimsSettings();

    // So that we can access the settings from the derived class T.
    [[nodiscard]] SimsSettings const& settings() const noexcept {
      return *this;
    }

    Subclass& number_of_threads(size_t val);

    [[nodiscard]] size_t number_of_threads() const noexcept {
      return _num_threads;
    }

    Subclass& presentation(Presentation<word_type> const& p);

    [[nodiscard]] Presentation<word_type> const& presentation() const noexcept {
      return _presentation;
    }

    Subclass& cbegin_long_rules(std::vector<word_type>::const_iterator it);

    Subclass& cbegin_long_rules(size_t pos);

    [[nodiscard]] std::vector<word_type>::const_iterator
    cbegin_long_rules() const noexcept {
      LIBSEMIGROUPS_ASSERT(_presentation.rules.cbegin() <= _longs_begin);
      LIBSEMIGROUPS_ASSERT(_longs_begin <= _presentation.rules.cend());
      return _longs_begin;
    }

    Subclass& clear_long_rules() {
      return cbegin_long_rules(_presentation.rules.cend());
    }

    [[nodiscard]] size_t number_of_long_rules() const noexcept {
      return std::distance(_longs_begin, _presentation.rules.cend()) / 2;
    }

    Subclass& long_rule_length(size_t val);

    auto const& pruners() const noexcept {
      return _pruners;
    }

    template <typename Func>
    Subclass& add_pruner(Func&& func) {
      _pruners.emplace_back(func);
      // TODO(2) could return an iterator to the inserted func in case we want
      // to remove it again
      return static_cast<Subclass&>(*this);
    }

    Subclass& clear_pruners();

    [[nodiscard]] std::vector<word_type> const&
    included_pairs() const noexcept {
      return _include;
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass& add_included_pair_no_checks(Iterator1 first1,
                                          Iterator2 last1,
                                          Iterator3 first2,
                                          Iterator4 last2) {
      return include_exclude_no_checks(first1, last1, first2, last2, _include);
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass& add_included_pair(Iterator1 first1,
                                Iterator2 last1,
                                Iterator3 first2,
                                Iterator4 last2) {
      return include_exclude(first1, last1, first2, last2, _include);
    }

    Subclass& clear_included_pairs() {
      _include.clear();
      return static_cast<Subclass&>(*this);
    }

    [[nodiscard]] std::vector<word_type> const&
    excluded_pairs() const noexcept {
      return _exclude;
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass& add_excluded_pair_no_checks(Iterator1 first1,
                                          Iterator2 last1,
                                          Iterator3 first2,
                                          Iterator4 last2) {
      add_exclude_pruner();
      return include_exclude_no_checks(first1, last1, first2, last2, _exclude);
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass& add_excluded_pair(Iterator1 first1,
                                Iterator2 last1,
                                Iterator3 first2,
                                Iterator4 last2) {
      add_exclude_pruner();
      return include_exclude(first1, last1, first2, last2, _exclude);
    }

    Subclass& clear_excluded_pairs();

    [[nodiscard]] SimsStats& stats() const noexcept {
      return _stats;
    }

    [[nodiscard]] size_t idle_thread_restarts() const noexcept {
      return _idle_thread_restarts;
    }

    // Number of times an idle thread will attempt to restart before yielding.
    Subclass& idle_thread_restarts(size_t val);

    // TODO(1) rm
    template <typename Iterator1, typename Iterator2>
    void throw_if_letter_not_in_alphabet(Iterator1 first,
                                         Iterator2 last) const {
      presentation().throw_if_letter_not_in_alphabet(first, last);
    }
 
   protected:
    Subclass const& stats_copy_from(SimsStats const& stts) const {
      _stats = std::move(stts);
      return static_cast<Subclass const&>(*this);
    }
 
   private:
    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass&
    include_exclude_no_checks(Iterator1               first1,
                              Iterator2               last1,
                              Iterator3               first2,
                              Iterator4               last2,
                              std::vector<word_type>& include_or_exclude) {
      include_or_exclude.emplace_back(first1, last1);
      include_or_exclude.emplace_back(first2, last2);
      return static_cast<Subclass&>(*this);
    }
 
    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Subclass& include_exclude(Iterator1               first1,
                              Iterator2               last1,
                              Iterator3               first2,
                              Iterator4               last2,
                              std::vector<word_type>& include_or_exclude) {
      throw_if_letter_not_in_alphabet(first1, last1);
      throw_if_letter_not_in_alphabet(first2, last2);
      return static_cast<Subclass&>(*this).include_exclude_no_checks(
          first1, last1, first2, last2, include_or_exclude);
    }
 
    size_t add_exclude_pruner();
  };

  namespace sims {
    template <typename Subclass, typename Word>
    Subclass& add_included_pair_no_checks(SimsSettings<Subclass>& sims,
                                          Word const&             u,
                                          Word const&             v) {
      return sims.add_included_pair_no_checks(
          u.cbegin(), u.cend(), v.cbegin(), v.cend());
    }

    template <typename Subclass, typename Int>
    Subclass& add_included_pair_no_checks(SimsSettings<Subclass>& sims,
                                          std::initializer_list<Int> const& u,
                                          std::initializer_list<Int> const& v) {
      static_assert(std::is_integral_v<Int>);
      return add_included_pair_no_checks<Subclass, std::vector<Int>>(
          sims, u, v);
    }

    template <typename Subclass>
    Subclass& add_included_pair_no_checks(SimsSettings<Subclass>& sims,
                                          char const*             u,
                                          char const*             v) {
      return sims.add_included_pair_no_checks(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of the
    // same type but both convertible to string_view
    template <typename Subclass>
    Subclass& add_included_pair_no_checks(SimsSettings<Subclass>& sims,
                                          std::string_view        u,
                                          std::string_view        v) {
      return sims.add_included_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Subclass, typename Word>
    Subclass& add_included_pair(SimsSettings<Subclass>& sims,
                                Word const&             u,
                                Word const&             v) {
      return sims.add_included_pair(u.cbegin(), u.cend(), v.cbegin(), v.cend());
    }

    template <typename Subclass, typename Int>
    Subclass& add_included_pair(SimsSettings<Subclass>&           sims,
                                std::initializer_list<Int> const& u,
                                std::initializer_list<Int> const& v) {
      static_assert(std::is_integral_v<Int>);
      return add_included_pair<Subclass, std::vector<Int>>(sims, u, v);
    }

    template <typename Subclass>
    Subclass& add_included_pair(SimsSettings<Subclass>& sims,
                                char const*             u,
                                char const*             v) {
      return sims.add_included_pair(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of the
    // same type but both convertible to string_view
    template <typename Subclass>
    Subclass& add_included_pair(SimsSettings<Subclass>& sims,
                                std::string_view        u,
                                std::string_view        v) {
      return sims.add_included_pair(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Subclass, typename Word>
    Subclass& add_excluded_pair_no_checks(SimsSettings<Subclass>& sims,
                                          Word const&             u,
                                          Word const&             v) {
      return sims.add_excluded_pair_no_checks(
          u.cbegin(), u.cend(), v.cbegin(), v.cend());
    }

    template <typename Subclass, typename Int>
    Subclass& add_excluded_pair_no_checks(SimsSettings<Subclass>& sims,
                                          std::initializer_list<Int> const& u,
                                          std::initializer_list<Int> const& v) {
      static_assert(std::is_integral_v<Int>);
      return add_excluded_pair_no_checks<Subclass, std::vector<Int>>(
          sims, u, v);
    }

    template <typename Subclass>
    Subclass& add_excluded_pair_no_checks(SimsSettings<Subclass>& sims,
                                          char const*             u,
                                          char const*             v) {
      return sims.add_excluded_pair_no_checks(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of the
    // same type but both convertible to string_view
    template <typename Subclass>
    Subclass& add_excluded_pair_no_checks(SimsSettings<Subclass>& sims,
                                          std::string_view        u,
                                          std::string_view        v) {
      return sims.add_excluded_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Subclass, typename Word>
    Subclass& add_excluded_pair(SimsSettings<Subclass>& sims,
                                Word const&             u,
                                Word const&             v) {
      return sims.add_excluded_pair(u.cbegin(), u.cend(), v.cbegin(), v.cend());
    }

    template <typename Subclass, typename Int>
    Subclass& add_excluded_pair(SimsSettings<Subclass>&           sims,
                                std::initializer_list<Int> const& u,
                                std::initializer_list<Int> const& v) {
      static_assert(std::is_integral_v<Int>);
      return add_excluded_pair<Subclass, std::vector<Int>>(sims, u, v);
    }

    template <typename Subclass>
    Subclass& add_excluded_pair(SimsSettings<Subclass>& sims,
                                char const*             u,
                                char const*             v) {
      return sims.add_excluded_pair(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of the
    // same type but both convertible to string_view
    template <typename Subclass>
    Subclass& add_excluded_pair(SimsSettings<Subclass>& sims,
                                std::string_view        u,
                                std::string_view        v) {
      return sims.add_excluded_pair(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }
 
  }  // namespace sims

  // Sims1 - Sims2 - forward decl
 
  class Sims1;
  class Sims2;
 
  namespace detail {
    template <typename Sims1or2>
    class SimsBase : public SimsSettings<Sims1or2>, public Reporter {
      static_assert(std::is_same_v<Sims1or2, Sims1>
                    || std::is_same_v<Sims1or2, Sims2>);
 
     public:
      // We use WordGraph, even though the iterators produced by this class
      // hold FelschGraph's, none of the features of FelschGraph are useful
      // for the output, only for the implementation
      using word_graph_type = typename SimsSettings<Sims1or2>::word_graph_type;

      using node_type = typename word_graph_type::node_type;

      using label_type = typename word_graph_type::label_type;

      using size_type = typename word_graph_type::size_type;

      using letter_type = typename word_type::value_type;

      // SimsBase nested classes - protected
 
      // This class collects some common aspects of the iterator and
      // thread_iterator nested classes. The mutex does nothing for <iterator>
      // and is an actual std::mutex for <thread_iterator>. Also subclassed by
      // Sims2::iterator_base.
      class IteratorBase {
       public:
        using const_reference = word_graph_type const&;
        using const_pointer   = word_graph_type const*;
        using sims_type       = Sims1or2;
 
       private:
        size_type _max_num_classes;
        size_type _min_target_node;
 
       protected:
        using PendingDef = typename Sims1or2::PendingDef;
        using Definition = std::pair<node_type, label_type>;
 
        // TODO(1) (Sims1) ensure that _felsch_graph's settings are
        // properly initialised
        FelschGraph<WordGraphWithSources<uint32_t>, std::vector<Definition>>
            _felsch_graph;
 
        // This mutex does nothing for iterator, only does something for
        // thread_iterator
        std::mutex              _mtx;
        std::vector<PendingDef> _pending;
        Sims1or2 const*         _sims1or2;
 
        // Push initial PendingDef's into _pending, see tpp file for
        // explanation.
        void init(size_type n);
 
        // We could use the copy constructor, but there's no point in copying
        // anything except the FelschGraph and so we only copy that.
        void partial_copy_for_steal_from(IteratorBase const& that) {
          _felsch_graph = that._felsch_graph;
        }
 
        // Try to pop from _pending into the argument (reference), returns
        // true if successful and false if not.
        [[nodiscard]] bool try_pop(PendingDef& pd);
 
        // Try to make the definition represented by PendingDef, returns false
        // if it wasn't possible, and true if it was.
        bool try_define(PendingDef const& current);
 
        // Install any new pending definitions arising from the definition of
        // "current", this should only be called after "try_define(current)",
        // and is in a separate function so that we can define another version
        // of "try_define" in "Sims2".
        bool install_descendents(PendingDef const& current);
 
        IteratorBase(Sims1or2 const* s, size_type n);
 
       public:
        // None of the constructors are noexcept because the corresponding
        // constructors for Presentation aren't currently
        IteratorBase();
        IteratorBase(IteratorBase const& that);
        IteratorBase(IteratorBase&& that);
        IteratorBase& operator=(IteratorBase const& that);
        IteratorBase& operator=(IteratorBase&& that);
        ~IteratorBase();
 
        [[nodiscard]] bool operator==(IteratorBase const& that) const noexcept {
          return _felsch_graph == that._felsch_graph;
        }
 
        [[nodiscard]] bool operator!=(IteratorBase const& that) const noexcept {
          return !(operator==(that));
        }
 
        [[nodiscard]] const_reference operator*() const noexcept {
          return _felsch_graph;
        }
 
        [[nodiscard]] const_pointer operator->() const noexcept {
          return &_felsch_graph;
        }
 
        void swap(IteratorBase& that) noexcept;
 
        SimsStats& stats() noexcept {
          return _sims1or2->stats();
        }
 
        size_type maximum_number_of_classes() const noexcept {
          return _max_num_classes;
        }
 
        Sims1or2 const& sims() const noexcept {
          return *_sims1or2;
        }
      };  // class IteratorBase
 
     public:
      // SimsBase nested classes - public

      class iterator : public Sims1or2::iterator_base {
        using iterator_base = typename Sims1or2::iterator_base;
        using PendingDef    = typename Sims1or2::PendingDef;
 
        using iterator_base::init;
        using iterator_base::install_descendents;
        using iterator_base::try_define;
        using iterator_base::try_pop;
 
       public:
        using const_pointer = typename iterator_base::const_pointer;
        using const_reference = typename iterator_base::const_reference;
        using size_type = typename std::vector<word_graph_type>::size_type;
        using difference_type =
            typename std::vector<word_graph_type>::difference_type;
        using pointer = typename std::vector<word_graph_type>::pointer;
        using reference = typename std::vector<word_graph_type>::reference;
        using value_type = word_graph_type;
        using iterator_category = std::forward_iterator_tag;

        using sims_type = typename iterator_base::sims_type;

        using iterator_base::iterator_base;
 
       private:
        // Only want SimsBase to be able to use this constructor.
        iterator(Sims1or2 const* s, size_type n);
 
        // So that we can use the constructor above.
        friend iterator SimsBase::cbegin(SimsBase::size_type) const;
        friend iterator SimsBase::cend(SimsBase::size_type) const;
 
       public:
        ~iterator();

        iterator() : iterator_base() {}

        iterator(iterator const& that) : iterator_base(that) {}

        iterator(iterator&& that) : iterator_base(std::move(that)) {}

        iterator& operator=(iterator const& that) {
          iterator_base::operator=(that);
          return *this;
        }

        iterator& operator=(iterator&& that) {
          iterator_base::operator=(std::move(that));
          return *this;
        }

        // prefix
        iterator const& operator++();

        // postfix
        iterator operator++(int) {
          return detail::default_postfix_increment(*this);
        }
 
        using iterator_base::swap;
      };  // class iterator
 
     private:
      class thread_runner;
      class thread_iterator;
 
      void report_at_start(size_t num_classes) const;
      void report_progress_from_thread() const;
      void report_final() const;
 
      void throw_if_not_ready(size_type n) const;
 
     public:
      SimsBase();
      SimsBase(SimsBase const& other)      = default;
      SimsBase(SimsBase&&)                 = default;
      SimsBase& operator=(SimsBase const&) = default;
      SimsBase& operator=(SimsBase&&)      = default;
      ~SimsBase();
 
      Sims1or2& init();
 
      // Required because we are inheriting from Reporter and SimsSettings
      using SimsSettings<Sims1or2>::presentation;
      using SimsSettings<Sims1or2>::number_of_threads;
      using SimsSettings<Sims1or2>::stats;
      using SimsSettings<Sims1or2>::included_pairs;
      using SimsSettings<Sims1or2>::excluded_pairs;
      using SimsSettings<Sims1or2>::cbegin_long_rules;
 
      [[nodiscard]] iterator cbegin(size_type n) const {
        throw_if_not_ready(n);
        return iterator(static_cast<Sims1or2 const*>(this), n);
      }
 
      [[nodiscard]] iterator cend(size_type n) const {
        throw_if_not_ready(n);
        return iterator(static_cast<Sims1or2 const*>(this), 0);
      }
 
      // Apply the function pred to every congruence with at
      // most n classes
      void for_each(size_type                                   n,
                    std::function<void(word_graph_type const&)> pred) const;
 
      word_graph_type
      find_if(size_type                                   n,
              std::function<bool(word_graph_type const&)> pred) const;
 
      uint64_t number_of_congruences(size_type n) const;
    };  // SimsBase
  }     // namespace detail
 
  namespace sims {
    class const_cgp_iterator;
    class const_rcgp_iterator;
  }  // namespace sims

  class Sims1 : public detail::SimsBase<Sims1> {
    // Aliases
    using SimsBase      = detail::SimsBase<Sims1>;
    using iterator_base = IteratorBase;
 
    // Friends
    // so that SimsBase can access iterator_base, PendingDef, etc
    friend SimsBase;
    // so that Sims2 can access PendingDef
    friend Sims2;
 
    // Forward decl
    struct PendingDef;
 
   public:
    // We use WordGraph, even though the iterators produced by this class
    // hold FelschGraph's, none of the features of FelschGraph are useful
    // for the output, only for the implementation
    using word_graph_type = SimsBase::word_graph_type;

    using node_type = word_graph_type::node_type;

    using label_type = word_graph_type::label_type;

    using letter_type = word_type::value_type;

    using size_type = word_graph_type::size_type;
 
   private:
    using Definition = std::pair<node_type, label_type>;
 
    friend class sims::const_rcgp_iterator;
    friend class sims::const_cgp_iterator;
 
    using felsch_graph_type
        = detail::FelschGraph<detail::WordGraphWithSources<uint32_t>,
                              std::vector<Definition>>;
 
   public:
    Sims1() = default;
 
    using SimsBase::init;

    //! \sa init
    explicit Sims1(Presentation<word_type> const& p) : Sims1() {
      presentation(p);
    }

    //! \copydoc Sims1::Sims1(Presentation<word_type> const&)
    explicit Sims1(Presentation<word_type> const&& p) : Sims1() {
      presentation(std::move(p));
    }

    Sims1(Sims1 const&) = default;

    Sims1(Sims1&&) = default;

    Sims1& operator=(Sims1 const&) = default;

    Sims1& operator=(Sims1&&) = default;
 
    ~Sims1() = default;

    //! \sa presentation(Presentation<word_type> const&)
    Sims1& init(Presentation<word_type> const& p) {
      init();
      presentation(p);
      return *this;
    }

    //! \copydoc Sims1::init(Presentation<word_type> const&)
    Sims1& init(Presentation<word_type> const&& p) {
      init();
      presentation(std::move(p));
      return *this;
    }
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    Sims1& init();

    uint64_t number_of_congruences(size_type n) const;

    void for_each(size_type                                   n,
                  std::function<void(word_graph_type const&)> pred) const;

    word_graph_type
    find_if(size_type                                   n,
            std::function<bool(word_graph_type const&)> pred) const;

    // TODO(2) (Sims1) it'd be good to remove node 0 to avoid confusion. This
    // seems complicated however, and so isn't done at present.
    [[nodiscard]] iterator cbegin(size_type n) const;

    [[nodiscard]] iterator cend(size_type n) const;
#endif  // LIBSEMIGROUPS_PARSED_BY_DOXYGEN
  };

  class Sims2 : public detail::SimsBase<Sims2> {
    using SimsBase = detail::SimsBase<Sims2>;
    // so that SimsBase can access iterator_base, PendingDef, etc
    friend SimsBase;
 
   public:
    using word_graph_type = SimsBase::word_graph_type;

    using node_type = word_graph_type::node_type;

    using label_type = word_graph_type::label_type;

    using letter_type = word_type::value_type;

    using size_type = word_graph_type::size_type;
 
    using SimsBase::init;

    Sims2() = default;

    Sims2(Sims2 const& other) = default;

    Sims2(Sims2&&) = default;

    Sims2& operator=(Sims2 const&) = default;

    Sims2& operator=(Sims2&&) = default;
 
    ~Sims2() = default;

    explicit Sims2(Presentation<word_type> const& p) : Sims2() {
      presentation(p);
    }

    explicit Sims2(Presentation<word_type> const&& p) : Sims2() {
      presentation(std::move(p));
    }

    Sims2& init(Presentation<word_type> const& p) {
      init();
      presentation(p);
      return *this;
    }

    Sims2& init(Presentation<word_type> const&& p) {
      init();
      presentation(std::move(p));
      return *this;
    }
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    Sims2& init();

    uint64_t number_of_congruences(size_type n) const;

    void for_each(size_type                                   n,
                  std::function<void(word_graph_type const&)> pred) const;

    word_graph_type
    find_if(size_type                                   n,
            std::function<bool(word_graph_type const&)> pred) const;

    [[nodiscard]] iterator cbegin(size_type n) const;

    [[nodiscard]] iterator cend(size_type n) const;
#endif
 
   private:
    struct PendingDef;
 
    // This class collects some common aspects of the iterator and
    // thread_iterator nested classes. The mutex does nothing for <iterator>
    // and is an actual std::mutex for <thread_iterator>.
    class iterator_base : public SimsBase::IteratorBase {
      class RuleContainer;
 
     public:
      using const_reference = SimsBase::IteratorBase::const_reference;
      using const_pointer   = SimsBase::IteratorBase::const_pointer;
 
     private:
      std::unique_ptr<RuleContainer> _2_sided_include;
      std::vector<word_type>         _2_sided_words;
 
     protected:
      // We could use the copy constructor, but there's no point in copying
      // anything except the FelschGraph and so we only copy that.
      void partial_copy_for_steal_from(iterator_base const& that);
 
      // Try to make the definition represented by PendingDef, returns false if
      // it wasn't possible, and true if it was.
      [[nodiscard]] bool try_define(PendingDef const&);
 
      iterator_base(Sims2 const* s, size_type n);
 
     public:
      iterator_base();
      iterator_base(iterator_base const& that);
      iterator_base(iterator_base&& that);
      iterator_base& operator=(iterator_base const& that);
      iterator_base& operator=(iterator_base&& that);
      ~iterator_base();

      void swap(iterator_base& that) noexcept;
 
      using SimsBase::IteratorBase::stats;
    };  // class iterator_base
  };    // class Sims2

  class RepOrc : public SimsSettings<RepOrc> {
   private:
    size_t _min;
    size_t _max;
    size_t _size;
 
   public:
    RepOrc() : _min(), _max(), _size() {
      init();
    }

    RepOrc& init();

    template <typename OtherSubclass>
    explicit RepOrc(SimsSettings<OtherSubclass> const& s) : RepOrc() {
      SimsSettings<RepOrc>::init(s);
    }

    template <typename OtherSubclass>
    RepOrc& init(SimsSettings<OtherSubclass> const& s) {
      SimsSettings<RepOrc>::init(s);
      return *this;
    }

    RepOrc& min_nodes(size_t val) noexcept {
      _min = val;
      return *this;
    }

    [[nodiscard]] size_t min_nodes() const noexcept {
      return _min;
    }

    RepOrc& max_nodes(size_t val) noexcept {
      _max = val;
      return *this;
    }

    [[nodiscard]] size_t max_nodes() const noexcept {
      return _max;
    }

    RepOrc& target_size(size_t val) noexcept {
      _size = val;
      return *this;
    }

    [[nodiscard]] size_t target_size() const noexcept {
      return _size;
    }

    [[nodiscard]] Sims1::word_graph_type word_graph() const;
  };  // class RepOrc

  class MinimalRepOrc : public SimsSettings<MinimalRepOrc> {
   private:
    size_t _size;
 
   public:
    using SimsSettings<MinimalRepOrc>::stats;

    MinimalRepOrc() : _size() {
      init();
    }

    MinimalRepOrc& init() {
      _size = 0;
      return *this;
    }

    MinimalRepOrc& target_size(size_t val) noexcept {
      _size = val;
      return *this;
    }

    [[nodiscard]] size_t target_size() const noexcept {
      return _size;
    }

    [[nodiscard]] Sims1::word_graph_type word_graph() const;
  };  // class MinimalRepOrc
 
  namespace sims {
    class const_cgp_iterator;

    // This is similar to FroidurePinBase::const_rule_iterator
    // Right Congruence Generating Pairs (rcgp)
    class const_rcgp_iterator {
     public:
      using size_type = typename std::vector<relation_type>::size_type;

      using difference_type =
          typename std::vector<relation_type>::difference_type;

      using const_pointer = typename std::vector<relation_type>::const_pointer;

      using pointer = typename std::vector<relation_type>::pointer;

      using const_reference =
          typename std::vector<relation_type>::const_reference;

      using reference = typename std::vector<relation_type>::reference;

      using value_type = relation_type;

      using iterator_category = std::forward_iterator_tag;

      using word_graph_type = Sims1::word_graph_type;

      using felsch_graph_type = Sims1::felsch_graph_type;

      using node_type = word_graph_type::node_type;

      using label_type = word_graph_type::label_type;
 
     protected:
      felsch_graph_type _reconstructed_word_graph;
 
     private:
      label_type             _gen;
      node_type              _source;
      mutable relation_type  _relation;
      Forest                 _tree;
      word_graph_type const* _word_graph;
 
      // Set source to ptr->number_of_active_nodes() for cend
      const_rcgp_iterator(Presentation<word_type> const& p,
                          word_graph_type const*         ptr,
                          node_type                      source,
                          label_type                     gen);
 
      // To allow the use of the above constructor
      template <typename Node>
      friend const_rcgp_iterator
      cbegin_right_generating_pairs_no_checks(WordGraph<Node> const&);
 
      template <typename Node>
      friend const_rcgp_iterator
      cbegin_right_generating_pairs_no_checks(Presentation<word_type> const&,
                                              WordGraph<Node> const&);
 
      // To allow the use of the above constructor
      template <typename Node>
      friend const_rcgp_iterator
      cend_right_generating_pairs_no_checks(WordGraph<Node> const&);
 
      template <typename Node>
      friend const_rcgp_iterator
      cend_right_generating_pairs_no_checks(Presentation<word_type> const&,
                                            WordGraph<Node> const&);
 
      // To allow the use of the private constructor from pointer
      template <typename Node>
      friend const_cgp_iterator
      cbegin_two_sided_generating_pairs_no_checks(WordGraph<Node> const&);
 
      template <typename Node>
      friend const_cgp_iterator cbegin_two_sided_generating_pairs_no_checks(
          Presentation<word_type> const&,
          WordGraph<Node> const&);
 
      // To allow the use of the above constructor
      template <typename Node>
      friend const_cgp_iterator
      cend_two_sided_generating_pairs_no_checks(WordGraph<Node> const&);
 
      template <typename Node>
      friend const_cgp_iterator
      cend_two_sided_generating_pairs_no_checks(Presentation<word_type> const&,
                                                WordGraph<Node> const&);
 
     public:
      const_rcgp_iterator() = default;
      const_rcgp_iterator(const_rcgp_iterator const&) = default;
      const_rcgp_iterator(const_rcgp_iterator&&) = default;
      const_rcgp_iterator& operator=(const_rcgp_iterator const&) = default;
      const_rcgp_iterator& operator=(const_rcgp_iterator&&) = default;
 
      ~const_rcgp_iterator();

      [[nodiscard]] bool
      operator==(const_rcgp_iterator const& that) const noexcept {
        return _gen == that._gen && _source == that._source;
      }

      [[nodiscard]] bool
      operator!=(const_rcgp_iterator const& that) const noexcept {
        return !(this->operator==(that));
      }

      [[nodiscard]] const_reference operator*() const {
        populate_relation();
        return _relation;
      }

      [[nodiscard]] const_pointer operator->() const {
        populate_relation();
        return &_relation;
      }

      const_rcgp_iterator const& operator++();

      const_rcgp_iterator operator++(int) noexcept {
        return detail::default_postfix_increment(*this);
      }

      void swap(const_rcgp_iterator& that) noexcept;
 
     protected:
      [[nodiscard]] bool at_end() const noexcept {
        return _source == _word_graph->number_of_active_nodes();
      }
 
     private:
      bool populate_relation() const;
    };  // const_rcgp_iterator

    class const_cgp_iterator : public const_rcgp_iterator {
     public:
      using size_type = const_rcgp_iterator::size_type;

      using difference_type = const_rcgp_iterator::difference_type;

      using const_pointer = const_rcgp_iterator::const_pointer;

      using pointer = const_rcgp_iterator::pointer;

      using const_reference = const_rcgp_iterator::const_reference;

      using reference = const_rcgp_iterator::reference;

      using value_type = relation_type;

      using iterator_category = std::forward_iterator_tag;

      using word_graph_type = Sims1::word_graph_type;

      using felsch_graph_type = Sims1::felsch_graph_type;

      using node_type = word_graph_type::node_type;

      using label_type = word_graph_type::label_type;
 
      using const_rcgp_iterator::const_rcgp_iterator;
 
      ~const_cgp_iterator();
 
      using const_rcgp_iterator::operator==;
      using const_rcgp_iterator::operator!=;
      using const_rcgp_iterator::operator*;
      using const_rcgp_iterator::operator->;

      const_cgp_iterator const& operator++();

      const_cgp_iterator operator++(int) noexcept {
        return detail::default_postfix_increment(*this);
      }

      void swap(const_cgp_iterator& that) noexcept {
        const_rcgp_iterator::swap(that);
      }
 
     private:
      bool populate_relation() const;
    };  // class const_cgp_iterator
 
    // Forward decl, documented below
    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs(Presentation<word_type> const& p,
                           WordGraph<Node> const&         wg);
 
    // Forward decl, documented below
    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs(WordGraph<Node> const& wg);
 
    // Forward decl, documented below
    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs(Presentation<word_type> const& p,
                               WordGraph<Node> const&         wg);
 
    // Forward decl, documented below
    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs(WordGraph<Node> const& wg);

    template <typename Node>
    bool is_right_congruence(Presentation<word_type> const& p,
                             WordGraph<Node> const&         wg);

    template <typename Node>
    void throw_if_not_right_congruence(Presentation<word_type> const& p,
                                       WordGraph<Node> const&         wg);

    template <typename Node>
    bool is_right_congruence_of_dual(Presentation<word_type> const& p,
                                     WordGraph<Node> const&         wg) {
      auto p_rev(p);
      presentation::reverse(p_rev);
      return is_right_congruence(p_rev, wg);
    }

    template <typename Node>
    bool is_two_sided_congruence_no_checks(Presentation<word_type> const& p,
                                           WordGraph<Node> const&         wg);

    template <typename Node>
    bool is_two_sided_congruence(Presentation<word_type> const& p,
                                 WordGraph<Node> const&         wg);

    template <typename Node>
    void throw_if_not_two_sided_congruence(Presentation<word_type> const& p,
                                           WordGraph<Node> const&         wg);

    // Note that this is the generating pairs of the right
    // congruence so defined not the two-sided congruence.
    template <typename Node>
    const_rcgp_iterator
    cbegin_right_generating_pairs_no_checks(Presentation<word_type> const& p,
                                            WordGraph<Node> const&         wg) {
      return const_rcgp_iterator(p, &wg, 0, 0);
    }

    template <typename Node>
    const_rcgp_iterator
    cbegin_right_generating_pairs(Presentation<word_type> const& p,
                                  WordGraph<Node> const&         wg) {
      throw_if_not_right_congruence(p, wg);
      return cbegin_right_generating_pairs_no_checks(p, wg);
    }

    // Note that this is the generating pairs of the right
    // congruence so defined not the two-sided congruence.
    template <typename Node>
    const_cgp_iterator cbegin_two_sided_generating_pairs_no_checks(
        Presentation<word_type> const& p,
        WordGraph<Node> const&         wg) {
      return const_cgp_iterator(p, &wg, 0, 0);
    }

    template <typename Node>
    const_cgp_iterator
    cbegin_two_sided_generating_pairs(Presentation<word_type> const& p,
                                      WordGraph<Node> const&         wg) {
      throw_if_not_two_sided_congruence(p, wg);
      return cbegin_two_sided_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    const_rcgp_iterator
    cend_right_generating_pairs_no_checks(Presentation<word_type> const& p,
                                          WordGraph<Node> const&         wg) {
      return const_rcgp_iterator(p, &wg, wg.number_of_active_nodes(), 0);
    }

    template <typename Node>
    const_rcgp_iterator
    cend_right_generating_pairs(Presentation<word_type> const& p,
                                WordGraph<Node> const&         wg) {
      throw_if_not_right_congruence(p, wg);
      return cend_right_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    const_cgp_iterator
    cend_two_sided_generating_pairs_no_checks(Presentation<word_type> const& p,
                                              WordGraph<Node> const& wg) {
      return const_cgp_iterator(p, &wg, wg.number_of_active_nodes(), 0);
    }

    template <typename Node>
    const_cgp_iterator
    cend_two_sided_generating_pairs(Presentation<word_type> const& p,
                                    WordGraph<Node> const&         wg) {
      throw_if_not_two_sided_congruence(p, wg);
      return cend_two_sided_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs_no_checks(Presentation<word_type> const& p,
                                     WordGraph<Node> const&         wg) {
      return rx::iterator_range(cbegin_right_generating_pairs_no_checks(p, wg),
                                cend_right_generating_pairs_no_checks(p, wg));
    }

    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs(Presentation<word_type> const& p,
                           WordGraph<Node> const&         wg) {
      throw_if_not_right_congruence(p, wg);
      return right_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs_no_checks(WordGraph<Node> const& wg) {
      Presentation<word_type> p;
      p.alphabet(wg.out_degree());
      return right_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    rx::iterator_range<const_rcgp_iterator>
    right_generating_pairs(WordGraph<Node> const& wg);

    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs_no_checks(Presentation<word_type> const& p,
                                         WordGraph<Node> const&         wg) {
      return rx::iterator_range(
          cbegin_two_sided_generating_pairs_no_checks(p, wg),
          cend_two_sided_generating_pairs_no_checks(p, wg));
    }

    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs(Presentation<word_type> const& p,
                               WordGraph<Node> const&         wg) {
      throw_if_not_two_sided_congruence(p, wg);
      return two_sided_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs_no_checks(WordGraph<Node> const& wg) {
      Presentation<word_type> p;
      p.alphabet(wg.out_degree());
      return rx::iterator_range(
          cbegin_two_sided_generating_pairs_no_checks(p, wg),
          cend_two_sided_generating_pairs_no_checks(p, wg));
    }

    template <typename Node>
    rx::iterator_range<const_cgp_iterator>
    two_sided_generating_pairs(WordGraph<Node> const& wg) {
      Presentation<word_type> p;
      p.alphabet(wg.out_degree());
      throw_if_not_two_sided_congruence(p, wg);
      return two_sided_generating_pairs_no_checks(p, wg);
    }

    template <typename Node>
    bool is_maximal_right_congruence(Presentation<word_type> const& p,
                                     WordGraph<Node> const&         wg);

    template <typename Iterator>
    BMat<> poset(Iterator first, Iterator last);

    // The following produces a self-contained Dot object which doesn't render
    // very well.
    template <typename Iterator>
    Dot dot_poset(Iterator first, Iterator last);
  }  // namespace sims

  // This struct provides an alternative way of doing MinimalRepOrc, when the
  // generating pairs of the minimal 2-sided congruences are known. These pairs
  // should be added to forbid, and then your SimsRefinerFaithful instance
  // should be passed to a Sims1 object via add_pruner.
  class SimsRefinerFaithful {
   private:
    std::vector<word_type> _forbid;
 
   public:
    SimsRefinerFaithful() : _forbid() {}

    SimsRefinerFaithful& init() {
      _forbid.clear();
      return *this;
    }

    // TODO(2): Construct from std::vector<std::string>
    // TODO(1) construct from iterators, and move word_type version of to helper
    // namespace
    explicit SimsRefinerFaithful(std::vector<word_type> const& forbid)
        : _forbid(forbid) {}

    // TODO(1) construct from iterators, and move word_type version of to helper
    // namespace
    SimsRefinerFaithful& init(std::vector<word_type> const& forbid) {
      _forbid.clear();
      _forbid = forbid;
      return *this;
    }

    [[nodiscard]] std::vector<word_type> const& forbid() const noexcept {
      return _forbid;
    }

    bool operator()(Sims1::word_graph_type const& wg);
  };  // class SimsRefinerFaithful

  class SimsRefinerIdeals {
   private:
    using node_type    = uint32_t;
    using KnuthBendix_ = KnuthBendix<word_type>;
 
    std::thread::id                                   _default_thread_id;
    std::unordered_map<std::thread::id, KnuthBendix_> _knuth_bendices;
    std::mutex                                        _mtx;
    Presentation<word_type>                           _presentation;
 
   public:
    SimsRefinerIdeals()
        : _default_thread_id(), _knuth_bendices(), _mtx(), _presentation() {
      init();
    }

    SimsRefinerIdeals& init();

    SimsRefinerIdeals(SimsRefinerIdeals const& that) : SimsRefinerIdeals() {
      *this = that;
    }

    SimsRefinerIdeals& operator=(SimsRefinerIdeals const& that);

    SimsRefinerIdeals(SimsRefinerIdeals&& that) : SimsRefinerIdeals() {
      *this = std::move(that);
    }

    SimsRefinerIdeals& operator=(SimsRefinerIdeals&& that);

    explicit SimsRefinerIdeals(Presentation<word_type> const& p);

    SimsRefinerIdeals& init(Presentation<word_type> const& p);

    [[nodiscard]] Presentation<word_type> const& presentation() const noexcept {
      return _presentation;
    }

    [[nodiscard]] bool operator()(Sims1::word_graph_type const& wg);
 
   private:
    KnuthBendix_ const& knuth_bendix(std::thread::id tid);
  };  // class SimsRefinerIdeals

  [[nodiscard]] std::string to_human_readable_repr(SimsStats const& x);

  [[nodiscard]] std::string to_human_readable_repr(Sims1 const& x);

  [[nodiscard]] std::string to_human_readable_repr(Sims2 const& x);

  [[nodiscard]] std::string to_human_readable_repr(RepOrc const& x);

  [[nodiscard]] std::string to_human_readable_repr(MinimalRepOrc const& x);

  [[nodiscard]] std::string to_human_readable_repr(SimsRefinerIdeals const& x);

  [[nodiscard]] std::string
  to_human_readable_repr(SimsRefinerFaithful const& x);
 
}  // namespace libsemigroups
 
#include "sims.tpp"
 
#endif  // LIBSEMIGROUPS_SIMS_HPP_