DGtal 1.3.0
Loading...
Searching...
No Matches
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 <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

◆ index_t

typedef unsigned int DGtal::OrderedAlphabet::index_t

The index datatype.

Definition at line 82 of file OrderedAlphabet.h.

◆ Integer

Internal integer type to consider in the OrderdAlphabet class.

Definition at line 77 of file OrderedAlphabet.h.

◆ size_t

typedef unsigned int DGtal::OrderedAlphabet::size_t

The size datatype.

Definition at line 87 of file OrderedAlphabet.h.

Constructor & Destructor Documentation

◆ ~OrderedAlphabet()

DGtal::OrderedAlphabet::~OrderedAlphabet ( )

Destructor.

◆ OrderedAlphabet() [1/3]

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

Constructor from letters

Parameters
firstthe first letter of the alphabet.
nbthe number of letters of the alphabet.

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

◆ OrderedAlphabet() [2/3]

DGtal::OrderedAlphabet::OrderedAlphabet ( )
protected

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

◆ OrderedAlphabet() [3/3]

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

Copy constructor.

Parameters
otherthe object to clone. Forbidden by default.

Member Function Documentation

◆ duvalPP()

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.
wa word which starts with a1 or a2 at position s.
sthe starting index in [w].
ethe index after the end in [w] (s<e).

Referenced by testDuvalPP().

◆ duvalPPMod()

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.
wa (cyclic) word which starts with a1 or a2 at position s.
sthe starting index in [w].
ethe index after the end in [w] (s and e arbitrary).

Referenced by testDuvalPPMod().

◆ duvalPPtoDSS()

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.
wa word which starts with a1 or a2 at position s.
sthe starting index in [w].
ethe index after the end in [w] (s<e).

◆ equal()

bool DGtal::OrderedAlphabet::equal ( char  c1,
char  c2 
) const
Parameters
c1a letter in the alphabet
c2another letter in the same alphabet.
Returns
'true' iff c1 == c2

◆ firstLyndonFactor()

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.
wa word
sthe starting index in [w].
ethe index after the end in [w] (s<e).

Referenced by testFLF().

◆ firstLyndonFactorMod()

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.
wa word
sthe starting index in [w].
ethe index after the end in [w] (s and e arbitrary).

◆ isValid()

bool DGtal::OrderedAlphabet::isValid ( ) const

Checks the validity/consistency of the object.

Returns
'true' if the object is valid, 'false' otherwise.

◆ less()

bool DGtal::OrderedAlphabet::less ( char  c1,
char  c2 
) const
Parameters
c1a letter in the alphabet
c2another letter in the same alphabet.
Returns
'true' iff c1 < c2

◆ lessOrEqual()

bool DGtal::OrderedAlphabet::lessOrEqual ( char  c1,
char  c2 
) const
Parameters
c1a letter in the alphabet
c2another letter in the same alphabet.
Returns
'true' iff c1 <= c2

◆ letter()

char DGtal::OrderedAlphabet::letter ( unsigned int  i) const
Parameters
ithe 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).

◆ nextEdge()

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)
wthe input (cyclic) word (may be modified in the process).
sthe 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.

◆ operator=()

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

Assignment.

Parameters
otherthe object to copy.
Returns
a reference on 'this'. Forbidden by default.

◆ order()

unsigned int DGtal::OrderedAlphabet::order ( char  c) const
Parameters
cany valid letter in this alphabet.
Returns
the index of the letter [c] in the order relation, starting from 0 to myNb-1.

◆ orderedAlphabet()

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

◆ reverse()

void DGtal::OrderedAlphabet::reverse ( )

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

◆ reverseAround12()

void DGtal::OrderedAlphabet::reverseAround12 ( )

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

◆ selfDisplay()

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

Writes/Displays the object on an output stream.

Parameters
outthe output stream where the object is written.

◆ shiftLeft()

void DGtal::OrderedAlphabet::shiftLeft ( )

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

◆ shiftRight()

void DGtal::OrderedAlphabet::shiftRight ( )

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

Field Documentation

◆ myFirst

char DGtal::OrderedAlphabet::myFirst
private

the first character.

Definition at line 345 of file OrderedAlphabet.h.

◆ myNb

unsigned int DGtal::OrderedAlphabet::myNb
private

the number of letters.

Definition at line 350 of file OrderedAlphabet.h.

◆ myOrder

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: