libsemigroups  v3.2.0
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
adapters.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2019-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#ifndef LIBSEMIGROUPS_ADAPTERS_HPP_
20#define LIBSEMIGROUPS_ADAPTERS_HPP_
21
22#include <algorithm> // for std::sort
23#include <array> // for array
24#include <cstddef> // for size_t
25#include <functional> // for std::equal_to
26#include <iterator> // for pair
27#include <memory> // for shared_ptr
28#include <type_traits> // for hash, is_same
29#include <utility> // for pair, hash
30#include <vector> // for std::vector
31
32#include "config.hpp" // for LIBSEMIGROUPS_SIZEOF_VOID_P
33
34namespace libsemigroups {
35
82
83 // This is not technically an adapter but put here for lack of a better place
84 struct Noop {
85 template <typename... Args>
86 constexpr void operator()(Args...) const noexcept {}
87 };
88
89 struct ReturnFalse {
90 template <typename... Args>
91 [[nodiscard]] constexpr bool operator()(Args...) const noexcept {
92 return false;
93 }
94 };
95
127 template <typename Element, typename = void>
129
165 template <typename Element, typename = void>
166 struct Degree;
167
205 template <typename Element, typename = void>
207
252 template <typename Element, typename = void>
253 struct One;
254
290 template <typename Element, typename = void>
291 struct Product;
292
325 template <typename Element, typename = void>
326 struct Inverse;
327
356 template <typename Element, typename Point, typename = void>
358
398 template <typename Element, typename Point, typename = void>
400
419 template <typename Value, typename = void>
420 struct EqualTo {
430 bool operator()(Value const& x, Value const& y) const {
431 return std::equal_to<Value>()(x, y);
432 }
433 };
434
452 template <typename Value, typename = void>
453 struct Hash {
462 size_t operator()(Value const& x) const {
463 return std::hash<Value>()(x);
464 }
465 };
466
468 // Hash specializations
470
483 template <typename T>
484 struct Hash<std::vector<T>> {
494 size_t operator()(std::vector<T> const& vec) const {
495 return Hash<std::vector<T>, Hash<T>>()(vec);
496 }
497 };
498
499 // TODO(2) same for array!
500
513 // TODO(later) What uses this?
514 template <typename T, typename Hasher>
515 struct Hash<std::vector<T>, Hasher> {
523 size_t operator()(std::vector<T> const& vec) const {
524 size_t val = 0;
525 for (T const& x : vec) {
526 val ^= Hasher()(x) + 0x9e3779b97f4a7c16 + (val << 6) + (val >> 2);
527 }
528 return val;
529 }
530 };
531
544 // TODO(later) What uses this?
545 template <typename T, size_t N>
546 struct Hash<std::array<T, N>> {
554 size_t operator()(std::array<T, N> const& ar) const {
555 size_t val = 0;
556 for (T const& x : ar) {
557 val ^= Hash<T>()(x) + 0x9e3779b97f4a7c16 + (val << 6) + (val >> 2);
558 }
559 return val;
560 }
561 };
562
576 // TODO(later) What uses this?
577 template <typename S, typename T>
578 struct Hash<std::pair<S, T>> {
586 size_t operator()(std::pair<S, T> const& x) const noexcept {
587 size_t val = 0;
588 val ^= Hash<S>()(x.first) + 0x9e3779b97f4a7c16 + (val << 6) + (val >> 2);
589 val ^= Hash<T>()(x.second) + 0x9e3779b97f4a7c16 + (val << 6) + (val >> 2);
590 return val;
591 }
592 };
593
604 template <>
605 struct Hash<std::pair<size_t, size_t>> {
613 size_t operator()(std::pair<size_t, size_t> const& x) const noexcept {
614 // TODO(2) this is a very bad hash when the values are larger than the
615 // shift width
616#if LIBSEMIGROUPS_SIZEOF_VOID_P == 8
617 return (x.first << 32) + x.second;
618#else
619 return (x.first << 16) + x.second;
620#endif
621 }
622 };
623
640 template <typename Value, typename = void>
641 struct Less {
651 bool operator()(Value const& x, Value const& y) const {
652 return std::less<Value>()(x, y);
653 }
654 };
655
672 template <typename Value, typename = void>
673 struct Swap {
680 void operator()(Value& x, Value& y) {
681 std::swap(x, y);
682 }
683 };
684
696 template <typename Element,
697 typename Point,
698 typename Container = std::vector<Point>>
699 struct OnTuples {
701 "the 3rd template parameter is not a container of objects of "
702 "type the 2nd template parameter");
721 void operator()(Container& res,
722 Container const& pt,
723 Element const& x) const {
724 for (size_t i = 0; i < pt.size(); ++i) {
725 ImageRightAction<Element, Point>()(res[i], pt[i], x);
726 }
727 }
728 };
729
743 // TODO(2) add a template param for sorting
744 template <typename Element,
745 typename Point,
746 typename Container = std::vector<Point>>
747 struct OnSets {
771 void operator()(Container& res,
772 Container const& pt,
773 Element const& p) const {
775 std::sort(res.begin(), res.end());
776 }
777 };
778
780 // KONIECZNY THINGS
782
797 // Note: this has to exist in order to allow different lambda functions based
798 // on type.
799 template <typename Element, typename = void>
801
816 // Note: this has to exist in order to allow different rho functions based
817 // on type.
818 template <typename Element, typename = void>
819 struct RhoValue;
820
839 template <typename Element, typename Point, typename = void>
840 struct Lambda;
841
860 template <typename Element, typename Point, typename = void>
861 struct Rho;
862
863 // TODO(now) does this brief make sense?
883 template <typename Element, typename = void>
884 class RankState {
885 public:
888 using type = void;
889
891 RankState() noexcept = default;
892
894 template <typename T>
895 RankState(T, T) noexcept {}
896
897 // Other constructors are deleted.
899 RankState(RankState const&) = default;
901 RankState(RankState&&) = delete;
903 RankState& operator=(RankState const&) = delete;
906 };
907
934 template <typename Element,
935 typename State = RankState<Element>,
936 typename = void>
937 struct Rank;
938
939} // namespace libsemigroups
940#endif // LIBSEMIGROUPS_ADAPTERS_HPP_
Base class for states for ranks.
Definition adapters.hpp:884
RankState & operator=(RankState const &)=delete
Deleted.
RankState(RankState const &)=default
Deleted.
RankState & operator=(RankState &&)=delete
Deleted.
void type
Definition adapters.hpp:888
RankState() noexcept=default
Default constructor; does nothing.
RankState(RankState &&)=delete
Deleted.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T sort(T... args)
Adapter for the complexity of multiplication.
Definition adapters.hpp:128
Adapter for the degree of an element.
Definition adapters.hpp:166
Adapter for testing equality.
Definition adapters.hpp:420
bool operator()(Value const &x, Value const &y) const
Compare x and y with std::equal_to.
Definition adapters.hpp:430
size_t operator()(std::array< T, N > const &ar) const
Hashes ar.
Definition adapters.hpp:554
size_t operator()(std::pair< S, T > const &x) const noexcept
Hashes x.
Definition adapters.hpp:586
size_t operator()(std::vector< T > const &vec) const
Hashes vec.
Definition adapters.hpp:523
size_t operator()(std::vector< T > const &vec) const
Hashes vec.
Definition adapters.hpp:494
Adapter for hashing.
Definition adapters.hpp:453
size_t operator()(Value const &x) const
Hash x using std::hash.
Definition adapters.hpp:462
Adapter for the value of a left action.
Definition adapters.hpp:357
Adapter for the value of a right action.
Definition adapters.hpp:399
Adapter for increasing the degree of an element.
Definition adapters.hpp:206
Adapter for the inverse of an element.
Definition adapters.hpp:326
Adapter for the action on LambdaValue's.
Definition adapters.hpp:840
Adapter for lambda functions.
Definition adapters.hpp:800
Adapter for comparisons.
Definition adapters.hpp:641
bool operator()(Value const &x, Value const &y) const
Compare if x is less than y.
Definition adapters.hpp:651
Adapter for calculating right actions of each element in a container.
Definition adapters.hpp:747
void operator()(Container &res, Container const &pt, Element const &p) const
Calculate right actions of each element in a container, then sort.
Definition adapters.hpp:771
Adapter for calculating right actions of each element in a container.
Definition adapters.hpp:699
void operator()(Container &res, Container const &pt, Element const &x) const
Calculate right actions of each element in a container.
Definition adapters.hpp:721
Adapter for the identity element of the given type.
Definition adapters.hpp:253
Adapter for the product of two elements.
Definition adapters.hpp:291
Adapter for calculating ranks.
Definition adapters.hpp:937
Adapter for the action on RhoValue's.
Definition adapters.hpp:861
Adapter for rho functions.
Definition adapters.hpp:819
Adapter for swapping.
Definition adapters.hpp:673
void operator()(Value &x, Value &y)
Swap x and y.
Definition adapters.hpp:680
T swap(T... args)