DGtal  1.5.beta
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Data Fields | Private Member Functions | Private Attributes | Static Private Attributes
DGtal::SternBrocot< TInteger, TQuotient > Class Template Reference

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

#include <DGtal/arithmetic/SternBrocot.h>

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 ((concepts::CInteger< Integer >))
 
 ~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
 The total number of fractions in the current tree. More...
 

Private Member Functions

 SternBrocot ()
 
 SternBrocot (const SternBrocot &other)
 
SternBrocot & operator= (const SternBrocot &other)
 

Private Attributes

Node * myZeroOverOne
 
Node * myOneOverZero
 
Node * myOneOverOne
 

Static Private Attributes

static SternBrocot * singleton
 Singleton class. More...
 

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.

Template Parameters
TIntegerthe integral type chosen for the fractions.
TQuotientthe 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 77 of file SternBrocot.h.

Member Typedef Documentation

◆ Integer

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

Definition at line 80 of file SternBrocot.h.

◆ Quotient

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

Definition at line 81 of file SternBrocot.h.

◆ Self

template<typename TInteger , typename TQuotient = int32_t>
typedef SternBrocot<Integer,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Self

Definition at line 82 of file SternBrocot.h.

Constructor & Destructor Documentation

◆ ~SternBrocot()

template<typename TInteger , typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot ( )

Destructor.

◆ SternBrocot() [1/2]

template<typename TInteger , typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot ( )
private

Constructor. Hidden since singleton class.

◆ SternBrocot() [2/2]

template<typename TInteger , typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::SternBrocot ( const SternBrocot< TInteger, TQuotient > &  other)
private

Copy constructor.

Parameters
otherthe object to clone. Forbidden by default.

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT()

template<typename TInteger , typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >)  )

◆ display()

template<typename TInteger , typename TQuotient = int32_t>
static void DGtal::SternBrocot< TInteger, TQuotient >::display ( std::ostream &  out,
const Fraction &  f 
)
static

Writes/Displays the fraction on an output stream.

Parameters
outthe output stream where the object is written.
fthe fraction to display.

◆ fraction()

template<typename TInteger , typename TQuotient = int32_t>
static Fraction DGtal::SternBrocot< TInteger, TQuotient >::fraction ( Integer  p,
Integer  q,
Fraction  ancestor = zeroOverOne() 
)
static

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

Parameters
pthe numerator (>=0)
qthe 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.

◆ instance()

template<typename TInteger , typename TQuotient = int32_t>
static SternBrocot& DGtal::SternBrocot< TInteger, TQuotient >::instance ( )
static
Returns
the (only) instance of SternBrocot.

◆ isValid()

template<typename TInteger , typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::isValid ( ) const

Checks the validity/consistency of the object.

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

◆ oneOverZero()

template<typename TInteger , typename TQuotient = int32_t>
static Fraction DGtal::SternBrocot< TInteger, TQuotient >::oneOverZero ( )
static

The fraction 1/0

◆ operator=()

template<typename TInteger , typename TQuotient = int32_t>
SternBrocot& DGtal::SternBrocot< TInteger, TQuotient >::operator= ( const SternBrocot< TInteger, TQuotient > &  other)
private

Assignment.

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

◆ zeroOverOne()

template<typename TInteger , typename TQuotient = int32_t>
static Fraction DGtal::SternBrocot< TInteger, TQuotient >::zeroOverOne ( )
static

The fraction 0/1

Field Documentation

◆ myOneOverOne

template<typename TInteger , typename TQuotient = int32_t>
Node* DGtal::SternBrocot< TInteger, TQuotient >::myOneOverOne
private

Definition at line 471 of file SternBrocot.h.

◆ myOneOverZero

template<typename TInteger , typename TQuotient = int32_t>
Node* DGtal::SternBrocot< TInteger, TQuotient >::myOneOverZero
private

Definition at line 470 of file SternBrocot.h.

◆ myZeroOverOne

template<typename TInteger , typename TQuotient = int32_t>
Node* DGtal::SternBrocot< TInteger, TQuotient >::myZeroOverOne
private

Definition at line 469 of file SternBrocot.h.

◆ nbFractions

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 460 of file SternBrocot.h.

◆ singleton

template<typename TInteger , typename TQuotient = int32_t>
SternBrocot* DGtal::SternBrocot< TInteger, TQuotient >::singleton
staticprivate

Singleton class.

Definition at line 467 of file SternBrocot.h.

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