#include <LighterSternBrocot.h>

Collaboration diagram for DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction:

Public Types
typedef TInteger	Integer
typedef TQuotient	Quotient
typedef LighterSternBrocot < TInteger, TQuotient, TMap >	SternBrocotTree
typedef SternBrocotTree::Fraction	Self
typedef NumberTraits< Integer > ::UnsignedVersion	UnsignedInteger
typedef std::pair< Quotient, Quotient >	Value
typedef std::vector< Quotient >	CFracSequence
typedef InputIteratorWithRankOnSequence < CFracSequence, Quotient >	ConstIterator
typedef Value	value_type
typedef ConstIterator	const_iterator
typedef const value_type &	const_reference

Public Member Functions
	Fraction (Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
	Fraction (Node *sb_node=0, bool sup1=false)
	Fraction (const Self &other)
Self &	operator= (const Self &other)
bool	null () const
Integer	p () const
Integer	q () const
Quotient	u () const
Quotient	k () const
bool	isSup1 () const
Quotient	trueK () const
Fraction	left () const
Fraction	right () const
bool	even () const
bool	odd () const
Fraction	ancestor () const
bool	isAncestorDirect () const
Fraction	father () const
Fraction	father (Quotient m) const
Fraction	previousPartial () const
Fraction	inverse () const
Fraction	partial (Quotient kp) const
Fraction	reduced (Quotient i) const
void	push_back (const std::pair< Quotient, Quotient > &quotient)
void	pushBack (const std::pair< Quotient, Quotient > &quotient)
void	getSplit (Fraction &f1, Fraction &f2) const
void	getSplitBerstel (Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
void	getCFrac (std::vector< Quotient > &quotients) const
bool	equals (Integer p1, Integer q1) const
bool	lessThan (Integer p1, Integer q1) const
bool	moreThan (Integer p1, Integer q1) const
bool	operator== (const Fraction &other) const
bool	operator!= (const Fraction &other) const
bool	operator< (const Fraction &other) const
bool	operator> (const Fraction &other) const
void	selfDisplay (std::ostream &out) const
ConstIterator	begin () const
ConstIterator	end () const

Protected Member Functions
Fraction	child (Quotient v) const
Fraction	origin () const
Fraction	next (Quotient v) const

Private Attributes
Node *	myNode
bool	mySup1

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
class DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction

This fraction is a model of CPositiveIrreducibleFraction.

It represents a positive irreducible fraction, i.e. some p/q qith gcd(p,q)=1. It is an inner class of LighterSternBrocot. This representation of a fraction is simply a pointer to the corresponding node in this tree, plus a boolean indicating if it is bigger than 1/1.

Definition at line 217 of file LighterSternBrocot.h.

Member Typedef Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef std::vector<Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::CFracSequence

Definition at line 225 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef ConstIterator DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::const_iterator

Definition at line 230 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef const value_type& DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::const_reference

Definition at line 231 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef InputIteratorWithRankOnSequence<CFracSequence,Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::ConstIterator

Definition at line 226 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TInteger DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Integer

Definition at line 219 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef TQuotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Quotient

Definition at line 220 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef SternBrocotTree::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Self

Definition at line 222 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef LighterSternBrocot<TInteger, TQuotient, TMap> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::SternBrocotTree

Definition at line 221 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef NumberTraits<Integer>::UnsignedVersion DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::UnsignedInteger

Definition at line 223 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef std::pair<Quotient, Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Value

Definition at line 224 of file LighterSternBrocot.h.

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

typedef Value DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::value_type

Definition at line 229 of file LighterSternBrocot.h.

Constructor & Destructor Documentation

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction	(	Integer	aP,
		Integer	aQ,
		Fraction	start = `SternBrocotTree::zeroOverOne()`
	)

inline

Creates the fraction aP/aQ. Complexity is in O(n) where n is the depth of continued fraction of aP/aQ.

Parameters:

aP	the numerator (>=0)
aQ	the denominator (>=0)
start	(optional) unused in this representation.

Definition at line 148 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::IntegerComputer< TInteger >::getEuclideanDiv(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::operator=(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne().

{
  if ( ( aP == NumberTraits<Integer>::ZERO ) &&
       ( aQ == NumberTraits<Integer>::ONE ) ) 
    this->operator=( zeroOverOne() );
  else
    {
      bool sup1 = aP >= aQ;
      if ( ! sup1 ) std::swap( aP, aQ );
      Node* node = instance().myOneOverZero;
      Integer _quot, _rem;
      IntegerComputer<Integer> ic;
      ic.getEuclideanDiv( _quot, _rem, aP, aQ );
      Quotient v = NumberTraits<Integer>::castToInt64_t( _quot );
      // std::cerr << "[u=" << v << "]";
      aP = aQ;
      aQ = _rem;
      while ( aQ != NumberTraits<Integer>::ZERO )
        {
          node = node->child( v + 1 );
          ic.getEuclideanDiv( _quot, _rem, aP, aQ );
          v = NumberTraits<Integer>::castToInt64_t( _quot );
          // std::cerr << "[u=" << v << "]";
          aP = aQ;
          aQ = _rem;
        }
      myNode = node->child( v );
      mySup1 = sup1;
    }
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction	(	Node *	sb_node = `0`,
		bool	sup1 = `false`
	)

inline

Default constructor.

Parameters:

sb_node	the associated node (or 0 for null fraction).
sup1	when 'false', the fraction is smaller greater than 1/1 and represents q/p.

Definition at line 182 of file LighterSternBrocot.ih.

  : myNode( sb_node ), mySup1( sup1 )
{
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction ( const Self & other )

inline

Copy constructor.

Parameters:

other the object to clone.

Definition at line 190 of file LighterSternBrocot.ih.

  : myNode( other.myNode ), mySup1( other.mySup1 )
{
}

Member Function Documentation

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::ancestor ( ) const

inline

Returns:: the ancestor of this fraction in O(1), ie [u0,...,u_{k-1},uk] => [u0,...,u_{k-1}] if u_{k-1} > 1, => [u0,...,u_{k-2}] otherwise. Equivalent to reduced( 1 ).

Definition at line 424 of file LighterSternBrocot.ih.

{
  return Fraction( myNode->ancestor(), mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::ConstIterator DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::begin ( ) const

inline

Returns:: a const iterator pointing on the beginning of the sequence of quotients of this fraction. NB: \( O(\sum_i u_i) \) operation.

Definition at line 663 of file LighterSternBrocot.ih.

{
  CFracSequence* seq = new CFracSequence;
  this->getCFrac( *seq );
  return ConstIterator( seq, seq->begin() );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::child ( Quotient v ) const

inlineprotected

Returns:: the fraction [u_0, ..., u_n - 1, v] if [u_0, ..., u_n] is the current fraction. Construct it if it does not exist yet.

Definition at line 415 of file LighterSternBrocot.ih.

{
  return Fraction( myNode->child( v ), mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::ConstIterator DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::end ( ) const

inline

Returns:: a const iterator pointing after the end of the sequence of quotients of this fraction. NB: O(1) operation.

Definition at line 674 of file LighterSternBrocot.ih.

{
  static CFracSequence dummy;
  return ConstIterator( 0, dummy.end() );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::equals	(	Integer	p1,
		Integer	q1
	)		const

inline

Parameters:

p1	a numerator.
q1	a denominator.

Returns:: 'true' if this is the fraction p1/q1.

Definition at line 271 of file LighterSternBrocot.ih.

{
  return ( this->p() == p1 ) && ( this->q() == q1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::even ( ) const

inline

Returns:: 'true' if it is an even fraction, i.e. its depth k() is even.

Definition at line 388 of file LighterSternBrocot.ih.

{
  return NumberTraits<Quotient>::even( k() );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::father ( ) const

inline

Returns:: the father of this fraction in O(1), ie [u0,...,uk] => [u0,.. .,uk - 1]

Definition at line 442 of file LighterSternBrocot.ih.

{
  return Fraction( myNode->father(), mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::father ( Quotient m ) const

inline

Parameters:

m	a quotient between 1 and uk-1.

Returns:: the fraction [u_0, ..., u_{n-1},m]

Definition at line 451 of file LighterSternBrocot.ih.

{
  if ( m >= NumberTraits<Quotient>::ONE ) // >= 1
    return Fraction( myNode->origin()->child( m ), mySup1 );
  else
    return reduced( 2 );
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::getCFrac ( std::vector< Quotient > & quotients ) const

inline

Parameters:

quotients (returns) the coefficients of the continued fraction of 'this'.

Definition at line 638 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::origin(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::u().

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display().

{
  ASSERT( k() >= NumberTraits<Quotient>::ZERO );
  int64_t i = NumberTraits<Quotient>::castToInt64_t( k() );
  if ( null() ) return;
  quotients.resize( i + 1 );
  Fraction f( *this );
  quotients[ i-- ] = f.u();
  f = f.origin();
  if ( i >= 0 )
    {
      for ( ; i >= 1; --i )
        {
          quotients[ i ] = f.u() - NumberTraits<Quotient>::ONE;
          f = f.origin();
        }
      quotients[ 0 ] = mySup1 ? f.u() - NumberTraits<Quotient>::ONE
        : NumberTraits<Quotient>::ZERO;
    }
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::getSplit	(	Fraction &	f1,
		Fraction &	f2
	)		const

inline

Splitting formula, O(1) time complexity. This fraction should not be 0/1 or 1/0. NB: 'this' = [f1] [f2].

Parameters:

f1	(returns) the left part of the split.
f2	(returns) the right part of the split.

Definition at line 597 of file LighterSternBrocot.ih.

{
  if ( odd() )
    {
      f1 = ancestor();
      f2 = father();
    }
  else
    {
      f1 = father();
      f2 = ancestor();
    }
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::getSplitBerstel	(	Fraction &	f1,
		Quotient &	nb1,
		Fraction &	f2,
		Quotient &	nb2
	)		const

inline

Berstel splitting formula, O(1) time complexity. This fraction should not be 0/1 or 1/0. NB: 'this' = nb1*[f1] nb2*[f2]. Also, if 'this->k' is even then nb1=1, otherwise nb2=1.

Parameters:

f1	(returns) the left part of the split (left pattern).
nb1	(returns) the number of repetition of the left pattern
f2	(returns) the right part of the split (right pattern).
nb2	(returns) the number of repetition of the right pattern

Definition at line 615 of file LighterSternBrocot.ih.

{
  if ( odd() )
    {
      f1 = ancestor();
      f2 = reduced( 2 );
      nb1 = this->u();
      nb2 = 1;
    }
  else
    {
      f1 = reduced( 2 );
      f2 = ancestor();
      nb1 = 1;
      nb2 = this->u();
    }
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::inverse ( ) const

inline

Returns:: the inverse of this fraction in O(1), ie [u0,...,uk] => [0,u0,...,uk] or [0,u0,...,uk] => [u0,...,uk].

Definition at line 472 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::pushBack().

{
  return ( ( myNode->k == NumberTraits<Quotient>::ZERO )
           && ( myNode->u == NumberTraits<Quotient>::ONE ) )
    ? *this
    : Fraction( myNode, ! mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::isAncestorDirect ( ) const

inline

Returns:: 'true' if its ancestor has depth k-1, otherwise returns false.

Definition at line 433 of file LighterSternBrocot.ih.

{
  return myNode->k == myNode->ancestor()->k + NumberTraits<Quotient>::ONE;
}

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::isSup1 ( ) const

inline

Attention:: Only for debug purposes.

Returns:: 'true' iff the fraction is greater than 1/1.

Definition at line 288 of file LighterSternBrocot.h.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::mySup1.

{ return mySup1; }

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::k ( ) const

inline

Returns:: its depth (1+number of coefficients of its continued fraction).

Definition at line 252 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display().

{
  ASSERT( myNode != 0 );
  // The default of this approach is that node 1/1 has two possible depths !
  return mySup1
    ? myNode->k
    : myNode->k + NumberTraits<Quotient>::ONE;
  // JOL: 2012/11/21: I left these lines in comments because I am not
  // sure yet if my correction above has no other side effects.
  //
  // return ( mySup1 || ( myNode == instance().myOneOverOne ) )
  //   ? myNode->k
  //   : myNode->k + NumberTraits<Quotient>::ONE;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::left ( ) const

inline

Returns:: its left descendant (construct it if it does not exist yet).

Definition at line 356 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverOne(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin().

{
  ASSERT( ! this->null() );
  Node* node;
  if ( myNode == instance().myOneOverZero )
    return oneOverOne();
  node = ( myNode->isSameDepthLeft() ) 
    ? myNode->origin()->child( u() + NumberTraits<Quotient>::ONE )
    : myNode->child( 2 );
  return Fraction( node, mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::lessThan	(	Integer	p1,
		Integer	q1
	)		const

inline

Parameters:

p1	a numerator.
q1	a denominator.

Returns:: 'true' if this is < to the fraction p/q.

Definition at line 280 of file LighterSternBrocot.ih.

{
  Integer d = p() * q1 - q() * p1;
  return d < NumberTraits<Integer>::ZERO;
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::moreThan	(	Integer	p1,
		Integer	q1
	)		const

inline

Parameters:

p1	a numerator.
q1	a denominator.

Returns:: 'true' if this is > to the fraction p1/q1.

Definition at line 290 of file LighterSternBrocot.ih.

{
  Integer d = p() * q1 - q() * p1;
  return d > NumberTraits<Integer>::ZERO;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::next ( Quotient v ) const

inlineprotected

Returns:: the fraction [u_0, ..., u_n, v] if [u_0, ..., u_n] is the current fraction. Construct it if it does not exist yet.

Definition at line 342 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin().

{
  ASSERT( ! this->null() );
  typedef typename MapQuotientToNode::iterator Iterator;
  if ( v == NumberTraits<Quotient>::ZERO )
    return *this;
  Node* node = myNode->origin()->child( u() + NumberTraits<Quotient>::ONE );
  return Fraction( node->child( v ), mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::null ( ) const

inline

Returns:: 'true' iff it is the null fraction 0/0.

Definition at line 213 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display().

{
  return myNode == 0;
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::odd ( ) const

inline

Returns:: 'true' if it is an odd fraction, i.e. its depth k() is odd.

Definition at line 397 of file LighterSternBrocot.ih.

{
  return NumberTraits<Quotient>::odd( k() );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator!= ( const Fraction & other ) const

inline

Parameters:

other any fraction.

Returns:: 'true' iff this is different from other.

Definition at line 313 of file LighterSternBrocot.ih.

References operator==().

{
  return ! this->operator==( other );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator< ( const Fraction & other ) const

inline

Parameters:

other any fraction.

Returns:: 'true' iff this is < to other.

Definition at line 322 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::p(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::q().

{
  return this->lessThan( other.p(), other.q() );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction & DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator= ( const Self & other )

inline

Assignment

Parameters:

other the object to clone.

Returns:: a reference to 'this'.

Definition at line 199 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::myNode, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::mySup1.

{
  if ( this != &other )
    {
      myNode = other.myNode;
      mySup1 = other.mySup1;
    }
  return *this;
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator== ( const Fraction & other ) const

inline

Parameters:

other any fraction.

Returns:: 'true' iff this is equal to other.

Definition at line 300 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::myNode, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::mySup1, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::p, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::q.

{
  if ( mySup1 == other.mySup1 ) 
    return ( myNode == other.myNode );
  else
    return ( ( myNode->p == other.myNode->q )
             && ( myNode->q == other.myNode->p ) );
}

template<typename TInteger , typename TQuotient , typename TMap >

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator> ( const Fraction & other ) const

inline

Parameters:

other any fraction.

Returns:: 'true' iff this is > to other.

Definition at line 331 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::p(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::q().

{
  return this->moreThan( other.p(), other.q() );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::origin ( ) const

inlineprotected

Returns:: the origin of this fraction in O(1), ie [u0,...,uk] => [u0,...,u_{k-1},1], i.e. [u0,...,u_{k-1}+1].

Definition at line 406 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::getCFrac().

{
  return Fraction( myNode->origin(), mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Integer DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::p ( ) const

inline

Returns:: its numerator;

Definition at line 222 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator<(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator>().

{
  return myNode ? ( mySup1 ? myNode->p : myNode->q ) : 0;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::partial ( Quotient kp ) const

inline

Parameters:

kp	the chosen depth of the partial fraction (kp <= k()).

Returns:: the partial fraction of depth kp, ie. [u0,...,uk] => [u0,...,ukp]

Definition at line 484 of file LighterSternBrocot.ih.

{
  ASSERT( ( ((Quotient)-2) <= kp ) && ( kp <= k() ) );
  return reduced( k() - kp );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::previousPartial ( ) const

inline

Returns:: the previous partial of this fraction in O(1), ie [u0,...,u{k-1},uk] => [u0,...,u{k-1}]. Otherwise said, it is its ascendant with a smaller depth.

Definition at line 463 of file LighterSternBrocot.ih.

{
  return ancestor();
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::push_back ( const std::pair< Quotient, Quotient > & quotient )

inline

    Modifies this fraction \form#77 to obtain the
    fraction \form#147. The depth of the quotient
    must be given, since continued fractions have two writings

\([u_0,...,u_k]\) and \([u_0,...,u_k - 1, 1]\).

    Useful to create output iterators, for instance with

    @code 
    typedef ... Fraction; 
    Fraction f;
    std::back_insert_iterator<Fraction> itout = std::back_inserter( f );
    @endcode

    @param quotient the pair \form#76.

Definition at line 522 of file LighterSternBrocot.ih.

{
  pushBack( quotient );
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::pushBack ( const std::pair< Quotient, Quotient > & quotient )

inline

    Modifies this fraction \form#77 to obtain the
    fraction \form#147. The depth of the quotient
    must be given, since continued fractions have two writings

\([u_0,...,u_k]\) and \([u_0,...,u_k - 1, 1]\).

    See push_back for creating output iterators.

    @param quotient the pair \form#76.

Definition at line 531 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::inverse(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverZero(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::operator=(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne().

{
  // std::vector<Quotient> quots;
  // if ( ! null() )
  //   {
  //     this->getCFrac( quots );
  //     std::cerr << "F[";
  //     for ( unsigned int i = 0; i < quots.size(); ++i )
  //       std::cerr << " " << quots[ i ];
  //   }
  // else std::cerr << "[";
  // std::cerr << "] + " << "(" << quotient.first 
  //           << "," << quotient.second << ")";
  if ( null() )
    {
      ASSERT( quotient.second <= NumberTraits<Quotient>::ZERO );
      if ( quotient.second < NumberTraits<Quotient>::ZERO )
        this->operator=( oneOverZero() );
      else if ( quotient.first == NumberTraits<Quotient>::ZERO ) // (0,0)
        this->operator=( zeroOverOne() );
      else
        this->operator=( oneOverZero().child( quotient.first ) );
    }
  else if ( this->myNode == instance().myOneOverZero )
    {
      if ( this->mySup1 ) // 1/0
        {
          ASSERT( quotient.second == NumberTraits<Quotient>::ZERO );
          if ( quotient.first == NumberTraits<Quotient>::ZERO ) // (0,0)
            this->operator=( zeroOverOne() );
          else
            this->operator=( oneOverZero().child( quotient.first ) );
        }
      else // 0/1
        {
          ASSERT( quotient.second == NumberTraits<Quotient>::ONE );
          this->operator=( oneOverZero().child( quotient.first ).inverse() );
        }
    }
  else 
    { // Generic case.
      if ( quotient.second == this->k() + NumberTraits<Quotient>::ONE )
        this->operator=( origin().child( u() + NumberTraits<Quotient>::ONE )
                         .child( quotient.first ) );
      else if ( ( this->k() == NumberTraits<Quotient>::ZERO ) 
                && ( this->u() == NumberTraits<Quotient>::ONE ) ) // (1/1)
        {
          this->operator=( oneOverZero().child( 2 ).inverse() );  // (1/(1+1))
          if ( quotient.first > NumberTraits<Quotient>::ONE )
            this->operator=( child( quotient.first ) ); // (1/(1+1/q))
        }
      else // preceding node was [....,u_k,1]
        this->operator=( child( 2 ).child( quotient.first ) );
    }
  // quots.clear();
  // this->getCFrac( quots );
  // std::cerr << " => F[";
  // for ( unsigned int i = 0; i < quots.size(); ++i )
  //   std::cerr << " " << quots[ i ];
  // std::cerr << "]" << std::endl;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Integer DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::q ( ) const

inline

Returns:: its denominator;

Definition at line 231 of file LighterSternBrocot.ih.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator<(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator>().

{
  return myNode ? ( mySup1 ? myNode->q : myNode->p ) : 0;
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::reduced ( Quotient i ) const

inline

Parameters:

i	a positive integer smaller or equal to k()+2.

Returns:: the partial fraction of depth k()-i, ie. [u0,...,uk] => [u0,...,u{k-i}]

Definition at line 494 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverZero(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::u, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne().

{
  ASSERT( ( ((Quotient)0) <= i ) && ( i <= ( k()+((Quotient)2) ) ) );
  if ( i == NumberTraits<Quotient>::ZERO )
    return *this;
  if ( i > myNode->k )
    {
      Quotient m = i - k();
      return NumberTraits<Quotient>::odd( m ) 
        ? oneOverZero()
        : zeroOverOne();
    }
  // reduced( [0, ...], n ) = [0]
  if ( ! mySup1 && ( i == k() ) )
    return zeroOverOne();
  // reduced( z_n, k ), for k <= n
  Node* node = myNode;
  for ( ; i != NumberTraits<Quotient>::ZERO; --i )
    node = node->origin();
  Quotient _u = node->u;
  node = node->origin()->child( _u - NumberTraits<Quotient>::ONE );
  return Fraction( node, mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::right ( ) const

inline

Returns:: its right descendant (construct it if it does not exist yet).

Definition at line 372 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::child(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverOne(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::origin().

{
  ASSERT( ! this->null() );
  Node* node;
  if ( myNode == instance().myOneOverZero )
    return oneOverOne();
  node = ( ! myNode->isSameDepthLeft() ) 
    ? myNode->origin()->child( u() + NumberTraits<Quotient>::ONE )
    : myNode->child( 2 );
  return Fraction( node, mySup1 );
}

template<typename TInteger , typename TQuotient , typename TMap >

void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::selfDisplay ( std::ostream & out ) const

inline

Writes/Displays the fraction on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 684 of file LighterSternBrocot.ih.

{
  if ( this->null() ) out << "[Fraction null]";
  else
    {
      out << "[Fraction f=" << this->p() 
          << "/" << this->q()
          << " u=" << this->u()
          << " k=" << this->k()
          << std::flush;
      std::vector<Quotient> quotients;
      if ( this->k() >= 0 )
        {
          this->getCFrac( quotients );
          out << " [" << quotients[ 0 ];
          for ( unsigned int i = 1; i < quotients.size(); ++i )
            out << "," << quotients[ i ];
          out << "]";
        }
      out << " ]";
    }
}

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::trueK ( ) const

inline

Attention:: Only for debug purposes.

Returns:: the depth of the node.

Definition at line 290 of file LighterSternBrocot.h.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::k, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::myNode.

{ return myNode->k; }

template<typename TInteger , typename TQuotient , typename TMap >

DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::u ( ) const

inline

Returns:: its quotient (last coefficient of its continued fraction).

Definition at line 240 of file LighterSternBrocot.ih.

References DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::instance(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero, and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Node::u.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::display(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::getCFrac().

{
  ASSERT( myNode != 0 );
  return myNode == instance().myOneOverZero 
    ? ( mySup1 ? NumberTraits<Quotient>::ONE : NumberTraits<Quotient>::ZERO )
    : myNode->u;
}

Field Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::myNode

private

The pointer to the corresponding node in the Stern-Brocot tree, i.e. the node p/q if p >= q or the node q/p otherwise.

Definition at line 236 of file LighterSternBrocot.h.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator=(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator==(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::trueK().

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>

bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::mySup1

private

When 'true', the fraction is greater or equal than 1/1 (to its right).

Definition at line 238 of file LighterSternBrocot.h.

Referenced by DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::isSup1(), DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator=(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator==().

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

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder> class DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
class DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction