kambites-class.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021-2025 James D. Mitchell + Maria Tsalakou
//
// 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 Kambites class implementing the
// algorithm described in:
//
// Kambites, M. (2009). Small overlap monoids. I. The word problem. J. Algebra,
// 321(8), 2187–2205.
//
// for solving the word problem in small overlap monoids, and a novel algorithm
// for computing normal forms in small overlap monoids, by Maria Tsalakou.
 
#ifndef LIBSEMIGROUPS_KAMBITES_CLASS_HPP_
#define LIBSEMIGROUPS_KAMBITES_CLASS_HPP_
 
#include <algorithm>         // for equal, move, copy, min
#include <cstddef>           // for size_t
#include <cstdint>           // for uint64_t
#include <functional>        // for swap
#include <initializer_list>  // for begin, end
#include <string>            // for basic_string, string, swap
#include <tuple>             // for get, tie, swap, tuple
#include <type_traits>       // for is_same_v, conditional_t
#include <unordered_map>     // for swap, unordered_map
#include <utility>           // for get, move, swap, make_pair
#include <vector>            // for vector, swap
 
#include "constants.hpp"        // for UNDEFINED, operator==
#include "debug.hpp"            // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"        // for LIBSEMIGROUPS_EXCEPTION
#include "order.hpp"            // for lexicographical_compare
#include "presentation.hpp"     // for operator!=, Presentation
#include "to-presentation.hpp"  // for to<Presentation>
#include "types.hpp"            // for tril, congruence_kind
#include "ukkonen.hpp"          // for maximal_piece_prefix_no...
#include "word-range.hpp"       // for operator+=, operator+
 
#include "detail/cong-common-class.hpp"  // for detail::CongruenceCommon
#include "detail/fmt.hpp"                // for format
#include "detail/multi-string-view.hpp"  // for MultiStringView, is_prefix
#include "detail/string.hpp"             // for is_prefix, maximum_comm...
#include "detail/uf.hpp"                 // for Duf
 
namespace libsemigroups {






  // TODO(1) example
  template <typename Word = detail::MultiStringView>
  class Kambites : public detail::CongruenceCommon {
   public:
    // Kambites - aliases - public

    using native_word_type
        = std::conditional_t<std::is_same_v<Word, detail::MultiStringView>,
                             std::string,
                             Word>;
 
   private:
    using internal_type = Word;

    // Kambites - inner classes - private
 
    // Data structure for caching the regularly accessed parts of the
    // relation words.
    struct RelationWords;
 
    // Data structure for caching the complements of each relation word.
    //
    // We say that a relation word u' is a *complement* of a relation word u
    // if there are relation words u = r_1,r_2, ..., r_n = u'$ such that
    // either (r_i,r_{i+1}) \in R or (r_{i+1},r_i) \in R for $1 \leq i \leq
    // n$. We say that $u'$ is a *proper complement* of the relation word u
    // if it is a complement of u and u is not equal to u'.
    class Complements;

    // Kambites - data members - private
 
    mutable size_t                     _class;
    mutable Complements                _complements;
    mutable bool                       _have_class;
    mutable std::vector<RelationWords> _XYZ_data;
    mutable native_word_type           _tmp_value1, _tmp_value2;
 
    std::vector<native_word_type>  _generating_pairs;
    Presentation<native_word_type> _presentation;
    Ukkonen                        _suffix_tree;
 
    using internal_type_iterator = typename internal_type::const_iterator;
 
    void throw_if_1_sided(congruence_kind knd) const;
 
   public:
    // Kambites - Constructors, destructor, initialisation - public

    Kambites();

    Kambites& init();

    Kambites(Kambites const&);

    Kambites(Kambites&&);

    Kambites& operator=(Kambites const&);

    Kambites& operator=(Kambites&&);
 
    ~Kambites();

    //! \ref congruence_kind::twosided.
    Kambites(congruence_kind knd, Presentation<native_word_type> const& p)
        // call the rval ref constructor
        : Kambites(knd, Presentation<native_word_type>(p)) {}

    //! \ref congruence_kind::twosided.
    Kambites& init(congruence_kind                       knd,
                   Presentation<native_word_type> const& p) {
      // call the rval ref init
      return init(knd, Presentation<native_word_type>(p));
    }

    //! const&)
    Kambites(congruence_kind knd, Presentation<native_word_type>&& p)
        : Kambites() {
      init(knd, std::move(p));
    }

    Kambites& init(congruence_kind knd, Presentation<native_word_type>&& p);

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

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

