Processing math: 100%
DGtal 2.0.0
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction Class Reference

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

#include <DGtal/arithmetic/LighterSternBrocot.h>

Public Types

typedef TInteger Integer
typedef TQuotient Quotient
typedef LighterSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
typedef SternBrocotTree::Fraction Self
typedef NumberTraits< Integer >::UnsignedVersion UnsignedInteger
typedef std::pair< Quotient, QuotientValue
typedef std::vector< QuotientCFracSequence
typedef InputIteratorWithRankOnSequence< CFracSequence, QuotientConstIterator
typedef Value value_type
typedef ConstIterator const_iterator
typedef const value_typeconst_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)
Selfoperator= (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 child (Quotient v) const
Fraction origin () const
Fraction next (Quotient v) const

Private Attributes

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

Detailed Description

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

Member Typedef Documentation

◆ CFracSequence

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef std::vector<Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::CFracSequence

Definition at line 224 of file LighterSternBrocot.h.

◆ const_iterator

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef ConstIterator DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::const_iterator

Definition at line 229 of file LighterSternBrocot.h.

◆ const_reference

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef const value_type& DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::const_reference

Definition at line 230 of file LighterSternBrocot.h.

◆ ConstIterator

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef InputIteratorWithRankOnSequence<CFracSequence,Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::ConstIterator

Definition at line 225 of file LighterSternBrocot.h.

◆ Integer

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

Definition at line 218 of file LighterSternBrocot.h.

◆ Quotient

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

Definition at line 219 of file LighterSternBrocot.h.

◆ Self

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

Definition at line 221 of file LighterSternBrocot.h.

◆ SternBrocotTree

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

Definition at line 220 of file LighterSternBrocot.h.

◆ UnsignedInteger

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef NumberTraits<Integer>::UnsignedVersion DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::UnsignedInteger

Definition at line 222 of file LighterSternBrocot.h.

◆ Value

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef std::pair<Quotient, Quotient> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Value

Definition at line 223 of file LighterSternBrocot.h.

◆ value_type

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
typedef Value DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::value_type

Definition at line 228 of file LighterSternBrocot.h.

Constructor & Destructor Documentation

◆ Fraction() [1/3]

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< 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
aPthe numerator (>=0)
aQthe denominator (>=0)
start(optional) unused in this representation.

References Fraction(), and DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::zeroOverOne().

Referenced by ancestor(), child(), father(), father(), Fraction(), getSplit(), getSplitBerstel(), inverse(), left(), next(), operator!=(), operator<(), operator==(), operator>(), origin(), partial(), previousPartial(), reduced(), and right().

◆ Fraction() [2/3]

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::Fraction ( Node * sb_node = 0,
bool sup1 = false )

Default constructor.

Parameters
sb_nodethe associated node (or 0 for null fraction).
sup1when 'false', the fraction is smaller greater than 1/1 and represents q/p.

◆ Fraction() [3/3]

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

Copy constructor.

Parameters
otherthe object to clone.

Member Function Documentation

◆ ancestor()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< 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. Equivalent to reduced( 1 ).

References Fraction().

◆ begin()

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

◆ child()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::child ( Quotient v) const
protected
Returns
the fraction [u_0, ..., u_n - 1, v] if [u_0, ..., u_n] is the current fraction. Construct it if it does not exist yet.

References Fraction().

◆ end()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
ConstIterator DGtal::LighterSternBrocot< 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::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::equals ( Integer p1,
Integer q1 ) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is the fraction p1/q1.

◆ even()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< 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::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::father ( ) const
Returns
the father of this fraction in O(1), ie [u0,...,uk] => [u0,.. .,uk - 1]

References Fraction().

◆ father() [2/2]

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::father ( Quotient m) const
Parameters
ma quotient between 1 and uk-1.
Returns
the fraction [u_0, ..., u_{n-1},m]

References Fraction().

◆ getCFrac()

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

References Fraction().

◆ getSplitBerstel()

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

References Fraction().

◆ inverse()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< 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].

References Fraction().

◆ isAncestorDirect()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< 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::LighterSternBrocot< 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 287 of file LighterSternBrocot.h.

287{ return mySup1; }
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...

References mySup1.

◆ k()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Quotient DGtal::LighterSternBrocot< 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::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::left ( ) const
Returns
its left descendant (construct it if it does not exist yet).

References Fraction().

◆ lessThan()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::lessThan ( Integer p1,
Integer q1 ) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is < to the fraction p/q.

◆ moreThan()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::moreThan ( Integer p1,
Integer q1 ) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is > to the fraction p1/q1.

◆ next()

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

References Fraction().

◆ null()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< 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::LighterSternBrocot< 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::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator!= ( const Fraction & other) const
Parameters
otherany fraction.
Returns
'true' iff this is different from other.

References Fraction().

◆ operator<()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator< ( const Fraction & other) const
Parameters
otherany fraction.
Returns
'true' iff this is < to other.

References Fraction().

◆ operator=()

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

Assignment

Parameters
otherthe object to clone.
Returns
a reference to 'this'.

◆ operator==()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator== ( const Fraction & other) const
Parameters
otherany fraction.
Returns
'true' iff this is equal to other.

References Fraction().

◆ operator>()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::operator> ( const Fraction & other) const
Parameters
otherany fraction.
Returns
'true' iff this is > to other.

References Fraction().

◆ origin()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::origin ( ) const
protected
Returns
the origin of this fraction in O(1), ie [u0,...,uk] => [u0,...,u_{k-1},1], i.e. [u0,...,u_{k-1}+1].

References Fraction().

◆ p()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Integer DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::p ( ) const
Returns
its numerator;

◆ partial()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::partial ( Quotient kp) const
Parameters
kpthe chosen depth of the partial fraction (kp <= k()).
Returns
the partial fraction of depth kp, ie. [u0,...,uk] => [u0,...,ukp]

References Fraction().

◆ previousPartial()

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

References Fraction().

◆ push_back()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
void DGtal::LighterSternBrocot< 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;
std::back_insert_iterator<Fraction> itout = std::back_inserter( f );
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
Parameters
quotientthe pair (m,k+1).

◆ pushBack()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
void DGtal::LighterSternBrocot< 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
quotientthe pair (m,k+1).

◆ q()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Integer DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::q ( ) const
Returns
its denominator;

◆ reduced()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::reduced ( Quotient i) const
Parameters
ia positive integer smaller or equal to k()+2.
Returns
the partial fraction of depth k()-i, ie. [u0,...,uk] => [u0,...,u{k-i}]

References Fraction().

◆ right()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Fraction DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::right ( ) const
Returns
its right descendant (construct it if it does not exist yet).

References Fraction().

◆ selfDisplay()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
void DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::selfDisplay ( std::ostream & out) const

Writes/Displays the fraction on an output stream.

Parameters
outthe output stream where the object is written.

◆ trueK()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::trueK ( ) const
inline
Attention
Only for debug purposes.
Returns
the depth of the node.

Definition at line 289 of file LighterSternBrocot.h.

289{ return myNode->k; }

References myNode.

◆ u()

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
Quotient DGtal::LighterSternBrocot< 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::LighterSternBrocot< 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 235 of file LighterSternBrocot.h.

Referenced by trueK().

◆ mySup1

template<typename TInteger, typename TQuotient, typename TMap = StdMapRebinder>
bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Fraction::mySup1
private

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

Definition at line 237 of file LighterSternBrocot.h.

Referenced by isSup1().


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