DGtal  0.9.3beta
DGtal::OrderedAlphabet Class Reference

#include <DGtal/base/OrderedAlphabet.h>

## Public Types

typedef int Integer

typedef unsigned int index_t

typedef unsigned int size_t

## Public Member Functions

~OrderedAlphabet ()

OrderedAlphabet (char first, unsigned int nb)

std::string orderedAlphabet () const

void shiftLeft ()

void shiftRight ()

void reverse ()

void reverseAround12 ()

unsigned int order (char c) const

char letter (unsigned int i) const

bool less (char c1, char c2) const

bool lessOrEqual (char c1, char c2) const

bool equal (char c1, char c2) const

void firstLyndonFactor (size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const

void firstLyndonFactorMod (size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const

bool duvalPP (size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const

bool duvalPPMod (size_t &len, size_t &nb, const std::string &w, index_t s, index_t e) const

bool duvalPPtoDSS (size_t &len, size_t &nb, unsigned int &n1, unsigned int &n2, unsigned int &Lf1, unsigned int &Lf2, const std::string &w, index_t s, index_t e) const

size_t nextEdge (size_t &nb_a1, size_t &nb_a2, std::string &w, index_t &s, bool &cvx)

void selfDisplay (std::ostream &out) const

bool isValid () const

## Protected Member Functions

OrderedAlphabet ()

## Private Member Functions

OrderedAlphabet (const OrderedAlphabet &other)

OrderedAlphabetoperator= (const OrderedAlphabet &other)

## Private Attributes

char myFirst

unsigned int myNb

unsigned int * myOrder

## Detailed Description

Aim: Describes an alphabet over an interval of (ascii) letters, where the lexicographic order can be changed (shifted, reversed, ...). Useful for the arithmetic minimum length polygon (AMLP).

Description of class 'OrderedAlphabet'

Standard operators '<' and '<=' compares letters using their ascii codes. In order to compare letters with respect to an 'OrderedAlphabet', one uses the classe's functions 'less' and 'lessOrEqual'.

Definition at line 69 of file OrderedAlphabet.h.

## Member Typedef Documentation

 typedef unsigned int DGtal::OrderedAlphabet::index_t

The index datatype.

Definition at line 82 of file OrderedAlphabet.h.

 typedef int DGtal::OrderedAlphabet::Integer

Internal integer type to consider in the OrderdAlphabet class.

Definition at line 77 of file OrderedAlphabet.h.

 typedef unsigned int DGtal::OrderedAlphabet::size_t

The size datatype.

Definition at line 87 of file OrderedAlphabet.h.

## Constructor & Destructor Documentation

 DGtal::OrderedAlphabet::~OrderedAlphabet ( )

Destructor.

 DGtal::OrderedAlphabet::OrderedAlphabet ( char first, unsigned int nb )

Constructor from letters

Parameters
 first the first letter of the alphabet. nb the number of letters of the alphabet.

Exemple: OrderedAlphabet( '0', 4 ) defines the alphabet for 4-connected freeman chains.

 DGtal::OrderedAlphabet::OrderedAlphabet ( )
protected

Constructor. Forbidden by default (protected to avoid g++ warnings).

 DGtal::OrderedAlphabet::OrderedAlphabet ( const OrderedAlphabet & other )
private

Copy constructor.

Parameters
 other the object to clone. Forbidden by default.

## Member Function Documentation

 bool DGtal::OrderedAlphabet::duvalPP ( size_t & len, size_t & nb, const std::string & w, index_t s, index_t e ) const

Adaptation of Duval's algorithm to extract the first Lyndon factor (FLF). Whilst scanning the Lyndon factor, it also checks whether it is a Christoffel word or not. It returns 'true' if the FLF is indeed a Christoffel word, otherwise returns false. It starts the extraction at position [s] in the word [w].

The alphabet takes the form a0 < a1 < a2 < ... < an-1. [w] starts with a1 or a2 at position s.

See [Provencal, Lachaud 2009].

Parameters
 len (returns) the length of the primitive Lyndon factor (which starts at position s). nb (returns) the number of times the Lyndon factor appears. w a word which starts with a1 or a2 at position s. s the starting index in [w]. e the index after the end in [w] (s
 bool DGtal::OrderedAlphabet::duvalPPMod ( size_t & len, size_t & nb, const std::string & w, index_t s, index_t e ) const

Adaptation of Duval's algorithm to extract the first Lyndon factor (FLF). Whilst scanning the Lyndon factor, it also checks whether it is a Christoffel word or not. It returns 'true' if the FLF is indeed a Christoffel word, otherwise returns false. It starts the extraction at position [s] in the cyclic word [w].

The alphabet takes the form a0 < a1 < a2 < ... < an-1. [w] starts with a1 or a2 at position s.

See [Provencal, Lachaud 2009].

Parameters
 len (returns) the length of the primitive Lyndon factor (which starts at position s). nb (returns) the number of times the Lyndon factor appears. w a (cyclic) word which starts with a1 or a2 at position s. s the starting index in [w]. e the index after the end in [w] (s and e arbitrary).
 bool DGtal::OrderedAlphabet::duvalPPtoDSS ( size_t & len, size_t & nb, unsigned int & n1, unsigned int & n2, unsigned int & Lf1, unsigned int & Lf2, const std::string & w, index_t s, index_t e ) const

Second version of the algorithm Duval++ (see OrderedAlphabet::duvalPP), this one dynamically returns extra informations in order to compute leanning points.

Parameters
 len (returns) the length of the primitive Lyndon factor (which starts at position s). nb (returns) the number of times the Lyndon factor appears. n1 (returns) the number of occurrences of the letter a1 in the Lyndon factor n2 (returns) the number of occurrences of the letter a2 in the Lyndon factor Lf1 (returns) the number of occurrences of the letter a1 from 's' to the first lower leaning point. Lf2 (returns) the number of occurrences of the letter a2 from 's' to the first lower leaning point. w a word which starts with a1 or a2 at position s. s the starting index in [w]. e the index after the end in [w] (s
 bool DGtal::OrderedAlphabet::equal ( char c1, char c2 ) const
Parameters
 c1 a letter in the alphabet c2 another letter in the same alphabet.
Returns
'true' iff c1 == c2
 void DGtal::OrderedAlphabet::firstLyndonFactor ( size_t & len, size_t & nb, const std::string & w, index_t s, index_t e ) const

Gives the first lyndon factor of the word [w] starting at position [s] in this alphabet.

Parameters
 len (returns) the length of the primitive Lyndon factor (which starts at position s). nb (returns) the number of times the Lyndon factor appears. w a word s the starting index in [w]. e the index after the end in [w] (s
 void DGtal::OrderedAlphabet::firstLyndonFactorMod ( size_t & len, size_t & nb, const std::string & w, index_t s, index_t e ) const

Gives the first lyndon factor of the cyclic word [w] starting at position [s] in this alphabet.

Parameters
 len (returns) the length of the primitive Lyndon factor (which starts at position s). nb (returns) the number of times the Lyndon factor appears. w a word s the starting index in [w]. e the index after the end in [w] (s and e arbitrary).
 bool DGtal::OrderedAlphabet::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.
 bool DGtal::OrderedAlphabet::less ( char c1, char c2 ) const
Parameters
 c1 a letter in the alphabet c2 another letter in the same alphabet.
Returns
'true' iff c1 < c2
 bool DGtal::OrderedAlphabet::lessOrEqual ( char c1, char c2 ) const
Parameters
 c1 a letter in the alphabet c2 another letter in the same alphabet.
Returns
'true' iff c1 <= c2
 char DGtal::OrderedAlphabet::letter ( unsigned int i ) const
Parameters
 i the index of some letter in the order relation, between 0 and myNb-1.
Returns
c the corresponding letter in this alphabet.

NB: O(nb of letters in the alphabet).

 size_t DGtal::OrderedAlphabet::nextEdge ( size_t & nb_a1, size_t & nb_a2, std::string & w, index_t & s, bool & cvx )

Extracts the next edge of the minimum length polygon starting from position [s] on the word [w]. The alphabet may be modified (reversed or shifted). The output alphabet is some a0 < a1 < a2 < ...

Parameters
 nb_a1 (returns) the number of letters a1 in the extracted edge (a1 in the output alphabet) nb_a2 (returns) the number of letters a2 in the extracted edge (a2 in the output alphabet) w the input (cyclic) word (may be modified in the process). s the starting point in the word (updated). cvx (updates) this boolean is flipped only if a change of convexity is detected.
Returns
the number of letters of the extracted edge.
 OrderedAlphabet& DGtal::OrderedAlphabet::operator= ( const OrderedAlphabet & other )
private

Assignment.

Parameters
 other the object to copy.
Returns
a reference on 'this'. Forbidden by default.
 unsigned int DGtal::OrderedAlphabet::order ( char c ) const
Parameters
 c any valid letter in this alphabet.
Returns
the index of the letter [c] in the order relation, starting from 0 to myNb-1.
 std::string DGtal::OrderedAlphabet::orderedAlphabet ( ) const
Returns
the current ordered alphabet.
 void DGtal::OrderedAlphabet::reverse ( )

Reverse the order a0 < a1 < ... < an to an < ... < a1 < a0

 void DGtal::OrderedAlphabet::reverseAround12 ( )

Reverse the order a0 < a1 < ... < an to a3 < a2 < a1 < a0 < an < ...

 void DGtal::OrderedAlphabet::selfDisplay ( std::ostream & out ) const

Writes/Displays the object on an output stream.

Parameters
 out the output stream where the object is written.
 void DGtal::OrderedAlphabet::shiftLeft ( )

Shift a0 < a1 < ... < an to a1 < ... < an < a0

 void DGtal::OrderedAlphabet::shiftRight ( )

Shift a0 < a1 < ... < an to an < a0 < ... < an-1

## Field Documentation

 char DGtal::OrderedAlphabet::myFirst
private

the first character.

Definition at line 345 of file OrderedAlphabet.h.

 unsigned int DGtal::OrderedAlphabet::myNb
private

the number of letters.

Definition at line 350 of file OrderedAlphabet.h.

 unsigned int* DGtal::OrderedAlphabet::myOrder
private

the order relation, given by the isomorphism with 0..myNb-1.

Definition at line 355 of file OrderedAlphabet.h.

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