Defined in froidure-pin-base.hpp.

FroidurePinBase is an abstract base class for the class template FroidurePin.

FroidurePinBase allows a polymorphic interface to instances of FroidurePin and its member functions reflect those member functions of FroidurePin that do not depend on the template parameter Element (the type of the elements of the semigroup represented).

See also: FroidurePin and FroidurePinTraits.

Inheritance diagram for FroidurePinBase:

[legend]

Classes
class	const_normal_form_iterator
	Return type of cbegin_normal_forms and cend_normal_forms. More...

class	const_rule_iterator
	Return type of cbegin_rules and cend_rules. More...

Public Types
using	cayley_graph_type = WordGraph<element_index_type>
	Alias for the types of the left and right Cayley graphs.

using	element_index_type = size_type
	Alias for the index of an element.

using	generator_index_type = size_type
	Alias for the index of a generator.

using	size_type = uint32_t
	Alias for the type of the size of the enumerated semigroup.

Public Types inherited from Runner
enum class	state { never_run = 0 , running_to_finish = 1 , running_for = 2 , running_until = 3 , timed_out = 4 , stopped_by_predicate = 6 , not_running = 7 , dead = 8 }
	Enum class for the state of the Runner. More...

Public Types inherited from Reporter
using	nanoseconds = std::chrono::nanoseconds
	Alias for std::chrono::nanoseconds.

using	time_point = std::chrono::high_resolution_clock::time_point
	Alias for std::chrono::high_resolution_clock::time_point.

Public Member Functions
	FroidurePinBase ()
	Default constructor.

	FroidurePinBase (FroidurePinBase &&other)=default
	Default move constructor.

	FroidurePinBase (FroidurePinBase const &S)
	Copy constructor.

size_t	batch_size () const noexcept
	Returns the current value of the batch size.

FroidurePinBase &	batch_size (size_t batch_size) noexcept
	Set a new value for the batch size.

const_normal_form_iterator	cbegin_current_normal_forms () const
	Returns an iterator pointing at the first normal form (if any).

const_rule_iterator	cbegin_current_rules () const
	Returns a forward iterator pointing to the first rule (if any).

const_normal_form_iterator	cbegin_normal_forms ()
	Returns an iterator pointing at the first normal form (if any).

const_rule_iterator	cbegin_rules ()
	Returns a forward iterator pointing to the first rule (if any).

const_normal_form_iterator	cend_current_normal_forms () const
	Returns an iterator pointing one beyond the last normal form (if any).

const_rule_iterator	cend_current_rules () const
	Returns a forward iterator pointing one past the last rule (if any).

const_normal_form_iterator	cend_normal_forms ()
	Returns an iterator pointing one beyond the last normal form (if any).

const_rule_iterator	cend_rules ()
	Returns a forward iterator pointing one past the last rule (if any).

bool	contains_one ()
	Check if the categorical multiplicative identity is an element.

template<typename Iterator>
void	current_factorisation_no_checks (Iterator d_first, element_index_type pos) const
	Output to an iterator a word representing an element given by index.

cayley_graph_type const &	current_left_cayley_graph () const noexcept
	Returns a const reference to the left Cayley graph.

size_t	current_length (element_index_type pos) const
	Returns the length of the short-lex least word equal to the element with given index.

size_t	current_length_no_checks (element_index_type pos) const
	Returns the length of the short-lex least word equal to the element with given index.

size_t	current_max_word_length () const noexcept
	Returns the maximum length of a word in the generators so far computed.

template<typename Iterator>
void	current_minimal_factorisation (Iterator d_first, element_index_type pos) const
	Output to an iterator the short-lex least word representing an element given by index.

template<typename Iterator>
void	current_minimal_factorisation_no_checks (Iterator d_first, element_index_type pos) const
	Output to an iterator the short-lex least word representing an element given by index.

size_t	current_number_of_rules () const noexcept
	Returns the number of rules that have been found so far.

template<typename Iterator1, typename Iterator2>
element_index_type	current_position (Iterator1 first, Iterator2 last) const
	Returns the position corresponding to a word.

template<typename Iterator1, typename Iterator2>
element_index_type	current_position_no_checks (Iterator1 first, Iterator2 last) const
	Returns the position corresponding to a word.

cayley_graph_type const &	current_right_cayley_graph () const noexcept
	Returns a const reference to the right Cayley graph.

size_t	current_size () const noexcept
	Returns the number of elements so far enumerated.

bool	currently_contains_one () const noexcept
	Check if the categorical multiplicative identity is known to be an element.

size_t	degree () const noexcept
	Returns the degree of any and all elements.

void	enumerate (size_t limit)
	Enumerate until at least a specified number of elements are found.

template<typename Iterator>
void	factorisation (Iterator d_first, element_index_type pos)
	Output to an iterator a word representing an element given by index.

generator_index_type	final_letter (element_index_type pos) const
	Returns the last letter of the element with specified index.

generator_index_type	final_letter_no_checks (element_index_type pos) const
	Returns the first letter of the element with specified index.

generator_index_type	first_letter (element_index_type pos) const
	Returns the first letter of the element with specified index.

