DGtal 1.3.0
Loading...
Searching...
No Matches
Data Structures | Public Types | Public Member Functions | Static Public Member Functions | Data Fields | Private Member Functions | Private Attributes | Static Private Attributes
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap > 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/LighterSternBrocot.h>

Data Structures

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

Public Types

typedef TInteger Integer
 
typedef TQuotient Quotient
 
typedef TMap Map
 
typedef LighterSternBrocot< TInteger, TQuotient, TMap > Self
 
typedef TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
 

Public Member Functions

 BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >))
 
 ~LighterSternBrocot ()
 
bool isValid () const
 

Static Public Member Functions

static LighterSternBrocotinstance ()
 
static Fraction zeroOverOne ()
 
static Fraction oneOverZero ()
 
static Fraction oneOverOne ()
 
static Fraction fraction (Integer p, Integer q, Fraction ancestor=oneOverZero())
 
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

 LighterSternBrocot ()
 
 LighterSternBrocot (const LighterSternBrocot &other)
 
LighterSternBrocotoperator= (const LighterSternBrocot &other)
 

Private Attributes

NodemyOneOverZero
 
NodemyOneOverOne
 

Static Private Attributes

static LighterSternBrocotsingleton
 Singleton class. More...
 

Detailed Description

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

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 'LighterSternBrocot'

There are two main differences with the class SternBrocot. The first one is that inverses are not stored. With this optimization, there are twice less nodes and each node is lighter. The second one lies in the access to the children of a node. Here, a map type M is provided so that a node [u_0; u_1, ..., u_n] can access its child node [u_0; u_1, ..., u_n, k] in the time of the operation M::operator[]. This representation is also different from LightSternBrocot in the sense that nodes have only one set of child nodes and that only fractions greater than 1/1 are stored.

In this representation, the fraction 1/1 has depth 0, like 2/1, 3/1, etc. Furthermore, each fraction [u_0,...,u_n] has an origin which is the fraction [u_0,...,u_{n-1},1]. It is the top extremity of this branch. The origin has depth n-1 since [u_0,...,u_{n-1},1] = [u_0,...,u_{n-1}+1]. Inversely a k-child of [u_0,...,u_n], for k >= 2, is the fraction [u_0,...,u_n - 1, k]. A 1-child of a fraction f is itself, except for the fraction 1/0 where its 1-child is 1/1 by convention.

In practice, also this class has supposedly a better complexity than SternBrocot, it is 1% slower for integers smaller than 10^9 and 5% slower for integers smaller than 10^4. Note however that it takes like 7 times less memory (and asymptotically less when the number of computations tends toward infinity).

This class is not to be instantiated, since it is useless to duplicate it. Use static method LighterSternBrocot::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).
TMapthe rebinder type for defining an association TQuotient -> LighterSternBrocot::Node*. For instance, StdMapRebinder is fine.
Examples
arithmetic/approximation.cpp, arithmetic/convergents-biginteger.cpp, arithmetic/convergents.cpp, arithmetic/fraction.cpp, and arithmetic/pattern.cpp.

Definition at line 108 of file LighterSternBrocot.h.

Member Typedef Documentation

◆ Integer

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
typedef TInteger DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Integer

Definition at line 111 of file LighterSternBrocot.h.

◆ Map

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
typedef TMap DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Map

Definition at line 113 of file LighterSternBrocot.h.

◆ MapQuotientToNode

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
typedef TMap::template Rebinder<Quotient,Node*>::Type DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::MapQuotientToNode

Definition at line 119 of file LighterSternBrocot.h.

◆ Quotient

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
typedef TQuotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Quotient

Definition at line 112 of file LighterSternBrocot.h.

◆ Self

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
typedef LighterSternBrocot<TInteger,TQuotient,TMap> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Self

Definition at line 114 of file LighterSternBrocot.h.

Constructor & Destructor Documentation

◆ ~LighterSternBrocot()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::~LighterSternBrocot ( )

Destructor.

◆ LighterSternBrocot() [1/2]

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::LighterSternBrocot ( )
private

Constructor. Hidden since singleton class.

◆ LighterSternBrocot() [2/2]

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::LighterSternBrocot ( const LighterSternBrocot< TInteger, TQuotient, TMap > &  other)
private

Copy constructor.

Parameters
otherthe object to clone. Forbidden by default.

Member Function Documentation

◆ BOOST_CONCEPT_ASSERT()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::BOOST_CONCEPT_ASSERT ( (concepts::CInteger< Integer >)  )

◆ display()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
static void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>
static Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::fraction ( Integer  p,
Integer  q,
Fraction  ancestor = oneOverZero() 
)
static

Any fraction p/q. Complexity is in O(n) where n is the depth of continued fraction of p/q.

Parameters
pthe numerator (>=0)
qthe denominator (>=0)
ancestor(optional) unused in this representation.
Returns
the corresponding fraction in the Stern-Brocot tree.

◆ instance()

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

◆ isValid()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::isValid ( ) const

Checks the validity/consistency of the object.

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

◆ oneOverOne()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
static Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverOne ( )
static

The fraction 1/1

◆ oneOverZero()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
static Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::oneOverZero ( )
static

The fraction 1/0

◆ operator=()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
LighterSternBrocot & DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::operator= ( const LighterSternBrocot< TInteger, TQuotient, TMap > &  other)
private

Assignment.

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

◆ zeroOverOne()

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
static Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne ( )
static

The fraction 0/1

Field Documentation

◆ myOneOverOne

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverOne
private

Definition at line 551 of file LighterSternBrocot.h.

◆ myOneOverZero

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
Node* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::myOneOverZero
private

Definition at line 550 of file LighterSternBrocot.h.

◆ nbFractions

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::nbFractions

The total number of fractions in the current tree.

Definition at line 540 of file LighterSternBrocot.h.

◆ singleton

template<typename TInteger , typename TQuotient , typename TMap = StdMapRebinder>
LighterSternBrocot* DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::singleton
staticprivate

Singleton class.

Definition at line 548 of file LighterSternBrocot.h.


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