todd-coxeter-impl.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-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 Todd-Coxeter
// algorithm for semigroups and monoids.
//
// TODO(1)
// * re-implement reserve
// * remove preferred_defs from FelschGraph etc (except where they are really
// needed)? Or possibly reintroduce PrefDefs here
 
#ifndef LIBSEMIGROUPS_DETAIL_TODD_COXETER_IMPL_HPP_
#define LIBSEMIGROUPS_DETAIL_TODD_COXETER_IMPL_HPP_
 
#include <chrono>    // for nanoseconds
#include <cstddef>   // for size_t
#include <cstdint>   // for uint32_t
#include <iterator>  // for bidirect...
#include <memory>    // for unique_ptr
#include <numeric>   // for iota
#include <string>    // for string
#include <utility>   // for move, pair
#include <vector>    // for vector
 
#include "libsemigroups/constants.hpp"        // for operator!=
#include "libsemigroups/debug.hpp"            // for LIBSEMIG...
#include "libsemigroups/forest.hpp"           // for Forest
#include "libsemigroups/order.hpp"            // for Order
#include "libsemigroups/presentation.hpp"     // for Presenta...
#include "libsemigroups/ranges.hpp"           // for operator|
#include "libsemigroups/runner.hpp"           // for Reporter
#include "libsemigroups/to-presentation.hpp"  // for to_prese...
#include "libsemigroups/types.hpp"            // for word_type
#include "libsemigroups/word-graph.hpp"       // for WordGraph
 
#include "cong-common-class.hpp"        // for Congruen...
#include "felsch-graph.hpp"             // for FelschGraph
#include "node-managed-graph.hpp"       // for NodeMana...
#include "node-manager.hpp"             // for NodeMana...
#include "word-graph-with-sources.hpp"  // for WordGrap...

// This file is organised as follows:
// 0.  ToddCoxeterImpl - member types - public
// 1.  ToddCoxeterImpl - nested classes - private
// 2.  ToddCoxeterImpl - data members - private
// 3.  ToddCoxeterImpl - constructors + initializers - public
// 4.  ToddCoxeterImpl - interface requirements - add_generating_pair
// 5.  ToddCoxeterImpl - interface requirements - number_of_classes
// 6.  ToddCoxeterImpl - interface requirements - contains
// 7.  ToddCoxeterImpl - interface requirements - reduce
// 8.  ToddCoxeterImpl - settings - public
// 9.  ToddCoxeterImpl - accessors - public
// 10. ToddCoxeterImpl - modifiers - public
// 11. ToddCoxeterImpl - word -> index
// 12. ToddCoxeterImpl - index -> word
// 13. Runner          - pure virtual member functions - private
// 14. ToddCoxeterImpl - member functions - private
 
namespace libsemigroups {
 
