froidure-pin.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_HPP_
#define LIBSEMIGROUPS_FROIDURE_PIN_HPP_
 
#include <cstddef>           // for size_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for make_move_iterator
#include <memory>            // for shared_ptr, make_shared
#include <mutex>             // for mutex
#include <type_traits>       // for is_const, remove_pointer
#include <unordered_map>     // for unordered_map
#include <utility>           // for pair
#include <vector>            // for vector
 
#include "adapters.hpp"           // for Complexity, Degree, IncreaseDegree
#include "debug.hpp"              // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"          // for LIBSEMIGROUPS_EXCEPTION
#include "froidure-pin-base.hpp"  // for FroidurePinBase, FroidurePinBase::s...
#include "types.hpp"              // for letter_type, word_type
 
#include "detail/bruidhinn-traits.hpp"  // for detail::BruidhinnTraits
#include "detail/iterator.hpp"          // for ConstIteratorStateless
#include "detail/report.hpp"            // for report_default
#include "detail/stl.hpp"               // for EqualTo, Hash
 
#include "rx/ranges.hpp"  // for iterator_range

namespace libsemigroups {
 
  template <typename T>
  struct FroidurePinState {
    using type = void;
  };

  template <typename Element,
            typename State = typename FroidurePinState<Element>::type>
  struct FroidurePinTraits {
    // Require to get the value_type from detail::BruidhinnTraits to remove
    // pointer to const.
    using element_type = typename detail::BruidhinnTraits<Element>::value_type;

    using state_type = State;

    using Complexity = ::libsemigroups::Complexity<element_type>;

    using Degree = ::libsemigroups::Degree<element_type>;

    using EqualTo = ::libsemigroups::EqualTo<element_type>;

    using Hash = ::libsemigroups::Hash<element_type>;

    using IncreaseDegree = ::libsemigroups::IncreaseDegree<element_type>;

    using Less = ::libsemigroups::Less<element_type>;

    using One = ::libsemigroups::One<element_type>;

    using Product = ::libsemigroups::Product<element_type>;

    using Swap = ::libsemigroups::Swap<element_type>;
  };

