Regina 7.3 Calculation Engine
Public Member Functions | List of all members
regina::GroupExpression Class Reference

Represents an expression involving generators from a group presentation or a free group. More...

#include <algebra/grouppresentation.h>

Inheritance diagram for regina::GroupExpression:
regina::ShortOutput< GroupExpression, true > regina::Output< GroupExpression, supportsUtf8 >

Public Member Functions

 GroupExpression ()=default
 The terms that make up this expression. More...
 
 GroupExpression (const GroupExpressionTerm &term)
 Creates a new expression containing a single term. More...
 
 GroupExpression (unsigned long generator, long exponent)
 Creates a new expression containing a single term. More...
 
 GroupExpression (const GroupExpression &)=default
 Creates a new expression that is a clone of the given expression. More...
 
 GroupExpression (GroupExpression &&) noexcept=default
 Moves the contents of the given expression to this new expression. More...
 
 GroupExpression (const char *input, unsigned long nGens=0)
 Attempts to interpret the given input string as a word in a group. More...
 
 GroupExpression (const std::string &input, unsigned long nGens=0)
 Attempts to interpret the given input string as a word in a group. More...
 
GroupExpressionoperator= (const GroupExpression &)=default
 Makes this expression a clone of the given expression. More...
 
GroupExpressionoperator= (GroupExpression &&) noexcept=default
 Moves the contents of the given expression to this expression. More...
 
void swap (GroupExpression &other) noexcept
 Swaps the contents of this and the given expression. More...
 
bool operator== (const GroupExpression &comp) const
 Equality operator. More...
 
bool operator!= (const GroupExpression &comp) const
 Inequality operator. More...
 
std::list< GroupExpressionTerm > & terms ()
 Returns the list of terms in this expression. More...
 
const std::list< GroupExpressionTerm > & terms () const
 Returns a constant reference to the list of terms in this expression. More...
 
size_t countTerms () const
 Returns the number of terms in this expression. More...
 
size_t wordLength () const
 Returns the length of the word, i.e. More...
 
bool isTrivial () const
 Tests whether this is the trivial (unit) word. More...
 
void erase ()
 Erases all terms from this this word. More...
 
GroupExpressionTermterm (size_t index)
 Returns the term at the given index in this expression. More...
 
const GroupExpressionTermterm (size_t index) const
 Returns a constant reference to the term at the given index in this expression. More...
 
unsigned long generator (size_t index) const
 Returns the generator corresonding to the term at the given index in this expression. More...
 
long exponent (size_t index) const
 Returns the exponent corresonding to the term at the given index in this expression. More...
 
void addTermFirst (const GroupExpressionTerm &term)
 Adds the given term to the beginning of this expression. More...
 
void addTermFirst (unsigned long generator, long exponent)
 Adds the given term to the beginning of this expression. More...
 
void addTermLast (const GroupExpressionTerm &term)
 Adds the given term to the end of this expression. More...
 
void addTermLast (unsigned long generator, long exponent)
 Adds the given term to the end of this expression. More...
 
void addTermsFirst (GroupExpression word)
 Multiplies this expression on the left by the given word. More...
 
void addTermsLast (GroupExpression word)
 Multiplies this expression on the right by the given word. More...
 
void cycleRight ()
 Cycles this word by moving the leftmost term around to the rightmost. More...
 
void cycleLeft ()
 Cycles this word by moving the rightmost term around to the leftmost. More...
 
GroupExpression inverse () const
 Returns the inverse of this expression. More...
 
void invert ()
 Inverts this expression. More...
 
GroupExpression power (long exponent) const
 Returns this expression raised to the given power. More...
 
bool simplify (bool cyclic=false)
 Simplifies this expression. More...
 
bool substitute (unsigned long generator, const GroupExpression &expansion, bool cyclic=false)
 Replaces every occurrence of the given generator with the given substitute expression. More...
 
void substitute (const std::vector< GroupExpression > &expansions, bool cyclic=false)
 Replaces every generator in this expression with the corresponding substitute expression from the given map. More...
 
