libsemigroups  v3.1.2
C++ library for semigroups and monoids
Loading...
Searching...
No Matches
cong-class.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 Congruence class template, for
20// creating congruence over FroidurePin objects or over Presentation objects.
21
22#ifndef LIBSEMIGROUPS_CONG_CLASS_HPP_
23#define LIBSEMIGROUPS_CONG_CLASS_HPP_
24
25#include <cstddef> // for size_t
26#include <cstdint> // for uint64_t
27#include <memory> // for shared_ptr
28#include <string> // for string
29#include <string_view> // for string_view
30#include <utility> // for move
31#include <vector> // for vector
32
33#include "knuth-bendix-class.hpp" // for KnuthBendix
34#include "presentation.hpp" // for Presentation
35#include "todd-coxeter-class.hpp" // for ToddCoxeter
36#include "types.hpp" // for letter_type, wor...
37
38#include "detail/cong-common-class.hpp" // for detail::CongruenceCommon
39#include "detail/race.hpp" // for Race
40
41namespace libsemigroups {
42 class FroidurePinBase; // Forward declaration, constructor parameters
43
44 template <typename Node>
45 class WordGraph;
46
47 namespace detail {
48 struct CongruenceBase {};
49 } // namespace detail
50
61
70
86
96
107
121
156 template <typename Word>
157 class Congruence : public detail::CongruenceCommon,
158 public detail::CongruenceBase {
159 enum class RunnerKind : size_t { TC = 0, KB = 1, K = 2 };
160
162 // Congruence - data - private
164
165 mutable detail::Race _race;
166 mutable bool _runners_initted;
167 std::vector<RunnerKind> _runner_kinds;
168
169 public:
171 // Interface requirements - native-types
173
181 using native_word_type = Word;
182
184 // Congruence - constructors - public
186
194
207
214
221
228
235
236 ~Congruence();
237
250 // NOTE: No rvalue ref version because we anyway must copy p multiple times
252 : Congruence() {
253 init(knd, p);
254 }
255
270 // NOTE: No rvalue ref version because we anyway must copy p multiple times
272
274 // Congruence - interface requirements - add_generating_pair
276
293 template <typename Iterator1,
294 typename Iterator2,
295 typename Iterator3,
296 typename Iterator4>
298 Iterator2 last1,
299 Iterator3 first2,
300 Iterator4 last2) {
301 _runners_initted = false;
302 return detail::CongruenceCommon::add_internal_generating_pair_no_checks<
303 Congruence>(first1, last1, first2, last2);
304 }
305
320 template <typename Iterator1,
321 typename Iterator2,
322 typename Iterator3,
323 typename Iterator4>
325 Iterator2 last1,
326 Iterator3 first2,
327 Iterator4 last2) {
328 _runners_initted = false;
329 return detail::CongruenceCommon::add_generating_pair<Congruence>(
330 first1, last1, first2, last2);
331 }
332
334 // Congruence - interface requirements - number_of_classes
336
351 [[nodiscard]] uint64_t number_of_classes();
352
354 // Congruence - interface requirements - contains
356
375 template <typename Iterator1,
376 typename Iterator2,
377 typename Iterator3,
378 typename Iterator4>
379 [[nodiscard]] tril currently_contains_no_checks(Iterator1 first1,
380 Iterator2 last1,
381 Iterator3 first2,
382 Iterator4 last2) const;
383
402 template <typename Iterator1,
403 typename Iterator2,
404 typename Iterator3,
405 typename Iterator4>
406 [[nodiscard]] tril currently_contains(Iterator1 first1,
407 Iterator2 last1,
408 Iterator3 first2,
409 Iterator4 last2) const {
410 return detail::CongruenceCommon::currently_contains<Congruence>(
411 first1, last1, first2, last2);
412 }
413
435 template <typename Iterator1,
436 typename Iterator2,
437 typename Iterator3,
438 typename Iterator4>
439 [[nodiscard]] bool contains_no_checks(Iterator1 first1,
440 Iterator2 last1,
441 Iterator3 first2,
442 Iterator4 last2) {
443 return detail::CongruenceCommon::contains_no_checks<Congruence>(
444 first1, last1, first2, last2);
445 }
446
464 template <typename Iterator1,
465 typename Iterator2,
466 typename Iterator3,
467 typename Iterator4>
468 [[nodiscard]] bool contains(Iterator1 first1,
469 Iterator2 last1,
470 Iterator3 first2,
471 Iterator4 last2) {
472 return detail::CongruenceCommon::contains<Congruence>(
473 first1, last1, first2, last2);
474 }
475
477 // Congruence - interface requirements - reduce
479
497 template <typename OutputIterator, typename Iterator1, typename Iterator2>
498 OutputIterator reduce_no_run_no_checks(OutputIterator d_first,
499 Iterator1 first,
500 Iterator2 last) const;
501
519 template <typename OutputIterator, typename Iterator1, typename Iterator2>
520 OutputIterator reduce_no_run(OutputIterator d_first,
521 Iterator1 first,
522 Iterator2 last) const {
523 return detail::CongruenceCommon::reduce_no_run<Congruence>(
524 d_first, first, last);
525 }
526
542 template <typename OutputIterator,
543 typename InputIterator1,
544 typename InputIterator2>
545 OutputIterator reduce_no_checks(OutputIterator d_first,
546 InputIterator1 first,
547 InputIterator2 last) {
548 return detail::CongruenceCommon::reduce_no_checks<Congruence>(
549 d_first, first, last);
550 }
551
567 template <typename OutputIterator,
568 typename InputIterator1,
569 typename InputIterator2>
570 OutputIterator reduce(OutputIterator d_first,
571 InputIterator1 first,
572 InputIterator2 last) {
573 return detail::CongruenceCommon::reduce<Congruence>(d_first, first, last);
574 }
575
577 // Congruence - interface requirements - throw_if_letter_not_in_alphabet
579
597 template <typename Iterator1, typename Iterator2>
598 void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const;
599
601 // Congruence - member functions - public
603
622 template <typename Thing>
624
644 template <typename Thing>
645 [[nodiscard]] bool has() const;
646
662 [[nodiscard]] size_t max_threads() const noexcept {
663 return _race.max_threads();
664 }
665
682 Congruence& max_threads(size_t val) noexcept {
683 _race.max_threads(val);
684 return *this;
685 }
686
698 [[nodiscard]] size_t number_of_runners() const noexcept {
699 return _race.number_of_runners();
700 }
701
714 [[nodiscard]] Presentation<Word> const& presentation() const;
715
727 [[nodiscard]] std::vector<Word> const& generating_pairs() const;
728
729#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
744 [[nodiscard]] congruence_kind kind() const noexcept;
745
761 [[nodiscard]] size_t number_of_generating_pairs() const noexcept;
762#endif
763
764 private:
766 // Congruence - member functions - private
768
769 void add_runner(std::shared_ptr<ToddCoxeter<Word>>&& ptr) {
770 _race.add_runner(std::move(ptr));
771 _runner_kinds.push_back(RunnerKind::TC);
772 }
773
774 void add_runner(std::shared_ptr<KnuthBendix<Word>>&& ptr) {
775 _race.add_runner(std::move(ptr));
776 _runner_kinds.push_back(RunnerKind::KB);
777 }
778
779 void add_runner(std::shared_ptr<Kambites<Word>>&& ptr) {
780 _race.add_runner(std::move(ptr));
781 _runner_kinds.push_back(RunnerKind::K);
782 }
783
784 template <typename Result, typename Node>
785 friend auto to(congruence_kind knd,
786 FroidurePinBase& fpb,
787 WordGraph<Node> const& wg)
788 -> std::enable_if_t<
789 std::is_same_v<Congruence<typename Result::native_word_type>,
790 Result>,
791 Result>;
792
793 void init_runners() const;
794
796 // Runner - pure virtual member functions - private
798
799 void run_impl() override;
800 bool finished_impl() const override {
801 return _race.finished();
802 }
803 }; // class Congruence
804
813 template <typename Word>
814 Congruence(congruence_kind, Presentation<Word> const&) -> Congruence<Word>;
815
824 // NOTE:there's no rvalue ref constructor, so it's possible this guide is
825 // superfluous
826 template <typename Word>
828
837 template <typename Word>
838 Congruence(Congruence<Word> const&) -> Congruence<Word>;
839
848 template <typename Word>
849 Congruence(Congruence<Word>&&) -> Congruence<Word>;
850
866 template <typename Word>
867 std::string to_human_readable_repr(Congruence<Word> const& c);
868} // namespace libsemigroups
869
870#include "cong-class.tpp"
871
872#endif // LIBSEMIGROUPS_CONG_CLASS_HPP_
Base class for FroidurePin containing non-element specific data and member functions.
Definition froidure-pin-base.hpp:66
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:102
Class for representing word graphs.
Definition word-graph.hpp:82
std::string to_human_readable_repr(AhoCorasick const &ac)
Return a string representation.
std::shared_ptr< Thing > get() const
Get a derived class of detail::CongruenceCommon being used to compute a Congruence instance.
bool has() const
Check if a derived class of detail::CongruenceCommon being used to compute a Congruence instance.
Congruence(congruence_kind, Presentation< Word > const &) -> Congruence< Word >
Deduction guide.
Congruence(Congruence const &)
Copy constructor.
Congruence(Congruence &&)
Move constructor.
Congruence()
Default constructor.
Congruence & init()
Re-initialize a Congruence instance.
Congruence & operator=(Congruence &&)
Move assignment operator.
Congruence(congruence_kind knd, Presentation< Word > const &p)
Construct from congruence_kind and Presentation.
Definition cong-class.hpp:251
void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const
Throws if any letter in a range is out of bounds.
Congruence & operator=(Congruence const &)
Copy assignment operator.
Congruence & init(congruence_kind knd, Presentation< Word > const &p)
Re-initialize a Congruence instance.
OutputIterator reduce_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word with no checks.
Definition cong-class.hpp:545
uint64_t number_of_classes()
Compute the number of classes in the congruence.
bool contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
Definition cong-class.hpp:439
OutputIterator reduce_no_run_no_checks(OutputIterator d_first, Iterator1 first, Iterator2 last) const
Reduce a word with no computation or checks.
tril currently_contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Definition cong-class.hpp:406
Congruence & add_generating_pair(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
Definition cong-class.hpp:324
OutputIterator reduce(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word.
Definition cong-class.hpp:570
size_t number_of_generating_pairs() const noexcept
Returns the number of generating pairs.
tril currently_contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Congruence & add_generating_pair_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
Definition cong-class.hpp:297
bool contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
Definition cong-class.hpp:468
std::vector< Word > const & generating_pairs() const
Get the generating pairs of the congruence.
congruence_kind kind() const noexcept
The kind of the congruence (1- or 2-sided).
OutputIterator reduce_no_run(OutputIterator d_first, Iterator1 first, Iterator2 last) const
Reduce a word with no computation.
Definition cong-class.hpp:520
Presentation< Word > const & presentation() const
Get the presentation defining the parent semigroup of the congruence.
Word native_word_type
Type of the words in the relations of the presentation stored in a Congruence instance.
Definition cong-class.hpp:181
Congruence & max_threads(size_t val) noexcept
Set the maximum number of threads.
Definition cong-class.hpp:682
size_t max_threads() const noexcept
Get the current maximum number of threads.
Definition cong-class.hpp:662
size_t number_of_runners() const noexcept
Get the number of runners.
Definition cong-class.hpp:698
tril
Enum to indicate true, false or not currently knowable.
Definition types.hpp:54
congruence_kind
Enum to indicate the sided-ness of a congruence.
Definition types.hpp:67
T move(T... args)
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
T push_back(T... args)