generator_index_type	first_letter_no_checks (element_index_type pos) const
	Returns the first letter of the element with specified index.

FroidurePinBase &	init ()
	Reinitialize a FroidurePinBase object.

cayley_graph_type const &	left_cayley_graph ()
	Returns a const reference to the left Cayley graph.

size_t	length (element_index_type pos)
	Returns the length of the short-lex least word equal to the element with given index.

size_t	length_no_checks (element_index_type pos)
	Returns the length of the short-lex least word equal to the element with given index.

template<typename Iterator>
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.

size_t	number_of_elements_of_length (size_t len) const
	Returns the number of elements so far enumerated with given length.

size_t	number_of_elements_of_length (size_t min, size_t max) const
	Returns the number of elements so far enumerated with length in a given range.

size_t	number_of_rules ()
	Returns the total number of relations in the presentation.

FroidurePinBase &	operator= (FroidurePinBase &&)=default
	Move assignment operator.

FroidurePinBase &	operator= (FroidurePinBase const &)
	Copy assignment operator.

template<typename Iterator1, typename Iterator2>
element_index_type	position (Iterator1 first, Iterator2 last)
	Returns the position corresponding to a word.

template<typename Iterator1, typename Iterator2>
element_index_type	position_no_checks (Iterator1 first, Iterator2 last)
	Returns the position corresponding to a word.

element_index_type	position_of_generator (generator_index_type i) const
	Returns the position of the generator with specified index.

element_index_type	position_of_generator_no_checks (generator_index_type i) const
	Returns the position of the generator with specified index.

element_index_type	prefix (element_index_type pos) const
	Returns the position of the longest proper prefix.

element_index_type	prefix_no_checks (element_index_type pos) const
	Returns the position of the longest proper prefix.

cayley_graph_type const &	right_cayley_graph ()
	Returns a const reference to the right Cayley graph.

size_t	size ()
	Returns the size of a FroidurePin instance.

element_index_type	suffix (element_index_type pos) const
	Returns the position of the longest proper suffix.

element_index_type	suffix_no_checks (element_index_type pos) const
	Returns the position of the longest proper suffix.

template<typename Iterator1, typename Iterator2>
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.

void	throw_if_element_index_out_of_range (element_index_type i) const
	Throw an exception if an index is out of range.

void	throw_if_generator_index_out_of_range (generator_index_type i) const
	Throw an exception if a generator index is out of range.

Public Member Functions inherited from Runner
	Runner ()
	Default constructor.

	Runner (Runner &&other)
	Move constructor.

	Runner (Runner const &other)
	Copy constructor.

state	current_state () const noexcept
	Return the current state.

bool	dead () const noexcept
	Check if the runner is dead.

bool	finished () const
	Check if run has been run to completion or not.

Runner &	init ()
	Initialize an existing Runner object.

void	kill () noexcept
	Stop run from running (thread-safe).

Runner &	operator= (Runner &&other)
	Move assignment operator.

Runner &	operator= (Runner const &other)
	Copy assignment operator.

void	report_why_we_stopped () const
	Report why run stopped.

void	run ()
	Run until finished.

void	run_for (std::chrono::nanoseconds t)
	Run for a specified amount of time.

template<typename Time>
void	run_for (Time t)
	Run for a specified amount of time.

void	run_until (bool(*func)())
	Run until a nullary predicate returns `true` or finished.

template<typename Func>
void	run_until (Func &&func)
	Run until a nullary predicate returns `true` or finished.

bool	running () const noexcept
	Check if currently running.

bool	running_for () const noexcept
	Check if the runner is currently running for a particular length of time.

bool	running_until () const noexcept
	Check if the runner is currently running until a nullary predicate returns `true`.

bool	started () const noexcept
	Check if run has been called at least once before.

bool	stopped () const
	Check if the runner is stopped.

bool	stopped_by_predicate () const
	Check if the runner was stopped, or should stop, because of the argument last passed to run_until.

virtual bool	success () const
	Check if run has been run to completion successfully.

bool	timed_out () const
	Check if the amount of time passed to run_for has elapsed.

Public Member Functions inherited from Reporter
	Reporter ()
	Default constructor.

	Reporter (Reporter &&that)
	Default move constructor.

	Reporter (Reporter const &that)
	Default copy constructor.

void	emit_divider ()

Reporter &	init ()
	Initialize an existing Reporter object.

time_point	last_report () const noexcept
	Get the time point of the last report.

Reporter &	operator= (Reporter &&that)
	Default move assignment operator.

Reporter &	operator= (Reporter const &that)
	Default copy assignment operator.

bool	report () const
	Check if it is time to report.

std::string const &	report_divider () const noexcept

Reporter &	report_divider (std::string const &val)

nanoseconds	report_every () const noexcept
	Get the minimum elapsed time between reports.

Reporter &	report_every (nanoseconds val) noexcept
	Set the minimum elapsed time between reports in nanoseconds.

template<typename Time>
Reporter &	report_every (Time t) noexcept
	Set the minimum elapsed time between reports in a unit of time other than nanoseconds.