std::list< std::map< unsigned long, GroupExpressionTerm > > relabellingsThisToOther (const GroupExpression &other, bool cyclic=false) const
 Determines whether or not one can relabel the generators in this word to obtain the given other word. More...
 
void writeXMLData (std::ostream &out) const
 Writes a chunk of XML containing this expression. More...
 
std::string tex () const
 Returns a TeX representation of this expression. More...
 
void writeTeX (std::ostream &out) const
 Writes a TeX represesentation of this expression to the given output stream. More...
 
std::string str (bool alphaGen) const
 Returns a short text representation of this group expression, with a choice of either numbered generators or alphabetic generators. More...
 
std::string utf8 (bool alphaGen) const
 Returns a short text representation of this group expression using unicode characters, with a choice of either numbered generators or alphabetic generators. More...
 
void writeTextShort (std::ostream &out, bool utf8=false, bool alphaGen=false) const
 Writes a short text representation of this object to the given output stream, using either numbered generators or alphabetic generators. More...
 
void writeTextLong (std::ostream &out) const
 A default implementation for detailed output. More...
 
std::string str () const
 Returns a short text representation of this object. More...
 
std::string utf8 () const
 Returns a short text representation of this object using unicode characters. More...
 
std::string detail () const
 Returns a detailed text representation of this object. More...
 

Detailed Description

Represents an expression involving generators from a group presentation or a free group.

An expression is represented as word, i.e, a sequence of powers of generators all of which are multiplied in order. Each power of a generator corresponds to an individual GroupExpressionTerm.

For instance, the expression g1^2 g3^-1 g6 contains the three terms g1^2, g3^-1 and g6^1 in that order.

Note that generators are indexed starting from 0 (so, for example, g3 represents the fourth generator in the group presentation, not the third).

This class implements C++ move semantics and adheres to the C++ Swappable requirement. It is designed to avoid deep copies wherever possible, even when passing or returning objects by value.

Constructor & Destructor Documentation

◆ GroupExpression() [1/7]

regina::GroupExpression::GroupExpression ( )
default

The terms that make up this expression.

Creates a new expression with no terms.

◆ GroupExpression() [2/7]

regina::GroupExpression::GroupExpression ( const GroupExpressionTerm term)
inline

Creates a new expression containing a single term.

Parameters
termthe term to use as the new expression.

◆ GroupExpression() [3/7]

regina::GroupExpression::GroupExpression ( unsigned long  generator,
long  exponent 
)
inline

Creates a new expression containing a single term.

Parameters
generatorthe number of the generator to use in the term.
exponentthe exponent to which the given generator is raised in the term.

◆ GroupExpression() [4/7]

regina::GroupExpression::GroupExpression ( const GroupExpression )
default

Creates a new expression that is a clone of the given expression.

◆ GroupExpression() [5/7]

regina::GroupExpression::GroupExpression ( GroupExpression &&  )
defaultnoexcept

Moves the contents of the given expression to this new expression.

This is a fast (constant time) operation.

The expression that was passed will no longer be usable.

◆ GroupExpression() [6/7]

regina::GroupExpression::GroupExpression ( const char *  input,
unsigned long  nGens = 0 
)

Attempts to interpret the given input string as a word in a group.

Regina can recognise strings in the following four basic forms:

  • a^7b^-2
  • aaaaaaaBB
  • a^7B^2
  • g0^7g1^-2

The string may contain whitespace, which will simply be ignored. The empty string will be treated as an expression with no terms.

Note that generators are numbered starting from 0. This means, for example, that a, b and c correspond to g0, g1 and g2 respectively.

If the optional argument nGens is passed and is positive, then this constructor will explicitly check that the given string only uses generators 0,...,(nGens-1).

Exceptions
InvalidArgumentThe given string could not be interpreted as a group expression, or else nGens was positive and the given string contains an out-of-range generator.
Parameters
inputthe input string that is to be interpreted.
nGensthe number of generators in the group presentation. If this is 0 (the default), then this argument will be ignored and this constructor will not check whether generators are within range.

◆ GroupExpression() [7/7]

regina::GroupExpression::GroupExpression ( const std::string &  input,
unsigned long  nGens = 0 
)
inline