  // NOTE: groups are defined here because the order they are declared is the
  // order they appear in the output doc.






 
  namespace detail {
    class ToddCoxeterImpl : public CongruenceCommon,
                            public FelschGraphSettings<ToddCoxeterImpl> {
      using FelschGraphSettings_ = FelschGraphSettings<ToddCoxeterImpl>;
 
     public:
      // 0. ToddCoxeterImpl - member types - public
 
      struct options : public FelschGraphSettings_::options {
        enum class strategy { hlt, felsch, CR, R_over_C, Cr, Rc };
 
        enum class lookahead_extent { full, partial };
 
        enum class lookahead_style { hlt, felsch };
 
        enum class def_policy : uint8_t {
          no_stack_if_no_space,
          purge_from_top,
          purge_all,
          discard_all_if_no_space,
          unlimited
        };
      };  // struct options
 
      enum class state : uint8_t { none, hlt, felsch, lookahead };
 
      using node_type        = typename WordGraph<uint32_t>::node_type;
      using index_type       = node_type;
      using label_type       = typename WordGraph<uint32_t>::label_type;
      using native_word_type = word_type;
 
     private:
      // 1. ToddCoxeterImpl - nested classes - private
 
      struct Settings;
 
      class SettingsGuard;
      friend class SettingsGuard;
 
      struct NonAtomicStats {
        using time_point = std::chrono::high_resolution_clock::time_point;
 
        // Data
        time_point               create_or_init_time;
        std::chrono::nanoseconds all_runs_time;
 
        std::chrono::nanoseconds all_hlt_phases_time;
        std::chrono::nanoseconds all_felsch_phases_time;
        std::chrono::nanoseconds all_lookahead_phases_time;
 
        uint64_t all_num_hlt_phases;
        uint64_t all_num_felsch_phases;
        uint64_t all_num_lookahead_phases;
 
        uint64_t   run_index;
        time_point run_start_time;
 
        uint64_t run_edges_active_at_start;
        uint64_t run_nodes_active_at_start;
 
        std::chrono::nanoseconds run_hlt_phases_time;
        std::chrono::nanoseconds run_felsch_phases_time;
        std::chrono::nanoseconds run_lookahead_phases_time;
 
        uint64_t run_num_hlt_phases;
        uint64_t run_num_felsch_phases;
        uint64_t run_num_lookahead_phases;
 
        uint64_t   phase_index;
        uint64_t   phase_edges_active_at_start;
        float      phase_complete_at_start;
        uint64_t   phase_nodes_defined_at_start;
        uint64_t   phase_nodes_killed_at_start;
        uint64_t   phase_nodes_active_at_start;
        time_point phase_start_time;
 
        mutable uint64_t report_index;
        mutable uint64_t report_edges_active_prev;
        mutable float    report_complete_prev;
        mutable uint64_t report_nodes_defined_prev;
        mutable uint64_t report_nodes_killed_prev;
        mutable uint64_t report_nodes_active_prev;
 
        // Constructors + initializers
 
        NonAtomicStats() {
          init();
        }
 
        NonAtomicStats& init();
 
        NonAtomicStats(NonAtomicStats const&)            = default;
        NonAtomicStats(NonAtomicStats&&)                 = default;
        NonAtomicStats& operator=(NonAtomicStats const&) = default;
        NonAtomicStats& operator=(NonAtomicStats&&)      = default;
      };
 
      struct Stats : public NonAtomicStats {
        // Data
        std::atomic_uint64_t lookahead_nodes_killed;
        std::atomic_uint64_t lookahead_position;
 
        // Constructors + initialisers
 
        Stats()
            : NonAtomicStats(),
              lookahead_nodes_killed(),
              lookahead_position() {}
 
        Stats& init() {
          NonAtomicStats::init();
          return *this;
        }
 
        Stats(Stats const& that)
            : NonAtomicStats(that),
              lookahead_nodes_killed(that.lookahead_nodes_killed.load()),
              lookahead_position(that.lookahead_position.load()) {}
 
        Stats(Stats&& that)
            : NonAtomicStats(std::move(that)),
              lookahead_nodes_killed(that.lookahead_nodes_killed.load()),
              lookahead_position(that.lookahead_position.load()) {}
 
        Stats& operator=(Stats const& that) {
          NonAtomicStats::operator=(that);
          lookahead_nodes_killed = that.lookahead_nodes_killed.load();
          lookahead_position     = that.lookahead_position.load();
          return *this;
        }
 
        Stats& operator=(Stats&& that) {
          NonAtomicStats::operator=(std::move(that));
          lookahead_nodes_killed = that.lookahead_nodes_killed.load();
          lookahead_position     = that.lookahead_position.load();
          return *this;
        }
      };
 
      void stats_run_start() {
        _stats.run_start_time = std::chrono::high_resolution_clock::now();
 
        _stats.run_nodes_active_at_start
            = current_word_graph().number_of_nodes_active();
        _stats.run_edges_active_at_start
            = current_word_graph().number_of_edges_active();
        _stats.run_num_hlt_phases       = 0;
        _stats.run_num_felsch_phases    = 0;
        _stats.run_num_lookahead_phases = 0;
 
        _stats.run_hlt_phases_time       = std::chrono::nanoseconds(0);
        _stats.run_felsch_phases_time    = std::chrono::nanoseconds(0);
        _stats.run_lookahead_phases_time = std::chrono::nanoseconds(0);
 
        _stats.phase_index = 0;
      }
 
      void stats_run_stop() {
        _stats.run_index++;
 
        _stats.all_runs_time += delta(_stats.run_start_time);
        _stats.all_num_hlt_phases += _stats.run_num_hlt_phases;
        _stats.all_num_felsch_phases += _stats.run_num_felsch_phases;
        _stats.all_num_lookahead_phases += _stats.run_num_lookahead_phases;
 
        _stats.all_hlt_phases_time += _stats.run_hlt_phases_time;
        _stats.all_felsch_phases_time += _stats.run_felsch_phases_time;
        _stats.all_lookahead_phases_time += _stats.run_lookahead_phases_time;
      }
 
      void stats_phase_start() {
        _stats.phase_start_time = std::chrono::high_resolution_clock::now();
        _stats.report_index     = 0;
 
        _stats.phase_nodes_active_at_start
            = current_word_graph().number_of_nodes_active();
        _stats.phase_nodes_killed_at_start
            = current_word_graph().number_of_nodes_killed();
        _stats.phase_nodes_defined_at_start
            = current_word_graph().number_of_nodes_defined();
 
        _stats.phase_edges_active_at_start
            = current_word_graph().number_of_edges_active();
        _stats.phase_complete_at_start
            = complete(current_word_graph().number_of_edges_active());
      }
 
      void stats_phase_stop() {
        _stats.phase_index++;
 
        switch (_state) {
          case state::none: {
            break;
          }
          case state::hlt: {
            _stats.run_num_hlt_phases++;
            _stats.run_hlt_phases_time += delta(_stats.phase_start_time);
            break;
          }
          case state::felsch: {
            _stats.run_num_felsch_phases++;
            _stats.run_felsch_phases_time += delta(_stats.phase_start_time);
            break;
          }
          case state::lookahead: {
            _stats.run_num_lookahead_phases++;
            _stats.run_lookahead_phases_time += delta(_stats.phase_start_time);
            break;
          }
          default: {
            break;
          }
        }
      }
 
      void stats_report_stop() const {
        _stats.report_index++;
      }
 
      // Simple struct that allows the "receivers" value to be set to "val" but
      // only when the object goes out of scope. Useful in reporting when
      // we want to do something with an old value, then update the data member
      // of Stats.
      class DeferSet {
        uint64_t& _receiver;
        uint64_t  _val;
 
       public:
        DeferSet(uint64_t& receiver, uint64_t val)
            : _receiver(receiver), _val(val) {}
 
        operator uint64_t() {
          return _val;
        }
 
        ~DeferSet() {
          _receiver = _val;
        }
      };
 
     public:
      // ?. ToddCoxeterImpl - nested classes - public
 
      class Definitions {
        using Definition = std::pair<node_type, label_type>;
 
       private:
        bool                    _any_skipped;
        std::vector<Definition> _definitions;
        ToddCoxeterImpl const*  _tc;
 
       public:
        Definitions() : _any_skipped(false), _definitions(), _tc(nullptr) {}
        // TODO(1) init()
 
        Definitions(Definitions const&)                 = default;
        Definitions(Definitions&&)                      = default;
        Definitions& operator=(Definitions const& that) = default;
        Definitions& operator=(Definitions&&)           = default;
 
        // TODO(1) corresponding constructor
        void init(ToddCoxeterImpl const* tc) {
          _any_skipped = false;
          _definitions.clear();
          _tc = tc;
        }
 
        void emplace_back(node_type c, label_type x);
 
        [[nodiscard]] bool any_skipped() const noexcept {
          return _any_skipped;
        }
 
        [[nodiscard]] bool empty() const noexcept {
          return _definitions.empty();
        }
 
        void pop(Definition& d) {
          d = std::move(_definitions.back());
          _definitions.pop_back();
        }
 
        void clear() {
          _definitions.clear();
        }
 
       private:
        bool is_active_node(node_type n) const noexcept {
          return _tc->current_word_graph().is_active_node(n);
        }
      };  // class Definitions
 
      class Graph
          : public FelschGraph<NodeManagedGraph<node_type>, Definitions> {
        using FelschGraph_
            = FelschGraph<NodeManagedGraph<node_type>, Definitions>;
 
       public:
        Graph()                        = default;
        Graph(Graph const&)            = default;
        Graph(Graph&&)                 = default;
        Graph& operator=(Graph const&) = default;
        Graph& operator=(Graph&&)      = default;
 
        Graph& operator=(WordGraph<node_type> const& wg) {
          FelschGraph_::operator=(wg);
          return *this;
        }
 
        using FelschGraph_::presentation;
        using FelschGraph_::target_no_checks;
 
        Graph& init();
        Graph& init(Presentation<word_type>&& p);
 
        Graph& init(Presentation<word_type> const& p,
                    WordGraph<node_type> const&    wg) {
          FelschGraph_::operator=(wg);
          FelschGraph_::presentation_no_checks(p);
          return *this;
        }
 
        Graph& presentation_no_checks(Presentation<word_type> const& p);
 
        void process_definitions();
 
        template <bool RegDefs>
        void push_definition_hlt(node_type const& c,
                                 word_type const& u,
                                 word_type const& v);
 
        template <typename Iterator>
        void make_compatible(ToddCoxeterImpl* tc,
                             node_type&       current,
                             Iterator         first,
                             Iterator         last,
                             bool             stop_early);
 
       private:
        void report_lookahead_stop_early(ToddCoxeterImpl* tc,
                                         size_t           expected,
                                         size_t           killed_last_interval);
      };  // class Graph
 
     private:
      // 2. ToddCoxeterImpl - data members - private
 
      bool                                   _finished;
      Forest                                 _forest;
      std::vector<std::unique_ptr<Settings>> _settings_stack;
      Order                                  _standardized;
      // _state must be atomic to avoid the situation where the ticker
      // function is called concurrently with a new lookahead starting
      std::atomic<state> _state;
      Stats              _stats;
      bool               _ticker_running;
      Graph              _word_graph;
 
     public:
      using word_graph_type = Graph;

      // 3. ToddCoxeterImpl - constructors + initializers - public
 
      ToddCoxeterImpl();
      ToddCoxeterImpl& init();
 
      ToddCoxeterImpl(ToddCoxeterImpl const& that);
      ToddCoxeterImpl(ToddCoxeterImpl&&);
      ToddCoxeterImpl& operator=(ToddCoxeterImpl const&);
      ToddCoxeterImpl& operator=(ToddCoxeterImpl&&);
 
      ~ToddCoxeterImpl();
 
      ToddCoxeterImpl(congruence_kind knd, Presentation<word_type>&& p);
      ToddCoxeterImpl& init(congruence_kind knd, Presentation<word_type>&& p);
      ToddCoxeterImpl(congruence_kind knd, Presentation<word_type> const& p);
      ToddCoxeterImpl& init(congruence_kind                knd,
                            Presentation<word_type> const& p);
 
      // TODO(1) a "to" function variant that throws if wg is not valid see
      // below
      template <typename Node>
      ToddCoxeterImpl(congruence_kind knd, WordGraph<Node> const& wg)
          : ToddCoxeterImpl() {
        LIBSEMIGROUPS_ASSERT(!_settings_stack.empty());
        init(knd, wg);
      }
 
      template <typename Node>
      ToddCoxeterImpl& init(congruence_kind knd, WordGraph<Node> const& wg);
 
      // TODO(1) rvalue ref WordGraph init + constructor
 
      ToddCoxeterImpl(congruence_kind knd, ToddCoxeterImpl const& tc);
 
      ToddCoxeterImpl& init(congruence_kind knd, ToddCoxeterImpl const& tc);
 
      ToddCoxeterImpl& presentation_no_checks(Presentation<word_type> const& p);
 
      // This is a constructor and not a helper so that everything that takes
      // a presentation has the same constructors, regardless of what they use
      // inside.
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      // Used in Sims
      // TODO(1) could this and the next function be removed, and replaced
      // with something else?
      template <typename Node>
      ToddCoxeterImpl(congruence_kind                knd,
                      Presentation<word_type> const& p,
                      WordGraph<Node> const&         wg) {
        init(knd, p, wg);
      }
 
      // TODO(1) a to_todd_coxeter variant that throws if p is not valid
      template <typename Node>
      ToddCoxeterImpl& init(congruence_kind                knd,
                            Presentation<word_type> const& p,
                            WordGraph<Node> const&         wg);
#endif
 
      template <typename Iterator1, typename Iterator2>
      void throw_if_letter_not_in_alphabet(Iterator1 first,
                                           Iterator2 last) const {
        internal_presentation().throw_if_letter_not_in_alphabet(first, last);
      }

      // 4. ToddCoxeterImpl - interface requirements - add_generating_pair
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      ToddCoxeterImpl& add_generating_pair_no_checks(Iterator1 first1,
                                                     Iterator2 last1,
                                                     Iterator3 first2,
                                                     Iterator4 last2) {
        return CongruenceCommon::add_internal_generating_pair_no_checks<
            ToddCoxeterImpl>(first1, last1, first2, last2);
      }
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      ToddCoxeterImpl& add_generating_pair(Iterator1 first1,
                                           Iterator2 last1,
                                           Iterator3 first2,
                                           Iterator4 last2) {
        return CongruenceCommon::add_generating_pair<ToddCoxeterImpl>(
            first1, last1, first2, last2);
      }

      // 5. ToddCoxeterImpl - interface requirements - number_of_classes

      [[nodiscard]] uint64_t number_of_classes();

      // 6. ToddCoxeterImpl - interface requirements - contains
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      tril currently_contains_no_checks(Iterator1 first1,
                                        Iterator2 last1,
                                        Iterator3 first2,
                                        Iterator4 last2) const;
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      tril currently_contains(Iterator1 first1,
                              Iterator2 last1,
                              Iterator3 first2,
                              Iterator4 last2) const {
        return CongruenceCommon::currently_contains<ToddCoxeterImpl>(
            first1, last1, first2, last2);
      }
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      bool contains_no_checks(Iterator1 first1,
                              Iterator2 last1,
                              Iterator3 first2,
                              Iterator4 last2);
 
      template <typename Iterator1,
                typename Iterator2,
                typename Iterator3,
                typename Iterator4>
      bool contains(Iterator1 first1,
                    Iterator2 last1,
                    Iterator3 first2,
                    Iterator4 last2);

      // 7. ToddCoxeterImpl - interface requirements - reduce
 
      template <typename OutputIterator,
                typename InputIterator1,
                typename InputIterator2>
      OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
                                             InputIterator1 first,
                                             InputIterator2 last) const;
 
