froidure-pin-base.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2019-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/>.
//
 
#ifndef LIBSEMIGROUPS_FROIDURE_PIN_BASE_HPP_
#define LIBSEMIGROUPS_FROIDURE_PIN_BASE_HPP_
 
#include <array>             // for array
#include <cstddef>           // for size_t
#include <cstdint>           // for uint32_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for forward_iterator_tag
#include <utility>           // for swap
#include <vector>            // for vector, allocator
 
#include "constants.hpp"   // for UNDEFINED
#include "ranges.hpp"      // for iterator_range
#include "runner.hpp"      // for Runner
#include "types.hpp"       // for word_type, generator_index_type, tril
#include "word-graph.hpp"  // for WordGraph
 
#include "detail/containers.hpp"  // for DynamicArray2
 
namespace libsemigroups {


  class FroidurePinBase : public Runner {
    template <typename Element, typename Traits>
    friend class FroidurePin;
 
   public:
    // It should be possible to change this type and everything will just work,
    // provided the size of the semigroup is less than the maximum value of
    // this type of integer.
    using size_type = uint32_t;

    using generator_index_type = size_type;

    using element_index_type = size_type;

    using cayley_graph_type = WordGraph<element_index_type>;
 
   private:
    // See comments in FroidurePin
    using enumerate_index_type = size_type;

    // FroidurePin - data members - private
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // This now only contains a single data member, which might make it a bit
    // redundant.
    struct Settings {
      Settings() noexcept : _batch_size(8'192) {}
      Settings(Settings const&) noexcept            = default;
      Settings(Settings&&) noexcept                 = default;
      Settings& operator=(Settings const&) noexcept = default;
      Settings& operator=(Settings&&) noexcept      = default;
      ~Settings()                                   = default;
 
      size_t _batch_size;
    } _settings;
#endif
 
    size_t _degree;
    std::vector<std::pair<generator_index_type, generator_index_type>>
                                      _duplicate_gens;
    std::vector<element_index_type>   _enumerate_order;
    std::vector<generator_index_type> _final;
    std::vector<generator_index_type> _first;
    bool                              _found_one;
    bool                              _idempotents_found;
    std::vector<int>                  _is_idempotent;
    cayley_graph_type                 _left;
    std::vector<size_type>            _length;
    std::vector<enumerate_index_type> _lenindex;
    std::vector<element_index_type>   _letter_to_pos;
    size_type                         _nr;
    size_t                            _nr_products;
    size_t                            _nr_rules;
    enumerate_index_type              _pos;
    element_index_type                _pos_one;
    std::vector<element_index_type>   _prefix;
    detail::DynamicArray2<bool>       _reduced;
    cayley_graph_type                 _right;
    std::vector<element_index_type>   _suffix;
    size_t                            _wordlen;
 
   public:
    // FroidurePinBase - constructors - public

    FroidurePinBase();

    FroidurePinBase& init();

    FroidurePinBase(FroidurePinBase const& S);

    FroidurePinBase(FroidurePinBase&& other) = default;

    FroidurePinBase& operator=(FroidurePinBase const&);

    FroidurePinBase& operator=(FroidurePinBase&&) = default;
 
    virtual ~FroidurePinBase();

    // FroidurePinBase - settings - public

    FroidurePinBase& batch_size(size_t batch_size) noexcept {
      _settings._batch_size = batch_size;
      return *this;
    }

    [[nodiscard]] size_t batch_size() const noexcept {
      return _settings._batch_size;
    }
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // FroidurePinBase - pure virtual member functions - public
 
    [[nodiscard]] virtual size_t number_of_generators() const = 0;
    [[nodiscard]] virtual tril   is_finite() const            = 0;
 
#endif  // LIBSEMIGROUPS_PARSED_BY_DOXYGEN not defined

