DGtal  1.3.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)
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 
134  struct Node {
135 
146  Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
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:
226  Fraction( Integer aP, Integer aQ,
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;
290  Fraction ancestor() const;
294  bool isAncestorDirect() const;
295 
300  Fraction father() const;
301 
309  Fraction father( Quotient m ) const;
315  Fraction previousPartial() const;
320  Fraction inverse() const;
327  Fraction partial( Quotient kp ) const;
334  Fraction reduced( Quotient i ) 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 
450  ConstIterator begin() const;
451 
456  ConstIterator end() const;
457 
458  };
459 
460 
461 
462  // ----------------------- Standard services ------------------------------
463  public:
468 
472  static LightSternBrocot & instance();
473 
475  static Fraction zeroOverOne();
476 
478  static Fraction oneOverZero();
479 
493  static Fraction fraction( Integer p, Integer q,
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 
546  LightSternBrocot ( const LightSternBrocot & other );
547 
554  LightSternBrocot & operator= ( const LightSternBrocot & other );
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)
DGtal::LightSternBrocot::Fraction::push_back
void push_back(const std::pair< Quotient, Quotient > &quotient)
DGtal::LightSternBrocot::Fraction::getSplitBerstel
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
ConstIterator
MyDigitalSurface::ConstIterator ConstIterator
Definition: greedy-plane-segmentation-ex2.cpp:93
DGtal::LightSternBrocot::Node::descendant2
MapQuotientToNode descendant2
Definition: LightSternBrocot.h:166
DGtal::LightSternBrocot::display
static void display(std::ostream &out, const Fraction &f)
DGtal::LightSternBrocot::Fraction::previousPartial
Fraction previousPartial() const
DGtal::LightSternBrocot::Node::odd
bool odd() const
Definition: LightSternBrocot.h:173
DGtal::concepts::CInteger
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:87
DGtal::LightSternBrocot::instance
static LightSternBrocot & instance()
DGtal::LightSternBrocot::Fraction::inverse
Fraction inverse() const
DGtal::NumberTraits
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:562
DGtal::LightSternBrocot::Fraction::equals
bool equals(Integer p1, Integer q1) const
DGtal::LightSternBrocot::Fraction::pushBack
void pushBack(const std::pair< Quotient, Quotient > &quotient)
DGtal::LightSternBrocot::Fraction::reduced
Fraction reduced(Quotient i) const
DGtal::LightSternBrocot::Map
TMap Map
Definition: LightSternBrocot.h:112
DGtal::NumberTraitsImpl< std::decay< T >::type >::odd
static bool odd(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:183
DGtal::LightSternBrocot::Quotient
TQuotient Quotient
Definition: LightSternBrocot.h:111
DGtal::LightSternBrocot::Node::isSameDepthLeft
bool isSameDepthLeft() const
Definition: LightSternBrocot.h:177
DGtal::LightSternBrocot::Fraction::selfDisplay
void selfDisplay(std::ostream &out) const
DGtal::LightSternBrocot::Fraction::ConstIterator
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Definition: LightSternBrocot.h:201
DGtal::LightSternBrocot::Node::ascendant
Node * ascendant
A pointer to the node that is the preceding principal convergent.
Definition: LightSternBrocot.h:158
DGtal::LightSternBrocot::nbFractions
Quotient nbFractions
The total number of fractions in the current tree.
Definition: LightSternBrocot.h:513
DGtal::LightSternBrocot::Fraction::q
Integer q() const
DGtal::LightSternBrocot::Node::even
bool even() const
Definition: LightSternBrocot.h:169
DGtal::LightSternBrocot::Fraction::next1
Fraction next1(Quotient v) const
DGtal::LightSternBrocot::Fraction::Integer
TInteger Integer
Definition: LightSternBrocot.h:194
DGtal::LightSternBrocot::Node
Definition: LightSternBrocot.h:134
DGtal::LightSternBrocot::Fraction::Self
SternBrocotTree::Fraction Self
Definition: LightSternBrocot.h:197
DGtal::LightSternBrocot::Fraction::right
Fraction right() const
DGtal::LightSternBrocot::Fraction::moreThan
bool moreThan(Integer p1, Integer q1) const
DGtal::LightSternBrocot::Fraction::Quotient
TQuotient Quotient
Definition: LightSternBrocot.h:195
DGtal::LightSternBrocot::Fraction::const_reference
const typedef value_type & const_reference
Definition: LightSternBrocot.h:206
DGtal::LightSternBrocot::Fraction::p
Integer p() const
DGtal::LightSternBrocot::Fraction::trueK
Quotient trueK() const
Definition: LightSternBrocot.h:266
DGtal::LightSternBrocot::~LightSternBrocot
~LightSternBrocot()
DGtal::LightSternBrocot::Node::u
Quotient u
the quotient (last coefficient of its continued fraction).
Definition: LightSternBrocot.h:154
DGtal::LightSternBrocot::Fraction::Value
std::pair< Quotient, Quotient > Value
Definition: LightSternBrocot.h:199
DGtal::LightSternBrocot::Fraction::begin
ConstIterator begin() const
DGtal::LightSternBrocot::Fraction::SternBrocotTree
LightSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
Definition: LightSternBrocot.h:196
DGtal::LightSternBrocot::myOneOverOne
Node * myOneOverOne
Definition: LightSternBrocot.h:529
DGtal::LightSternBrocot::Fraction::const_iterator
ConstIterator const_iterator
Definition: LightSternBrocot.h:205
DGtal::LightSternBrocot::Fraction::father
Fraction father() const
DGtal::LightSternBrocot::isValid
bool isValid() const
DGtal::LightSternBrocot::Fraction
This fraction is a model of CPositiveIrreducibleFraction.
Definition: LightSternBrocot.h:192
DGtal::LightSternBrocot::Fraction::CFracSequence
std::vector< Quotient > CFracSequence
Definition: LightSternBrocot.h:200
DGtal::LightSternBrocot::Node::k
Quotient k
the depth (1+number of coefficients of its continued fraction).
Definition: LightSternBrocot.h:156
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::LightSternBrocot::operator=
LightSternBrocot & operator=(const LightSternBrocot &other)
DGtal::LightSternBrocot::Fraction::operator>
bool operator>(const Fraction &other) const
DGtal::LightSternBrocot::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
DGtal::LightSternBrocot::Fraction::Fraction
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
DGtal::LightSternBrocot::Fraction::operator<
bool operator<(const Fraction &other) const
DGtal::LightSternBrocot::Fraction::left
Fraction left() const
DGtal::LightSternBrocot::Fraction::isAncestorDirect
bool isAncestorDirect() const
DGtal::LightSternBrocot::myZeroOverOne
Node * myZeroOverOne
Definition: LightSternBrocot.h:527
DGtal::LightSternBrocot::zeroOverOne
static Fraction zeroOverOne()
DGtal::LightSternBrocot::Fraction::getCFrac
void getCFrac(std::vector< Quotient > &quotients) const
DGtal::LightSternBrocot::Fraction::u
Quotient u() const
DGtal::LightSternBrocot::Fraction::UnsignedInteger
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Definition: LightSternBrocot.h:198
DGtal::LightSternBrocot::LightSternBrocot
LightSternBrocot()
DGtal::LightSternBrocot::Fraction::operator=
Self & operator=(const Self &other)
DGtal::LightSternBrocot::Fraction::lessThan
bool lessThan(Integer p1, Integer q1) const
DGtal::InputIteratorWithRankOnSequence
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence....
Definition: InputIteratorWithRankOnSequence.h:79
DGtal::LightSternBrocot::myOneOverZero
Node * myOneOverZero
Definition: LightSternBrocot.h:528
DGtal::LightSternBrocot::Fraction::myNode
Node * myNode
Definition: LightSternBrocot.h:212
Integer
Point::Coordinate Integer
Definition: examplePlaneProbingParallelepipedEstimator.cpp:44
DGtal::LightSternBrocot::Fraction::ancestor
Fraction ancestor() const
DGtal::LightSternBrocot::singleton
static LightSternBrocot * singleton
Singleton class.
Definition: LightSternBrocot.h:521
DGtal::LightSternBrocot
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition: LightSternBrocot.h:107
DGtal::LightSternBrocot::Fraction::next
Fraction next(Quotient v) const
DGtal::LightSternBrocot::Fraction::partial
Fraction partial(Quotient kp) const
DGtal::LightSternBrocot::Fraction::value_type
Value value_type
Definition: LightSternBrocot.h:204
DGtal::LightSternBrocot::Fraction::even
bool even() const
DGtal::LightSternBrocot::Node::descendant
MapQuotientToNode descendant
Definition: LightSternBrocot.h:162
DGtal::LightSternBrocot::Fraction::k
Quotient k() const
DGtal::LightSternBrocot::Fraction::mySup1
bool mySup1
When 'true', the fraction is greater than 1/1 (to its right).
Definition: LightSternBrocot.h:214
DGtal::LightSternBrocot::Node::Node
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *ascendant)
DGtal::LightSternBrocot::oneOverZero
static Fraction oneOverZero()
DGtal::LightSternBrocot::Fraction::end
ConstIterator end() const
DGtal::LightSternBrocot::Fraction::operator==
bool operator==(const Fraction &other) const
DGtal::LightSternBrocot::Integer
TInteger Integer
Definition: LightSternBrocot.h:110
DGtal::LightSternBrocot::MapQuotientToNode
TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
Definition: LightSternBrocot.h:117
DGtal::LightSternBrocot::Fraction::operator!=
bool operator!=(const Fraction &other) const
DGtal::NumberTraitsImpl< std::decay< T >::type >::even
static bool even(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:173
DGtal::LightSternBrocot::Self
LightSternBrocot< TInteger, TQuotient, TMap > Self
Definition: LightSternBrocot.h:113
DGtal::LightSternBrocot::fraction
static Fraction fraction(Integer p, Integer q, Fraction ancestor=zeroOverOne())
DGtal::LightSternBrocot::Fraction::odd
bool odd() const
DGtal::LightSternBrocot::Node::p
Integer p
the numerator;
Definition: LightSternBrocot.h:150
DGtal::LightSternBrocot::Fraction::getSplit
void getSplit(Fraction &f1, Fraction &f2) const
DGtal::LightSternBrocot::Fraction::isSup1
bool isSup1() const
Definition: LightSternBrocot.h:264
DGtal::LightSternBrocot::Node::q
Integer q
the denominator;
Definition: LightSternBrocot.h:152