    // Interface requirements - add_pairs

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Kambites& add_generating_pair_no_checks(Iterator1 first1,
                                            Iterator2 last1,
                                            Iterator3 first2,
                                            Iterator4 last2);
    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    Kambites& add_generating_pair(Iterator1 first1,
                                  Iterator2 last1,
                                  Iterator3 first2,
                                  Iterator4 last2) {
      return detail::CongruenceCommon::add_generating_pair<Kambites>(
          first1, last1, first2, last2);
    }

    // Interface requirements - number_of_classes

    // Not noexcept, throws
    [[nodiscard]] uint64_t number_of_classes() {
      throw_if_not_C4();
      return POSITIVE_INFINITY;
    }

    // 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;
    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<Kambites>(
          first1, last1, first2, last2);
    }

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

    // Interface requirements - reduce
 
   private:
    void normal_form_no_checks(native_word_type&       result,
                               native_word_type const& w) const;
 
   public:
    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<Kambites>(
          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<Kambites>(
          d_first, first, last);
    }

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

    // Kambites - member functions - public

    // not noexcept because number_of_pieces_no_checks isn't
    [[nodiscard]] size_t small_overlap_class();

    [[nodiscard]] size_t small_overlap_class() const noexcept;

    //! \noexcept
    [[nodiscard]] auto const& ukkonen() noexcept {
      run();
      return _suffix_tree;
    }

    // Kambites - validation functions - public

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

    void throw_if_not_C4();

    void throw_if_not_C4() const;

    //! at least \f$4\f$.
    [[nodiscard]] bool success() const override {
      return finished() && _class >= 4;
    }
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    [[nodiscard]] congruence_kind kind() const noexcept;