      template <typename OutputIterator,
                typename InputIterator1,
                typename InputIterator2>
      OutputIterator reduce_no_run(OutputIterator d_first,
                                   InputIterator1 first,
                                   InputIterator2 last) const {
        return CongruenceCommon::reduce_no_run<ToddCoxeterImpl>(
            d_first, first, last);
      }
 
      template <typename OutputIterator,
                typename InputIterator1,
                typename InputIterator2>
      OutputIterator reduce_no_checks(OutputIterator d_first,
                                      InputIterator1 first,
                                      InputIterator2 last) {
        return CongruenceCommon::reduce_no_checks<ToddCoxeterImpl>(
            d_first, first, last);
      }
 
      template <typename OutputIterator,
                typename InputIterator1,
                typename InputIterator2>
      OutputIterator reduce(OutputIterator d_first,
                            InputIterator1 first,
                            InputIterator2 last) {
        return CongruenceCommon::reduce<ToddCoxeterImpl>(d_first, first, last);
      }

      // 8. ToddCoxeterImpl - settings - public
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      // This is documented in Reporter, so we don't duplicate the doc here.
      template <typename Time>
      void report_every(Time val) {
        CongruenceCommon::report_every(val);
      }
 
      [[nodiscard]] nanoseconds report_every() const noexcept {
        return Reporter::report_every();
      }
#endif

      ToddCoxeterImpl& def_max(size_t val) noexcept;

      [[nodiscard]] size_t def_max() const noexcept;

      ToddCoxeterImpl& def_policy(options::def_policy val);

      [[nodiscard]] options::def_policy def_policy() const noexcept;

      ToddCoxeterImpl& f_defs(size_t val);

      [[nodiscard]] size_t f_defs() const noexcept;

      ToddCoxeterImpl& hlt_defs(size_t val);

      [[nodiscard]] size_t hlt_defs() const noexcept;

      ToddCoxeterImpl& large_collapse(size_t val) noexcept;

      [[nodiscard]] size_t large_collapse() const noexcept;

      ToddCoxeterImpl& lookahead_extent(options::lookahead_extent val) noexcept;

      [[nodiscard]] options::lookahead_extent lookahead_extent() const noexcept;

      ToddCoxeterImpl& lookahead_growth_factor(float val);

      [[nodiscard]] float lookahead_growth_factor() const noexcept;

      ToddCoxeterImpl& lookahead_growth_threshold(size_t val) noexcept;

      [[nodiscard]] size_t lookahead_growth_threshold() const noexcept;

      ToddCoxeterImpl& lookahead_min(size_t val) noexcept;

      [[nodiscard]] size_t lookahead_min() const noexcept;

