DGtal  0.9.2
LighterSternBrocot.h
1 
17 #pragma once
18 
33 #if defined(LighterSternBrocot_RECURSES)
34 #error Recursive header files inclusion detected in LighterSternBrocot.h
35 #else // defined(LighterSternBrocot_RECURSES)
36 
37 #define LighterSternBrocot_RECURSES
38 
39 #if !defined LighterSternBrocot_h
40 
41 #define LighterSternBrocot_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 LighterSternBrocot
106  template <typename TInteger, typename TQuotient,
107  typename TMap = StdMapRebinder >
109  {
110  public:
111  typedef TInteger Integer;
112  typedef TQuotient Quotient;
113  typedef TMap Map;
115 
117 
118  struct Node;
119  typedef typename TMap:: template Rebinder<Quotient, Node*>::Type MapQuotientToNode;
120 
121  public:
122 
139  struct Node {
140 
150  Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
151  Node* anOrigin );
152 
155  Node* child( Quotient v );
156 
161  Node* origin() const;
162 
169  Node* ancestor() const;
174  Node* father() const;
175 
177  Integer p;
179  Integer q;
181  Quotient u;
183  Quotient k;
189  MapQuotientToNode myChildren;
190 
191 
193  inline bool even() const {
194  return NumberTraits<Quotient>::even( k );
195  }
197  inline bool odd() const {
198  return NumberTraits<Quotient>::odd( k );
199  }
201  inline bool isSameDepthLeft() const {
202  return odd();
203  }
204 
205  };
206 
216  class Fraction {
217  public:
218  typedef TInteger Integer;
219  typedef TQuotient Quotient;
221  typedef typename SternBrocotTree::Fraction Self;
223  typedef std::pair<Quotient, Quotient> Value;
224  typedef std::vector<Quotient> CFracSequence;
226 
227  // --------------------- std types ------------------------------
228  typedef Value value_type;
229  typedef ConstIterator const_iterator;
230  typedef const value_type & const_reference;
231 
232  private:
237  bool mySup1;
238 
239  public:
249  Fraction( Integer aP, Integer aQ,
251 
259  Fraction( Node* sb_node = 0, bool sup1 = false );
260 
265  Fraction( const Self & other );
266 
272  Self& operator=( const Self & other );
273 
275  bool null() const;
277  Integer p() const;
279  Integer q() const;
281  Quotient u() const;
283  Quotient k() const;
284 
287  bool isSup1() const { return mySup1; }
289  Quotient trueK() const { return myNode->k; }
290 
291  protected:
294  Fraction child( Quotient v ) const;
299  Fraction origin() const;
302  Fraction next( Quotient v ) const;
303 
304  public:
305 
307  Fraction left() const;
309  Fraction right() const;
311  bool even() const;
313  bool odd() const;
314 
321  Fraction ancestor() const;
325  bool isAncestorDirect() const;
330  Fraction father() const;
335  Fraction father( Quotient m ) const;
341  Fraction previousPartial() const;
346  Fraction inverse() const;
353  Fraction partial( Quotient kp ) const;
360  Fraction reduced( Quotient i ) const;
361 
378  void push_back( const std::pair<Quotient, Quotient> & quotient );
379 
390  void pushBack( const std::pair<Quotient, Quotient> & quotient );
391 
399  void getSplit( Fraction & f1, Fraction & f2 ) const;
400 
412  void getSplitBerstel( Fraction & f1, Quotient & nb1,
413  Fraction & f2, Quotient & nb2 ) const;
414 
419  void getCFrac( std::vector<Quotient> & quotients ) const;
420 
426  bool equals( Integer p1, Integer q1 ) const;
427 
433  bool lessThan( Integer p1, Integer q1 ) const;
434 
440  bool moreThan( Integer p1, Integer q1 ) const;
441 
446  bool operator==( const Fraction & other ) const;
447 
452  bool operator!=( const Fraction & other ) const;
453 
458  bool operator<( const Fraction & other ) const;
459 
464  bool operator>( const Fraction & other ) const;
465 
470  void selfDisplay ( std::ostream & out ) const;
471 
476  ConstIterator begin() const;
477 
482  ConstIterator end() const;
483 
484  };
485 
486 
487 
488  // ----------------------- Standard services ------------------------------
489  public:
494 
498  static LighterSternBrocot & instance();
499 
501  static Fraction zeroOverOne();
502 
504  static Fraction oneOverZero();
505 
507  static Fraction oneOverOne();
508 
520  static Fraction fraction( Integer p, Integer q,
521  Fraction ancestor = oneOverZero() );
522 
523  // ----------------------- Interface --------------------------------------
524  public:
525 
531  static void display ( std::ostream & out, const Fraction & f );
532 
537  bool isValid() const;
538 
540  Quotient nbFractions;
541 
542  // ------------------------- Protected Datas ------------------------------
543  protected:
544  // ------------------------- Private Datas --------------------------------
545  private:
546 
549 
552 
553  // ------------------------- Hidden services ------------------------------
554  protected:
555 
556  private:
557 
562 
568  LighterSternBrocot ( const LighterSternBrocot & other );
569 
577 
578  // ------------------------- Internals ------------------------------------
579  private:
580 
581  }; // end of class LighterSternBrocot
582 
583 
590  // template <typename TInteger, typename TQuotient, typename TMap>
591  // std::ostream&
592  // operator<< ( std::ostream & out,
593  // const typename LighterSternBrocot<TInteger, TQuotient, TMap>::Fraction & object );
594 
595 } // namespace DGtal
596 
597 
599 // Includes inline functions.
600 #include "DGtal/arithmetic/LighterSternBrocot.ih"
601 
602 // //
604 
605 #endif // !defined LighterSternBrocot_h
606 
607 #undef LighterSternBrocot_RECURSES
608 #endif // else defined(LighterSternBrocot_RECURSES)
Quotient u
the quotient (last coefficient of its continued fraction).
void selfDisplay(std::ostream &out) const
This fraction is a model of CPositiveIrreducibleFraction.
static void display(std::ostream &out, const Fraction &f)
Self & operator=(const Self &other)
void push_back(const std::pair< Quotient, Quotient > &quotient)
TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
LighterSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
static Fraction oneOverZero()
void pushBack(const std::pair< Quotient, Quotient > &quotient)
LighterSternBrocot & operator=(const LighterSternBrocot &other)
static Fraction fraction(Integer p, Integer q, Fraction ancestor=oneOverZero())
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
static Fraction oneOverOne()
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *anOrigin)
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
bool operator==(const Fraction &other) const
void getSplit(Fraction &f1, Fraction &f2) const
bool operator!=(const Fraction &other) const
bool equals(Integer p1, Integer q1) const
bool moreThan(Integer p1, Integer q1) const
bool operator>(const Fraction &other) const
Fraction child(Quotient v) const
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:69
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence...
Fraction reduced(Quotient i) const
std::pair< Quotient, Quotient > Value
Fraction next(Quotient v) const
Node * myOrigin
A pointer to the origin node [u_0,...,u_{n-1},1].
bool lessThan(Integer p1, Integer q1) const
Fraction partial(Quotient kp) const
static bool even(ParamType aT)
Definition: NumberTraits.h:162
ConstIterator begin() const
DGtal is the top-level namespace which contains all DGtal functions and types.
Quotient k
the depth (1+number of coefficients of its continued fraction).
Quotient nbFractions
The total number of fractions in the current tree.
void getCFrac(std::vector< Quotient > &quotients) const
LighterSternBrocot< TInteger, TQuotient, TMap > Self
static Fraction zeroOverOne()
bool operator<(const Fraction &other) const
static LighterSternBrocot & instance()
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
bool mySup1
When 'true', the fraction is greater or equal than 1/1 (to its right).
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
static LighterSternBrocot * singleton
Singleton class.
static bool odd(ParamType aT)
Definition: NumberTraits.h:170