libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
froidure-pin.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_FROIDURE_PIN_HPP_
20#define LIBSEMIGROUPS_FROIDURE_PIN_HPP_
21
22#include <cstddef> // for size_t
23#include <initializer_list> // for initializer_list
24#include <iterator> // for make_move_iterator
25#include <memory> // for shared_ptr, make_shared
26#include <mutex> // for mutex
27#include <type_traits> // for is_const, remove_pointer
28#include <unordered_map> // for unordered_map
29#include <utility> // for pair
30#include <vector> // for vector
31
32#include "adapters.hpp" // for Complexity, Degree, IncreaseDegree
33#include "debug.hpp" // for LIBSEMIGROUPS_ASSERT
34#include "exception.hpp" // for LIBSEMIGROUPS_EXCEPTION
35#include "froidure-pin-base.hpp" // for FroidurePinBase, FroidurePinBase::s...
36#include "types.hpp" // for letter_type, word_type
37
38#include "detail/bruidhinn-traits.hpp" // for detail::BruidhinnTraits
39#include "detail/iterator.hpp" // for ConstIteratorStateless
40#include "detail/report.hpp" // for report_default
41#include "detail/stl.hpp" // for EqualTo, Hash
42
43#include "rx/ranges.hpp" // for iterator_range
44
46namespace libsemigroups {
47
48 template <typename T>
49 struct FroidurePinState {
50 using type = void;
51 };
52
66 template <typename Element,
67 typename State = typename FroidurePinState<Element>::type>
69 // Require to get the value_type from detail::BruidhinnTraits to remove
70 // pointer to const.
75 using element_type = typename detail::BruidhinnTraits<Element>::value_type;
76
81 using state_type = State;
82
85
88
91
94
97
100
103
106
109 };
110
186 template <typename Element, typename Traits = FroidurePinTraits<Element>>
187 class FroidurePin : private detail::BruidhinnTraits<Element>,
188 public FroidurePinBase {
189 private:
191 // FroidurePin - typedefs - private
193
194 using internal_element_type =
195 typename detail::BruidhinnTraits<Element>::internal_value_type;
196 using internal_const_element_type =
197 typename detail::BruidhinnTraits<Element>::internal_const_value_type;
198 using internal_const_reference =
199 typename detail::BruidhinnTraits<Element>::internal_const_reference;
200 using internal_idempotent_pair
202
203 static_assert(
204 std::is_const_v<internal_const_element_type>
205 || std::is_const_v<
206 std::remove_pointer_t<internal_const_element_type>>,
207 "internal_const_element_type must be const or pointer to const");
208
209 // The elements of a semigroup are stored in _elements, but because of the
210 // way add_generators/closure work, it might not be the case that all the
211 // words of a given length are contiguous in _elements. Hence we require a
212 // means of finding the next element of a given length. In
213 // _enumerate_order, the first K_1 values are element_index_type's equal to
214 // the positions in _elements of the words of length 1, the next K_2 values
215 // are the element_index_type's equal to the positions in _elements of the
216 // words of length 2, and so on.
217 //
218 // This alias is used to distinguish variables that refer to positions in
219 // _elements (element_index_type) from those that refer to positions in
220 // _enumerate_order (enumerate_index_type).
221 using enumerate_index_type = FroidurePinBase::enumerate_index_type;
222
223 struct InternalEqualTo : private detail::BruidhinnTraits<Element> {
224 [[nodiscard]] bool operator()(internal_const_reference x,
225 internal_const_reference y) const {
226 return EqualTo()(this->to_external_const(x),
227 this->to_external_const(y));
228 }
229 };
230
231 struct InternalHash : private detail::BruidhinnTraits<Element> {
232 [[nodiscard]] size_t operator()(internal_const_reference x) const {
233 return Hash()(this->to_external_const(x));
234 }
235 };
236
237 using map_type = std::unordered_map<internal_const_element_type,
239 InternalHash,
240 InternalEqualTo>;
241
242 public:
244 // FroidurePin - typedefs - public
246
248 using element_type = typename detail::BruidhinnTraits<Element>::value_type;
249
251 // This only really exists to allow the python bindings to compile with
252 // gcc-6 + 7 (at least).
253 using value_type = element_type;
254
256 using const_element_type =
257 typename detail::BruidhinnTraits<Element>::const_value_type;
258
260 using const_reference =
261 typename detail::BruidhinnTraits<Element>::const_reference;
262
264 using rvalue_reference =
265 typename detail::BruidhinnTraits<Element>::rvalue_reference;
266
268 using reference = typename detail::BruidhinnTraits<Element>::reference;
269
271 using const_pointer =
272 typename detail::BruidhinnTraits<Element>::const_pointer;
273
276
279
282
284 using state_type = typename Traits::state_type;
285
287 using Complexity = typename Traits::Complexity;
288
290 using Degree = typename Traits::Degree;
291
293 using EqualTo = typename Traits::EqualTo;
294
296 using Hash = typename Traits::Hash;
297
299 using IncreaseDegree = typename Traits::IncreaseDegree;
300
302 using Less = typename Traits::Less;
303
305 using One = typename Traits::One;
306
308 using Product = typename Traits::Product;
309
311 using Swap = typename Traits::Swap;
312
313 private:
314 template <typename T>
315 static constexpr bool IsState
316 = ((!std::is_void_v<T>) &&std::is_same_v<state_type, T>);
317
319 // FroidurePin - data - private
321
324 internal_element_type _id;
326 map_type _map;
327 mutable std::mutex _mtx;
330 mutable internal_element_type _tmp_product;
331
332 void internal_product(reference xy,
335 state_type* stt,
336 size_t tid = 0) const {
337 if constexpr (std::is_void_v<state_type>) {
338 (void) stt; // To silence warnings in g++-9
339 Product()(xy, x, y, tid);
340 } else {
341 Product()(xy, x, y, stt, tid);
342 }
343 }
344
345 public:
347 // FroidurePin - constructors + destructor - public
349
355 FroidurePin();
356
366 FroidurePin& init();
367
380 template <typename State, typename = std::enable_if_t<IsState<State>>>
382 _state = stt;
383 }
384
396 template <typename State, typename = std::enable_if_t<IsState<State>>>
398 init();
399 _state = stt;
400 }
401
418 template <typename State, typename = std::enable_if_t<IsState<State>>>
419 explicit FroidurePin(State const& stt)
420 : FroidurePin(std::make_shared<state_type>(stt)) {}
421
433 template <typename State, typename = std::enable_if_t<IsState<State>>>
434 FroidurePin& init(State const& stt) {
436 }
437
440
442 FroidurePin& operator=(FroidurePin&&) = default;
443
458 template <typename Iterator1, typename Iterator2>
459 FroidurePin(Iterator1 first, Iterator2 last);
460
477 template <typename Iterator1, typename Iterator2>
478 FroidurePin& init(Iterator1 first, Iterator2 last);
479
490 FroidurePin(FroidurePin const& that);
491
493 FroidurePin(FroidurePin&&) = default;
494
495 ~FroidurePin();
496
497 private:
498 void free_data();
499
501 // FroidurePin - constructor - private
503
505
506 public:
508 // FroidurePin - member functions - public
510
539 template <typename Iterator1, typename Iterator2>
540 [[nodiscard]] const_reference to_element_no_checks(Iterator1 first,
541 Iterator2 last) const;
542
572 template <typename Iterator1, typename Iterator2>
573 [[nodiscard]] const_reference to_element(Iterator1 first,
574 Iterator2 last) const;
575
600 template <typename Iterator1,
601 typename Iterator2,
602 typename Iterator3,
603 typename Iterator4>
604 [[nodiscard]] bool equal_to_no_checks(Iterator1 first1,
605 Iterator2 last1,
606 Iterator3 first2,
607 Iterator4 last2) const;
608
631 template <typename Iterator1,
632 typename Iterator2,
633 typename Iterator3,
634 typename Iterator4>
635 [[nodiscard]] bool equal_to(Iterator1 first1,
636 Iterator2 last1,
637 Iterator3 first2,
638 Iterator4 last2) const {
641 return equal_to_no_checks(first1, last1, first2, last2);
642 }
643
655 [[nodiscard]] size_t number_of_generators() const noexcept override;
656
677 [[nodiscard]] const_reference generator(generator_index_type i) const;
678
699 [[nodiscard]] const_reference
701
723
724#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
726#endif
727
761 [[nodiscard]] element_index_type
763
778 //! This function does not trigger any enumeration.
780 element_index_type j) const {
783 return fast_product_no_checks(i, j);
784 }
785
799 [[nodiscard]] size_t number_of_idempotents();
800
816 // TODO(1) improve this it doesn't need to trigger a full enum.
817 [[nodiscard]] bool is_idempotent_no_checks(element_index_type i);
818
833 //! This function triggers a full enumeration.
834 [[nodiscard]] bool is_idempotent(element_index_type i) {
835 run();
837 return is_idempotent_no_checks(i);
838 }
839
857 FroidurePin& reserve(size_t val);
858
872 [[nodiscard]] bool contains(const_reference x);
873
891
910
927 // There's no no-checks version of this, there can't be.
929
944 [[nodiscard]] const_reference at(element_index_type i);
945
961
977
993
994#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
995 // The following are required, they are documented in FroidurePinBase.
996 // Sphinx/doxygen get confused by this, so we don't allow Doxygen to parse
997 // these two declarations.
1000#endif
1001
1020 //! No enumeration is triggered by calls to this function.
1021 [[nodiscard]] tril is_finite() const override {
1022 return tril::TRUE;
1023 }
1024
1043 template <typename Iterator1, typename Iterator2>
1044 FroidurePin& add_generators_no_checks(Iterator1 first, Iterator2 last);
1045
1064 template <typename Iterator1, typename Iterator2>
1065 FroidurePin& add_generators(Iterator1 first, Iterator2 last);
1066
1105
1144
1145 // TODO(1) make the following work
1146 // FroidurePin add_generator(rvalue_reference x);
1147
1169 template <typename Iterator1, typename Iterator2>
1170 [[nodiscard]] FroidurePin
1171 copy_add_generators_no_checks(Iterator1 first, Iterator2 last) const;
1172
1197 template <typename Iterator1, typename Iterator2>
1198 [[nodiscard]] FroidurePin copy_add_generators(Iterator1 first,
1199 Iterator2 last) const {
1200 throw_if_degree_too_small(first, last);
1201 throw_if_inconsistent_degree(first, last);
1202 return copy_add_generators_no_checks(first, last);
1203 }
1204
1205 // TODO(1) copy_add_generator
1206 // TODO(1) copy_add_generators_no_checks
1207
1238 template <typename Iterator1, typename Iterator2>
1239 FroidurePin& closure_no_checks(Iterator1 first, Iterator2 last);
1240
1263 template <typename Iterator1, typename Iterator2>
1264 FroidurePin& closure(Iterator1 first, Iterator2 last) {
1265 throw_if_degree_too_small(first, last);
1266 throw_if_inconsistent_degree(first, last);
1267 return closure_no_checks(first, last);
1268 }
1269
1270 // TODO(1) closure(const_reference)
1271 // TODO(1) closure_no_checks(const_reference)
1272
1297 template <typename Iterator1, typename Iterator2>
1298 [[nodiscard]] FroidurePin copy_closure_no_checks(Iterator1 first,
1299 Iterator2 last);
1300
1328 template <typename Iterator1, typename Iterator2>
1329 [[nodiscard]] FroidurePin copy_closure(Iterator1 first, Iterator2 last) {
1330 throw_if_degree_too_small(first, last);
1331 throw_if_inconsistent_degree(first, last);
1332 return copy_closure_no_checks(first, last);
1333 }
1334
1335 // TODO(1) copy_closure(const_reference)
1336 // TODO(1) copy_closure_no_checks(const_reference)
1337
1344 //! \no_libsemigroups_except
1346 return _state;
1347 }
1348
1364 template <typename Iterator1, typename Iterator2>
1365 static void throw_if_inconsistent_degree(Iterator1 first, Iterator2 last);
1366
1367 private:
1369 // FroidurePin - validation member functions - private
1371
1372 void throw_if_bad_degree(const_reference) const;
1373
1374 template <typename Iterator1, typename Iterator2>
1375 void throw_if_bad_degree(Iterator1, Iterator2) const;
1376
1377 template <typename Iterator1, typename Iterator2>
1378 void throw_if_degree_too_small(Iterator1, Iterator2) const;
1379
1381 // FroidurePin - enumeration member functions - private
1383
1384 void expand(size_type);
1385 void is_one(internal_const_element_type x, element_index_type) noexcept(
1386 std::is_nothrow_default_constructible_v<InternalEqualTo>&& noexcept(
1388
1389 void copy_generators_from_elements(size_t);
1390 void closure_update(element_index_type,
1394 size_type,
1395 size_t const&,
1397 state_type*);
1398
1399 void init_degree(const_reference);
1400
1401 template <typename Iterator1, typename Iterator2>
1402 void add_generators_before_start(Iterator1, Iterator2);
1403
1404 template <typename Iterator1, typename Iterator2>
1405 void add_generators_after_start(Iterator1, Iterator2);
1406
1408 // FroidurePin - initialisation member functions - private
1410
1411 void init_sorted();
1412 void init_idempotents();
1413 void idempotents(enumerate_index_type,
1414 enumerate_index_type,
1415 enumerate_index_type,
1417
1418 // Forward declarations - implemented in froidure-pin.tpp
1419 struct DerefPairFirst;
1420 struct AddressOfPairFirst;
1421 struct IteratorPairFirstTraits;
1422
1424 // FroidurePin - iterators - private
1426
1427 // A type for const iterators through (element, index) pairs of \c this.
1428 using const_iterator_pair_first
1429 = detail::ConstIteratorStateless<IteratorPairFirstTraits>;
1430
1431 public:
1433 // FroidurePin - iterators - public
1440 using const_iterator
1441 = detail::BruidhinnConstIterator<element_type,
1443
1448 using const_iterator_sorted = const_iterator_pair_first;
1449
1457 using const_iterator_idempotents = const_iterator_pair_first;
1458
1478 [[nodiscard]] const_iterator cbegin() const;
1479
1499 [[nodiscard]] const_iterator begin() const;
1500
1520 [[nodiscard]] const_iterator cend() const;
1521
1541 [[nodiscard]] const_iterator end() const;
1542
1556 [[nodiscard]] const_iterator_sorted cbegin_sorted();
1557
1570 [[nodiscard]] const_iterator_sorted cend_sorted();
1571
1585
1598
1599 private:
1600 void run_impl() override;
1601
1602 void report_progress();
1603
1604 bool finished_impl() const override;
1605 };
1606
1611 template <typename Iterator1, typename Iterator2>
1612 FroidurePin(Iterator1, Iterator2)
1614
1615 // Namespace doc is in froidure-pin-base.hpp
1616 namespace froidure_pin {
1617
1632 // NOTE: this isn't called make because it is not constructing anything,
1633 // rather re-initializing.
1634 template <typename Container>
1637 Container const& gens) {
1638 return fp.init(std::begin(gens), std::end(gens));
1639 }
1640
1641 // TODO(1) make the following work
1642 // template <typename Container>
1643 // FroidurePin<typename Container::value_type>&
1644 // init(FroidurePin<typename Container::value_type>& fp, Container&& gens) {
1645 // return fp.init(std::make_move_iterator(std::begin(gens)),
1646 // std::make_move_iterator(std::end(gens)));
1647 // }
1648
1649 // clang-format off
1650 // NOLINTNEXTLINE(whitespace/line_length)
1652 // clang-format on
1653 template <typename Element>
1654 [[nodiscard]] FroidurePin<Element>
1656 return fp.init(std::begin(gens), std::end(gens));
1657 }
1658
1670 template <typename Container>
1672 Container const& coll) {
1673 fp.add_generators(std::begin(coll), std::end(coll));
1674 }
1675
1688 template <typename Container>
1689 void
1694
1695 // TODO(1) make the following work
1696 // template <typename Container>
1697 // FroidurePin<typename Container::value_type>&
1698 // add_generators(FroidurePin<typename Container::value_type>& fp,
1699 // Container&& coll) {
1700 // // Note that this currently doesn't do anything different than the
1701 // // function above.
1702 // return fp.add_generators(std::make_move_iterator(std::begin(coll)),
1703 // std::make_move_iterator(std::end(coll)));
1704 // }
1705
1717 template <typename Element>
1722
1735 template <typename Element>
1740
1756 template <typename Container>
1759 Container const& coll) {
1760 return fp.copy_add_generators(std::begin(coll), std::end(coll));
1761 }
1762
1779 template <typename Container>
1783 Container const& coll) {
1784 return fp.copy_add_generators_no_checks(std::begin(coll), std::end(coll));
1785 }
1786
1802 template <typename Element>
1803 [[nodiscard]] FroidurePin<Element>
1808
1824 template <typename Element>
1825 [[nodiscard]] FroidurePin<Element>
1830
1842 template <typename Container>
1844 Container const& coll) {
1845 fp.closure(std::begin(coll), std::end(coll));
1846 }
1847
1859 template <typename Container>
1861 Container const& coll) {
1862 fp.closure_no_checks(std::begin(coll), std::end(coll));
1863 }
1864
1876 template <typename Element>
1879 fp.closure(std::begin(coll), std::end(coll));
1880 }
1881
1893 template <typename Element>
1898
1913 template <typename Container>
1916 Container const& coll) {
1917 return fp.copy_closure(std::begin(coll), std::end(coll));
1918 }
1919
1934 template <typename Container>
1937 Container const& coll) {
1938 return fp.copy_closure_no_checks(std::begin(coll), std::end(coll));
1939 }
1940
1956 template <typename Element>
1957 [[nodiscard]] FroidurePin<Element>
1962
1978 template <typename Element>
1979 [[nodiscard]] FroidurePin<Element>
1984
1985 // TODO(1) implement the next function
1986 // \brief Returns a range object containing the so-far enumerated
1987 // idempotents.
1988 //
1989 // This function returns a range object containing the so-far enumerated
1990 // idempotents. No enumeration of \p fp is triggered by calls to this
1991 // function.
1992 //
1993 // See TODO(1) for more details about range objects.
1994 //
1995 // \tparam Element the type of the elements in the represented
1996 // semigroup.
1997 //
1998 // \tparam Traits a traits class holding various adapters used by the
1999 // implementation (defaults to FroidurePinTraits).
2000 //
2001 // \param fp the FroidurePin instance.
2002 //
2003 // \returns A range object.
2004 //
2005 // is_idempotent_no_checks current performs a full enum. so this doesn't
2006 // work.
2007 //
2008 // template <typename Element, typename Traits>
2009 // [[nodiscard]] auto
2010 // current_idempotents(FroidurePin<Element, Traits> const& fp) {
2011 // return rx::iterator_range(fp.cbegin(), fp.cend())
2012 // | rx::filter([&fp](auto const& x) {
2013 // return fp.is_idempotent_no_checks(fp.current_position(x));
2014 // });
2015 // }
2016
2036 template <typename Element, typename Traits>
2038 fp.run();
2039 return rx::iterator_range(fp.cbegin_idempotents(), fp.cend_idempotents());
2040 }
2041
2061 template <typename Element, typename Traits>
2063 return rx::iterator_range(fp.cbegin_sorted(), fp.cend_sorted());
2064 }
2065
2066 // TODO(1) current_sorted_elements
2067
2088 template <typename Element, typename Traits>
2089 [[nodiscard]] auto
2091 return rx::iterator_range(fp.cbegin(), fp.cend());
2092 }
2093
2112 template <typename Element, typename Traits>
2113 [[nodiscard]] auto elements(FroidurePin<Element, Traits>& fp) {
2114 fp.run();
2115 return current_elements(fp);
2116 }
2117
2145 template <typename Element, typename Traits, typename Word>
2148 Word const& w) {
2149 return fp.to_element_no_checks(std::begin(w), std::end(w));
2150 }
2151
2152 // clang-format off
2153 // NOLINTNEXTLINE(whitespace/line_length)
2155 // clang-format on
2156 template <typename Element, typename Traits, typename T = size_t>
2163
2190 template <typename Element, typename Traits, typename Word>
2192 to_element(FroidurePin<Element, Traits> const& fp, Word const& w) {
2193 return fp.to_element(std::begin(w), std::end(w));
2194 }
2195
2196 // clang-format off
2197 // NOLINTNEXTLINE(whitespace/line_length)
2199 // clang-format on
2200 template <typename Element, typename Traits, typename T = size_t>
2206
2228 template <typename Element, typename Traits, typename Word>
2229 [[nodiscard]] bool
2231 Word const& x,
2232 Word const& y) {
2233 return fp.equal_to_no_checks(
2234 std::begin(x), std::end(x), std::begin(y), std::end(y));
2235 }
2236
2257 template <typename Element, typename Traits, typename Word>
2258 [[nodiscard]] bool equal_to(FroidurePin<Element, Traits> const& fp,
2259 Word const& x,
2260 Word const& y) {
2261 return fp.equal_to(
2262 std::begin(x), std::end(x), std::begin(y), std::end(y));
2263 }
2264
2286 template <typename Element, typename Traits, typename Word = word_type>
2287 [[nodiscard]] Word minimal_factorisation(
2290
2310 template <typename Element, typename Traits, typename Word>
2313 Word& w,
2315
2338 template <typename Element, typename Traits, typename Word = word_type>
2339 [[nodiscard]] Word
2342
2365 template <typename Element, typename Traits, typename Word>
2366 void
2368 Word& w,
2370
2371 } // namespace froidure_pin
2372
2383
2396 // TODO this only works if FroidurePin is stateless.
2397 template <template <typename...> typename Thing,
2398 typename Container,
2399 typename Element = typename Container::value_type>
2400 [[nodiscard]] auto make(Container const& gens)
2401 -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
2404 std::end(gens));
2405 return FroidurePin(std::begin(gens), std::end(gens));
2406 }
2407
2408 // TODO(1) make the following work
2409 // template <typename Container>
2410 // FroidurePin<typename Container::value_type>
2411 // make(Container&& gens) {
2412 // return FroidurePin(std::make_move_iterator(std::begin(gens)),
2413 // std::make_move_iterator(std::end(gens)));
2414 // }
2415
2435 template <template <typename...> typename Thing, typename Element>
2437 -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
2440 std::end(gens));
2441 return FroidurePin(std::begin(gens), std::end(gens));
2442 }
2443
2465 template <template <typename...> typename Thing,
2466 typename Iterator1,
2467 typename Iterator2,
2468 typename Element
2469 = std::decay_t<decltype(*std::declval<Iterator1>())>>
2470 [[nodiscard]] auto make(Iterator1 first, Iterator2 last)
2471 -> std::enable_if_t<std::is_same_v<Thing<Element>, FroidurePin<Element>>,
2473 static_assert(
2474 std::is_same_v<std::decay_t<decltype(*std::declval<Iterator2>())>,
2475 Element>);
2477 return FroidurePin(first, last);
2478 }
2479
2498 template <typename Element, typename Traits>
2499 [[nodiscard]] std::string
2501
2502} // namespace libsemigroups
2503
2504#include "froidure-pin.tpp"
2505
2506#endif // LIBSEMIGROUPS_FROIDURE_PIN_HPP_
T begin(T... args)
element_index_type current_position(Iterator1 first, Iterator2 last) const
Returns the position corresponding to a word.
Definition froidure-pin-base.hpp:310
FroidurePinBase()
Default constructor.
void minimal_factorisation(Iterator d_first, element_index_type pos)
Output to an iterator the short-lex least word representing an element given by index.
Definition froidure-pin-base.hpp:1086
void throw_if_element_index_out_of_range(element_index_type i) const
Throw an exception if an index is out of range.
size_type element_index_type
Alias for the index of an element.
Definition froidure-pin-base.hpp:87
void factorisation(Iterator d_first, element_index_type pos)
Output to an iterator a word representing an element given by index.
Definition froidure-pin-base.hpp:1155
void throw_if_any_generator_index_out_of_range(Iterator1 first, Iterator2 last) const
Throw an exception if any generator index is out of range.
Definition froidure-pin-base.hpp:1805
size_type generator_index_type
Alias for the index of a generator.
Definition froidure-pin-base.hpp:81
WordGraph< element_index_type > cayley_graph_type
Alias for the types of the left and right Cayley graphs.
Definition froidure-pin-base.hpp:90
uint32_t size_type
Alias for the type of the size of the enumerated semigroup.
Definition froidure-pin-base.hpp:75
Class implementing the Froidure-Pin algorithm.
Definition froidure-pin.hpp:188
typename detail::BruidhinnTraits< Element >::const_pointer const_pointer
Type of element const pointers.
Definition froidure-pin.hpp:270
const_reference generator_no_checks(generator_index_type i) const
Returns the generator with specified index.
const_reference at(element_index_type i)
Access element specified by index with bound checks.
typename detail::BruidhinnTraits< Element >::reference reference
Type of element references.
Definition froidure-pin.hpp:267
typename Traits::EqualTo EqualTo
Adapter for testing equality.
Definition froidure-pin.hpp:292
bool contains(const_reference x)
Test membership of an element.
const_iterator begin() const
Returns a const iterator pointing to the first element (ordered by discovery).
bool is_idempotent(element_index_type i)
Check if an element is an idempotent via its index.
Definition froidure-pin.hpp:833
const_reference sorted_at(element_index_type i)
Access element specified by sorted index with bound checks.
const_iterator cbegin() const
Returns a const iterator pointing to the first element (ordered by discovery).
FroidurePin & operator=(FroidurePin const &)
Copy assignment operator.
const_reference to_element_no_checks(Iterator1 first, Iterator2 last) const
Convert a word in the generators to an element.
tril is_finite() const override
Check finiteness.
Definition froidure-pin.hpp:1020
FroidurePin copy_closure_no_checks(Iterator1 first, Iterator2 last)
Copy and add non-redundant generators.
const_iterator_sorted cbegin_sorted()
Returns a const iterator pointing to the first element (sorted by Less).
typename Traits::One One
Adapter for the identity element of the given type.
Definition froidure-pin.hpp:304
FroidurePin & closure(Iterator1 first, Iterator2 last)
Add non-redundant generators in collection.
Definition froidure-pin.hpp:1263
typename detail::BruidhinnTraits< Element >::const_reference const_reference
Type of element const references.
Definition froidure-pin.hpp:259
FroidurePinBase::element_index_type element_index_type
Alias for the index of an element.
Definition froidure-pin.hpp:277
element_index_type fast_product_no_checks(element_index_type i, element_index_type j) const
Multiply elements via their indices.
bool is_idempotent_no_checks(element_index_type i)
Check if an element is an idempotent via its index.
typename Traits::Degree Degree
Adapter for the degree of an element.
Definition froidure-pin.hpp:289
typename Traits::Less Less
Adapter for comparisons.
Definition froidure-pin.hpp:301
typename detail::BruidhinnTraits< Element >::value_type element_type
Type of the elements.
Definition froidure-pin.hpp:247
FroidurePinBase::cayley_graph_type cayley_graph_type
Alias for the types of the left and right Cayley graphs.
Definition froidure-pin.hpp:280
FroidurePin copy_add_generators_no_checks(Iterator1 first, Iterator2 last) const
Copy and add a collection of generators.
element_index_type fast_product(element_index_type i, element_index_type j) const
Multiply elements via their indices.
Definition froidure-pin.hpp:778
typename Traits::Hash Hash
Adapter for hashing.
Definition froidure-pin.hpp:295
FroidurePin & closure_no_checks(Iterator1 first, Iterator2 last)
Add non-redundant generators in collection.
size_t number_of_idempotents()
Returns the number of idempotents.
element_index_type sorted_position(const_reference x)
Returns the sorted index of an element.
std::shared_ptr< state_type > state() const
Returns a std::shared_ptr to the state (if any).
Definition froidure-pin.hpp:1344
const_reference operator[](element_index_type i) const
Access element specified by index.
typename Traits::state_type state_type
Type of the state used for multiplication (if any).
Definition froidure-pin.hpp:283
FroidurePin & init()
Reinitialize a FroidurePin object.
FroidurePin(Iterator1, Iterator2) -> FroidurePin< std::decay_t< decltype(*std::declval< Iterator1 >())> >
size_t number_of_generators() const noexcept override
Returns the number of generators.
FroidurePinBase::size_type size_type
Alias for the type of the size of the enumerated semigroup.
Definition froidure-pin.hpp:274
const_iterator_pair_first const_iterator_idempotents
Return type of cbegin_idempotents and cend_idempotents.
Definition froidure-pin.hpp:1454
typename detail::BruidhinnTraits< Element >::rvalue_reference rvalue_reference
Type of element rvalue references.
Definition froidure-pin.hpp:263
const_iterator cend() const
Returns a const iterator pointing to one past the last known element.
bool equal_to_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check equality of words in the generators.
typename Traits::Swap Swap
Adapter for swapping.
Definition froidure-pin.hpp:310
const_iterator_idempotents cend_idempotents()
Returns a const iterator pointing one past the last idempotent.
static void throw_if_inconsistent_degree(Iterator1 first, Iterator2 last)
Throws if the degrees of the elements in a given range are not all equal.
typename Traits::Complexity Complexity
Adapter for the complexity of multiplication.
Definition froidure-pin.hpp:286
FroidurePin copy_add_generators(Iterator1 first, Iterator2 last) const
Copy and add a collection of generators.
Definition froidure-pin.hpp:1197
typename Traits::Product Product
Adapter for the product of two elements.
Definition froidure-pin.hpp:307
const_reference generator(generator_index_type i) const
Returns the generator with specified index.
element_type value_type
Alias for element_type.
Definition froidure-pin.hpp:252
FroidurePin copy_closure(Iterator1 first, Iterator2 last)
Copy and add non-redundant generators.
Definition froidure-pin.hpp:1328
element_index_type to_sorted_position(element_index_type i)
Returns the sorted index of an element via its index.
typename detail::BruidhinnTraits< Element >::const_value_type const_element_type
Type of const elements.
Definition froidure-pin.hpp:255
element_index_type current_position(const_reference x) const
Find the position of an element with no enumeration.
FroidurePin & add_generator_no_checks(const_reference x)
Add a copy of an element to the generators.
const_reference to_element(Iterator1 first, Iterator2 last) const
Convert a word in the generators to an element.
const_iterator end() const
Returns a const iterator pointing one past the last known element.
bool equal_to(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check equality of words in the generators.
Definition froidure-pin.hpp:634
std::string to_human_readable_repr(FroidurePin< Element, Traits > const &fp)
Return a human readable representation of a FroidurePin object.
FroidurePin & add_generator(const_reference x)
Add a copy of an element to the generators.
FroidurePin & add_generators(Iterator1 first, Iterator2 last)
Add collection of generators via iterators.
const_iterator_idempotents cbegin_idempotents()
Returns a const iterator pointing at the first idempotent.
detail::BruidhinnConstIterator< element_type, std::vector< internal_element_type > > const_iterator
Return type of cbegin and cend.
Definition froidure-pin.hpp:1438
const_reference sorted_at_no_checks(element_index_type i)
Access element specified by sorted index with bound checks.
typename Traits::IncreaseDegree IncreaseDegree
Adapter for increasing the degree of an element.
Definition froidure-pin.hpp:298
element_index_type position(const_reference x)
Find the position of an element with enumeration if necessary.
const_iterator_sorted cend_sorted()
Returns a const iterator pointing one past the last element (sorted by Less).
FroidurePin & add_generators_no_checks(Iterator1 first, Iterator2 last)
Add collection of generators via iterators.
FroidurePin & reserve(size_t val)
Requests the given capacity for elements.
const_iterator_pair_first const_iterator_sorted
Return type of cbegin_sorted and cend_sorted.
Definition froidure-pin.hpp:1445
FroidurePin()
Default constructor.
void run()
Run until finished.
T declval(T... args)
T end(T... args)
enable_if_is_same< Return, Blocks > make(Container const &cont)
Check the arguments, construct a Blocks object, and check it.
Definition bipart.hpp:798
tril
Enum to indicate true, false or not currently knowable.
Definition types.hpp:54
@ TRUE
Value representing true.
Definition types.hpp:58
T make_shared(T... args)
This namespace contains helper functions for the FroidurePin class template.
Definition froidure-pin-base.hpp:1843
FroidurePin< typename Container::value_type > copy_closure(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Copy and add non-redundant generators from a container.
Definition froidure-pin.hpp:1915
auto elements(FroidurePin< Element, Traits > &fp)
Returns a range object containing all of the elements.
Definition froidure-pin.hpp:2113
bool equal_to(FroidurePin< Element, Traits > const &fp, Word const &x, Word const &y)
Check equality of words in the generators.
Definition froidure-pin.hpp:2258
FroidurePin< typename Container::value_type > copy_add_generators(FroidurePin< typename Container::value_type > const &fp, Container const &coll)
Copy a FroidurePin instance and add a collection of generators from a container.
Definition froidure-pin.hpp:1758
FroidurePin< Element, Traits >::const_reference to_element(FroidurePin< Element, Traits > const &fp, Word const &w)
Convert a word in the generators to an element.
Definition froidure-pin.hpp:2192
void add_generators_no_checks(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Add collection of generators from container.
Definition froidure-pin.hpp:1690
bool equal_to_no_checks(FroidurePin< Element, Traits > const &fp, Word const &x, Word const &y)
Check equality of words in the generators.
Definition froidure-pin.hpp:2230
void closure_no_checks(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Add non-redundant generators from a container.
Definition froidure-pin.hpp:1860
FroidurePin< typename Container::value_type > & init(FroidurePin< typename Container::value_type > &fp, Container const &gens)
Re-initialize a FroidurePin object from a container of generators.
Definition froidure-pin.hpp:1636
FroidurePin< Element, Traits >::const_reference to_element_no_checks(FroidurePin< Element, Traits > const &fp, Word const &w)
Convert a word in the generators to an element.
Definition froidure-pin.hpp:2147
void add_generators(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Add collection of generators from container.
Definition froidure-pin.hpp:1671
void factorisation(FroidurePinBase &fpb, Word &word, FroidurePinBase::element_index_type pos)
Modify a word to contain a word representing an element given by index.
Definition froidure-pin-base.hpp:2304
auto current_elements(FroidurePin< Element, Traits > const &fp)
Returns a range object containing the so-far enumerated elements.
Definition froidure-pin.hpp:2090
FroidurePin< typename Container::value_type > copy_add_generators_no_checks(FroidurePin< typename Container::value_type > const &fp, Container const &coll)
Copy a FroidurePin instance and add a collection of generators from a container.
Definition froidure-pin.hpp:1781
void minimal_factorisation(FroidurePinBase &fpb, Word &word, FroidurePinBase::element_index_type pos)
Modify a word to contain the short-lex least word representing an element given by index.
Definition froidure-pin-base.hpp:2204
auto idempotents(FroidurePin< Element, Traits > &fp)
Returns a range object containing all of the idempotents.
Definition froidure-pin.hpp:2037
void closure(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Add non-redundant generators from a container.
Definition froidure-pin.hpp:1843
auto sorted_elements(FroidurePin< Element, Traits > &fp)
Returns a range object containing all of the elements.
Definition froidure-pin.hpp:2062
FroidurePin< typename Container::value_type > copy_closure_no_checks(FroidurePin< typename Container::value_type > &fp, Container const &coll)
Copy and add non-redundant generators from a container.
Definition froidure-pin.hpp:1936
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
Adapter for the complexity of multiplication.
Definition adapters.hpp:121
Adapter for the degree of an element.
Definition adapters.hpp:159
Adapter for testing equality.
Definition adapters.hpp:413
Traits class for FroidurePin.
Definition froidure-pin.hpp:68
::libsemigroups::Degree< element_type > Degree
Adapter for the degree of an element.
Definition froidure-pin.hpp:87
::libsemigroups::Product< element_type > Product
Adapter for the product of two elements.
Definition froidure-pin.hpp:105
::libsemigroups::Complexity< element_type > Complexity
Adapter for the complexity of multiplication.
Definition froidure-pin.hpp:84
typename detail::BruidhinnTraits< Element >::value_type element_type
The type of the elements of a FroidurePin instance.
Definition froidure-pin.hpp:75
::libsemigroups::Hash< element_type > Hash
Adapter for hashing.
Definition froidure-pin.hpp:93
::libsemigroups::IncreaseDegree< element_type > IncreaseDegree
Adapter for increasing the degree of an element.
Definition froidure-pin.hpp:96
::libsemigroups::Less< element_type > Less
Adapter for comparisons.
Definition froidure-pin.hpp:99
::libsemigroups::Swap< element_type > Swap
Adapter for swapping.
Definition froidure-pin.hpp:108
::libsemigroups::EqualTo< element_type > EqualTo
Adapter for testing equality.
Definition froidure-pin.hpp:90
::libsemigroups::One< element_type > One
Adapter for the identity element of the given type.
Definition froidure-pin.hpp:102
State state_type
The type of the state (if any).
Definition froidure-pin.hpp:81
Adapter for hashing.
Definition adapters.hpp:446
Adapter for increasing the degree of an element.
Definition adapters.hpp:199
Adapter for comparisons.
Definition adapters.hpp:634
Adapter for the identity element of the given type.
Definition adapters.hpp:246
Adapter for the product of two elements.
Definition adapters.hpp:284
Adapter for swapping.
Definition adapters.hpp:666