cong-common-helpers.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2024-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 helper functions for the derived classes of
// detail::CongruenceCommon. This is a separate file so that we can declare all
// the derived classes of detail::CongruenceCommon prior to declaring the
// functions in this file.
//
// The implementation of all helpers must go into the namespace
// congruence_common, and then be aliased into the, e.g., todd_coxeter
// namespace. This makes it possible to generically use, e.g.,
// congruence_common::normal_forms in, e.g., the python bindings.
 
#ifndef LIBSEMIGROUPS_CONG_COMMON_HELPERS_HPP_
#define LIBSEMIGROUPS_CONG_COMMON_HELPERS_HPP_
 
#include <algorithm>         // for remove_if
#include <cstring>           // for strlen, size_t
#include <initializer_list>  // for initializer_list, begin, end
#include <iterator>          // for begin, end, back_inserter
#include <string>            // for string
#include <string_view>       // for basic_string_view, string_view
#include <type_traits>       // for is_base_of_v, decay_t, is_same_v
#include <unordered_map>     // for unordered_map
#include <vector>            // for vector
 
#include "exception.hpp"             // for LIBSEMIGROUPS_EXCEPTION
#include "is_specialization_of.hpp"  // for is_specialization_of
#include "ranges.hpp"                // for is_input_or_sink_v, iterator_...
 
#include "detail/string.hpp"  // for throw_if_nullptr
 
namespace libsemigroups {
 
  // Forward decls
  template <typename Word>
  class Congruence;
 
  template <typename Word>
  class ToddCoxeter;
 
  enum class tril;
 
  namespace detail {
    class ToddCoxeterImpl;
    class CongruenceCommon;
  }  // namespace detail
 
  namespace congruence_common {