  template <typename Element, typename Traits = FroidurePinTraits<Element>>
  class FroidurePin : private detail::BruidhinnTraits<Element>,
                      public FroidurePinBase {
   private:
    // FroidurePin - typedefs - private
 
    using internal_element_type =
        typename detail::BruidhinnTraits<Element>::internal_value_type;
    using internal_const_element_type =
        typename detail::BruidhinnTraits<Element>::internal_const_value_type;
    using internal_const_reference =
        typename detail::BruidhinnTraits<Element>::internal_const_reference;
    using internal_idempotent_pair
        = std::pair<internal_element_type, element_index_type>;
 
    static_assert(
        std::is_const_v<internal_const_element_type>
            || std::is_const_v<
                std::remove_pointer_t<internal_const_element_type>>,
        "internal_const_element_type must be const or pointer to const");
 
    // The elements of a semigroup are stored in _elements, but because of the
    // way add_generators/closure work, it might not be the case that all the
    // words of a given length are contiguous in _elements. Hence we require a
    // means of finding the next element of a given length. In
    // _enumerate_order, the first K_1 values are element_index_type's equal to
    // the positions in _elements of the words of length 1, the next K_2 values
    // are the element_index_type's equal to the positions in _elements of the
    // words of length 2, and so on.
    //
    // This alias is used to distinguish variables that refer to positions in
    // _elements (element_index_type) from those that refer to positions in
    // _enumerate_order (enumerate_index_type).
    using enumerate_index_type = FroidurePinBase::enumerate_index_type;
 
    struct InternalEqualTo : private detail::BruidhinnTraits<Element> {
      [[nodiscard]] bool operator()(internal_const_reference x,
                                    internal_const_reference y) const {
        return EqualTo()(this->to_external_const(x),
                         this->to_external_const(y));
      }
    };
 
    struct InternalHash : private detail::BruidhinnTraits<Element> {
      [[nodiscard]] size_t operator()(internal_const_reference x) const {
        return Hash()(this->to_external_const(x));
      }
    };
 
    using map_type = std::unordered_map<internal_const_element_type,
                                        element_index_type,
                                        InternalHash,
                                        InternalEqualTo>;
 
   public:
    // FroidurePin - typedefs - public

    using element_type = typename detail::BruidhinnTraits<Element>::value_type;

    // This only really exists to allow the python bindings to compile with
    // gcc-6 + 7 (at least).
    using value_type = element_type;

    using const_element_type =
        typename detail::BruidhinnTraits<Element>::const_value_type;

    using const_reference =
        typename detail::BruidhinnTraits<Element>::const_reference;

    using rvalue_reference =
        typename detail::BruidhinnTraits<Element>::rvalue_reference;

    using reference = typename detail::BruidhinnTraits<Element>::reference;

    using const_pointer =
        typename detail::BruidhinnTraits<Element>::const_pointer;

    using size_type = FroidurePinBase::size_type;

    using element_index_type = FroidurePinBase::element_index_type;

    using cayley_graph_type = FroidurePinBase::cayley_graph_type;

    using state_type = typename Traits::state_type;

    using Complexity = typename Traits::Complexity;

    using Degree = typename Traits::Degree;

    using EqualTo = typename Traits::EqualTo;

    using Hash = typename Traits::Hash;

    using IncreaseDegree = typename Traits::IncreaseDegree;

    using Less = typename Traits::Less;

    using One = typename Traits::One;

    using Product = typename Traits::Product;

    using Swap = typename Traits::Swap;
 
   private:
    template <typename T>
    static constexpr bool IsState
        = ((!std::is_void_v<T>) &&std::is_same_v<state_type, T>);

    // FroidurePin - data - private
 
    std::vector<internal_element_type>    _elements;
    std::vector<internal_element_type>    _gens;
    internal_element_type                 _id;
    std::vector<internal_idempotent_pair> _idempotents;
    map_type                              _map;
    mutable std::mutex                    _mtx;
    std::vector<std::pair<internal_element_type, element_index_type>> _sorted;
    std::shared_ptr<state_type>                                       _state;
    mutable internal_element_type _tmp_product;
 
    void internal_product(reference       xy,
                          const_reference x,
                          const_reference y,
                          state_type*     stt,
                          size_t          tid = 0) const {
      if constexpr (std::is_void_v<state_type>) {
        (void) stt;  // To silence warnings in g++-9
        Product()(xy, x, y, tid);
      } else {
        Product()(xy, x, y, stt, tid);
      }
    }
 
   public:
    // FroidurePin - constructors + destructor - public

    FroidurePin();

    FroidurePin& init();

    template <typename State, typename = std::enable_if_t<IsState<State>>>
    explicit FroidurePin(std::shared_ptr<State> stt) : FroidurePin() {
      _state = stt;
    }

    template <typename State, typename = std::enable_if_t<IsState<State>>>
    FroidurePin& init(std::shared_ptr<State> stt) {
      init();
      _state = stt;
    }

    template <typename State, typename = std::enable_if_t<IsState<State>>>
    explicit FroidurePin(State const& stt)
        : FroidurePin(std::make_shared<state_type>(stt)) {}

    template <typename State, typename = std::enable_if_t<IsState<State>>>
    FroidurePin& init(State const& stt) {
      return init(std::make_shared<state_type>(stt));
    }

    FroidurePin& operator=(FroidurePin const&);

    FroidurePin& operator=(FroidurePin&&) = default;

    template <typename Iterator1, typename Iterator2>
    FroidurePin(Iterator1 first, Iterator2 last);

    template <typename Iterator1, typename Iterator2>
    FroidurePin& init(Iterator1 first, Iterator2 last);

    FroidurePin(FroidurePin const& that);

    FroidurePin(FroidurePin&&) = default;
 
    ~FroidurePin();
 
   private:
    void free_data();

    // FroidurePin - constructor - private
 
    FroidurePin(FroidurePin const&, const_reference);
 
   public:
    // FroidurePin - member functions - public

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

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

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] bool equal_to_no_checks(Iterator1 first1,
                                          Iterator2 last1,
                                          Iterator3 first2,
                                          Iterator4 last2) const;

