knuth-bendix-class.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2025 James D. Mitchell + Joseph Edwards
//
// 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 class template KnuthBendix which
// is really just a facade for detail::KnuthBendixImpl.
 
#ifndef LIBSEMIGROUPS_KNUTH_BENDIX_CLASS_HPP_
#define LIBSEMIGROUPS_KNUTH_BENDIX_CLASS_HPP_
 
#include <algorithm>  // for for_each
#include <utility>    // for move
#include <vector>     // for vector
 
#include "order.hpp"         // for ShortLexCompare
#include "presentation.hpp"  // for Presentation
 
#include "detail/citow.hpp"              // for citow
#include "detail/cong-common-class.hpp"  // for CongruenceCommon
#include "detail/knuth-bendix-impl.hpp"  // for KnuthBendixImpl
#include "detail/rewriters.hpp"          // for RewriteTrie
 
namespace libsemigroups {
  enum class congruence_kind;
  enum class tril;


  template <typename Word,
            typename Rewriter       = detail::RewriteTrie,
            typename ReductionOrder = ShortLexCompare>
  class KnuthBendix : public detail::KnuthBendixImpl<Rewriter, ReductionOrder> {
   private:
    using KnuthBendixImpl_ = detail::KnuthBendixImpl<Rewriter, ReductionOrder>;
 
    bool               _extra_letter_added;
    std::vector<Word>  _generating_pairs;
    Presentation<Word> _presentation;
 
    // defined in detail/kbe.hpp
    friend class ::libsemigroups::detail::KBE<KnuthBendix>;
 
   public:
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    struct options {
      enum class overlap {
        ABC = 0,
        AB_BC = 1,
        MAX_AB_BC = 2
      };
    };
#endif

    using native_word_type = Word;

    using rule_type = std::pair<Word, Word>;

    KnuthBendix();

    // TODO(1) to tpp file
    KnuthBendix& init() {
      _extra_letter_added = false;
      _generating_pairs.clear();
      _presentation.init();
      KnuthBendixImpl_::init();
      return *this;
    }

    KnuthBendix(KnuthBendix const& that);

    KnuthBendix(KnuthBendix&&);

    KnuthBendix& operator=(KnuthBendix const&);

    KnuthBendix& operator=(KnuthBendix&&);
 
    ~KnuthBendix();

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

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

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

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

    template <typename Iterator1, typename Iterator2>
    void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;
 
#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    [[nodiscard]] congruence_kind kind() const noexcept;

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

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

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

    // KnuthBendix - interface requirements - add_generating_pair

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

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

    // KnuthBendix - interface requirements - contains
 
    // TODO: contains_no_checks is implemented
    // and documented in KnuthBendixImpl
 
    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    tril currently_contains_no_checks(Iterator1 first1,
                                      Iterator2 last1,
                                      Iterator3 first2,
                                      Iterator4 last2) const {
      return KnuthBendixImpl_::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 CongruenceCommon version so that we perform bound checks
      // in KnuthBendix and not KnuthBendixImpl_
      return detail::CongruenceCommon::currently_contains<KnuthBendix>(
          first1, last1, first2, last2);
    }

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

    // KnuthBendix - 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 KnuthBendixImpl_::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_checks(OutputIterator d_first,
                                    InputIterator1 first,
                                    InputIterator2 last) {
      return KnuthBendixImpl_::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_no_run(OutputIterator d_first,
                                 InputIterator1 first,
                                 InputIterator2 last) const {
      // Call CongruenceCommon version so that we perform bound checks
      // in KnuthBendix and not KnuthBendixImpl_
      return detail::CongruenceCommon::reduce_no_run<KnuthBendix>(
          d_first, first, last);
    }

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

    // KnuthBendix specific stuff

    // TODO(1) should be const
    auto active_rules();

    std::vector<Word> gilman_graph_node_labels();
 
   private:
    void run_impl();
 
    [[nodiscard]] bool requires_extra_letter() const {
      return (!generating_pairs().empty()
              && detail::CongruenceCommon::kind() == congruence_kind::onesided);
    }
  };  // class KnuthBendix

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

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

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

  template <typename Word>
  KnuthBendix(KnuthBendix<Word>&&) -> KnuthBendix<Word>;
 
}  // namespace libsemigroups
 
#include "knuth-bendix-class.tpp"
#endif  // LIBSEMIGROUPS_KNUTH_BENDIX_CLASS_HPP_