DGtal  1.2.beta
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 
100  struct Node {
101 
115  Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
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:
183  Fraction( Integer aP, Integer aQ,
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;
235  Fraction father( Quotient m ) const;
241  Fraction previousPartial() const;
246  Fraction inverse() const;
253  Fraction partial( Quotient kp ) const;
260  Fraction reduced( Quotient i ) 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 
376  ConstIterator begin() const;
377 
382  ConstIterator end() const;
383 
389  Fraction median(const Fraction & g) const;
390 
391 
400  Fraction simplestFractionInBetween(const Fraction & other) const;
401 
402  };
403 
404 
405 
406  // ----------------------- Standard services ------------------------------
407  public:
408 
412  ~SternBrocot();
413 
417  static SternBrocot & instance();
418 
420  static Fraction zeroOverOne();
421 
423  static Fraction oneOverZero();
424 
440  static Fraction fraction( Integer p, Integer q,
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 
479  SternBrocot();
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)
ConstIterator end() const
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
void getSplit(Fraction &f1, Fraction &f2) const
bool equals(Integer p1, Integer q1) const
static SternBrocot & instance()
Node * ascendantLeft
the node that is the left ascendant.
Definition: SternBrocot.h:129
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
SternBrocot< Integer, Quotient > Self
Definition: SternBrocot.h:82
SternBrocot< TInteger, TQuotient > SternBrocotTree
Definition: SternBrocot.h:152
Fraction reduced(Quotient i) const
bool operator==(const Fraction &other) const
static SternBrocot * singleton
Singleton class.
Definition: SternBrocot.h:467
Quotient k
the depth (1+number of coefficients of its continued fraction).
Definition: SternBrocot.h:127
TQuotient Quotient
Definition: SternBrocot.h:81
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Definition: SternBrocot.h:157
Quotient nbFractions
The total number of fractions in the current tree.
Definition: SternBrocot.h:460
bool operator<(const Fraction &other) const
static Fraction oneOverZero()
bool operator!=(const Fraction &other) const
const value_type & const_reference
Definition: SternBrocot.h:162
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
Fraction median(const Fraction &g) const
Node * descendantLeft
the node that is the left descendant or 0 (if none exist).
Definition: SternBrocot.h:133
This fraction is a model of CPositiveIrreducibleFraction.
Definition: SternBrocot.h:148
static Fraction zeroOverOne()
Fraction partial(Quotient kp) const
SternBrocot & operator=(const SternBrocot &other)
Quotient u
the quotient (last coefficient of its continued fraction).
Definition: SternBrocot.h:125
bool moreThan(Integer p1, Integer q1) const
std::pair< Quotient, Quotient > Value
Definition: SternBrocot.h:155
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
bool operator>(const Fraction &other) const
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:531
Node * inverse
the node that is its inverse.
Definition: SternBrocot.h:137
void getCFrac(std::vector< Quotient > &quotients) const
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...
std::vector< Quotient > CFracSequence
Definition: SternBrocot.h:156
Fraction simplestFractionInBetween(const Fraction &other) const
DGtal is the top-level namespace which contains all DGtal functions and types.
Self & operator=(const Self &other)
SternBrocotTree::Fraction Self
Definition: SternBrocot.h:153
void selfDisplay(std::ostream &out) 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:135
Fraction previousPartial() const
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Definition: SternBrocot.h:154
static void display(std::ostream &out, const Fraction &f)
Integer q
the denominator;
Definition: SternBrocot.h:123
Integer p
the numerator;
Definition: SternBrocot.h:121
void pushBack(const std::pair< Quotient, Quotient > &quotient)
ConstIterator begin() const
bool lessThan(Integer p1, Integer q1) const
Node * ascendantRight
the node that is the right ascendant.
Definition: SternBrocot.h:131
bool isValid() 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