std::string const &	report_prefix () const noexcept
	Get the current prefix string for reporting.

Reporter &	report_prefix (std::string const &val)
	Set the prefix string for reporting.

Reporter const &	reset_last_report () const
	Set the last report time point to now.

Reporter const &	reset_start_time () const
	Reset the start time (and last report) to now.

time_point	start_time () const noexcept
	Get the start time.

Additional Inherited Members
Related Symbols inherited from Reporter
static std::chrono::nanoseconds	delta (std::chrono::high_resolution_clock::time_point const &t)
	The time between a given point and now.

Member Typedef Documentation

◆ element_index_type

using element_index_type = size_type

The size of the semigroup being enumerated must be at most std::numeric_limits<element_index_type>::max().

◆ generator_index_type

using generator_index_type = size_type

Alias for size_type used to indicate that a value should be the index of a generator.

Constructor & Destructor Documentation

◆ FroidurePinBase() [1/3]

FroidurePinBase ( )

Default constructor.

◆ FroidurePinBase() [2/3]

FroidurePinBase ( FroidurePinBase const & S )

Copy constructor.

◆ FroidurePinBase() [3/3]

FroidurePinBase ( FroidurePinBase && other )

default

Default move constructor.

Member Function Documentation

◆ batch_size() [1/2]

size_t batch_size ( ) const

inlinenodiscardnoexcept

This function returns the minimum number of elements enumerated in any call to run.

Returns: The current value of the batch size.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

See also: batch_size(size_t).

◆ batch_size() [2/2]

FroidurePinBase & batch_size ( size_t batch_size )

inlinenoexcept

The batch size is the number of new elements to be found by any call to run. This is used by, for example, FroidurePin::position so that it is possible to find the position of an element after only partially enumerating the elements of a FrodiurePin instance.

The default value of the batch size is 8192.

Parameters

batch_size the new value for the batch size.

Returns: A reference to *this.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

See also: batch_size.

◆ cbegin_current_normal_forms()

const_normal_form_iterator cbegin_current_normal_forms ( ) const

inlinenodiscard

This function returns an iterator pointing at the normal form of the first element of the semigroup represented by a FroidurePinBase instance (if any).

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then use cbegin_normal_forms instead.

Returns: An iterator of type const_normal_form_iterator pointing to a word_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ cbegin_current_rules()

const_rule_iterator cbegin_current_rules ( ) const

inlinenodiscard

Returns a forward iterator pointing to the first rule in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin object. If you want to obtain the complete set of rules, then use cbegin_rules instead.

Returns: An iterator of type const_rule_iterator pointing to a relation_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Iterator validity: The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

See also: cend_rules

Example: FroidurePin<BMat8> S;

S.add_generator(BMat8({{1, 0, 0, 0},

{1, 0, 0, 0},

{1, 0, 0, 0},

{1, 0, 0, 0}}));

S.add_generator(BMat8({{0, 1, 0, 0},

{0, 1, 0, 0},

{0, 1, 0, 0},

{0, 1, 0, 0}}));

S.add_generator(BMat8({{0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 1, 0}}));

S.add_generator(BMat8({{0, 0, 0, 1},

{0, 0, 0, 1},

{0, 0, 0, 1},

{0, 0, 0, 1}}));

S.size(); // 4

std::vector<relation_type>(S.cbegin_rules(), S.cend_rules());

// {{{0, 0}, {0}},

// {{0, 1}, {1}},

// {{0, 2}, {2}},

// {{0, 3}, {3}},

// {{1, 0}, {0}},

// {{1, 1}, {1}},

// {{1, 2}, {2}},

// {{1, 3}, {3}},

// {{2, 0}, {0}},

// {{2, 1}, {1}},

// {{2, 2}, {2}},

// {{2, 3}, {3}},

// {{3, 0}, {0}},

// {{3, 1}, {1}},

// {{3, 2}, {2}},

// {{3, 3}, {3}}}

libsemigroups::BMat8
Fast boolean matrices of dimension up to 8 x 8.
Definition bmat8.hpp:74

libsemigroups::FroidurePinBase::cend_rules
const_rule_iterator cend_rules()
Returns a forward iterator pointing one past the last rule (if any).
Definition froidure-pin-base.hpp:1509

libsemigroups::FroidurePinBase::size
size_t size()
Returns the size of a FroidurePin instance.
Definition froidure-pin-base.hpp:850

libsemigroups::FroidurePinBase::cbegin_rules
const_rule_iterator cbegin_rules()
Returns a forward iterator pointing to the first rule (if any).
Definition froidure-pin-base.hpp:1405

libsemigroups::FroidurePin::add_generator
FroidurePin & add_generator(const_reference x)
Add a copy of an element to the generators.

Note: This function does not trigger any enumeration.

◆ cbegin_normal_forms()

const_normal_form_iterator cbegin_normal_forms ( )

inlinenodiscard

This function returns an iterator pointing at the normal form of the first element of the semigroup represented by a FroidurePinBase instance (if any).