    template <typename Iterator1,
              typename Iterator2,
              typename Iterator3,
              typename Iterator4>
    [[nodiscard]] bool equal_to(Iterator1 first1,
                                Iterator2 last1,
                                Iterator3 first2,
                                Iterator4 last2) const {
      throw_if_any_generator_index_out_of_range(first1, last1);
      throw_if_any_generator_index_out_of_range(first2, last2);
      return equal_to_no_checks(first1, last1, first2, last2);
    }

    [[nodiscard]] size_t number_of_generators() const noexcept override;

    [[nodiscard]] const_reference generator(generator_index_type i) const;

    [[nodiscard]] const_reference
    generator_no_checks(generator_index_type i) const;

    [[nodiscard]] element_index_type current_position(const_reference x) const;
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    using FroidurePinBase::current_position;
#endif

    [[nodiscard]] element_index_type
    fast_product_no_checks(element_index_type i, element_index_type j) const;

    //! This function does not trigger any enumeration.
    [[nodiscard]] element_index_type fast_product(element_index_type i,
                                                  element_index_type j) const {
      throw_if_element_index_out_of_range(i);
      throw_if_element_index_out_of_range(j);
      return fast_product_no_checks(i, j);
    }

    [[nodiscard]] size_t number_of_idempotents();

    // TODO(1) improve this it doesn't need to trigger a full enum.
    [[nodiscard]] bool is_idempotent_no_checks(element_index_type i);

    //! This function triggers a full enumeration.
    [[nodiscard]] bool is_idempotent(element_index_type i) {
      run();
      throw_if_element_index_out_of_range(i);
      return is_idempotent_no_checks(i);
    }

    FroidurePin& reserve(size_t val);

    [[nodiscard]] bool contains(const_reference x);

    [[nodiscard]] element_index_type position(const_reference x);

    [[nodiscard]] element_index_type sorted_position(const_reference x);

    // There's no no-checks version of this, there can't be.
    [[nodiscard]] element_index_type to_sorted_position(element_index_type i);

    [[nodiscard]] const_reference at(element_index_type i);

    const_reference operator[](element_index_type i) const;

    [[nodiscard]] const_reference sorted_at(element_index_type i);

    [[nodiscard]] const_reference sorted_at_no_checks(element_index_type i);
 
#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
    // The following are required, they are documented in FroidurePinBase.
    // Sphinx/doxygen get confused by this, so we don't allow Doxygen to parse
    // these two declarations.
    using FroidurePinBase::factorisation;
    using FroidurePinBase::minimal_factorisation;
#endif

    //! No enumeration is triggered by calls to this function.
    [[nodiscard]] tril is_finite() const override {
      return tril::TRUE;
    }

    template <typename Iterator1, typename Iterator2>
    FroidurePin& add_generators_no_checks(Iterator1 first, Iterator2 last);

    template <typename Iterator1, typename Iterator2>
    FroidurePin& add_generators(Iterator1 first, Iterator2 last);

    FroidurePin& add_generator_no_checks(const_reference x);

    FroidurePin& add_generator(const_reference x);
 
