#include <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'

Definition at line 64 of file OrderedAlphabet.h.

Member Typedef Documentation

typedef unsigned int DGtal::OrderedAlphabet::index_t

The index datatype.

Definition at line 77 of file OrderedAlphabet.h.

typedef int DGtal::OrderedAlphabet::Integer

Internal integer type to consider in the OrderdAlphabet class.

Definition at line 72 of file OrderedAlphabet.h.

typedef unsigned int DGtal::OrderedAlphabet::size_t

The size datatype.

Definition at line 82 of file OrderedAlphabet.h.

Constructor & Destructor Documentation

DGtal::OrderedAlphabet::~OrderedAlphabet ( )

Destructor.

Definition at line 48 of file OrderedAlphabet.cpp.

{
  if ( myOrder != 0 )
    delete[ ] myOrder;
}

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

inline

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.

Definition at line 54 of file OrderedAlphabet.ih.

References myNb, and myOrder.

  : myFirst( first ), myNb( nb )
{
  myOrder = new unsigned int[ nb ];
  ASSERT( ( myOrder != 0 ) 
          && "[DGtal::OrderedAlphabet::OrderedAlphabet( char first, int nb )] error in new: no memory left ?" );
  for ( unsigned int i = 0; i < myNb; ++i )
    myOrder[ i ] = i;
}

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

Definition at line 218 of file OrderedAlphabet.cpp.

{
  ASSERT( ( order( w[ s ] ) == 1 ) || ( order( w[ s ] ) == 2 ) );
  index_t i = s;
  index_t j = s+1;
  index_t p = s;
  index_t q = s+1;
  while ( ( j < e ) && ( lessOrEqual( w[ i ], w[ j ] ) ) )
  {
    if ( equal( w[ i ], w[ j ] ) )
    {
      if ( j == q ) 
        q += (p-s+1);
      ++i;
    }
    else
    {
      if ( ( j != q ) || ( order ( w[ j ] ) != 2 ) )
      {
        len = j-s; nb = 0;
        return false;
      }
      index_t tmp = p; 
      p = q;
      q += q - tmp;
      i = s;
    }
    ++j;
  }
  len = (size_t) j - i;
  nb = ( (size_t) (j-s) ) / len;
  return true;
}

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

Definition at line 378 of file OrderedAlphabet.cpp.

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

{
  ASSERT( ( order( w[ s ] ) == 1 )
          || ( order( w[ s ] ) == 2 ) );
  size_t modulo = (DGtal::OrderedAlphabet::size_t)w.size();
  ModuloComputer< Integer > mc( modulo );
  ModuloComputer< Integer >::UnsignedInteger i = s;
  index_t j = mc.next( s );
  unsigned int p = 1;
  unsigned int q = 2;
  while ( ( j != e ) && ( lessOrEqual( w[ i ], w[ j ] ) ) )
    {
      // cerr << "i=" << i << " j=" << j << " p=" << p << " q=" << q << endl;
      if ( equal( w[ i ], w[ j ] ) )
  {
    if ( j == mc.cast( s + q - 1 ) )
      q += p;
    mc.increment( i );
  }
      else 
  {
    if ( ( j != mc.cast( s + q - 1 ) ) || ( order ( w[ j ] ) != 2 ) )
      {
        len = j; nb = 0;
        return false;
      }
    unsigned int tmp = p; 
    p = q;
    q += q - tmp;
    i = s;
  }
      mc.increment( j );
    }
  len = j >= i ? (size_t) ( j - i )
    : (size_t) ( j + modulo - i );
  nb = ( (size_t) ( ( j + modulo - s ) % modulo ) ) / len;
  return true;
}

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

bool convex;

Definition at line 277 of file OrderedAlphabet.cpp.

