DGtal::SternBrocot< TInteger, TQuotient >::Fraction Class Reference

This fraction is a model of CPositiveIrreducibleFraction. More...

#include <DGtal/arithmetic/SternBrocot.h>

Public Types
typedef TInteger	Integer
typedef TQuotient	Quotient
typedef SternBrocot< TInteger, TQuotient >	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 ancestor=SternBrocotTree::zeroOverOne())
	Fraction (Node *sb_node=0)
	Fraction (const Self &other)
Self &	operator= (const Self &other)
bool	null () const
Integer	p () const
Integer	q () const
Quotient	u () const
Quotient	k () const
Fraction	left () const
Fraction	right () const
bool	even () const
bool	odd () 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
Fraction	median (const Fraction &g) const
Fraction	simplestFractionInBetween (const Fraction &other) const

Private Attributes
Node *	myNode

Detailed Description

template<typename TInteger, typename TQuotient = int32_t>
class DGtal::SternBrocot< TInteger, TQuotient >::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 SternBrocot. This representation of a fraction is simply a pointer to the corresponding node in this tree.

Definition at line 148 of file SternBrocot.h.

Member Typedef Documentation

CFracSequence

template<typename TInteger , typename TQuotient = int32_t>

std::vector<Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::CFracSequence

Definition at line 156 of file SternBrocot.h.

const_iterator

template<typename TInteger , typename TQuotient = int32_t>

ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_iterator

Definition at line 161 of file SternBrocot.h.

const_reference

template<typename TInteger , typename TQuotient = int32_t>

const value_type& DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_reference

Definition at line 162 of file SternBrocot.h.

ConstIterator

template<typename TInteger , typename TQuotient = int32_t>

InputIteratorWithRankOnSequence<CFracSequence,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::ConstIterator

Definition at line 157 of file SternBrocot.h.

Integer

template<typename TInteger , typename TQuotient = int32_t>

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

Definition at line 150 of file SternBrocot.h.

Quotient

template<typename TInteger , typename TQuotient = int32_t>

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

Definition at line 151 of file SternBrocot.h.

Self

template<typename TInteger , typename TQuotient = int32_t>

SternBrocotTree::Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Self

Definition at line 153 of file SternBrocot.h.

SternBrocotTree

template<typename TInteger , typename TQuotient = int32_t>

SternBrocot<TInteger,TQuotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::SternBrocotTree

Definition at line 152 of file SternBrocot.h.

UnsignedInteger

template<typename TInteger , typename TQuotient = int32_t>

NumberTraits<Integer>::UnsignedVersion DGtal::SternBrocot< TInteger, TQuotient >::Fraction::UnsignedInteger

Definition at line 154 of file SternBrocot.h.

Value

template<typename TInteger , typename TQuotient = int32_t>

std::pair<Quotient, Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Value

Definition at line 155 of file SternBrocot.h.

value_type

template<typename TInteger , typename TQuotient = int32_t>

Value DGtal::SternBrocot< TInteger, TQuotient >::Fraction::value_type

Definition at line 160 of file SternBrocot.h.

Constructor & Destructor Documentation

Fraction() [1/3]

template<typename TInteger , typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction	(	Integer	aP,
		Integer	aQ,
		Fraction	ancestor = SternBrocotTree::zeroOverOne() )

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

Parameters

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

Construct 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 aP/aQ.

Fraction() [2/3]

template<typename TInteger , typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction

(

Node *

sb_node = 0

)

Default constructor.

Parameters

sb_node

the associated node (or 0 for null fraction).

Fraction() [3/3]

template<typename TInteger , typename TQuotient = int32_t>

DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction

(

const Self &

other

)

Copy constructor.

Parameters

other

the object to clone.

Member Function Documentation

begin()

template<typename TInteger , typename TQuotient = int32_t>

ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::begin

(

)

const

Returns

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

end()

template<typename TInteger , typename TQuotient = int32_t>

ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::end

(

)

const

Returns

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

equals()

template<typename TInteger , typename TQuotient = int32_t>

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

Parameters

p1	a numerator.
q1	a denominator.

Returns

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

even()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::even

(

)

const

Returns

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

father() [1/2]

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::father

(

)

const

Returns

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

father() [2/2]

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::father

(

Quotient

m

)

const

Parameters

m	a quotient between 1 and uk-1.

Returns

a given father of this fraction in O(uk - m), ie [u0,...,uk] => [u0,...,m]

Todo

Do it in O(1)... but require to change the data structure.

