DGtal  1.5.beta
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)
37 #define LightSternBrocot_RECURSES
38 
39 #if !defined LightSternBrocot_h
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 
134  struct Node {
135 
147  Node* ascendant );
148 
167 
169  inline bool even() const {
171  }
173  inline bool odd() const {
174  return NumberTraits<Quotient>::odd( k );
175  }
177  inline bool isSameDepthLeft() const {
178  return odd();
179  }
180 
181  };
182 
192  class Fraction {
193  public:
194  typedef TInteger Integer;
195  typedef TQuotient Quotient;
197  typedef typename SternBrocotTree::Fraction Self;
199  typedef std::pair<Quotient, Quotient> Value;
200  typedef std::vector<Quotient> CFracSequence;
202 
203  // --------------------- std types ------------------------------
204  typedef Value value_type;
206  typedef const value_type & const_reference;
207 
208 
209  private:
214  bool mySup1;
215 
216  public:
228 
236  Fraction( Node* sb_node = 0, bool sup1 = false );
237 
242  Fraction( const Self & other );
243 
249  Self& operator=( const Self & other );
250 
252  bool null() const;
254  Integer p() const;
256  Integer q() const;
258  Quotient u() const;
260  Quotient k() const;
261 
264  bool isSup1() const { return mySup1; }
266  Quotient trueK() const { return myNode->k; }
267 
268  protected:
271  Fraction next( Quotient v ) const;
274  Fraction next1( Quotient v ) const;
275  public:
276 
278  Fraction left() const;
280  Fraction right() const;
282  bool even() const;
284  bool odd() const;
294  bool isAncestorDirect() const;
295 
300  Fraction father() const;
301 
320  Fraction inverse() const;
327  Fraction partial( Quotient kp ) const;
335 
352  void push_back( const std::pair<Quotient, Quotient> & quotient );
353 
364  void pushBack( const std::pair<Quotient, Quotient> & quotient );
365 
373  void getSplit( Fraction & f1, Fraction & f2 ) const;
374 
386  void getSplitBerstel( Fraction & f1, Quotient & nb1,
387  Fraction & f2, Quotient & nb2 ) const;
388 
393  void getCFrac( std::vector<Quotient> & quotients ) const;
394 
400  bool equals( Integer p1, Integer q1 ) const;
401 
407  bool lessThan( Integer p1, Integer q1 ) const;
408 
414  bool moreThan( Integer p1, Integer q1 ) const;
415 
420  bool operator==( const Fraction & other ) const;
421 
426  bool operator!=( const Fraction & other ) const;
427 
432  bool operator<( const Fraction & other ) const;
433 
438  bool operator>( const Fraction & other ) const;
439 
444  void selfDisplay ( std::ostream & out ) const;
445 
451 
457 
458  };
459 
460 
461 
462  // ----------------------- Standard services ------------------------------
463  public:
468 
473 
476 
479 
494  Fraction ancestor = zeroOverOne() );
495 
496  // ----------------------- Interface --------------------------------------
497  public:
498 
504  static void display ( std::ostream & out, const Fraction & f );
505 
510  bool isValid() const;
511 
514 
515  // ------------------------- Protected Datas ------------------------------
516  protected:
517  // ------------------------- Private Datas --------------------------------
518  private:
519 
522 
523 
524  // ------------------------- Datas ----------------------------------------
525  private:
526 
530 
531  // ------------------------- Hidden services ------------------------------
532  protected:
533 
534  private:
539 
540 
547 
555 
556  // ------------------------- Internals ------------------------------------
557  private:
558 
559  }; // end of class LightSternBrocot
560 
561 
568  // template <typename TInteger, typename TQuotient, typename TMap>
569  // std::ostream&
570  // operator<< ( std::ostream & out,
571  // const typename LightSternBrocot<TInteger, TQuotient, TMap>::Fraction & object );
572 
573 } // namespace DGtal
574 
575 
577 // Includes inline functions.
578 #include "DGtal/arithmetic/LightSternBrocot.ih"
579 
580 // //
582 
583 #endif // !defined LightSternBrocot_h
584 
585 #undef LightSternBrocot_RECURSES
586 #endif // else defined(LightSternBrocot_RECURSES)
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence....
This fraction is a model of CPositiveIrreducibleFraction.
Fraction next1(Quotient v) const
std::pair< Quotient, Quotient > Value
LightSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
SternBrocotTree::Fraction Self
Self & operator=(const Self &other)
bool mySup1
When 'true', the fraction is greater than 1/1 (to its right).
bool operator>(const Fraction &other) const
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Fraction partial(Quotient kp) const
bool equals(Integer p1, Integer q1) const
Fraction(Node *sb_node=0, bool sup1=false)
bool moreThan(Integer p1, Integer q1) const
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Fraction reduced(Quotient i) const
bool lessThan(Integer p1, Integer q1) const
void pushBack(const std::pair< Quotient, Quotient > &quotient)
bool operator<(const Fraction &other) const
void push_back(const std::pair< Quotient, Quotient > &quotient)
Fraction next(Quotient v) const
std::vector< Quotient > CFracSequence
ConstIterator begin() const
void getCFrac(std::vector< Quotient > &quotients) const
void selfDisplay(std::ostream &out) const
bool operator==(const Fraction &other) const
Fraction father(Quotient m) const
void getSplit(Fraction &f1, Fraction &f2) const
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
bool operator!=(const Fraction &other) const
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
LightSternBrocot< TInteger, TQuotient, TMap > Self
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
static void display(std::ostream &out, const Fraction &f)
static LightSternBrocot * singleton
Singleton class.
TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
LightSternBrocot(const LightSternBrocot &other)
static LightSternBrocot & instance()
Quotient nbFractions
The total number of fractions in the current tree.
static Fraction oneOverZero()
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
LightSternBrocot & operator=(const LightSternBrocot &other)
static Fraction zeroOverOne()
DGtal is the top-level namespace which contains all DGtal functions and types.
Integer q
the denominator;
Quotient k
the depth (1+number of coefficients of its continued fraction).
Node * ascendant
A pointer to the node that is the preceding principal convergent.
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *ascendant)
Quotient u
the quotient (last coefficient of its continued fraction).
std::decay< T >::type UnsignedVersion
Alias to the unsigned version of the number type.
Definition: NumberTraits.h:90
static bool even(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:173
static bool odd(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:183
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:88