Attempts to interpret the given input string as a word in a group.

Regina can recognise strings in the following four basic forms:

  • a^7b^-2
  • aaaaaaaBB
  • a^7B^2
  • g0^7g1^-2

The string may contain whitespace, which will simply be ignored. The empty string will be treated as an expression with no terms.

Note that generators are numbered starting from 0. This means, for example, that a, b and c correspond to g0, g1 and g2 respectively.

If the optional argument nGens is passed and is positive, then this constructor will explicitly check that the given string only uses generators 0,...,(nGens-1).

Exceptions
InvalidArgumentThe given string could not be interpreted as a group expression, or else nGens was positive and the given string contains an out-of-range generator.
Parameters
inputthe input string that is to be interpreted.
nGensthe number of generators in the group presentation. If this is 0 (the default), then this argument will be ignored and this constructor will not check whether generators are within range.

Member Function Documentation

◆ addTermFirst() [1/2]

void regina::GroupExpression::addTermFirst ( const GroupExpressionTerm term)
inline

Adds the given term to the beginning of this expression.

Parameters
termthe term to add.

◆ addTermFirst() [2/2]

void regina::GroupExpression::addTermFirst ( unsigned long  generator,
long  exponent 
)
inline

Adds the given term to the beginning of this expression.

Parameters
generatorthe number of the generator corresponding to the new term.
exponentthe exponent to which the given generator is raised.

◆ addTermLast() [1/2]

void regina::GroupExpression::addTermLast ( const GroupExpressionTerm term)
inline

Adds the given term to the end of this expression.

Parameters
termthe term to add.

◆ addTermLast() [2/2]

void regina::GroupExpression::addTermLast ( unsigned long  generator,
long  exponent 
)
inline

Adds the given term to the end of this expression.

Parameters
generatorthe number of the generator corresponding to the new term.
exponentthe exponent to which the given generator is raised.

◆ addTermsFirst()

void regina::GroupExpression::addTermsFirst ( GroupExpression  word)
inline

Multiplies this expression on the left by the given word.

This expression will be modified directly.

Parameters
wordthe word to multiply with this expression.

◆ addTermsLast()

void regina::GroupExpression::addTermsLast ( GroupExpression  word)
inline

Multiplies this expression on the right by the given word.

This expression will be modified directly.

Parameters
wordthe word to multiply with this expression.

◆ countTerms()

size_t regina::GroupExpression::countTerms ( ) const
inline

Returns the number of terms in this expression.

For instance, the expression g1^2 g3^-1 g6 contains three terms. See also wordLength().

Returns
the number of terms.

◆ cycleLeft()

void regina::GroupExpression::cycleLeft ( )

Cycles this word by moving the rightmost term around to the leftmost.

All other terms shift one step to the right.

If the word is of the form g_i1^j1 g_i2^j2 ... g_in^jn, this converts it into the word g_in^jn g_i1^j1 g_i1^j1 ... g_in-1^jn-1.

◆ cycleRight()

void regina::GroupExpression::cycleRight ( )

Cycles this word by moving the leftmost term around to the rightmost.

All other terms shift one step to the left.

If the word is of the form g_i1^j1 g_i2^j2 ... g_in^jn, this converts it into the word g_i2^j2 ... g_in^jn g_i1^j1.

◆ detail()

std::string regina::Output< GroupExpression , supportsUtf8 >::detail ( ) const
inherited

Returns a detailed text representation of this object.

This text may span many lines, and should provide the user with all the information they could want. It should be human-readable, should not contain extremely long lines (which cause problems for users reading the output in a terminal), and should end with a final newline. There are no restrictions on the underlying character set.

Returns
a detailed text representation of this object.

◆ erase()

void regina::GroupExpression::erase ( )
inline

Erases all terms from this this word.

This effectively turns this word into the identity element.

◆ exponent()

long regina::GroupExpression::exponent ( size_t  index) const
inline

Returns the exponent corresonding to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and countTerms()-1 inclusive.
Returns
the requested exponent.

◆ generator()

unsigned long regina::GroupExpression::generator ( size_t  index) const
inline