This function performs a full enumeration of the FroidurePin. If you want to obtain the current set of normal forms without triggering an enumeration, then use cbegin_current_normal_forms instead.

Returns: An iterator of type const_normal_form_iterator pointing to a word_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Same as FroidurePinBase::enumerate.

Note: This function triggers a full enumeration.

◆ cbegin_rules()

const_rule_iterator cbegin_rules ( )

inlinenodiscard

Returns a forward iterator pointing to the first rule in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by a FroidurePinBase instance.

This function fully enumerate the FroidurePinBase object. If you want to obtain a (possibly incomplete) set of rules without triggering a full enumeration, then use cbegin_current_rules instead.

Returns: An iterator of type const_rule_iterator pointing to a relation_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Iterator validity: The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Note: This function triggers a full enumeration.

See also: cend_rules

◆ cend_current_normal_forms()

const_normal_form_iterator cend_current_normal_forms ( ) const

inlinenodiscard

This function returns an iterator pointing one beyond the normal form of the last element of the semigroup represented by a FroidurePinBase instance (if any).

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then use cend_normal_forms instead.

Returns: An iterator of type const_normal_form_iterator pointing to a word_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ cend_current_rules()

const_rule_iterator cend_current_rules ( ) const

inlinenodiscard

Returns a forward iterator pointing one-past-the-last rule (currently known) in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function does not perform any enumeration of the FroidurePin. If you want to obtain the complete set of rules, then use cend_rules instead.

Returns: An iterator of type const_rule_iterator pointing to a relation_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Iterator validity: The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Note: This function does not trigger any enumeration.

See also: cbegin_rules

Example: FroidurePin<BMat8> S;

S.add_generator(BMat8({{1, 0, 0, 0},

{1, 0, 0, 0},

{1, 0, 0, 0},

{1, 0, 0, 0}}));

S.add_generator(BMat8({{0, 1, 0, 0},

{0, 1, 0, 0},

{0, 1, 0, 0},

{0, 1, 0, 0}}));

S.add_generator(BMat8({{0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 1, 0},

{0, 0, 1, 0}}));

S.add_generator(BMat8({{0, 0, 0, 1},

{0, 0, 0, 1},

{0, 0, 0, 1},

{0, 0, 0, 1}}));

S.size(); // 4

std::vector<relation_type>(S.cbegin_rules(), S.cend_rules());

// {{{0, 0}, {0}},

// {{0, 1}, {1}},

// {{0, 2}, {2}},

// {{0, 3}, {3}},

// {{1, 0}, {0}},

// {{1, 1}, {1}},

// {{1, 2}, {2}},

// {{1, 3}, {3}},

// {{2, 0}, {0}},

// {{2, 1}, {1}},

// {{2, 2}, {2}},

// {{2, 3}, {3}},

// {{3, 0}, {0}},

// {{3, 1}, {1}},

// {{3, 2}, {2}},

// {{3, 3}, {3}}}

◆ cend_normal_forms()

const_normal_form_iterator cend_normal_forms ( )

inlinenodiscard

This function returns an iterator pointing one beyond the normal form of the last element of the semigroup represented by a FroidurePinBase instance (if any).

This function performs a full enumeration of the FroidurePin. If you want to obtain the current set of rules without triggering an enumeration, then use cend_current_normal_forms instead.

Returns: An iterator of type const_normal_form_iterator pointing to a word_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function triggers a full enumeration.

◆ cend_rules()

const_rule_iterator cend_rules ( )

inlinenodiscard

Returns a forward iterator pointing one-past-the-last rule in a confluent terminating rewriting system defining a semigroup isomorphic to the one defined by this.

This function fully enumerate the FroidurePin object. If you want to obtain a (possibly incomplete) set of rules without triggering a full enumeration, then use cend_rules instead.

Returns: An iterator of type const_rule_iterator pointing to a relation_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Iterator validity: The iterators returned by this function are valid until the underlying FroidurePin instance is deleted.

Note: This function triggers a full enumeration.

See also: cbegin_rules

◆ contains_one()

bool contains_one ( )

nodiscard

This function returns true if the return value of FroidurePin::One() is an element of the FroidurePin instance.

Returns: Whether or not the multiplicative identity is an element.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by a FroidurePinBase instance, and \(n\) is FroidurePin::number_of_generators.

Note: This function triggers a full enumeration.

◆ current_factorisation_no_checks()

template<typename Iterator>

void current_factorisation_no_checks	(	Iterator	d_first,
		element_index_type	pos ) const

inline

This function computes a (not necessarily minimal) word (in the generators) equal to the element in position pos and stores the result in the output range starting from d_first.

Template Parameters

Iterator the type of the first argument (an output iterator).

Parameters

d_first	output iterator for the result.
pos	the index of the element whose factorisation is sought.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: \(O(m)\) where \(m\) is the length of the returned word.

Note: This function triggers an enumeration until it is complete or at least pos elements are found.

Warning: This function does not check its arguments. In particular, it is assumed that pos is less than current_size.

◆ current_left_cayley_graph()

cayley_graph_type const & current_left_cayley_graph ( ) const

inlinenodiscardnoexcept

This function returns a const reference to the left Cayley graph.

Returns: The (possibly partially enumerated) left Cayley graph.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by the FroidurePinBase instance, and \(n\) is FroidurePin::number_of_generators.

Note: This function does not trigger any enumeration.

◆ current_length()

size_t current_length ( element_index_type pos ) const

inlinenodiscard

This function returns the length of the short-lex least word (in the generators) equal to the element with index pos.

Parameters

pos	the position.

Returns: The length of the word equal to the element with index pos.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: This function does not trigger any enumeration.

See also: length.

◆ current_length_no_checks()

size_t current_length_no_checks ( element_index_type pos ) const

inlinenodiscard

This function returns the length of the short-lex least word (in the generators) equal to the element with index pos. No enumeration is triggered by calls to this function.

Parameters

pos	the position.

Returns: The length of the word equal to the element with index pos.

Complexity: Constant.

Note: This function does not trigger any enumeration.

Warning: This function does not check that pos is valid. In particular, if pos > current_size(), then bad things will happen.

See also: length.

◆ current_max_word_length()

size_t current_max_word_length ( ) const

inlinenodiscardnoexcept

Every element can be expressed as the short-lex least product of the generators that equals that element. This function returns the length of the longest short-lex least word in the generators that has so far been enumerated.

Returns: A value of type size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ current_minimal_factorisation()

template<typename Iterator>

void current_minimal_factorisation	(	Iterator	d_first,
		element_index_type	pos ) const

inline

This function computes a minimal word with respect to the short-lex ordering (of the generators) equal to the element in position pos and stores the result in the output range starting from d_first.

Template Parameters

Iterator the type of the first argument (an output iterator).

Parameters

d_first	output iterator for the result.
pos	the index of the element whose factorisation is sought.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ current_minimal_factorisation_no_checks()

template<typename Iterator>

void current_minimal_factorisation_no_checks	(	Iterator	d_first,
		element_index_type	pos ) const

inline

This function computes a minimal word with respect to the short-lex ordering (of the generators) equal to the element in position pos and stores the result in the output range starting from d_first.

Template Parameters

Iterator the type of the first argument (an output iterator).

Parameters

d_first	output iterator for the result.
pos	the index of the element whose factorisation is sought.

Complexity: Constant.

Note: This function does not trigger any enumeration.

Warning: This function does not check that pos is valid. In particular, if pos > current_size(), then bad things will happen.

◆ current_number_of_rules()

size_t current_number_of_rules ( ) const

inlinenodiscardnoexcept

This is only guaranteed to be the actual number of rules in a presentation defining the FroidurePinBase object if it is fully enumerated.

Returns: The number of rules found so far.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

◆ current_position()

template<typename Iterator1, typename Iterator2>

element_index_type current_position	(	Iterator1	first,
		Iterator2	last ) const

inlinenodiscard

This function returns the position in a FroidurePin instance corresponding to the word in the generators given by first and last. No enumeration is performed, and UNDEFINED is returned if the word does not currently correspond to an element.

Template Parameters

Iterator1	type of the first argument.
Iterator2	type of the second argument.

Parameters

first	iterator pointing at the first letter in the word.
last	iterator pointing one beyond the last letter in the word.

Returns: The index of the element corresponding to the word given by first and last, or UNDEFINED if there is no such element.

Exceptions

LibsemigroupsException if any of the letters (pointed at by iterators in the range from first to last) is out of range (exceeds FroidurePin::number_of_generators).

Complexity: \(O(n)\) where \(n\) is the length of the distance from first to last.

Note: This function does not trigger any enumeration.

See also: FroidurePin::to_element; FroidurePin::current_position_no_checks; FroidurePin::position_no_checks; FroidurePin::position

◆ current_position_no_checks()

template<typename Iterator1, typename Iterator2>

FroidurePinBase::element_index_type current_position_no_checks	(	Iterator1	first,
		Iterator2	last ) const

nodiscard

This function returns the position in a FroidurePin instance corresponding to the word in the generators given by the iterators first and last. No enumeration is performed, and UNDEFINED is returned if the word does not currently correspond to an element.

Template Parameters

Iterator1	type of the first argument.
Iterator2	type of the second argument.

Parameters

first	iterator pointing at the first letter in the word.
last	iterator pointing one beyond the last letter in the word.

Returns: The index of the element corresponding to the word given by first and last, or UNDEFINED if there is no such element.

Complexity: \(O(n)\) where \(n\) is the length of the distance from first to last.

Note: This function does not trigger any enumeration.

Warning: This function does not check its argument is valid. In particular, if any of the letters (pointed at by iterators in the range from first to last) is out of range, then bad things will happen.

See also: FroidurePin::to_element; FroidurePin::current_position; FroidurePin::position_no_checks; FroidurePin::position

◆ current_right_cayley_graph()

cayley_graph_type const & current_right_cayley_graph ( ) const

inlinenodiscardnoexcept

This function triggers a full enumeration, and then returns the right Cayley graph of the semigroup represented by a FroidurePin instance.

Returns: The full enumerated right Cayley graph.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ current_size()

size_t current_size ( ) const

inlinenodiscardnoexcept

This is only the actual size if the FroidurePinBase object is fully enumerated.

Returns: A value of type size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ currently_contains_one()

bool currently_contains_one ( ) const

inlinenodiscardnoexcept

This function returns true if the return value of FroidurePin::One()() is already known to be an element of the FroidurePin instance.

Returns: Whether or not the multiplicative identity is already known to be an element.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by a FroidurePinBase instance, and \(n\) is FroidurePin::number_of_generators.

Note: This function does not trigger any enumeration.

◆ degree()

size_t degree ( ) const

inlinenodiscardnoexcept

This function returns the degree of any and all elements.

Returns: A value of type size_t.

Exceptions: This function is noexcept and is guaranteed never to throw.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ enumerate()

void enumerate ( size_t limit )

If an FroidurePinBase instance is already fully enumerated, or the number of elements previously enumerated exceeds limit, then calling this function does nothing. Otherwise, run attempts to find at least the maximum of limit and batch_size additional elements of the semigroup.

Parameters

limit the approximate limit for current_size.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(mn)\) where \(m\) equals limit and \(n\) is FroidurePin::number_of_generators.

◆ factorisation()

template<typename Iterator>

void factorisation	(	Iterator	d_first,
		element_index_type	pos )

inline

This function computes a (not necessarily minimal) word (in the generators) equal to the element in position pos and stores the result in the output range starting from d_first.

Template Parameters

Iterator the type of the first argument (an output iterator).

Parameters

d_first	output iterator for the result.
pos	the index of the element whose factorisation is sought.

Exceptions

LibsemigroupsException if pos is greater than or equal to size.

Complexity: At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Note: This function triggers an enumeration until it is complete or at least pos elements are found.

◆ final_letter()

generator_index_type final_letter ( element_index_type pos ) const

inlinenodiscard

This function returns the final letter of the element in position pos, which is the index of the generator corresponding to the final letter of the element.

Parameters

pos	the position.

Returns: A value of type generator_index_type.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.; This function does not trigger any enumeration.

◆ final_letter_no_checks()

generator_index_type final_letter_no_checks ( element_index_type pos ) const

inlinenodiscard

This function returns the first letter of the element in position pos, which is the index of the generator corresponding to the first letter of the element.

This function does not trigger an enumeration.

Parameters

pos	the position.

Returns: A value of type generator_index_type.

Complexity: Constant.

Note: Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.; This function does not trigger any enumeration.

Warning: No checks are made that the argument pos is valid. In particular, if pos is greater than or equal to current_size, then bad things will happen.

◆ first_letter()

generator_index_type first_letter ( element_index_type pos ) const

inlinenodiscard

This function returns the first letter of the element in position pos, which is the index of the generator corresponding to the first letter of the element.

Parameters

pos	the position.

Returns: A value of type generator_index_type.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.; This function does not trigger any enumeration.

◆ first_letter_no_checks()

generator_index_type first_letter_no_checks ( element_index_type pos ) const

inlinenodiscard

This function returns the first letter of the element in position pos, which is the index of the generator corresponding to the first letter of the element.

This function does not trigger an enumeration.

Parameters

pos	the position.

Returns: A value of type generator_index_type.

Complexity: Constant.

Note: Note that FroidurePin::generator(first_letter(pos)) is only equal to FroidurePin::at(first_letter(pos)) if there are no duplicate generators.; This function does not trigger any enumeration.

Warning: No checks are made that the argument pos is valid. In particular, if pos is greater than or equal to current_size, then bad things will happen.

◆ init()

FroidurePinBase & init ( )

This function re-initializes a FroidurePinBase object so that it is in the same state as if it had just been default constructed.

Returns: A reference to *this.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

◆ left_cayley_graph()

cayley_graph_type const & left_cayley_graph ( )

inlinenodiscard

This function triggers a full enumeration, and then returns the left Cayley graph of the semigroup represented by a FroidurePin instance.

Returns: The fully enumerated left Cayley graph.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function triggers a full enumeration.

◆ length()

size_t length ( element_index_type pos )

nodiscard

This function returns the length of the short-lex least word equal to the element with given index.

Parameters

pos	the position.

Returns: The length of the element with index pos.

Exceptions

LibsemigroupsException if pos is greater than or equal to size.

Complexity: Constant.

Note: This function triggers a full enumeration.

See also: current_length.

◆ length_no_checks()

size_t length_no_checks ( element_index_type pos )

nodiscard

This function returns the length of the short-lex least word equal to the element with given index.

Parameters

pos	the position.

Returns: The length of the element with index pos.

Complexity: Constant.

Note: This function triggers a full enumeration.

Warning: This function does not check that pos is valid. In particular, if pos is greater than or equal to size, then bad things will happen.

See also: current_length.

◆ minimal_factorisation()

template<typename Iterator>

void minimal_factorisation	(	Iterator	d_first,
		element_index_type	pos )

inline

This function computes a minimal word with respect to the short-lex ordering (of the generators) equal to the element in position pos and stores the result in the output range starting from d_first.

