26#ifndef LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
27#define LIBSEMIGROUPS_TODD_COXETER_CLASS_HPP_
37#include "presentation.hpp"
38#include "to-presentation.hpp"
41#include "detail/citow.hpp"
42#include "detail/cong-common-class.hpp"
43#include "detail/fmt.hpp"
44#include "detail/todd-coxeter-impl.hpp"
138 template <
typename Word>
139 class ToddCoxeter :
public detail::ToddCoxeterImpl {
141 std::vector<Word> _generating_pairs;
145#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
153 struct options :
public FelschGraphSettings_::options {
373 using node_type =
typename detail::ToddCoxeterImpl::node_type;
398 using index_type =
typename detail::ToddCoxeterImpl::index_type;
406 using label_type =
typename detail::ToddCoxeterImpl::label_type;
530 ToddCoxeterImpl::init(knd, tc);
531 _presentation = tc.presentation();
532 _presentation.rules.insert(_presentation.rules.end(),
533 tc.generating_pairs().cbegin(),
534 tc.generating_pairs().cend());
536 _generating_pairs.clear();
559 template <
typename Node>
581 template <
typename Node>
584#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
588 template <
typename Node>
596 template <
typename Node>
620 template <
typename Iterator1,
typename Iterator2>
622 Iterator2 last)
const {
623 presentation().throw_if_letter_not_in_alphabet(first, last);
640 return _generating_pairs;
660 return _presentation;
684 template <
typename Iterator1,
707 template <
typename Iterator1,
717 return detail::CongruenceCommon::add_generating_pair<ToddCoxeter>(
718 first1, last1, first2, last2);
745 template <
typename Iterator1,
752 Iterator4 last2)
const {
753 return ToddCoxeterImpl::currently_contains_no_checks(
754 detail::citow(
this, first1),
755 detail::citow(
this, last1),
756 detail::citow(
this, first2),
757 detail::citow(
this, last2));
780 template <
typename Iterator1,
787 Iterator4 last2)
const {
790 return detail::CongruenceCommon::currently_contains<ToddCoxeter>(
791 first1, last1, first2, last2);
811 template <
typename Iterator1,
819 return ToddCoxeterImpl::contains_no_checks(detail::citow(
this, first1),
820 detail::citow(
this, last1),
821 detail::citow(
this, first2),
822 detail::citow(
this, last2));
842 template <
typename Iterator1,
876 template <
typename OutputIterator,
877 typename InputIterator1,
878 typename InputIterator2>
880 InputIterator1 first,
881 InputIterator2 last)
const {
882 return ToddCoxeterImpl::reduce_no_run_no_checks(
883 detail::itow(
this, d_first),
884 detail::citow(
this, first),
885 detail::citow(
this, last))
909 template <
typename OutputIterator,
910 typename InputIterator1,
911 typename InputIterator2>
913 InputIterator1 first,
914 InputIterator2 last)
const {
915 return detail::CongruenceCommon::reduce_no_run<ToddCoxeter>(
916 d_first, first, last);
942 template <
typename OutputIterator,
943 typename InputIterator1,
944 typename InputIterator2>
946 InputIterator1 first,
947 InputIterator2 last) {
948 return ToddCoxeterImpl::reduce_no_checks(detail::itow(
this, d_first),
949 detail::citow(
this, first),
950 detail::citow(
this, last))
977 template <
typename OutputIterator,
978 typename InputIterator1,
979 typename InputIterator2>
980 OutputIterator
reduce(OutputIterator d_first,
981 InputIterator1 first,
982 InputIterator2 last) {
985 return detail::CongruenceCommon::reduce<ToddCoxeter>(
986 d_first, first, last);
1034 template <
typename Iterator1,
typename Iterator2>
1036 Iterator2 last)
const {
1037 return ToddCoxeterImpl::current_index_of_no_checks(
1038 detail::citow(
this, first), detail::citow(
this, last));
1064 template <
typename Iterator1,
typename Iterator2>
1094 template <
typename Iterator1,
typename Iterator2>
1096 return ToddCoxeterImpl::index_of_no_checks(detail::citow(
this, first),
1097 detail::citow(
this, last));
1124 template <
typename Iterator1,
typename Iterator2>
1179 template <
typename OutputIterator>
1182 return ToddCoxeterImpl::current_word_of_no_checks(
1183 detail::itow(
this, d_first), i)
1209 template <
typename OutputIterator>
1211 return ToddCoxeterImpl::current_word_of(detail::itow(
this, d_first), i)
1237 template <
typename Iterator>
1239 return ToddCoxeterImpl::word_of_no_checks(detail::itow(
this, d_first), i)
1266 template <
typename Iterator>
1268 return ToddCoxeterImpl::word_of(detail::itow(
this, d_first), i).get();
1282 template <
typename Word>
1293 template <
typename Word>
1304 template <
typename Word>
1315 template <
typename Node>
1317 -> ToddCoxeter<word_type>;
1327 template <
typename Node>
1338 template <
typename Word>
1349 template <
typename Word>
1368 template <
typename Word>
1372#include "todd-coxeter-class.tpp"
For an implementation of presentations for semigroups or monoids.
Definition presentation.hpp:103
Class for representing word graphs.
Definition word-graph.hpp:83
std::string to_human_readable_repr(Action< Element, Point, Func, Traits, LeftOrRight > const &action)
Return a human readable representation of an Action object.
Presentation(Presentation< Word > const &) -> Presentation< Word >
Deduction guide.
ToddCoxeter(congruence_kind, Presentation< Word > const &) -> ToddCoxeter< Word >
Deduction guide.
OutputIterator current_word_of(OutputIterator d_first, index_type i) const
Insert a current word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1210
Iterator word_of_no_checks(Iterator d_first, index_type i)
Insert the word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1238
Iterator word_of(Iterator d_first, index_type i)
Insert the word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1267
OutputIterator current_word_of_no_checks(OutputIterator d_first, index_type i) const
Insert a current word representing a class with given index into an output iterator.
Definition todd-coxeter-class.hpp:1180
ToddCoxeter(congruence_kind knd, Presentation< Word > &&p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:461
ToddCoxeter & init(congruence_kind knd, Presentation< Word > &&p)
Re-initialize a ToddCoxeter instance.
ToddCoxeter & operator=(ToddCoxeter &&)=default
Move assignment operator.
ToddCoxeter()=default
Default constructor.
ToddCoxeter & init(congruence_kind knd, WordGraph< Node > const &wg)
Re-initialize a ToddCoxeter instance.
void throw_if_letter_not_in_alphabet(Iterator1 first, Iterator2 last) const
Throws if any letter in a range is out of bounds.
Definition todd-coxeter-class.hpp:621
ToddCoxeter & operator=(ToddCoxeter const &)=default
Copy assignment operator.
ToddCoxeter(ToddCoxeter const &)=default
ToddCoxeter(congruence_kind knd, WordGraph< Node > const &wg)
Construct from congruence_kind and WordGraph.
Definition todd-coxeter-class.hpp:560
ToddCoxeter(congruence_kind knd, Presentation< Word > const &p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:483
ToddCoxeter(ToddCoxeter &&)=default
ToddCoxeter & init(congruence_kind knd, Presentation< Word > const &p)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:489
ToddCoxeter & init()
Re-initialize a ToddCoxeter instance.
ToddCoxeter & init(congruence_kind knd, ToddCoxeter const &tc)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:529
ToddCoxeter(congruence_kind knd, ToddCoxeter const &tc)
Construct from congruence_kind and ToddCoxeter.
Definition todd-coxeter-class.hpp:509
OutputIterator reduce_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word with no checks.
Definition todd-coxeter-class.hpp:945
bool contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:815
tril currently_contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:784
OutputIterator reduce(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word.
Definition todd-coxeter-class.hpp:980
size_t number_of_generating_pairs() const noexcept
Returns the number of generating pairs.
ToddCoxeter & add_generating_pair(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
Definition todd-coxeter-class.hpp:711
std::vector< Word > const & generating_pairs() const noexcept
Get the generating pairs of the congruence.
Definition todd-coxeter-class.hpp:639
tril currently_contains_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2) const
Check containment of a pair of words via iterators.
Definition todd-coxeter-class.hpp:749
bool contains(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Check containment of a pair of words via iterators.
ToddCoxeter & add_generating_pair_no_checks(Iterator1 first1, Iterator2 last1, Iterator3 first2, Iterator4 last2)
Add generating pair via iterators.
congruence_kind kind() const noexcept
The kind of the congruence (1- or 2-sided).
Presentation< Word > const & presentation() const noexcept
Get the presentation used to define a ToddCoxeter instance (if any).
Definition todd-coxeter-class.hpp:659
OutputIterator reduce_no_run_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration or checks.
Definition todd-coxeter-class.hpp:879
OutputIterator reduce_no_run(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration.
Definition todd-coxeter-class.hpp:912
typename detail::ToddCoxeterImpl::word_graph_type word_graph_type
The type of the underlying WordGraph.
Definition todd-coxeter-class.hpp:381
typename detail::ToddCoxeterImpl::node_type node_type
The type of the nodes in the word graph.
Definition todd-coxeter-class.hpp:373
typename detail::ToddCoxeterImpl::index_type index_type
The type of the index of a class.
Definition todd-coxeter-class.hpp:398
typename detail::ToddCoxeterImpl::label_type label_type
The type of the edge-labels in the word graph.
Definition todd-coxeter-class.hpp:406
Word native_word_type
Type of the letters in the relations of the presentation stored in a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:365
index_type current_index_of(Iterator1 first, Iterator2 last) const
Returns the current index of the class containing a word.
Definition todd-coxeter-class.hpp:1065
index_type current_index_of_no_checks(Iterator1 first, Iterator2 last) const
Returns the current index of the class containing a word.
Definition todd-coxeter-class.hpp:1035
index_type index_of_no_checks(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1095
index_type index_of(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1125
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
Namespace for everything in the libsemigroups library.
Definition action.hpp:44
Struct containing various options that can be used to control the behaviour of Todd-Coxeter.
Definition todd-coxeter-class.hpp:153
lookahead_style
Enum class for specifying the style of any lookahead performed.
Definition todd-coxeter-class.hpp:239
lookahead_extent
Enum class for specifying the extent of any lookahead performed.
Definition todd-coxeter-class.hpp:222
@ partial
Definition todd-coxeter-class.hpp:230
@ full
Definition todd-coxeter-class.hpp:226
strategy
Enum class containing various strategies.
Definition todd-coxeter-class.hpp:164
@ CR
Definition todd-coxeter-class.hpp:183
@ Cr
Definition todd-coxeter-class.hpp:202
@ hlt
Definition todd-coxeter-class.hpp:168
@ felsch
Definition todd-coxeter-class.hpp:173
@ Rc
Definition todd-coxeter-class.hpp:213
@ R_over_C
Definition todd-coxeter-class.hpp:192
def_version
Values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:316
@ two
Version 2 definition processing.
Definition todd-coxeter-class.hpp:320
@ one
Version 1 definition processing.
Definition todd-coxeter-class.hpp:318
def_policy
Enum class containing values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:270
@ discard_all_if_no_space
Definition todd-coxeter-class.hpp:287
@ unlimited
Definition todd-coxeter-class.hpp:290
@ no_stack_if_no_space
Definition todd-coxeter-class.hpp:273
@ purge_from_top
Definition todd-coxeter-class.hpp:278
@ purge_all
Definition todd-coxeter-class.hpp:283