Returns the generator corresonding to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and countTerms()-1 inclusive.
Returns
the number of the requested generator.

◆ inverse()

GroupExpression regina::GroupExpression::inverse ( ) const

Returns the inverse of this expression.

The terms will be reversed and the exponents negated.

Returns
the inverse of this expression.

◆ invert()

void regina::GroupExpression::invert ( )

Inverts this expression.

Does not allocate or deallocate anything.

◆ isTrivial()

bool regina::GroupExpression::isTrivial ( ) const
inline

Tests whether this is the trivial (unit) word.

No attempt is made to remove redundant terms (so the word g g^-1 will be treated as non-trivial).

Returns
true if and only if this is the trivial word.

◆ operator!=()

bool regina::GroupExpression::operator!= ( const GroupExpression comp) const
inline

Inequality operator.

Checks to see whether or not these two words represent different literal strings.

Parameters
compthe expression to compare against this.
Returns
true if this and the given string literal are not identical.

◆ operator=() [1/2]

GroupExpression & regina::GroupExpression::operator= ( const GroupExpression )
default

Makes this expression a clone of the given expression.

Returns
a reference to this expression.

◆ operator=() [2/2]

GroupExpression & regina::GroupExpression::operator= ( GroupExpression &&  )
defaultnoexcept

Moves the contents of the given expression to this expression.

This is a fast (constant time) operation.

The expression that was passed will no longer be usable.

Returns
a reference to this expression.

◆ operator==()

bool regina::GroupExpression::operator== ( const GroupExpression comp) const
inline

Equality operator.

Checks to see whether or not these two words represent the same literal string.

Parameters
compthe expression to compare against this.
Returns
true if this and the given string literal are identical.

◆ power()

GroupExpression regina::GroupExpression::power ( long  exponent) const

Returns this expression raised to the given power.

The given exponent may be positive, zero or negative.

Parameters
exponentthe power to which this expression should be raised.
Returns
this expression raised to the given power.

◆ relabellingsThisToOther()

std::list< std::map< unsigned long, GroupExpressionTerm > > regina::GroupExpression::relabellingsThisToOther ( const GroupExpression other,
bool  cyclic = false 
) const

Determines whether or not one can relabel the generators in this word to obtain the given other word.

If so, returns a non-empty list of all such relabellings. If not, returns an empty list.

Relabellings are partially-defined permutations on the generator set, also allowing for possible inversions if cyclic is true.

Warning
The API for this class or function has not yet been finalised. This means that the interface may change in new versions of Regina, without maintaining backward compatibility. If you use this class directly in your own code, please check the detailed changelog with each new release to see if you need to make changes to your code.
Todo:
Change this to use less heavyweight types and less deep copying.
Precondition
If cyclic is true, then both this word and other have been cyclically reduced.
Python
Not present.
Parameters
otherthe word to compare against this.
cyclicif false we get a list of exact relabellings from this word to other. If true, it can be up to cyclic permutation and inversion.
Returns
a list of permutations, implemented as maps from generator indices of this word to generator indices of other.

◆ simplify()

bool regina::GroupExpression::simplify ( bool  cyclic = false)

Simplifies this expression.

Adjacent powers of the same generator will be combined, and terms with an exponent of zero will be removed. Note that it is not assumed that the underlying group is abelian.

You may declare that the expression is cyclic, in which case it is assumed that terms may be moved from the back to the front and vice versa. Thus expression g1 g2 g1 g2 g1 simplifies to g1^2 g2 g1 g2 if it is cyclic, but does not simplify at all if it is not cyclic.

Parameters
cyclictrue if and only if the expression may be assumed to be cyclic.
Returns
true if and only if this expression was changed.

◆ str() [1/2]

std::string regina::Output< GroupExpression , supportsUtf8 >::str ( ) const
inherited

Returns a short text representation of this object.

This text should be human-readable, should use plain ASCII characters where possible, and should not contain any newlines.

Within these limits, this short text ouptut should be as information-rich as possible, since in most cases this forms the basis for the Python __str__() and __repr__() functions.

