Word Class Reference

Class Word (defines a representation of a Word over a group alphabet)//. More...

#include <Word.h>

Inheritance diagram for Word:

List of all members.

Public Types

typedef ConstWordIterator const_iterator

typedef WordIterator iterator

typedef pair< int, int > PII

Public Member Functions

Word ()

Default constructor (creates the empty word $w = \varepsilon$ ).

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.

template<class IntIterator>

Word (const IntIterator &B, const IntIterator &E)

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 Word &conjugator)

Conjugate a word by another word (the result is reduced).

Word operator^ (const Word &conjugator) const

Word & operator^= (int power)

Conjugate a word by another word (the result is reduced).

Word operator^ (int power) const

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.

void pop_back ()

Remove the last symbol.

void pop_front ()

Remove the first symbol.

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., $cyclicLeftShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_2 \ldots x_{k-1} x_k x_1$ .

void cyclicRightShift ()

Shifts the word one position to the right, i.e., $cyclicRightShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_k x_1 x_2 \ldots x_{k-1}$ .

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 replaceGenerators (const vector< Word > &images) const

Returns a word in which generators are replaced by words.

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 $X = \{x_1,\ldots,x_n\}$ .

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 $X = \{x_1,\ldots,x_n\}$ .

Private Member Functions

ostream & printOn (ostream &os) const

Friends

ostream & operator<< (ostream &os, const Word &w)

istream & operator>> (istream &is, Word &w)

Detailed Description

Class Word (defines a representation of a Word over a group alphabet)//.

A reduced word is the one which does not involve subwords of the type $x x^{-1}$ or $x^{-1} x$ . We represent a reduced word over a group alphabet $X$ as a list of non-trivial integers list< int >. Each generator $x \in X$ is represented by the unique number $n_x$ . For each $x \in X$ it is assumed that $n_{x^{-1}} = -n_x$ .

Definition at line 38 of file Word.h.

Member Typedef Documentation

typedef ConstWordIterator Word::const_iterator

Definition at line 42 of file Word.h.

typedef WordIterator Word::iterator

Definition at line 43 of file Word.h.

typedef pair< int , int > Word::PII

Definition at line 53 of file Word.h.

Constructor & Destructor Documentation

Word::Word ( ) [inline]

Default constructor (creates the empty word $w = \varepsilon$ ).

Definition at line 56 of file Word.h.

Word::Word ( const vector< int > & gens ) [inline]

Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).

Definition at line 58 of file Word.h.

Word::Word ( const list< int > & gens ) [inline]

Cast constructor. Constructs a word by its presentation (if the word defined in gens is not reduced then it reduces it).

Definition at line 60 of file Word.h.

Word::Word ( int g ) [inline]

Cast constructor. Constructs a one letter word.

Definition at line 62 of file Word.h.

template<class IntIterator>

Word::Word	(	const IntIterator &	B,
		const IntIterator &	E
	)			`[inline]`

Definition at line 65 of file Word.h.

Member Function Documentation

bool Word::operator< ( const Word & wr ) const [inline]

Comparison operator.

The result of comparison of $u = u_1 \ldots u_k$ and $v = v_1 \ldots v_m$ is defined by $u<v ~\Leftrightarrow~ k<m ~\vee~ ( k=m ~\wedge~ u_i<v_i \mbox{ where $i$ is the smallest index such that $u_i\ne v_i$})$

Definition at line 82 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

bool Word::operator> ( const Word & wr ) const [inline]

Comparison operator.

Definition at line 84 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

bool Word::operator== ( const Word & wr ) const [inline]

Comparison operator.

Definition at line 86 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

bool Word::operator!= ( const Word & wr ) const [inline]

Comparison operator.

Definition at line 88 of file Word.h.

References ObjectOf< Rep >::look(), and ObjectOf< WordRep >::look().

Word& Word::operator*= ( const Word & w ) [inline]

Multiply the word on the right by another word (the result is reduced).

Definition at line 91 of file Word.h.

References ObjectOf< WordRep >::change(), and ObjectOf< Rep >::look().

Word Word::operator* ( const Word & w ) const [inline]

Multiply two words (the result is reduced).

Definition at line 96 of file Word.h.

Word& Word::operator^= ( const Word & conjugator ) [inline]

Conjugate a word by another word (the result is reduced).

Definition at line 104 of file Word.h.

References ObjectOf< WordRep >::change(), and ObjectOf< Rep >::look().

Word Word::operator^ ( const Word & conjugator ) const [inline]

Definition at line 108 of file Word.h.

Word& Word::operator^= ( int power ) [inline]

Conjugate a word by another word (the result is reduced).

Definition at line 116 of file Word.h.

References ObjectOf< WordRep >::change().

Word Word::operator^ ( int power ) const [inline]

Definition at line 120 of file Word.h.

Word Word::operator- ( ) const [inline]

Invert a word (works the same as inverse).

Reimplemented in ThompsonGroupFNormalForm.

Definition at line 128 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look().

