DGtal  1.2.0
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
53 namespace 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;
153  typedef typename SternBrocotTree::Fraction Self;
155  typedef std::pair<Quotient, Quotient> Value;
156  typedef std::vector<Quotient> CFracSequence;
158
159  // --------------------- std types ------------------------------
160  typedef Value value_type;
162  typedef const value_type & const_reference;
163
164  private:
166
167  public:
184  Fraction ancestor = SternBrocotTree::zeroOverOne() );
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;
218  Fraction right() const;
220  bool even() const;
222  bool odd() const;
227  Fraction father() const;
246  Fraction inverse() const;
253  Fraction partial( Quotient kp ) 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
312  void getSplitBerstel( Fraction & f1, Quotient & nb1,
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
417  static SternBrocot & instance();
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
494  SternBrocot & operator= ( const SternBrocot & other );
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
Self & operator=(const Self &other)
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
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 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
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
SternBrocot & operator=(const SternBrocot &other)
SternBrocot< Integer, Quotient > Self
Definition: SternBrocot.h:82
static Fraction oneOverZero()
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
static SternBrocot & instance()
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