      ToddCoxeterImpl& lookahead_next(size_t val) noexcept;

      [[nodiscard]] size_t lookahead_next() const noexcept;

      ToddCoxeterImpl&
      lookahead_stop_early_interval(std::chrono::nanoseconds val) noexcept;

      std::chrono::nanoseconds lookahead_stop_early_interval() const noexcept;

      ToddCoxeterImpl& lookahead_stop_early_ratio(float val);

      float lookahead_stop_early_ratio() const noexcept;

      ToddCoxeterImpl& lookahead_style(options::lookahead_style val) noexcept;

      [[nodiscard]] options::lookahead_style lookahead_style() const noexcept;

      ToddCoxeterImpl& lower_bound(size_t val) noexcept;

      [[nodiscard]] size_t lower_bound() const noexcept;

      ToddCoxeterImpl& save(bool val) noexcept;

      [[nodiscard]] bool save() const noexcept;

      ToddCoxeterImpl& strategy(options::strategy val) noexcept;

      [[nodiscard]] options::strategy strategy() const noexcept;

      ToddCoxeterImpl& use_relations_in_extra(bool val) noexcept;

      [[nodiscard]] bool use_relations_in_extra() const noexcept;
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      ToddCoxeterImpl& def_version(options::def_version val);

      [[nodiscard]] options::def_version def_version() const noexcept;
#else
      using FelschGraphSettings_::def_version;
      using FelschGraphSettings_::settings;
#endif