    // Interface helpers - add_generating_pair


    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    void
    add_generating_pair_no_checks(Thing&                                  thing,
                                  typename Thing::native_word_type const& u,
                                  typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      thing.add_generating_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    void add_generating_pair_no_checks(Thing&                            thing,
                                       std::initializer_list<Int> const& u,
                                       std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      thing.add_generating_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing>
    void add_generating_pair_no_checks(Thing&      thing,
                                       char const* u,
                                       char const* v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      LIBSEMIGROUPS_ASSERT(u != nullptr);
      LIBSEMIGROUPS_ASSERT(v != nullptr);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      thing.add_generating_pair_no_checks(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of
    // the same type but both convertible to string_view
    template <typename Thing>
    void add_generating_pair_no_checks(Thing&           thing,
                                       std::string_view u,
                                       std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      thing.add_generating_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    void add_generating_pair(Thing&                                  thing,
                             typename Thing::native_word_type const& u,
                             typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      thing.add_generating_pair(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    void add_generating_pair(Thing&                            thing,
                             std::initializer_list<Int> const& u,
                             std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      thing.add_generating_pair(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing>
    void add_generating_pair(Thing& thing, char const* u, char const* v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      detail::throw_if_nullptr(u, "2nd");
      detail::throw_if_nullptr(v, "3rd");
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      thing.add_generating_pair(u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of
    // the same type but both convertible to string_view
    template <typename Thing>
    void add_generating_pair(Thing&           thing,
                             std::string_view u,
                             std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      thing.add_generating_pair_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }


    // Interface helpers - currently_contains_no_checks


    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] tril
    currently_contains_no_checks(Thing const&                            thing,
                                 typename Thing::native_word_type const& u,
                                 typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      return thing.currently_contains_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    [[nodiscard]] tril
    currently_contains_no_checks(Thing const&                      thing,
                                 std::initializer_list<Int> const& u,
                                 std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      return thing.currently_contains_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing>
    [[nodiscard]] tril currently_contains_no_checks(Thing const& thing,
                                                    char const*  u,
                                                    char const*  v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      LIBSEMIGROUPS_ASSERT(u != nullptr);
      LIBSEMIGROUPS_ASSERT(v != nullptr);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.currently_contains_no_checks(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }

    // NOTE: This version of the function catches the cases when u & v are not
    // of the same type but both convertible to string_view
    template <typename Thing>
    [[nodiscard]] tril currently_contains_no_checks(Thing const&     thing,
                                                    std::string_view u,
                                                    std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.currently_contains_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    // Interface helpers - currently_contains

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] tril
    currently_contains(Thing const&                            thing,
                       typename Thing::native_word_type const& u,
                       typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      return thing.currently_contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    [[nodiscard]] tril currently_contains(Thing const& thing,
                                          std::initializer_list<Int> const& u,
                                          std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      return thing.currently_contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing>
    [[nodiscard]] tril currently_contains(Thing const& thing,
                                          char const*  u,
                                          char const*  v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      detail::throw_if_nullptr(u, "2nd");
      detail::throw_if_nullptr(v, "3rd");
      return thing.currently_contains(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of
    // the same type but both convertible to string_view
    template <typename Thing>
    [[nodiscard]] tril currently_contains(Thing const&     thing,
                                          std::string_view u,
                                          std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      return thing.currently_contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    // Interface helpers - contains_no_checks

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] bool
    contains_no_checks(Thing&                                  thing,
                       typename Thing::native_word_type const& u,
                       typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      return thing.contains_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    [[nodiscard]] bool contains_no_checks(Thing& thing,
                                          std::initializer_list<Int> const& u,
                                          std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      return contains_no_checks<Thing, std::initializer_list<Int>>(thing, u, v);
    }

    template <typename Thing>
    [[nodiscard]] bool contains_no_checks(Thing&      thing,
                                          char const* u,
                                          char const* v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      LIBSEMIGROUPS_ASSERT(u != nullptr);
      LIBSEMIGROUPS_ASSERT(v != nullptr);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.contains_no_checks(
          u, u + std::strlen(u), v, v + std::strlen(v));
    }
 
    // This version of the function catches the cases when u & v are not of
    // the same type but both convertible to string_view
    template <typename Thing>
    [[nodiscard]] bool contains_no_checks(Thing&           thing,
                                          std::string_view u,
                                          std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.contains_no_checks(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    // Interface helpers - contains

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] bool contains(Thing&                                  thing,
                                typename Thing::native_word_type const& u,
                                typename Thing::native_word_type const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      return thing.contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing, typename Int>
    [[nodiscard]] bool contains(Thing&                            thing,
                                std::initializer_list<Int> const& u,
                                std::initializer_list<Int> const& v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      static_assert(std::is_integral_v<Int>);
      return thing.contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }
 
    // This version of the function catches the cases when u & v are not of
    // the same type but both convertible to string_view
    template <typename Thing>
    [[nodiscard]] bool contains(Thing&           thing,
                                std::string_view u,
                                std::string_view v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.contains(
          std::begin(u), std::end(u), std::begin(v), std::end(v));
    }

    template <typename Thing>
    [[nodiscard]] bool contains(Thing& thing, char const* u, char const* v) {
      static_assert(std::is_base_of_v<detail::CongruenceCommon, Thing>);
      detail::throw_if_nullptr(u, "2nd");
      detail::throw_if_nullptr(v, "3rd");
      // We could static_assert that Thing::native_word_type == std::string,
      // but it doesn't seem that adding this restriction would gain us
      // anything, so it is not currently done.
      return thing.contains(u, u + std::strlen(u), v, v + std::strlen(v));
    }


    // Interface helpers - reduce_no_run_no_checks


    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run_no_checks(Thing const&                            thing,
                            typename Thing::native_word_type const& w);
 
    // No string_view version is required because there is only a single
    // "word" parameter, and so the first template will catch every case
    // except initializer_list and char const*

    template <typename Thing, typename Int>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run_no_checks(Thing const&                      thing,
                            std::initializer_list<Int> const& w);

    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run_no_checks(Thing const& thing, char const* w);

    // Interface helpers - reduce_no_run

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run(Thing const&                            thing,
                  typename Thing::native_word_type const& w);
 
    // No string_view version is required because there is only a single
    // "w" parameter, and so the first template will catch every case
    // except initializer_list and char const*

    template <typename Thing, typename Int>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run(Thing const& thing, std::initializer_list<Int> const& w);

    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_run(Thing const& thing, char const* w);

    // Interface helpers - reduce_no_checks

    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_checks(Thing const&                            thing,
                     typename Thing::native_word_type const& w);
 
    // No string_view version is required because there is only a single
    // "word" parameter, and so the first template will catch every case
    // except initializer_list and char const*

    template <typename Thing, typename Int>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_checks(Thing const& thing, std::initializer_list<Int> const& w);

    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce_no_checks(Thing const& thing, char const* w);

    // Interface helpers - reduce
    // NOTE: we use native_word_type and not another template param to avoid
    // unexpected behaviour, if for example we add words which are strings to a
    // ToddCoxeter<word_type>, then unexpected things might happen.
    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type
    reduce(Thing const& thing, typename Thing::native_word_type const& w);
 
    // No string_view version is required because there is only a single
    // "word" parameter, and so the first template will catch every case
    // except initializer_list and char const*

    template <typename Thing, typename Int>
    [[nodiscard]] typename Thing::native_word_type
    reduce(Thing const& thing, std::initializer_list<Int> const& w);

    template <typename Thing>
    [[nodiscard]] typename Thing::native_word_type reduce(Thing const& thing,
                                                          char const*  w);


    // Interface helpers - normal_forms
 
    // There's nothing in common to implement in this file.

    // Interface helpers - partition

 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // Forward decls defined in todd-coxeter-helpers.tpp and cong-helpers.tpp
    template <typename Word,
              typename Range,
              typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
    [[nodiscard]] std::vector<std::vector<Word>>
    partition(ToddCoxeter<Word>& thing, Range r);
 
    template <typename Word,
              typename Range,
              typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
    [[nodiscard]] std::vector<std::vector<Word>>
    partition(Congruence<Word>& thing, Range r);
#endif

    template <typename Thing,
              typename Range,
              typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
    [[nodiscard]] std::vector<std::vector<typename Thing::native_word_type>>
    partition(Thing& thing, Range r);

    template <typename Thing, typename Iterator1, typename Iterator2>
    std::vector<std::vector<typename Thing::native_word_type>>
    partition(Thing& thing, Iterator1 first, Iterator2 last) {
      // static asserts are in done in the next call to partition
      return partition(thing, rx::iterator_range(first, last));
    }

    // Interface helpers - non_trivial_classes

    template <typename Thing,
              typename Range,
              typename = std::enable_if_t<rx::is_input_or_sink_v<Range>>>
    [[nodiscard]] std::vector<std::vector<typename Thing::native_word_type>>
    non_trivial_classes(Thing& thing, Range r);

    template <typename Thing, typename Iterator1, typename Iterator2>
    std::vector<std::vector<typename Thing::native_word_type>>
    non_trivial_classes(Thing& thing, Iterator1 first, Iterator2 last) {
      return non_trivial_classes(thing, rx::iterator_range(first, last));
    }

  }  // namespace congruence_common
}  // namespace libsemigroups
 
#include "cong-common-helpers.tpp"
 
#endif  // LIBSEMIGROUPS_CONG_COMMON_HELPERS_HPP_