#include <SternBrocot.h>

Collaboration diagram for DGtal::SternBrocot< TInteger, TQuotient >:

Data Structures
class	Fraction
	This fraction is a model of CPositiveIrreducibleFraction. More...
struct	Node

Public Types
typedef TInteger	Integer
typedef TQuotient	Quotient
typedef SternBrocot< Integer, Quotient >	Self

Public Member Functions
	BOOST_CONCEPT_ASSERT ((CInteger< Integer >))
	BOOST_CONCEPT_ASSERT ((CSignedInteger< Quotient >))
	~SternBrocot ()
bool	isValid () const

Static Public Member Functions
static SternBrocot &	instance ()
static Fraction	zeroOverOne ()
static Fraction	oneOverZero ()
static Fraction	fraction (Integer p, Integer q, Fraction ancestor=zeroOverOne())
static void	display (std::ostream &out, const Fraction &f)

Data Fields
Quotient	nbFractions

Private Member Functions
	SternBrocot ()
	SternBrocot (const SternBrocot &other)
SternBrocot &	operator= (const SternBrocot &other)
template<>
SternBrocot< DGtal::int32_t, DGtal::int32_t > *	singleton
template<>
SternBrocot< DGtal::int64_t, DGtal::int32_t > *	singleton
template<>
SternBrocot< DGtal::int64_t, DGtal::int64_t > *	singleton

Private Attributes
Node *	myZeroOverOne
Node *	myOneOverZero
Node *	myOneOverOne

Static Private Attributes
static SternBrocot *	singleton = 0

Detailed Description

template<typename TInteger, typename TQuotient = int32_t>
class DGtal::SternBrocot< TInteger, TQuotient >

Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it progressively and to navigate within fractions in O(1) time for most operations. It is well known that the structure of this tree is a coding of the continued fraction representation of fractions.

Description of template class 'SternBrocot'

This class is not to be instantiated, since it is useless to duplicate it. Use static method SternBrocot::fraction to obtain your fractions.

Parameters:

TInteger	the integral type chosen for the fractions.
TQuotient	the integral type chosen for the quotients/coefficients or depth (may be "smaller" than TInteger, since they are generally much smaller than the fraction itself).

Definition at line 78 of file SternBrocot.h.

Member Typedef Documentation

template<typename TInteger, typename TQuotient = int32_t>

typedef TInteger DGtal::SternBrocot< TInteger, TQuotient >::Integer

Definition at line 81 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>

typedef TQuotient DGtal::SternBrocot< TInteger, TQuotient >::Quotient

Definition at line 82 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>

typedef SternBrocot<Integer,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Self

Definition at line 83 of file SternBrocot.h.

Constructor & Destructor Documentation

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot ( )

inline

Destructor.

Definition at line 533 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::myOneOverOne, DGtal::SternBrocot< TInteger, TQuotient >::myOneOverZero, and DGtal::SternBrocot< TInteger, TQuotient >::myZeroOverOne.

{
  if ( myOneOverOne != 0 ) delete myOneOverOne;
  if ( myOneOverZero != 0 ) delete myOneOverZero;
  if ( myZeroOverOne != 0 ) delete myZeroOverOne;
}

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot ( )

inlineprivate

Constructor. Hidden since singleton class.

Definition at line 542 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::Node::ascendantLeft, DGtal::SternBrocot< TInteger, TQuotient >::Node::descendantLeft, DGtal::SternBrocot< TInteger, TQuotient >::Node::descendantRight, DGtal::SternBrocot< TInteger, TQuotient >::Node::inverse, DGtal::SternBrocot< TInteger, TQuotient >::myOneOverOne, DGtal::SternBrocot< TInteger, TQuotient >::myOneOverZero, DGtal::SternBrocot< TInteger, TQuotient >::myZeroOverOne, and DGtal::SternBrocot< TInteger, TQuotient >::nbFractions.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::instance().

