DGtal: 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)

OrderedAlphabet &	operator= (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

typedef int DGtal::OrderedAlphabet::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

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.

◆ 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

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

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

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

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

◆ equal()

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

◆ 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.
w	a word
s	the starting index in [w].
e	the 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.
w	a word
s	the starting index in [w].
e	the 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

c1	a letter in the alphabet
c2	another letter in the same alphabet.

Returns: 'true' iff c1 < c2

◆ lessOrEqual()

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

◆ letter()

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

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

◆ operator=()

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

private

Assignment.

Parameters

other the object to copy.

Returns: a reference on 'this'. Forbidden by default.

◆ order()

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.

◆ 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

out	the 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:

OrderedAlphabet.h

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ index_t

◆ Integer

◆ size_t

Constructor & Destructor Documentation

◆ ~OrderedAlphabet()

◆ OrderedAlphabet() [1/3]

◆ OrderedAlphabet() [2/3]

◆ OrderedAlphabet() [3/3]

Member Function Documentation

◆ duvalPP()

◆ duvalPPMod()

◆ duvalPPtoDSS()

◆ equal()

◆ firstLyndonFactor()

◆ firstLyndonFactorMod()

◆ isValid()

◆ less()

◆ lessOrEqual()

◆ letter()

◆ nextEdge()

◆ operator=()

◆ order()

◆ orderedAlphabet()

◆ reverse()

◆ reverseAround12()

◆ selfDisplay()

◆ shiftLeft()

◆ shiftRight()

Field Documentation

◆ myFirst

◆ myNb

◆ myOrder