todd-coxeter-class.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025-2026 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 the declaration of the ToddCoxeter class. This class
// exists mostly to wrap ToddCoxeterImpl (where the action happens) to make it
// more user friendly. In particular, ToddCoxeter presentation()
// and generating_pairs() return the input presentation and generating pairs,
// whatever their type, and not the normalized Presentation<word_type> required
// by ToddCoxeterImpl.
 
#ifndef LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
#define LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
 
#include <algorithm>    // for equal
#include <cstddef>      // for ptrdiff_t, size_t
#include <iterator>     // for bidirectional_iterator_tag
#include <string>       // for basic_string, string
#include <type_traits>  // for is_same_v
#include <utility>      // for move
#include <vector>       // for vector
 
#include "presentation.hpp"  // for Presentation
#include "types.hpp"         // for congruence_kind
 
#include "detail/citow.hpp"              // for detail::citow and detail::itow
#include "detail/cong-common-class.hpp"  // for detail::CongruenceCommon
#include "detail/fmt.hpp"                // for fmt
#include "detail/todd-coxeter-impl.hpp"  // for ToddCoxeterImpl
 
namespace libsemigroups {


  template <typename Word>
  class ToddCoxeter : public detail::ToddCoxeterImpl {
   private:
    std::vector<Word>  _generating_pairs;
    Presentation<Word> _presentation;
 
   public:
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    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
      };
 
      // NOTE: The next enum (def_version) is actually defined in FelschGraph,
      // not in ToddCoxeter

