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
// * implement number_of_nodes_killed_last_phase or similar, to allow easy
// running of the previous perform_lookahead(stop_early).
// * make all the non-core strategies helpers
 
#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/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...
 
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:
      // Member types - public
 
      struct options : public FelschGraphSettings_::options {
        enum class strategy {
          hlt,
          felsch,
          lookahead,
          lookbehind,
          CR,
          R_over_C,
          Cr,
          Rc,
        };
 
        enum class lookahead_extent { full, partial };
        // TODO(1) enum class lookbehind_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, lookbehind };
 
      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:
      // 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;
        std::chrono::nanoseconds all_lookbehind_phases_time;
 
        uint64_t all_num_hlt_phases;
        uint64_t all_num_felsch_phases;
        uint64_t all_num_lookahead_phases;
        uint64_t all_num_lookbehind_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;
        std::chrono::nanoseconds run_lookbehind_phases_time;
 
        uint64_t run_num_hlt_phases;
        uint64_t run_num_felsch_phases;
        uint64_t run_num_lookahead_phases;
        uint64_t run_num_lookbehind_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_or_behind_nodes_killed;
        std::atomic_uint64_t lookahead_or_behind_position;
 
        // Constructors + initialisers
        Stats();
        Stats& init();
        Stats(Stats const& that);
        Stats(Stats&& that);
        Stats& operator=(Stats const& that);
        Stats& operator=(Stats&& that);
      };
 
      void stats_run_start();
      void stats_run_stop();
      void stats_phase_start();
      void stats_phase_stop();
      void stats_report_stop() const;
 
     public:
      // 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
 
      // TODO(v4) document ToddCoxeterImpl::Graph, some of ToddCoxeterImpl's
      // doc for deprecated mem fns already refers to mem fns of Graph, so when
      // they are removed the doc will have no where to live if it isn't
      // included here.
      class Graph
          : public FelschGraph<NodeManagedGraph<node_type>, Definitions> {
        friend class ToddCoxeterImpl;

        // Private aliases
        using FelschGraph_
            = FelschGraph<NodeManagedGraph<node_type>, Definitions>;

        // Private data
        mutable Forest _forest;
        mutable bool   _forest_valid;
        Order          _standardization_order;
 
       public:
        // Constructors and initializers
        Graph();
        Graph& init();
 
        Graph(Graph const&)            = default;
        Graph(Graph&&)                 = default;
        Graph& operator=(Graph const&) = default;
        Graph& operator=(Graph&&)      = default;
 
        Graph& init(Presentation<word_type>&& p);
 
        Graph& init(Presentation<word_type> const& p,
                    WordGraph<node_type> const&    wg);
 
        Graph& operator=(WordGraph<node_type> const& wg);

        // FelschGraph_ mem fns
 
        using FelschGraph_::presentation;
        using FelschGraph_::standardize;
        using FelschGraph_::target_no_checks;

        // Modifiers
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
        // NOTE: Should be private but can't be because used by is_non_trivial
        // but is_non_trivial is declared in todd-coxeter-helpers.hpp and so
        // it is not straightforward to make these functions friends,
        // unfortunately.
        template <typename Functor = Noop>
        void process_coincidences(Functor&& func = Noop{});
 
        // NOTE: Should be private but can't be because used by is_non_trivial
        // but is_non_trivial is declared in todd-coxeter-helpers.hpp and so
        // it is not straightforward to make these functions friends,
        // unfortunately.
        void process_definitions();
#endif

        // Spanning tree
 
        // TODO(v4) doc
        [[nodiscard]] bool is_spanning_tree_valid() const noexcept {
          return _forest_valid;
        }
 
        // TODO(v4) doc
        Forest const& current_spanning_tree() const {
          return const_cast<Graph&>(*this).current_spanning_tree();
        }

        // Standardization
 
        [[nodiscard]] bool is_standardized(Order val) const {
          return _standardization_order == val;
        }
 
        [[nodiscard]] bool is_standardized() const {
          return _standardization_order != Order::none;
        }
 
        [[nodiscard]] inline Order standardization_order() const noexcept {
          return _standardization_order;
        }
 
       private:
        // Almost all non-const mem fns are private, since they cannot be used
        // anyway (we only permit const access to the word_graph)

        // Spanning tree
 
        Forest& current_spanning_tree();

        // Standardization
 
        bool standardize(Order val);

        // FelschGraph_ mem fns overrides
 
        // Functions that are present in the FelschGraph_, but must be
        // overridden here so that the validation and standardization stuff is
        // reset.
 
        Graph& target_no_checks(node_type  s,
                                label_type a,
                                node_type  t) noexcept;
 
        Graph& register_target_no_checks(node_type  s,
                                         label_type a,
                                         node_type  t) noexcept;

        // Other modifiers
 
        Graph& presentation_no_checks(Presentation<word_type> const& p);
 
        template <typename Iterator>
        void make_compatible(ToddCoxeterImpl* tc,
                             node_type&       current,
                             Iterator         first,
                             Iterator         last,
                             bool             should_stop_early);
 
        template <bool RegDefs>
        void push_definition_hlt(node_type const& c,
                                 word_type const& u,
                                 word_type const& v);

        // Reporting
 
        void report_lookahead_stop_early(ToddCoxeterImpl* tc,
                                         size_t           expected,
                                         size_t           killed_last_interval);
      };  // class Graph
 
     private:
      // Data members - private
 
      std::function<void(std::back_insert_iterator<word_type>,
                         typename word_type::const_iterator,
                         typename word_type::const_iterator)>
                                             _lookbehind_collapser;
      bool                                   _finished;
      bool                                   _never_run;
      std::vector<std::unique_ptr<Settings>> _settings_stack;
      // _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;

      // 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 "make" 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);
      }

      // 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);
      }

      // Interface requirements - number_of_classes

      [[nodiscard]] uint64_t number_of_classes();

      // 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);

      // 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);
      }

      // Settings - public
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      // This is documented in Reporter, so we don't duplicate the doc here.
      template <typename Time>
      [[deprecated]] void report_every(Time val) {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
        CongruenceCommon::report_every(val);
#pragma GCC diagnostic pop
      }
 
      [[deprecated]] [[nodiscard]] nanoseconds report_every() const noexcept {
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
        return Reporter::report_every();
#pragma GCC diagnostic pop
      }