{
  myOneOverZero = new Node( NumberTraits<Integer>::ONE,
                            NumberTraits<Integer>::ZERO,
                            NumberTraits<Quotient>::ZERO,
                            -NumberTraits<Quotient>::ONE,
                            myZeroOverOne, 0, myOneOverOne, 0,
                            myZeroOverOne );
  myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
                            NumberTraits<Integer>::ONE,
                            NumberTraits<Quotient>::ZERO,
                            NumberTraits<Quotient>::ZERO,
                            myZeroOverOne, myOneOverZero, 0, myOneOverOne,
                            myOneOverZero );
  myOneOverOne = new Node( NumberTraits<Integer>::ONE,
                           NumberTraits<Integer>::ONE,
                           NumberTraits<Quotient>::ONE,
                           NumberTraits<Quotient>::ZERO,
                           myZeroOverOne, myOneOverZero, 0, 0,
                           myOneOverOne );
  myOneOverZero->ascendantLeft = myZeroOverOne;
  myOneOverZero->descendantLeft = myOneOverOne;
  myOneOverZero->inverse = myZeroOverOne;
  myZeroOverOne->ascendantLeft = myZeroOverOne;
  myZeroOverOne->descendantRight = myOneOverOne;
  myOneOverOne->inverse = myOneOverOne;
  nbFractions = 3;
}

template<typename TInteger, typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot ( const SternBrocot< TInteger, TQuotient > & other )

private

Copy constructor.

Parameters:

other the object to clone. Forbidden by default.

Member Function Documentation

template<typename TInteger, typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::BOOST_CONCEPT_ASSERT ( (CInteger< Integer >) )

template<typename TInteger, typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::BOOST_CONCEPT_ASSERT ( (CSignedInteger< Quotient >) )

template<typename TInteger , typename TQuotient >

void DGtal::SternBrocot< TInteger, TQuotient >::display	(	std::ostream &	out,
		const Fraction &	f
	)

inlinestatic

Writes/Displays the fraction on an output stream.

Parameters:

out	the output stream where the object is written.
f	the fraction to display.

Writes/Displays the object on an output stream.

Parameters:

out	the output stream where the object is written.