{
  ASSERT( ( order( w[ s ] ) == 1 ) || ( order( w[ s ] ) == 2 ) );
  index_t i = s;
  index_t j = s+1;
  index_t p = s;
  index_t q = s+1;
  unsigned int slope1 = (order( w[ i ] ) == 1) ? 1 : 0;
  unsigned int slope2 = (order( w[ i ] ) == 2) ? 1 : 0;
  lf1 = n1 = slope1;
  lf2 = n2 = slope2;
  nb = 1;
  //cerr << "input : " << w << endl;
  
  // Convex is not used so I comment it
  while ( ( j < e ) && ( lessOrEqual( w[ i ], w[ j ] ) ) ) {
    //cerr << "i=" << i << " j=" << j << " p=" << p << " q=" 
    //  << q << " nb=" << nb << " n1=" << n1 << " n2=" << n2 
    //  << " lf1=" << lf1 << " lf2=" << lf2 << endl;g
    //This 'if/else if' is added to compute the vector defined by
    //the Christoffel word, this is usefull in order to compute the
    //leaning points.
    if (order( w[ j ] ) == 1)
      ++slope1;
    else if (order( w[ j ] ) == 2)
      ++slope2;
    if ( equal( w[ i ], w[ j ] ) ) {
      if ( j == q ) {
        q += (p-s+1);
      //A repetition is read when j==s+(nb+1)*(p-s+1)-1
      } 
      if ( j == nb * (p-s+1) + p ) {
        ++nb;
      }
      ++i;
    } else {
      if ( ( j != q ) || ( order ( w[ j ] ) != 2 ) ) {
        //   convex = false;
        break;
      }
      index_t tmp = p; 
      p = q;
      q += q - tmp;
      i = s;
      // Extra information to compute the leaning points
      lf1 = lf1 + (nb-1)*n1;
      lf2 = lf2 + (nb-1)*n2;
      n1 = slope1;
      n2 = slope2;
      nb = 1;
    }
    ++j;
  }
  len = (size_t) j - i;
  //cerr << "Termine" << endl;
  //cerr << "i=" << i << " j=" << j << " p=" << p << " q=" 
  //  << q << " nb=" << nb << " n1=" << n1 << " n2=" << n2 
  //  << " lf1=" << lf1 << " lf2=" << lf2 << endl;
  if ( nb != (size_t) (j-s) / len)
    cout << "ASSERT(" << nb << " == (" << j << "-" << s << ") / "<<len << ")" << endl;
  ASSERT( nb == (size_t) (j-s) / len);
  //nb = (size_t) (j-s) / len;
  return true;
}

bool DGtal::OrderedAlphabet::equal	(	char	c1,
		char	c2
	)		const

inline

Parameters:

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

Returns:: 'true' iff c1 == c2

Definition at line 131 of file OrderedAlphabet.ih.

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

Definition at line 152 of file OrderedAlphabet.cpp.

{
  index_t i = s;
  index_t j = s+1;
  while ( ( j < e ) && ( lessOrEqual( w[ i ], w[ j ] ) ) )
    {
      if ( equal( w[ i ], w[ j ] ) )
  ++i;
      else 
  i = s;
      ++j;
    }
  len = (size_t) j - i;
  nb = ( (size_t) ( j - s ) ) / len;
}

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

Definition at line 186 of file OrderedAlphabet.cpp.

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

{
  size_t modulo = (DGtal::OrderedAlphabet::size_t)w.size();
  ModuloComputer< Integer > mc( modulo );
  index_t i = s;
  index_t j = mc.next( s );
  while ( ( j != e ) && ( lessOrEqual( w[ i ], w[ j ] ) ) )
    {
      if ( equal( w[ i ], w[ j ] ) )
  mc.increment( i );
      else 
  i = s;
      mc.increment( j );
    }
  len = j >= i ? (size_t) ( j - i )
    : (size_t) ( j + modulo - i );
  nb = ( (size_t) ( ( j + modulo - s ) % modulo ) ) / len;
}

bool DGtal::OrderedAlphabet::isValid ( ) const

Checks the validity/consistency of the object.

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

Definition at line 439 of file OrderedAlphabet.cpp.

{
    return true;
}

bool DGtal::OrderedAlphabet::less	(	char	c1,
		char	c2
	)		const

inline

Parameters:

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

Returns:: 'true' iff c1 < c2

Definition at line 107 of file OrderedAlphabet.ih.

{
  return myOrder[ c1 - myFirst ] < myOrder[ c2 - myFirst ];
}

bool DGtal::OrderedAlphabet::lessOrEqual	(	char	c1,
		char	c2
	)		const

inline

Parameters:

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

Returns:: 'true' iff c1 <= c2

Definition at line 119 of file OrderedAlphabet.ih.

{
  return myOrder[ c1 - myFirst ] <= myOrder[ c2 - myFirst ];
}

char DGtal::OrderedAlphabet::letter ( unsigned int i ) const

inline

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

Definition at line 90 of file OrderedAlphabet.ih.

{
  ASSERT( i < myNb );
  for ( unsigned int j = 0; j < myNb; ++j )
    if ( myOrder[ j ] == i )
      return myFirst + j;
  return myFirst;
}

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.

Definition at line 470 of file OrderedAlphabet.cpp.