Template Parameters

Iterator the type of the first argument (an output iterator).

Parameters

d_first	output iterator for the result.
pos	the index of the element whose factorisation is sought.

Exceptions

LibsemigroupsException if pos is greater than or equal to size().

Complexity: At worst \(O(mn)\) where \(m\) equals pos and \(n\) is the return value of FroidurePin::number_of_generators.

Note: This function triggers an enumeration until it is complete or at least pos elements are found.

◆ number_of_elements_of_length() [1/2]

size_t number_of_elements_of_length ( size_t len ) const

nodiscard

This function returns the number of elements that have been enumerated so far with length len. This function does not trigger any enumeration.

Parameters

len	the length.

Returns: The number of elements with length len.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ number_of_elements_of_length() [2/2]

size_t number_of_elements_of_length	(	size_t	min,
		size_t	max ) const

nodiscard

This function returns the number of elements that have been enumerated so far with length in the range \([min, max)\). This function does not trigger any enumeration.

Parameters

min	the minimum length.
max	the maximum length plus one.

Returns: The number of elements with lengths in the specified range.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ number_of_rules()

size_t number_of_rules ( )

inlinenodiscard

This function returns the total number of relations in the presentation.

Returns: A value of type size_t.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Note: This function triggers a full enumeration.

See also: cbegin_rules and cend_rules.

◆ operator=() [1/2]

FroidurePinBase & operator= ( FroidurePinBase && )

default

Move assignment operator.

◆ operator=() [2/2]

FroidurePinBase & operator= ( FroidurePinBase const & )

Copy assignment operator.

◆ position()

template<typename Iterator1, typename Iterator2>

element_index_type position	(	Iterator1	first,
		Iterator2	last )

inlinenodiscard

This function returns the position in a FroidurePin instance corresponding to the word in the generators given by first and last. This function triggers a full enumeration.

Template Parameters

Iterator1	type of the first argument.
Iterator2	type of the second argument.

Parameters

first	iterator pointing at the first letter in the word.
last	iterator pointing one beyond the last letter in the word.

Returns: The index of the element corresponding to the word given by first and last, or UNDEFINED if there is no such element.

Exceptions

LibsemigroupsException if any of the letters (pointed at by iterators in the range from first to last) is out of range (exceeds FroidurePin::number_of_generators).

Complexity: \(O(n)\) where \(n\) is the length of the distance from first to last.

Note: This function triggers a full enumeration.

See also: FroidurePin::to_element; FroidurePin::current_position; FroidurePin::current_position_no_checks; FroidurePin::position_no_checks; FroidurePin::position

◆ position_no_checks()

template<typename Iterator1, typename Iterator2>

element_index_type position_no_checks	(	Iterator1	first,
		Iterator2	last )

inlinenodiscard

This function returns the position in a FroidurePin instance corresponding to the word in the generators given by the iterators first and last. This function triggers a full enumeration.

Template Parameters

Iterator1	type of the first argument.
Iterator2	type of the second argument.

Parameters

first	iterator pointing at the first letter in the word.
last	iterator pointing one beyond the last letter in the word.

Returns: The index of the element corresponding to the word given by first and last.

Complexity: \(O(n)\) where \(n\) is the length of the distance from first to last.

Note: This function triggers a full enumeration.

Warning: This function does not check its argument is valid. In particular, if any of the letters (pointed at by iterators in the range from first to last) is out of range, then bad things will happen.

See also: FroidurePin::to_element; FroidurePin::current_position_no_checks; FroidurePin::current_position; FroidurePin::position

◆ position_of_generator()

element_index_type position_of_generator ( generator_index_type i ) const

inlinenodiscard

In many cases position_of_generator(i) will equal i, examples of when this will not be the case are:

there are duplicate generators;
FroidurePin::add_generators was called after a FroidurePinBase object was already partially enumerated.

Parameters

i	the index of the generator.

Returns: The position of the i-th generator.

Exceptions

LibsemigroupsException if i is greater than or equal to FroidurePin::number_of_generators.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ position_of_generator_no_checks()

element_index_type position_of_generator_no_checks ( generator_index_type i ) const

inlinenodiscard

In many cases position_of_generator(i) will equal i, examples of when this will not be the case are:

there are duplicate generators;
FroidurePin::add_generators was called after a FroidurePinBase object was already partially enumerated.

Parameters

i	the index of the generator.

Returns: The position of the i-th generator.

Complexity: Constant.

Note: This function does not trigger any enumeration.

Warning: This function does not check its argument is valid. In particular, if there is no generator with index i, then bad things will happen.

◆ prefix()

element_index_type prefix ( element_index_type pos ) const

inline

Returns the position of the prefix of the element x in position pos of length one less than the length of x.

Parameters

pos	the position.

Returns: A value of type element_index_type.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ prefix_no_checks()

element_index_type prefix_no_checks ( element_index_type pos ) const

inline

Returns the position of the prefix of the element x in position pos (of the semigroup) of length one less than the length of x.

Parameters

pos	the position.

Returns: A value of type element_index_type.

Complexity: Constant.

