libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
kbe.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// This file contains the declaration of the class KBE, which can be used as
20// the element_type for a FroidurePin instance. This class just wraps a
21// reduced word of a KnuthBendixImpl instance.
22
23#ifndef LIBSEMIGROUPS_DETAIL_KBE_HPP_
24#define LIBSEMIGROUPS_DETAIL_KBE_HPP_
25
26#include <cstddef> // for size_t
27#include <string> // for string
28#include <utility> // for hash
29
30#include "libsemigroups/adapters.hpp" // for One
31#include "libsemigroups/froidure-pin.hpp" // for FroidurePin
32#include "libsemigroups/obvinf.hpp" // for is_obviously_infinite
33#include "libsemigroups/types.hpp" // for word_type, letter_type
34#include "libsemigroups/word-range.hpp" // for namespace words
35
36namespace libsemigroups {
37 namespace detail {
38 // This class is used to wrap KnuthBendix_::native_word_type into an
39 // object that can be used as generators for a FroidurePin object.
40 template <typename KnuthBendix_>
41 class KBE {
42 public:
43 using knuth_bendix_type = KnuthBendix_;
44 using native_word_type = typename KnuthBendix_::native_word_type;
45 using native_letter_type =
46 typename KnuthBendix_::native_word_type::value_type;
47
48 KBE() = default;
49
50 KBE(KBE const&) = default;
51 KBE(KBE&&) = default;
52
53 KBE& operator=(KBE const&) = default;
54 KBE& operator=(KBE&&) = default;
55
56 ~KBE() = default;
57
58 // Construct from external types
59 KBE(knuth_bendix_type&, native_letter_type const&);
60 KBE(knuth_bendix_type&, native_word_type const&);
61
62 bool operator==(KBE const&) const;
63 bool operator<(KBE const&) const;
64 void swap(KBE&);
65
66 native_word_type const& word() const noexcept;
67
68 friend std::ostringstream& operator<<(std::ostringstream& os,
69 KBE const& kbe) {
70 os << kbe.word();
71 return os;
72 }
73
74 private:
75 native_word_type _kb_word;
76 };
77
78 } // namespace detail
79
81 // Adapters for KBE class
83
84 template <typename KnuthBendix_>
85 struct Complexity<detail::KBE<KnuthBendix_>> {
86 constexpr size_t
87 operator()(detail::KBE<KnuthBendix_> const&) const noexcept {
88 return LIMIT_MAX;
89 }
90 };
91
92 template <typename KnuthBendix_>
93 struct Degree<detail::KBE<KnuthBendix_>> {
94 constexpr size_t
95 operator()(detail::KBE<KnuthBendix_> const&) const noexcept {
96 return 0;
97 }
98 };
99
100 template <typename KnuthBendix_>
101 struct IncreaseDegree<detail::KBE<KnuthBendix_>> {
102 void operator()(detail::KBE<KnuthBendix_> const&, size_t) const noexcept {}
103 };
104
105 template <typename KnuthBendix_>
106 struct One<detail::KBE<KnuthBendix_>> {
107 detail::KBE<KnuthBendix_>
108 operator()(detail::KBE<KnuthBendix_> const&) const noexcept {
109 return detail::KBE<KnuthBendix_>();
110 }
111
112 detail::KBE<KnuthBendix_> operator()(size_t = 0) const noexcept {
113 return detail::KBE<KnuthBendix_>();
114 }
115 };
116
117 template <typename KnuthBendix_>
118 struct Product<detail::KBE<KnuthBendix_>> {
119 void operator()(detail::KBE<KnuthBendix_>& xy,
120 detail::KBE<KnuthBendix_> const& x,
121 detail::KBE<KnuthBendix_> const& y,
122 KnuthBendix_* kb,
123 size_t) {
124 using words::operator+=;
125 using KBE_ = detail::KBE<KnuthBendix_>;
126 auto w(x.word());
127 w += y.word();
128 // TODO improve
129 xy = KBE_(*kb, w);
130 }
131 };
132
133 template <typename KnuthBendix_>
134 struct FroidurePinState<detail::KBE<KnuthBendix_>> {
135 using type = KnuthBendix_;
136 };
137
138 // template <>
139 // word_type FroidurePin<detail::KBE<KnuthBendixImpl<>>>::factorisation(
140 // detail::KBE<KnuthBendixImpl<>> const& x);
141
142 // template <>
143 // tril FroidurePin<detail::KBE<KnuthBendixImpl<>>>::is_finite() const;
144
145} // namespace libsemigroups
146
148// Specializations of std::hash and std::equal_to
150
151namespace std {
152 template <typename KnuthBendix_>
153 struct hash<libsemigroups::detail::KBE<KnuthBendix_>> {
154 size_t operator()(libsemigroups::detail::KBE<KnuthBendix_> const& x) const {
155 return hash<typename libsemigroups::detail::KBE<
156 KnuthBendix_>::native_word_type>()(x.word());
157 }
158 };
159
160 template <typename KnuthBendix_>
161 struct equal_to<libsemigroups::detail::KBE<KnuthBendix_>> {
162 bool operator()(libsemigroups::detail::KBE<KnuthBendix_> const& x,
163 libsemigroups::detail::KBE<KnuthBendix_> const& y) const {
164 return x == y;
165 }
166 };
167} // namespace std
168
169#include "kbe.tpp"
170
171#endif // LIBSEMIGROUPS_DETAIL_KBE_HPP_
LimitMax const LIMIT_MAX
Value for the maximum of something.
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T operator()(T... args)
Adapter for the complexity of multiplication.
Definition adapters.hpp:121
Adapter for the degree of an element.
Definition adapters.hpp:159
Adapter for increasing the degree of an element.
Definition adapters.hpp:199
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284