Defined in presentation.hpp
.
This class template can be used to construction presentations for semigroups or monoids and is intended to be used as the input to other algorithms in libsemigroups
. The idea is to provide a shallow wrapper around a vector of words of type Word
. We refer to this vector of words as the rules of the presentation. In addition to the rules, a Presentation object has an alphabet.
In a valid presentation, rules will only consist of letters from within the alphabet; however, for performance reasons, it is possible to update both the rules and the alphabet independently of each other. For this reason, it is possible for the alphabet and the rules to become out of sync. The Presentation class provides some checks that the rules define a valid presentation, and some related functionality is available in the namespace libsemigroups::presentation
.
Word | the type of the underlying words. |
Public Types | |
using | const_iterator = typename std::vector<word_type>::const_iterator |
Type of a const iterator to either side of a rule. | |
using | iterator = typename std::vector<word_type>::iterator |
Type of an iterator to either side of a rule. | |
using | letter_type = typename word_type::value_type |
Type of the letters in the words that constitute the rules of a Presentation object. | |
using | size_type = typename std::vector<word_type>::size_type |
Size type for rules. | |
using | word_type = Word |
Type of the words in the rules of a Presentation object. | |
Public Member Functions | |
Presentation () | |
Default constructor. | |
Presentation (Presentation &&) | |
Default move constructor. | |
Presentation (Presentation const &) | |
Default copy constructor. | |
letter_type | add_generator () |
Add a generator. | |
Presentation & | add_generator (letter_type x) |
Add x as a generator. | |
Presentation & | add_generator_no_checks (letter_type x) |
Add x as a generator. | |
template<typename Iterator1, typename Iterator2> | |
Presentation & | add_rule (Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end) |
Add a rule to the presentation and check it is valid. | |
template<typename Iterator1, typename Iterator2> | |
Presentation & | add_rule_no_checks (Iterator1 lhs_begin, Iterator1 lhs_end, Iterator2 rhs_begin, Iterator2 rhs_end) |
Add a rule to the presentation. | |
word_type const & | alphabet () const noexcept |
Return the alphabet of the presentation. | |
template<typename Return = Presentation&> | |
auto | alphabet (char const *lphbt) -> std::enable_if_t< std::is_same_v< std::string, word_type >, Return > |
Set the alphabet from string literal. | |
Presentation & | alphabet (size_type n) |
Set the alphabet by size. | |
Presentation & | alphabet (std::initializer_list< typename word_type::value_type > const &lphbt) |
Set the alphabet from std::initializer_list. | |
template<typename Return = Presentation&> | |
auto | alphabet (std::string_view lphbt) -> std::enable_if_t< std::is_same_v< std::string, word_type >, Return & > |
Set the alphabet from string_view. | |
Presentation & | alphabet (word_type &&lphbt) |
Set the alphabet from rvalue reference. | |
Presentation & | alphabet (word_type const &lphbt) |
Set the alphabet const reference. | |
Presentation & | alphabet_from_rules () |
Set the alphabet to be the letters in the rules. | |
bool | contains_empty_word () const noexcept |
Return whether the empty word is a valid relation word. | |
Presentation & | contains_empty_word (bool val) noexcept |
Set whether whether the empty word is a valid relation word. | |
bool | in_alphabet (letter_type val) const |
Check if a letter belongs to the alphabet or not. | |
size_type | index (letter_type val) const |
Return the index of a letter in the alphabet. | |
size_type | index_no_checks (letter_type val) const |
Return the index of a letter in the alphabet. | |
Presentation & | init () |
Remove the alphabet and all rules. | |
letter_type | letter (size_type i) const |
Return a letter in the alphabet by index. | |
letter_type | letter_no_checks (size_type i) const |
Return a letter in the alphabet by index. | |
Presentation & | operator= (Presentation &&) |
Default move assignment operator. | |
Presentation & | operator= (Presentation const &) |
Default copy assignment operator. | |
Presentation & | remove_generator (letter_type x) |
Remove x as a generator. | |
Presentation & | remove_generator_no_checks (letter_type x) |
Remove x as a generator. | |
void | throw_if_alphabet_has_duplicates () const |
Check if the alphabet is valid. | |
void | throw_if_bad_alphabet_or_rules () const |
Check if the alphabet and rules are valid. | |
void | throw_if_bad_rules () const |
Check if every word in every rule consists only of letters belonging to the alphabet. | |
template<typename Iterator1, typename Iterator2> | |
void | throw_if_letter_not_in_alphabet (Iterator1 first, Iterator2 last) const |
Check if every letter in a range belongs to the alphabet. | |
void | throw_if_letter_not_in_alphabet (letter_type c) const |
Check if a letter belongs to the alphabet or not. | |
Presentation | ( | ) |
Constructs an empty presentation with no rules and no alphabet.
Presentation | ( | Presentation< Word > const & | ) |
Default copy constructor.
Presentation | ( | Presentation< Word > && | ) |
Default move constructor.
letter_type add_generator | ( | ) |
Add the first letter not in the alphabet as a generator and return this letter.
LibsemigroupsException | if the alphabet is of the maximum possible size supported by letter_type . |
Presentation & add_generator | ( | letter_type | x | ) |
Add the letter x
as a generator.
x | the letter to add as a generator. |
*this
.LibsemigroupsException | if x is in p.alphabet() . |
Presentation & add_generator_no_checks | ( | letter_type | x | ) |
Add the letter x
as a generator.
x | the letter to add as a generator. |
*this
.
|
inline |
After checking that the left-hand side and right-hand side only contain letters in alphabet, this function performs the same as add_rule_no_checks(lhs_begin, lhs_end, rhs_begin, rhs_end)
.
LibsemigroupsException | if any letter does not belong to the alphabet. |
LibsemigroupsException | if contains_empty_word returns false and lhs_begin equals lhs_end or rhs_begin equals rhs_end . |
|
inline |
Adds the rule with left-hand side [lhs_begin, lhs_end)
and right-hand side [rhs_begin, rhs_end)
to the rules. It is possible to add rules directly via the data member rules, this function just exists to encourage adding rules with both sides defined at the same time.
Iterator1 | the type of the first two parameters (iterators, or pointers). |
Iterator2 | the type of the second two parameters (iterators, or pointers). |
lhs_begin | an iterator pointing to the first letter of the left-hand side of the rule to be added. |
lhs_end | an iterator pointing one past the last letter of the left-hand side of the rule to be added. |
rhs_begin | an iterator pointing to the first letter of the right-hand side of the rule to be added. |
rhs_end | an iterator pointing one past the last letter of the right-hand side of the rule to be added. |
*this
.
|
inlinenodiscardnoexcept |
Returns the alphabet of the presentation.
Presentation::word_type
.noexcept
and is guaranteed never to throw.
|
inline |
This is an overload for alphabet(word_type&&) to allow string literals to be used for the parameter lphbt
.
Presentation & alphabet | ( | size_type | n | ) |
Sets the alphabet to the range \([0, n)\) consisting of values of type letter_type.
n | the size of the alphabet. |
*this
.LibsemigroupsException | if the value of n is greater than the maximum number of letters supported by letter_type. |
|
inline |
This is an overload for alphabet(word_type&&) to allow std::initializer_list to be used for the parameter lphbt
.
|
inline |
This is an overload for alphabet(word_type&&) to allow std::string_view to be used for the parameter lphbt
.
Presentation & alphabet | ( | word_type && | lphbt | ) |
Sets the alphabet to be the letters in lphbt
.
lphbt | the alphabet. |
*this
.LibsemigroupsException | if there are duplicate letters in lphbt . |
Presentation & alphabet | ( | word_type const & | lphbt | ) |
Sets the alphabet to be the letters in lphbt
.
lphbt | the alphabet. |
*this
.LibsemigroupsException | if there are duplicate letters in lphbt . |
Presentation & alphabet_from_rules | ( | ) |
Sets the alphabet to be the letters in rules.
*this
.
|
inlinenodiscardnoexcept |
Returns true
if the empty word is a valid relation word, and false
if the empty word is not a valid relation word.
If the presentation is not allowed to contain the empty word (according to this function), the presentation may still be isomorphic to a monoid, but is not given as a quotient of a free monoid.
bool
.noexcept
and is guaranteed never to throw.
|
inlinenoexcept |
Specify whether the empty word should be a valid relation word (corresponding to val
being true
), or not (corresponding to val
being false
).
If the presentation is not allowed to contain the empty word (according to the value specified here), the presentation may still be isomorphic to a monoid, but is not given as a quotient of a free monoid.
val | whether the presentation can contain the empty word. |
*this
.noexcept
and is guaranteed never to throw.
|
inlinenodiscard |
Check if a letter belongs to the alphabet or not.
val | the letter to check. |
bool
.
|
nodiscard |
After checking that val
is in the the alphabet, this function performs the same as index_no_checks(letter_type val) const
.
LibsemigroupsException | if val does not belong to the alphabet. |
|
inlinenodiscard |
Get the index of a letter in the alphabet.
val | the letter. |
Presentation & init | ( | ) |
This function clears the alphabet and all rules from the presentation, putting it back into the state it would be in if it was newly constructed.
this
.
|
nodiscard |
After checking that i
is in the range \([0, n)\), where \(n\) is the length of the alphabet, this function performs the same as letter_no_checks(size_type i) const
.
LibsemigroupsException | if i is not in the range \([0, n)\). |
|
inlinenodiscard |
Returns the letter of the alphabet in position i
.
i | the index. |
i
. Presentation & operator= | ( | Presentation< Word > && | ) |
Default move assignment operator.
Presentation & operator= | ( | Presentation< Word > const & | ) |
Default copy assignment operator.
Presentation & remove_generator | ( | letter_type | x | ) |
Remove the letter x
as a generator.
x | the letter to remove as a generator. |
*this
.LibsemigroupsException | if x is not in p.alphabet() . |
Presentation & remove_generator_no_checks | ( | letter_type | x | ) |
Remove the letter x
as a generator.
x | the letter to remove as a generator. |
*this
.x
is not a generator, then bad things will happen.
|
inline |
Check if the alphabet is valid.
LibsemigroupsException | if there are duplicate letters in the alphabet. |
|
inline |
Check if the alphabet and rules are valid.
LibsemigroupsException | if throw_if_alphabet_has_duplicates or throw_if_bad_rules does. |
void throw_if_bad_rules | ( | ) | const |
Check if every word in every rule consists only of letters belonging to the alphabet, and that there are an even number of words in this->rules
.
LibsemigroupsException | if any word contains a letter not in the alphabet. |
LibsemigroupsException | if the number of words in this->rules is odd. |
void throw_if_letter_not_in_alphabet | ( | Iterator1 | first, |
Iterator2 | last ) const |
Check if every letter in a range belongs to the alphabet.
Iterator | the type of the arguments (iterators). |
first | iterator pointing at the first letter to check. |
last | iterator pointing one beyond the last letter to check. |
LibsemigroupsException | if there is a letter not in the alphabet between first and last |
void throw_if_letter_not_in_alphabet | ( | letter_type | c | ) | const |
Check if a letter belongs to the alphabet or not.
c | the letter to check. |
LibsemigroupsException | if c does not belong to the alphabet. |
std::vector<word_type> rules |
The rules can be altered using the member functions of std::vector
, and the presentation can be checked for validity using throw_if_bad_alphabet_or_rules.