DGtal 1.3.0
Loading...
Searching...
No Matches
SternBrocot.h
1
17#pragma once
18
33#if defined(SternBrocot_RECURSES)
34#error Recursive header files inclusion detected in SternBrocot.h
35#else // defined(SternBrocot_RECURSES)
37#define SternBrocot_RECURSES
38
39#if !defined SternBrocot_h
41#define SternBrocot_h
42
44// Inclusions
45#include <iostream>
46#include <vector>
47#include "DGtal/base/Common.h"
48#include "DGtal/base/InputIteratorWithRankOnSequence.h"
49#include "DGtal/kernel/CInteger.h"
50#include "DGtal/kernel/NumberTraits.h"
52
53namespace DGtal
54{
55
57 // template class SternBrocot
76 template <typename TInteger, typename TQuotient = int32_t>
78 {
79 public:
80 typedef TInteger Integer;
81 typedef TQuotient Quotient;
83
85
86 public:
87
100 struct Node {
101
116 Node* ascendant_left1, Node* ascendant_right1,
117 Node* descendant_left1, Node* descendant_right1,
118 Node* inverse1 );
119
138 };
139
148 class Fraction {
149 public:
150 typedef TInteger Integer;
151 typedef TQuotient Quotient;
155 typedef std::pair<Quotient, Quotient> Value;
156 typedef std::vector<Quotient> CFracSequence;
158
159 // --------------------- std types ------------------------------
163
164 private:
166
167 public:
185
190 Fraction( Node* sb_node = 0 );
191
196 Fraction( const Self & other );
197
203 Self& operator=( const Self & other );
204
206 bool null() const;
208 Integer p() const;
210 Integer q() const;
212 Quotient u() const;
214 Quotient k() const;
216 Fraction left() const;
220 bool even() const;
222 bool odd() const;
261
278 void push_back( const std::pair<Quotient, Quotient> & quotient );
279
290 void pushBack( const std::pair<Quotient, Quotient> & quotient );
291
299 void getSplit( Fraction & f1, Fraction & f2 ) const;
300
313 Fraction & f2, Quotient & nb2 ) const;
314
319 void getCFrac( std::vector<Quotient> & quotients ) const;
320
326 bool equals( Integer p1, Integer q1 ) const;
327
333 bool lessThan( Integer p1, Integer q1 ) const;
334
340 bool moreThan( Integer p1, Integer q1 ) const;
341
346 bool operator==( const Fraction & other ) const;
347
352 bool operator!=( const Fraction & other ) const;
353
358 bool operator<( const Fraction & other ) const;
359
364 bool operator>( const Fraction & other ) const;
365
370 void selfDisplay ( std::ostream & out ) const;
371
377
383
389 Fraction median(const Fraction & g) const;
390
391
401
402 };
403
404
405
406 // ----------------------- Standard services ------------------------------
407 public:
408
413
418
421
424
441 Fraction ancestor = zeroOverOne() );
442
443 // ----------------------- Interface --------------------------------------
444 public:
445
451 static void display ( std::ostream & out, const Fraction & f );
452
457 bool isValid() const;
458
461
462 // ------------------------- Protected Datas ------------------------------
463 private:
464 // ------------------------- Private Datas --------------------------------
465 private:
468
472
473 // ------------------------- Hidden services ------------------------------
474 private:
475
480
486 SternBrocot ( const SternBrocot & other );
487
495
496 // ------------------------- Internals ------------------------------------
497 private:
498
499 }; // end of class SternBrocot
500
501
508 // template <typename TInteger, typename TQuotient>
509 // std::ostream&
510 // operator<< ( std::ostream & out,
511 // const typename SternBrocot<TInteger, TQuotient>::Fraction & object );
512
513} // namespace DGtal
514
515
517// Includes inline functions.
518#include "DGtal/arithmetic/SternBrocot.ih"
519
520// //
522
523#endif // !defined SternBrocot_h
524
525#undef SternBrocot_RECURSES
526#endif // else defined(SternBrocot_RECURSES)
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence....
This fraction is a model of CPositiveIrreducibleFraction.
Definition: SternBrocot.h:148
std::pair< Quotient, Quotient > Value
Definition: SternBrocot.h:155
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Definition: SternBrocot.h:157
ConstIterator end() const
void push_back(const std::pair< Quotient, Quotient > &quotient)
bool operator==(const Fraction &other) const
Fraction partial(Quotient kp) const
void getSplit(Fraction &f1, Fraction &f2) const
Fraction reduced(Quotient i) const
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Definition: SternBrocot.h:154
void getCFrac(std::vector< Quotient > &quotients) const
std::vector< Quotient > CFracSequence
Definition: SternBrocot.h:156
Fraction previousPartial() const
bool operator>(const Fraction &other) const
void pushBack(const std::pair< Quotient, Quotient > &quotient)
Fraction median(const Fraction &g) const
bool lessThan(Integer p1, Integer q1) const
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
const value_type & const_reference
Definition: SternBrocot.h:162
SternBrocotTree::Fraction Self
Definition: SternBrocot.h:153
void selfDisplay(std::ostream &out) const
Fraction(const Self &other)
bool operator!=(const Fraction &other) const
bool operator<(const Fraction &other) const
bool moreThan(Integer p1, Integer q1) const
SternBrocot< TInteger, TQuotient > SternBrocotTree
Definition: SternBrocot.h:152
Fraction(Integer aP, Integer aQ, Fraction ancestor=SternBrocotTree::zeroOverOne())
bool equals(Integer p1, Integer q1) const
Self & operator=(const Self &other)
Fraction simplestFractionInBetween(const Fraction &other) const
Fraction father(Quotient m) const
ConstIterator begin() const
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition: SternBrocot.h:78
static SternBrocot * singleton
Singleton class.
Definition: SternBrocot.h:467
TQuotient Quotient
Definition: SternBrocot.h:81
static SternBrocot & instance()
static Fraction zeroOverOne()
static void display(std::ostream &out, const Fraction &f)
Quotient nbFractions
The total number of fractions in the current tree.
Definition: SternBrocot.h:460
SternBrocot & operator=(const SternBrocot &other)
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
SternBrocot< Integer, Quotient > Self
Definition: SternBrocot.h:82
static Fraction oneOverZero()
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
bool isValid() const
SternBrocot(const SternBrocot &other)
DGtal is the top-level namespace which contains all DGtal functions and types.
std::decay< T >::type UnsignedVersion
Alias to the unsigned version of the number type.
Definition: NumberTraits.h:90
Integer q
the denominator;
Definition: SternBrocot.h:123
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *ascendant_left1, Node *ascendant_right1, Node *descendant_left1, Node *descendant_right1, Node *inverse1)
Node * inverse
the node that is its inverse.
Definition: SternBrocot.h:137
Node * ascendantRight
the node that is the right ascendant.
Definition: SternBrocot.h:131
Quotient k
the depth (1+number of coefficients of its continued fraction).
Definition: SternBrocot.h:127
Quotient u
the quotient (last coefficient of its continued fraction).
Definition: SternBrocot.h:125
Node * ascendantLeft
the node that is the left ascendant.
Definition: SternBrocot.h:129
Integer p
the numerator;
Definition: SternBrocot.h:121
Node * descendantLeft
the node that is the left descendant or 0 (if none exist).
Definition: SternBrocot.h:133
Node * descendantRight
the node that is the right descendant or 0 (if none exist).
Definition: SternBrocot.h:135
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:88