Word Class Reference

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

#include <Word.h>

Inheritance diagram for Word:

ObjectOf< WordRep > 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.
Wordoperator *= (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).
Wordoperator^= (const Word &conjugator)
 Conjugate a word by another word (the result is reduced).
Word operator^ (const Word &conjugator) const
Wordoperator^= (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.
Wordpush_back (int gen)
 Multiply the word by a one-letter word defined by gen on the right. The result is being reduced.
Wordpush_front (int gen)
 Multiply the word by a one-letter word defined by gen on the left. The result is being reduced.
Wordpush_back (const Word &w)
 Multiply the word by a word on the right. The result is being reduced.
Wordpush_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 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

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

Cyclically permute the word.

Definition at line 233 of file Word.h.

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

iterator Word::begin  )  [inline]
 

Definition at line 145 of file Word.h.

const_iterator Word::begin  )  const [inline]
 

Definition at line 143 of file Word.h.

Referenced by WordDraw::drawCompressedBraid(), freelyReduce(), and WhiteheadGraph::WhiteheadGraph().

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::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().

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 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().

void Word::cyclicallyReduceWord  )  [inline]
 

Cyclically reduces the Word.

Definition at line 205 of file Word.h.

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

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().

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().

iterator Word::end  )  [inline]
 

Definition at line 146 of file Word.h.

const_iterator Word::end  )  const [inline]
 

Definition at line 144 of file Word.h.

Referenced by WordDraw::drawCompressedBraid(), freelyReduce(), and WhiteheadGraph::WhiteheadGraph().

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

Definition at line 259 of file Word.h.

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

Word Word::freelyReduce iterator  B,
iterator  E
 

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

Word Word::freelyReduce  )  [inline]
 

Freely reduce a word.

Definition at line 149 of file Word.h.

References begin(), and end().

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().

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().

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().

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().

void Word::insert WordIterator  it,
int  g
 

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

template<class ConstIntIterator>
void Word::insert WordIterator  it,
ConstIntIterator  B,
ConstIntIterator  E
 

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

void Word::insert int  pos,
int  g
 

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

template<class ConstIntIterator>
void Word::insert int  pos,
ConstIntIterator  B,
ConstIntIterator  E
 

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

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().

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

Definition at line 263 of file Word.h.

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

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 WordDraw::WordDraw().

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

Compute the minimal equivalent word.

permutableGenerators must be positive.

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 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().

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 [inline]
 

Invert a word (works the same as inverse).

Definition at line 128 of file Word.h.

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

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 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 84 of file Word.h.

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

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

Definition at line 120 of file Word.h.

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^= 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().

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().

Word Word::power int  t  )  const
 

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

Definition at line 327 of file Word.h.

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

Word& Word::push_back const Word w  ) 
 

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

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().

Word& Word::push_front const Word w  ) 
 

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

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().

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\}$.

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().

template<class ConstIntIterator>
void Word::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.

void Word::replace int  pos,
const Generator g
 

Replace a generator at a position pos by g.

void Word::replace WordIterator  it,
const Generator g
 

Replace a generator at a position it by g.

Word Word::segment int  from,
int  to
const [inline]
 

Definition at line 253 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().


Friends And Related Function Documentation

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

Definition at line 315 of file Word.h.

istream& operator>> istream &  is,
Word w
[friend]
 

Definition at line 321 of file Word.h.


The documentation for this class was generated from the following file:
Generated on Sun Dec 3 10:59:06 2006 for CRyptography And Groups (CRAG) by  doxygen 1.4.6