todd-coxeter-helpers.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 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/>.
//
 
// This file contains the declarations of some helper functions for the
// ToddCoxeter<Word> class.
 
#ifndef LIBSEMIGROUPS_TODD_COXETER_HELPERS_HPP_
#define LIBSEMIGROUPS_TODD_COXETER_HELPERS_HPP_
 
#include <algorithm>         // for reverse
#include <chrono>            // for milliseconds
#include <cstring>           // for strlen, size_t
#include <initializer_list>  // for begin, end, initi...
#include <iterator>          // for back_inserter
#include <string>            // for basic_string, string
#include <type_traits>       // for is_integral_v
#include <utility>           // for move
#include <vector>            // for vector
 
#include "cong-common-helpers.hpp"  // for partition, add_ge...
#include "constants.hpp"            // for UNDEFINED, operat...
#include "exception.hpp"            // for LIBSEMIGROUPS_EXC...
#include "paths.hpp"                // for Paths
#include "presentation.hpp"         // for Presentation::val...
#include "ranges.hpp"               // for seq, operator|
#include "todd-coxeter-class.hpp"   // for ToddCoxeter
#include "types.hpp"                // for word_type, congru...
#include "word-graph.hpp"           // for follow_path_no_ch...
 
#include "detail/fmt.hpp"             // for format
#include "detail/path-iterators.hpp"  // for const_pilo_iterat...
 
namespace libsemigroups {
  namespace todd_coxeter {
    // ToddCoxeter<Word> helpers
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // This is just for our convenience here, so not documented.
    using index_type = typename detail::ToddCoxeterImpl::index_type;
#endif

 
    // TODO(1) this group is a bit hard to look at, it'd be better if all the
    // overloads of a given function were on one page, with a single bit of
    // documentation. This is because the overloads all do the same thing, and
    // so there's no real benefit in repeating the doc over and over again.

    // Possible future interface helpers - word -> index