Python
The Python "stringification" function __str__() will use precisely this function, and for most classes the Python __repr__() function will incorporate this into its output.
Returns
a short text representation of this object.

◆ str() [2/2]

std::string regina::GroupExpression::str ( bool  alphaGen) const
inline

Returns a short text representation of this group expression, with a choice of either numbered generators or alphabetic generators.

If alphaGen is false, the text representation will be of the form g2^4 g13^-5 g4. If alphaGen is true, this routine will assume your word is in an alphabet of no more than 26 letters, and will format the word using lower-case ASCII, i.e., c^4 n^-5 e.

Note that there is also a zero-argument version of str(), inherited through the ShortOutput base class. This zero-argument str() gives the same output as str(false).

Note that generators are numbered starting from 0. This means, for example, that a, b and c correspond to g0, g1 and g2 respectively.

Precondition
If alphaGen is true, the number of generators in the corresponding group must be 26 or fewer.
Parameters
alphaGenindicates whether to use numbered or alphabetic generators, as described above.
Returns
a short text representation of this group expression.

◆ substitute() [1/2]

void regina::GroupExpression::substitute ( const std::vector< GroupExpression > &  expansions,
bool  cyclic = false 
)

Replaces every generator in this expression with the corresponding substitute expression from the given map.

Specifically, each generator i will be replaced with the expression expansions[i].

The expression will be simplified once all substitutions are complete.

Unlike the single-generator verison of substitute(), it is perfectly fine if this GroupExpression object appears in the expansions list, and/or if the same GroupExpression object appears several times in the given list.

Precondition
The length of expansions is at least g+1, where g is the largest generator that appears in this expression. In other words, expansions[i] exists for every generator i that appears in this expression.
Parameters
expansionsthe list of substitutes for all generators in this expression.
cyclictrue if and only if the expression may be assumed to be cyclic; see simplify() for further details.

◆ substitute() [2/2]

bool regina::GroupExpression::substitute ( unsigned long  generator,
const GroupExpression expansion,
bool  cyclic = false 
)

Replaces every occurrence of the given generator with the given substitute expression.

If the given generator was found, the expression will be simplified once the substitution is complete.

Precondition
The given expansion is not the same GroupExpression object as this.
Parameters
generatorthe generator to be replaced.
expansionthe substitute expression that will replace every occurrence of the given generator.
cyclictrue if and only if the expression may be assumed to be cyclic; see simplify() for further details.
Returns
true if and only if any substitutions were made.

◆ swap()

void regina::GroupExpression::swap ( GroupExpression other)
inlinenoexcept

Swaps the contents of this and the given expression.

Parameters
otherthe expression whose contents should be swapped with this.

◆ term() [1/2]

GroupExpressionTerm & regina::GroupExpression::term ( size_t  index)

Returns the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and countTerms()-1 inclusive.
Returns
the requested term.

◆ term() [2/2]

const GroupExpressionTerm & regina::GroupExpression::term ( size_t  index) const

Returns a constant reference to the term at the given index in this expression.

Index 0 represents the first term, index 1 represents the second term and so on.

Warning
This routine is O(n) where n is the number of terms in this expression.
Parameters
indexthe index of the term to return; this must be between 0 and countTerms()-1 inclusive.
Returns
the requested term.

◆ terms() [1/2]

std::list< GroupExpressionTerm > & regina::GroupExpression::terms ( )
inline

Returns the list of terms in this expression.

These are the actual terms stored internally; any modifications made to this list will show up in the expression itself.

For instance, the expression g1^2 g3^-1 g6 has list consisting of three terms g1^2, g3^-1 and g6^1 in that order.

Python
The list itself is not returned by reference (instead this routine returns a new Python list). However, the terms within this list are still returned by reference (i.e., you can use the elements of this list to modify each term individually).
Returns
the list of terms.

◆ terms() [2/2]

const std::list< GroupExpressionTerm > & regina::GroupExpression::terms ( ) const
inline

Returns a constant reference to the list of terms in this expression.

For instance, the expression g1^2 g3^-1 g6 has list consisting of three terms g1^2, g3^-1 and g6^1 in that order.

