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 <utility>  // for move
#include <vector>   // for vector
 
#include "order.hpp"         // for ShortLexCompare
#include "presentation.hpp"  // for Presentation
 
#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>;
 
    std::vector<Word>  _generating_pairs;
    Presentation<Word> _presentation;
 
   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() {
      _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));
    }

    // TODO(0) remove this
    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);
    }
 
#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) {
      // Call detail::CongruenceCommon version so that we perform bound checks
      // in KnuthBendix and not KnuthBendixImpl
      return detail::CongruenceCommon::add_generating_pair<KnuthBendix>(
          first1, last1, first2, last2);
    }

    // KnuthBendix - interface requirements - contains
 
    // NOTE: contains_no_checks and currently_contains_no_checks are implemented
    // and documented in KnuthBendixImpl

    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
 
    // NOTE: reduce_no_checks and reduce_no_run_no_checks are implemented and
    // documented in KnuthBendixImpl

    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();
  };  // 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_