transf.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021-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 declaration of the partial transformation class and
// its subclasses.
 
// TODO(later)
// * benchmarks
// * add some tests for PTransf themselves
// * allocator
// * implement is_transformation(Iterator, Iterator) etc to avoid code
// duplication with hpcombi.hpp
 
#ifndef LIBSEMIGROUPS_TRANSF_HPP_
#define LIBSEMIGROUPS_TRANSF_HPP_
 
#include <algorithm>         // for sort, max_element, unique
#include <array>             // for array
#include <cstddef>           // for size_t
#include <cstdint>           // for uint64_t, uint32_t
#include <initializer_list>  // for initializer_list
#include <iterator>          // for distance
#include <limits>            // for numeric_limits
#include <numeric>           // for iota
#include <tuple>             // for tuple_size
#include <type_traits>       // for enable_if_t
#include <unordered_map>     // for unordered_map
#include <unordered_set>     // for unordered_set
#include <utility>           // for forward
#include <vector>            // for vector
 
#include "config.hpp"  // for LIBSEMIGROUPS_HPCOMBI_ENABLED
 
#include "adapters.hpp"   // for Hash etc
#include "bitset.hpp"     // for BitSet
#include "constants.hpp"  // for UNDEFINED, Undefined
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "hpcombi.hpp"    // for HPCombi::Transf16
#include "types.hpp"      // for SmallestInteger
 
#include "detail/stl.hpp"  // for is_array_v
 
namespace libsemigroups {
 
  namespace detail {
    struct PTransfPolymorphicBase {};
  }  // namespace detail

  // TODO(1) example

  template <typename T>
  static constexpr bool IsDerivedFromPTransf
      = std::is_base_of_v<detail::PTransfPolymorphicBase, T>;
 
  namespace detail {
 
    template <typename T>
    struct IsStaticHelper : std::false_type {};
 
    template <typename T>
    struct IsDynamicHelper : std::false_type {};
 
  }  // namespace detail

  template <typename Scalar, typename Container>
  class PTransfBase : public detail::PTransfPolymorphicBase {
    static_assert(std::is_integral_v<Scalar>,
                  "template parameter Scalar must be an integral type");
    static_assert(!std::numeric_limits<Scalar>::is_signed,
                  "template parameter Scalar must be unsigned");
 
   public:
    using point_type = Scalar;

    using container_type = Container;
 
    // Required by python bindings
    [[nodiscard]] static point_type undef() noexcept {
      return static_cast<point_type>(UNDEFINED);
    }

    PTransfBase() = default;
 
    // No constructor from size_t this is delegated to StaticPTransf and
    // DynamicPTransf

    explicit PTransfBase(Container const& cont) : _container(cont) {}

    explicit PTransfBase(Container&& cont) : _container(std::move(cont)) {}

    template <typename Iterator>
    explicit PTransfBase(Iterator first, Iterator last) : PTransfBase() {
      using OtherScalar = typename std::iterator_traits<Iterator>::value_type;
      // The below assertions exist to insure that we are not badly assigning
      // values. The subsequent pragmas exist to suppress the false-positive
      // warnings produced by g++ 13.2.0
      static_assert(
          std::is_same_v<OtherScalar, Undefined>
              || std::is_convertible_v<OtherScalar, point_type>,
          "the template parameter Iterator must have "
          "value_type \"Undefined\" or convertible to \"point_type\"!");
      static_assert(std::is_same_v<std::decay_t<decltype(*_container.begin())>,
                                   point_type>);
      resize(_container, std::distance(first, last));
#pragma GCC diagnostic push
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC diagnostic ignored "-Wstringop-overflow"
#endif
      std::copy(first, last, _container.begin());
#pragma GCC diagnostic pop
    }

    PTransfBase(std::initializer_list<Scalar> cont)
        : PTransfBase(cont.begin(), cont.end()) {}

    template <typename Subclass, typename OtherContainer = Container>
    [[nodiscard]] static Subclass make(OtherContainer&& cont);

    template <typename Subclass, typename OtherScalar>
    [[nodiscard]] static Subclass make(std::initializer_list<OtherScalar> cont);

    PTransfBase(PTransfBase const&) = default;

    PTransfBase(PTransfBase&&) = default;

    PTransfBase& operator=(PTransfBase const&) = default;

    PTransfBase& operator=(PTransfBase&&) = default;

