DGtal  0.9.2
LightSternBrocot.h
1 
17 #pragma once
18 
33 #if defined(LightSternBrocot_RECURSES)
34 #error Recursive header files inclusion detected in LightSternBrocot.h
35 #else // defined(LightSternBrocot_RECURSES)
36 
37 #define LightSternBrocot_RECURSES
38 
39 #if !defined LightSternBrocot_h
40 
41 #define LightSternBrocot_h
42 
44 // Inclusions
45 #include <iostream>
46 #include <vector>
47 #include "DGtal/base/Common.h"
48 #include "DGtal/base/StdRebinders.h"
49 #include "DGtal/base/InputIteratorWithRankOnSequence.h"
50 #include "DGtal/kernel/CInteger.h"
51 #include "DGtal/kernel/NumberTraits.h"
53 
54 namespace DGtal
55 {
56 
58  // template class LightSternBrocot
105  template <typename TInteger, typename TQuotient,
106  typename TMap = StdMapRebinder>
108  {
109  public:
110  typedef TInteger Integer;
111  typedef TQuotient Quotient;
112  typedef TMap Map;
114 
116 
117  struct Node;
118  typedef typename TMap:: template Rebinder<Quotient, Node*>::Type MapQuotientToNode;
119 
120  public:
121 
135  struct Node {
136 
147  Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
148  Node* ascendant );
149 
151  Integer p;
153  Integer q;
155  Quotient u;
157  Quotient k;
163  MapQuotientToNode descendant;
167  MapQuotientToNode descendant2;
168 
170  inline bool even() const {
171  return NumberTraits<Quotient>::even( k );
172  }
174  inline bool odd() const {
175  return NumberTraits<Quotient>::odd( k );
176  }
178  inline bool isSameDepthLeft() const {
179  return odd();
180  }
181 
182  };
183 
193  class Fraction {
194  public:
195  typedef TInteger Integer;
196  typedef TQuotient Quotient;
198  typedef typename SternBrocotTree::Fraction Self;
200  typedef std::pair<Quotient, Quotient> Value;
201  typedef std::vector<Quotient> CFracSequence;
203 
204  // --------------------- std types ------------------------------
205  typedef Value value_type;
206  typedef ConstIterator const_iterator;
207  typedef const value_type & const_reference;
208 
209 
210  private:
215  bool mySup1;
216 
217  public:
227  Fraction( Integer aP, Integer aQ,
229 
237  Fraction( Node* sb_node = 0, bool sup1 = false );
238 
243  Fraction( const Self & other );
244 
250  Self& operator=( const Self & other );
251 
253  bool null() const;
255  Integer p() const;
257  Integer q() const;
259  Quotient u() const;
261  Quotient k() const;
262 
265  bool isSup1() const { return mySup1; }
267  Quotient trueK() const { return myNode->k; }
268 
269  protected:
272  Fraction next( Quotient v ) const;
275  Fraction next1( Quotient v ) const;
276  public:
277 
279  Fraction left() const;
281  Fraction right() const;
283  bool even() const;
285  bool odd() const;
291  Fraction ancestor() const;
295  bool isAncestorDirect() const;
296 
301  Fraction father() const;
302 
310  Fraction father( Quotient m ) const;
316  Fraction previousPartial() const;
321  Fraction inverse() const;
328  Fraction partial( Quotient kp ) const;
335  Fraction reduced( Quotient i ) const;
336 
353  void push_back( const std::pair<Quotient, Quotient> & quotient );
354 
365  void pushBack( const std::pair<Quotient, Quotient> & quotient );
366 
374  void getSplit( Fraction & f1, Fraction & f2 ) const;
375 
387  void getSplitBerstel( Fraction & f1, Quotient & nb1,
388  Fraction & f2, Quotient & nb2 ) const;
389 
394  void getCFrac( std::vector<Quotient> & quotients ) const;
395 
401  bool equals( Integer p1, Integer q1 ) const;
402 
408  bool lessThan( Integer p1, Integer q1 ) const;
409 
415  bool moreThan( Integer p1, Integer q1 ) const;
416 
421  bool operator==( const Fraction & other ) const;
422 
427  bool operator!=( const Fraction & other ) const;
428 
433  bool operator<( const Fraction & other ) const;
434 
439  bool operator>( const Fraction & other ) const;
440 
445  void selfDisplay ( std::ostream & out ) const;
446 
451  ConstIterator begin() const;
452 
457  ConstIterator end() const;
458 
459  };
460 
461 
462 
463  // ----------------------- Standard services ------------------------------
464  public:
469 
473  static LightSternBrocot & instance();
474 
476  static Fraction zeroOverOne();
477 
479  static Fraction oneOverZero();
480 
494  static Fraction fraction( Integer p, Integer q,
495  Fraction ancestor = zeroOverOne() );
496 
497  // ----------------------- Interface --------------------------------------
498  public:
499 
505  static void display ( std::ostream & out, const Fraction & f );
506 
511  bool isValid() const;
512 
514  Quotient nbFractions;
515 
516  // ------------------------- Protected Datas ------------------------------
517  protected:
518  // ------------------------- Private Datas --------------------------------
519  private:
520 
523 
524 
525  // ------------------------- Datas ----------------------------------------
526  private:
527 
531 
532  // ------------------------- Hidden services ------------------------------
533  protected:
534 
535  private:
540 
541 
547  LightSternBrocot ( const LightSternBrocot & other );
548 
555  LightSternBrocot & operator= ( const LightSternBrocot & other );
556 
557  // ------------------------- Internals ------------------------------------
558  private:
559 
560  }; // end of class LightSternBrocot
561 
562 
569  // template <typename TInteger, typename TQuotient, typename TMap>
570  // std::ostream&
571  // operator<< ( std::ostream & out,
572  // const typename LightSternBrocot<TInteger, TQuotient, TMap>::Fraction & object );
573 
574 } // namespace DGtal
575 
576 
578 // Includes inline functions.
579 #include "DGtal/arithmetic/LightSternBrocot.ih"
580 
581 // //
583 
584 #endif // !defined LightSternBrocot_h
585 
586 #undef LightSternBrocot_RECURSES
587 #endif // else defined(LightSternBrocot_RECURSES)
Quotient u
the quotient (last coefficient of its continued fraction).
bool moreThan(Integer p1, Integer q1) const
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Quotient nbFractions
The total number of fractions in the current tree.
std::pair< Quotient, Quotient > Value
static Fraction zeroOverOne()
LightSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *ascendant)
bool operator<(const Fraction &other) const
static LightSternBrocot & instance()
bool equals(Integer p1, Integer q1) const
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Fraction next(Quotient v) const
Integer p
the numerator;
Integer q
the denominator;
void getSplit(Fraction &f1, Fraction &f2) const
Fraction reduced(Quotient i) const
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
LightSternBrocot< TInteger, TQuotient, TMap > Self
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
bool operator>(const Fraction &other) const
Self & operator=(const Self &other)
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:69
void selfDisplay(std::ostream &out) const
void getCFrac(std::vector< Quotient > &quotients) const
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence...
ConstIterator begin() const
bool mySup1
When 'true', the fraction is greater than 1/1 (to its right).
ConstIterator end() const
Fraction next1(Quotient v) const
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
static bool even(ParamType aT)
Definition: NumberTraits.h:162
bool operator==(const Fraction &other) const
DGtal is the top-level namespace which contains all DGtal functions and types.
std::vector< Quotient > CFracSequence
static void display(std::ostream &out, const Fraction &f)
Fraction partial(Quotient kp) const
Quotient k
the depth (1+number of coefficients of its continued fraction).
bool operator!=(const Fraction &other) const
This fraction is a model of CPositiveIrreducibleFraction.
static LightSternBrocot * singleton
Singleton class.
LightSternBrocot & operator=(const LightSternBrocot &other)
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
bool lessThan(Integer p1, Integer q1) const
void push_back(const std::pair< Quotient, Quotient > &quotient)
SternBrocotTree::Fraction Self
Node * ascendant
A pointer to the node that is the preceding principal convergent.
void pushBack(const std::pair< Quotient, Quotient > &quotient)
static Fraction oneOverZero()
static bool odd(ParamType aT)
Definition: NumberTraits.h:170