libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
ke.hpp
1//
2// libsemigroups - C++ library for semigroups and monoids
3// Copyright (C) 2023-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_KE_HPP_
24#define LIBSEMIGROUPS_DETAIL_KE_HPP_
25
26#include <cstddef> // for size_t
27#include <functional> // for hash
28#include <string> // for basic_string
29#include <type_traits> // for enable_if_t, integral_constant
30
31#include "libsemigroups/adapters.hpp" // for Complexity
32#include "libsemigroups/constants.hpp" // for Max, LimitMax, LIMIT_MAX
33#include "libsemigroups/froidure-pin.hpp" // for FroidurePin, FroidurePi...
34#include "libsemigroups/kambites-class.hpp" // for Kambites
35#include "libsemigroups/order.hpp" // for shortlex_compare
36#include "libsemigroups/presentation.hpp" // for to_word
37#include "libsemigroups/types.hpp" // for word_type, tril
38#include "libsemigroups/word-range.hpp" // for ToWord, ToString
39
40namespace libsemigroups {
41 namespace detail {
42 // This class is used to wrap libsemigroups::Kambites::value_type into an
43 // object that can be used as generators for a FroidurePin object.
44 template <typename Word>
45 class KE {
46 public:
47 using value_type = typename Kambites<Word>::native_word_type;
48 using native_word_type = typename Kambites<Word>::native_word_type;
49
50 private:
51 value_type _value;
52
53 public:
54 KE() = default;
55 KE(KE const&) = default;
56 KE(KE&&) = default;
57 KE& operator=(KE const&) = default;
58 KE& operator=(KE&&) = default;
59 ~KE() = default;
60
61 KE(Kambites<Word>& k, value_type const& w) : _value() {
62 k.reduce_no_checks(std::back_inserter(_value), w.begin(), w.end());
63 }
64
65 // KE(Kambites<Word>& k, value_type&& w)
66 // : _value(kambites::reduce_no_checks(k, std::move(w))) {}
67
68 KE(Kambites<Word>& k, letter_type a)
69 : KE(k, value_type({k.presentation().letter_no_checks(a)})) {}
70
71 bool operator==(KE const& that) const {
72 return that._value == this->_value;
73 }
74
75 bool operator<(KE const& that) const {
76 return shortlex_compare(_value, that._value);
77 }
78
79 void swap(KE& x) {
80 std::swap(x._value, _value);
81 }
82
83 value_type const& value() const noexcept {
84 return _value;
85 }
86
87 word_type to_word(Kambites<Word> const& k) const {
88 v4::ToWord<std::string> to_word(k.presentation().alphabet());
89 return to_word(_value);
90 }
91
92 template <typename SFINAE = std::string>
93 auto to_string() const noexcept
94 -> std::enable_if_t<!std::is_same_v<Word, word_type>, SFINAE> {
95 return _value;
96 }
97 };
98
99 template <>
100 word_type KE<word_type>::to_word(Kambites<word_type> const&) const;
101
102 // The following are not really required but are here as a reminder that
103 // KE are used in BruidhinnTraits which depends on the values in the
104 // static_asserts below.
105 static_assert(!std::is_trivial<KE<std::string>>::value,
106 "KE is not trivial!!!");
107 static_assert(
108 std::integral_constant<bool, (sizeof(KE<std::string>) <= 32)>::value,
109 "KE's sizeof exceeds 32!!");
110
111 } // namespace detail
112
113 template <typename Word>
114 struct FroidurePinState<detail::KE<Word>> {
115 using type = Kambites<Word>;
116 };
117
119 // Adapters for KE class
121
122 template <typename Word>
123 struct Complexity<detail::KE<Word>> {
124 constexpr size_t operator()(detail::KE<Word> const&) const noexcept {
125 return LIMIT_MAX;
126 }
127 };
128
129 template <typename Word>
130 struct Degree<detail::KE<Word>> {
131 constexpr size_t operator()(detail::KE<Word> const&) const noexcept {
132 return 0;
133 }
134 };
135
136 template <typename Word>
137 struct IncreaseDegree<detail::KE<Word>> {
138 void operator()(detail::KE<Word> const&, size_t) const noexcept {}
139 };
140
141 template <typename Word>
142 struct One<detail::KE<Word>> {
143 detail::KE<Word> operator()(detail::KE<Word> const&) {
144 return detail::KE<Word>();
145 }
146
147 detail::KE<Word> operator()(size_t = 0) const {
148 return detail::KE<Word>();
149 }
150 };
151
152 template <typename Word>
153 struct Product<detail::KE<Word>> {
154 void operator()(detail::KE<Word>& xy,
155 detail::KE<Word> const& x,
156 detail::KE<Word> const& y,
157 Kambites<Word>* k,
158 size_t) {
159 using value_type = typename detail::KE<Word>::value_type;
160 using words::operator+=;
161 value_type w(x.value()); // string_type
162 w += y.value();
163 xy = detail::KE<Word>(*k, w);
164 }
165 };
166
167#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
168 // TODO(1) uncomment
169 // template <>
170 // word_type FroidurePin<
171 // detail::KE<std::string>,
172 // FroidurePinTraits<detail::KE<std::string>, Kambites<std::string>>>::
173 // factorisation(detail::KE<std::string> const& x);
174
175 // template <>
176 // word_type FroidurePin<detail::KE<detail::MultiView>,
177 // FroidurePinTraits<detail::KE<detail::MultiView>,
178 // Kambites<detail::MultiView>>>::
179 // factorisation(detail::KE<detail::MultiView> const& x);
180
181 // template <>
182 // word_type
183 // FroidurePin<detail::KE<word_type>,
184 // FroidurePinTraits<detail::KE<word_type>,
185 // Kambites<word_type>>>::
186 // factorisation(detail::KE<word_type> const& x);
187
188 template <>
191 Kambites<std::string>>>::is_finite() const;
192
193 template <>
195 detail::KE<detail::MultiView<std::string>>,
197 Kambites<detail::MultiView<std::string>>>>::is_finite()
198 const;
199
200 template <>
203 Kambites<word_type>>>::is_finite() const;
204
205// TODO(1) this doesn't work because size is a mem fn of FroidurePinBase...
206// template <>
207// [[nodiscard]] size_t
208// FroidurePin<detail::KE<std::string>,
209// FroidurePinTraits<detail::KE<std::string>,
210// Kambites<std::string>>>::size();
211//
212// template <>
213// [[nodiscard]] size_t
214// FroidurePin<detail::KE<detail::MultiView>,
215// FroidurePinTraits<detail::KE<detail::MultiView>,
216// Kambites<detail::MultiView>>>::size();
217//
218// template <>
219// [[nodiscard]] size_t FroidurePin<
220// detail::KE<word_type>,
221// FroidurePinTraits<detail::KE<word_type>, Kambites<word_type>>>::size();
222#endif
223
224} // namespace libsemigroups
225
227// Specializations of std::hash and std::equal_to
229
230namespace std {
231 template <typename Word>
232 struct hash<libsemigroups::detail::KE<Word>> {
233 size_t operator()(libsemigroups::detail::KE<Word> const& x) const {
234 using value_type = typename libsemigroups::detail::KE<Word>::value_type;
235 return hash<value_type>()(x.value());
236 }
237 };
238
239 template <typename Word>
240 struct equal_to<libsemigroups::detail::KE<Word>> {
241 bool operator()(libsemigroups::detail::KE<Word> const& x,
242 libsemigroups::detail::KE<Word> const& y) const {
243 return x == y;
244 }
245 };
246} // namespace std
247#endif // LIBSEMIGROUPS_DETAIL_KE_HPP_
T back_inserter(T... args)
Class implementing the Froidure-Pin algorithm.
Definition froidure-pin.hpp:188
LimitMax const LIMIT_MAX
Value for the maximum of something.
Kambites(congruence_kind, Presentation< Word > const &) -> Kambites< Word >
Deduction guide.
std::conditional_t< std::is_same_v< Word, detail::MultiView< std::string > >, std::string, Word > native_word_type
Type of the words in the relations of the presentation stored in a Kambites instance.
Definition kambites-class.hpp:164
bool shortlex_compare(T const &first1, T const &last1, T const &first2, T const &last2)
Compare two objects of the same type using the short-lex reduction ordering.
Definition order.hpp:273
std::vector< letter_type > word_type
Type for a word over the generators of a semigroup.
Definition types.hpp:99
size_t letter_type
Type for the index of a generator of a semigroup.
Definition types.hpp:96
tril
Enum to indicate true, false or not currently knowable.
Definition types.hpp:54
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
Traits class for FroidurePin.
Definition froidure-pin.hpp:68
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
T swap(T... args)