      // 9. ToddCoxeterImpl - accessors - public
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      [[nodiscard]] Presentation<word_type> const&
      internal_presentation() const noexcept {
        return _word_graph.presentation();
      }
#endif

      // This isn't really necessary in C++, but in the python bindings we don't
      // bind ToddCoxeter::Graph and so we expose this here.
      [[nodiscard]] uint64_t number_of_nodes_active() const noexcept {
        return current_word_graph().number_of_nodes_active();
      }

      // This isn't really necessary in C++, but in the python bindings we don't
      // bind ToddCoxeter::Graph and so we expose this here.
      [[nodiscard]] uint64_t number_of_edges_active() const noexcept {
        return current_word_graph().number_of_edges_active();
      }

      [[nodiscard]] float complete() const noexcept {
        return complete(current_word_graph().number_of_edges_active());
      }
 
      // [[nodiscard]] bool empty() const {
      //   return (internal_presentation().rules.empty() &&
      //   generating_pairs().empty()
      //           && current_word_graph().number_of_nodes_active() == 1);
      //   // FIXME(1) there's an issue where the word graph can have 0
      //   nodes but
      //   1
      //   // active node.
      // }

      word_graph_type const& current_word_graph() const noexcept {
        return _word_graph;
      }

      word_graph_type const& word_graph();

      Forest const& current_spanning_tree() const noexcept {
        return _forest;
      }

      Forest const& spanning_tree();

      inline Order standardization_order() const noexcept {
        return _standardized;
      }

      bool is_standardized(Order val) const;

      bool is_standardized() const;

      [[nodiscard]] uint64_t number_of_large_collapses() const noexcept {
        return _word_graph.stats().num_large_collapses;
      }

      // 10. ToddCoxeterImpl - modifiers - public

      void shrink_to_fit();

      bool standardize(Order val);

      void perform_lookahead(bool stop_early);

      // 11. ToddCoxeterImpl - word -> index


      // NOTE: the graph contains one more node than there are element
      // if the underlying presentation does not contain the empty word
      template <typename Iterator1, typename Iterator2>
      index_type current_index_of_no_checks(Iterator1 first,
                                            Iterator2 last) const;

      template <typename Iterator1, typename Iterator2>
      index_type current_index_of(Iterator1 first, Iterator2 last) const {
        throw_if_letter_not_in_alphabet(first, last);
        return current_index_of_no_checks(first, last);
      }

      template <typename Iterator1, typename Iterator2>
      index_type index_of_no_checks(Iterator1 first, Iterator2 last);

