DGtal 1.3.0
|
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 > "ient) |
void | pushBack (const std::pair< Quotient, Quotient > "ient) |
void | getSplit (Fraction &f1, Fraction &f2) const |
void | getSplitBerstel (Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const |
void | getCFrac (std::vector< Quotient > "ients) 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 |
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.
typedef std::vector<Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::CFracSequence |
Definition at line 156 of file SternBrocot.h.
typedef ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_iterator |
Definition at line 161 of file SternBrocot.h.
typedef const value_type& DGtal::SternBrocot< TInteger, TQuotient >::Fraction::const_reference |
Definition at line 162 of file SternBrocot.h.
typedef InputIteratorWithRankOnSequence<CFracSequence,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::ConstIterator |
Definition at line 157 of file SternBrocot.h.
typedef TInteger DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Integer |
Definition at line 150 of file SternBrocot.h.
typedef TQuotient DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Quotient |
Definition at line 151 of file SternBrocot.h.
typedef SternBrocotTree::Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Self |
Definition at line 153 of file SternBrocot.h.
typedef SternBrocot<TInteger,TQuotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::SternBrocotTree |
Definition at line 152 of file SternBrocot.h.
typedef NumberTraits<Integer>::UnsignedVersion DGtal::SternBrocot< TInteger, TQuotient >::Fraction::UnsignedInteger |
Definition at line 154 of file SternBrocot.h.
typedef std::pair<Quotient, Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Value |
Definition at line 155 of file SternBrocot.h.
typedef Value DGtal::SternBrocot< TInteger, TQuotient >::Fraction::value_type |
Definition at line 160 of file SternBrocot.h.
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.
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.
DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction | ( | Node * | sb_node = 0 | ) |
Default constructor.
sb_node | the associated node (or 0 for null fraction). |
DGtal::SternBrocot< TInteger, TQuotient >::Fraction::Fraction | ( | const Self & | other | ) |
Copy constructor.
other | the object to clone. |
ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::begin | ( | ) | const |
ConstIterator DGtal::SternBrocot< TInteger, TQuotient >::Fraction::end | ( | ) | const |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::equals | ( | Integer | p1, |
Integer | q1 | ||
) | const |
p1 | a numerator. |
q1 | a denominator. |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::even | ( | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::father | ( | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::father | ( | Quotient | m | ) | const |
m | a quotient between 1 and uk-1. |
void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::getCFrac | ( | std::vector< Quotient > & | quotients | ) | const |
quotients | (returns) the coefficients of the continued fraction of 'this'. |
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].
f1 | (returns) the left part of the split. |
f2 | (returns) the right part of the split. |
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.
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 |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::inverse | ( | ) | const |
Quotient DGtal::SternBrocot< TInteger, TQuotient >::Fraction::k | ( | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::left | ( | ) | const |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::lessThan | ( | Integer | p1, |
Integer | q1 | ||
) | const |
p1 | a numerator. |
q1 | a denominator. |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::median | ( | const Fraction & | g | ) | const |
g | any fraction |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::moreThan | ( | Integer | p1, |
Integer | q1 | ||
) | const |
p1 | a numerator. |
q1 | a denominator. |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::null | ( | ) | const |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::odd | ( | ) | const |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator!= | ( | const Fraction & | other | ) | const |
other | any fraction. |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator< | ( | const Fraction & | other | ) | const |
other | any fraction. |
Self & DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator= | ( | const Self & | other | ) |
Assignment
other | the object to clone. |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator== | ( | const Fraction & | other | ) | const |
other | any fraction. |
bool DGtal::SternBrocot< TInteger, TQuotient >::Fraction::operator> | ( | const Fraction & | other | ) | const |
other | any fraction. |
Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::p | ( | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::partial | ( | Quotient | kp | ) | const |
kp | the chosen depth of the partial fraction (kp <= k()). |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::previousPartial | ( | ) | const |
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
quotient | the pair \((m,k+1)\). |
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.
quotient | the pair \((m,k+1)\). |
Integer DGtal::SternBrocot< TInteger, TQuotient >::Fraction::q | ( | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::reduced | ( | Quotient | i | ) | const |
Fraction DGtal::SternBrocot< TInteger, TQuotient >::Fraction::right | ( | ) | const |
void DGtal::SternBrocot< TInteger, TQuotient >::Fraction::selfDisplay | ( | std::ostream & | out | ) | const |
Writes/Displays the fraction on an output stream.
out | the output stream where the object is written. |
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.
other | any fraction |
Quotient DGtal::SternBrocot< TInteger, TQuotient >::Fraction::u | ( | ) | const |
|
private |
Definition at line 165 of file SternBrocot.h.