DGtal 1.3.0
|
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it progressively and to navigate within fractions in O(1) time for most operations. It is well known that the structure of this tree is a coding of the continued fraction representation of fractions. More...
#include <DGtal/arithmetic/SternBrocot.h>
Data Structures | |
class | Fraction |
This fraction is a model of CPositiveIrreducibleFraction. More... | |
struct | Node |
Public Types | |
typedef TInteger | Integer |
typedef TQuotient | Quotient |
typedef SternBrocot< Integer, Quotient > | Self |
Public Member Functions | |
BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >)) | |
~SternBrocot () | |
bool | isValid () const |
Static Public Member Functions | |
static SternBrocot & | instance () |
static Fraction | zeroOverOne () |
static Fraction | oneOverZero () |
static Fraction | fraction (Integer p, Integer q, Fraction ancestor=zeroOverOne()) |
static void | display (std::ostream &out, const Fraction &f) |
Data Fields | |
Quotient | nbFractions |
The total number of fractions in the current tree. More... | |
Private Member Functions | |
SternBrocot () | |
SternBrocot (const SternBrocot &other) | |
SternBrocot & | operator= (const SternBrocot &other) |
Private Attributes | |
Node * | myZeroOverOne |
Node * | myOneOverZero |
Node * | myOneOverOne |
Static Private Attributes | |
static SternBrocot * | singleton |
Singleton class. More... | |
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it progressively and to navigate within fractions in O(1) time for most operations. It is well known that the structure of this tree is a coding of the continued fraction representation of fractions.
Description of template class 'SternBrocot'
This class is not to be instantiated, since it is useless to duplicate it. Use static method SternBrocot::fraction to obtain your fractions.
TInteger | the integral type chosen for the fractions. |
TQuotient | the integral type chosen for the quotients/coefficients or depth (may be "smaller" than TInteger, since they are generally much smaller than the fraction itself). |
Definition at line 77 of file SternBrocot.h.
typedef TInteger DGtal::SternBrocot< TInteger, TQuotient >::Integer |
Definition at line 80 of file SternBrocot.h.
typedef TQuotient DGtal::SternBrocot< TInteger, TQuotient >::Quotient |
Definition at line 81 of file SternBrocot.h.
typedef SternBrocot<Integer,Quotient> DGtal::SternBrocot< TInteger, TQuotient >::Self |
Definition at line 82 of file SternBrocot.h.
DGtal::SternBrocot< TInteger, TQuotient >::~SternBrocot | ( | ) |
Destructor.
|
private |
Constructor. Hidden since singleton class.
|
private |
Copy constructor.
other | the object to clone. Forbidden by default. |
DGtal::SternBrocot< TInteger, TQuotient >::BOOST_CONCEPT_ASSERT | ( | (concepts::CInteger< Integer >) | ) |
|
static |
Writes/Displays the fraction on an output stream.
out | the output stream where the object is written. |
f | the fraction to display. |
|
static |
Any fraction p/q. Complexity is in \( \sum_i u_i \), where u_i are the partial quotients of p/q.
p | the numerator (>=0) |
q | the denominator (>=0) |
ancestor | (optional) any ancestor of p/q in the tree (for speed-up). |
NB: Complexity is bounded by \( 2 \sum_i u_i \), where u_i are the partial quotients of p/q.
|
static |
bool DGtal::SternBrocot< TInteger, TQuotient >::isValid | ( | ) | const |
Checks the validity/consistency of the object.
|
static |
The fraction 1/0
|
private |
Assignment.
other | the object to copy. |
|
static |
The fraction 0/1
|
private |
Definition at line 471 of file SternBrocot.h.
|
private |
Definition at line 470 of file SternBrocot.h.
|
private |
Definition at line 469 of file SternBrocot.h.
Quotient DGtal::SternBrocot< TInteger, TQuotient >::nbFractions |
The total number of fractions in the current tree.
Definition at line 460 of file SternBrocot.h.
|
staticprivate |
Singleton class.
Definition at line 467 of file SternBrocot.h.