cong-class.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-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 Congruence class template, for
// creating congruence over FroidurePin objects or over Presentation objects.
 
#ifndef LIBSEMIGROUPS_CONG_CLASS_HPP_
#define LIBSEMIGROUPS_CONG_CLASS_HPP_
 
#include <cstddef>      // for size_t
#include <cstdint>      // for uint64_t
#include <memory>       // for shared_ptr
#include <string>       // for string
#include <string_view>  // for string_view
#include <utility>      // for move
#include <vector>       // for vector
 
#include "knuth-bendix-class.hpp"  // for KnuthBendix
#include "presentation.hpp"        // for Presentation
#include "todd-coxeter-class.hpp"  // for ToddCoxeter
#include "types.hpp"               // for letter_type, wor...
#include "word-graph-helpers.hpp"  // for complete_no_checks
 
#include "detail/cong-common-class.hpp"  // for detail::CongruenceCommon
#include "detail/race.hpp"               // for Race
 
namespace libsemigroups {
  class FroidurePinBase;  // Forward declaration, constructor parameters
 
  template <typename Node>
  class WordGraph;







  template <typename Word>
  class Congruence : public detail::CongruenceCommon {
    enum class RunnerKind : size_t { TC = 0, KB = 1, K = 2 };

    // Congruence - data - private
 
    std::vector<Word>               _generating_pairs;
    Presentation<Word>              _presentation;
    mutable detail::Race            _race;
    mutable bool                    _runners_initted;
    mutable std::vector<RunnerKind> _runner_kinds;
 
    // Private init Congruence but not CongruenceCommon
    Congruence& init_no_base_classes();
 
   public:
    // Interface requirements - native-types

    using native_word_type = Word;

    // Congruence - constructors - public

    Congruence();

    Congruence& init();

    Congruence(Congruence const&);

    Congruence(Congruence&&);

    Congruence& operator=(Congruence const&);

    Congruence& operator=(Congruence&&);
 
    ~Congruence();

    // NOTE: No rvalue ref version because we anyway must copy p multiple times
    // TODO note no longer valid impl
    Congruence(congruence_kind knd, Presentation<Word> const& p)
        : Congruence() {
      init(knd, p);
    }

    // NOTE:  No rvalue ref version because we anyway must copy p multiple times
    // TODO note no longer valid impl
    Congruence& init(congruence_kind knd, Presentation<Word> const& p);

