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"
135 template <
typename Word>
136 class ToddCoxeter :
public detail::ToddCoxeterImpl {
138 std::vector<Word> _generating_pairs;
142#ifdef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
150 struct options :
public FelschGraphSettings_::options {
370 using node_type =
typename detail::ToddCoxeterImpl::node_type;
395 using index_type =
typename detail::ToddCoxeterImpl::index_type;
403 using label_type =
typename detail::ToddCoxeterImpl::label_type;
527 ToddCoxeterImpl::init(knd, tc);
528 _presentation = tc.presentation();
529 _presentation.rules.insert(_presentation.rules.end(),
530 tc.generating_pairs().cbegin(),
531 tc.generating_pairs().cend());
533 _generating_pairs.clear();
556 template <
typename Node>
578 template <
typename Node>
581#ifndef LIBSEMIGROUPS_PARSED_BY_DOXYGEN
585 template <
typename Node>
593 template <
typename Node>
617 template <
typename Iterator1,
typename Iterator2>
619 Iterator2 last)
const {
620 presentation().throw_if_letter_not_in_alphabet(first, last);
637 return _generating_pairs;
657 return _presentation;
681 template <
typename Iterator1,
704 template <
typename Iterator1,
714 return detail::CongruenceCommon::add_generating_pair<ToddCoxeter>(
715 first1, last1, first2, last2);
742 template <
typename Iterator1,
749 Iterator4 last2)
const {
750 return ToddCoxeterImpl::currently_contains_no_checks(
751 detail::citow(
this, first1),
752 detail::citow(
this, last1),
753 detail::citow(
this, first2),
754 detail::citow(
this, last2));
777 template <
typename Iterator1,
784 Iterator4 last2)
const {
787 return detail::CongruenceCommon::currently_contains<ToddCoxeter>(
788 first1, last1, first2, last2);
808 template <
typename Iterator1,
816 return ToddCoxeterImpl::contains_no_checks(detail::citow(
this, first1),
817 detail::citow(
this, last1),
818 detail::citow(
this, first2),
819 detail::citow(
this, last2));
839 template <
typename Iterator1,
873 template <
typename OutputIterator,
874 typename InputIterator1,
875 typename InputIterator2>
877 InputIterator1 first,
878 InputIterator2 last)
const {
879 return ToddCoxeterImpl::reduce_no_run_no_checks(
880 detail::itow(
this, d_first),
881 detail::citow(
this, first),
882 detail::citow(
this, last))
906 template <
typename OutputIterator,
907 typename InputIterator1,
908 typename InputIterator2>
910 InputIterator1 first,
911 InputIterator2 last)
const {
912 return detail::CongruenceCommon::reduce_no_run<ToddCoxeter>(
913 d_first, first, last);
939 template <
typename OutputIterator,
940 typename InputIterator1,
941 typename InputIterator2>
943 InputIterator1 first,
944 InputIterator2 last) {
945 return ToddCoxeterImpl::reduce_no_checks(detail::itow(
this, d_first),
946 detail::citow(
this, first),
947 detail::citow(
this, last))
974 template <
typename OutputIterator,
975 typename InputIterator1,
976 typename InputIterator2>
977 OutputIterator
reduce(OutputIterator d_first,
978 InputIterator1 first,
979 InputIterator2 last) {
982 return detail::CongruenceCommon::reduce<ToddCoxeter>(
983 d_first, first, last);
1031 template <
typename Iterator1,
typename Iterator2>
1033 Iterator2 last)
const {
1034 return ToddCoxeterImpl::current_index_of_no_checks(
1035 detail::citow(
this, first), detail::citow(
this, last));
1061 template <
typename Iterator1,
typename Iterator2>
1091 template <
typename Iterator1,
typename Iterator2>
1093 return ToddCoxeterImpl::index_of_no_checks(detail::citow(
this, first),
1094 detail::citow(
this, last));
1121 template <
typename Iterator1,
typename Iterator2>
1176 template <
typename OutputIterator>
1179 return ToddCoxeterImpl::current_word_of_no_checks(
1180 detail::itow(
this, d_first), i)
1206 template <
typename OutputIterator>
1208 return ToddCoxeterImpl::current_word_of(detail::itow(
this, d_first), i)
1234 template <
typename Iterator>
1236 return ToddCoxeterImpl::word_of_no_checks(detail::itow(
this, d_first), i)
1263 template <
typename Iterator>
1265 return ToddCoxeterImpl::word_of(detail::itow(
this, d_first), i).get();
1279 template <
typename Word>
1290 template <
typename Word>
1301 template <
typename Word>
1312 template <
typename Node>
1314 -> ToddCoxeter<word_type>;
1324 template <
typename Node>
1335 template <
typename Word>
1346 template <
typename Word>
1365 template <
typename Word>
1369#include "todd-coxeter-class.tpp"
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.
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:1207
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:1235
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:1264
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:1177
ToddCoxeter(congruence_kind knd, Presentation< Word > &&p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:458
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:618
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:557
ToddCoxeter(congruence_kind knd, Presentation< Word > const &p)
Construct from congruence_kind and Presentation.
Definition todd-coxeter-class.hpp:480
ToddCoxeter(ToddCoxeter &&)=default
ToddCoxeter & init(congruence_kind knd, Presentation< Word > const &p)
Re-initialize a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:486
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:526
ToddCoxeter(congruence_kind knd, ToddCoxeter const &tc)
Construct from congruence_kind and ToddCoxeter.
Definition todd-coxeter-class.hpp:506
OutputIterator reduce_no_checks(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word with no checks.
Definition todd-coxeter-class.hpp:942
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:812
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:781
OutputIterator reduce(OutputIterator d_first, InputIterator1 first, InputIterator2 last)
Reduce a word.
Definition todd-coxeter-class.hpp:977
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:708
std::vector< Word > const & generating_pairs() const noexcept
Get the generating pairs of the congruence.
Definition todd-coxeter-class.hpp:636
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:746
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:656
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:876
OutputIterator reduce_no_run(OutputIterator d_first, InputIterator1 first, InputIterator2 last) const
Reduce a word with no enumeration.
Definition todd-coxeter-class.hpp:909
typename detail::ToddCoxeterImpl::word_graph_type word_graph_type
The type of the underlying WordGraph.
Definition todd-coxeter-class.hpp:378
typename detail::ToddCoxeterImpl::node_type node_type
The type of the nodes in the word graph.
Definition todd-coxeter-class.hpp:370
typename detail::ToddCoxeterImpl::index_type index_type
The type of the index of a class.
Definition todd-coxeter-class.hpp:395
typename detail::ToddCoxeterImpl::label_type label_type
The type of the edge-labels in the word graph.
Definition todd-coxeter-class.hpp:403
Word native_word_type
Type of the letters in the relations of the presentation stored in a ToddCoxeter instance.
Definition todd-coxeter-class.hpp:362
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:1062
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:1032
index_type index_of_no_checks(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1092
index_type index_of(Iterator1 first, Iterator2 last)
Returns the index of the class containing a word.
Definition todd-coxeter-class.hpp:1122
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:150
lookahead_style
Enum class for specifying the style of any lookahead performed.
Definition todd-coxeter-class.hpp:236
lookahead_extent
Enum class for specifying the extent of any lookahead performed.
Definition todd-coxeter-class.hpp:219
@ partial
Definition todd-coxeter-class.hpp:227
@ full
Definition todd-coxeter-class.hpp:223
strategy
Enum class containing various strategies.
Definition todd-coxeter-class.hpp:161
@ CR
Definition todd-coxeter-class.hpp:180
@ Cr
Definition todd-coxeter-class.hpp:199
@ hlt
Definition todd-coxeter-class.hpp:165
@ felsch
Definition todd-coxeter-class.hpp:170
@ Rc
Definition todd-coxeter-class.hpp:210
@ R_over_C
Definition todd-coxeter-class.hpp:189
def_version
Values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:313
@ two
Version 2 definition processing.
Definition todd-coxeter-class.hpp:317
@ one
Version 1 definition processing.
Definition todd-coxeter-class.hpp:315
def_policy
Enum class containing values for specifying how to handle edge definitions.
Definition todd-coxeter-class.hpp:267
@ discard_all_if_no_space
Definition todd-coxeter-class.hpp:284
@ unlimited
Definition todd-coxeter-class.hpp:287
@ no_stack_if_no_space
Definition todd-coxeter-class.hpp:270
@ purge_from_top
Definition todd-coxeter-class.hpp:275
@ purge_all
Definition todd-coxeter-class.hpp:280