#include <Word.h>
Inheritance diagram for Word:
Public Types | |
typedef ConstWordIterator | const_iterator |
typedef WordIterator | iterator |
typedef pair< int, int > | PII |
Public Member Functions | |
Word () | |
Default constructor (creates the empty word ![]() | |
Word (const vector< int > &gens) | |
Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it). | |
Word (const list< int > &gens) | |
Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it). | |
Word (int g) | |
Cast constructor. Constructs a one letter word. | |
bool | operator< (const Word &wr) const |
Comparison operator. | |
bool | operator> (const Word &wr) const |
Comparison operator. | |
bool | operator== (const Word &wr) const |
Comparison operator. | |
bool | operator!= (const Word &wr) const |
Comparison operator. | |
Word & | operator *= (const Word &w) |
Multiply the word on the right by another word. The result is reduced. | |
Word | operator * (const Word &w) const |
Multiply two words. The result is reduced. | |
Word | operator- () const |
Invert a word (works the same as inverse). | |
const_iterator | begin () const |
const_iterator | end () const |
iterator | begin () |
iterator | end () |
Word | freelyReduce () |
Freely reduce a word. | |
Word | freelyReduce (iterator B, iterator E) |
Freely reduce a segment of a word defined by [B,E). | |
const list< int > & | getList () const |
Get a constant representation the word. | |
list< int > & | getList () |
Get a representation the word. This allows direct manipulation with the representation (which requires caution). | |
int | length () const |
Get the length of the word. | |
Word & | push_back (int gen) |
Multiply the word by a one-letter word defined by gen on the right. The result is being reduced. | |
Word & | push_front (int gen) |
Multiply the word by a one-letter word defined by gen on the left. The result is being reduced. | |
Word & | push_back (const Word &w) |
Multiply the word by a word on the right. The result is being reduced. | |
Word & | push_front (const Word &w) |
Multiply the word by a word on the left. The result is being reduced. | |
int | getPower (Word &base) const |
Determines the power of the word (as an element of a free monoid, not as an element of a free group). | |
bool | doesContain (const int &gen) const |
Checks if the word contains a generator given by gen. | |
void | cyclicLeftShift () |
Shifts the word one position to the left, i.e., ![]() | |
void | cyclicRightShift () |
Shifts the word one position to the right, i.e., ![]() | |
Word | cyclicallyReduce () const |
Returns the cyclically reduced word. | |
void | cyclicallyReduceWord () |
Cyclically reduces the Word. | |
Word | cyclicallyReduce (Word &conjugator) const |
Returns the cyclically reduced word and the corresponding conjugator. | |
void | cyclicallyReduceWord (Word &conjugator) |
Cyclically reduces the Word and returns the corresponding conjugator. | |
Word | inverse () const |
Invert the word. | |
Word | cyclicallyPermute (int n) const |
Cyclically permute the word and return the result. | |
Word & | _cyclicallyPermute (int n) |
Cyclically permute the word. | |
Word | initialSegment (int len) const |
Get an initial segment of the word of length len. | |
Word | terminalSegment (int len) const |
Get a terminal segment of the word of length len. | |
Word | segment (int from, int to) const |
int | exponentSum (const int &gen) const |
int | isIn (const int &gen) const |
Word | power (int t) const |
template<class ConstIntIterator> | |
void | insert (int pos, ConstIntIterator B, ConstIntIterator E) |
Insert a sequence of generators [B,E) into a word at a position pos. | |
void | insert (int pos, int g) |
Insert a generator g into a word at a position pos. | |
template<class ConstIntIterator> | |
void | insert (WordIterator it, ConstIntIterator B, ConstIntIterator E) |
Insert a sequence of generators [B,E) into a word before a position it. | |
void | insert (WordIterator it, int g) |
Insert a generator g into a word before a position it. | |
void | replace (WordIterator it, const Generator &g) |
Replace a generator at a position it by g. | |
void | replace (int pos, const Generator &g) |
Replace a generator at a position pos by g. | |
template<class ConstIntIterator> | |
void | replace (WordIterator it, ConstIntIterator B, ConstIntIterator E) |
Replace a subword of a word starting at a position it by a word [B,E). The length of the word does not increase if [B,E) is longer than the terminal segment of the word [it,end()). In that case terminal symbols of [B,E) are ignored. | |
Word | minimalEquivalentForm (const set< int > &permutableGenerators, bool inverses, bool cyclicPermutations) const |
Compute the minimal equivalent word. | |
Static Public Member Functions | |
static Word | randomWord (int n, int wLen) |
Generates a pseudo randomly reduced word of the length wLen over the alphabet ![]() | |
static Word | randomWord (int n, int wLenMin, int wLenMax) |
Generates a pseudo randomly reduced word of a length in [wLenMin,wLenMax] and over the alphabet ![]() | |
Private Member Functions | |
ostream & | printOn (ostream &os) const |
Friends | |
ostream & | operator<< (ostream &os, const Word &w) |
istream & | operator>> (istream &is, Word &w) |
A reduced word is the one which does not involve subwords of the type or
. We represent a reduced word over a group alphabet
as a list of non-trivial integers list< int >. Each generator
is represented by the unique number
. For each
it is assumed that
.
Definition at line 38 of file Word.h.
|
|
|
|
|
|
|
Default constructor (creates the empty word
|
|
Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).
|
|
Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).
|
|
Cast constructor. Constructs a one letter word.
|
|
Cyclically permute the word.
Definition at line 200 of file Word.h. References ObjectOf< WordRep >::change(), and cyclicallyPermute(). |
|
|
|
Definition at line 116 of file Word.h. Referenced by WordDraw::drawCompressedBraid(), freelyReduce(), and WhiteheadGraph::WhiteheadGraph(). |
|
Cyclically permute the word and return the result. n>0 => left-shift, n<0 => rigth-shift permute. Definition at line 194 of file Word.h. References ObjectOf< Rep >::change(). Referenced by _cyclicallyPermute(). |
|
Returns the cyclically reduced word and the corresponding conjugator.
Definition at line 175 of file Word.h. References ObjectOf< Rep >::change(), and cyclicallyReduce(). |
|
Returns the cyclically reduced word.
Definition at line 165 of file Word.h. References ObjectOf< Rep >::change(). Referenced by cyclicallyReduce(), and cyclicallyReduceWord(). |
|
Cyclically reduces the Word and returns the corresponding conjugator.
Definition at line 181 of file Word.h. References ObjectOf< Rep >::change(), ObjectOf< WordRep >::change(), and cyclicallyReduce(). |
|
Cyclically reduces the Word.
Definition at line 172 of file Word.h. References ObjectOf< WordRep >::change(), and cyclicallyReduce(). |
|
Shifts the word one position to the left, i.e.,
Definition at line 160 of file Word.h. References ObjectOf< WordRep >::change(), and WordRep::cyclicLeftShift(). |
|
Shifts the word one position to the right, i.e.,
Definition at line 162 of file Word.h. References ObjectOf< WordRep >::change(), and WordRep::cyclicRightShift(). |
|
Checks if the word contains a generator given by gen.
Definition at line 157 of file Word.h. References WordRep::doesContain(), and ObjectOf< WordRep >::look(). |
|
|
|
Definition at line 117 of file Word.h. Referenced by WordDraw::drawCompressedBraid(), freelyReduce(), and WhiteheadGraph::WhiteheadGraph(). |
|
Definition at line 226 of file Word.h. References WordRep::exponentSum(), and ObjectOf< WordRep >::look(). |
|
Freely reduce a segment of a word defined by [B,E).
|
|
Freely reduce a word.
|
|
Get a representation the word. This allows direct manipulation with the representation (which requires caution).
Definition at line 139 of file Word.h. References ObjectOf< WordRep >::change(), and WordRep::getList(). |
|
Get a constant representation the word.
Definition at line 137 of file Word.h. References WordRep::getList(), and ObjectOf< WordRep >::look(). |
|
Determines the power of the word (as an element of a free monoid, not as an element of a free group).
Definition at line 154 of file Word.h. References ObjectOf< Rep >::change(), WordRep::getPower(), and ObjectOf< WordRep >::look(). |
|
Get an initial segment of the word of length len.
Definition at line 206 of file Word.h. References ObjectOf< Rep >::change(). |
|
Insert a generator g into a word before a position it.
|
|
Insert a sequence of generators [B,E) into a word before a position it.
|
|
Insert a generator g into a word at a position pos.
|
|
Insert a sequence of generators [B,E) into a word at a position pos.
|
|
Invert the word.
Definition at line 186 of file Word.h. References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look(). |
|
Definition at line 230 of file Word.h. References WordRep::isIn(), and ObjectOf< WordRep >::look(). |
|
Get the length of the word.
Definition at line 142 of file Word.h. References WordRep::length(), and ObjectOf< WordRep >::look(). Referenced by WordDraw::WordDraw(). |
|
Compute the minimal equivalent word. permutableGenerators must be positive. |
|
Multiply two words. The result is reduced.
|
|
Multiply the word on the right by another word. The result is reduced.
Definition at line 88 of file Word.h. References ObjectOf< WordRep >::change(), and ObjectOf< Rep >::look(). |
|
Comparison operator.
Definition at line 85 of file Word.h. References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look(). |
|
Invert a word (works the same as inverse).
Definition at line 101 of file Word.h. References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look(). |
|
Comparison operator.
The result of comparison of Definition at line 79 of file Word.h. References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look(). |
|
Comparison operator.
Definition at line 83 of file Word.h. References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look(). |
|
Comparison operator.
Definition at line 81 of file Word.h. References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look(). |
|
|
|
Definition at line 294 of file Word.h. References InfiniteAlphabet::defaultAlphabet, and Alphabet::printWord(). |
|
Multiply the word by a word on the right. The result is being reduced.
|
|
Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.
Definition at line 145 of file Word.h. References ObjectOf< WordRep >::change(), and WordRep::push_back(). |
|
Multiply the word by a word on the left. The result is being reduced.
|
|
Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.
Definition at line 147 of file Word.h. References ObjectOf< WordRep >::change(), and WordRep::push_front(). |
|
Generates a pseudo randomly reduced word of a length in [wLenMin,wLenMax] and over the alphabet
|
|
Generates a pseudo randomly reduced word of the length wLen over the alphabet
Referenced by RandomPairGenerator::getFalsePair(), and RandomPairGenerator::getTruePair(). |
|
Replace a subword of a word starting at a position it by a word [B,E). The length of the word does not increase if [B,E) is longer than the terminal segment of the word [it,end()). In that case terminal symbols of [B,E) are ignored.
|
|
Replace a generator at a position pos by g.
|
|
Replace a generator at a position it by g.
|
|
Definition at line 220 of file Word.h. References ObjectOf< Rep >::change(). |
|
Get a terminal segment of the word of length len.
Definition at line 213 of file Word.h. References ObjectOf< Rep >::change(). |
|
|
|
|