Public Types | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes

DGtal::OrderedAlphabet Class Reference

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

#include <OrderedAlphabet.h>

Public Types

typedef int Integer
typedef unsigned int index_t
typedef unsigned int size_t

Public Member Functions

 ~OrderedAlphabet ()
INLINE OrderedAlphabet (char first, unsigned int nb)
std::string orderedAlphabet () const
void shiftLeft ()
void shiftRight ()
void reverse ()
void reverseAround12 ()
INLINE unsigned int order (char c) const
INLINE char letter (unsigned int i) const
INLINE bool less (char c1, char c2) const
INLINE bool lessOrEqual (char c1, char c2) const
INLINE 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
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'


Member Typedef Documentation

typedef unsigned int DGtal::OrderedAlphabet::index_t

The index datatype.

Internal integer type to consider in the OrderdAlphabet class.

typedef unsigned int DGtal::OrderedAlphabet::size_t

The size datatype.


Constructor & Destructor Documentation

DGtal::OrderedAlphabet::~OrderedAlphabet (  ) 

Destructor.

References myOrder.

INLINE 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<e).

References ASSERT.

Referenced by testDuvalPP().

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

References ASSERT, DGtal::ModuloComputer< TInteger >::cast(), equal(), DGtal::ModuloComputer< TInteger >::increment(), lessOrEqual(), DGtal::ModuloComputer< TInteger >::next(), and order().

Referenced by nextEdge(), and testDuvalPPMod().

INLINE 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

Referenced by duvalPPMod().

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

Referenced by testFLF().

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

References DGtal::ModuloComputer< TInteger >::increment(), and DGtal::ModuloComputer< TInteger >::next().

bool DGtal::OrderedAlphabet::isValid (  )  const

Checks the validity/consistency of the object.

Returns:
'true' if the object is valid, 'false' otherwise.
INLINE 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
INLINE 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

Referenced by duvalPPMod().

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

Referenced by nextEdge().

DGtal::OrderedAlphabet::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:
(returns) the number of letters a1 in the extracted edge (a1 in the output alphabet)
(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.

References duvalPPMod(), letter(), order(), reverseAround12(), and shiftRight().

OrderedAlphabet& DGtal::OrderedAlphabet::operator= ( const OrderedAlphabet other  )  [private]

Assignment.

Parameters:
other the object to copy.
Returns:
a reference on 'this'. Forbidden by default.
INLINE 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.

Referenced by duvalPPMod(), DGtal::FreemanChain< TInteger >::findQuadrantChange(), DGtal::FreemanChain< TInteger >::findQuadrantChange4(), and nextEdge().

string DGtal::OrderedAlphabet::orderedAlphabet (  )  const
Returns:
the current ordered alphabet.

References myFirst, myNb, and myOrder.

Referenced by selfDisplay().

void DGtal::OrderedAlphabet::reverse (  ) 

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

References myNb, and myOrder.

Referenced by DGtal::FreemanChain< TInteger >::findQuadrantChange(), and DGtal::FreemanChain< TInteger >::findQuadrantChange4().

void DGtal::OrderedAlphabet::reverseAround12 (  ) 

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

References myNb, and myOrder.

Referenced by nextEdge().

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.

References orderedAlphabet().

void DGtal::OrderedAlphabet::shiftLeft (  ) 

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

References myNb, and myOrder.

Referenced by DGtal::FreemanChain< TInteger >::findQuadrantChange(), and DGtal::FreemanChain< TInteger >::findQuadrantChange4().

void DGtal::OrderedAlphabet::shiftRight (  ) 

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

References myNb, and myOrder.

Referenced by nextEdge().


Field Documentation

the first character.

Referenced by orderedAlphabet().

unsigned int DGtal::OrderedAlphabet::myNb [private]

the number of letters.

Referenced by orderedAlphabet(), reverse(), reverseAround12(), shiftLeft(), and shiftRight().

unsigned int* DGtal::OrderedAlphabet::myOrder [private]

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

Referenced by orderedAlphabet(), reverse(), reverseAround12(), shiftLeft(), shiftRight(), and ~OrderedAlphabet().


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