DGtal  0.9.3beta
Public Types | Public Member Functions | Private Attributes
DGtal::SternBrocot< TInteger, TQuotient >::Fraction Class Reference

#include <DGtal/arithmetic/SternBrocot.h>

Collaboration diagram for DGtal::SternBrocot< TInteger, TQuotient >::Fraction:
[legend]

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, 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 ancestor=SternBrocotTree::zeroOverOne())
 
 Fraction (Node *sb_node=0)
 
 Fraction (const Self &other)
 
Selfoperator= (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

NodemyNode
 

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

Member Typedef Documentation

template<typename TInteger, typename TQuotient = int32_t>
typedef std::vector<Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::CFracSequence

Definition at line 157 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_iterator

Definition at line 162 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef const value_type& DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_reference

Definition at line 163 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef InputIteratorWithRankOnSequence<CFracSequence,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::ConstIterator

Definition at line 158 of file SternBrocot.h.

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

Definition at line 151 of file SternBrocot.h.

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

Definition at line 152 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef SternBrocotTree::Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Self

Definition at line 154 of file SternBrocot.h.

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

Definition at line 153 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef NumberTraits<Integer>::UnsignedVersion DGtal::SternBrocot< TInteger, TQuotient >::Fraction::UnsignedInteger

Definition at line 155 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef std::pair<Quotient, Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Value

Definition at line 156 of file SternBrocot.h.

template<typename TInteger, typename TQuotient = int32_t>
typedef Value DGtal::SternBrocot< TInteger, TQuotient >::Fraction::value_type

Definition at line 161 of file SternBrocot.h.

Constructor & Destructor Documentation

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
aPthe numerator (>=0)
aQthe 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.

template<typename TInteger, typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction ( Node sb_node = 0)

Default constructor.

Parameters
sb_nodethe associated node (or 0 for null fraction).
template<typename TInteger, typename TQuotient = int32_t>
DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction ( const Self other)

Copy constructor.

Parameters
otherthe object to clone.

Member Function Documentation

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.
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.
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::equals ( Integer  p1,
Integer  q1 
) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is the fraction p1/q1.
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.
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]
template<typename TInteger, typename TQuotient = int32_t>
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::father ( Quotient  m) const
Parameters
ma 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.
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'.
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.
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
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].
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).
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).
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::lessThan ( Integer  p1,
Integer  q1 
) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is < to the fraction p/q.
template<typename TInteger, typename TQuotient = int32_t>
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::median ( const Fraction g) const
Parameters
gany fraction
Returns
the median of 'this' and g
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::moreThan ( Integer  p1,
Integer  q1 
) const
Parameters
p1a numerator.
q1a denominator.
Returns
'true' if this is > to the fraction p1/q1.
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.
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.
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator!= ( const Fraction other) const
Parameters
otherany fraction.
Returns
'true' iff this is different from other.
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator< ( const Fraction other) const
Parameters
otherany fraction.
Returns
'true' iff this is < to other.
template<typename TInteger, typename TQuotient = int32_t>
Self& DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator= ( const Self other)

Assignment

Parameters
otherthe object to clone.
Returns
a reference to 'this'.
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator== ( const Fraction other) const
Parameters
otherany fraction.
Returns
'true' iff this is equal to other.
template<typename TInteger, typename TQuotient = int32_t>
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator> ( const Fraction other) const
Parameters
otherany fraction.
Returns
'true' iff this is > to other.
template<typename TInteger, typename TQuotient = int32_t>
Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::p ( ) const
Returns
its numerator;
template<typename TInteger, typename TQuotient = int32_t>
Fraction DGtal::SternBrocot< TInteger, TQuotient >::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]
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.
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;
std::back_insert_iterator<Fraction> itout = std::back_inserter( f );
Parameters
quotientthe pair \((m,k+1)\).
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
quotientthe pair \((m,k+1)\).
template<typename TInteger, typename TQuotient = int32_t>
Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::q ( ) const
Returns
its denominator;
template<typename TInteger, typename TQuotient = int32_t>
Fraction DGtal::SternBrocot< TInteger, TQuotient >::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}]
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).
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
outthe output stream where the object is written.
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
otherany fraction
Returns
a fraction NB: \( O(k) where k is the depth of the output fraction\).
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

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

Definition at line 166 of file SternBrocot.h.


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