- Generated on Sat Nov 9 2024 12:45:01 for DGtal by
1.9.1
|
DGtal
1.5.beta
|
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/LighterSternBrocot.h>
Data Structures | |
| class | Fraction |
| This fraction is a model of CPositiveIrreducibleFraction. More... | |
| struct | Node |
Public Types | |
| typedef TInteger | Integer |
| typedef TQuotient | Quotient |
| typedef TMap | Map |
| typedef LighterSternBrocot< TInteger, TQuotient, TMap > | Self |
| typedef TMap::template Rebinder< Quotient, Node * >::Type | MapQuotientToNode |
Public Member Functions | |
| BOOST_CONCEPT_ASSERT ((concepts::CInteger< Integer >)) | |
| ~LighterSternBrocot () | |
| bool | isValid () const |
Static Public Member Functions | |
| static LighterSternBrocot & | instance () |
| static Fraction | zeroOverOne () |
| static Fraction | oneOverZero () |
| static Fraction | oneOverOne () |
| static Fraction | fraction (Integer p, Integer q, Fraction ancestor=oneOverZero()) |
| 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 | |
| LighterSternBrocot () | |
| LighterSternBrocot (const LighterSternBrocot &other) | |
| LighterSternBrocot & | operator= (const LighterSternBrocot &other) |
Private Attributes | |
| Node * | myOneOverZero |
| Node * | myOneOverOne |
Static Private Attributes | |
| static LighterSternBrocot * | 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 'LighterSternBrocot'
There are two main differences with the class SternBrocot. The first one is that inverses are not stored. With this optimization, there are twice less nodes and each node is lighter. The second one lies in the access to the children of a node. Here, a map type M is provided so that a node [u_0; u_1, ..., u_n] can access its child node [u_0; u_1, ..., u_n, k] in the time of the operation M::operator[]. This representation is also different from LightSternBrocot in the sense that nodes have only one set of child nodes and that only fractions greater than 1/1 are stored.
In this representation, the fraction 1/1 has depth 0, like 2/1, 3/1, etc. Furthermore, each fraction [u_0,...,u_n] has an origin which is the fraction [u_0,...,u_{n-1},1]. It is the top extremity of this branch. The origin has depth n-1 since [u_0,...,u_{n-1},1] = [u_0,...,u_{n-1}+1]. Inversely a k-child of [u_0,...,u_n], for k >= 2, is the fraction [u_0,...,u_n - 1, k]. A 1-child of a fraction f is itself, except for the fraction 1/0 where its 1-child is 1/1 by convention.
In practice, also this class has supposedly a better complexity than SternBrocot, it is 1% slower for integers smaller than 10^9 and 5% slower for integers smaller than 10^4. Note however that it takes like 7 times less memory (and asymptotically less when the number of computations tends toward infinity).
This class is not to be instantiated, since it is useless to duplicate it. Use static method LighterSternBrocot::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). |
| TMap | the rebinder type for defining an association TQuotient -> LighterSternBrocot::Node*. For instance, StdMapRebinder is fine. |
Definition at line 108 of file LighterSternBrocot.h.
| typedef TInteger DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Integer |
Definition at line 111 of file LighterSternBrocot.h.
| typedef TMap DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Map |
Definition at line 113 of file LighterSternBrocot.h.
| typedef TMap:: template Rebinder<Quotient, Node*>::Type DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::MapQuotientToNode |
Definition at line 119 of file LighterSternBrocot.h.
| typedef TQuotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Quotient |
Definition at line 112 of file LighterSternBrocot.h.
| typedef LighterSternBrocot<TInteger,TQuotient,TMap> DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::Self |
Definition at line 114 of file LighterSternBrocot.h.
| DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::~LighterSternBrocot | ( | ) |
Destructor.
|
private |
Constructor. Hidden since singleton class.
|
private |
Copy constructor.
| other | the object to clone. Forbidden by default. |
| DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::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 O(n) where n is the depth of continued fraction of p/q.
| p | the numerator (>=0) |
| q | the denominator (>=0) |
| ancestor | (optional) unused in this representation. |
|
static |
| bool DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::isValid | ( | ) | const |
Checks the validity/consistency of the object.
|
static |
The fraction 1/1
|
static |
The fraction 1/0
|
private |
Assignment.
| other | the object to copy. |
|
static |
The fraction 0/1
|
private |
Definition at line 551 of file LighterSternBrocot.h.
|
private |
Definition at line 550 of file LighterSternBrocot.h.
| Quotient DGtal::LighterSternBrocot< TInteger, TQuotient, TMap >::nbFractions |
The total number of fractions in the current tree.
Definition at line 540 of file LighterSternBrocot.h.
|
staticprivate |
Singleton class.
Definition at line 548 of file LighterSternBrocot.h.
1.9.1