Definition at line 609 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::Fraction::getCFrac(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::k(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::null(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::p(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::q(), and DGtal::SternBrocot< TInteger, TQuotient >::Fraction::u().

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

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient >::Fraction DGtal::SternBrocot< TInteger, TQuotient >::fraction	(	Integer	p,
		Integer	q,
		Fraction	ancestor = `zeroOverOne()`
	)

inlinestatic

Any fraction p/q. Complexity is in \( \sum_i u_i \), where u_i are the partial quotients of p/q.

Parameters:

p	the numerator (>=0)
q	the denominator (>=0)
ancestor	(optional) any ancestor of p/q in the tree (for speed-up).

Returns:: the corresponding fraction in the Stern-Brocot tree.

NB: Complexity is bounded by \( 2 \sum_i u_i \), where u_i are the partial quotients of p/q.

Definition at line 652 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::Fraction::equals(), DGtal::IntegerComputer< TInteger >::gcd(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::left(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::lessThan(), DGtal::SternBrocot< TInteger, TQuotient >::oneOverZero(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::p(), DGtal::SternBrocot< TInteger, TQuotient >::Fraction::q(), and DGtal::SternBrocot< TInteger, TQuotient >::Fraction::right().

{
  IntegerComputer<Integer> ic;
  Integer g = ic.gcd( p, q );
  if ( g != NumberTraits<Integer>::ZERO )
    {
      p /= g;
      q /= g;
    }
  // special case 1/0
  if ( ( p == NumberTraits<Integer>::ONE ) 
       && ( q == NumberTraits<Integer>::ZERO ) ) return oneOverZero();
  // other positive fractions
  while ( ! ancestor.equals( p, q ) )
    {
      ASSERT( ( p + q ) >= ( ancestor.p() + ancestor.q() )
              && "[ImaGene::SternBrocot::fraction] bad ancestor." );
      ancestor = ancestor.lessThan( p, q ) 
        ? ancestor.right()
        : ancestor.left();
    }
  return ancestor;
}

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient > & DGtal::SternBrocot< TInteger, TQuotient >::instance ( )

inlinestatic

Returns:: the (only) instance of SternBrocot.

Definition at line 574 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::singleton(), and DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot().

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::Fraction::left(), DGtal::SternBrocot< TInteger, TQuotient >::oneOverZero(), and DGtal::SternBrocot< TInteger, TQuotient >::zeroOverOne().

{
  if ( singleton == 0 )
    singleton = new SternBrocot;
  return *singleton;
}

template<typename TInteger , typename TQuotient >

bool DGtal::SternBrocot< TInteger, TQuotient >::isValid ( ) const

inline

Checks the validity/consistency of the object.

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

Definition at line 640 of file SternBrocot.ih.

{
    return true;
}

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient >::Fraction DGtal::SternBrocot< TInteger, TQuotient >::oneOverZero ( )

inlinestatic

The fraction 1/0

Definition at line 594 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::instance(), and DGtal::SternBrocot< TInteger, TQuotient >::myOneOverZero.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::fraction(), and DGtal::SternBrocot< TInteger, TQuotient >::Fraction::pushBack().

{
  return Fraction( instance().myOneOverZero );
}

template<typename TInteger, typename TQuotient = int32_t>

SternBrocot& DGtal::SternBrocot< TInteger, TQuotient >::operator= ( const SternBrocot< TInteger, TQuotient > & other )

private

Assignment.

Parameters:

other the object to copy.

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

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction(), and DGtal::SternBrocot< TInteger, TQuotient >::Fraction::pushBack().

template<>

SternBrocot< DGtal::int32_t, DGtal::int32_t > * DGtal::SternBrocot< DGtal::int32_t, DGtal::int32_t >::singleton ( )

private

Definition at line 57 of file SternBrocot.cpp.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::instance().

template<>

SternBrocot< DGtal::int64_t, DGtal::int32_t > * DGtal::SternBrocot< DGtal::int64_t, DGtal::int32_t >::singleton ( )

private

Definition at line 61 of file SternBrocot.cpp.

template<>

SternBrocot< DGtal::int64_t, DGtal::int64_t > * DGtal::SternBrocot< DGtal::int64_t, DGtal::int64_t >::singleton ( )

private

Definition at line 65 of file SternBrocot.cpp.

template<typename TInteger , typename TQuotient >

DGtal::SternBrocot< TInteger, TQuotient >::Fraction DGtal::SternBrocot< TInteger, TQuotient >::zeroOverOne ( )

inlinestatic

The fraction 0/1

Definition at line 586 of file SternBrocot.ih.

References DGtal::SternBrocot< TInteger, TQuotient >::instance(), and DGtal::SternBrocot< TInteger, TQuotient >::myZeroOverOne.

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

{
  return Fraction( instance().myZeroOverOne );
}

Field Documentation

template<typename TInteger, typename TQuotient = int32_t>

Node* DGtal::SternBrocot< TInteger, TQuotient >::myOneOverOne

private

Definition at line 456 of file SternBrocot.h.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot(), and DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot().

template<typename TInteger, typename TQuotient = int32_t>

Node* DGtal::SternBrocot< TInteger, TQuotient >::myOneOverZero

private

Definition at line 455 of file SternBrocot.h.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::oneOverZero(), DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot(), and DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot().

template<typename TInteger, typename TQuotient = int32_t>

Node* DGtal::SternBrocot< TInteger, TQuotient >::myZeroOverOne

private

Definition at line 454 of file SternBrocot.h.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot(), DGtal::SternBrocot< TInteger, TQuotient >::zeroOverOne(), and DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot().

template<typename TInteger, typename TQuotient = int32_t>

Quotient DGtal::SternBrocot< TInteger, TQuotient >::nbFractions

The total number of fractions in the current tree.

Definition at line 445 of file SternBrocot.h.

Referenced by DGtal::SternBrocot< TInteger, TQuotient >::Fraction::left(), and DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot().

template<typename TInteger, typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient > * DGtal::SternBrocot< TInteger, TQuotient >::singleton = 0

staticprivate

Singleton class.

Definition at line 452 of file SternBrocot.h.

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

Data Structures

Public Types

Public Member Functions

Static Public Member Functions

Data Fields

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

template<typename TInteger, typename TQuotient = int32_t> class DGtal::SternBrocot< TInteger, TQuotient >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Field Documentation

template<typename TInteger, typename TQuotient = int32_t>
class DGtal::SternBrocot< TInteger, TQuotient >