      enum class def_version : uint8_t {
        one,
        two,
      };
    };

    [[nodiscard]] congruence_kind kind() const noexcept;

    [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
#endif

    using native_word_type = Word;

    using node_type = typename detail::ToddCoxeterImpl::node_type;

    using word_graph_type = typename detail::ToddCoxeterImpl::word_graph_type;

    using index_type = typename detail::ToddCoxeterImpl::index_type;

    using label_type = typename detail::ToddCoxeterImpl::label_type;

    ToddCoxeter() = default;

    ToddCoxeter& init();

    ToddCoxeter(ToddCoxeter const&) = default;

    ToddCoxeter(ToddCoxeter&&) = default;

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

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

    ToddCoxeter(congruence_kind knd, Presentation<Word>&& p) : ToddCoxeter() {
      init(knd, std::move(p));
    }

    ToddCoxeter& init(congruence_kind knd, Presentation<Word>&& p);

    ToddCoxeter(congruence_kind knd, Presentation<Word> const& p)
        // call the rval ref constructor
        : ToddCoxeter(knd, Presentation<Word>(p)) {}

    ToddCoxeter& init(congruence_kind knd, Presentation<Word> const& p) {
      // call the rval ref init
      return init(knd, Presentation<Word>(p));
    }

    ToddCoxeter(congruence_kind knd, ToddCoxeter const& tc) : ToddCoxeter() {
      init(knd, tc);
    }

    ToddCoxeter& init(congruence_kind knd, ToddCoxeter const& tc);

    template <typename Node>
    ToddCoxeter(congruence_kind knd, WordGraph<Node> const& wg)
        : ToddCoxeter() {
      init(knd, wg);
    }

    template <typename Node>
    ToddCoxeter& init(congruence_kind knd, WordGraph<Node> const& wg);
 
#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>
    ToddCoxeter(congruence_kind           knd,
                Presentation<Word> const& p,
                WordGraph<Node> const&    wg) {
      init(knd, p, wg);
    }
 
    // TODO(1) a "make" variant that throws if params are valid
    template <typename Node>
    ToddCoxeter& init(congruence_kind           knd,
                      Presentation<Word> const& p,
                      WordGraph<Node> const&    wg);
#endif

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

    [[nodiscard]] std::vector<Word> const& generating_pairs() const noexcept {
      return _generating_pairs;
    }

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

    // ToddCoxeter - interface requirements - add_generating_pair

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    ToddCoxeter& add_generating_pair_no_checks(Iterator1 first1,
                                               Iterator2 last1,
                                               Iterator3 first2,
                                               Iterator4 last2);

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    ToddCoxeter& add_generating_pair(Iterator1 first1,
                                     Iterator2 last1,
                                     Iterator3 first2,
                                     Iterator4 last2) {
      // Call detail::CongruenceCommon version so that we perform bound checks
      // in ToddCoxeter and not ToddCoxeterImpl
      return detail::CongruenceCommon::add_generating_pair<ToddCoxeter>(
          first1, last1, first2, last2);
    }

    // ToddCoxeter - 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 {
      return ToddCoxeterImpl::currently_contains_no_checks(
          detail::citow(this, first1),
          detail::citow(this, last1),
          detail::citow(this, first2),
          detail::citow(this, last2));
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    tril currently_contains(Iterator1 first1,
                            Iterator2 last1,
                            Iterator3 first2,
                            Iterator4 last2) const {
      // Call detail::CongruenceCommon version so that we perform bound checks
      // in ToddCoxeter and not ToddCoxeterImpl
      return detail::CongruenceCommon::currently_contains<ToddCoxeter>(
          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) {
      return ToddCoxeterImpl::contains_no_checks(detail::citow(this, first1),
                                                 detail::citow(this, last1),
                                                 detail::citow(this, first2),
                                                 detail::citow(this, last2));
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    bool contains(Iterator1 first1,
                  Iterator2 last1,
                  Iterator3 first2,
                  Iterator4 last2);

    // ToddCoxeter - interface requirements - reduce

    template <typename OutputIterator,
              typename InputIterator1,
              typename InputIterator2>
    OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
                                           InputIterator1 first,
                                           InputIterator2 last) const {
      return ToddCoxeterImpl::reduce_no_run_no_checks(
                 detail::itow(this, d_first),
                 detail::citow(this, first),
                 detail::citow(this, last))
          .get();
    }

    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<ToddCoxeter>(
          d_first, first, last);
    }

    template <typename OutputIterator,
              typename InputIterator1,
              typename InputIterator2>
    OutputIterator reduce_no_checks(OutputIterator d_first,
                                    InputIterator1 first,
                                    InputIterator2 last) {
      return ToddCoxeterImpl::reduce_no_checks(detail::itow(this, d_first),
                                               detail::citow(this, first),
                                               detail::citow(this, last))
          .get();
    }

    template <typename OutputIterator,
              typename InputIterator1,
              typename InputIterator2>
    OutputIterator reduce(OutputIterator d_first,
                          InputIterator1 first,
                          InputIterator2 last) {
      // Call detail::CongruenceCommon version so that we perform bound checks
      // in ToddCoxeter and not ToddCoxeterImpl
      return detail::CongruenceCommon::reduce<ToddCoxeter>(
          d_first, first, last);
    }

    // ToddCoxeterImpl - word -> index


    // NOTE THAT: 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 {
      return ToddCoxeterImpl::current_index_of_no_checks(
          detail::citow(this, first), detail::citow(this, last));
    }

    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) {
      return ToddCoxeterImpl::index_of_no_checks(detail::citow(this, first),
                                                 detail::citow(this, 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);
    }


    // ToddCoxeter - 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 {
      return ToddCoxeterImpl::current_word_of_no_checks(
                 detail::itow(this, d_first), i)
          .get();
    }

    template <typename OutputIterator>
    OutputIterator current_word_of(OutputIterator d_first, index_type i) const {
      return ToddCoxeterImpl::current_word_of(detail::itow(this, d_first), i)
          .get();
    }

    template <typename Iterator>
    Iterator word_of_no_checks(Iterator d_first, index_type i) {
      return ToddCoxeterImpl::word_of_no_checks(detail::itow(this, d_first), i)
          .get();
    }

    template <typename Iterator>
    Iterator word_of(Iterator d_first, index_type i) {
      return ToddCoxeterImpl::word_of(detail::itow(this, d_first), i).get();
    }


    // Lookbehind
 
    // NOTE: the following functions must also appear here because the
    // "collapser" needs to be wrapped for compatibility with ToddCoxeterImpl
 
    template <typename Func>
    ToddCoxeter& perform_lookbehind_no_checks(Func&& collapser);
 
    template <typename Func>
    ToddCoxeter& perform_lookbehind_for_no_checks(std::chrono::nanoseconds t,
                                                  Func&& collapser);
 
    template <typename Func>
    ToddCoxeter&
    perform_lookbehind_until_no_checks(std::function<bool()>&& pred,
                                       Func&&                  collapser);
 
    template <typename Func>
    ToddCoxeter&
    perform_lookbehind_until_no_checks(std::function<bool()> const& pred,
                                       Func&&                       collapser) {
      return perform_lookbehind_until_no_checks(std::function<bool()>(pred),
                                                collapser);
    }
  };  // class ToddCoxeter

  template <typename Word>
  ToddCoxeter(congruence_kind, Presentation<Word> const&) -> ToddCoxeter<Word>;

  //
  template <typename Word>
  ToddCoxeter(congruence_kind, Presentation<Word>&&) -> ToddCoxeter<Word>;

  //
  template <typename Word>
  ToddCoxeter(congruence_kind, ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;

  //
  template <typename Node>
  ToddCoxeter(congruence_kind, WordGraph<Node> const&)
      -> ToddCoxeter<word_type>;

  //
  template <typename Node>
  ToddCoxeter(congruence_kind, WordGraph<Node>&&) -> ToddCoxeter<word_type>;

  //
  template <typename Word>
  ToddCoxeter(ToddCoxeter<Word> const&) -> ToddCoxeter<Word>;

  //
  template <typename Word>
  ToddCoxeter(ToddCoxeter<Word>&&) -> ToddCoxeter<Word>;

  template <typename Word>
  std::string to_human_readable_repr(ToddCoxeter<Word> const& tc);
}  // namespace libsemigroups
 
#include "todd-coxeter-class.tpp"
#endif  // LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_