    template <typename Word>
    [[nodiscard]] index_type
    current_index_of_no_checks(ToddCoxeter<Word> const& tc, Word const& w) {
      return tc.current_index_of_no_checks(std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] index_type current_index_of(ToddCoxeter<Word> const& tc,
                                              Word const&              w) {
      return tc.current_index_of(std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] index_type index_of_no_checks(ToddCoxeter<Word>& tc,
                                                Word const&        w) {
      return tc.index_of_no_checks(std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] index_type index_of(ToddCoxeter<Word>& tc, Word const& w) {
      return tc.index_of(std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] index_type
    current_index_of_no_checks(ToddCoxeter<Word>&                tc,
                               std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return tc.current_index_of_no_checks(std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] index_type
    current_index_of(ToddCoxeter<Word>&                tc,
                     std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return tc.current_index_of(std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] index_type
    index_of_no_checks(ToddCoxeter<Word>&                tc,
                       std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return tc.index_of_no_checks(std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] index_type index_of(ToddCoxeter<Word>&                tc,
                                      std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return tc.index_of(std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] inline index_type
    current_index_of_no_checks(ToddCoxeter<Word>& tc, char const* w) {
      LIBSEMIGROUPS_ASSERT(w != nullptr);
      return tc.current_index_of_no_checks(w, w + std::strlen(w));
    }

    template <typename Word>
    [[nodiscard]] inline index_type current_index_of(ToddCoxeter<Word>& tc,
                                                     char const*        w) {
      detail::throw_if_nullptr(w, "2nd");
      return tc.current_index_of(w, w + std::strlen(w));
    }

    template <typename Word>
    [[nodiscard]] inline index_type index_of_no_checks(ToddCoxeter<Word>& tc,
                                                       char const*        w) {
      LIBSEMIGROUPS_ASSERT(w != nullptr);
      return tc.index_of_no_checks(w, w + std::strlen(w));
    }

    template <typename Word>
    [[nodiscard]] inline index_type index_of(ToddCoxeter<Word>& tc,
                                             char const*        w) {
      detail::throw_if_nullptr(w, "2nd");
      return tc.index_of(w, w + std::strlen(w));
    }

    // Possible future interface helpers - index -> word

    template <typename Word>
    [[nodiscard]] Word current_word_of_no_checks(ToddCoxeter<Word>& tc,
                                                 index_type         i);

    template <typename Word>
    [[nodiscard]] Word current_word_of(ToddCoxeter<Word>& tc, index_type i);

    template <typename Word>
    [[nodiscard]] Word word_of_no_checks(ToddCoxeter<Word>& tc, index_type i);

    template <typename Word>
    [[nodiscard]] Word word_of(ToddCoxeter<Word>& tc, index_type i);

    // Possible future interface helpers - class_of

    // Can't out of line this because of auto return type
    template <typename Word>
    [[nodiscard]] auto class_by_index(ToddCoxeter<Word>& tc, index_type n) {
      size_t const offset = (tc.presentation().contains_empty_word() ? 0 : 1);
      tc.run();
      // We call run and then current_word_graph, because the word
      // graph does not need to be standardized for this to work.
      // TODO(1) again there are alots of copies here
      // TODO(1) this also has the disadvantage that we can't set the various
      // settings in the Paths object, in particular, the size_hint + count
      // functions!
      return Paths(tc.current_word_graph()).source(0).target(n + offset)
             | rx::transform([&tc](auto const& w) {
                 Word ww;
                 for (auto index : w) {
                   ww.push_back(tc.presentation().letter_no_checks(index));
                 }
                 return ww;
               });
    }

    // Can't out of line this because of auto return type
    template <typename Word>
    [[nodiscard]] auto class_by_index_no_checks(ToddCoxeter<Word>& tc,
                                                index_type         n) {
      size_t const offset = (tc.presentation().contains_empty_word() ? 0 : 1);
      tc.run();
      // We call run and then current_word_graph, because the word
      // graph does not need to be standardized for this to work.
      // TODO(1) again there are alots of copies here
      // TODO(1) this also has the disadvantage that we can't set the various
      // settings in the Paths object, in particular, the size_hint + count
      // functions!
      return Paths(tc.current_word_graph())
                 .source_no_checks(0)
                 .target_no_checks(n + offset)
             | rx::transform([&tc](auto const& w) {
                 Word ww;
                 for (auto index : w) {
                   ww.push_back(tc.presentation().letter_no_checks(index));
                 }
                 return ww;
               });
    }

    template <typename Word, typename Iterator1, typename Iterator2>
    [[nodiscard]] auto class_of(ToddCoxeter<Word>& tc,
                                Iterator1          first,
                                Iterator2          last) {
      return class_by_index(tc, tc.index_of(first, last));
    }

    template <typename Word, typename Iterator1, typename Iterator2>
    [[nodiscard]] auto class_of_no_checks(ToddCoxeter<Word>& tc,
                                          Iterator1          first,
                                          Iterator2          last) {
      return class_by_index_no_checks(tc, tc.index_of_no_checks(first, last));
    }

    template <typename Word>
    [[nodiscard]] auto class_of(ToddCoxeter<Word>& tc, Word const& w) {
      return class_of(tc, std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] auto class_of_no_checks(ToddCoxeter<Word>& tc,
                                          Word const&        w) {
      return class_of_no_checks(tc, std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] auto class_of(ToddCoxeter<Word>&                tc,
                                std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return class_of(tc, std::begin(w), std::end(w));
    }

    template <typename Word, typename Int>
    [[nodiscard]] auto class_of_no_checks(ToddCoxeter<Word>&                tc,
                                          std::initializer_list<Int> const& w) {
      static_assert(std::is_integral_v<Int>);
      return class_of_no_checks(tc, std::begin(w), std::end(w));
    }

    template <typename Word>
    [[nodiscard]] inline auto class_of_no_checks(ToddCoxeter<Word>& tc,
                                                 char const*        w) {
      LIBSEMIGROUPS_ASSERT(w != nullptr);
      return class_of_no_checks(tc, w, w + std::strlen(w));
    }

    template <typename Word>
    [[nodiscard]] auto class_of(ToddCoxeter<Word>& tc, char const* w) {
      detail::throw_if_nullptr(w, "2nd");
      LIBSEMIGROUPS_ASSERT(w != nullptr);
 
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wnonnull"
#endif
      return class_of(tc, w, w + std::strlen(w));
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic pop
#endif
    }

    // Possible future interface helpers - is_non_trivial

    [[nodiscard]] tril is_non_trivial(detail::ToddCoxeterImpl&  tc,
                                      size_t                    tries = 10,
                                      std::chrono::milliseconds try_for
                                      = std::chrono::milliseconds(100),
                                      float threshold = 0.99);

    // Possible future interface helpers - redundant_rule

    template <typename Word, typename Time>
    [[nodiscard]] typename std::vector<Word>::const_iterator
    redundant_rule(Presentation<Word> const& p, Time t);

 
  }  // namespace todd_coxeter
 
  // This namespace contains implementations of the interface helpers (i.e.
  // specific versions for ToddCoxeterImpl of the helper functions from
  // cong-common.hpp).
  namespace congruence_common {
    // Interface helpers - normal_forms

    template <typename Word>
    [[nodiscard]] auto normal_forms(ToddCoxeter<Word>& tc);

    // Interface helpers - partition

    // The following function is also declared in cong-common-helpers.hpp:
    template <typename Word, typename Range, typename>
    [[nodiscard]] std::vector<std::vector<Word>>
    partition(ToddCoxeter<Word>& tc, Range r);

    // Interface helpers - non_trivial_classes

    template <typename Word>
    [[nodiscard]] std::vector<std::vector<Word>>
    non_trivial_classes(ToddCoxeter<Word>& tc1, ToddCoxeter<Word>& tc2);
  }  // namespace congruence_common
 
  // The todd_coxeter namespace contains all helpers specific to
  // ToddCoxeter<Word> and aliases for the common functionality in the
  // congruence_common namespace.
  namespace todd_coxeter {
    // ToddCoxeter<Word> add_generating_pairs helpers
 
    using congruence_common::add_generating_pair;
    using congruence_common::add_generating_pair_no_checks;

    // Interface helpers - contains
 
    using congruence_common::contains;
    using congruence_common::contains_no_checks;
    using congruence_common::currently_contains;
    using congruence_common::currently_contains_no_checks;

    // Interface helpers - reduce[_no_run][_no_checks]
 
    using congruence_common::reduce;
    using congruence_common::reduce_no_checks;
    using congruence_common::reduce_no_run;
    using congruence_common::reduce_no_run_no_checks;

    // Interface helpers - partitioning and normal forms
 
    using congruence_common::non_trivial_classes;
    using congruence_common::normal_forms;
    using congruence_common::partition;
 
  }  // namespace todd_coxeter
}  // namespace libsemigroups
 
#include "todd-coxeter-helpers.tpp"
#endif  // LIBSEMIGROUPS_TODD_COXETER_HELPERS_HPP_