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

#include <DGtal/arithmetic/LightSternBrocot.h>

Public Types
typedef TInteger	Integer

typedef TQuotient	Quotient

typedef LightSternBrocot< 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	next (Quotient v) const

Fraction	next1 (Quotient v) const

Private Attributes
Node *	myNode

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

Detailed Description

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
class DGtal::LightSternBrocot< 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 LightSternBrocot. 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 192 of file LightSternBrocot.h.

Member Typedef Documentation

◆ CFracSequence

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

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

Definition at line 200 of file LightSternBrocot.h.

◆ const_iterator

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

ConstIterator DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::const_iterator

Definition at line 205 of file LightSternBrocot.h.

◆ const_reference

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

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

Definition at line 206 of file LightSternBrocot.h.

◆ ConstIterator

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

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

Definition at line 201 of file LightSternBrocot.h.

◆ Integer

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

TInteger DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Integer

Definition at line 194 of file LightSternBrocot.h.

◆ Quotient

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

TQuotient DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Quotient

Definition at line 195 of file LightSternBrocot.h.

◆ Self

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

SternBrocotTree::Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::Self

Definition at line 197 of file LightSternBrocot.h.

◆ SternBrocotTree

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

LightSternBrocot<TInteger, TQuotient, TMap> DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::SternBrocotTree

Definition at line 196 of file LightSternBrocot.h.

◆ UnsignedInteger

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

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

Definition at line 198 of file LightSternBrocot.h.

◆ Value

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

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

Definition at line 199 of file LightSternBrocot.h.

◆ value_type

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

Value DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::value_type

Definition at line 204 of file LightSternBrocot.h.

Constructor & Destructor Documentation

◆ Fraction() [1/3]

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

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

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.

◆ Fraction() [2/3]

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

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

Default constructor.

Parameters

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

◆ Fraction() [3/3]

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

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

Copy constructor.

Parameters

other the object to clone.

Member Function Documentation

◆ ancestor()

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

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

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.

◆ begin()

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

ConstIterator DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

ConstIterator DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

bool DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

bool DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

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

Parameters

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

◆ getSplit()

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

void DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

void DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

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

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

◆ isAncestorDirect()

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

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

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

◆ isSup1()

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

bool DGtal::LightSternBrocot< 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 264 of file LightSternBrocot.h.

264{ return mySup1; }

DGtal::LightSternBrocot::Fraction::mySup1

bool mySup1

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

Definition LightSternBrocot.h:214

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

◆ k()

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

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

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

◆ left()

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

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

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

◆ lessThan()

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

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

Parameters

p1	a numerator.
q1	a denominator.

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

◆ moreThan()

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

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

Parameters

p1	a numerator.
q1	a denominator.

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

◆ next()

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

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

protected

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.

◆ next1()

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

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::next1 ( Quotient v ) const

protected

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

◆ null()

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

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

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

◆ odd()

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

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

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

◆ operator!=()

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

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

Parameters

other any fraction.

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

◆ operator<()

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

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

Parameters

other any fraction.

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

◆ operator=()

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

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

Assignment

Parameters

other the object to clone.

Returns: a reference to 'this'.

◆ operator==()

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

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

Parameters

other any fraction.

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

◆ operator>()

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

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

Parameters

other any fraction.

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

◆ p()

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

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

Returns: its numerator;

◆ partial()

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

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

void DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

void DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

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

Returns: its denominator;

◆ reduced()

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

Fraction DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::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 , typename TMap = StdMapRebinder>

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

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

◆ selfDisplay()

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

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

Writes/Displays the fraction on an output stream.

Parameters

out	the output stream where the object is written.

◆ trueK()

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

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

inline

Attention: Only for debug purposes.

Returns: the depth of the node.

Definition at line 266 of file LightSternBrocot.h.

266{ return myNode->k; }

DGtal::LightSternBrocot::Fraction::myNode

Node * myNode

Definition LightSternBrocot.h:212

DGtal::LightSternBrocot::Node::k

Quotient k

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

Definition LightSternBrocot.h:156

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

◆ u()

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

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

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

Field Documentation

◆ myNode

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

Node* DGtal::LightSternBrocot< 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 212 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::trueK().

◆ mySup1

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

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

private

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

Definition at line 214 of file LightSternBrocot.h.

Referenced by DGtal::LightSternBrocot< TInteger, TQuotient, TMap >::Fraction::isSup1().

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

LightSternBrocot.h

Public Types

Public Member Functions

Protected Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ CFracSequence

◆ const_iterator

◆ const_reference

◆ ConstIterator

◆ Integer

◆ Quotient

◆ Self

◆ SternBrocotTree

◆ UnsignedInteger

◆ Value

◆ value_type

Constructor & Destructor Documentation

◆ Fraction() [1/3]

◆ Fraction() [2/3]

◆ Fraction() [3/3]

Member Function Documentation

◆ ancestor()

◆ begin()

◆ end()

◆ equals()

◆ even()

◆ father() [1/2]

◆ father() [2/2]

◆ getCFrac()

◆ getSplit()

◆ getSplitBerstel()

◆ inverse()

◆ isAncestorDirect()

◆ isSup1()

◆ k()

◆ left()

◆ lessThan()

◆ moreThan()

◆ next()

◆ next1()

◆ null()

◆ odd()

◆ operator!=()

◆ operator<()

◆ operator=()

◆ operator==()

◆ operator>()

◆ p()

◆ partial()

◆ previousPartial()

◆ push_back()

◆ pushBack()

◆ q()

◆ reduced()

◆ right()

◆ selfDisplay()

◆ trueK()

◆ u()

Field Documentation

◆ myNode

◆ mySup1