getCFrac()

template<typename TInteger , typename TQuotient = int32_t>

void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::getCFrac

(

std::vector< Quotient > &

quotients

)

const

Parameters

quotients

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

getSplit()

template<typename TInteger , typename TQuotient = int32_t>

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

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

Parameters

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

getSplitBerstel()

template<typename TInteger , typename TQuotient = int32_t>

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

Berstel splitting formula, O(1) time complexity. This fraction should not be 0/1 or 1/0. NB: 'this' = nb1*[f1] $\oplus$ 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

inverse()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::inverse

(

)

const

Returns

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

k()

template<typename TInteger , typename TQuotient = int32_t>

Quotient DGtal::SternBrocot< TInteger, TQuotient >::Fraction::k

(

)

const

Returns

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

left()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::left

(

)

const

Returns

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

lessThan()

template<typename TInteger , typename TQuotient = int32_t>

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

Parameters

p1	a numerator.
q1	a denominator.

Returns

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

median()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::median

(

const Fraction &

g

)

const

Parameters

g	any fraction

Returns

the median of 'this' and g

moreThan()

template<typename TInteger , typename TQuotient = int32_t>

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

Parameters

p1	a numerator.
q1	a denominator.

Returns

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

null()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::null

(

)

const

Returns

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

odd()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::odd

(

)

const

Returns

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

operator!=()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator!=

(

const Fraction &

other

)

const

Parameters

other

any fraction.

Returns

'true' iff this is different from other.

operator<()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator<

(

const Fraction &

other

)

const

Parameters

other

any fraction.

Returns

'true' iff this is < to other.

operator=()

template<typename TInteger , typename TQuotient = int32_t>

Self & DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator=

(

const Self &

other

)

Assignment

Parameters

other

the object to clone.

Returns

a reference to 'this'.

operator==()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator==

(

const Fraction &

other

)

const

Parameters

other

any fraction.

Returns

'true' iff this is equal to other.

operator>()

template<typename TInteger , typename TQuotient = int32_t>

bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator>

(

const Fraction &

other

)

const

Parameters

other

any fraction.

Returns

'true' iff this is > to other.

p()

template<typename TInteger , typename TQuotient = int32_t>

Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::p

(

)

const

Returns

its numerator;

partial()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::partial

(

Quotient

kp

)

const

Parameters

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

Returns

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

previousPartial()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::previousPartial

(

)

const

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.

push_back()

template<typename TInteger , typename TQuotient = int32_t>

void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::push_back

(

const std::pair< Quotient, Quotient > &

quotient

)

Modifies this fraction $[u_0,...,u_k]$ to obtain the fraction $[u_0,...,u_k,m]$. 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

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

Parameters

quotient

the pair $(m,k+1)$.

pushBack()

template<typename TInteger , typename TQuotient = int32_t>

void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::pushBack

(

const std::pair< Quotient, Quotient > &

quotient

)

Modifies this fraction $[u_0,...,u_k]$ to obtain the fraction $[u_0,...,u_k,m]$. 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.

Parameters

quotient

the pair $(m,k+1)$.

q()

template<typename TInteger , typename TQuotient = int32_t>

Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::q

(

)

const

Returns

its denominator;

reduced()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::reduced

(

Quotient

i

)

const

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}]

right()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::right

(

)

const

Returns

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

selfDisplay()

template<typename TInteger , typename TQuotient = int32_t>

void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::selfDisplay

(

std::ostream &

out

)

const

Writes/Displays the fraction on an output stream.

Parameters

out	the output stream where the object is written.

simplestFractionInBetween()

template<typename TInteger , typename TQuotient = int32_t>

Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::simplestFractionInBetween

(

const Fraction &

other

)

const

Compute the fraction of smallest denominator strictly between this fraction and other fraction. Assumes that "this" fraction is smaller than "other" fraction.

Parameters

other

any fraction

Returns

a fraction NB: $O(k)$ where $k$ is the depth of the output fraction.

u()

template<typename TInteger , typename TQuotient = int32_t>

Quotient DGtal::SternBrocot< TInteger, TQuotient >::Fraction::u

(

)

const

Returns

its quotient (last coefficient of its continued fraction).

Field Documentation

myNode

template<typename TInteger , typename TQuotient = int32_t>

Node* DGtal::SternBrocot< TInteger, TQuotient >::Fraction::myNode

private

Definition at line 165 of file SternBrocot.h.

---

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

• SternBrocot.h