    // TODO(1) make the following work
    // FroidurePin add_generator(rvalue_reference x);

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

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] FroidurePin copy_add_generators(Iterator1 first,
                                                  Iterator2 last) const {
      throw_if_degree_too_small(first, last);
      throw_if_inconsistent_degree(first, last);
      return copy_add_generators_no_checks(first, last);
    }
 
    // TODO(1) copy_add_generator
    // TODO(1) copy_add_generators_no_checks

    template <typename Iterator1, typename Iterator2>
    FroidurePin& closure_no_checks(Iterator1 first, Iterator2 last);

    template <typename Iterator1, typename Iterator2>
    FroidurePin& closure(Iterator1 first, Iterator2 last) {
      throw_if_degree_too_small(first, last);
      throw_if_inconsistent_degree(first, last);
      return closure_no_checks(first, last);
    }
 
    // TODO(1) closure(const_reference)
    // TODO(1) closure_no_checks(const_reference)

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] FroidurePin copy_closure_no_checks(Iterator1 first,
                                                     Iterator2 last);

    template <typename Iterator1, typename Iterator2>
    [[nodiscard]] FroidurePin copy_closure(Iterator1 first, Iterator2 last) {
      throw_if_degree_too_small(first, last);
      throw_if_inconsistent_degree(first, last);
      return copy_closure_no_checks(first, last);
    }
 
    // TODO(1) copy_closure(const_reference)
    // TODO(1) copy_closure_no_checks(const_reference)

    //! \no_libsemigroups_except
    std::shared_ptr<state_type> state() const {
      return _state;
    }

    template <typename Iterator1, typename Iterator2>
    static void throw_if_inconsistent_degree(Iterator1 first, Iterator2 last);
 
   private:
    // FroidurePin - validation member functions - private
 
    void throw_if_bad_degree(const_reference) const;
 
    template <typename Iterator1, typename Iterator2>
    void throw_if_bad_degree(Iterator1, Iterator2) const;
 
    template <typename Iterator1, typename Iterator2>
    void throw_if_degree_too_small(Iterator1, Iterator2) const;

    // FroidurePin - enumeration member functions - private
 
    void expand(size_type);
    void is_one(internal_const_element_type x, element_index_type) noexcept(
        std::is_nothrow_default_constructible_v<InternalEqualTo>&& noexcept(
            std::declval<InternalEqualTo>()(x, x)));
 
    void copy_generators_from_elements(size_t);
    void closure_update(element_index_type,
                        generator_index_type,
                        generator_index_type,
                        element_index_type,
                        size_type,
                        size_t const&,
                        std::vector<bool>&,
                        state_type*);
 
    void init_degree(const_reference);
 
    template <typename Iterator1, typename Iterator2>
    void add_generators_before_start(Iterator1, Iterator2);
 
    template <typename Iterator1, typename Iterator2>
    void add_generators_after_start(Iterator1, Iterator2);

    // FroidurePin - initialisation member functions - private
 
    void init_sorted();
    void init_idempotents();
    void idempotents(enumerate_index_type,
                     enumerate_index_type,
                     enumerate_index_type,
                     std::vector<internal_idempotent_pair>&);
 
    // Forward declarations - implemented in froidure-pin.tpp
    struct DerefPairFirst;
    struct AddressOfPairFirst;
    struct IteratorPairFirstTraits;

    // FroidurePin - iterators - private
 
    // A type for const iterators through (element, index) pairs of \c this.
    using const_iterator_pair_first
        = detail::ConstIteratorStateless<IteratorPairFirstTraits>;
 
   public:
    // FroidurePin - iterators - public
    using const_iterator
        = detail::BruidhinnConstIterator<element_type,
                                         std::vector<internal_element_type>>;

    using const_iterator_sorted = const_iterator_pair_first;

    using const_iterator_idempotents = const_iterator_pair_first;

    [[nodiscard]] const_iterator cbegin() const;

    [[nodiscard]] const_iterator begin() const;

    [[nodiscard]] const_iterator cend() const;

    [[nodiscard]] const_iterator end() const;

    [[nodiscard]] const_iterator_sorted cbegin_sorted();

    [[nodiscard]] const_iterator_sorted cend_sorted();

    [[nodiscard]] const_iterator_idempotents cbegin_idempotents();

    [[nodiscard]] const_iterator_idempotents cend_idempotents();
 
   private:
    void run_impl() override;
 
    void report_progress();
 
    bool finished_impl() const override;
  };

  template <typename Iterator1, typename Iterator2>
  FroidurePin(Iterator1, Iterator2)
      -> FroidurePin<std::decay_t<decltype(*std::declval<Iterator1>())>>;
 
  // Namespace doc is in froidure-pin-base.hpp
  namespace froidure_pin {

    // NOTE: this isn't called make because it is not constructing anything,
    // rather re-initializing.
    template <typename Container>
    FroidurePin<typename Container::value_type>&
    init(FroidurePin<typename Container::value_type>& fp,
         Container const&                             gens) {
      return fp.init(std::begin(gens), std::end(gens));
    }
 
    // TODO(1) make the following work
    // template <typename Container>
    // FroidurePin<typename Container::value_type>&
    // init(FroidurePin<typename Container::value_type>& fp, Container&& gens) {
    //   return fp.init(std::make_move_iterator(std::begin(gens)),
    //                  std::make_move_iterator(std::end(gens)));
    // }
 
    // clang-format off
    // NOLINTNEXTLINE(whitespace/line_length)
    // clang-format on
    template <typename Element>
    [[nodiscard]] FroidurePin<Element>
    init(FroidurePin<Element>& fp, std::initializer_list<Element> gens) {
      return fp.init(std::begin(gens), std::end(gens));
    }

    template <typename Container>
    void add_generators(FroidurePin<typename Container::value_type>& fp,
                        Container const&                             coll) {
      fp.add_generators(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    void
    add_generators_no_checks(FroidurePin<typename Container::value_type>& fp,
                             Container const& coll) {
      fp.add_generators_no_checks(std::begin(coll), std::end(coll));
    }
 
    // TODO(1) make the following work
    // template <typename Container>
    // FroidurePin<typename Container::value_type>&
    // add_generators(FroidurePin<typename Container::value_type>& fp,
    //                Container&&                                  coll) {
    //   // Note that this currently doesn't do anything different than the
    //   // function above.
    //   return fp.add_generators(std::make_move_iterator(std::begin(coll)),
    //                            std::make_move_iterator(std::end(coll)));
    // }

    template <typename Element>
    void add_generators(FroidurePin<Element>&          fp,
                        std::initializer_list<Element> coll) {
      fp.add_generators(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    void add_generators_no_checks(FroidurePin<Element>&          fp,
                                  std::initializer_list<Element> coll) {
      fp.add_generators_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    [[nodiscard]] FroidurePin<typename Container::value_type>
    copy_add_generators(FroidurePin<typename Container::value_type> const& fp,
                        Container const& coll) {
      return fp.copy_add_generators(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    [[nodiscard]] FroidurePin<typename Container::value_type>
    copy_add_generators_no_checks(
        FroidurePin<typename Container::value_type> const& fp,
        Container const&                                   coll) {
      return fp.copy_add_generators_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    [[nodiscard]] FroidurePin<Element>
    copy_add_generators(FroidurePin<Element> const&    fp,
                        std::initializer_list<Element> coll) {
      return fp.copy_add_generators(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    [[nodiscard]] FroidurePin<Element>
    copy_add_generators_no_checks(FroidurePin<Element> const&    fp,
                                  std::initializer_list<Element> coll) {
      return fp.copy_add_generators_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    void closure(FroidurePin<typename Container::value_type>& fp,
                 Container const&                             coll) {
      fp.closure(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    void closure_no_checks(FroidurePin<typename Container::value_type>& fp,
                           Container const&                             coll) {
      fp.closure_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    void closure(FroidurePin<Element>&          fp,
                 std::initializer_list<Element> coll) {
      fp.closure(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    void closure_no_checks(FroidurePin<Element>&          fp,
                           std::initializer_list<Element> coll) {
      fp.closure_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    [[nodiscard]] FroidurePin<typename Container::value_type>
    copy_closure(FroidurePin<typename Container::value_type>& fp,
                 Container const&                             coll) {
      return fp.copy_closure(std::begin(coll), std::end(coll));
    }

    template <typename Container>
    [[nodiscard]] FroidurePin<typename Container::value_type>
    copy_closure_no_checks(FroidurePin<typename Container::value_type>& fp,
                           Container const&                             coll) {
      return fp.copy_closure_no_checks(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    [[nodiscard]] FroidurePin<Element>
    copy_closure(FroidurePin<Element>&          fp,
                 std::initializer_list<Element> coll) {
      return fp.copy_closure(std::begin(coll), std::end(coll));
    }

    template <typename Element>
    [[nodiscard]] FroidurePin<Element>
    copy_closure_no_checks(FroidurePin<Element>&          fp,
                           std::initializer_list<Element> coll) {
      return fp.copy_closure(std::begin(coll), std::end(coll));
    }
 
    // TODO(1) implement the next function
    // \brief Returns a range object containing the so-far enumerated
    // idempotents.
    //
    // This function returns a range object containing the so-far enumerated
    // idempotents. No enumeration of \p fp is triggered by calls to this
    // function.
    //
    // See TODO(1) for more details about range objects.
    //
    // \tparam Element the type of the elements in the represented
    // semigroup.
    //
    // \tparam Traits a traits class holding various adapters used by the
    // implementation (defaults to FroidurePinTraits).
    //
    // \param fp the FroidurePin instance.
    //
    // \returns A range object.
    //
    // is_idempotent_no_checks current performs a full enum. so this doesn't
    // work.
    //
    // template <typename Element, typename Traits>
    // [[nodiscard]] auto
    // current_idempotents(FroidurePin<Element, Traits> const& fp) {
    //   return rx::iterator_range(fp.cbegin(), fp.cend())
    //          | rx::filter([&fp](auto const& x) {
    //              return fp.is_idempotent_no_checks(fp.current_position(x));
    //            });
    // }

    template <typename Element, typename Traits>
    [[nodiscard]] auto idempotents(FroidurePin<Element, Traits>& fp) {
      fp.run();
      return rx::iterator_range(fp.cbegin_idempotents(), fp.cend_idempotents());
    }

    template <typename Element, typename Traits>
    [[nodiscard]] auto sorted_elements(FroidurePin<Element, Traits>& fp) {
      return rx::iterator_range(fp.cbegin_sorted(), fp.cend_sorted());
    }
 
    // TODO(1) current_sorted_elements

    template <typename Element, typename Traits>
    [[nodiscard]] auto
    current_elements(FroidurePin<Element, Traits> const& fp) {
      return rx::iterator_range(fp.cbegin(), fp.cend());
    }

    template <typename Element, typename Traits>
    [[nodiscard]] auto elements(FroidurePin<Element, Traits>& fp) {
      fp.run();
      return current_elements(fp);
    }

    template <typename Element, typename Traits, typename Word>
    [[nodiscard]] typename FroidurePin<Element, Traits>::const_reference
    to_element_no_checks(FroidurePin<Element, Traits> const& fp,
                         Word const&                         w) {
      return fp.to_element_no_checks(std::begin(w), std::end(w));
    }
 
    // clang-format off
    // NOLINTNEXTLINE(whitespace/line_length)
    // clang-format on
    template <typename Element, typename Traits, typename T = size_t>
    [[nodiscard]] typename FroidurePin<Element, Traits>::const_reference
    to_element_no_checks(FroidurePin<Element, Traits> const& fp,
                         std::initializer_list<T> const&     w) {
      return to_element_no_checks<Element, Traits, std::initializer_list<T>>(fp,
                                                                             w);
    }

    template <typename Element, typename Traits, typename Word>
    [[nodiscard]] typename FroidurePin<Element, Traits>::const_reference
    to_element(FroidurePin<Element, Traits> const& fp, Word const& w) {
      return fp.to_element(std::begin(w), std::end(w));
    }
 
    // clang-format off
    // NOLINTNEXTLINE(whitespace/line_length)
    // clang-format on
    template <typename Element, typename Traits, typename T = size_t>
    [[nodiscard]] typename FroidurePin<Element, Traits>::const_reference
    to_element(FroidurePin<Element, Traits> const& fp,
               std::initializer_list<T> const&     w) {
      return to_element<Element, Traits, std::initializer_list<T>>(fp, w);
    }

    template <typename Element, typename Traits, typename Word>
    [[nodiscard]] bool
    equal_to_no_checks(FroidurePin<Element, Traits> const& fp,
                       Word const&                         x,
                       Word const&                         y) {
      return fp.equal_to_no_checks(
          std::begin(x), std::end(x), std::begin(y), std::end(y));
    }

    template <typename Element, typename Traits, typename Word>
    [[nodiscard]] bool equal_to(FroidurePin<Element, Traits> const& fp,
                                Word const&                         x,
                                Word const&                         y) {
      return fp.equal_to(
          std::begin(x), std::end(x), std::begin(y), std::end(y));
    }

    template <typename Element, typename Traits, typename Word = word_type>
    [[nodiscard]] Word minimal_factorisation(
        FroidurePin<Element, Traits>&                          fp,
        typename FroidurePin<Element, Traits>::const_reference x);

    template <typename Element, typename Traits, typename Word>
    void minimal_factorisation(
        FroidurePin<Element, Traits>&                          fp,
        Word&                                                  w,
        typename FroidurePin<Element, Traits>::const_reference x);

    template <typename Element, typename Traits, typename Word = word_type>
    [[nodiscard]] Word
    factorisation(FroidurePin<Element, Traits>&                          fp,
                  typename FroidurePin<Element, Traits>::const_reference x);

    template <typename Element, typename Traits, typename Word>
    void
    factorisation(FroidurePin<Element, Traits>&                          fp,
                  Word&                                                  w,
                  typename FroidurePin<Element, Traits>::const_reference x);
 
  }  // namespace froidure_pin


  template <template <typename...> typename Thing,
            typename Container,
            typename Element = typename Container::value_type>
  [[nodiscard]] auto make(Container const& gens)
      -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
                          FroidurePin<Element>> {
    FroidurePin<Element>::throw_if_inconsistent_degree(std::begin(gens),
                                                       std::end(gens));
    return FroidurePin(std::begin(gens), std::end(gens));
  }
 
  // TODO(1) make the following work
  // template <typename Container>
  // FroidurePin<typename Container::value_type>
  // make(Container&& gens) {
  //   return FroidurePin(std::make_move_iterator(std::begin(gens)),
  //                      std::make_move_iterator(std::end(gens)));
  // }

  template <template <typename...> typename Thing, typename Element>
  auto make(std::initializer_list<Element> gens)
      -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
                          FroidurePin<Element>> {
    FroidurePin<Element>::throw_if_inconsistent_degree(std::begin(gens),
                                                       std::end(gens));
    return FroidurePin(std::begin(gens), std::end(gens));
  }

  template <template <typename...> typename Thing,
            typename Iterator1,
            typename Iterator2,
            typename Element
            = std::decay_t<decltype(*std::declval<Iterator1>())>>
  [[nodiscard]] auto make(Iterator1 first, Iterator2 last)
      -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
                          FroidurePin<Element>> {
    static_assert(
        std::is_same_v<std::decay_t<decltype(*std::declval<Iterator2>())>,
                       Element>);
    FroidurePin<Element>::throw_if_inconsistent_degree(first, last);
    return FroidurePin(first, last);
  }

  template <typename Element, typename Traits>
  [[nodiscard]] std::string
  to_human_readable_repr(FroidurePin<Element, Traits> const& fp);
 
}  // namespace libsemigroups
 
#include "froidure-pin.tpp"
 
#endif  // LIBSEMIGROUPS_FROIDURE_PIN_HPP_