      template <typename Iterator1, typename Iterator2>
      index_type index_of(Iterator1 first, Iterator2 last) {
        throw_if_letter_not_in_alphabet(first, last);
        return index_of_no_checks(first, last);
      }


      // 12. ToddCoxeterImpl - index -> word


      // NOTE THAT: the graph contains one more node than there are element
      // if the underlying presentation does not contain the empty word
      template <typename OutputIterator>
      OutputIterator current_word_of_no_checks(OutputIterator d_first,
                                               index_type     i) const;

      template <typename OutputIterator>
      OutputIterator current_word_of(OutputIterator d_first,
                                     index_type     i) const;

      template <typename Iterator>
      Iterator word_of_no_checks(Iterator d_first, index_type i) {
        run();
        LIBSEMIGROUPS_ASSERT(finished());
        return current_word_of_no_checks(d_first, i);
      }

      template <typename Iterator>
      Iterator word_of(Iterator d_first, index_type i) {
        run();
        LIBSEMIGROUPS_ASSERT(finished());
        return current_word_of(d_first, i);
      }

 
     private:
      // 13. Runner - pure virtual member functions - private
 
      void really_run_impl();
 
      void run_impl() override;
 
      [[nodiscard]] bool finished_impl() const override {
        return _finished;
      }

      // 14. ToddCoxeterImpl - member functions - private
 
      void copy_settings_into_graph();
 
      // This function has prefix tc_ because there's already a settings
      // function in a base class
      Settings&       tc_settings();
      Settings const& tc_settings() const;
 
      void reset_settings_stack();
 
      [[nodiscard]] bool any_change() const {
        return _stats.run_nodes_active_at_start
               != current_word_graph().number_of_nodes_active();
      }
 
      // We take both values here, although we could compute them, so that in
      // report_progress_from_thread we do not report at one point in time with
      // some value, then within the same function call (if the graph is
      // changing a lot) report with another value
      [[nodiscard]] float complete(uint64_t num_nodes,
                                   int64_t  num_edges) const noexcept {
        return static_cast<float>(num_edges)
               / (static_cast<uint64_t>(num_nodes)
                  * current_word_graph().out_degree());
      }
 
      [[nodiscard]] float complete(int64_t num_edges) const noexcept {
        return complete(current_word_graph().number_of_nodes_active(),
                        num_edges);
      }
 
      [[nodiscard]] bool lookahead_stop_early(
          bool                                            stop_early,
          std::chrono::high_resolution_clock::time_point& last_stop_early_check,
          uint64_t& killed_at_prev_interval);

      // ToddCoxeterImpl - main strategies - private
 
      void init_run();
      void finalise_run();
 
      void felsch();
      void hlt();
      void CR_style();
      void R_over_C_style();
      void Cr_style();
      void Rc_style();

      // ToddCoxeterImpl - reporting - private
 
      void report_after_phase() const;
      void report_after_lookahead(size_t old_lookahead_next) const;
      void report_after_run() const;
      void report_before_phase(std::string_view = "") const;
      void report_before_lookahead() const;
      void report_before_run() const;
      void report_lookahead_stop_early(size_t expected,
                                       size_t killed_last_interval);
      void report_presentation() const;
      void report_progress_from_thread(bool divider) const;
      void report_times() const;
 
      void add_timing_row(ReportCell<5>& rc) const;
 
      // The 2nd (and 3rd) arguments for the next 2 functions are required
      // because we need the values at a fixed point in time (due to
      // multi-threaded reporting).
      void add_nodes_rows(ReportCell<5>& rc, uint64_t num_active_nodes) const;
      void add_edges_rows(ReportCell<5>& rc,
                          uint64_t       num_active_nodes,
                          uint64_t       num_active_edges) const;
      void add_lookahead_row(ReportCell<5>& rc) const;

      // ToddCoxeterImpl - lookahead - private
 
      static constexpr bool StopEarly      = true;
      static constexpr bool DoNotStopEarly = false;
 
      void hlt_lookahead(bool stop_early);
      void felsch_lookahead(bool stop_early);
    };  // class ToddCoxeterImpl
 
  }  // namespace detail
 
}  // namespace libsemigroups
 
#include "todd-coxeter-impl.tpp"
#endif  // LIBSEMIGROUPS_DETAIL_TODD_COXETER_IMPL_HPP_