stephen.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2022-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/>.
//
 
#ifndef LIBSEMIGROUPS_STEPHEN_HPP_
#define LIBSEMIGROUPS_STEPHEN_HPP_
 
#include <array>    // for array
#include <cstddef>  // for size_t
#include <cstdint>  // for uint32_t
#include <memory>   // for shared_ptr
#include <string>   // for string
#include <tuple>    // for tie
#include <utility>  // for make_pair
#include <vector>   // for vector
 
#include "constants.hpp"     // for Max, UNDEFINED
#include "debug.hpp"         // for LIBSEMIGROUPS_ASSERT
#include "dot.hpp"           // for Dot
#include "exception.hpp"     // for LIBSEMIGROUPS_EXCEPTION
#include "paths.hpp"         // for Paths
#include "presentation.hpp"  // for Presentation
#include "runner.hpp"        // for Runner
#include "types.hpp"         // for word_type
#include "word-graph.hpp"    // for WordGraph
 
#include "detail/felsch-graph.hpp"             // for DoNotReg...
#include "detail/node-managed-graph.hpp"       // for NodeMana...
#include "detail/node-manager.hpp"             // for NodeManager
#include "detail/report.hpp"                   // for report_n...
#include "detail/string.hpp"                   // for group_di...
#include "detail/word-graph-with-sources.hpp"  // for WordGrap...
 
// TODO(2)
// * update so that run_for, run_until work properly (at present basically
//   run_impl starts again from scratch every time)
// * minimal rep (as per Reinis) (named normal_form?)
// * invert() - just swap the initial and accept states and re-standardize
// * idempotent() - just make the accept state = initial state.
// * class_of for inverse Stephen (i.e. all walks in the graph through all
// nodes) (not sure how to do this just yet). This is different than
// words_accepted see Corollary 3.2 in Stephen's "Presentations of inverse
// monoids" paper (not thesis).
// * canonical_form (as per Howie's book)

 
namespace libsemigroups {

  template <typename PresentationType>
  class Stephen : public Runner {
    template <typename Q>
    static constexpr bool is_valid_presentation() {
      return std::is_same_v<Q, Presentation<word_type>>
             || std::is_same_v<Q, InversePresentation<word_type>>;
      // TODO(2): uncomment when we figure out how to handle std::string
      // presentations
      //|| std::is_same_v<Q, Presentation<std::string>>
      //|| std::is_same_v<Q, InversePresentation<std::string>>;
    }
 
    // TODO (2): Change the error message once std::string presentations are
    // supported
    static_assert(is_valid_presentation<PresentationType>(),
                  "the template parameter PresentationType must be "
                  "Presentation<word_type> or InversePresentation<word_type>");
 
   public:
    using presentation_type = PresentationType;

    using word_graph_type = WordGraph<uint32_t>;
    using node_type = word_graph_type::node_type;
 
   private:
    class StephenGraph;  // forward decl
 
    // Data members
    node_type                         _accept_state;
    bool                              _finished;
    bool                              _is_word_set;
    std::shared_ptr<PresentationType> _presentation;
    word_type                         _word;
    StephenGraph                      _word_graph;
 
   public:
    Stephen();

    Stephen& init();
 
    // TODO(2): Implement make<Stephen> function which checks args
    // Should presentation::throw_if_not_normalized (until we separate the
    // implementation and external interface later on).
    // Should also throw if `p.throw_if_bad_alphabet_or_rules()` throws.
    // Should also throw if if `p.alphabet().size()` is `0`.

    // Not noexcept because allocated memory
    explicit Stephen(PresentationType const& p) : Stephen() {
      init(p);
    }

    explicit Stephen(PresentationType&& p) : Stephen() {
      init(std::move(p));
    }

    explicit Stephen(std::shared_ptr<PresentationType> const& ptr) : Stephen() {
      init(ptr);
    }

    Stephen(Stephen const& that) = default;

    Stephen(Stephen&&) = default;

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

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

    Stephen& init(PresentationType const& p) {
      return init(std::make_shared<PresentationType>(p));
    }

    Stephen& init(PresentationType&& p) {
      return init(std::make_shared<PresentationType>(std::move(p)));
    }

    Stephen& init(std::shared_ptr<PresentationType> const& ptr);

    presentation_type const& presentation() const noexcept {
      return *_presentation;
    }

    template <typename Iterator1, typename Iterator2>
    Stephen& set_word(Iterator1 first, Iterator2 last) {
      presentation().throw_if_letter_not_in_alphabet(first, last);
      return set_word_no_checks(first, last);
    }

    template <typename Iterator1, typename Iterator2>
    Stephen& set_word_no_checks(Iterator1 first, Iterator2 last);

    bool is_word_set() const noexcept {
      return _is_word_set;
    }

    word_type const& word() const {
      throw_if_not_ready();
      return _word;
    }

    word_graph_type const& word_graph() const {
      throw_if_not_ready();
      return _word_graph;
    }

    // Throws if run throws, also this is not in the helper namespace because
    // we cache the return value.
    node_type accept_state();

    static constexpr node_type initial_state() noexcept {
      return 0;
    }

    void operator*=(Stephen<PresentationType>& that);

    void append_no_checks(Stephen<PresentationType>& that);
 
   private:
    // Reporting
 
