DGtal  1.1.0
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 
151  Node* anOrigin );
152 
156 
161  Node* origin() const;
162 
169  Node* ancestor() const;
174  Node* father() const;
175 
190 
191 
193  inline bool even() const {
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;
230  typedef const value_type & const_reference;
231 
232  private:
237  bool mySup1;
238 
239  public:
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 
325  bool isAncestorDirect() const;
330  Fraction father() const;
346  Fraction inverse() const;
353  Fraction partial( Quotient kp ) 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 
477 
483 
484  };
485 
486 
487 
488  // ----------------------- Standard services ------------------------------
489  public:
494 
499 
502 
505 
508 
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 
541 
542  // ------------------------- Protected Datas ------------------------------
543  protected:
544  // ------------------------- Private Datas --------------------------------
545  private:
546 
549 
552 
553  // ------------------------- Hidden services ------------------------------
554  protected:
555 
556  private:
557 
562 
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)
DGtal::LighterSternBrocot::MapQuotientToNode
TMap::template Rebinder< Quotient, Node * >::Type MapQuotientToNode
Definition: LighterSternBrocot.h:118
DGtal::LighterSternBrocot::Fraction::ancestor
Fraction ancestor() const
DGtal::LighterSternBrocot::Node::isSameDepthLeft
bool isSameDepthLeft() const
Definition: LighterSternBrocot.h:201
DGtal::LighterSternBrocot::Map
TMap Map
Definition: LighterSternBrocot.h:113
DGtal::LighterSternBrocot::Fraction::k
Quotient k() const
DGtal::LighterSternBrocot::Node::myChildren
MapQuotientToNode myChildren
Definition: LighterSternBrocot.h:189
DGtal::LighterSternBrocot::Fraction::isSup1
bool isSup1() const
Definition: LighterSternBrocot.h:287
DGtal::LighterSternBrocot::Fraction::getSplitBerstel
void getSplitBerstel(Fraction &f1, Quotient &nb1, Fraction &f2, Quotient &nb2) const
DGtal::LighterSternBrocot::myOneOverOne
Node * myOneOverOne
Definition: LighterSternBrocot.h:551
DGtal::LighterSternBrocot::LighterSternBrocot
LighterSternBrocot(const LighterSternBrocot &other)
DGtal::LighterSternBrocot::Node::father
Node * father() const
DGtal::LighterSternBrocot::Fraction
This fraction is a model of CPositiveIrreducibleFraction.
Definition: LighterSternBrocot.h:216
DGtal::LighterSternBrocot::Fraction::begin
ConstIterator begin() const
DGtal::LighterSternBrocot::Fraction::getCFrac
void getCFrac(std::vector< Quotient > &quotients) const
DGtal::LighterSternBrocot::Node::u
Quotient u
the quotient (last coefficient of its continued fraction).
Definition: LighterSternBrocot.h:181
DGtal::LighterSternBrocot::oneOverZero
static Fraction oneOverZero()
DGtal::concepts::CInteger
Aim: Concept checking for Integer Numbers. More precisely, this concept is a refinement of both CEucl...
Definition: CInteger.h:88
DGtal::LighterSternBrocot::nbFractions
Quotient nbFractions
The total number of fractions in the current tree.
Definition: LighterSternBrocot.h:540
DGtal::LighterSternBrocot::Fraction::mySup1
bool mySup1
When 'true', the fraction is greater or equal than 1/1 (to its right).
Definition: LighterSternBrocot.h:237
DGtal::LighterSternBrocot::Fraction::const_iterator
ConstIterator const_iterator
Definition: LighterSternBrocot.h:229
DGtal::LighterSternBrocot::Fraction::q
Integer q() const
DGtal::NumberTraits
Aim: The traits class for all models of Cinteger.
Definition: NumberTraits.h:533
DGtal::LighterSternBrocot::Fraction::SternBrocotTree
LighterSternBrocot< TInteger, TQuotient, TMap > SternBrocotTree
Definition: LighterSternBrocot.h:220
DGtal::LighterSternBrocot::Node
Definition: LighterSternBrocot.h:139
DGtal::LighterSternBrocot::Self
LighterSternBrocot< TInteger, TQuotient, TMap > Self
Definition: LighterSternBrocot.h:114
DGtal::LighterSternBrocot::Node::even
bool even() const
Definition: LighterSternBrocot.h:193
DGtal::LighterSternBrocot::Fraction::Integer
TInteger Integer
Definition: LighterSternBrocot.h:218
DGtal::LighterSternBrocot::Fraction::odd
bool odd() const
DGtal::NumberTraitsImpl< std::decay< T >::type >::odd
static bool odd(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:173
DGtal::LighterSternBrocot::Node::p
Integer p
the numerator;
Definition: LighterSternBrocot.h:177
DGtal::LighterSternBrocot::zeroOverOne
static Fraction zeroOverOne()
DGtal::LighterSternBrocot::Fraction::p
Integer p() const
DGtal::LighterSternBrocot::Fraction::inverse
Fraction inverse() const
DGtal::LighterSternBrocot::Fraction::Fraction
Fraction(Node *sb_node=0, bool sup1=false)
DGtal::LighterSternBrocot::Fraction::operator<
bool operator<(const Fraction &other) const
DGtal::LighterSternBrocot::Fraction::partial
Fraction partial(Quotient kp) const
DGtal::LighterSternBrocot::Fraction::operator!=
bool operator!=(const Fraction &other) const
DGtal::LighterSternBrocot::Fraction::u
Quotient u() const
DGtal::LighterSternBrocot::Fraction::lessThan
bool lessThan(Integer p1, Integer q1) const
DGtal::LighterSternBrocot::Node::child
Node * child(Quotient v)
DGtal::LighterSternBrocot::Fraction::moreThan
bool moreThan(Integer p1, Integer q1) const
DGtal::LighterSternBrocot::Fraction::getSplit
void getSplit(Fraction &f1, Fraction &f2) const
DGtal::LighterSternBrocot::Fraction::Quotient
TQuotient Quotient
Definition: LighterSternBrocot.h:219
DGtal::LighterSternBrocot::Fraction::even
bool even() const
DGtal::LighterSternBrocot::Fraction::Value
std::pair< Quotient, Quotient > Value
Definition: LighterSternBrocot.h:223
DGtal::LighterSternBrocot::Fraction::origin
Fraction origin() const
DGtal::LighterSternBrocot::Node::myOrigin
Node * myOrigin
A pointer to the origin node [u_0,...,u_{n-1},1].
Definition: LighterSternBrocot.h:185
DGtal::LighterSternBrocot::Fraction::ConstIterator
InputIteratorWithRankOnSequence< CFracSequence, Quotient > ConstIterator
Definition: LighterSternBrocot.h:225
DGtal::LighterSternBrocot::Fraction::father
Fraction father(Quotient m) const
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
Definition: ClosedIntegerHalfPlane.h:49
DGtal::LighterSternBrocot::display
static void display(std::ostream &out, const Fraction &f)
DGtal::LighterSternBrocot::singleton
static LighterSternBrocot * singleton
Singleton class.
Definition: LighterSternBrocot.h:548
DGtal::LighterSternBrocot::Node::k
Quotient k
the depth (1+number of coefficients of its continued fraction).
Definition: LighterSternBrocot.h:183
DGtal::LighterSternBrocot::Fraction::pushBack
void pushBack(const std::pair< Quotient, Quotient > &quotient)
DGtal::LighterSternBrocot::Node::q
Integer q
the denominator;
Definition: LighterSternBrocot.h:179
DGtal::LighterSternBrocot::Quotient
TQuotient Quotient
Definition: LighterSternBrocot.h:112
DGtal::LighterSternBrocot::Node::origin
Node * origin() const
DGtal::LighterSternBrocot::BOOST_CONCEPT_ASSERT
BOOST_CONCEPT_ASSERT((concepts::CInteger< Integer >))
DGtal::LighterSternBrocot::Node::Node
Node(Integer p1, Integer q1, Quotient u1, Quotient k1, Node *anOrigin)
DGtal::LighterSternBrocot::Fraction::isAncestorDirect
bool isAncestorDirect() const
DGtal::LighterSternBrocot::Fraction::right
Fraction right() const
DGtal::LighterSternBrocot::Fraction::previousPartial
Fraction previousPartial() const
DGtal::LighterSternBrocot::Fraction::operator=
Self & operator=(const Self &other)
DGtal::LighterSternBrocot::Fraction::equals
bool equals(Integer p1, Integer q1) const
DGtal::LighterSternBrocot::Fraction::reduced
Fraction reduced(Quotient i) const
DGtal::LighterSternBrocot::Fraction::father
Fraction father() const
DGtal::LighterSternBrocot::Fraction::left
Fraction left() const
DGtal::LighterSternBrocot::Fraction::child
Fraction child(Quotient v) const
DGtal::LighterSternBrocot::Fraction::trueK
Quotient trueK() const
Definition: LighterSternBrocot.h:289
DGtal::InputIteratorWithRankOnSequence
Aim: Useful to create an iterator that returns a pair (value,rank) when visiting a sequence....
Definition: InputIteratorWithRankOnSequence.h:80
DGtal::LighterSternBrocot::myOneOverZero
Node * myOneOverZero
Definition: LighterSternBrocot.h:550
DGtal::LighterSternBrocot::Fraction::Fraction
Fraction(const Self &other)
DGtal::LighterSternBrocot::fraction
static Fraction fraction(Integer p, Integer q, Fraction ancestor=oneOverZero())
DGtal::LighterSternBrocot::Fraction::operator>
bool operator>(const Fraction &other) const
DGtal::LighterSternBrocot::Fraction::CFracSequence
std::vector< Quotient > CFracSequence
Definition: LighterSternBrocot.h:224
DGtal::LighterSternBrocot::Fraction::const_reference
const value_type & const_reference
Definition: LighterSternBrocot.h:230
DGtal::LighterSternBrocot::Fraction::next
Fraction next(Quotient v) const
DGtal::LighterSternBrocot::LighterSternBrocot
LighterSternBrocot()
DGtal::LighterSternBrocot::instance
static LighterSternBrocot & instance()
DGtal::LighterSternBrocot
Aim: The Stern-Brocot tree is the tree of irreducible fractions. This class allows to construct it pr...
Definition: LighterSternBrocot.h:109
DGtal::LighterSternBrocot::Fraction::Fraction
Fraction(Integer aP, Integer aQ, Fraction start=SternBrocotTree::zeroOverOne())
DGtal::LighterSternBrocot::~LighterSternBrocot
~LighterSternBrocot()
DGtal::LighterSternBrocot::operator=
LighterSternBrocot & operator=(const LighterSternBrocot &other)
DGtal::LighterSternBrocot::Integer
TInteger Integer
Definition: LighterSternBrocot.h:111
DGtal::LighterSternBrocot::isValid
bool isValid() const
DGtal::LighterSternBrocot::Fraction::Self
SternBrocotTree::Fraction Self
Definition: LighterSternBrocot.h:221
DGtal::LighterSternBrocot::Fraction::push_back
void push_back(const std::pair< Quotient, Quotient > &quotient)
DGtal::LighterSternBrocot::Fraction::operator==
bool operator==(const Fraction &other) const
DGtal::LighterSternBrocot::Fraction::myNode
Node * myNode
Definition: LighterSternBrocot.h:235
DGtal::LighterSternBrocot::Node::odd
bool odd() const
Definition: LighterSternBrocot.h:197
DGtal::NumberTraitsImpl< std::decay< T >::type >::even
static bool even(ParamType aT)
Check the parity of a number.
Definition: NumberTraits.h:163
DGtal::LighterSternBrocot::Fraction::value_type
Value value_type
Definition: LighterSternBrocot.h:228
DGtal::LighterSternBrocot::oneOverOne
static Fraction oneOverOne()
DGtal::LighterSternBrocot::Fraction::selfDisplay
void selfDisplay(std::ostream &out) const
DGtal::LighterSternBrocot::Node::ancestor
Node * ancestor() const
DGtal::LighterSternBrocot::Fraction::end
ConstIterator end() const
DGtal::LighterSternBrocot::Fraction::UnsignedInteger
NumberTraits< Integer >::UnsignedVersion UnsignedInteger
Definition: LighterSternBrocot.h:222