    // FroidurePinBase - member functions - public

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] element_index_type
    current_position_no_checks(Iterator1 first, Iterator2 last) const;

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] element_index_type current_position(Iterator1 first,
                                                      Iterator2 last) const {
      throw_if_any_generator_index_out_of_range(first, last);
      return current_position_no_checks(first, last);
    }

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] element_index_type position_no_checks(Iterator1 first,
                                                        Iterator2 last) {
      run();
      return current_position_no_checks(first, last);
    }

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] element_index_type position(Iterator1 first, Iterator2 last) {
      run();
      return current_position(first, last);
    }

    [[nodiscard]] element_index_type
    position_of_generator_no_checks(generator_index_type i) const {
      LIBSEMIGROUPS_ASSERT(i < _letter_to_pos.size());
      return _letter_to_pos[i];
    }

    [[nodiscard]] element_index_type
    position_of_generator(generator_index_type i) const {
      throw_if_generator_index_out_of_range(i);
      return position_of_generator_no_checks(i);
    }

    [[nodiscard]] size_t current_max_word_length() const noexcept {
      return _length[_enumerate_order.back()];
    }

    [[nodiscard]] size_t degree() const noexcept {
      return _degree;
    }

    [[nodiscard]] size_t current_size() const noexcept {
      return _nr;
    }

    [[nodiscard]] size_t current_number_of_rules() const noexcept {
      return _nr_rules;
    }

    element_index_type prefix_no_checks(element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _prefix.size());
      return _prefix[pos];
    }

    element_index_type prefix(element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      return prefix_no_checks(pos);
    }

    [[nodiscard]] element_index_type
    suffix_no_checks(element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _suffix.size());
      return _suffix[pos];
    }

    [[nodiscard]] element_index_type suffix(element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      return suffix_no_checks(pos);
    }

    [[nodiscard]] generator_index_type
    first_letter_no_checks(element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _first.size());
      return _first[pos];
    }

    [[nodiscard]] generator_index_type
    first_letter(element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      return first_letter_no_checks(pos);
    }

    [[nodiscard]] generator_index_type
    final_letter_no_checks(element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _final.size());
      return _final[pos];
    }

    [[nodiscard]] generator_index_type
    final_letter(element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      return final_letter_no_checks(pos);
    }

    [[nodiscard]] size_t
    current_length_no_checks(element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < _length.size());
      return _length[pos];
    }

    [[nodiscard]] size_t current_length(element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      return current_length_no_checks(pos);
    }

    // This function could be a helper, but current_length cannot be, so keeping
    // this as a mem fn.
    [[nodiscard]] size_t length(element_index_type pos);

    // This function could be a helper, but current_length cannot be, so keeping
    // this as a mem fn.
    [[nodiscard]] size_t length_no_checks(element_index_type pos);

    [[nodiscard]] size_t size() {
      run();
      return current_size();
    }

    [[nodiscard]] bool contains_one();

    [[nodiscard]] bool currently_contains_one() const noexcept {
      return _found_one;
    }

    [[nodiscard]] size_t number_of_rules() {
      run();
      return _nr_rules;
    }

    [[nodiscard]] cayley_graph_type const& right_cayley_graph() {
      run();
      return _right;
    }

    [[nodiscard]] cayley_graph_type const&
    current_right_cayley_graph() const noexcept {
      return _right;
    }

    [[nodiscard]] cayley_graph_type const& left_cayley_graph() {
      run();
      return _left;
    }

    [[nodiscard]] cayley_graph_type const&
    current_left_cayley_graph() const noexcept {
      return _left;
    }
 
    // Here's a little summary of the functions for minimal_factorisation:
    // [x] current_minimal_factorisation_no_checks(2 args)
    // [x] current_minimal_factorisation(2 args)
    // [x] minimal_factorisation(2 args)

    template <typename Iterator>
    void current_minimal_factorisation_no_checks(Iterator           d_first,
                                                 element_index_type pos) const {
      LIBSEMIGROUPS_ASSERT(pos < current_size());
      while (pos != UNDEFINED) {
        *d_first = first_letter_no_checks(pos);
        pos      = suffix_no_checks(pos);
      }
    }

    template <typename Iterator>
    void current_minimal_factorisation(Iterator           d_first,
                                       element_index_type pos) const {
      throw_if_element_index_out_of_range(pos);
      current_minimal_factorisation_no_checks(d_first, pos);
    }

    //
    // Note: There's no no_check version of this function because it doesn't
    // make sense (see the impl of minimal_factorisation(word_type&,
    // element_index_type)
    template <typename Iterator>
    void minimal_factorisation(Iterator d_first, element_index_type pos) {
      if (pos >= current_size() && !finished()) {
        enumerate(pos + 1);
      }
      throw_if_element_index_out_of_range(pos);
      current_minimal_factorisation_no_checks(d_first, pos);
    }
 
    // Here's a little summary of the functions for (non-minimal) factorisation:
    // [x] current_factorisation_no_checks(2 args)
    // [ ] current_factorisation(2 args) TODO(1)
    // [x] factorisation(2 args)

    // TODO(1) check that all _no_checks functions have this warning
    template <typename Iterator>
    void current_factorisation_no_checks(Iterator           d_first,
                                         element_index_type pos) const {
      current_minimal_factorisation_no_checks(d_first, pos);
    }

    //
    // Note: There's no no_check version of this function because it doesn't
    // make sense (see the impl of minimal_factorisation(word_type&,
    // element_index_type)
    template <typename Iterator>
    void factorisation(Iterator d_first, element_index_type pos) {
      minimal_factorisation(d_first, pos);
    }

    void enumerate(size_t limit);

    [[nodiscard]] size_t number_of_elements_of_length(size_t min,
                                                      size_t max) const;

    [[nodiscard]] size_t number_of_elements_of_length(size_t len) const;

    class const_rule_iterator {
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
 
     public:
      using size_type = typename std::vector<relation_type>::size_type;
      using difference_type =
          typename std::vector<relation_type>::difference_type;
      using const_pointer = typename std::vector<relation_type>::const_pointer;
      using pointer       = typename std::vector<relation_type>::pointer;
      using const_reference =
          typename std::vector<relation_type>::const_reference;
      using reference         = typename std::vector<relation_type>::reference;
      using value_type        = relation_type;
      using iterator_category = std::forward_iterator_tag;
 
      const_rule_iterator()                                      = default;
      const_rule_iterator(const_rule_iterator const&)            = default;
      const_rule_iterator(const_rule_iterator&&)                 = default;
      const_rule_iterator& operator=(const_rule_iterator const&) = default;
      const_rule_iterator& operator=(const_rule_iterator&&)      = default;
 
      const_rule_iterator(FroidurePinBase const* ptr,
                          enumerate_index_type   pos,
                          generator_index_type   gen);
 
      ~const_rule_iterator() = default;
 
      [[nodiscard]] bool
      operator==(const_rule_iterator const& that) const noexcept {
        return _gen == that._gen && _pos == that._pos;
      }
 
      [[nodiscard]] bool
      operator!=(const_rule_iterator const& that) const noexcept {
        return !(this->operator==(that));
      }
 
      [[nodiscard]] const_reference operator*() const {
        populate_relation();
        return _relation;
      }
 
      [[nodiscard]] const_pointer operator->() const {
        populate_relation();
        return &_relation;
      }
 
      // prefix
      const_rule_iterator const& operator++() noexcept;
 
      // postfix
      [[nodiscard]] const_rule_iterator operator++(int) noexcept {
        const_rule_iterator copy(*this);
        ++(*this);
        return copy;
      }
 
      void swap(const_rule_iterator& that) noexcept {
        _current.swap(that._current);
        std::swap(_froidure_pin, that._froidure_pin);
        std::swap(_gen, that._gen);
        std::swap(_pos, that._pos);
      }
#endif  // LIBSEMIGROUPS_PARSED_BY_DOXYGEN not defined
 
     private:
      void populate_relation() const;
 
      std::array<generator_index_type, 3> _current;
      FroidurePinBase const*              _froidure_pin;
      generator_index_type                _gen;
      enumerate_index_type                _pos;
      mutable relation_type               _relation;
    };  // const_rule_iterator
 
    // Assert that the forward iterator requirements are met
    static_assert(std::is_default_constructible_v<const_rule_iterator>,
                  "forward iterator requires default-constructible");
    static_assert(std::is_copy_constructible_v<const_rule_iterator>,
                  "forward iterator requires copy-constructible");
    static_assert(std::is_copy_assignable_v<const_rule_iterator>,
                  "forward iterator requires copy-assignable");
    static_assert(std::is_destructible_v<const_rule_iterator>,
                  "forward iterator requires destructible");

    // clang-format off
    // clang-format on
    [[nodiscard]] const_rule_iterator cbegin_current_rules() const {
      return const_rule_iterator(this, UNDEFINED, 0);
    }

    [[nodiscard]] const_rule_iterator cbegin_rules() {
      run();
      return const_rule_iterator(this, UNDEFINED, 0);
    }

    // clang-format off
    // clang-format on
    [[nodiscard]] const_rule_iterator cend_current_rules() const {
      return const_rule_iterator(this, current_size(), 0);
    }

    [[nodiscard]] const_rule_iterator cend_rules() {
      run();
      return const_rule_iterator(this, current_size(), 0);
    }
 
    // TODO(later) it'd be more efficient to have this be a forward
    // iterator only (i.e. as is done in the GAP version of FroidurePin)
    class const_normal_form_iterator {
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
      // Private data
      mutable FroidurePinBase const* _froidure_pin;
      enumerate_index_type           _pos;
      mutable word_type              _word;
 
     public:
      using size_type       = typename std::vector<word_type>::size_type;
      using difference_type = typename std::vector<word_type>::difference_type;
      using const_pointer   = typename std::vector<word_type>::const_pointer;
      using pointer         = typename std::vector<word_type>::pointer;
      using const_reference = typename std::vector<word_type>::const_reference;
      using reference       = typename std::vector<word_type>::reference;
      using value_type      = word_type;
      using iterator_category = std::random_access_iterator_tag;
 
      const_normal_form_iterator()                                  = default;
      const_normal_form_iterator(const_normal_form_iterator const&) = default;
      const_normal_form_iterator(const_normal_form_iterator&&)      = default;
      const_normal_form_iterator& operator=(const_normal_form_iterator const&)
          = default;
      const_normal_form_iterator& operator=(const_normal_form_iterator&&)
          = default;
 
      ~const_normal_form_iterator() = default;
 
      const_normal_form_iterator(FroidurePinBase const* ptr,
                                 enumerate_index_type   pos)
          : _froidure_pin(ptr), _pos(pos), _word() {}
 
      [[nodiscard]] bool
      operator==(const_normal_form_iterator const& that) const noexcept {
        return _pos == that._pos;
      }
 
      [[nodiscard]] bool
      operator!=(const_normal_form_iterator const& that) const noexcept {
        return !(*this == that);
      }
 
      [[nodiscard]] bool
      operator<(const_normal_form_iterator const& that) const noexcept {
        return _pos < that._pos;
      }
 
      [[nodiscard]] bool
      operator>(const_normal_form_iterator const& that) const noexcept {
        return _pos > that._pos;
      }
 
      [[nodiscard]] bool
      operator<=(const_normal_form_iterator const& that) const noexcept {
        return _pos < that._pos;
      }
 
      [[nodiscard]] bool
      operator>=(const_normal_form_iterator const& that) const noexcept {
        return _pos > that._pos;
      }
 
      [[nodiscard]] const_reference operator*() const noexcept {
        populate_word();
        return _word;
      }
 
      [[nodiscard]] const_pointer operator->() const noexcept {
        populate_word();
        return &_word;
      }
 
      [[nodiscard]] const_reference operator[](size_type index) const {
        const_cast<const_normal_form_iterator*>(this)->_pos += index;
        populate_word();
        const_cast<const_normal_form_iterator*>(this)->_pos -= index;
        return _word;
      }
 
      // prefix
      const_normal_form_iterator const& operator++() noexcept {
        _pos++;
        return *this;
      }
 
      [[nodiscard]] const_normal_form_iterator operator++(int) noexcept {
        const_normal_form_iterator copy(*this);
        ++(*this);
        return copy;
      }
 
      const_normal_form_iterator const& operator--() noexcept {
        _pos--;
        return *this;
      }
 
      [[nodiscard]] const_normal_form_iterator operator--(int) noexcept {
        const_normal_form_iterator copy(*this);
        --(*this);
        return copy;
      }
 
      void operator+=(size_type val) noexcept {
        _pos += val;
      }
 
      void operator-=(size_type val) noexcept {
        _pos -= val;
      }
 
      [[nodiscard]] const_normal_form_iterator
      operator+(size_type val) const noexcept {
        const_normal_form_iterator copy(*this);
        copy += val;
        return copy;
      }
 
      [[nodiscard]] const_normal_form_iterator
      operator-(size_type val) const noexcept {
        const_normal_form_iterator copy(*this);
        copy -= val;
        return copy;
      }
 
      [[nodiscard]] difference_type
      operator-(const_normal_form_iterator const& that) const noexcept {
        return _pos - that._pos;
      }
 
      void swap(const_normal_form_iterator& that) noexcept {
        std::swap(_froidure_pin, that._froidure_pin);
        std::swap(_pos, that._pos);
        std::swap(_word, that._word);
      }
 
     private:
      void populate_word() const {
        _word.clear();
        _froidure_pin->current_minimal_factorisation_no_checks(
            std::back_inserter(_word), _pos);
      }
#endif  // LIBSEMIGROUPS_PARSED_BY_DOXYGEN not defined
    };

    [[nodiscard]] const_normal_form_iterator
    cbegin_current_normal_forms() const {
      return const_normal_form_iterator(this, 0);
    }

    [[nodiscard]] const_normal_form_iterator cend_current_normal_forms() const {
      return const_normal_form_iterator(this, current_size());
    }

    [[nodiscard]] const_normal_form_iterator cbegin_normal_forms() {
      run();
      return const_normal_form_iterator(this, 0);
    }

    [[nodiscard]] const_normal_form_iterator cend_normal_forms() {
      run();
      return const_normal_form_iterator(this, size());
    }

    // FroidurePin - validation member functions - public

    void throw_if_element_index_out_of_range(element_index_type i) const;

    void throw_if_generator_index_out_of_range(generator_index_type i) const;

    template <typename Iterator1, typename Iterator2>
    void throw_if_any_generator_index_out_of_range(Iterator1 first,
                                                   Iterator2 last) const {
      for (auto it = first; it != last; ++it) {
        throw_if_generator_index_out_of_range(*it);
      }
    }
 
   private:
    // FroidurePinBase - member functions - private
    void partial_copy(FroidurePinBase const& S);
  };  // class FroidurePinBase

  // Implementations of mem fn templates for FroidurePinBase
 
  template <typename Iterator1, typename Iterator2>
  [[nodiscard]] FroidurePinBase::element_index_type
  FroidurePinBase::current_position_no_checks(Iterator1 first,
                                              Iterator2 last) const {
    if (first == last) {
      if (_found_one) {
        return _pos_one;
      } else {
        return UNDEFINED;
      }
    }
    element_index_type s = position_of_generator_no_checks(*first);
    return word_graph::follow_path_no_checks(
        current_right_cayley_graph(), s, first + 1, last);
  }

  namespace froidure_pin {
    [[nodiscard]] FroidurePinBase::element_index_type
    product_by_reduction_no_checks(
        FroidurePinBase const&                       fpb,
        typename FroidurePinBase::element_index_type i,
        typename FroidurePinBase::element_index_type j);

    [[nodiscard]] typename FroidurePinBase::element_index_type
    product_by_reduction(FroidurePinBase const&                       fpb,
                         typename FroidurePinBase::element_index_type i,
                         typename FroidurePinBase::element_index_type j);

    // Position helper functions

    template <typename Word>
    [[nodiscard]] FroidurePinBase::element_index_type
    current_position_no_checks(FroidurePinBase const& fpb, Word const& w) {
      return fpb.current_position_no_checks(std::begin(w), std::end(w));
    }

    [[nodiscard]] static inline FroidurePinBase::element_index_type
    current_position_no_checks(FroidurePinBase const&            fpb,
                               std::initializer_list<int> const& w) {
      return current_position_no_checks<std::initializer_list<int>>(fpb, w);
    }

    template <typename Word>
    [[nodiscard]] FroidurePinBase::element_index_type
    current_position(FroidurePinBase const& fpb, Word const& w) {
      return fpb.current_position(std::begin(w), std::end(w));
    }

    [[nodiscard]] static inline FroidurePinBase::element_index_type
    current_position(FroidurePinBase const&            fpb,
                     std::initializer_list<int> const& w) {
      return current_position<std::initializer_list<int>>(fpb, w);
    }

    template <typename Word>
    [[nodiscard]] FroidurePinBase::element_index_type
    position_no_checks(FroidurePinBase& fpb, Word const& w) {
      return fpb.position_no_checks(std::begin(w), std::end(w));
    }

    [[nodiscard]] static inline FroidurePinBase::element_index_type
    position_no_checks(FroidurePinBase&                  fpb,
                       std::initializer_list<int> const& w) {
      return position_no_checks<std::initializer_list<int>>(fpb, w);
    }

    template <typename Word>
    [[nodiscard]] FroidurePinBase::element_index_type
    position(FroidurePinBase& fpb, Word const& w) {
      return fpb.position(std::begin(w), std::end(w));
    }

    [[nodiscard]] static inline FroidurePinBase::element_index_type
    position(FroidurePinBase& fpb, std::initializer_list<int> const& w) {
      return position<std::initializer_list<int>>(fpb, w);
    }

    // Minimal factorisation helper functions

    template <typename Word>
    void current_minimal_factorisation_no_checks(
        FroidurePinBase const&              fpb,
        Word&                               word,
        FroidurePinBase::element_index_type pos) {
      // TODO(1) remove the clear (makes the functions more flexible), but will
      // require care
      word.clear();
      fpb.current_minimal_factorisation_no_checks(std::back_inserter(word),
                                                  pos);
    }

    template <typename Word = word_type>
    [[nodiscard]] Word current_minimal_factorisation_no_checks(
        FroidurePinBase const&              fpb,
        FroidurePinBase::element_index_type pos) {
      Word word;
      current_minimal_factorisation_no_checks(fpb, word, pos);
      return word;
    }

    template <typename Word>
    void
    current_minimal_factorisation(FroidurePinBase const&              fpb,
                                  Word&                               word,
                                  FroidurePinBase::element_index_type pos) {
      // TODO(1) remove the clear (makes the functions more flexible), but will
      // require care
      word.clear();
      fpb.current_minimal_factorisation(std::back_inserter(word), pos);
    }

    template <typename Word = word_type>
    [[nodiscard]] Word
    current_minimal_factorisation(FroidurePinBase const&              fpb,
                                  FroidurePinBase::element_index_type pos) {
      Word word;
      current_minimal_factorisation(fpb, word, pos);
      return word;
    }

    // Note: there's no no_check version of this function because it doesn't
    // make sense (see the impl of minimal_factorisation(word_type&,
    // FroidurePinBase::element_index_type);
    template <typename Word>
    void minimal_factorisation(FroidurePinBase&                    fpb,
                               Word&                               word,
                               FroidurePinBase::element_index_type pos) {
      // TODO(1) remove the clear (makes the functions more flexible), but will
      // require care
      word.clear();
      fpb.minimal_factorisation(std::back_inserter(word), pos);
    }

    // Notes:
    // * There's no no_check version of this function because it doesn't make
    //   sense (see the impl of minimal_factorisation(word_type&,
    //   FroidurePinBase::element_index_type);
    template <typename Word = word_type>
    [[nodiscard]] Word
    minimal_factorisation(FroidurePinBase&                    fpb,
                          FroidurePinBase::element_index_type pos) {
      Word word;
      minimal_factorisation(fpb, word, pos);
      return word;
    }

    // (Non-minimal) factorisation helper functions

    template <typename Word>
    void
    current_factorisation_no_checks(FroidurePinBase const&              fpb,
                                    Word&                               word,
                                    FroidurePinBase::element_index_type pos) {
      return current_minimal_factorisation_no_checks<Word>(fpb, word, pos);
    }

    template <typename Word>
    void factorisation(FroidurePinBase&                    fpb,
                       Word&                               word,
                       FroidurePinBase::element_index_type pos) {
      return minimal_factorisation<Word>(fpb, word, pos);
    }

    template <typename Word = word_type>
    [[nodiscard]] Word factorisation(FroidurePinBase&                    fpb,
                                     FroidurePinBase::element_index_type pos) {
      return minimal_factorisation<Word>(fpb, pos);
    }

    // TODO(1) complexity?
    [[nodiscard]] rx::iterator_range<
        FroidurePinBase::const_normal_form_iterator>
    current_normal_forms(FroidurePinBase const& fpb);

    [[nodiscard]] rx::iterator_range<
        FroidurePinBase::const_normal_form_iterator>
    normal_forms(FroidurePinBase& fpb);

    // TODO(1) complexity?
    [[nodiscard]] rx::iterator_range<FroidurePinBase::const_rule_iterator>
    current_rules(FroidurePinBase const& fpb);

    [[nodiscard]] rx::iterator_range<FroidurePinBase::const_rule_iterator>
    rules(FroidurePinBase& fpb);
 
  }  // namespace froidure_pin
}  // namespace libsemigroups
#endif  // LIBSEMIGROUPS_FROIDURE_PIN_BASE_HPP_