    [[nodiscard]] bool operator<(PTransfBase const& that) const {
      return _container < that._container;
    }

    [[nodiscard]] bool operator>(PTransfBase const& that) const {
      return that < *this;
    }

    [[nodiscard]] bool operator==(PTransfBase const& that) const {
      return _container == that._container;
    }

    [[nodiscard]] bool operator<=(PTransfBase const& that) const {
      return _container < that._container || _container == that._container;
    }

    [[nodiscard]] bool operator>=(PTransfBase const& that) const {
      return that <= *this;
    }

    [[nodiscard]] bool operator!=(PTransfBase const& that) const {
      return !(*this == that);
    }

    [[nodiscard]] point_type& operator[](size_t i) {
      return _container[i];
    }

    [[nodiscard]] point_type const& operator[](size_t i) const {
      return _container[i];
    }

    // TODO(1) better exception message for python bindings
    [[nodiscard]] point_type& at(size_t i) {
      return _container.at(i);
    }

    // TODO(1) better exception message for python bindings
    [[nodiscard]] point_type const& at(size_t i) const {
      return _container.at(i);
    }

    // TODO(later) other operators such as power
    template <typename Subclass>
    [[nodiscard]] Subclass operator*(Subclass const& that) const {
      static_assert(IsDerivedFromPTransf<Subclass>,
                    "the template parameter Subclass must be derived from "
                    "PTransfPolymorphicBase");
      Subclass xy(that.degree());
      xy.product_inplace(*static_cast<Subclass const*>(this), that);
      return xy;
    }

    using iterator = typename Container::iterator;

    using const_iterator = typename Container::const_iterator;

    [[nodiscard]] const_iterator cbegin() const noexcept {
      return _container.cbegin();
    }

    [[nodiscard]] const_iterator cend() const noexcept {
      return _container.cend();
    }

    [[nodiscard]] const_iterator begin() const noexcept {
      return _container.begin();
    }

    [[nodiscard]] const_iterator end() const noexcept {
      return _container.end();
    }

    [[nodiscard]] iterator begin() noexcept {
      return _container.begin();
    }

    [[nodiscard]] iterator end() noexcept {
      return _container.end();
    }

    [[nodiscard]] size_t rank() const {
      auto vals = std::unordered_set<point_type>(cbegin(), cend());
      return (vals.find(UNDEFINED) == vals.end() ? vals.size()
                                                 : vals.size() - 1);
    }

    // not noexcept because Hash<T>::operator() isn't
    [[nodiscard]] size_t hash_value() const {
      return Hash<Container>()(_container);
    }

    void swap(PTransfBase& that) noexcept {
      std::swap(_container, that._container);
    }

    [[nodiscard]] size_t degree() const noexcept {
      return _container.size();
    }

    template <typename Subclass>
    [[nodiscard]] static Subclass one(size_t N) {
      static_assert(IsDerivedFromPTransf<Subclass>,
                    "the template parameter Subclass must be derived from "
                    "PTransfPolymorphicBase");
      Subclass result(N);
      std::iota(result.begin(), result.end(), 0);
      return result;
    }
 
   protected:
    static void resize(container_type& c, size_t N, point_type val = 0);
    void        resize(size_t N, point_type val = 0) {
      resize(_container, N, val);
    }
 
   private:
    template <typename T>
    static void throw_if_bad_args(T const& cont);
 
    Container _container;
  };

  // Helper variable templates

  template <typename T>
  static constexpr bool IsStatic = detail::IsStaticHelper<T>::value;

  template <typename T>
  static constexpr bool IsDynamic = detail::IsDynamicHelper<T>::value;

  // DynamicPTransf

  template <typename Scalar>
  class DynamicPTransf : public PTransfBase<Scalar, std::vector<Scalar>> {
    using base_type = PTransfBase<Scalar, std::vector<Scalar>>;
 
   public:
    using point_type = Scalar;

    using container_type = std::vector<point_type>;
 
    using PTransfBase<point_type, container_type>::PTransfBase;
    using base_type::begin;
    using base_type::degree;
    using base_type::end;
 
    // No default constructor, because the degree would be 0, and so we can
    // just use the PTransfBase default constructor for that. Note that there's
    // a default constructor for StaticPTransf since there we do know the degree
    // (at compile time) and we can fill it with UNDEFINED values.

    explicit DynamicPTransf(size_t n) : base_type() {
      resize(n, UNDEFINED);
    }

