libsemigroups  v3.1.3
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
transf.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2021-2025 James D. Mitchell
4//
5// This program is free software: you can redistribute it and/or modify
6// it under the terms of the GNU General Public License as published by
7// the Free Software Foundation, either version 3 of the License, or
8// (at your option) any later version.
9//
10// This program is distributed in the hope that it will be useful,
11// but WITHOUT ANY WARRANTY; without even the implied warranty of
12// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13// GNU General Public License for more details.
14//
15// You should have received a copy of the GNU General Public License
16// along with this program. If not, see <http://www.gnu.org/licenses/>.
17//
18
19// This file contains the declaration of the partial transformation class and
20// its subclasses.
21
22// TODO(later)
23// * benchmarks
24// * add some tests for PTransf themselves
25// * allocator
26// * implement is_transformation(Iterator, Iterator) etc to avoid code
27// duplication with hpcombi.hpp
28
29#ifndef LIBSEMIGROUPS_TRANSF_HPP_
30#define LIBSEMIGROUPS_TRANSF_HPP_
31
32#include <algorithm> // for sort, max_element, unique
33#include <array> // for array
34#include <cstddef> // for size_t
35#include <cstdint> // for uint64_t, uint32_t
36#include <initializer_list> // for initializer_list
37#include <iterator> // for distance
38#include <limits> // for numeric_limits
39#include <numeric> // for iota
40#include <tuple> // for tuple_size
41#include <type_traits> // for enable_if_t
42#include <unordered_map> // for unordered_map
43#include <unordered_set> // for unordered_set
44#include <utility> // for forward
45#include <vector> // for vector
46
47#include "config.hpp" // for LIBSEMIGROUPS_HPCOMBI_ENABLED
48
49#include "adapters.hpp" // for Hash etc
50#include "bitset.hpp" // for BitSet
51#include "constants.hpp" // for UNDEFINED, Undefined
52#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
53#include "exception.hpp" // for LIBSEMIGROUPS_EXCEPTION
54#include "hpcombi.hpp" // for HPCombi::Transf16
55#include "is_specialization_of.hpp" // for is_specialization_of
56#include "types.hpp" // for SmallestInteger
57
58#include "detail/stl.hpp" // for is_array_v
59
60namespace libsemigroups {
70
71 namespace detail {
76 } // namespace detail
77
92 // TODO(1) example
93
101 template <typename T>
102 static constexpr bool IsDerivedFromPTransf
103 = std::is_base_of_v<detail::PTransfPolymorphicBase, T>;
104
105 namespace detail {
106
107 template <typename T>
108 struct IsStaticHelper : std::false_type {};
109
110 template <typename T>
111 struct IsDynamicHelper : std::false_type {};
112
113 } // namespace detail
114
128 template <typename Scalar, typename Container>
130 static_assert(std::is_integral_v<Scalar>,
131 "template parameter Scalar must be an integral type");
132 static_assert(std::is_unsigned_v<Scalar>,
133 "template parameter Scalar must be unsigned");
134
135 public:
139 using point_type = Scalar;
140
144 using container_type = Container;
145
146 // Required by python bindings
157 [[nodiscard]] static point_type undef() noexcept {
158 return static_cast<point_type>(UNDEFINED);
159 }
160
170 PTransfBase() = default;
171
172 // No constructor from size_t this is delegated to StaticPTransf and
173 // DynamicPTransf
174
195 explicit PTransfBase(Container const& cont) : _container(cont) {}
196
198 explicit PTransfBase(Container&& cont) : _container(std::move(cont)) {}
199
220 template <typename Iterator>
221 explicit PTransfBase(Iterator first, Iterator last) : PTransfBase() {
222 using OtherScalar = typename std::iterator_traits<Iterator>::value_type;
223 // The below assertions exist to insure that we are not badly assigning
224 // values. The subsequent pragmas exist to suppress the false-positive
225 // warnings produced by g++ 13.2.0
226 static_assert(
227 std::is_same_v<OtherScalar, Undefined>
228 || std::is_convertible_v<OtherScalar, point_type>,
229 "the template parameter Iterator must have "
230 "value_type \"Undefined\" or convertible to \"point_type\"!");
231 static_assert(std::is_same_v<std::decay_t<decltype(*_container.begin())>,
232 point_type>);
233 resize(_container, std::distance(first, last));
234#pragma GCC diagnostic push
235#if defined(__GNUC__) && !defined(__clang__)
236#pragma GCC diagnostic ignored "-Wstringop-overflow"
237#endif
238 std::copy(first, last, _container.begin());
239#pragma GCC diagnostic pop
240 }
241
245
267 template <typename Subclass, typename OtherContainer = Container>
268 [[nodiscard]] static Subclass make(OtherContainer&& cont);
269
290 template <typename Subclass, typename OtherScalar>
291 [[nodiscard]] static Subclass make(std::initializer_list<OtherScalar> cont);
292
296 PTransfBase(PTransfBase const&) = default;
297
302
307
312
328 [[nodiscard]] bool operator<(PTransfBase const& that) const {
329 return _container < that._container;
330 }
331
347 [[nodiscard]] bool operator>(PTransfBase const& that) const {
348 return that < *this;
349 }
350
366 [[nodiscard]] bool operator==(PTransfBase const& that) const {
367 return _container == that._container;
368 }
369
385 [[nodiscard]] bool operator<=(PTransfBase const& that) const {
386 return _container < that._container || _container == that._container;
387 }
388
404 [[nodiscard]] bool operator>=(PTransfBase const& that) const {
405 return that <= *this;
406 }
407
423 [[nodiscard]] bool operator!=(PTransfBase const& that) const {
424 return !(*this == that);
425 }
426
441 [[nodiscard]] point_type& operator[](size_t i) {
442 return _container[i];
443 }
444
459 [[nodiscard]] point_type const& operator[](size_t i) const {
460 return _container[i];
461 }
462
476 // TODO(1) better exception message for python bindings
477 [[nodiscard]] point_type& at(size_t i) {
478 return _container.at(i);
479 }
480
494 // TODO(1) better exception message for python bindings
495 [[nodiscard]] point_type const& at(size_t i) const {
496 return _container.at(i);
497 }
498
519 // TODO(later) other operators such as power
520 // TODO to tpp
521 template <typename Subclass>
522 [[nodiscard]] Subclass operator*(Subclass const& that) const {
523 static_assert(IsDerivedFromPTransf<Subclass>,
524 "the template parameter Subclass must be derived from "
525 "PTransfPolymorphicBase");
526 Subclass xy(that.degree());
527 xy.product_inplace(*static_cast<Subclass const*>(this), that);
528 return xy;
529 }
530
534 using iterator = typename Container::iterator;
535
539 using const_iterator = typename Container::const_iterator;
540
552 [[nodiscard]] const_iterator cbegin() const noexcept {
553 return _container.cbegin();
554 }
555
567 [[nodiscard]] const_iterator cend() const noexcept {
568 return _container.cend();
569 }
570
572 [[nodiscard]] const_iterator begin() const noexcept {
573 return _container.begin();
574 }
575
577 [[nodiscard]] const_iterator end() const noexcept {
578 return _container.end();
579 }
580
592 [[nodiscard]] iterator begin() noexcept {
593 return _container.begin();
594 }
595
607 [[nodiscard]] iterator end() noexcept {
608 return _container.end();
609 }
610
624 [[nodiscard]] size_t rank() const {
626 return (vals.find(UNDEFINED) == vals.end() ? vals.size()
627 : vals.size() - 1);
628 }
629
640 // not noexcept because Hash<T>::operator() isn't
641 [[nodiscard]] size_t hash_value() const {
642 return Hash<Container>()(_container);
643 }
644
651 void swap(PTransfBase& that) noexcept {
652 std::swap(_container, that._container);
653 }
654
666 [[nodiscard]] size_t degree() const noexcept {
667 return _container.size();
668 }
669
683 template <typename Subclass>
684 [[nodiscard]] static Subclass one(size_t N) {
685 static_assert(IsDerivedFromPTransf<Subclass>,
686 "the template parameter Subclass must be derived from "
687 "PTransfPolymorphicBase");
688 Subclass result(N);
689 std::iota(result.begin(), result.end(), 0);
690 return result;
691 }
692
693 protected:
694 static void resize(container_type& c, size_t N, point_type val = 0);
695 void resize(size_t N, point_type val = 0) {
696 resize(_container, N, val);
697 }
698
699 private:
700 template <typename T>
701 static void throw_if_bad_args(T const& cont);
702
703 Container _container;
704 };
705
707 // Helper variable templates
709
717 template <typename T>
718 static constexpr bool IsStatic = detail::IsStaticHelper<T>::value;
719
727 template <typename T>
728 static constexpr bool IsDynamic = detail::IsDynamicHelper<T>::value;
729
731 // DynamicPTransf
733
746 template <typename Scalar>
747 class DynamicPTransf : public PTransfBase<Scalar, std::vector<Scalar>> {
749
750 public:
756 using point_type = Scalar;
757
764
766 using base_type::begin;
767 using base_type::degree;
768 using base_type::end;
769
770 // No default constructor, because the degree would be 0, and so we can
771 // just use the PTransfBase default constructor for that. Note that there's
772 // a default constructor for StaticPTransf since there we do know the degree
773 // (at compile time) and we can fill it with UNDEFINED values.
774
787 explicit DynamicPTransf(size_t n) : base_type() {
788 resize(n, UNDEFINED);
789 }
790
806 resize(degree() + m);
807 std::iota(end() - m, end(), degree() - m);
808 return *this;
809 }
810
811 protected:
812 using base_type::resize;
813 };
814
816 // StaticPTransf
818
831 template <size_t N, typename Scalar>
832 class StaticPTransf : public PTransfBase<Scalar, std::array<Scalar, N>> {
834
835 public:
837 using point_type = Scalar;
838
843
845 using base_type::begin;
846 using base_type::end;
847
858 StaticPTransf() : base_type() {
860 }
861
872 explicit StaticPTransf(size_t n);
873
880 // do nothing can't increase the degree
881 LIBSEMIGROUPS_EXCEPTION("cannot increase the degree of a StaticPTransf!");
882 return *this;
883 }
884 };
885
887 // PTransf
889
907 template <
908 size_t N = 0,
909 typename Scalar
910 = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
911 using PTransf = std::
912 conditional_t<N == 0, DynamicPTransf<Scalar>, StaticPTransf<N, Scalar>>;
913
914 namespace detail {
915 template <typename T>
916 struct IsPTransfHelper : std::false_type {};
917
918 template <typename Scalar>
919 struct IsPTransfHelper<DynamicPTransf<Scalar>> : std::true_type {};
920
921 template <size_t N, typename Scalar>
922 struct IsPTransfHelper<StaticPTransf<N, Scalar>> : std::true_type {};
923
924 template <size_t N, typename Scalar>
925 struct IsStaticHelper<StaticPTransf<N, Scalar>> : std::true_type {};
926
927 template <typename Scalar>
928 struct IsDynamicHelper<DynamicPTransf<Scalar>> : std::true_type {};
929
930 } // namespace detail
931
942 template <typename T>
943 static constexpr bool IsPTransf = detail::IsPTransfHelper<T>::value;
944
960 // TODO(1) to tpp
961 template <typename Scalar, typename Container>
962 void
964 size_t const M = f.degree();
965 for (auto const& val : f) {
966 // the type of "val" is an unsigned int, and so we don't check for val
967 // being less than 0
968 if (val >= M && val != UNDEFINED) {
969 LIBSEMIGROUPS_EXCEPTION("image value out of bounds, expected value in "
970 "[{}, {}), found {}",
971 0,
972 M,
973 val);
974 }
975 }
976 }
977
979 // Transf
981
1008 template <
1009 size_t N = 0,
1010 typename Scalar
1011 = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
1012 class Transf : public PTransf<N, Scalar> {
1013 using base_type = PTransf<N, Scalar>;
1014
1015 public:
1019 using point_type = Scalar;
1020
1024 using container_type = typename base_type::container_type;
1025
1026 using PTransf<N, Scalar>::PTransf;
1027 using base_type::degree;
1028
1048 void product_inplace(Transf const& f, Transf const& g);
1049
1063 [[nodiscard]] static Transf one(size_t M) {
1064 return base_type::template one<Transf>(M);
1065 }
1066 };
1067
1068 namespace detail {
1069 template <typename T>
1070 struct IsTransfHelper : std::false_type {};
1071
1072 template <size_t N, typename Scalar>
1073 struct IsTransfHelper<Transf<N, Scalar>> : std::true_type {};
1074
1075 template <size_t N, typename Scalar>
1076 struct IsStaticHelper<Transf<N, Scalar>>
1077 : IsStaticHelper<PTransf<N, Scalar>> {};
1078
1079 template <size_t N, typename Scalar>
1080 struct IsDynamicHelper<Transf<N, Scalar>>
1081 : IsDynamicHelper<PTransf<N, Scalar>> {};
1082 } // namespace detail
1083
1085 // Transf helpers
1087
1095 template <typename T>
1096 static constexpr bool IsTransf = detail::IsTransfHelper<T>::value;
1097
1099 // Transf throw_if_image_value_out_of_range
1101
1115 template <size_t N, typename Scalar>
1117
1119 // make<Transf>
1121
1132
1155 template <typename Return, typename OtherContainer>
1156 [[nodiscard]] std::enable_if_t<IsTransf<Return>, Return>
1157 make(OtherContainer&& cont) {
1158 return Return::template make<Return>(std::forward<OtherContainer>(cont));
1159 }
1160
1184 template <typename Return, typename OtherScalar>
1185 [[nodiscard]] std::enable_if_t<IsTransf<Return>, Return>
1189
1191 // PPerm
1193
1221 template <
1222 size_t N = 0,
1223 typename Scalar
1224 = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
1225 class PPerm : public PTransf<N, Scalar> {
1226 using base_type = PTransf<N, Scalar>;
1227
1228 public:
1232 using point_type = Scalar;
1233
1237 using container_type = typename base_type::container_type;
1238
1239 using PTransf<N, point_type>::PTransf;
1240 using base_type::degree;
1241 using base_type::undef;
1242
1262 //
1263 // Note: we use vectors here not container_type (which might be array),
1264 // because the length of dom and img might not equal degree().
1265 // Also we don't use a universal reference because we can't actually use an
1266 // rvalue reference here (we don't store dom or img).
1267 template <typename OtherScalar>
1269 std::vector<OtherScalar> const& img,
1270 size_t M);
1271
1276 size_t M)
1277 : PPerm(std::vector<point_type>(dom), std::vector<point_type>(img), M) {
1278 }
1279
1296 void product_inplace(PPerm const& f, PPerm const& g);
1297
1299 [[nodiscard]] static PPerm one(size_t M) {
1300 return base_type::template one<PPerm>(M);
1301 }
1302 };
1303
1304 namespace detail {
1305 template <
1306 size_t N = 0,
1307 typename Scalar = std::
1308 conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
1309 void throw_if_bad_args(std::vector<Scalar> const& dom,
1310 std::vector<Scalar> const& ran,
1311 size_t deg = N);
1312
1314 // PPerm helpers
1316
1317 template <typename T>
1318 struct IsPPermHelper : std::false_type {};
1319
1320 template <size_t N, typename Scalar>
1321 struct IsPPermHelper<PPerm<N, Scalar>> : std::true_type {};
1322
1323 template <size_t N, typename Scalar>
1324 struct IsStaticHelper<PPerm<N, Scalar>>
1325 : IsStaticHelper<PTransf<N, Scalar>> {};
1326
1327 template <size_t N, typename Scalar>
1328 struct IsDynamicHelper<PPerm<N, Scalar>>
1329 : IsDynamicHelper<PTransf<N, Scalar>> {};
1330 } // namespace detail
1331
1339 template <typename T>
1340 static constexpr bool IsPPerm = detail::IsPPermHelper<T>::value;
1341
1343 // PPerm check
1345
1360 template <size_t N, typename Scalar>
1363 detail::throw_if_duplicates(f.begin(), f.end());
1364 }
1365
1367 // make<PPerm>
1369
1380
1404 template <typename Return, typename OtherContainer>
1405 [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
1406 make(OtherContainer&& cont) {
1407 return Return::template make<Return>(std::forward<OtherContainer>(cont));
1408 }
1409
1431 template <typename Return>
1432 [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
1437
1461 template <typename Return>
1462 [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
1465 size_t M);
1466
1490 template <typename Return>
1491 [[nodiscard]] std::enable_if_t<IsPPerm<Return>, Return>
1499
1501 // Perm
1503
1530 template <
1531 size_t N = 0,
1532 typename Scalar
1533 = std::conditional_t<N == 0, uint32_t, typename SmallestInteger<N>::type>>
1534 class Perm : public Transf<N, Scalar> {
1535 using base_type = PTransf<N, Scalar>;
1536
1537 public:
1541 using point_type = Scalar;
1542
1547
1548 using Transf<N, Scalar>::Transf;
1549 using base_type::degree;
1550
1552 [[nodiscard]] static Perm one(size_t M) {
1553 return base_type::template one<Perm>(M);
1554 }
1555 };
1556
1558 // Perm helpers
1560
1561 namespace detail {
1562 template <typename T>
1563 struct IsPermHelper : std::false_type {};
1564
1565 template <size_t N, typename Scalar>
1566 struct IsPermHelper<Perm<N, Scalar>> : std::true_type {};
1567 } // namespace detail
1568
1576 template <typename T>
1577 static constexpr bool IsPerm = detail::IsPermHelper<T>::value;
1578
1580 // Perm throw_if_not_perm
1582
1597 template <size_t N, typename Scalar>
1600 detail::throw_if_duplicates(f.begin(), f.end());
1601 }
1602
1604 // make<Perm>
1606
1617
1641 template <typename Return, typename OtherContainer>
1642 [[nodiscard]] std::enable_if_t<IsPerm<Return>, Return>
1643 make(OtherContainer&& cont) {
1644 return Return::template make<Return>(std::forward<OtherContainer>(cont));
1645 }
1646
1669 template <typename Return>
1670 [[nodiscard]] std::enable_if_t<IsPerm<Return>, Return>
1675
1677 // Helper functions
1679
1706 template <typename T, typename Scalar>
1707 void image(T const& f, std::vector<Scalar>& im);
1708
1730 template <typename T>
1732
1759 template <typename T, typename Scalar>
1760 void domain(T const& f, std::vector<Scalar>& dom);
1761
1783 template <typename T>
1785
1804 template <typename T>
1805 [[nodiscard]] auto one(T const& f)
1806 -> std::enable_if_t<IsDerivedFromPTransf<T>, T> {
1807 return T::one(f.degree());
1808 }
1809
1827 template <size_t N, typename Scalar>
1829 // TODO(1) void pass by reference version
1830
1848 template <size_t N, typename Scalar>
1850 // TODO(1) void pass by reference version
1851
1867 // Put the inverse of this into that
1868 template <size_t N, typename Scalar>
1870
1893 template <size_t N, typename Scalar>
1895 PPerm<N, Scalar> to(f.degree());
1896 inverse(f, to);
1897 return to;
1898 }
1899
1918 template <size_t N, typename Scalar>
1920
1941 template <size_t N, typename Scalar>
1942 [[nodiscard]] Perm<N, Scalar> inverse(Perm<N, Scalar> const& f);
1943
1945 // Adapters
1947
1948 template <typename T>
1949 struct Degree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
1950 [[nodiscard]] constexpr size_t operator()(T const& x) const noexcept {
1951 return x.degree();
1952 }
1953 };
1954
1955 template <typename T>
1956 struct One<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
1957 [[nodiscard]] T operator()(T const& x) const {
1958 return (*this)(x.degree());
1959 }
1960
1961 [[nodiscard]] T operator()(size_t N) const {
1962 return T::one(N);
1963 }
1964 };
1965
1966 template <size_t N, typename Scalar>
1967 struct Inverse<Perm<N, Scalar>> {
1968 [[nodiscard]] Perm<N, Scalar> operator()(Perm<N, Scalar> const& x) {
1969 return inverse(x);
1970 }
1971 };
1972
1973 template <typename Subclass>
1974 struct Product<Subclass, std::enable_if_t<IsDerivedFromPTransf<Subclass>>> {
1975 void
1976 operator()(Subclass& xy, Subclass const& x, Subclass const& y, size_t = 0) {
1977 xy.product_inplace(x, y);
1978 }
1979 };
1980
1981 template <typename T>
1982 struct Hash<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
1983 [[nodiscard]] constexpr size_t operator()(T const& x) const {
1984 return x.hash_value();
1985 }
1986 };
1987
1988 template <typename T>
1989 struct Complexity<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
1990 [[nodiscard]] constexpr size_t operator()(T const& x) const noexcept {
1991 return x.degree();
1992 }
1993 };
1994
1999 template <typename T>
2000 struct IncreaseDegree<T, std::enable_if_t<IsDerivedFromPTransf<T>>> {
2002 inline void operator()(T& x, size_t n) const {
2003 x.increase_degree_by(n);
2004 }
2005 };
2006
2008 // ImageRight/LeftAction - Transf
2010
2011 // Equivalent to OnSets in GAP
2012 // Slowest
2013 // works for T = std::vector and T = StaticVector1
2018 template <size_t N, typename Scalar, typename T>
2019 struct ImageRightAction<Transf<N, Scalar>, T> {
2021 void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const;
2022 };
2023
2024 // Fastest, but limited to at most degree 64
2029 template <size_t N, typename Scalar, size_t M>
2030 struct ImageRightAction<Transf<N, Scalar>, BitSet<M>> {
2032 void operator()(BitSet<M>& res,
2033 BitSet<M> const& pt,
2034 Transf<N, Scalar> const& x) const {
2035 res.reset();
2036 // Apply the lambda to every set bit in pt
2037 pt.apply([&x, &res](size_t i) { res.set(x[i]); });
2038 }
2039 };
2040
2041 // OnKernelAntiAction
2042 // T = StaticVector1<S> or std::vector<S>
2047 template <size_t N, typename Scalar, typename T>
2048 struct ImageLeftAction<Transf<N, Scalar>, T> {
2050 void operator()(T& res, T const& pt, Transf<N, Scalar> const& x) const;
2051 };
2052
2054 // Lambda/Rho - Transformation
2056
2057 // This currently limits the use of Konieczny to transformation of degree at
2058 // most 64 with the default traits class, since we cannot know the degree at
2059 // compile time, only at run time.
2066 template <size_t N, typename Scalar>
2067 struct LambdaValue<Transf<N, Scalar>> {
2070 using type = BitSet<BitSet<1>::max_size()>;
2071 };
2072
2073 // Benchmarks indicate that using std::vector yields similar performance to
2074 // using StaticVector1's.
2078 template <size_t N, typename Scalar>
2079 struct RhoValue<Transf<N, Scalar>> {
2083 };
2084
2085 // T = std::vector or StaticVector1
2090 template <size_t N, typename Scalar, typename T>
2091 struct Lambda<Transf<N, Scalar>, T> {
2092 // not noexcept because std::vector::resize isn't (although
2093 // StaticVector1::resize is).
2096 void operator()(T& res, Transf<N, Scalar> const& x) const;
2097 };
2098
2103 template <size_t N, typename Scalar, size_t M>
2104 struct Lambda<Transf<N, Scalar>, BitSet<M>> {
2105 // not noexcept because it can throw
2108 void operator()(BitSet<M>& res, Transf<N, Scalar> const& x) const;
2109 };
2110
2111 // T = std::vector<S> or StaticVector1<S, N>
2116 template <size_t N, typename Scalar, typename T>
2117 struct Rho<Transf<N, Scalar>, T> {
2129 // not noexcept because std::vector::resize isn't (although
2130 // StaticVector1::resize is).
2131 void operator()(T& res, Transf<N, Scalar> const& x) const;
2132 };
2133
2137 template <size_t N, typename Scalar>
2138 struct Rank<Transf<N, Scalar>> {
2151 [[nodiscard]] size_t operator()(Transf<N, Scalar> const& x) const {
2152 return x.rank();
2153 }
2154 };
2155
2157 // ImageRight/LeftAction - PPerm
2159
2160 // Slowest
2165 template <size_t N, typename Scalar>
2166 struct ImageRightAction<PPerm<N, Scalar>, PPerm<N, Scalar>> {
2169 PPerm<N, Scalar> const& pt,
2170 PPerm<N, Scalar> const& x) const noexcept {
2171 LIBSEMIGROUPS_ASSERT(res.degree() == pt.degree());
2172 LIBSEMIGROUPS_ASSERT(res.degree() == x.degree());
2173 res.product_inplace(pt, x);
2174 res = right_one(res);
2175 }
2176 };
2177
2178 // Faster than the above, but slower than the below
2179 // works for T = std::vector and T = StaticVector1
2184 template <size_t N, typename Scalar, typename T>
2185 struct ImageRightAction<PPerm<N, Scalar>, T> {
2187 void operator()(T& res, T const& pt, PPerm<N, Scalar> const& x) const;
2188 };
2189
2190 // Fastest, but limited to at most degree 64
2195 template <size_t N, typename Scalar, size_t M>
2196 struct ImageRightAction<PPerm<N, Scalar>, BitSet<M>> {
2198 void operator()(BitSet<M>& res,
2199 BitSet<M> const& pt,
2200 PPerm<N, Scalar> const& x) const;
2201 };
2202
2203 // Slowest
2208 template <size_t N, typename Scalar>
2209 struct ImageLeftAction<PPerm<N, Scalar>, PPerm<N, Scalar>> {
2212 PPerm<N, Scalar> const& pt,
2213 PPerm<N, Scalar> const& x) const noexcept {
2214 res.product_inplace(x, pt);
2215 res = left_one(res);
2216 }
2217 };
2218
2219 // Fastest when used with BitSet<N>.
2220 // works for T = std::vector and T = BitSet<N>
2221 // Using BitSet<N> limits this to size 64. However, if we are trying to
2222 // compute a LeftAction object, then the max size of such is 2 ^ 64, which
2223 // is probably not achievable. So, for higher degrees, we will only be able
2224 // to compute relatively sparse LeftActions (i.e. not containing the
2225 // majority of the 2 ^ n possible subsets), in which case using vectors or
2226 // StaticVector1's might be not be appreciable slower anyway. All of this is
2227 // to say that it probably isn't worthwhile trying to make BitSet's work for
2228 // more than 64 bits.
2233 template <size_t N, typename Scalar, typename T>
2234 struct ImageLeftAction<PPerm<N, Scalar>, T> {
2235 void operator()(T& res, T const& pt, PPerm<N, Scalar> const& x) const {
2237 static PPerm<N, Scalar> xx(x.degree());
2238 inverse(x, xx); // invert x into xx
2239 ImageRightAction<PPerm<N, Scalar>, T>()(res, pt, xx);
2240 }
2241 };
2242
2244 // Lambda/Rho - PPerm
2246
2247 // This currently limits the use of Konieczny to partial perms of degree at
2248 // most 64 with the default traits class, since we cannot know the degree
2249 // at compile time, only at run time.
2255 template <size_t N, typename Scalar>
2256 struct LambdaValue<PPerm<N, Scalar>> {
2259 using type = BitSet<BitSet<1>::max_size()>;
2260 };
2261
2267 template <size_t N, typename Scalar>
2268 struct RhoValue<PPerm<N, Scalar>> {
2272 };
2273
2278 template <size_t N, typename Scalar, size_t M>
2279 struct Lambda<PPerm<N, Scalar>, BitSet<M>> {
2282 void operator()(BitSet<M>& res, PPerm<N, Scalar> const& x) const;
2283 };
2284
2289 template <size_t N, typename Scalar, size_t M>
2290 struct Rho<PPerm<N, Scalar>, BitSet<M>> {
2293 void operator()(BitSet<M>& res, PPerm<N, Scalar> const& x) const;
2294 };
2295
2299 template <size_t N, typename Scalar>
2300 struct Rank<PPerm<N, Scalar>> {
2304 [[nodiscard]] size_t operator()(PPerm<N, Scalar> const& x) const {
2305 return x.rank();
2306 }
2307 };
2308
2310 // Perm
2312
2317 // TODO(later) this could work for everything derived from PTransf
2318 template <size_t N, typename Scalar, typename T>
2319 struct ImageRightAction<Perm<N, Scalar>,
2320 T,
2321 std::enable_if_t<std::is_integral_v<T>>> {
2323 void operator()(T& res,
2324 T const& pt,
2325 Perm<N, Scalar> const& p) const noexcept {
2326 LIBSEMIGROUPS_ASSERT(pt < p.degree());
2327 res = p[pt];
2328 }
2329
2331 [[nodiscard]] T operator()(T pt, Perm<N, Scalar> const& x) {
2332 return x[pt];
2333 }
2334 };
2335
2337 // Helpers
2339
2340 namespace detail {
2341 template <size_t N>
2342 struct LeastTransfHelper {
2343#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
2344 using type = std::conditional_t<N >= 17, Transf<N>, HPCombi::Transf16>;
2345#else
2346 using type = Transf<N>;
2347#endif
2348 };
2349
2350 template <size_t N>
2351 struct LeastPPermHelper {
2352#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
2353 using type = std::conditional_t<N >= 17, PPerm<N>, HPCombi::PPerm16>;
2354#else
2355 using type = PPerm<N>;
2356#endif
2357 };
2358
2359 template <size_t N>
2360 struct LeastPermHelper {
2361#ifdef LIBSEMIGROUPS_HPCOMBI_ENABLED
2362 using type = std::conditional_t<N >= 17, Perm<N>, HPCombi::Perm16>;
2363#else
2364 using type = Perm<N>;
2365#endif
2366 };
2367 } // namespace detail
2368
2381 template <size_t N>
2382 using LeastTransf = typename detail::LeastTransfHelper<N>::type;
2383
2396 template <size_t N>
2397 using LeastPPerm = typename detail::LeastPPermHelper<N>::type;
2398
2411 template <size_t N>
2412 using LeastPerm = typename detail::LeastPermHelper<N>::type;
2413
2438 template <size_t N, typename Scalar>
2440 std::string_view prefix = "",
2441 std::string_view braces = "{}");
2442
2467 template <size_t N, typename Scalar>
2469 std::string_view prefix = "",
2470 std::string_view braces = "{}");
2471
2497 template <size_t N, typename Scalar>
2499 std::string_view prefix = "",
2500 std::string_view braces = "{}");
2501
2531 template <size_t N, typename Scalar>
2533 std::string_view prefix = "",
2534 std::string_view braces
2535 = "{}",
2536 size_t max_width = 72);
2537
2566 template <size_t N, typename Scalar>
2568 std::string_view prefix = "",
2569 std::string_view braces
2570 = "{}",
2571 size_t max_width = 72);
2572
2603 template <size_t N, typename Scalar>
2605 std::string_view prefix = "",
2606 std::string_view braces
2607 = "{}",
2608 size_t max_width = 72);
2609} // namespace libsemigroups
2610
2611#include "transf.tpp"
2612
2613#endif // LIBSEMIGROUPS_TRANSF_HPP_
Partial transformations with dynamic degree.
Definition transf.hpp:747
DynamicPTransf(size_t n)
Construct with given degree.
Definition transf.hpp:787
size_t degree() const noexcept
Returns the degree of a partial transformation.
Definition transf.hpp:666
const_iterator end() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last image value.
Definition transf.hpp:577
DynamicPTransf & increase_degree_by(size_t m)
Increase the degree in-place.
Definition transf.hpp:805
Scalar point_type
Type of the image values.
Definition transf.hpp:756
std::vector< point_type > container_type
Type of the underlying container.
Definition transf.hpp:763
Partial permutations with static or dynamic degree.
Definition transf.hpp:1225
PPerm(std::initializer_list< point_type > dom, std::initializer_list< point_type > img, size_t M)
Construct from domain, range, and degree.
Definition transf.hpp:1274
PPerm(std::vector< OtherScalar > const &dom, std::vector< OtherScalar > const &img, size_t M)
Construct from domain, range, and degree.
Scalar point_type
Type of the image values.
Definition transf.hpp:1232
void product_inplace(PPerm const &f, PPerm const &g)
Multiply two partial perms and store the product in this.
static PPerm one(size_t M)
Returns the identity transformation on the given number of points.
Definition transf.hpp:1299
typename base_type::container_type container_type
Type of the underlying container.
Definition transf.hpp:1237
Base class for partial transformations.
Definition transf.hpp:129
typename Container::iterator iterator
Type of iterators pointing to image values.
Definition transf.hpp:534
bool operator==(PTransfBase const &that) const
Compare for equality.
Definition transf.hpp:366
Subclass operator*(Subclass const &that) const
Multiply by another partial transformation.
Definition transf.hpp:522
size_t rank() const
Returns the number of distinct image values.
Definition transf.hpp:624
typename Container::const_iterator const_iterator
Type of const iterators pointing to image values.
Definition transf.hpp:539
PTransfBase(PTransfBase const &)=default
Default copy constructor.
const_iterator begin() const noexcept
Definition transf.hpp:572
PTransfBase()=default
Default constructor.
bool operator>=(PTransfBase const &that) const
Compare for greater than or equal.
Definition transf.hpp:404
PTransfBase & operator=(PTransfBase const &)=default
Default copy assignment operator.
PTransfBase(std::initializer_list< Scalar > cont)
Construct from a container of images.
Definition transf.hpp:243
point_type const & at(size_t i) const
Get a const reference to the image of a point.
Definition transf.hpp:495
size_t degree() const noexcept
Returns the degree of a partial transformation.
Definition transf.hpp:666
const_iterator end() const noexcept
Definition transf.hpp:577
bool operator>(PTransfBase const &that) const
Compare for greater.
Definition transf.hpp:347
static Subclass make(OtherContainer &&cont)
Construct from universal reference container and check.
PTransfBase & operator=(PTransfBase &&)=default
Default move assignment operator.
PTransfBase(PTransfBase &&)=default
Default move constructor.
Scalar point_type
Type of the image values.
Definition transf.hpp:139
static Subclass make(std::initializer_list< OtherScalar > cont)
Construct from std::initializer_list and check.
iterator begin() noexcept
Returns an iterator (random access iterator) pointing at the first image value.
Definition transf.hpp:592
const_iterator cend() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last image value.
Definition transf.hpp:567
Container container_type
Type of the underlying container.
Definition transf.hpp:144
const_iterator cbegin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first image value.
Definition transf.hpp:552
point_type & at(size_t i)
Get a reference to the image of a point.
Definition transf.hpp:477
static Subclass one(size_t N)
Returns the identity transformation on the given number of points.
Definition transf.hpp:684
PTransfBase(Iterator first, Iterator last)
Construct from a range of images.
Definition transf.hpp:221
point_type & operator[](size_t i)
Get a reference to the image of a point.
Definition transf.hpp:441
static point_type undef() noexcept
Returns the value used to represent "undefined".
Definition transf.hpp:157
size_t hash_value() const
Returns a hash value.
Definition transf.hpp:641
bool operator<=(PTransfBase const &that) const
Compare for less than or equal.
Definition transf.hpp:385
bool operator<(PTransfBase const &that) const
Compare for less.
Definition transf.hpp:328
PTransfBase(Container const &cont)
Construct from a container of images.
Definition transf.hpp:195
point_type const & operator[](size_t i) const
Get a const reference to the image of a point.
Definition transf.hpp:459
void swap(PTransfBase &that) noexcept
Swap with another partial transformation.
Definition transf.hpp:651
PTransfBase(Container &&cont)
Construct from a container of images.
Definition transf.hpp:198
bool operator!=(PTransfBase const &that) const
Compare for inequality.
Definition transf.hpp:423
iterator end() noexcept
Returns an iterator (random access iterator) pointing one past the last image value.
Definition transf.hpp:607
Permutations with static or dynamic degree.
Definition transf.hpp:1534
static Perm one(size_t M)
Returns the identity transformation on the given number of points.
Definition transf.hpp:1552
Scalar point_type
Type of the image values.
Definition transf.hpp:1541
typename PTransf< N, point_type >::container_type container_type
Type of the underlying container.
Definition transf.hpp:1546
Partial transformations with static degree.
Definition transf.hpp:832
StaticPTransf & increase_degree_by(size_t)
Increase the degree in-place.
Definition transf.hpp:879
const_iterator begin() const noexcept
Returns a const_iterator (random access iterator) pointing at the first image value.
Definition transf.hpp:572
std::array< Scalar, N > container_type
Type of the underlying container.
Definition transf.hpp:842
const_iterator end() const noexcept
Returns a const_iterator (random access iterator) pointing one past the last image value.
Definition transf.hpp:577
StaticPTransf(size_t n)
Construct with given degree.
StaticPTransf()
Default constructor.
Definition transf.hpp:858
Scalar point_type
Type of the image values.
Definition transf.hpp:837
Transformations with static or dynamic degree.
Definition transf.hpp:1012
static Transf one(size_t M)
Returns the identity transformation on the given number of points.
Definition transf.hpp:1063
Scalar point_type
Type of the image values.
Definition transf.hpp:1019
void product_inplace(Transf const &f, Transf const &g)
Multiply two transformations and store the product in this.
typename base_type::container_type container_type
Type of the underlying container.
Definition transf.hpp:1024
T copy(T... args)
T distance(T... args)
T fill(T... args)
T forward(T... args)
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
Undefined const UNDEFINED
Value for something undefined.
#define LIBSEMIGROUPS_EXCEPTION(...)
Throw a LibsemigroupsException.
Definition exception.hpp:99
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:790
typename detail::LeastPermHelper< N >::type LeastPerm
Type of perms using the least memory for a given degree.
Definition transf.hpp:2412
static constexpr bool IsPPerm
Helper variable template.
Definition transf.hpp:1340
auto one(T const &f) -> std::enable_if_t< IsDerivedFromPTransf< T >, T >
Returns the identity transformation of same degree as a sample.
Definition transf.hpp:1805
static constexpr bool IsTransf
Helper variable template.
Definition transf.hpp:1096
typename detail::LeastTransfHelper< N >::type LeastTransf
Type of transformations using the least memory for a given degree.
Definition transf.hpp:2382
PPerm< N, Scalar > left_one(PPerm< N, Scalar > const &f)
Returns the left one of a partial perm.
typename detail::LeastPPermHelper< N >::type LeastPPerm
Type of partial perms using the least memory for a given degree.
Definition transf.hpp:2397
void domain(T const &f, std::vector< Scalar > &dom)
Replace the contents of a vector by the set of points where a partial transformation is defined.
static constexpr bool IsPTransf
Helper variable template.
Definition transf.hpp:943
PPerm< N, Scalar > right_one(PPerm< N, Scalar > const &f)
Returns the right one of a partial perm.
static constexpr bool IsDynamic
Helper variable template.
Definition transf.hpp:728
static constexpr bool IsStatic
Helper variable template.
Definition transf.hpp:718
void throw_if_not_pperm(PPerm< N, Scalar > const &f)
Check a partial perm.
Definition transf.hpp:1361
void image(T const &f, std::vector< Scalar > &im)
Replace the contents of a vector by the set of images of a partial transformation.
void throw_if_image_value_out_of_range(PTransfBase< Scalar, Container > const &f)
Check a partial transformation.
Definition transf.hpp:963
std::string to_input_string(Transf< N, Scalar > const &x, std::string_view prefix="", std::string_view braces="{}")
Return a string that can be used to recreate a transformation.
static constexpr bool IsPerm
Helper variable template.
Definition transf.hpp:1577
auto throw_if_not_perm(Perm< N, Scalar > const &f)
Check a permutation.
Definition transf.hpp:1598
static constexpr bool IsDerivedFromPTransf
Helper variable template.
Definition transf.hpp:103
std:: conditional_t< N==0, DynamicPTransf< Scalar >, StaticPTransf< N, Scalar > > PTransf
Partial transformations with static or dynamic degree.
Definition transf.hpp:911
void inverse(PPerm< N, Scalar > const &from, PPerm< N, Scalar > &to)
Replace contents of a partial perm with the inverse of another.
T iota(T... args)
T move(T... args)
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
auto to(detail::KnuthBendixImpl< Rewriter, ReductionOrder > &kb) -> std::enable_if_t< std::is_same_v< Presentation< typename Result::word_type >, Result >, Result >
No doc.
Adapter for the complexity of multiplication.
Definition adapters.hpp:121
Adapter for the degree of an element.
Definition adapters.hpp:159
Adapter for hashing.
Definition adapters.hpp:446
size_t operator()(Value const &x) const
Hash x using std::hash.
Definition adapters.hpp:455
void operator()(PPerm< N, Scalar > &res, PPerm< N, Scalar > const &pt, PPerm< N, Scalar > const &x) const noexcept
Stores the idempotent in res.
Definition transf.hpp:2211
void operator()(T &res, T const &pt, PPerm< N, Scalar > const &x) const
Definition transf.hpp:2235
void operator()(T &res, T const &pt, Transf< N, Scalar > const &x) const
Stores the image of pt under the left action of x in res.
Adapter for the value of a left action.
Definition adapters.hpp:350
void operator()(BitSet< M > &res, BitSet< M > const &pt, PPerm< N, Scalar > const &x) const
Stores the image set of pt under x in res.
void operator()(PPerm< N, Scalar > &res, PPerm< N, Scalar > const &pt, PPerm< N, Scalar > const &x) const noexcept
Stores the idempotent in res.
Definition transf.hpp:2168
void operator()(T &res, T const &pt, PPerm< N, Scalar > const &x) const
Stores the image set of pt under x in res.
void operator()(T &res, T const &pt, Perm< N, Scalar > const &p) const noexcept
Stores the image of pt under the action of p in res.
Definition transf.hpp:2323
T operator()(T pt, Perm< N, Scalar > const &x)
Returns the image of pt under the action of p.
Definition transf.hpp:2331
void operator()(BitSet< M > &res, BitSet< M > const &pt, Transf< N, Scalar > const &x) const
Stores the image set of pt under x in res.
Definition transf.hpp:2032
void operator()(T &res, T const &pt, Transf< N, Scalar > const &x) const
Stores the image set of pt under x in res.
Adapter for the value of a right action.
Definition adapters.hpp:392
void operator()(T &x, size_t n) const
Returns x->increase_degree_by(n).
Definition transf.hpp:2002
Adapter for increasing the degree of an element.
Definition adapters.hpp:199
Adapter for the inverse of an element.
Definition adapters.hpp:319
void operator()(BitSet< M > &res, PPerm< N, Scalar > const &x) const
void operator()(BitSet< M > &res, Transf< N, Scalar > const &x) const
void operator()(T &res, Transf< N, Scalar > const &x) const
Adapter for the action on LambdaValue's.
Definition adapters.hpp:833
BitSet< BitSet< 1 >::max_size()> type
Definition transf.hpp:2259
BitSet< BitSet< 1 >::max_size()> type
Definition transf.hpp:2070
Adapter for lambda functions.
Definition adapters.hpp:793
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284
size_t operator()(PPerm< N, Scalar > const &x) const
Definition transf.hpp:2304
size_t operator()(Transf< N, Scalar > const &x) const
Definition transf.hpp:2151
Adapter for calculating ranks.
Definition adapters.hpp:930
void operator()(BitSet< M > &res, PPerm< N, Scalar > const &x) const
void operator()(T &res, Transf< N, Scalar > const &x) const
Adapter for the action on RhoValue's.
Definition adapters.hpp:854
typename LambdaValue< PPerm< N, Scalar > >::type type
Definition transf.hpp:2271
std::vector< Scalar > type
Definition transf.hpp:2082
Adapter for rho functions.
Definition adapters.hpp:812
T swap(T... args)