Note: This function does not trigger any enumeration.

Warning: No checks are made that the argument pos is valid. In particular, if pos is greater than or equal to current_size, then bad things will happen.

◆ right_cayley_graph()

cayley_graph_type const & right_cayley_graph ( )

inlinenodiscard

This function returns a const reference to the right Cayley graph.

Returns: A const reference to cayley_graph_type.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by this, and \(n\) is the return value of FroidurePin::number_of_generators.

Note: This function triggers a full enumeration.

◆ size()

size_t size ( )

inlinenodiscard

This function fully enumerates the FroidurePin instance and then returns the number of elements.

Returns: The size.

Exceptions: This function guarantees not to throw a LibsemigroupsException.

Complexity: At worst \(O(|S|n)\) where \(S\) is the semigroup represented by a FroidurePinBase instance, and \(n\) is FroidurePin::number_of_generators.

Note: This function triggers a full enumeration.

◆ suffix()

element_index_type suffix ( element_index_type pos ) const

inlinenodiscard

Returns the position of the suffix of the element x in position pos of length one less than the length of x.

Parameters

pos	the position.

Returns: A value of type element_index_type.

Exceptions

LibsemigroupsException if pos is greater than or equal to current_size.

Complexity: Constant.

Note: This function does not trigger any enumeration.

◆ suffix_no_checks()

element_index_type suffix_no_checks ( element_index_type pos ) const

inlinenodiscard

Returns the position of the suffix of the element x in position pos of length one less than the length of x.

Parameters

pos	the position.

Returns: A value of type element_index_type.

Complexity: Constant.

Note: This function does not trigger any enumeration.

Warning: No checks are made that the argument pos is valid. In particular, if pos is greater than or equal to current_size, then bad things will happen.

◆ throw_if_any_generator_index_out_of_range()

template<typename Iterator1, typename Iterator2>

void throw_if_any_generator_index_out_of_range	(	Iterator1	first,
		Iterator2	last ) const

inline

This function throws an exception if any index pointed at by an iterator in the range between first and last is greater than FroidurePin::number_of_generators.

Template Parameters

Iterator1	the type of the first argument.
Iterator2	the type of the second argument.

Parameters

first	iterator pointing at the first index.
last	iterating pointing one beyond the last index.

Exceptions

LibsemigroupsException if any index pointed at by an iterator in the range from first to last exceeds FroidurePin::number_of_generators.

◆ throw_if_element_index_out_of_range()

void throw_if_element_index_out_of_range ( element_index_type i ) const

This function throws an exception if the argument i exceeds current_size.

Parameters

i	the index to check.

Exceptions

LibsemigroupsException if i exceeds current_size.

◆ throw_if_generator_index_out_of_range()

void throw_if_generator_index_out_of_range ( generator_index_type i ) const

This function throws an exception if the argument i exceeds FroidurePin::number_of_generators.

Parameters

i	the index to check.

Exceptions

LibsemigroupsException if i exceeds FroidurePin::number_of_generators.

The documentation for this class was generated from the following file:

/Users/jdm/libsemigroups/include/libsemigroups/froidure-pin-base.hpp

Classes

Public Types

Public Member Functions

Additional Inherited Members

Member Typedef Documentation

◆ element_index_type

◆ generator_index_type

Constructor & Destructor Documentation

◆ FroidurePinBase() [1/3]

◆ FroidurePinBase() [2/3]

◆ FroidurePinBase() [3/3]

Member Function Documentation

◆ batch_size() [1/2]

◆ batch_size() [2/2]

◆ cbegin_current_normal_forms()

◆ cbegin_current_rules()

◆ cbegin_normal_forms()

◆ cbegin_rules()

◆ cend_current_normal_forms()

◆ cend_current_rules()

◆ cend_normal_forms()

◆ cend_rules()

◆ contains_one()

◆ current_factorisation_no_checks()

◆ current_left_cayley_graph()

◆ current_length()

◆ current_length_no_checks()

◆ current_max_word_length()

◆ current_minimal_factorisation()

◆ current_minimal_factorisation_no_checks()

◆ current_number_of_rules()

◆ current_position()

◆ current_position_no_checks()

◆ current_right_cayley_graph()

◆ current_size()

◆ currently_contains_one()

◆ degree()

◆ enumerate()

◆ factorisation()

◆ final_letter()

◆ final_letter_no_checks()

◆ first_letter()

◆ first_letter_no_checks()

◆ init()

◆ left_cayley_graph()

◆ length()

◆ length_no_checks()

◆ minimal_factorisation()

◆ number_of_elements_of_length() [1/2]

◆ number_of_elements_of_length() [2/2]

◆ number_of_rules()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ position()

◆ position_no_checks()

◆ position_of_generator()

◆ position_of_generator_no_checks()

◆ prefix()

◆ prefix_no_checks()

◆ right_cayley_graph()

◆ size()

◆ suffix()

◆ suffix_no_checks()

◆ throw_if_any_generator_index_out_of_range()

◆ throw_if_element_index_out_of_range()

◆ throw_if_generator_index_out_of_range()