#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;

      [[nodiscard]] ToddCoxeterImpl& lookbehind_threshold(size_t val) noexcept;

      [[nodiscard]] size_t lookbehind_threshold() 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

      // 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.
      [[deprecated]] [[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.
      [[deprecated]] [[nodiscard]] uint64_t
      number_of_edges_active() const noexcept {
        return current_word_graph().number_of_edges_active();
      }

      // TODO(v4) move to the word graph itself
      [[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();

      // TODO(v4) move the doc to Graph
      [[deprecated]] Forest const& current_spanning_tree() const {
        return _word_graph.current_spanning_tree();
      }

      // TODO(v4) move the doc to Graph
      [[deprecated]] Forest const& spanning_tree();

      [[deprecated]] inline Order standardization_order() const noexcept {
        return current_word_graph().standardization_order();
      }

      [[deprecated]] bool is_standardized(Order val) const {
        return current_word_graph().is_standardized(val);
      }

      [[deprecated]] bool is_standardized() const {
        return current_word_graph().is_standardized();
      }

      // TODO(v4) deprecate and move to Graph, don't expose stats because it
      // contains a bunch of stuff that's probably not interesting
      [[nodiscard]] uint64_t number_of_large_collapses() const noexcept {
        return _word_graph.stats().num_large_collapses;
      }

      // Modifiers - public

      void shrink_to_fit();

      // We don't deprecated this (at least for now) since we only provide
      // const access to _word_graph, and so require modifiers to also be
      // member functions of ToddCoxeterImpl
      bool standardize(Order val) {
        return _word_graph.standardize(val);
      }

      ToddCoxeterImpl& perform_lookahead();

      [[deprecated]] void perform_lookahead(bool stop_early);

      ToddCoxeterImpl& perform_lookahead_for(std::chrono::nanoseconds t);

      ToddCoxeterImpl& perform_lookahead_until(std::function<bool()>&& pred);

      ToddCoxeterImpl&
      perform_lookahead_until(std::function<bool()> const& pred) {
        return perform_lookahead_until(std::function<bool()>(pred));
      }

      // This test takes a couple of seconds to run.
      ToddCoxeterImpl& perform_lookbehind();

      template <typename Func>
      ToddCoxeterImpl& perform_lookbehind_no_checks(Func&& collapser);

      ToddCoxeterImpl& perform_lookbehind_for(std::chrono::nanoseconds t);

      template <typename Func>
      ToddCoxeterImpl&
      perform_lookbehind_for_no_checks(std::chrono::nanoseconds t,
                                       Func&&                   collapser);

      ToddCoxeterImpl& perform_lookbehind_until(std::function<bool()>&& pred);

      ToddCoxeterImpl&
      perform_lookbehind_until(std::function<bool()> const& pred) {
        return perform_lookbehind_until(std::function<bool()>(pred));
      }

      template <typename Func>
      ToddCoxeterImpl&
      perform_lookbehind_until_no_checks(std::function<bool()>&& pred,
                                         Func&&                  collapser);

      template <typename Func>
      ToddCoxeterImpl&
      perform_lookbehind_until_no_checks(std::function<bool()> const& pred,
                                         Func&& collapser) {
        return perform_lookbehind_until_no_checks(std::function<bool()>(pred),
                                                  collapser);
      }

      // 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);
      }


      // 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:
      // Runner - pure virtual member functions - private
 
      [[nodiscard]] bool finished_impl() const override {
        return _finished;
      }
 
      void run_impl() override;

      // Misc member functions - private
 
      void copy_settings_into_graph();
 
      // WARNING: there's already a settings() mem fn in FelschGraphSettings,
      // beware of confusing the two.
      Settings&       settings();
      Settings const& settings() const;
 
      void reset_settings_stack();
 
      [[nodiscard]] bool any_change_last_run() const;
 
      // 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
      // TODO(v4) move into Graph
      [[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());
      }
 
      // TODO(v4) move into Graph
      [[nodiscard]] float complete(int64_t num_edges) const noexcept {
        return complete(current_word_graph().number_of_nodes_active(),
                        num_edges);
      }

      // Lookahead - private
 
      [[nodiscard]] bool lookahead_stop_early(
          bool                                            should_stop_early,
          std::chrono::high_resolution_clock::time_point& last_stop_early_check,
          uint64_t& killed_at_prev_interval);
 
      [[nodiscard]] size_t lookahead_update_settings();
 
      ToddCoxeterImpl& perform_lookahead_impl(bool should_stop_early);
      ToddCoxeterImpl& perform_lookbehind_impl();
 
      void hlt_lookahead(bool should_stop_early);
      void felsch_lookahead(bool should_stop_early);

      // Main strategies - private
 
      void before_run();
      void after_run();
      void felsch();
      void hlt();
 
      // TODO(v4) to helpers
      void CR_style();
      void R_over_C_style();
      void Cr_style();
      void Rc_style();

      // ToddCoxeterImpl - reporting - private
 
      using ReportCell_ = ReportCell<6>;
 
      void report_after_phase() 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_settings(size_t old_lookahead_next) 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_& 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_& rc, uint64_t num_active_nodes) const;
      void add_edges_rows(ReportCell_& rc,
                          uint64_t     num_active_nodes,
                          uint64_t     num_active_edges) const;
      void add_lookahead_or_behind_row(ReportCell_& rc) const;
    };  // class ToddCoxeterImpl
  }     // namespace detail
}  // namespace libsemigroups
#include "todd-coxeter-impl.tpp"
#endif  // LIBSEMIGROUPS_DETAIL_TODD_COXETER_IMPL_HPP_