    [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
#endif
 
   private:
    // Kambites - XYZ functions - private
 
    void really_init_XYZ_data(size_t i) const;
 
    // init_XYZ_data is split into the function that really does the work
    // (really_init_XYZ_data) which is called once, and init_XYZ_data which
    // can be called very often.
    // Intentionally inlined, do not move to tpp file.
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Winline"
#endif
    inline void init_XYZ_data(size_t i) const {
      LIBSEMIGROUPS_ASSERT(i < _presentation.rules.size());
      if (_XYZ_data.empty()) {
        _XYZ_data.resize(_presentation.rules.size());
      }
      if (!_XYZ_data[i].is_initialized) {
        really_init_XYZ_data(i);
      }
    }
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
    [[nodiscard]] internal_type const& X(size_t i) const;
    [[nodiscard]] internal_type const& Y(size_t i) const;
    [[nodiscard]] internal_type const& Z(size_t i) const;
    [[nodiscard]] internal_type const& XY(size_t i) const;
    [[nodiscard]] internal_type const& YZ(size_t i) const;
    [[nodiscard]] internal_type const& XYZ(size_t i) const;

    // Kambites - helpers - private
 
    // Returns the index of the relation word r_i = X_iY_iZ_i if [first,
    // last) = X_iY_iw for some w. If no such exists, then UNDEFINED is
    // returned.
    // Not noexcept because is_prefix isn't
    [[nodiscard]] size_t
    relation_prefix(internal_type_iterator const& first,
                    internal_type_iterator const& last) const;
 
    // Returns the index of the relation word r_i = X_iY_iZ_i such that
    // X_iY_i is a clean overlap prefix of <s>, i.e. <s> = X_iY_iw for some
    // w, and there's no factor of <s> of the form X_jY_j starting before
    // the beginning of Y_i. If no such exists, UNDEFINED is returned. Not
    // noexcept because relation_prefix isn't
    [[nodiscard]] inline size_t
    clean_overlap_prefix(internal_type const& s) const {
      return clean_overlap_prefix(s.cbegin(), s.cend());
    }
 
    [[nodiscard]] size_t
    clean_overlap_prefix(internal_type_iterator const& first,
                         internal_type_iterator const& last) const;
 
    // Calls clean_overlap_prefix on every suffix of <s> starting within the
    // range [0, n), and returns a std::pair p where:
    //
    // * <p.first> is the starting index of the suffix of <s> that contains
    // a clean_overlap_prefix.
    //
    // * <p.second> is the index of the relation word that's a clear overlap
    //   prefix of a suffix of <s>
    [[nodiscard]] std::pair<size_t, size_t>
    clean_overlap_prefix_mod(internal_type const& s, size_t n) const;
 
    // If x + [first, last) = aX_sY_sw words a, w and for some index s,
    // where X_s = X_s'X_s'', x = aX_s', and [first, last) = X_s''Y_sw, then
    // this function returns a tuple <Word> where:
    //
    // 1. std::get<0>(Word) is the index <s>
    //
    // 2. std::get<1>(Word) is an iterator <it1> into <x>, such that
    //    [it1, x.cend()) = X_s'
    //
    // 3. std::get<2>(Word) is an iterator <it2> into [first, last), such
    //    that [it2, last) = w
    //
    // If no such relation word exists, then
    //
    //    (UNDEFINED, first.cend(), second.cend())
    //
    // is returned.
    //
    // Not noexcept because relation_prefix isn't
    [[nodiscard]] std::
        tuple<size_t, internal_type_iterator, internal_type_iterator>
        p_active(internal_type const&          x,
                 internal_type_iterator const& first,
                 internal_type_iterator const& last) const;
 
    // Returns a word equal to w in this, starting with the piece p, no
    // checks are performed. Used in the normal_form function. Not noexcept
    // because detail::is_prefix isn't
    void replace_prefix(internal_type& w, internal_type const& p) const;

    // Kambites - complement helpers - private
 
    // Returns j among the complements of i such that [first,
    // last) is a prefix of X_jY_jZ_j, and UNDEFINED otherwise.
    [[nodiscard]] size_t
    prefix_of_complement(size_t                        i,
                         internal_type_iterator const& first,
                         internal_type_iterator const& last) const;
 
    // Helper for the above
    [[nodiscard]] size_t prefix_of_complement(size_t               i,
                                              internal_type const& w) const {
      return prefix_of_complement(i, w.cbegin(), w.cend());
    }
 
    // Returns the index j of a complement of X_iY_iZ_i such that X_jY_j is
    // a prefix of w. Otherwise, UNDEFINED is returned.
    [[nodiscard]] size_t complementary_XY_prefix(size_t               i,
                                                 internal_type const& w) const;
 
    // Returns j such that w is Z_j-active for some Z_j in the
    // complements of Z_i.  Otherwise it returns UNDEFINED.
    //
    // See also: p_active.
    [[nodiscard]] size_t Z_active_complement(size_t               i,
                                             internal_type const& w) const;
 
    // Returns j such that w is Z_j-active for some Z_j in the
    // proper (j != i) complements of Z_i.  Otherwise it returns UNDEFINED.
    [[nodiscard]] size_t
    Z_active_proper_complement(size_t i, internal_type const& w) const;
 
    [[nodiscard]] size_t
    Z_active_proper_complement(size_t                        i,
                               internal_type_iterator const& first,
                               internal_type_iterator const& last) const;

    // Kambites - static functions - private
 
    [[nodiscard]] static size_t complementary_relation_word(size_t i) {
      return (i % 2 == 0 ? i + 1 : i - 1);
    }
 
    template <typename native_word_type>
    static void pop_front(native_word_type& x) {
      x.erase(x.begin());
    }
 
    static void pop_front(detail::MultiStringView& x) {
      x.pop_front();
    }
 
    template <typename Iterator>
    static void append(std::string& w, Iterator first, Iterator last) {
      w.append(first, last);
    }
 
    template <typename Iterator>
    static void append(detail::MultiStringView& w,
                       Iterator                 first,
                       Iterator                 last) {
      w.append(first, last);
    }
 
    template <typename Iterator>
    static void append(word_type& w, Iterator first, Iterator last) {
      w.insert(w.end(), first, last);
    }

    // Kambites - main functions - private
 
    // copies u, v, and/or p if they are an rrvalue ref or a const ref.
 
    // Implementation of the function of the same name in: Kambites, M.
    // (2009). Small overlap monoids. I. The word problem. J. Algebra,
    // 321(8), 2187–2205.
    //
    // Returns true if u and v represent the same element of the fp
    // semigroup represented by this, and p is a possible prefix of u, and
    // v.
    //
    // Parameters are given by value because they are modified by wp_prefix,
    // and it was too difficult to untangle the different cases (when u, v
    // are equal, not equal, references, rvalue references etc). It's
    // possible that it could be modified to only copy when necessary, but
    // this doesn't seem worth it at present.
    [[nodiscard]] bool wp_prefix(internal_type u,
                                 internal_type v,
                                 internal_type p) const;
 
    // Implementational detail
    // Not noexcept because nothing else is and lots allocations
    void normal_form_inner(size_t& r, internal_type& v, internal_type& w) const;

    // Runner - pure virtual member functions - private
 
    void run_impl() override;
 
    bool finished_impl() const override {
      return _have_class;
    }
  };  // class Kambites

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

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

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

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

  template <typename Word>
  std::string to_human_readable_repr(Kambites<Word> const& k);
 
}  // namespace libsemigroups
 
#include "kambites-class.tpp"
 
#endif  // LIBSEMIGROUPS_KAMBITES_CLASS_HPP_