const_iterator Word::begin ( ) const [inline]

Definition at line 143 of file Word.h.

Referenced by BraidDrawPDF::drawCompressedBraid(), WordDraw::drawCompressedBraid(), MaxCommutePartition::findCommutParts(), freelyReduce(), DCBraidReduction::shorten(), and WhiteheadGraph::WhiteheadGraph().

const_iterator Word::end ( ) const [inline]

Definition at line 144 of file Word.h.

Referenced by BraidDrawPDF::drawCompressedBraid(), WordDraw::drawCompressedBraid(), MaxCommutePartition::findCommutParts(), freelyReduce(), DCBraidReduction::shorten(), and WhiteheadGraph::WhiteheadGraph().

iterator Word::begin ( ) [inline]

Definition at line 145 of file Word.h.

iterator Word::end ( ) [inline]

Definition at line 146 of file Word.h.

Word Word::freelyReduce ( ) [inline]

Freely reduce a word.

Definition at line 149 of file Word.h.

References begin(), and end().

Word Word::freelyReduce	(	iterator	B,
		iterator	E
	)

Freely reduce a segment of a word defined by [B,E).

static Word Word::randomWord	(	int	n,
		int	wLen
	)			`[static]`

Generates a pseudo randomly reduced word of the length wLen over the alphabet $X = \{x_1,\ldots,x_n\}$ .

Referenced by RandomPairGenerator::getFalsePair(), and RandomPairGenerator::getTruePair().

static Word Word::randomWord	(	int	n,
		int	wLenMin,
		int	wLenMax
	)			`[static]`

Generates a pseudo randomly reduced word of a length in [wLenMin,wLenMax] and over the alphabet $X = \{x_1,\ldots,x_n\}$ .

const list< int >& Word::getList ( ) const [inline]

Get a constant representation the word.

Definition at line 164 of file Word.h.

References WordRep::getList(), and ObjectOf< WordRep >::look().

Referenced by ThompsonGroupFNormalForm::operator*(), and ThompsonGroupFNormalForm::operator*=().

list< int >& Word::getList ( ) [inline]

Get a representation the word. This allows direct manipulation with the representation (which requires caution).

Definition at line 166 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::getList().

int Word::length ( ) const [inline]

Get the length of the word.

Definition at line 169 of file Word.h.

References WordRep::length(), and ObjectOf< WordRep >::look().

Referenced by UniformPartition::getPartition(), and WordDraw::WordDraw().

Word& Word::push_back ( int gen ) [inline]

Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.

Definition at line 172 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::push_back().

Referenced by DCBraidReduction::shorten().

Word& Word::push_front ( int gen ) [inline]

Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.

Definition at line 174 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::push_front().

Word& Word::push_back ( const Word & w )

Multiply the word by a word on the right. The result is being reduced.

Word& Word::push_front ( const Word & w )

Multiply the word by a word on the left. The result is being reduced.

void Word::pop_back ( ) [inline]

Remove the last symbol.

Definition at line 181 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::pop_back().

void Word::pop_front ( ) [inline]

Remove the first symbol.

Definition at line 183 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::pop_front().

int Word::getPower ( Word & base ) const [inline]

Determines the power of the word (as an element of a free monoid, not as an element of a free group).

Definition at line 187 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::getPower(), and ObjectOf< WordRep >::look().

bool Word::doesContain ( const int & gen ) const [inline]

Checks if the word contains a generator given by gen.

Definition at line 190 of file Word.h.

References WordRep::doesContain(), and ObjectOf< WordRep >::look().

void Word::cyclicLeftShift ( ) [inline]

Shifts the word one position to the left, i.e., $cyclicLeftShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_2 \ldots x_{k-1} x_k x_1$ .

Definition at line 193 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::cyclicLeftShift().

void Word::cyclicRightShift ( ) [inline]

Shifts the word one position to the right, i.e., $cyclicRightShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_k x_1 x_2 \ldots x_{k-1}$ .

Definition at line 195 of file Word.h.

References ObjectOf< WordRep >::change(), and WordRep::cyclicRightShift().

Word Word::cyclicallyReduce ( ) const [inline]

Returns the cyclically reduced word.

Definition at line 198 of file Word.h.

References ObjectOf< Rep >::change().

Referenced by cyclicallyReduce(), and cyclicallyReduceWord().

void Word::cyclicallyReduceWord ( ) [inline]

Cyclically reduces the Word.

Definition at line 205 of file Word.h.

References ObjectOf< WordRep >::change(), and cyclicallyReduce().

Word Word::cyclicallyReduce ( Word & conjugator ) const [inline]

Returns the cyclically reduced word and the corresponding conjugator.

Definition at line 208 of file Word.h.

References ObjectOf< Rep >::change(), and cyclicallyReduce().

void Word::cyclicallyReduceWord ( Word & conjugator ) [inline]

Cyclically reduces the Word and returns the corresponding conjugator.

Definition at line 214 of file Word.h.

References ObjectOf< Rep >::change(), ObjectOf< WordRep >::change(), and cyclicallyReduce().