    DynamicPTransf& increase_degree_by(size_t m) {
      resize(degree() + m);
      std::iota(end() - m, end(), degree() - m);
      return *this;
    }
 
   protected:
    using base_type::resize;
  };

  // StaticPTransf

  template <size_t N, typename Scalar>
  class StaticPTransf : public PTransfBase<Scalar, std::array<Scalar, N>> {
    using base_type = PTransfBase<Scalar, std::array<Scalar, N>>;
 
   public:
    using point_type = Scalar;

    using container_type = std::array<Scalar, N>;
 
    using PTransfBase<point_type, container_type>::PTransfBase;
    using base_type::begin;
    using base_type::end;

    StaticPTransf() : base_type() {
      std::fill(begin(), end(), UNDEFINED);
    }

    explicit StaticPTransf(size_t n);

    StaticPTransf& increase_degree_by(size_t) {
      // do nothing can't increase the degree
      LIBSEMIGROUPS_EXCEPTION("cannot increase the degree of a StaticPTransf!");
      return *this;
    }
  };

  // PTransf

  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  using PTransf = std::
      conditional_t<N == 0, DynamicPTransf<Scalar>, StaticPTransf<N, Scalar>>;
 
  namespace detail {
    template <typename T>
    struct IsPTransfHelper : std::false_type {};
 
    template <typename Scalar>
    struct IsPTransfHelper<DynamicPTransf<Scalar>> : std::true_type {};
 
    template <size_t N, typename Scalar>
    struct IsPTransfHelper<StaticPTransf<N, Scalar>> : std::true_type {};
 
    template <size_t N, typename Scalar>
    struct IsStaticHelper<StaticPTransf<N, Scalar>> : std::true_type {};
 
    template <typename Scalar>
    struct IsDynamicHelper<DynamicPTransf<Scalar>> : std::true_type {};
 
  }  // namespace detail

  template <typename T>
  static constexpr bool IsPTransf = detail::IsPTransfHelper<T>::value;

