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
// * re-add report why stopped
 
#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 detail::CongruenceCommon,
          public detail::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
 
      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;
 
      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 detail::NodeManagedGraph<
                        detail::FelschGraph<word_type, uint32_t, Definitions>> {
        using FelschGraph_
            = detail::FelschGraph<word_type, uint32_t, Definitions>;
        using NodeManagedGraph_ = NodeManagedGraph<FelschGraph_>;
 
       public:
        using node_type = typename NodeManagedGraph_::node_type;
 
        Graph()                        = default;
        Graph(Graph const&)            = default;
        Graph(Graph&&)                 = default;
        Graph& operator=(Graph const&) = default;
        Graph& operator=(Graph&&)      = default;
        // TODO(1) init()
 
        Graph& operator=(WordGraph<node_type> const& wg) {
          NodeManagedGraph_::operator=(wg);
          return *this;
        }
 
        using FelschGraph_::presentation;
        using FelschGraph_::target_no_checks;
        using NodeManagedGraph_::NodeManagedGraph;
 
        Graph& init();
        // TODO(1) corresponding constructors
        Graph& init(Presentation<word_type> const& p);
        Graph& init(Presentation<word_type>&& p);
 
        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>
        size_t 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

      // 2. ToddCoxeterImpl - data members - private
 
      bool                                   _finished;
      Forest                                 _forest;
      std::vector<std::unique_ptr<Settings>> _settings_stack;
      Order                                  _standardized;
      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_todd_coxeter 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 detail::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 detail::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 detail::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 detail::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 detail::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 detail::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) {
        detail::CongruenceCommon::report_every(val);
        _word_graph.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
 
      [[nodiscard]] uint64_t number_of_nodes_active() const noexcept {
        return _word_graph.number_of_nodes_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;

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

      // 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_lookahead(size_t old_lookahead_next,
                                  size_t number_killed_in_lookahead,
                                  std::chrono::high_resolution_clock::time_point
                                      lookahead_start_time) const;
      void report_after_run() const;
      void report_before_lookahead() const;
      void report_before_run() const;
      void report_presentation() const;
      void report_strategy() const;

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