Quelle  transf.hpp   Sprache: C

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2021 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

#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_set>     // for unordered_set
#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 "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "hpcombi.hpp"    // for HPCombi::Transf16
#include "types.hpp"      // for SmallestInteger

namespace libsemigroups {

  //! Empty base class for polymorphism.
  //!
  //! \sa IsDerivedFromPTransf
  struct PTransfPolymorphicBase {};

  namespace detail {
    template <typename T>
    struct IsDerivedFromPTransfHelper final {
      static constexpr bool value
          = std::is_base_of<PTransfPolymorphicBase, T>::value;
    };
  }  // namespace detail

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! derived from PTransfPolymorphicBase.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsDerivedFromPTransf
      = detail::IsDerivedFromPTransfHelper<T>::value;

  namespace detail {

    template <typename... Args>
    struct IsStdArray final : std::false_type {};

    template <typename T, size_t N>
    struct IsStdArray<std::array<T, N>> final : std::true_type {};

    template <typename T>
    struct IsStaticHelper : std::false_type {};

    template <typename T>
    struct IsDynamicHelper : std::false_type {};

    //! Base class for partial transformations.
    //!
    //! This is a class template for partial transformations.
    //!
    //! \tparam TValueType the type of image values (must be an unsigned integer
    //! type).
    //! \tparam TContainer the type of the container holding the image values.
    //!
    //! A *partial transformation* \f$f\f$ is just a function defined on a
    //! subset of \f$\{0, 1, \ldots, n - 1\}\f$ for some integer \f$n\f$ called
    //! the *degree*  of *f*.  A partial transformation is stored as a vector
    //! of the images of \f$\{0, 1, \ldots, n -1\}\f$, i.e. \f$\{(0)f, (1)f,
    //! \ldots, (n - 1)f\}\f$ where the value \ref UNDEFINED is used to
    //! indicate that \f$(i)f\f$ is, you guessed it, undefined (i.e. not among
    //! the points where \f$f\f$ is defined).
    template <typename TValueType, typename TContainer>
    class PTransfBase : public PTransfPolymorphicBase {
      static_assert(std::is_integral<TValueType>::value,
                    "template parameter TValueType must be an integral type");
      static_assert(!std::numeric_limits<TValueType>::is_signed,
                    "template parameter TValueType must be unsigned");

     public:
      //! Type of the image values.
      //!
      //! Also the template parameter \c Scalar.
      using value_type = TValueType;

      //! Type of the underlying container.
      //!
      //! In this case, this is `std::vector<value_type>`.
      using container_type = TContainer;

      // Required by python bindings
      //! Returns the value used to represent \"undefined\".
      //!
      //! This static function returns the value of type \ref value_type used to
      //! represent an \"undefined\" value.
      //!
      //! \parameters
      //! (None)
      //!
      //! \returns
      //! A value of type \ref value_type.
      //!
      //! \exception
      //! \noexcept
      static value_type undef() noexcept {
        return static_cast<value_type>(UNDEFINED);
      }

      //! Default constructor.
      //!
      //! Constructs an uninitialized partial transformation of degree \c 0.
      //!
      //! \parameters
      //! (None)
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Constant.
      PTransfBase() = default;

      //! Construct from container.
      //!
      //! Constructs an partial transformation initialized using the
      //! container \p cont as follows: the image of the point \c i under
      //! the partial transformation is the value in position \c i of the
      //! container \p cont.
      //!
      //! \param cont the container.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in the size of the container \p cont.
      //!
      //! \warning
      //! No checks on the validity of \p cont are performed.
      explicit PTransfBase(TContainer&& cont) : _container(std::move(cont)) {}

      //! Construct from container.
      //!
      //! Constructs an partial transformation initialized using the
      //! container \p cont as follows: the image of the point \c i under
      //! the partial transformation is the value in position \c i of the
      //! container \p cont.
      //!
      //! \param cont the container.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in the size of the container \p cont.
      //!
      //! \warning
      //! No checks on the validity of \p cont are performed.
      explicit PTransfBase(TContainer const& cont) : _container(cont) {}

      //! Construct from an initializer list.
      //!
      //! Constructs an partial transformation initialized using the
      //! container \p cont as follows: the image of the point \c i under
      //! the partial transformation is the value in position \c i of the
      //! container \p cont. The values in the initializer list must be
      //! convertible to value_type or equal to \ref UNDEFINED.
      //!
      //! \param cont the initializer list.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in the size of the initializer list \p cont.
      //!
      //! \warning
      //! No checks on the validity of \p cont are performed.
      //!
      //! \sa
      //! \ref make
      template <typename T>
      explicit PTransfBase(std::initializer_list<T> cont) : PTransfBase() {
        static_assert(std::is_same<T, Undefined>::value
                          || std::is_convertible<T, value_type>::value,
                      "the template parameter T must be Undefined or "
                      "convertible to value_type!");
        resize(_container, cont.size());
        std::copy(cont.begin(), cont.end(), _container.begin());
      }

      //! Construct from a container and validates.
      //!
      //! Constructs an partial transformation initialized using the
      //! container \p cont as follows: the image of the point \c i under
      //! the partial transformation is the value in position \c i of the
      //! container \p cont.
      //!
      //! \param cont the container.
      //!
      //! \throw LibsemigroupsException if any of the following hold:
      //! * the size of \p cont is incompatible with \ref container_type.
      //! * any value in \p cont exceeds `cont.size()` and is not equal to
      //!   libsemigroups::UNDEFINED.
      //!
      //! \complexity
      //! Linear in the size of the container \p cont.
      template <typename TSubclass, typename TContainerAgain = TContainer>
      static TSubclass make(TContainerAgain&& cont) {
        validate_args(std::forward<TContainerAgain>(cont));
        TSubclass result(std::forward<TContainerAgain>(cont));
        validate(result);
        return result;
      }

      //! Construct from an initializer list.
      //!
      //! \sa
      //! \ref make
      template <typename TSubclass>
      static TSubclass make(std::initializer_list<value_type> const& cont) {
        return PTransfBase::make<TSubclass, std::initializer_list<value_type>>(
            cont);
      }

      //! Default copy constructor
      PTransfBase(PTransfBase const&) = default;

      //! Default move constructor
      PTransfBase(PTransfBase&&) = default;