{
  ModuloComputer< Integer > mc( (const unsigned int)w.size() );
  size_t l;
  size_t len;
  size_t nb;
  bool inC = duvalPPMod( len, nb, w, s, s );
  if ( ! inC ) 
    // case : change of convexity
    {
//       cerr << "Convexity change" <<  orderedAlphabet() ;
//       cerr << " (" << w[ len ] << "==" << letter( 2 ) << ")";
      // JOL : temporary change of letter w[ s ]
      char tmp = w[ s ];
      index_t tmp_s = s;
      w[ s ] = letter( 2 ); // a3
      this->reverseAround12();
      cvx = ! cvx;
//       cerr << " => " << orderedAlphabet() << endl;
      l = nextEdge( nb_a1, nb_a2, w, s, cvx );
      // JOL : former letter is put back in string.
      w[ tmp_s ] = tmp;
    }
  else if ( ( len == 1 ) && ( order( w[ s ] ) == 1 ) ) 
    // case u=a1 => Quadrant change
    {
//       cerr << "Quadrant change " << orderedAlphabet() ;
      this->shiftRight();
//       cerr << " => " << orderedAlphabet() << endl;
      s = mc.cast( s + nb );
      nb_a1 = 0;
      nb_a2 = nb - 1;
      l = nb;
    }
  else 
    { // standard (convex) case.
//       cerr << "standard (convex) case " << orderedAlphabet() << endl;
      l = len * nb;
      char a2 = letter( 2 ); 
      nb_a1 = len;
      nb_a2 = 0;
      index_t ss = s;
      s = mc.cast( s + l );
      while ( len != 0 )
  {
    if ( w[ ss ] == a2 ) ++nb_a2;
    mc.increment( ss );
    --len;
  }
      nb_a1 -= nb_a2;
      nb_a1 *= nb;
      nb_a2 *= nb;
    }
  return l;
}

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

inline

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.

Definition at line 73 of file OrderedAlphabet.ih.

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

{
  ASSERT( ( c - myFirst ) < (int) myNb 
          && "[DGtal::OrderedAlphabet::order( char c )] invalid letter." );
  return myOrder[ c - myFirst ];
}

string DGtal::OrderedAlphabet::orderedAlphabet ( ) const

Returns:: the current ordered alphabet.

Definition at line 58 of file OrderedAlphabet.cpp.

{
  char *tbl;
  tbl = (char *)malloc((myNb + 1)*sizeof(char));
  for ( unsigned int i = 0; i < myNb; ++i )
    {
      tbl[ myOrder[ i ] ] = myFirst + i;
    }
  tbl[ myNb ] = '\0';
  string s( tbl );
  free(tbl);
  return s;
}

void DGtal::OrderedAlphabet::reverse ( )

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

Definition at line 108 of file OrderedAlphabet.cpp.

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

{
  unsigned int* p = myOrder;
  unsigned int* q = myOrder + myNb;
  while ( p != q )
    {
      *p = myNb - 1 - *p;
      ++p;
    }
}

void DGtal::OrderedAlphabet::reverseAround12 ( )

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

Definition at line 123 of file OrderedAlphabet.cpp.

{
  unsigned int* p = myOrder;
  unsigned int* q = myOrder + myNb;
  while ( p != q )
    {
      *p = ( myNb + 3 - *p ) % myNb;
      ++p;
    }
}

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.

Definition at line 428 of file OrderedAlphabet.cpp.

{
    out << "[OrderedAlphabet]";
    out << " " << orderedAlphabet() << endl;
}

void DGtal::OrderedAlphabet::shiftLeft ( )

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

Definition at line 76 of file OrderedAlphabet.cpp.

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

{
  unsigned int* p = myOrder;
  unsigned int* q = myOrder + myNb;
  while ( p != q )
    {
      unsigned int k = *p;
      *p = ( k == 0 ) ? myNb - 1 : k - 1; 
      ++p;
    }
}

void DGtal::OrderedAlphabet::shiftRight ( )

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

Definition at line 92 of file OrderedAlphabet.cpp.

{
  unsigned int* p = myOrder;
  unsigned int* q = myOrder + myNb;
  while ( p != q )
    {
      unsigned int k = *p + 1;
      *p = ( k == myNb ) ? 0 : k; 
      ++p;
    }
}

Field Documentation

char DGtal::OrderedAlphabet::myFirst

private

the first character.

Definition at line 340 of file OrderedAlphabet.h.

unsigned int DGtal::OrderedAlphabet::myNb

private

the number of letters.

Definition at line 345 of file OrderedAlphabet.h.

Referenced by OrderedAlphabet().

unsigned int* DGtal::OrderedAlphabet::myOrder

private

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

Definition at line 350 of file OrderedAlphabet.h.

Referenced by OrderedAlphabet().

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

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation