DGtal  0.9.2
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)
36 
37 #define SternBrocot_RECURSES
38 
39 #if !defined SternBrocot_h
40 
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 
101  struct Node {
102 
116  Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
117  Node* ascendant_left1, Node* ascendant_right1,
118  Node* descendant_left1, Node* descendant_right1,
119  Node* inverse1 );
120 
122  Integer p;
124  Integer q;
126  Quotient u;
128  Quotient k;
139  };
140 
149  class Fraction {
150  public:
151  typedef TInteger Integer;
152  typedef TQuotient Quotient;
154  typedef typename SternBrocotTree::Fraction Self;
156  typedef std::pair<Quotient, Quotient> Value;
157  typedef std::vector<Quotient> CFracSequence;
159 
160  // --------------------- std types ------------------------------
161  typedef Value value_type;
162  typedef ConstIterator const_iterator;
163  typedef const value_type & const_reference;
164 
165  private:
167 
168  public:
184  Fraction( Integer aP, Integer aQ,
185  Fraction ancestor = SternBrocotTree::zeroOverOne() );
186 
191  Fraction( Node* sb_node = 0 );
192 
197  Fraction( const Self & other );
198 
204  Self& operator=( const Self & other );
205 
207  bool null() const;
209  Integer p() const;
211  Integer q() const;
213  Quotient u() const;
215  Quotient k() const;
217  Fraction left() const;
219  Fraction right() const;
221  bool even() const;
223  bool odd() const;
228  Fraction father() const;
236  Fraction father( Quotient m ) const;
242  Fraction previousPartial() const;
247  Fraction inverse() const;
254  Fraction partial( Quotient kp ) const;
261  Fraction reduced( Quotient i ) const;
262 
279  void push_back( const std::pair<Quotient, Quotient> & quotient );
280 
291  void pushBack( const std::pair<Quotient, Quotient> & quotient );
292 
300  void getSplit( Fraction & f1, Fraction & f2 ) const;
301 
313  void getSplitBerstel( Fraction & f1, Quotient & nb1,
314  Fraction & f2, Quotient & nb2 ) const;
315 
320  void getCFrac( std::vector<Quotient> & quotients ) const;
321 
327  bool equals( Integer p1, Integer q1 ) const;
328 
334  bool lessThan( Integer p1, Integer q1 ) const;
335 
341  bool moreThan( Integer p1, Integer q1 ) const;
342 
347  bool operator==( const Fraction & other ) const;
348 
353  bool operator!=( const Fraction & other ) const;
354 
359  bool operator<( const Fraction & other ) const;
360 
365  bool operator>( const Fraction & other ) const;
366 
371  void selfDisplay ( std::ostream & out ) const;
372 
377  ConstIterator begin() const;
378 
383  ConstIterator end() const;
384 
390  Fraction median(const Fraction & g) const;
391 
392 
401  Fraction simplestFractionInBetween(const Fraction & other) const;
402 
403  };
404 
405 
406 
407  // ----------------------- Standard services ------------------------------
408  public:
409 
413  ~SternBrocot();
414 
418  static SternBrocot & instance();
419 
421  static Fraction zeroOverOne();
422 
424  static Fraction oneOverZero();
425 
441  static Fraction fraction( Integer p, Integer q,
442  Fraction ancestor = zeroOverOne() );
443 
444  // ----------------------- Interface --------------------------------------
445  public:
446 
452  static void display ( std::ostream & out, const Fraction & f );
453 
458  bool isValid() const;
459 
461  Quotient nbFractions;
462 
463  // ------------------------- Protected Datas ------------------------------
464  private:
465  // ------------------------- Private Datas --------------------------------
466  private:
469 
473 
474  // ------------------------- Hidden services ------------------------------
475  private:
476 
480  SternBrocot();
481 
487  SternBrocot ( const SternBrocot & other );
488 
495  SternBrocot & operator= ( const SternBrocot & other );
496 
497  // ------------------------- Internals ------------------------------------
498  private:
499 
500  }; // end of class SternBrocot
501 
502 
509  // template <typename TInteger, typename TQuotient>
510  // std::ostream&
511  // operator<< ( std::ostream & out,
512  // const typename SternBrocot<TInteger, TQuotient>::Fraction & object );
513 
514 } // namespace DGtal
515 
516 
518 // Includes inline functions.
519 #include "DGtal/arithmetic/SternBrocot.ih"
520 
521 // //
523 
524 #endif // !defined SternBrocot_h
525 
526 #undef SternBrocot_RECURSES
527 #endif // else defined(SternBrocot_RECURSES)
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
Fraction reduced(Quotient i) const
bool isValid() const
ConstIterator begin() const
static SternBrocot & instance()
bool lessThan(Integer p1, Integer q1) const
Node * ascendantLeft
the node that is the left ascendant.
Definition: SternBrocot.h:130
SternBrocot< Integer, Quotient > Self
Definition: SternBrocot.h:82
SternBrocot< TInteger, TQuotient > SternBrocotTree
Definition: SternBrocot.h:153
Fraction previousPartial() const
Quotient k
the depth (1+number of coefficients of its continued fraction).
Definition: SternBrocot.h:128
TQuotient Quotient
Definition: SternBrocot.h:81
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Definition: SternBrocot.h:158
void getSplit(Fraction &f1, Fraction &f2) const
Quotient nbFractions
The total number of fractions in the current tree.
Definition: SternBrocot.h:461
Fraction father() const
bool operator<(const Fraction &other) const
static Fraction oneOverZero()
const value_type & const_reference
Definition: SternBrocot.h:163
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
Node * descendantLeft
the node that is the left descendant or 0 (if none exist).
Definition: SternBrocot.h:134
This fraction is a model of CPositiveIrreducibleFraction.
Definition: SternBrocot.h:149
void getCFrac(std::vector< Quotient > &quotients) const
static Fraction zeroOverOne()
SternBrocot & operator=(const SternBrocot &other)
Quotient u
the quotient (last coefficient of its continued fraction).
Definition: SternBrocot.h:126
std::pair< Quotient, Quotient > Value
Definition: SternBrocot.h:156
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:69
Node * inverse
the node that is its inverse.
Definition: SternBrocot.h:138
void push_back(const std::pair< Quotient, Quotient > &quotient)
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence...
Fraction partial(Quotient kp) const
std::vector< Quotient > CFracSequence
Definition: SternBrocot.h:157
bool operator==(const Fraction &other) const
static SternBrocot * singleton
Singleton class.
Definition: SternBrocot.h:468
DGtal is the top-level namespace which contains all DGtal functions and types.
bool operator!=(const Fraction &other) const
Self & operator=(const Self &other)
SternBrocotTree::Fraction Self
Definition: SternBrocot.h:154
Fraction median(const Fraction &g) const
bool moreThan(Integer p1, Integer q1) const
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *ascendant_left1, Node *ascendant_right1, Node *descendant_left1, Node *descendant_right1, Node *inverse1)
Node * descendantRight
the node that is the right descendant or 0 (if none exist).
Definition: SternBrocot.h:136
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
ConstIterator end() const
bool operator>(const Fraction &other) const
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Definition: SternBrocot.h:155
static void display(std::ostream &out, const Fraction &f)
void selfDisplay(std::ostream &out) const
Integer q
the denominator;
Definition: SternBrocot.h:124
Integer p
the numerator;
Definition: SternBrocot.h:122
void pushBack(const std::pair< Quotient, Quotient > &quotient)
Fraction inverse() const
Fraction simplestFractionInBetween(const Fraction &other) const
Node * ascendantRight
the node that is the right ascendant.
Definition: SternBrocot.h:132
bool equals(Integer p1, Integer q1) const
Fraction(Integer aP, Integer aQ, Fraction ancestor=SternBrocotTree::zeroOverOne())
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition: SternBrocot.h:77