      //! Default copy assignment operator.
      PTransfBase& operator=(PTransfBase const&) = default;

      //! Default move assignment operator.
      PTransfBase& operator=(PTransfBase&&) = default;

      //! Compare for less.
      //!
      //! Returns \c true if `*this` is less than \p that by comparing the
      //! image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator<(PTransfBase const& that) const {
        return this->_container < that._container;
      }

      //! Compare for greater.
      //!
      //! Returns \c true if `*this` is greater than \p that by comparing the
      //! image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator>(PTransfBase const& that) const {
        return that < *this;
      }

      //! Compare for equality.
      //!
      //! Returns \c true if `*this` equals \p that by comparing the
      //! image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator==(PTransfBase const& that) const {
        return this->_container == that._container;
      }

      //! Compare for less than or equal.
      //!
      //! Returns \c true if `*this` is less than or equal to \p that by
      //! comparing the image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator<=(PTransfBase const& that) const {
        return this->_container < that._container
               || this->_container == that._container;
      }

      //! Compare for greater than or equal.
      //!
      //! Returns \c true if `*this` is greater than or equal to \p that by
      //! comparing the image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator>=(PTransfBase const& that) const {
        return that <= *this;
      }

      //! Compare for inequality.
      //!
      //! Returns \c true if `*this` does not equal \p that by comparing the
      //! image values of `*this` and \p that.
      //!
      //! \param that the partial transformation for comparison.
      //!
      //! \returns
      //! A value of type \c bool.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! At worst linear in degree().
      bool operator!=(PTransfBase const& that) const {
        return !(*this == that);
      }

      //! Get a reference to the image of a point.
      //!
      //! Returns a reference to the image of \p i.
      //!
      //! \param i the point.
      //!
      //! \returns
      //! A reference to a \ref value_type.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant.
      //!
      //! \warning
      //! No bound checks are performed on \p i.
      value_type& operator[](size_t i) {
        return _container[i];
      }

      //! Get a const reference to the image of a point.
      //!
      //! Returns a const reference to the image of \p i.
      //!
      //! \param i the point.
      //!
      //! \returns
      //! A const reference to a \ref value_type.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \complexity
      //! Constant.
      //!
      //! \warning
      //! No bound checks are performed on \p i.
      value_type const& operator[](size_t i) const {
        return _container[i];
      }

      //! Get a reference to the image of a point.
      //!
      //! Returns a reference to the image of \p i.
      //!
      //! \param i the point.
      //!
      //! \returns
      //! A reference to a \ref value_type.
      //!
      //! \throws std::out_of_range if \p i is out of range.
      //!
      //! \complexity
      //! Constant.
      value_type& at(size_t i) {
        return _container.at(i);
      }

      //! Get a const reference to the image of a point.
      //!
      //! Returns a const reference to the image of \p i.
      //!
      //! \param i the point.
      //!
      //! \returns
      //! A const reference to a \ref value_type.
      //!
      //! \throws std::out_of_range if \p i is out of range.
      //!
      //! \complexity
      //! Constant.
      value_type const& at(size_t i) const {
        return _container.at(i);
      }

      //! Multiply by another partial transformation.
      //!
      //! Returns a newly constructed partial transformation holding the
      //! product of `*this` and `that`.
      //!
      //! \tparam TSubclass
      //! A class derived from libsemigroups::PTransfPolymorphicBase.
      //!
      //! \param that a partial transformation.
      //!
      //! \returns
      //! A value of type \c TSubclass
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in degree().
      // TODO(later) other operators
      template <typename TSubclass>
      TSubclass operator*(TSubclass const& that) const {
        static_assert(IsDerivedFromPTransf<TSubclass>,
                      "the template parameter TSubclass must be derived from "
                      "PTransfPolymorphicBase");
        TSubclass xy(that.degree());
        xy.product_inplace(*static_cast<TSubclass const*>(this), that);
        return xy;
      }

      //! Type of iterators point to image values.
      using iterator = typename TContainer::iterator;

      //! Type of const iterators point to image values.
      using const_iterator = typename TContainer::const_iterator;

      //! Returns a \ref const_iterator (random access
      //! iterator) pointing at the first image value.
      //!
      //! \returns
      //! A const iterator to the first image value.
      //!
      //! \complexity
      //! Constant.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      const_iterator cbegin() const noexcept {
        return _container.cbegin();
      }

      //! Returns a \ref const_iterator (random access
      //! iterator) pointing one past the last image value.
      //!
      //! \returns
      //! A const iterator pointing one past the last image value.
      //!
      //! \complexity
      //! Constant.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      const_iterator cend() const noexcept {
        return _container.cend();
      }

      //! \copydoc cbegin()
      const_iterator begin() const noexcept {
        return _container.begin();
      }

      //! \copydoc cend()
      const_iterator end() const noexcept {
        return _container.end();
      }

      //! Returns an \ref iterator (random access iterator) pointing at the
      //! first image value.
      //!
      //! \returns
      //! An iterator to the first image value.
      //!
      //! \complexity
      //! Constant.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      iterator begin() noexcept {
        return _container.begin();
      }

      //! Returns an \ref iterator (random access
      //! iterator) pointing one past the last image value.
      //!
      //! \returns
      //! An iterator pointing one past the last image value.
      //!
      //! \complexity
      //! Constant.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      iterator end() noexcept {
        return _container.end();
      }

      //! Returns the number of distinct image values.
      //!
      //! The *rank* of a partial transformation is the number of its distinct
      //! image values, not including \ref libsemigroups::UNDEFINED.
      //!
      //! \returns
      //! A value of type \c size_t.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in degree().
      //!
      //! \par Parameters
      //! (None)
      size_t rank() const {
        auto vals
            = std::unordered_set<value_type>(this->cbegin(), this->cend());
        return (vals.find(UNDEFINED) == vals.end() ? vals.size()
                                                   : vals.size() - 1);
      }

      //! Returns a hash value.
      //!
      //! \returns
      //! A value of type \c size_t.
      //!
      //! \exceptions
      //! \no_libsemigroups_except_detail
      //!
      //! \complexity
      //! Linear in degree().
      //!
      //! \par Parameters
      //! (None)
      // not noexcept because Hash<T>::operator() isn't
      size_t hash_value() const {
        return Hash<TContainer>()(_container);
      }

      //! Swap with another partial transformation.
      //!
      //! \param that the partial transformation to swap with.
      //!
      //! \returns
      //! (None)
      //!
      //! \exceptions
      //! \noexcept
      void swap(PTransfBase& that) noexcept {
        std::swap(this->_container, that._container);
      }

      //! Returns the degree of a partial transformation.
      //!
      //! The *degree* of a partial transformation is the number of points used
      //! in its definition, which is equal to the size of the underlying
      //! container.
      //!
      //! \returns
      //! A value of type \c size_t.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      size_t degree() const noexcept {
        return _container.size();
      }

      //! Returns the identity transformation on degree() points.
      //!
      //! This function returns a newly constructed partial transformation with
      //! degree equal to the degree of \c this that fixes every value from \c 0
      //! to degree().
      //!
      //! \tparam TSubclass
      //! A class derived from libsemigroups::PTransfPolymorphicBase.
      //!
      //! \returns
      //! A value of type \c TSubclass.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      template <typename TSubclass>
      TSubclass identity() const {
        static_assert(IsDerivedFromPTransf<TSubclass>,
                      "the template parameter TSubclass must be derived from "
                      "PTransfPolymorphicBase");
        return identity<TSubclass>(degree());
      }

      //! Returns the identity transformation on the given number of points.
      //!
      //! This function returns a newly constructed partial transformation with
      //! degree equal to the degree of \c this that fixes every value from \c 0
      //! to degree().
      //!
      //! \tparam TSubclass
      //! A class derived from libsemigroups::PTransfPolymorphicBase.
      //!
      //! \returns
      //! A value of type \c TSubclass.
      //!
      //! \exceptions
      //! \noexcept
      //!
      //! \par Parameters
      //! (None)
      template <typename TSubclass>
      static TSubclass identity(size_t N) {
        static_assert(IsDerivedFromPTransf<TSubclass>,
                      "the template parameter TSubclass must be derived from "
                      "PTransfPolymorphicBase");
        TSubclass result(N);
        std::iota(result.begin(), result.end(), 0);
        return result;
      }

     protected:
      //! No doc
      template <typename SFINAE = void>
      static auto resize(container_type& c, size_t N, value_type val = 0)
          -> std::enable_if_t<detail::IsStdArray<container_type>::value,
                              SFINAE> {
        std::fill(c.begin() + N, c.end(), val);
      }

      //! No doc
      template <typename SFINAE = void>
      static auto resize(container_type& c, size_t N, value_type val = 0)
          -> std::enable_if_t<!detail::IsStdArray<container_type>::value,
                              SFINAE> {
        c.resize(N, val);
      }

      //! No doc
      void resize(size_t N, value_type val = 0) {
        resize(_container, N, val);
      }

     private:
      template <typename T, typename SFINAE = void>
      static auto validate_args(T const& cont)
          -> std::enable_if_t<detail::IsStdArray<container_type>::value,
                              SFINAE> {
        if (cont.size() != std::tuple_size<container_type>::value) {
          LIBSEMIGROUPS_EXCEPTION(
              "incorrect container size, expected %llu, found %llu",
              uint64_t(std::tuple_size<container_type>::value),
              uint64_t(cont.size()));
        }
      }

      template <typename T, typename SFINAE = void>
      static auto validate_args(T const&)
          -> std::enable_if_t<!detail::IsStdArray<container_type>::value,
                              SFINAE> {}
      TContainer _container;
    };
  }  // namespace detail

  ////////////////////////////////////////////////////////////////////////
  // Helper variable templates
  ////////////////////////////////////////////////////////////////////////

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! derived from StaticPTransf.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsStatic = detail::IsStaticHelper<T>::value;

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! derived from DynamicPTransf.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsDynamic = detail::IsDynamicHelper<T>::value;

  ////////////////////////////////////////////////////////////////////////
  // DynamicPTransf
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! Dynamic partial transformations.
  //!
  //! This is a class for partial transformations where the number of points
  //! acted on (the degree) can be set at run time.
  //!
  //! \tparam Scalar a unsigned integer type.
  template <typename Scalar>
  class DynamicPTransf
      : public detail::PTransfBase<Scalar, std::vector<Scalar>> {
    using base_type = detail::PTransfBase<Scalar, std::vector<Scalar>>;

   public:
    //! Type of the image values.
    //!
    //! Also the template parameter \c Scalar.
    using value_type = Scalar;

    //! Type of the underlying container.
    //!
    //! In this case, this is `std::vector<value_type>`.
    using container_type = std::vector<value_type>;

    // TODO(later) This is currently undocumentable. The doc is available in
    // PTransfBase but they aren't present in the doxygen xml output.
    using detail::PTransfBase<value_type, container_type>::PTransfBase;

    //! \copydoc detail::PTransfBase<value_type, container_type>::begin
    using base_type::begin;

    //! Returns the degree of a transformation.
    //!
    //! The *degree* of a transformation is the number of points used
    //! in its definition, which is equal to the size of the underlying
    //! container.
    //!
    //! \returns
    //! A value of type \c size_t.
    //!
    //! \exceptions
    //! \noexcept
    //!
    //! \par Parameters
    //! (None)
    using base_type::degree;

    //! \copydoc detail::PTransfBase<value_type, container_type>::end
    using base_type::end;

    //! Construct with given degree.
    //!
    //! Constructs a partial transformation of degree \p n with the image of
    //! every point set to \ref UNDEFINED.
    //!
    //! \param n the degree
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in the parameter \p n.
    explicit DynamicPTransf(size_t n) : base_type() {
      resize(n, UNDEFINED);
    }

    //! Increase the degree in-place.
    //!
    //! Increases the degree of \c this in-place, leaving existing values
    //! unaltered.
    //!
    //! \param m the number of points to add.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! At worst linear in the sum of the parameter \p m and degree().
    void increase_degree_by(size_t m) {
      resize(degree() + m);
      std::iota(end() - m, end(), degree() - m);
    }

   protected:
    using base_type::resize;
  };

  ////////////////////////////////////////////////////////////////////////
  // StaticPTransf
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! Static partial transformations.
  //!
  //! This is a class for partial transformations where the number of points
  //! acted on (the degree) is set at compile time.
  //!
  //! \tparam Scalar an unsigned integer type.
  template <size_t N, typename Scalar>
  class StaticPTransf
      : public detail::PTransfBase<Scalar, std::array<Scalar, N>> {
    using base_type = detail::PTransfBase<Scalar, std::array<Scalar, N>>;

   public:
    //! \copydoc detail::PTransfBase::value_type
    using value_type = Scalar;

    //! Type of the underlying container.
    //!
    //! In this case, this is `std::array<value_type, N>`.
    using container_type = std::array<Scalar, N>;

    // TODO(later) This is currently undocumentable. The doc is available in
    // PTransfBase but they aren't present in the doxygen xml output.
    using detail::PTransfBase<value_type, container_type>::PTransfBase;

    //! \copydoc detail::PTransfBase<value_type, container_type>::begin
    using base_type::begin;

    //! \copydoc detail::PTransfBase<value_type, container_type>::end
    using base_type::end;

    //! Default constructor.
    //!
    //! Constructs a partial transformation of degree equal to the template
    //! parameter \p N with the image of every point set to \ref UNDEFINED.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in the template parameter \p N.
    explicit StaticPTransf(size_t = 0) : base_type() {
      std::fill(begin(), end(), UNDEFINED);
    }

    //! \copydoc detail::PTransfBase<Scalar,TContainer>::degree
    constexpr size_t degree() const noexcept {
      return N;
    }

    //! Increase the degree in-place.
    //!
    //! This doesn't make sense for this type, and it throws every time.
    //!
    //! \throws LibsemigroupsException every time.
    void increase_degree_by(size_t) {
      // do nothing can't increase the degree
      LIBSEMIGROUPS_EXCEPTION("cannot increase the degree of a StaticPTransf!");
    }
  };

  ////////////////////////////////////////////////////////////////////////
  // PTransf
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! This alias equals either DynamicPTransf or StaticPTransf depending on the
  //! template parameters \p N and \p Scalar.
  //!
  //! If \p N is \c 0 (the default), then \c PTransf is \ref
  //! DynamicPTransf. In this case the default value of \p Scalar is \c
  //! uint32_t. If \p N is not \c 0, then \c PTransf is \ref StaticPTransf,
  //! and the default value of \p Scalar is the smallest integer type able to
  //! hold \c N. See also SmallestInteger.
  //!
  //! \tparam N  the degree (default: \c 0)
  //! \tparam Scalar an unsigned integer type (the type of the image values)
  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

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! either \ref DynamicPTransf or \ref StaticPTransf for any template
  //! parameters.
  //!
  //! \tparam T a type.
  // TODO(later) add doc link to IsStatic/IsDynamic (tried but it didn't work
  // on 15/03/2021)
  template <typename T>
  static constexpr bool IsPTransf = detail::IsPTransfHelper<T>::value;

  //! Check that a partial transformation is valid.
  //!
  //! \tparam N  the degree
  //! \tparam Scalar an unsigned integer type (the type of the image values)
  //!
  //! \param x a const reference to the partial transformation to validate.
  //!
  //! \returns
  //! (None)
  //!
  //! \throw LibsemigroupsException if any of the following hold:
  //! * the size of \p cont is incompatible with `T::container_type`.
  //! * any value in \p cont exceeds `cont.size()` and is not equal to \ref
  //!   libsemigroups::UNDEFINED.
  //!
  //! \complexity
  //! Linear in degree().
  template <typename T>
  auto validate(T const& x) -> std::enable_if_t<IsPTransf<T>> {
    size_t const M = x.degree();
    for (auto const& val : x) {
      // 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 "
                                "[%llu, %llu), found %llu",
                                uint64_t(0),
                                uint64_t(M),
                                uint64_t(val));
      }
    }
  }

  ////////////////////////////////////////////////////////////////////////
  // Transf
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! A *transformation* \f$f\f$ is just a function defined on the
  //! whole of \f$\{0, 1, \ldots, n - 1\}\f$ for some integer \f$n\f$
  //! called the *degree* of \f$f\f$.  A transformation is stored as a
  //! vector of the images of \f$\{0, 1, \ldots, n - 1\}\f$, i.e.
  //! \f$\{(0)f, (1)f, \ldots, (n - 1)f\}\f$.
  //!
  //! If \p N is \c 0 (the default), then the degree of a \ref Transf instance
  //! can be defined at runtime, and if \p N is not \c 0, then the degree is
  //! fixed at compile time.
  //!
  //! If \p N is \c 0, then the default value of \p Scalar is \c uint32_t. If
  //! \p N is not \c 0, then the default value of \p Scalar is the smallest
  //! integer type able to hold \c N. See also SmallestInteger.
  //!
  //! \tparam N  the degree (default: \c 0)
  //! \tparam Scalar an unsigned integer type (the type of the image values)
  //!
  //! \note
  //! Transf has the same member functions as
  //! \ref StaticPTransf and \ref DynamicPTransf, this isn't currently
  //! reflected by the contents of this page.
  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:
    //! Type of the image values.
    //!
    //! Also the template parameter \c Scalar.
    using value_type = Scalar;

    //! Type of the underlying container.
    //!
    //! In this case, this is PTransf<N, Scalar>::container_type.
    using container_type = typename base_type::container_type;

    using PTransf<N, Scalar>::PTransf;

    //! tESTING
    using base_type::degree;

    //! Construct from a container and validate.
    //!
    //! Constructs an transformation initialized using the
    //! container \p cont as follows: the image of the point \c i under
    //! the transformation is the value in position \c i of the container \p
    //! cont.
    //!
    //! \tparam T the type of the container \p cont.
    //!
    //! \param cont the container.
    //!
    //! \throw LibsemigroupsException if any of the following hold:
    //! * the size of \p cont is incompatible with \ref container_type.
    //! * any value in \p cont exceeds `cont.size()` or is equal to \ref
    //!    UNDEFINED.
    //!
    //! \complexity
    //! Linear in the size of the container \p cont.
    template <typename T>
    static Transf make(T&& cont) {
      return base_type::template make<Transf>(std::forward<T>(cont));
    }

    //! Construct from a container and validate.
    //!
    //! \sa \ref make
    static Transf make(std::initializer_list<value_type>&& cont) {
      return make<std::initializer_list<value_type>>(std::move(cont));
    }

    //! Multiply two transformations and store the product in \c this.
    //!
    //! Replaces the contents of \c this by the product of \p x and \p y.
    //!
    //! \param x a transformation.
    //! \param y a transformation.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in PTransf::degree.
    //!
    //! \warning
    //! No checks are made on whether or not the parameters are compatible. If
    //! \p x and \p y have different degrees, then bad things will happen.
    void product_inplace(Transf const& x, Transf const& y) {
      LIBSEMIGROUPS_ASSERT(x.degree() == y.degree());
      LIBSEMIGROUPS_ASSERT(x.degree() == this->degree());
      LIBSEMIGROUPS_ASSERT(&x != this && &y != this);
      size_t const n = this->degree();
      for (value_type i = 0; i < n; ++i) {
        (*this)[i] = y[x[i]];
      }
    }

    //! Returns the identity transformation on degree() points.
    //!
    //! This function returns a newly constructed transformation with
    //! degree equal to the degree of \c this that fixes every value from \c 0
    //! to degree().
    //!
    //! \returns
    //! A value of type \c Transf.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    Transf identity() const {
      return identity(degree());
    }

    //! Returns the identity transformation on the given number of points.
    //!
    //! This function returns a newly constructed transformation with
    //! degree equal to \p M that fixes every value from \c 0 to \p M.
    //!
    //! \param M the degree.
    //!
    //! \returns
    //! A value of type \c Transf.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    static Transf identity(size_t M) {
      return base_type::template identity<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
  ////////////////////////////////////////////////////////////////////////

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! \ref Transf for any template parameters.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsTransf = detail::IsTransfHelper<T>::value;

  ////////////////////////////////////////////////////////////////////////
  // Transf validate
  ////////////////////////////////////////////////////////////////////////

  //! Validate a transformation.
  //!
  //! \tparam T the type of the transformation to validate.
  //!
  //! \param x the transformation.
  //!
  //! \throw LibsemigroupsException if the image of any point exceeds \c
  //! x.degree() or is equal to \ref UNDEFINED.
  //!
  //! \complexity
  //! Linear in the size of the container \c x.degree().
  template <size_t N, typename Scalar>
  void validate(Transf<N, Scalar> const& x) {
    size_t const M = x.degree();
    for (auto const& val : x) {
      if (val >= M) {
        LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
                                "[%llu, %llu), found %llu",
                                uint64_t(0),
                                uint64_t(M),
                                uint64_t(val));
      }
    }
  }

  ////////////////////////////////////////////////////////////////////////
  // PPerm
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! A *partial permutation* \f$f\f$ is just an injective partial
  //! transformation, which is stored as a vector of the images of \f$\{0, 1,
  //! \ldots, n - 1\}\f$, i.e.  i.e. \f$\{(0)f, (1)f, \ldots, (n - 1)f\}\f$
  //! where the value \ref UNDEFINED is used to indicate that \f$(i)f\f$ is
  //! undefined (i.e. not among the points where \f$f\f$ is defined).
  //!
  //! If \p N is \c 0 (the default), then the degree of a \ref PPerm instance
  //! can be defined at runtime, and if \p N is not \c 0, then the degree is
  //! fixed at compile time.
  //!
  //! If \p N is \c 0, then the default value of \p Scalar is \c uint32_t. If
  //! \p N is not \c 0, then the default value of \p Scalar is the smallest
  //! integer type able to hold \c N. See also SmallestInteger.
  //!
  //! \tparam N  the degree (default: \c 0)
  //! \tparam Scalar an unsigned integer type (the type of the image values)
  //!
  //! \note
  //! PPerm has the same member functions as \ref StaticPTransf and \ref
  //! DynamicPTransf, this isn't current reflected by the contents of this
  //! page.
  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  class PPerm final : public PTransf<N, Scalar> {
    using base_type = PTransf<N, Scalar>;

   public:
    //! Type of the image values.
    //!
    //! Also the template parameter \c Scalar.
    using value_type = Scalar;

    //! Type of the underlying container.
    //!
    //! In this case, this is \c PTransf<N, Scalar>::container_type.
    using container_type = typename base_type::container_type;

    // Currently no way to document these
    using PTransf<N, value_type>::PTransf;

    // Currently no way to document these
    using base_type::degree;
    using base_type::undef;

    //! Construct from image list and validate
    //!
    //! Constructs a partial perm \f$f\f$ of degree \c M such that \f$f(i) =
    //! cont[i]\f$ for every value in the range \f$[0, M)\f$ where \f$M\f$ is
    //! \c cont.size()
    //!
    //! \param cont list of images or \ref UNDEFINED
    //!
    //! \complexity
    //! Linear in the size of \p cont.
    //!
    //! \throws LibsemigroupsException if any of the following fail to hold:
    //! * the size of \p cont is incompatible with \ref container_type.
    //! * any value in \p cont exceeds `cont.size()` and is not equal to \ref
    //!   UNDEFINED.
    //! * there are repeated values in \p cont.
    template <typename T>
    static PPerm make(T&& cont) {
      return base_type::template make<PPerm>(std::forward<T>(cont));
    }

    //! Construct from image list and validate
    //!
    //! Constructs a partial perm \f$f\f$ of degree \c M such that \f$f(i) =
    //! cont[i]\f$ for every value in the range \f$[0, M)\f$ where \f$M\f$ is
    //! \c cont.size()
    //!
    //! \param cont list of images or \ref UNDEFINED
    //!
    //! \complexity
    //! Linear in the size of \p cont.
    //!
    //! \throws LibsemigroupsException if any of the following fail to hold:
    //! * the size of \p cont is incompatible with \ref container_type.
    //! * any value in \p cont exceeds `cont.size()` and is not equal to
    //!   \ref UNDEFINED.
    //! * there are repeated values in \p cont.
    static PPerm make(std::initializer_list<value_type>&& cont) {
      return make<std::initializer_list<value_type>>(std::move(cont));
    }

    //! Construct from domain, range, and degree, and validate
    //!
    //! Constructs a partial perm of degree \p M such that `(dom[i])f = ran[i]`
    //! for all \c i and which is \ref UNDEFINED on every other value in the
    //! range \f$[0, M)\f$.
    //!
    //! \param dom the domain
    //! \param ran the range
    //! \param M the degree
    //!
    //! \complexity
    //! Linear in the size of \p dom.
    //!
    //! \throws LibsemigroupsException if any of the following fail to hold:
    //! * the value \p M is not compatible with the template parameter \p N
    //! * \p dom and \p ran do not have the same size
    //! * any value in \p dom or \p ran is greater than \p M
    //! * there are repeated entries in \p dom or \p ran.
    static PPerm make(std::vector<value_type> const& dom,
                      std::vector<value_type> const& ran,
                      size_t const                   M) {
      validate_args(dom, ran, M);
      PPerm result(dom, ran, M);
      validate(result);
      return result;
    }

    //! Construct from domain, range, and degree.
    //!
    //! Constructs a partial perm of degree \p M such that `(dom[i])f = ran[i]`
    //! for all \c i and which is \ref UNDEFINED on every other value in the
    //! range \f$[0, M)\f$.
    //!
    //! \param dom the domain
    //! \param ran the range
    //! \param M the degree
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in the size of \p dom.
    //!
    //! \warning
    //! No checks whatsoever are performed on the validity of the arguments.
    //!
    //! \sa
    //! \ref make.
    // Note: we use vectors here not container_type (which might be array),
    // because the length of dom and ran might not equal degree().
    PPerm(std::vector<value_type> const& dom,
          std::vector<value_type> const& ran,
          size_t                         M = N)
        : PPerm(M) {
      LIBSEMIGROUPS_ASSERT(M >= N);
      LIBSEMIGROUPS_ASSERT(dom.size() <= M);
      LIBSEMIGROUPS_ASSERT(ran.size() <= M);
      LIBSEMIGROUPS_ASSERT(ran.size() <= dom.size());
      for (size_t i = 0; i < dom.size(); ++i) {
        (*this)[dom[i]] = ran[i];
      }
    }

    //! Construct from domain, range, and degree.
    //!
    //! Constructs a partial perm of degree \p M such that `(dom[i])f = ran[i]`
    //! for all \c i and which is \ref UNDEFINED on every other value in the
    //! range \f$[0, M)\f$.
    //!
    //! \param dom the domain
    //! \param ran the range
    //! \param M the degree
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in the size of \p dom.
    //!
    //! \warning
    //! No checks whatsoever are performed on the validity of the arguments.
    //!
    //! \sa
    //! \ref make.
    PPerm(std::initializer_list<value_type> dom,
          std::initializer_list<value_type> ran,
          size_t                            M)
        : PPerm(std::vector<value_type>(dom), std::vector<value_type>(ran), M) {
    }

    //! Multiply two partial perms and store the product in \c this.
    //!
    //! Replaces the contents of \c this by the product of \p x and \p y.
    //!
    //! \param x a partial perm.
    //! \param y a partial perm.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in degree().
    //!
    //! \warning
    //! No checks are made on whether or not the parameters are compatible. If
    //! \p x and \p y have different degrees, then bad things will happen.
    void product_inplace(PPerm const& x, PPerm const& y) {
      LIBSEMIGROUPS_ASSERT(x.degree() == y.degree());
      LIBSEMIGROUPS_ASSERT(x.degree() == degree());
      LIBSEMIGROUPS_ASSERT(&x != this && &y != this);
      size_t const n = degree();
      for (value_type i = 0; i < n; ++i) {
        (*this)[i] = (x[i] == UNDEFINED ? UNDEFINED : y[x[i]]);
      }
    }

    //! Returns the identity partial perm on degree() points.
    //!
    //! This function returns a newly constructed partial perm with degree
    //! equal to the degree of \c this that fixes every value from \c 0 to
    //! degree().
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    PPerm identity() const {
      return identity(degree());
    }

    //! Returns the identity partial perm on the given number of points.
    //!
    //! This function returns a newly constructed partial perm with
    //! degree equal to \p M that fixes every value from \c 0 to \p M.
    //!
    //! \param M the degree.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in \p M.
    static PPerm identity(size_t M) {
      return base_type::template identity<PPerm>(M);
    }

    //! Returns the right one of this.
    //!
    //! This function returns a newly constructed partial perm with
    //! degree equal to \p M that fixes every value in the range of \c this,
    //! and is \ref UNDEFINED on any other values.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \complexity
    //! Linear in degree()
    PPerm right_one() const {
      size_t const n = degree();
      PPerm        result(n);
      std::fill(
          result.begin(), result.end(), static_cast<value_type>(UNDEFINED));
      for (size_t i = 0; i < n; ++i) {
        if ((*this)[i] != UNDEFINED) {
          result[(*this)[i]] = (*this)[i];
        }
      }
      return result;
    }

    //! Returns the left one of this.
    //!
    //! This function returns a newly constructed partial perm with
    //! degree equal to \p M that fixes every value in the domain of \c this,
    //! and is \ref UNDEFINED on any other values.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \complexity
    //! Linear in degree()
    PPerm left_one() const {
      size_t const n = degree();
      PPerm        result(n);
      std::fill(
          result.begin(), result.end(), static_cast<value_type>(UNDEFINED));
      for (size_t i = 0; i < n; ++i) {
        if ((*this)[i] != UNDEFINED) {
          result[i] = i;
        }
      }
      return result;
    }

    //! Returns the inverse.
    //!
    //! This function returns a newly constructed inverse of \c this.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \complexity
    //! Linear in degree()
    PPerm inverse() const {
      PPerm result(degree());
      inverse(result);
      return result;
    }

    //! Replace contents of a partial perm with the inverse of another.
    //!
    //! This function inverts \p that into \c this.
    //!
    //! \param that the partial perm to invert.
    //!
    //! \returns
    //! (None)
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in degree()
    // Put the inverse of this into that
    void inverse(PPerm& that) const {
      that.resize(degree());
      std::fill(that.begin(), that.end(), static_cast<value_type>(UNDEFINED));
      for (size_t i = 0; i < degree(); ++i) {
        if ((*this)[i] != UNDEFINED) {
          that[(*this)[i]] = i;
        }
      }
    }

   private:
    static void validate_args(std::vector<value_type> const& dom,
                              std::vector<value_type> const& ran,
                              size_t                         deg = N) {
      if (N != 0 && deg != N) {
        // Sanity check that the final argument is compatible with the
        // template param N, if we have a dynamic pperm
        LIBSEMIGROUPS_EXCEPTION(
            "the 3rd argument is not valid, expected %llu, found %llu",
            uint64_t(N),
            uint64_t(deg));
      } else if (dom.size() != ran.size()) {
        // The next 2 checks just verify that we can safely run the
        // constructor that uses *this[dom[i]] = im[i] for i = 0, ...,
        // dom.size() - 1.
        LIBSEMIGROUPS_EXCEPTION("domain and range size mismatch, domain has "
                                "size %llu but range has size %llu",
                                uint64_t(dom.size()),
                                uint64_t(ran.size()));
      } else if (!(dom.empty()
                   || deg > *std::max_element(dom.cbegin(), dom.cend()))) {
        LIBSEMIGROUPS_EXCEPTION(
            "domain value out of bounds, found %llu, must be less than %llu",
            uint64_t(*std::max_element(dom.cbegin(), dom.cend())),
            uint64_t(deg));
      }
    }
  };

  ////////////////////////////////////////////////////////////////////////
  // PPerm helpers
  ////////////////////////////////////////////////////////////////////////

  namespace detail {
    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

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! \ref PPerm for any template parameters.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsPPerm = detail::IsPPermHelper<T>::value;

  ////////////////////////////////////////////////////////////////////////
  // PPerm validate
  ////////////////////////////////////////////////////////////////////////

  namespace detail {
    template <typename T>
    void validate_no_duplicate_image_values(T const& x) {
      size_t const     deg = x.degree();
      std::vector<int> present(deg, false);
      for (auto it = x.cbegin(); it != x.cend(); ++it) {
        if (*it != UNDEFINED) {
          if (present[*it]) {
            LIBSEMIGROUPS_EXCEPTION(
                "duplicate image value, found %llu in position %llu, first "
                "occurrence in position %llu",
                uint64_t(*it),
                std::distance(x.begin(), it),
                std::distance(x.begin(), std::find(x.begin(), it, *it)));
          }
          present[*it] = 1;
        }
      }
    }
  }  // namespace detail

  //! Validate a partial perm.
  //!
  //! \tparam T the type of the partial perm to validate.
  //!
  //! \param x the partial perm.
  //!
  //! \throw LibsemigroupsException if:
  //! * the image of any point in \p x exceeds \c x.degree() and is not equal
  //!   to \ref UNDEFINED; or
  //! * \p x is not injective
  //!
  //! \complexity
  //! Linear in the size of the container \c x.degree().
  template <size_t N, typename Scalar>
  void validate(PPerm<N, Scalar> const& x) {
    validate(static_cast<PTransf<N, Scalar> const&>(x));
    detail::validate_no_duplicate_image_values(x);
  }

  ////////////////////////////////////////////////////////////////////////
  // Perm
  ////////////////////////////////////////////////////////////////////////

  //! Defined in ``transf.hpp``.
  //!
  //! A *permutation* \f$f\f$ is an injective transformation defined on the
  //! whole of \f$\{0, 1, \ldots, n - 1\}\f$ for some integer \f$n\f$ called
  //! the *degree* of \f$f\f$. A permutation is stored as a vector of the
  //! images of \f$(0, 1, \ldots, n - 1)\f$, i.e. \f$((0)f, (1)f, \ldots, (n -
  //! 1)f)\f$.
  //!
  //! If \p N is \c 0 (the default), then the degree of a \ref PPerm instance
  //! can be defined at runtime, and if \p N is not \c 0, then the degree is
  //! fixed at compile time.
  //!
  //! If \p N is \c 0, then the default value of \p Scalar is \c uint32_t. If
  //! \p N is not \c 0, then the default value of \p Scalar is the smallest
  //! integer type able to hold \c N. See also SmallestInteger.
  //!
  //! \tparam N  the degree (default: \c 0)
  //! \tparam Scalar an unsigned integer type (the type of the image values)
  //!
  //! \note
  //! Perm has the same member functions as \ref StaticPTransf and \ref
  //! DynamicPTransf, this isn't current reflected by the contents of this
  //! page.
  template <
      size_t N = 0,
      typename Scalar
      = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
  class Perm final : public Transf<N, Scalar> {
    using base_type = PTransf<N, Scalar>;

   public:
    //! Type of the image values.
    //!
    //! Also the template parameter \c Scalar.
    using value_type = Scalar;

    //! Type of the underlying container.
    //!
    //! In this case, this is \c PTransf<N, Scalar>::container_type.
    using container_type = typename PTransf<N, value_type>::container_type;

    // Currently no way to document these
    using Transf<N, Scalar>::Transf;

    // Currently no way to document these
    using base_type::degree;

    //! Construct from image list and validate
    //!
    //! Constructs a permutation \f$f\f$ of degree \c M such that \f$f(i) =
    //! cont[i]\f$ for every value in the range \f$[0, M)\f$ where \f$M\f$ is
    //! \c cont.size()
    //!
    //! \param cont list of images
    //!
    //! \complexity
    //! Linear in the size of \p cont.
    //!
    //! \throws LibsemigroupsException if any of the following fail to hold:
    //! * the size of \p cont is incompatible with \ref container_type.
    //! * any value in \p cont exceeds `cont.size()`
    //! * there are repeated values in \p cont.
    template <typename T>
    static Perm make(T&& cont) {
      return base_type::template make<Perm>(std::forward<T>(cont));
    }

#ifndef DOXYGEN_SHOULD_SKIP_THIS
    // We don't document this, because it's basically identical to the function
    // template above, and because it confuses the doc system.
    static Perm make(std::initializer_list<value_type>&& cont) {
      return make<std::initializer_list<value_type>>(std::move(cont));
    }
#endif

    //! Returns the identity permutation on degree() points.
    //!
    //! This function returns a newly constructed permutation with degree
    //! equal to the degree of \c this that fixes every value from \c 0 to
    //! degree().
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    Perm identity() const {
      return identity(degree());
    }

    //! Returns the identity permutation on the given number of points.
    //!
    //! This function returns a newly constructed permutation with
    //! degree equal to \p M that fixes every value from \c 0 to \p M.
    //!
    //! \param M the degree.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \complexity
    //! Linear in \p M.
    static Perm identity(size_t M) {
      return base_type::template identity<Perm>(M);
    }

    //! Returns the inverse.
    //!
    //! This function returns a newly constructed inverse of \c this.
    //! The *inverse* of a permutation \f$f\f$ is the permutation \f$g\f$ such
    //! that \f$fg = gf\f$ is the identity permutation of degree \f$n\f$.
    //!
    //! \returns
    //! A value of type \c PPerm.
    //!
    //! \exceptions
    //! \no_libsemigroups_except
    //!
    //! \par Parameters
    //! (None)
    //!
    //! \complexity
    //! Linear in degree()
    Perm inverse() const {
      size_t const n = degree();
      Perm         id(n);
      for (Scalar i = 0; i < n; i++) {
        id[(*this)[i]] = i;
      }
      return id;
    }
    // TODO(later) inverse(that)
  };

  ////////////////////////////////////////////////////////////////////////
  // 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

  //! Helper variable template.
  //!
  //! The value of this variable is \c true if the template parameter \p T is
  //! \ref Perm for any template parameters.
  //!
  //! \tparam T a type.
  template <typename T>
  static constexpr bool IsPerm = detail::IsPermHelper<T>::value;

  ////////////////////////////////////////////////////////////////////////
  // Perm validate
  ////////////////////////////////////////////////////////////////////////

  //! Validate a permutation.
  //!
  //! \tparam T the type of the permutation to validate.
  //!
  //! \param x the permutation.
  //!
  //! \throw LibsemigroupsException if:
  //! * the image of any point in \p x exceeds \c x.degree()
  //! * \p x is not injective
  //!
  //! \complexity
  //! Linear in the size of the container \c x.degree().
  template <size_t N, typename Scalar>
  auto validate(Perm<N, Scalar> const& x) {
    validate(static_cast<Transf<N, Scalar> const&>(x));
    detail::validate_no_duplicate_image_values(x);
  }

  ////////////////////////////////////////////////////////////////////////
  // Adapters
  ////////////////////////////////////////////////////////////////////////

  template <typename T>
  struct Degree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    constexpr size_t operator()(T const& x) const noexcept {
      return x.degree();
    }
  };

  template <typename T>
  struct One<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    T operator()(T const& x) const {
      return (*this)(x.degree());
    }

    T operator()(size_t N = 0) const {
      return T::identity(N);
    }
  };

  template <size_t N, typename Scalar>
  struct Inverse<Perm<N, Scalar>> {
    Perm<N, Scalar> operator()(Perm<N, Scalar> const& x) {
      return x.inverse();
    }
  };

  template <typename TSubclass>
  struct Product<TSubclass, std::enable_if_t<IsDerivedFromPTransf<TSubclass>>> {
    void operator()(TSubclass&       xy,
                    TSubclass const& x,
                    TSubclass const& y,
                    size_t = 0) {
      xy.product_inplace(x, y);
    }
  };

  template <typename T>
  struct Hash<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    constexpr size_t operator()(T const& x) const {
      return x.hash_value();
    }
  };

  template <typename T>
  struct Complexity<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    constexpr size_t operator()(T const& x) const noexcept {
      return x.degree();
    }
  };

  //! Specialization of the adapter IncreaseDegree for type derived from
  //! PTransfPolymorphicBase.
  //!
  //! \sa IncreaseDegree.
  template <typename T>
  struct IncreaseDegree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
    //! Returns \p x->increase_degree_by(\p n).
    inline void operator()(T& x, size_t n) const {
      return x.increase_degree_by(n);
    }
  };

  ////////////////////////////////////////////////////////////////////////
  // ImageRight/LeftAction - Transf
  ////////////////////////////////////////////////////////////////////////

  // Equivalent to OnSets in GAP
  // Slowest
  // works for T = std::vector and T = StaticVector1
  //! Specialization of the adapter ImageRightAction for instances of
  //! Transformation and std::vector.
  //!
  //! \sa ImageRightAction
  template <size_t N, typename Scalar, typename T>
  struct ImageRightAction<Transf<N, Scalar>, T> {
    //! Stores the image set of \c pt under \c x in \p res.
    void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const {
      res.clear();
      for (auto i : pt) {
        res.push_back(x[i]);
      }
      std::sort(res.begin(), res.end());
      res.erase(std::unique(res.begin(), res.end()), res.end());
    }
  };

  // Fastest, but limited to at most degree 64
  //! Specialization of the adapter ImageRightAction for instances of
  //! Transformation and BitSet<N> (\f$0 \leq N leq 64\f$).
  //!
  //! \sa ImageRightAction
  template <size_t N, typename Scalar, size_t M>
  struct ImageRightAction<Transf<N, Scalar>, BitSet<M>> {
    //! Stores the image set of \c pt under \c x in \p res.
    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>
  //! Specialization of the adapter ImageLeftAction for instances of
  //! Transformation and std::vector.
  //!
  //! \sa ImageLeftAction
  template <size_t N, typename Scalar, typename T>
  struct ImageLeftAction<Transf<N, Scalar>, T> {
    //! Stores the image of \p pt under the left action of \p x in \p res.
    void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const {
      res.clear();
      res.resize(x.degree());
      static thread_local std::vector<Scalar> buf;
      buf.clear();
      buf.resize(x.degree(), Scalar(UNDEFINED));
      Scalar next = 0;

      for (size_t i = 0; i < res.size(); ++i) {
        if (buf[pt[x[i]]] == UNDEFINED) {
          buf[pt[x[i]]] = next++;
        }
        res[i] = buf[pt[x[i]]];
      }
    }
  };

  ////////////////////////////////////////////////////////////////////////
  // 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.
  //! Specialization of the adapter LambdaValue for instances of
  //! Transformation. Note that the the type chosen here limits the Konieczny
  //! algorithm to Transformations of degree at most 64 (or 32 on 32-bit
  //! systems).
  //!
  //! \sa LambdaValue.
  template <size_t N, typename Scalar>
  struct LambdaValue<Transf<N, Scalar>> {
    //! For transformations, \c type is the largest BitSet available,
    //! representing the image set.
    using type = BitSet<BitSet<1>::max_size()>;
  };

  // Benchmarks indicate that using std::vector yields similar performance to
  // using StaticVector1's.
--> --------------------

--> maximum size reached

--> --------------------