  // TODO(1) to tpp
  template <typename Scalar, typename Container>
  void
  throw_if_image_value_out_of_range(PTransfBase<Scalar, Container> const& f) {
    size_t const M = f.degree();
    for (auto const& val : f) {
      // the type of "val" is an unsigned int, and so we don't check for val
      // being less than 0
      if (val >= M && val != UNDEFINED) {
        LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
                                "[{}, {}), found {}",
                                0,
                                M,
                                val);
      }
    }
  }

  // Transf

  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  class Transf : public PTransf<N, Scalar> {
    using base_type = PTransf<N, Scalar>;
 
   public:
    using point_type = Scalar;

    using container_type = typename base_type::container_type;
 
    using PTransf<N, Scalar>::PTransf;
    using base_type::degree;

    void product_inplace(Transf const& f, Transf const& g);

    [[nodiscard]] static Transf one(size_t M) {
      return base_type::template one<Transf>(M);
    }
  };
 
  namespace detail {
    template <typename T>
    struct IsTransfHelper : std::false_type {};
 
    template <size_t N, typename Scalar>
    struct IsTransfHelper<Transf<N, Scalar>> : std::true_type {};
 
    template <size_t N, typename Scalar>
    struct IsStaticHelper<Transf<N, Scalar>>
        : IsStaticHelper<PTransf<N, Scalar>> {};
 
    template <size_t N, typename Scalar>
    struct IsDynamicHelper<Transf<N, Scalar>>
        : IsDynamicHelper<PTransf<N, Scalar>> {};
  }  // namespace detail

  // Transf helpers

  template <typename T>
  static constexpr bool IsTransf = detail::IsTransfHelper<T>::value;

  // Transf throw_if_image_value_out_of_range

  template <size_t N, typename Scalar>
  void throw_if_image_value_out_of_range(Transf<N, Scalar> const& f);

  // make<Transf>


  template <typename Return, typename OtherContainer>
  [[nodiscard]] std::enable_if_t<IsTransf<Return>, Return>
  make(OtherContainer&& cont) {
    return Return::template make<Return>(std::forward<OtherContainer>(cont));
  }

  template <typename Return, typename OtherScalar>
  [[nodiscard]] std::enable_if_t<IsTransf<Return>, Return>
  make(std::initializer_list<OtherScalar> cont) {
    return make<Return, std::initializer_list<OtherScalar>>(std::move(cont));
  }

  // PPerm

  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  class PPerm : public PTransf<N, Scalar> {
    using base_type = PTransf<N, Scalar>;
 
   public:
    using point_type = Scalar;

    using container_type = typename base_type::container_type;
 
    using PTransf<N, point_type>::PTransf;
    using base_type::degree;
    using base_type::undef;

    //
    // Note: we use vectors here not container_type (which might be array),
    // because the length of dom and img might not equal degree().
    // Also we don't use a universal reference because we can't actually use an
    // rvalue reference here (we don't store dom or img).
    template <typename OtherScalar>
    PPerm(std::vector<OtherScalar> const& dom,
          std::vector<OtherScalar> const& img,
          size_t                          M);

    PPerm(std::initializer_list<point_type> dom,
          std::initializer_list<point_type> img,
          size_t                            M)
        : PPerm(std::vector<point_type>(dom), std::vector<point_type>(img), M) {
    }

    void product_inplace(PPerm const& f, PPerm const& g);

    [[nodiscard]] static PPerm one(size_t M) {
      return base_type::template one<PPerm>(M);
    }
  };
 
  namespace detail {
    template <
        size_t N        = 0,
        typename Scalar = std::
            conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
    void throw_if_bad_args(std::vector<Scalar> const& dom,
                           std::vector<Scalar> const& ran,
                           size_t                     deg = N);

    // PPerm helpers
 
    template <typename T>
    struct IsPPermHelper : std::false_type {};
 
    template <size_t N, typename Scalar>
    struct IsPPermHelper<PPerm<N, Scalar>> : std::true_type {};
 
    template <size_t N, typename Scalar>
    struct IsStaticHelper<PPerm<N, Scalar>>
        : IsStaticHelper<PTransf<N, Scalar>> {};
 
    template <size_t N, typename Scalar>
    struct IsDynamicHelper<PPerm<N, Scalar>>
        : IsDynamicHelper<PTransf<N, Scalar>> {};
  }  // namespace detail

  template <typename T>
  static constexpr bool IsPPerm = detail::IsPPermHelper<T>::value;

  // PPerm check

  template <size_t N, typename Scalar>
  void throw_if_not_pperm(PPerm<N, Scalar> const& f) {
    throw_if_image_value_out_of_range(f);
    detail::throw_if_duplicates(f.begin(), f.end());
  }

  // make<PPerm>


  template <typename Return, typename OtherContainer>
  [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
  make(OtherContainer&& cont) {
    return Return::template make<Return>(std::forward<OtherContainer>(cont));
  }

  template <typename Return>
  [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
  make(std::initializer_list<typename Return::point_type> cont) {
    return make<Return, std::initializer_list<typename Return::point_type>>(
        std::move(cont));
  }

  template <typename Return>
  [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
  make(std::vector<typename Return::point_type> const& dom,
       std::vector<typename Return::point_type> const& ran,
       size_t                                          M);

  template <typename Return>
  [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
  make(std::initializer_list<typename Return::point_type> dom,
       std::initializer_list<typename Return::point_type> ran,
       size_t                                             M) {
    return make<Return>(std::vector<typename Return::point_type>(dom),
                        std::vector<typename Return::point_type>(ran),
                        M);
  }

  // Perm

  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  class Perm : public Transf<N, Scalar> {
    using base_type = PTransf<N, Scalar>;
 
   public:
    using point_type = Scalar;

    using container_type = typename PTransf<N, point_type>::container_type;
 
    using Transf<N, Scalar>::Transf;
    using base_type::degree;

    [[nodiscard]] static Perm one(size_t M) {
      return base_type::template one<Perm>(M);
    }
  };

  // Perm helpers
 
  namespace detail {
    template <typename T>
    struct IsPermHelper : std::false_type {};
 
    template <size_t N, typename Scalar>
    struct IsPermHelper<Perm<N, Scalar>> : std::true_type {};
  }  // namespace detail

  template <typename T>
  static constexpr bool IsPerm = detail::IsPermHelper<T>::value;

  // Perm throw_if_not_perm

  template <size_t N, typename Scalar>
  auto throw_if_not_perm(Perm<N, Scalar> const& f) {
    throw_if_image_value_out_of_range(f);
    detail::throw_if_duplicates(f.begin(), f.end());
  }

  // make<Perm>


  template <typename Return, typename OtherContainer>
  [[nodiscard]] std::enable_if_t<IsPerm<Return>, Return>
  make(OtherContainer&& cont) {
    return Return::template make<Return>(std::forward<OtherContainer>(cont));
  }

  template <typename Return>
  [[nodiscard]] std::enable_if_t<IsPerm<Return>, Return>
  make(std::initializer_list<typename Return::point_type> cont) {
    return make<Return, std::initializer_list<typename Return::point_type>>(
        std::move(cont));
  }

  // Helper functions

  template <typename T, typename Scalar>
  void image(T const& f, std::vector<Scalar>& im);

  template <typename T>
  [[nodiscard]] std::vector<typename T::point_type> image(T const& f);

  template <typename T, typename Scalar>
  void domain(T const& f, std::vector<Scalar>& dom);

  template <typename T>
  [[nodiscard]] std::vector<typename T::point_type> domain(T const& f);

  template <typename T>
  [[nodiscard]] auto one(T const& f)
      -> std::enable_if_t<IsDerivedFromPTransf<T>, T> {
    return T::one(f.degree());
  }

  template <size_t N, typename Scalar>
  [[nodiscard]] PPerm<N, Scalar> right_one(PPerm<N, Scalar> const& f);
  // TODO(1) void pass by reference version

  template <size_t N, typename Scalar>
  [[nodiscard]] PPerm<N, Scalar> left_one(PPerm<N, Scalar> const& f);
  // TODO(1) void pass by reference version

  // Put the inverse of this into that
  template <size_t N, typename Scalar>
  void inverse(PPerm<N, Scalar> const& from, PPerm<N, Scalar>& to);

  template <size_t N, typename Scalar>
  [[nodiscard]] PPerm<N, Scalar> inverse(PPerm<N, Scalar> const& f) {
    PPerm<N, Scalar> to(f.degree());
    inverse(f, to);
    return to;
  }

  template <size_t N, typename Scalar>
  void inverse(Perm<N, Scalar> const& from, Perm<N, Scalar>& to);

  template <size_t N, typename Scalar>
  [[nodiscard]] Perm<N, Scalar> inverse(Perm<N, Scalar> const& f);

  // Adapters
 
  template <typename T>
  struct Degree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    [[nodiscard]] constexpr size_t operator()(T const& x) const noexcept {
      return x.degree();
    }
  };
 
  template <typename T>
  struct One<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    [[nodiscard]] T operator()(T const& x) const {
      return (*this)(x.degree());
    }
 
    [[nodiscard]] T operator()(size_t N) const {
      return T::one(N);
    }
  };
 
  template <size_t N, typename Scalar>
  struct Inverse<Perm<N, Scalar>> {
    [[nodiscard]] Perm<N, Scalar> operator()(Perm<N, Scalar> const& x) {
      return inverse(x);
    }
  };
 
  template <typename Subclass>
  struct Product<Subclass, std::enable_if_t<IsDerivedFromPTransf<Subclass>>> {
    void
    operator()(Subclass& xy, Subclass const& x, Subclass const& y, size_t = 0) {
      xy.product_inplace(x, y);
    }
  };
 
  template <typename T>
  struct Hash<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    [[nodiscard]] constexpr size_t operator()(T const& x) const {
      return x.hash_value();
    }
  };
 
  template <typename T>
  struct Complexity<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    [[nodiscard]] constexpr size_t operator()(T const& x) const noexcept {
      return x.degree();
    }
  };

  template <typename T>
  struct IncreaseDegree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    inline void operator()(T& x, size_t n) const {
      x.increase_degree_by(n);
    }
  };

  // ImageRight/LeftAction - Transf
 
  // Equivalent to OnSets in GAP
  // Slowest
  // works for T = std::vector and T = StaticVector1
  template <size_t N, typename Scalar, typename T>
  struct ImageRightAction<Transf<N, Scalar>, T> {
    void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const;
  };
 
  // Fastest, but limited to at most degree 64
  template <size_t N, typename Scalar, size_t M>
  struct ImageRightAction<Transf<N, Scalar>, BitSet<M>> {
    void operator()(BitSet<M>&               res,
                    BitSet<M> const&         pt,
                    Transf<N, Scalar> const& x) const {
      res.reset();
      // Apply the lambda to every set bit in pt
      pt.apply([&x, &res](size_t i) { res.set(x[i]); });
    }
  };
 
  // OnKernelAntiAction
  // T = StaticVector1<S> or std::vector<S>
  template <size_t N, typename Scalar, typename T>
  struct ImageLeftAction<Transf<N, Scalar>, T> {
    void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const;
  };

  // Lambda/Rho - Transformation
 
  // This currently limits the use of Konieczny to transformation of degree at
  // most 64 with the default traits class, since we cannot know the degree at
  // compile time, only at run time.
  template <size_t N, typename Scalar>
  struct LambdaValue<Transf<N, Scalar>> {
    using type = BitSet<BitSet<1>::max_size()>;
  };
 
  // Benchmarks indicate that using std::vector yields similar performance to
  // using StaticVector1's.
  template <size_t N, typename Scalar>
  struct RhoValue<Transf<N, Scalar>> {
    using type = std::vector<Scalar>;
  };
 
  // T = std::vector or StaticVector1
  template <size_t N, typename Scalar, typename T>
  struct Lambda<Transf<N, Scalar>, T> {
    // not noexcept because std::vector::resize isn't (although
    // StaticVector1::resize is).
    void operator()(T& res, Transf<N, Scalar> const& x) const;
  };

  template <size_t N, typename Scalar, size_t M>
  struct Lambda<Transf<N, Scalar>, BitSet<M>> {
    // not noexcept because it can throw
    void operator()(BitSet<M>& res, Transf<N, Scalar> const& x) const;
  };
 
  // T = std::vector<S> or StaticVector1<S, N>
  template <size_t N, typename Scalar, typename T>
  struct Rho<Transf<N, Scalar>, T> {
    // not noexcept because std::vector::resize isn't (although
    // StaticVector1::resize is).
    void operator()(T& res, Transf<N, Scalar> const& x) const;
  };

  template <size_t N, typename Scalar>
  struct Rank<Transf<N, Scalar>> {
    [[nodiscard]] size_t operator()(Transf<N, Scalar> const& x) const {
      return x.rank();
    }
  };

  // ImageRight/LeftAction - PPerm
 
  // Slowest
  template <size_t N, typename Scalar>
  struct ImageRightAction<PPerm<N, Scalar>, PPerm<N, Scalar>> {
    void operator()(PPerm<N, Scalar>&       res,
                    PPerm<N, Scalar> const& pt,
                    PPerm<N, Scalar> const& x) const noexcept {
      LIBSEMIGROUPS_ASSERT(res.degree() == pt.degree());
      LIBSEMIGROUPS_ASSERT(res.degree() == x.degree());
      res.product_inplace(pt, x);
      res = right_one(res);
    }
  };
 
  // Faster than the above, but slower than the below
  // works for T = std::vector and T = StaticVector1
  template <size_t N, typename Scalar, typename T>
  struct ImageRightAction<PPerm<N, Scalar>, T> {
    void operator()(T& res, T const& pt, PPerm<N, Scalar> const& x) const;
  };
 
  // Fastest, but limited to at most degree 64
  template <size_t N, typename Scalar, size_t M>
  struct ImageRightAction<PPerm<N, Scalar>, BitSet<M>> {
    void operator()(BitSet<M>&              res,
                    BitSet<M> const&        pt,
                    PPerm<N, Scalar> const& x) const;
  };
 
  // Slowest
  template <size_t N, typename Scalar>
  struct ImageLeftAction<PPerm<N, Scalar>, PPerm<N, Scalar>> {
    void operator()(PPerm<N, Scalar>&       res,
                    PPerm<N, Scalar> const& pt,
                    PPerm<N, Scalar> const& x) const noexcept {
      res.product_inplace(x, pt);
      res = left_one(res);
    }
  };
 
  // Fastest when used with BitSet<N>.
  // works for T = std::vector and T = BitSet<N>
  // Using BitSet<N> limits this to size 64. However, if we are trying to
  // compute a LeftAction object, then the max size of such is 2 ^ 64, which
  // is probably not achievable. So, for higher degrees, we will only be able
  // to compute relatively sparse LeftActions (i.e. not containing the
  // majority of the 2 ^ n possible subsets), in which case using vectors or
  // StaticVector1's might be not be appreciable slower anyway. All of this is
  // to say that it probably isn't worthwhile trying to make BitSet's work for
  // more than 64 bits.
  template <size_t N, typename Scalar, typename T>
  struct ImageLeftAction<PPerm<N, Scalar>, T> {
    void operator()(T& res, T const& pt, PPerm<N, Scalar> const& x) const {
      static PPerm<N, Scalar> xx(x.degree());
      inverse(x, xx);  // invert x into xx
      ImageRightAction<PPerm<N, Scalar>, T>()(res, pt, xx);
    }
  };

  // Lambda/Rho - PPerm
 
  // This currently limits the use of Konieczny to partial perms of degree at
  // most 64 with the default traits class, since we cannot know the degree
  // at compile time, only at run time.
  template <size_t N, typename Scalar>
  struct LambdaValue<PPerm<N, Scalar>> {
    using type = BitSet<BitSet<1>::max_size()>;
  };

  template <size_t N, typename Scalar>
  struct RhoValue<PPerm<N, Scalar>> {
    using type = typename LambdaValue<PPerm<N, Scalar>>::type;
  };

  template <size_t N, typename Scalar, size_t M>
  struct Lambda<PPerm<N, Scalar>, BitSet<M>> {
    void operator()(BitSet<M>& res, PPerm<N, Scalar> const& x) const;
  };

  template <size_t N, typename Scalar, size_t M>
  struct Rho<PPerm<N, Scalar>, BitSet<M>> {
    void operator()(BitSet<M>& res, PPerm<N, Scalar> const& x) const;
  };

  template <size_t N, typename Scalar>
  struct Rank<PPerm<N, Scalar>> {
    [[nodiscard]] size_t operator()(PPerm<N, Scalar> const& x) const {
      return x.rank();
    }
  };

  // Perm

  // TODO(later) this could work for everything derived from PTransf
  template <size_t N, typename Scalar, typename T>
  struct ImageRightAction<Perm<N, Scalar>,
                          T,
                          std::enable_if_t<std::is_integral_v<T>>> {
    void operator()(T&                     res,
                    T const&               pt,
                    Perm<N, Scalar> const& p) const noexcept {
      LIBSEMIGROUPS_ASSERT(pt < p.degree());
      res = p[pt];
    }

    [[nodiscard]] T operator()(T pt, Perm<N, Scalar> const& x) {
      return x[pt];
    }
  };

  // Helpers
 
  namespace detail {
    template <size_t N>
    struct LeastTransfHelper {
#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
      using type = std::conditional_t<N >= 17, Transf<N>, HPCombi::Transf16>;
#else
      using type = Transf<N>;
#endif
    };
 
    template <size_t N>
    struct LeastPPermHelper {
#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
      using type = std::conditional_t<N >= 17, PPerm<N>, HPCombi::PPerm16>;
#else
      using type = PPerm<N>;
#endif
    };
 
    template <size_t N>
    struct LeastPermHelper {
#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
      using type = std::conditional_t<N >= 17, Perm<N>, HPCombi::Perm16>;
#else
      using type = Perm<N>;
#endif
    };
  }  // namespace detail

  template <size_t N>
  using LeastTransf = typename detail::LeastTransfHelper<N>::type;

  template <size_t N>
  using LeastPPerm = typename detail::LeastPPermHelper<N>::type;

  template <size_t N>
  using LeastPerm = typename detail::LeastPermHelper<N>::type;

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_input_string(Transf<N, Scalar> const& x,
                                            std::string_view prefix = "",
                                            std::string_view braces = "{}");

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_input_string(Perm<N, Scalar> const& x,
                                            std::string_view       prefix = "",
                                            std::string_view braces = "{}");

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_input_string(PPerm<N, Scalar> const& x,
                                            std::string_view        prefix = "",
                                            std::string_view braces = "{}");

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_human_readable_repr(Transf<N, Scalar> const& x,
                                                   std::string_view prefix = "",
                                                   std::string_view braces
                                                   = "{}",
                                                   size_t max_width = 72);

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_human_readable_repr(Perm<N, Scalar> const& x,
                                                   std::string_view prefix = "",
                                                   std::string_view braces
                                                   = "{}",
                                                   size_t max_width = 72);

  template <size_t N, typename Scalar>
  [[nodiscard]] std::string to_human_readable_repr(PPerm<N, Scalar> const& x,
                                                   std::string_view prefix = "",
                                                   std::string_view braces
                                                   = "{}",
                                                   size_t max_width = 72);
}  // namespace libsemigroups
 
#include "transf.tpp"
 
#endif  // LIBSEMIGROUPS_TRANSF_HPP_