    void report_after_run() const;
    void report_before_run() const;
    void report_progress_from_thread() const;
 
    Stephen& init_after_presentation_set();
 
    void throw_if_presentation_empty(presentation_type const& p) const {
      if (p.alphabet().empty()) {
        LIBSEMIGROUPS_EXCEPTION("the presentation must not have 0 generators");
      }
    }
 
    void throw_if_not_ready() const;
 
    void init_word_graph_from_word_no_checks() {
      _word_graph.init(presentation());
      _word_graph.report_prefix("Stephen");
      _word_graph.complete_path(
          presentation(), 0, _word.cbegin(), _word.cend());
      // Here so we have accurate data when using to_human_readable_repr
      _word_graph.number_of_active_nodes(_word_graph.number_of_nodes_active());
    }
 
    void run_impl() override;
    void really_run_impl();
 
    bool finished_impl() const noexcept override {
      return _finished;
    }
 
    void standardize() {
      word_graph::standardize(_word_graph);
      _word_graph.induced_subgraph_no_checks(
          0, _word_graph.number_of_nodes_active());
    }
  };
 
  // Deduction guides
  // The following is not a mistake but intentional, if no presentation type is
  // explicitly used, then we use Presentation<word_type>.
  // Presentation<std::string> is not allowed.
  // TODO(2): allow for Presentation<std::string> by templating on Word (after
  // we separate implementation and interface)

  Stephen(Presentation<word_type> const&)->Stephen<Presentation<word_type>>;

  Stephen(Presentation<word_type>&)->Stephen<Presentation<word_type>>;

  Stephen(Presentation<word_type>&&)->Stephen<Presentation<word_type>>;

  Stephen(std::shared_ptr<Presentation<word_type>>&&)
      ->Stephen<Presentation<word_type>>;

  Stephen(InversePresentation<word_type> const&)
      ->Stephen<InversePresentation<word_type>>;

  Stephen(InversePresentation<word_type>&)
      ->Stephen<InversePresentation<word_type>>;

  Stephen(InversePresentation<word_type>&&)
      ->Stephen<InversePresentation<word_type>>;

  Stephen(std::shared_ptr<InversePresentation<word_type>>&&)
      ->Stephen<InversePresentation<word_type>>;
  // TODO(2): other shared_ptr guides?
 
}  // namespace libsemigroups
 
namespace libsemigroups {
  namespace stephen {

    template <typename PresentationType>
    bool accepts(Stephen<PresentationType>& s, word_type const& w);

    template <typename PresentationType>
    bool is_left_factor(Stephen<PresentationType>& s, word_type const& w);

    template <typename PresentationType>
    auto words_accepted(Stephen<PresentationType>& s) {
      s.run();
      Paths paths(s.word_graph());
      return paths.source(s.initial_state()).target(s.accept_state());
    }

    template <typename PresentationType>
    auto left_factors(Stephen<PresentationType>& s) {
      s.run();
      Paths paths(s.word_graph());
      return paths.source(s.initial_state());
    }

    // Not noexcept because number_of_paths isn't
    template <typename PresentationType>
    uint64_t number_of_words_accepted(Stephen<PresentationType>& s,
                                      size_t                     min = 0,
                                      size_t max = POSITIVE_INFINITY) {
      s.run();
      using node_type = typename Stephen<PresentationType>::node_type;
      return number_of_paths(
          s.word_graph(), node_type(0), s.accept_state(), min, max);
    }

    // Not noexcept because number_of_paths isn't
    template <typename PresentationType>
    uint64_t number_of_left_factors(Stephen<PresentationType>& s,
                                    size_t                     min = 0,
                                    size_t max = POSITIVE_INFINITY) {
      s.run();
      return number_of_paths(s.word_graph(), 0, min, max);
    }

    template <typename PresentationType>
    Dot dot(Stephen<PresentationType>& s);

    // things?
    template <typename PresentationType>
    Stephen<PresentationType>& set_word(Stephen<PresentationType>& s,
                                        word_type const&           w) {
      return s.set_word(w.cbegin(), w.cend());
    }

    template <typename PresentationType>
    Stephen<PresentationType>& set_word_no_checks(Stephen<PresentationType>& s,
                                                  word_type const& w) {
      return s.set_word_no_checks(w.cbegin(), w.cend());
    }
 
  }  // namespace stephen

  template <typename PresentationType>
  bool operator==(Stephen<PresentationType> const& x,
                  Stephen<PresentationType> const& y) {
    if (x.presentation() != y.presentation()) {
      LIBSEMIGROUPS_EXCEPTION(
          "x.presentation() must equal y.presentation() when comparing "
          "Stephen instances")
    }
    return equal_to_no_checks(x, y);
  }

  template <typename PresentationType>
  bool equal_to_no_checks(Stephen<PresentationType> const& x,
                          Stephen<PresentationType> const& y) {
    return stephen::accepts(const_cast<Stephen<PresentationType>&>(x), y.word())
           && stephen::accepts(const_cast<Stephen<PresentationType>&>(y),
                               x.word());
  }

  template <typename PresentationType>
  [[nodiscard]] std::string
  to_human_readable_repr(Stephen<PresentationType> const& x);
}  // namespace libsemigroups
 
#include "stephen.tpp"
 
#endif  // LIBSEMIGROUPS_STEPHEN_HPP_