Word Word::inverse ( ) const [inline]

Invert the word.

Definition at line 219 of file Word.h.

References ObjectOf< Rep >::change(), WordRep::inverse(), and ObjectOf< WordRep >::look().

Word Word::cyclicallyPermute ( int n ) const [inline]

Cyclically permute the word and return the result.

n>0 => left-shift, n<0 => rigth-shift permute.

Definition at line 227 of file Word.h.

References ObjectOf< Rep >::change().

Referenced by _cyclicallyPermute().

Word& Word::_cyclicallyPermute ( int n ) [inline]

Cyclically permute the word.

Definition at line 233 of file Word.h.

References ObjectOf< WordRep >::change(), and cyclicallyPermute().

Word Word::initialSegment ( int len ) const [inline]

Get an initial segment of the word of length len.

Definition at line 239 of file Word.h.

References ObjectOf< Rep >::change().

Word Word::terminalSegment ( int len ) const [inline]

Get a terminal segment of the word of length len.

Definition at line 246 of file Word.h.

References ObjectOf< Rep >::change().

Word Word::segment	(	int	from,
		int	to
	)			const `[inline]`

Definition at line 253 of file Word.h.

References ObjectOf< Rep >::change().

int Word::exponentSum ( const int & gen ) const [inline]

Definition at line 259 of file Word.h.

References WordRep::exponentSum(), and ObjectOf< WordRep >::look().

int Word::isIn ( const int & gen ) const [inline]

Definition at line 263 of file Word.h.

References WordRep::isIn(), and ObjectOf< WordRep >::look().

Word Word::power ( int t ) const

template<class ConstIntIterator>

void Word::insert	(	int	pos,
		ConstIntIterator	B,
		ConstIntIterator	E
	)			`[inline]`

Insert a sequence of generators [B,E) into a word at a position pos.

void Word::insert	(	int	pos,
		int	g
	)

Insert a generator g into a word at a position pos.

template<class ConstIntIterator>

void Word::insert	(	WordIterator	it,
		ConstIntIterator	B,
		ConstIntIterator	E
	)			`[inline]`

Insert a sequence of generators [B,E) into a word before a position it.

void Word::insert	(	WordIterator	it,
		int	g
	)

Insert a generator g into a word before a position it.

void Word::replace	(	WordIterator	it,
		const Generator &	g
	)

Replace a generator at a position it by g.

void Word::replace	(	int	pos,
		const Generator &	g
	)

Replace a generator at a position pos by g.

template<class ConstIntIterator>

void Word::replace	(	WordIterator	it,
		ConstIntIterator	B,
		ConstIntIterator	E
	)			`[inline]`

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 Word::replaceGenerators ( const vector< Word > & images ) const

Returns a word in which generators are replaced by words.

Replace generators with the words (images) contained in the vector

Parameters:

images

Word Word::minimalEquivalentForm	(	const set< int > &	permutableGenerators,
		bool	inverses,
		bool	cyclicPermutations
	)			const

Compute the minimal equivalent word.

permutableGenerators must be positive.

ostream& Word::printOn ( ostream & os ) const [inline, private]

Definition at line 334 of file Word.h.

References InfiniteAlphabet::defaultAlphabet, and Alphabet::printWord().

Friends And Related Function Documentation

ostream& operator<<	(	ostream &	os,
		const Word &	w
	)			`[friend]`

Definition at line 322 of file Word.h.

istream& operator>>	(	istream &	is,
		Word &	w
	)			`[friend]`

Definition at line 328 of file Word.h.

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

Elt/include/Word.h


Public Types
typedef ConstWordIterator	const_iterator
typedef WordIterator	iterator
typedef pair< int, int >	PII
Public Member Functions
	Word ()
	Default constructor (creates the empty word $w = \varepsilon$ ).
	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.
template<class IntIterator>
	Word (const IntIterator &B, const IntIterator &E)
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 Word &conjugator)
	Conjugate a word by another word (the result is reduced).
Word	operator^ (const Word &conjugator) const
Word &	operator^= (int power)
	Conjugate a word by another word (the result is reduced).
Word	operator^ (int power) const
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.
void	pop_back ()
	Remove the last symbol.
void	pop_front ()
	Remove the first symbol.
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., $cyclicLeftShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_2 \ldots x_{k-1} x_k x_1$ .
void	cyclicRightShift ()
	Shifts the word one position to the right, i.e., $cyclicRightShift( x_1 x_2 \ldots x_{k-1} x_k ) = x_k x_1 x_2 \ldots x_{k-1}$ .
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	replaceGenerators (const vector< Word > &images) const
	Returns a word in which generators are replaced by words.
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 $X = \{x_1,\ldots,x_n\}$ .
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 $X = \{x_1,\ldots,x_n\}$ .
Private Member Functions
ostream &	printOn (ostream &os) const
Friends
ostream &	operator<< (ostream &os, const Word &w)
istream &	operator>> (istream &is, Word &w)