    // Congruence - interface requirements - add_generating_pair

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Congruence& add_generating_pair_no_checks(Iterator1 first1,
                                              Iterator2 last1,
                                              Iterator3 first2,
                                              Iterator4 last2) {
      LIBSEMIGROUPS_ASSERT(!any_runner_started());
      _runners_initted = false;
      _generating_pairs.emplace_back(first1, last1);
      _generating_pairs.emplace_back(first2, last2);
      return detail::CongruenceCommon::add_internal_generating_pair_no_checks<
          Congruence>(first1, last1, first2, last2);
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Congruence& add_generating_pair(Iterator1 first1,
                                    Iterator2 last1,
                                    Iterator3 first2,
                                    Iterator4 last2) {
      _runners_initted = false;
      if (any_runner_started()) {
        LIBSEMIGROUPS_EXCEPTION(
            "any_runner_started() returned \"true\" so no further "
            "generating pairs can be added at this stage");
      }
      return detail::CongruenceCommon::add_generating_pair<Congruence>(
          first1, last1, first2, last2);
    }

    // Congruence - interface requirements - number_of_classes

    [[nodiscard]] uint64_t number_of_classes();

    // Congruence - interface requirements - contains

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] tril currently_contains_no_checks(Iterator1 first1,
                                                    Iterator2 last1,
                                                    Iterator3 first2,
                                                    Iterator4 last2) const;

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] tril currently_contains(Iterator1 first1,
                                          Iterator2 last1,
                                          Iterator3 first2,
                                          Iterator4 last2) const {
      return detail::CongruenceCommon::currently_contains<Congruence>(
          first1, last1, first2, last2);
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] bool contains_no_checks(Iterator1 first1,
                                          Iterator2 last1,
                                          Iterator3 first2,
                                          Iterator4 last2) {
      return detail::CongruenceCommon::contains_no_checks<Congruence>(
          first1, last1, first2, last2);
    }

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] bool contains(Iterator1 first1,
                                Iterator2 last1,
                                Iterator3 first2,
                                Iterator4 last2) {
      return detail::CongruenceCommon::contains<Congruence>(
          first1, last1, first2, last2);
    }

    // Congruence - interface requirements - reduce

    template <typename OutputIterator, typename Iterator1, typename Iterator2>
    OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
                                           Iterator1      first,
                                           Iterator2      last) const;

    template <typename OutputIterator, typename Iterator1, typename Iterator2>
    OutputIterator reduce_no_run(OutputIterator d_first,
                                 Iterator1      first,
                                 Iterator2      last) const {
      return detail::CongruenceCommon::reduce_no_run<Congruence>(
          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<Congruence>(
          d_first, first, last);
    }

    template <typename OutputIterator,
              typename InputIterator1,
              typename InputIterator2>
    OutputIterator reduce(OutputIterator d_first,
                          InputIterator1 first,
                          InputIterator2 last) {
      return detail::CongruenceCommon::reduce<Congruence>(d_first, first, last);
    }

    // Congruence - interface requirements - throw_if_letter_not_in_alphabet

    template <typename Iterator1, typename Iterator2>
    void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;

    // Congruence - member functions - public

    template <typename Thing>
    std::shared_ptr<Thing> get() const;

    template <typename Thing>
    [[nodiscard]] bool has() const;

    [[nodiscard]] size_t max_threads() const noexcept {
      return _race.max_threads();
    }

    Congruence& max_threads(size_t val) noexcept {
      _race.max_threads(val);
      return *this;
    }

    [[nodiscard]] size_t number_of_runners() const noexcept {
      return _race.number_of_runners();
    }

    // NOTE: for Congruence objects it's possible that "any_runner_started" is
    // true but "started" is false ("started" is true if and only if "run_impl"
    // has been called at least once, but, e.g. is_obviously_infinite might
    // call Kambites::start but there's no call to Congruence::run_impl).
    [[nodiscard]] bool any_runner_started() const noexcept {
      return std::any_of(_race.begin(), _race.end(), [](auto const& r) {
        return r->started();
      });
    }

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

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

    [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
#endif
 
   private:
    // Congruence - member functions - private
 
    void add_runner(std::shared_ptr<ToddCoxeter<Word>>&& ptr) const {
      _race.add_runner(std::move(ptr));
      _runner_kinds.push_back(RunnerKind::TC);
    }
 
    void add_runner(std::shared_ptr<KnuthBendix<Word>>&& ptr) const {
      _race.add_runner(std::move(ptr));
      _runner_kinds.push_back(RunnerKind::KB);
    }
 
    void add_runner(std::shared_ptr<Kambites<Word>>&& ptr) const {
      _race.add_runner(std::move(ptr));
      _runner_kinds.push_back(RunnerKind::K);
    }
 
    template <typename Result, typename Node>
    friend auto to(congruence_kind        knd,
                   FroidurePinBase&       fpb,
                   WordGraph<Node> const& wg)
        -> std::enable_if_t<
            std::is_same_v<Congruence<typename Result::native_word_type>,
                           Result>,
            Result>;
 
    template <typename Result, typename Node>
    friend auto
    to(congruence_kind knd, WordGraph<Node> const& wg) -> std::enable_if_t<
        std::is_same_v<Congruence<typename Result::native_word_type>, Result>,
        Result>;
 
    void init_runners() const;

    // Runner - pure virtual member functions - private
 
    void run_impl() override;
    bool finished_impl() const override {
      return _race.finished();
    }
  };  // class Congruence

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

  // NOTE:there's no rvalue ref constructor, so it's possible this guide is
  // superfluous
  template <typename Word>
  Congruence(congruence_kind, Presentation<Word>&&) -> Congruence<Word>;

  template <typename Word>
  Congruence(Congruence<Word> const&) -> Congruence<Word>;

  template <typename Word>
  Congruence(Congruence<Word>&&) -> Congruence<Word>;

  template <typename Word>
  std::string to_human_readable_repr(Congruence<Word> const& c);
}  // namespace libsemigroups
 
#include "cong-class.tpp"
 
#endif  // LIBSEMIGROUPS_CONG_CLASS_HPP_