Python
The list itself is not returned by reference (instead this routine returns a new Python list). However, the terms within this list are still returned by reference.
Returns
the list of terms.

◆ tex()

std::string regina::GroupExpression::tex ( ) const

Returns a TeX representation of this expression.

The text representation will be of the form g_2^4 g_{13}^{-5} g_4.

Returns
a TeX representation of this expression.

◆ utf8() [1/2]

std::string regina::Output< GroupExpression , supportsUtf8 >::utf8 ( ) const
inherited

Returns a short text representation of this object using unicode characters.

Like str(), this text should be human-readable, should not contain any newlines, and (within these constraints) should be as information-rich as is reasonable.

Unlike str(), this function may use unicode characters to make the output more pleasant to read. The string that is returned will be encoded in UTF-8.

Returns
a short text representation of this object.

◆ utf8() [2/2]

std::string regina::GroupExpression::utf8 ( bool  alphaGen) const
inline

Returns a short text representation of this group expression using unicode characters, with a choice of either numbered generators or alphabetic generators.

This outputs a similar text representation to str(bool), except that all exponents will be written using superscript characters encoded in UTF-8. See str(bool) for further details.

Note that there is also a zero-argument version of utf8(), inherited through the ShortOutput base class. This zero-argument utf8() gives the same output as utf8(false).

Precondition
If alphaGen is true, the number of generators in the corresponding group must be 26 or fewer.
Parameters
alphaGenindicates whether to use numbered or alphabetic generators, as described above.
Returns
a short text representation of this group expression.

◆ wordLength()

size_t regina::GroupExpression::wordLength ( ) const
inline

Returns the length of the word, i.e.

the number of letters with exponent +1 or -1 for which this word is expressable as a product.

For instance, the expression g1^2 g3^-1 g6 is a word of length four. See also countTerms().

No attempt is made to remove redundant terms (so the word g g^-1 will count as length two).

Returns
the length of the word.

◆ writeTeX()

void regina::GroupExpression::writeTeX ( std::ostream &  out) const

Writes a TeX represesentation of this expression to the given output stream.

The text representation will be of the form g_2^4 g_{13}^{-5} g_4.

Python
Not present. Instead use the variant tex() that takes no arguments and returns a string.
Parameters
outthe output stream to which to write.

◆ writeTextLong()

void regina::ShortOutput< GroupExpression , supportsUtf8 >::writeTextLong ( std::ostream &  out) const
inlineinherited

A default implementation for detailed output.

This routine simply calls T::writeTextShort() and appends a final newline.

Python
Not present. Instead you can call detail() from the subclass T, which returns this output as a string.
Parameters
outthe output stream to which to write.

◆ writeTextShort()

void regina::GroupExpression::writeTextShort ( std::ostream &  out,
bool  utf8 = false,
bool  alphaGen = false 
) const

Writes a short text representation of this object to the given output stream, using either numbered generators or alphabetic generators.

The text representation will be of the form g2^4 g13^-5 g4. If the alphaGen flag is true, it will assume your word is in an alphabet of no more than 26 letters, and will write the word using lower-case ASCII, i.e., c^4 n^-5 e. If the utf8 flag is true, all exponents will be written using superscript characters encoded in UTF-8.

Note that generators are numbered starting from 0. This means, for example, that a, b and c correspond to g0, g1 and g2 respectively.

Precondition
If alphaGen is true, the number of generators in the corresponding group must be 26 or fewer.
Python
Not present. Use str() or utf8() instead.
Parameters
outthe output stream to which to write.
utf8true if exponents should be written using unicode superscript characters, or false if they should be written using a caret (^) symbol.
alphaGenindicates whether to use numbered or alphabetic generators, as described above.

◆ writeXMLData()

void regina::GroupExpression::writeXMLData ( std::ostream &  out) const

Writes a chunk of XML containing this expression.

Python
The argument out should be an open Python file object.
Parameters
outthe output stream to which the XML should be written.

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

Copyright © 1999-2023, The Regina development team
This software is released under the GNU General Public License, with some additional permissions; see the source code for details.
For further information, or to submit a bug or other problem, please contact Ben Burton (bab@maths.uq.edu.au).