DGtal  1.5.beta
SternBrocot.ih
1 /**
2  * This program is free software: you can redistribute it and/or modify
3  * it under the terms of the GNU Lesser General Public License as
4  * published by the Free Software Foundation, either version 3 of the
5  * License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program. If not, see <http://www.gnu.org/licenses/>.
14  *
15  **/
16 
17 /**
18  * @file SternBrocot.ih
19  * @author Jacques-Olivier Lachaud (\c jacques-olivier.lachaud@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
21  * @author Xavier Provençal (\c xavier.provencal@univ-savoie.fr )
22  * Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
23  *
24  * @date 2012/03/07
25  *
26  * Implementation of inline methods defined in SternBrocot.h
27  *
28  * This file is part of the DGtal library.
29  */
30 
31 
32 //////////////////////////////////////////////////////////////////////////////
33 #include <cstdlib>
34 #include "DGtal/arithmetic/IntegerComputer.h"
35 //////////////////////////////////////////////////////////////////////////////
36 
37 ///////////////////////////////////////////////////////////////////////////////
38 // DEFINITION of static data members
39 ///////////////////////////////////////////////////////////////////////////////
40 
41 template <typename TInteger, typename TQuotient>
42 DGtal::SternBrocot<TInteger, TQuotient>*
43 DGtal::SternBrocot<TInteger, TQuotient>::singleton = 0;
44 
45 ///////////////////////////////////////////////////////////////////////////////
46 // IMPLEMENTATION of inline methods.
47 ///////////////////////////////////////////////////////////////////////////////
48 
49 ///////////////////////////////////////////////////////////////////////////////
50 // ----------------------- Standard services ------------------------------
51 
52 ///////////////////////////////////////////////////////////////////////////////
53 // DGtal::SternBrocot<TInteger, TQuotient>::Node
54 //-----------------------------------------------------------------------------
55 template <typename TInteger, typename TQuotient>
56 inline
57 DGtal::SternBrocot<TInteger, TQuotient>::Node::
58 Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
59  Node* ascendant_left1, Node* ascendant_right1,
60  Node* descendant_left1, Node* descendant_right1,
61  Node* inverse1 )
62  : p( p1 ), q( q1 ), u( u1 ), k( k1 ),
63  ascendantLeft( ascendant_left1 ),
64  ascendantRight( ascendant_right1 ),
65  descendantLeft( descendant_left1 ),
66  descendantRight( descendant_right1 ),
67  inverse( inverse1 )
68 {
69  // std::cerr << "(" << p1 << "/" << q1 << "," << u1 << "," << k1 << ")";
70 }
71 
72 //////////////////////////////////////////////////////////////////////////////
73 // DGtal::SternBrocot<TInteger, TQuotient>::Fraction
74 //-----------------------------------------------------------------------------
75 template <typename TInteger, typename TQuotient>
76 inline
77 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
78 Fraction( Integer aP, Integer aQ, Fraction ancestor )
79 {
80  this->operator=( SternBrocotTree::fraction( aP, aQ, ancestor ) );
81 }
82 //-----------------------------------------------------------------------------
83 template <typename TInteger, typename TQuotient>
84 inline
85 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
86 Fraction( Node* sb_node )
87  : myNode( sb_node )
88 {
89 }
90 //-----------------------------------------------------------------------------
91 template <typename TInteger, typename TQuotient>
92 inline
93 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
94 Fraction( const Self & other )
95  : myNode( other.myNode )
96 {
97 }
98 //-----------------------------------------------------------------------------
99 template <typename TInteger, typename TQuotient>
100 inline
101 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction &
102 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
103 operator=( const Self & other )
104 {
105  if ( this != &other )
106  {
107  myNode = other.myNode;
108  }
109  return *this;
110 }
111 //-----------------------------------------------------------------------------
112 template <typename TInteger, typename TQuotient>
113 inline
114 bool
115 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
116 null() const
117 {
118  return myNode == 0;
119 }
120 //-----------------------------------------------------------------------------
121 template <typename TInteger, typename TQuotient>
122 inline
123 typename DGtal::SternBrocot<TInteger, TQuotient>::Integer
124 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
125 p() const
126 {
127  return myNode ? myNode->p : 0;
128 }
129 //-----------------------------------------------------------------------------
130 template <typename TInteger, typename TQuotient>
131 inline
132 typename DGtal::SternBrocot<TInteger, TQuotient>::Integer
133 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
134 q() const
135 {
136  return myNode ? myNode->q : 0;
137 }
138 //-----------------------------------------------------------------------------
139 template <typename TInteger, typename TQuotient>
140 inline
141 typename DGtal::SternBrocot<TInteger, TQuotient>::Quotient
142 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
143 u() const
144 {
145  ASSERT( myNode != 0 );
146  return myNode->u;
147 }
148 //-----------------------------------------------------------------------------
149 template <typename TInteger, typename TQuotient>
150 inline
151 typename DGtal::SternBrocot<TInteger, TQuotient>::Quotient
152 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
153 k() const
154 {
155  ASSERT( myNode != 0 );
156  return myNode->k;
157 }
158 //-----------------------------------------------------------------------------
159 template <typename TInteger, typename TQuotient>
160 inline
161 bool
162 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
163 equals( Integer p1, Integer q1 ) const
164 {
165  return ( this->p() == p1 ) && ( this->q() == q1 );
166 }
167 //-----------------------------------------------------------------------------
168 template <typename TInteger, typename TQuotient>
169 inline
170 bool
171 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
172 lessThan( Integer p1, Integer q1 ) const
173 {
174  Integer d = p() * q1 - q() * p1;
175  return d < NumberTraits<Integer>::ZERO;
176 }
177 //-----------------------------------------------------------------------------
178 template <typename TInteger, typename TQuotient>
179 inline
180 bool
181 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
182 moreThan( Integer p1, Integer q1 ) const
183 {
184  Integer d = p() * q1 - q() * p1;
185  return d > NumberTraits<Integer>::ZERO;
186 }
187 //-----------------------------------------------------------------------------
188 template <typename TInteger, typename TQuotient>
189 inline
190 bool
191 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
192 operator==( const Fraction & other ) const
193 {
194  return myNode == other.myNode;
195 }
196 //-----------------------------------------------------------------------------
197 template <typename TInteger, typename TQuotient>
198 inline
199 bool
200 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
201 operator!=( const Fraction & other ) const
202 {
203  return myNode != other.myNode;
204 }
205 //-----------------------------------------------------------------------------
206 template <typename TInteger, typename TQuotient>
207 inline
208 bool
209 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
210 operator<( const Fraction & other ) const
211 {
212  return this->lessThan( other.p(), other.q() );
213 }
214 //-----------------------------------------------------------------------------
215 template <typename TInteger, typename TQuotient>
216 inline
217 bool
218 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
219 operator>( const Fraction & other ) const
220 {
221  return this->moreThan( other.p(), other.q() );
222 }
223 //-----------------------------------------------------------------------------
224 template <typename TInteger, typename TQuotient>
225 inline
226 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
227 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
228 left() const
229 {
230  if ( myNode->descendantLeft == 0 )
231  {
232  Node* pleft = myNode->ascendantLeft;
233  Node* n = new Node( p() + pleft->p,
234  q() + pleft->q,
235  odd() ? u() + 1 : (Quotient) 2,
236  odd() ? k() : k() + 1,
237  pleft, myNode,
238  0, 0, 0 );
239  Fraction inv = Fraction( myNode->inverse );
240  Node* invpright = inv.myNode->ascendantRight;
241  Node* invn = new Node( inv.p() + invpright->p,
242  inv.q() + invpright->q,
243  inv.even() ? inv.u() + 1 : (Quotient) 2,
244  inv.even() ? inv.k() : inv.k() + 1,
245  myNode->inverse, invpright,
246  0, 0, n );
247  n->inverse = invn;
248  myNode->inverse->descendantRight = invn;
249  myNode->descendantLeft = n;
250  instance().nbFractions += 2;
251  }
252  return Fraction( myNode->descendantLeft );
253 }
254 //-----------------------------------------------------------------------------
255 template <typename TInteger, typename TQuotient>
256 inline
257 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
258 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
259 right() const
260 {
261  if ( myNode->descendantRight == 0 )
262  {
263  Fraction inv( myNode->inverse );
264  inv.left();
265  ASSERT( myNode->descendantRight != 0 );
266  }
267  return Fraction( myNode->descendantRight );
268 }
269 //-----------------------------------------------------------------------------
270 template <typename TInteger, typename TQuotient>
271 inline
272 bool
273 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
274 even() const
275 {
276  return ( k() & 1 ) == 0;
277 }
278 //-----------------------------------------------------------------------------
279 template <typename TInteger, typename TQuotient>
280 inline
281 bool
282 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
283 odd() const
284 {
285  return ( k() & 1 ) != 0;
286 }
287 //-----------------------------------------------------------------------------
288 template <typename TInteger, typename TQuotient>
289 inline
290 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
291 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
292 father() const
293 {
294  return Fraction( odd() ? myNode->ascendantRight : myNode->ascendantLeft );
295 }
296 //-----------------------------------------------------------------------------
297 template <typename TInteger, typename TQuotient>
298 inline
299 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
300 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
301 father( Quotient m ) const
302 {
303  if ( m > NumberTraits<Quotient>::ONE ) // > 1
304  {
305  Node* n = myNode;
306  while ( n->u > m )
307  n = odd() ? n->ascendantRight : n->ascendantLeft;
308  return Fraction( n );
309  }
310  else if ( m != NumberTraits<Quotient>::ZERO ) // == 1
311  {
312  return odd() ? previousPartial().right() : previousPartial().left();
313  }
314  else // == 0
315  return reduced( 2 ); //previousPartial().previousPartial();
316 }
317 //-----------------------------------------------------------------------------
318 template <typename TInteger, typename TQuotient>
319 inline
320 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
321 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
322 previousPartial() const
323 {
324  return Fraction( odd() ? myNode->ascendantLeft : myNode->ascendantRight );
325  // return Fraction( odd()
326  // ? myNode->ascendantLeft->descendantRight
327  // : myNode->ascendantRight->descendantLeft );
328 }
329 //-----------------------------------------------------------------------------
330 template <typename TInteger, typename TQuotient>
331 inline
332 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
333 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
334 inverse() const
335 {
336  return Fraction( myNode->inverse );
337 }
338 //-----------------------------------------------------------------------------
339 template <typename TInteger, typename TQuotient>
340 inline
341 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
342 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
343 partial( Quotient kp ) const
344 {
345  ASSERT( ( ((Quotient)-2) <= kp ) && ( kp <= k() ) );
346  return reduced( k() - kp );
347 }
348 //-----------------------------------------------------------------------------
349 template <typename TInteger, typename TQuotient>
350 inline
351 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
352 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
353 reduced( Quotient i ) const
354 {
355  ASSERT( ( ((Quotient)0) <= i ) && ( i <= ( k()+((Quotient)2) ) ) );
356  Node* n = this->myNode;
357 
358  bool bleft = ( n->k & NumberTraits<Quotient>::ONE )
359  != NumberTraits<Quotient>::ZERO;
360  while ( i-- > NumberTraits<Quotient>::ZERO )
361  {
362  n = bleft ? n->ascendantLeft : n->ascendantRight;
363  bleft = ! bleft;
364  }
365  return Fraction( n );
366 }
367 //-----------------------------------------------------------------------------
368 template <typename TInteger, typename TQuotient>
369 inline
370 void
371 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
372 push_back( const std::pair<Quotient, Quotient> & quotient )
373 {
374  pushBack( quotient );
375 }
376 //-----------------------------------------------------------------------------
377 template <typename TInteger, typename TQuotient>
378 inline
379 void
380 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
381 pushBack( const std::pair<Quotient, Quotient> & quotient )
382 {
383  // std::vector<Quotient> quots;
384  // if ( ! null() )
385  // {
386  // this->getCFrac( quots );
387  // std::cerr << "F[";
388  // for ( unsigned int i = 0; i < quots.size(); ++i )
389  // std::cerr << " " << quots[ i ];
390  // }
391  // else std::cerr << "[";
392  // std::cerr << "] + " << "(" << quotient.first
393  // << "," << quotient.second << ")";
394  if ( null() )
395  {
396  ASSERT( quotient.second <= NumberTraits<Quotient>::ZERO );
397  if ( quotient.second < NumberTraits<Quotient>::ZERO )
398  this->operator=( oneOverZero() );
399  else if ( quotient.first == NumberTraits<Quotient>::ZERO ) // (0,0)
400  this->operator=( zeroOverOne() );
401  else
402  {
403  Fraction f = zeroOverOne();
404  for ( Quotient i = 0; i < quotient.first; ++i )
405  f = f.right();
406  this->operator=( f );
407  }
408  }
409  else if ( NumberTraits<Quotient>::even( quotient.second ) )
410  {
411  Fraction f = left();
412  for ( Quotient i = 1; i < quotient.first; ++i )
413  f = f.right();
414  this->operator=( f );
415  }
416  else
417  {
418  Fraction f = right();
419  for ( Quotient i = 1; i < quotient.first; ++i )
420  f = f.left();
421  this->operator=( f );
422  }
423  // quots.clear();
424  // this->getCFrac( quots );
425  // std::cerr << " => F[";
426  // for ( unsigned int i = 0; i < quots.size(); ++i )
427  // std::cerr << " " << quots[ i ];
428  // std::cerr << "]" << std::endl;
429 }
430 //-----------------------------------------------------------------------------
431 template <typename TInteger, typename TQuotient>
432 inline
433 void
434 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
435 getSplit( Fraction & f1, Fraction & f2 ) const
436 {
437  f1.myNode = myNode->ascendantLeft;
438  f2.myNode = myNode->ascendantRight;
439 }
440 //-----------------------------------------------------------------------------
441 template <typename TInteger, typename TQuotient>
442 inline
443 void
444 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
445 getSplitBerstel( Fraction & f1, Quotient & nb1,
446  Fraction & f2, Quotient & nb2 ) const
447 {
448  if ( odd() )
449  {
450  f1.myNode = myNode->ascendantLeft;
451  nb1 = this->u();
452  f2.myNode = f1.myNode->ascendantRight;
453  nb2 = 1;
454  }
455  else
456  {
457  f2.myNode = myNode->ascendantRight;
458  nb2 = this->u();
459  f1.myNode = f2.myNode->ascendantLeft;
460  nb1 = 1;
461  }
462 }
463 //-----------------------------------------------------------------------------
464 template <typename TInteger, typename TQuotient>
465 inline
466 void
467 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
468 getCFrac( std::vector<Quotient> & quotients ) const
469 {
470  ASSERT( this->k() >= NumberTraits<Quotient>::ZERO );
471  int64_t i = NumberTraits<Quotient>::castToInt64_t( this->k() );
472  quotients.resize( (unsigned int)i + 1 );
473  quotients[ (unsigned int)i-- ] = this->u();
474  Node* n = myNode;
475  bool bleft = odd() ? true : false;
476  while ( i >= 0 )
477  {
478  ASSERT( n->k >= NumberTraits<Quotient>::ZERO );
479  n = bleft ? n->ascendantLeft : n->ascendantRight;
480  quotients[ (unsigned int)i ] =
481  ( i == NumberTraits<Quotient>::castToInt64_t( n->k ) ) ? n->u : 1;
482  --i;
483  bleft = ! bleft;
484  }
485 }
486 //-----------------------------------------------------------------------------
487 template <typename TInteger, typename TQuotient>
488 inline
489 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction::ConstIterator
490 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
491 begin() const
492 {
493  CFracSequence* seq = new CFracSequence;
494  this->getCFrac( *seq );
495  return ConstIterator( seq, seq->begin() );
496 }
497 //-----------------------------------------------------------------------------
498 template <typename TInteger, typename TQuotient>
499 inline
500 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction::ConstIterator
501 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
502 end() const
503 {
504  static CFracSequence dummy;
505  return ConstIterator( 0, dummy.end() );
506 }
507 
508 template <typename TInteger, typename TQuotient>
509 inline
510 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
511 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
512 median(const Fraction & g) const
513 {
514  return Fraction(this->p()+g.p(),this->q()+g.q());
515 }
516 
517 //----------------------------------------------------------------------------
518 template <typename TInteger, typename TQuotient>
519 inline
520 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
521 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
522 simplestFractionInBetween(const Fraction & other) const
523 {
524  Fraction f(*this);
525  Fraction g(other);
526  Fraction res;
527 
528  if(f>g)
529  {
530  res = f; f = g; g = res;
531  }
532  res = Fraction();
533 
534  int i = 0;
535 
536  Value uf, ug;
537  ConstIterator itf=f.begin(), itg=g.begin();
538 
539  DGtal::functors::Abs<TInteger> absComputer;
540 
541  if(absComputer(f.p()*g.q()-f.q()*g.p())==NumberTraits<TInteger>::ONE)
542  return f.median(g);
543 
544  itf = f.begin(); itg = g.begin();
545  uf = *itf; ug = *itg;
546  while(uf.first == ug.first && i != f.k() && i != g.k())
547  {
548  res.push_back(std::make_pair(uf.first,i));
549  i++;
550  itf++;itg++;
551  uf = *itf;
552  ug = *itg;
553  }
554 
555  if(uf.first==ug.first)
556  {
557  if(i == f.k())
558  {
559  res.push_back(std::make_pair(uf.first,i));
560  i++;
561  itg++;
562  ug = *itg;
563  res.push_back(std::make_pair(ug.first+1,i));
564  }
565  else
566  {
567  res.push_back(std::make_pair(uf.first,i));
568  i++;
569  itf++;
570  uf = *itf;
571  res.push_back(std::make_pair(uf.first+1,i));
572  }
573  }
574  else
575  {
576  if(i!=f.k() && i != g.k())
577  (uf.first<ug.first)?res.push_back(std::make_pair(uf.first+1,i)):res.push_back(std::make_pair(ug.first+1,i));
578  else
579  if(i == f.k() && i == g.k())
580  (uf.first<ug.first)?res.push_back(std::make_pair(uf.first+1,i)):res.push_back(std::make_pair(ug.first+1,i));
581  else
582  if(i==f.k())
583  {
584  if(uf.first < ug.first)
585  res.push_back(std::make_pair(uf.first+1,i));
586  else
587  if(uf.first == ug.first + 1)
588  {
589  res.push_back(std::make_pair(ug.first,i));
590  i++;
591  itg++;
592  ug = *itg;
593  if(ug.first==NumberTraits<TInteger>::ONE)
594  {
595  res.push_back(std::make_pair(ug.first,i));
596  i++;
597  itg++;
598  ug = *itg;
599  res.push_back(std::make_pair(ug.first+1,i));
600  }
601  else
602  res.push_back(std::make_pair(2,i));
603  }
604  else
605  res.push_back(std::make_pair(ug.first+1,i));
606  }
607  else
608  {
609  if(ug.first < uf.first)
610  res.push_back(std::make_pair(ug.first+1,i));
611  else
612  if(ug.first == uf.first + 1)
613  {
614  res.push_back(std::make_pair(uf.first,i));
615  i++;
616  itf++;
617  uf = *itf;
618  if(uf.first==NumberTraits<TInteger>::ONE)
619  {
620  res.push_back(std::make_pair(uf.first,i));
621  i++;
622  itf++;
623  uf = *itf;
624  res.push_back(std::make_pair(uf.first+1,i));
625  }
626  else
627  res.push_back(std::make_pair(2,i));
628  }
629  else
630  res.push_back(std::make_pair(uf.first+1,i));
631 
632  }
633  }
634 
635  return res;
636 }
637 
638 
639 //-----------------------------------------------------------------------------
640 template <typename TInteger, typename TQuotient>
641 inline
642 void
643 DGtal::SternBrocot<TInteger, TQuotient>::Fraction::
644 selfDisplay( std::ostream & out ) const
645 {
646  if ( this->null() ) out << "[Fraction null]";
647  else
648  {
649  out << "[Fraction f=" << this->p()
650  << "/" << this->q()
651  << " u=" << this->u()
652  << " k=" << this->k()
653  << std::flush;
654  std::vector<Quotient> quotients;
655  if ( this->k() >= 0 )
656  {
657  this->getCFrac( quotients );
658  out << " [" << quotients[ 0 ];
659  for ( unsigned int i = 1; i < quotients.size(); ++i )
660  out << "," << quotients[ i ];
661  out << "]";
662  }
663  out << " ]";
664  }
665 }
666 
667 ///////////////////////////////////////////////////////////////////////////////
668 // DGtal::SternBrocot<TInteger, TQuotient>
669 
670 //-----------------------------------------------------------------------------
671 template <typename TInteger, typename TQuotient>
672 inline
673 DGtal::SternBrocot<TInteger, TQuotient>::~SternBrocot()
674 {
675  if ( myOneOverOne != 0 ) delete myOneOverOne;
676  if ( myOneOverZero != 0 ) delete myOneOverZero;
677  if ( myZeroOverOne != 0 ) delete myZeroOverOne;
678 }
679 //-----------------------------------------------------------------------------
680 template <typename TInteger, typename TQuotient>
681 inline
682 DGtal::SternBrocot<TInteger, TQuotient>::SternBrocot()
683 {
684  myOneOverZero = new Node( NumberTraits<Integer>::ONE,
685  NumberTraits<Integer>::ZERO,
686  NumberTraits<Quotient>::ZERO,
687  -NumberTraits<Quotient>::ONE,
688  myZeroOverOne, 0, myOneOverOne, 0,
689  myZeroOverOne );
690  myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
691  NumberTraits<Integer>::ONE,
692  NumberTraits<Quotient>::ZERO,
693  NumberTraits<Quotient>::ZERO,
694  myZeroOverOne, myOneOverZero, 0, myOneOverOne,
695  myOneOverZero );
696  myOneOverOne = new Node( NumberTraits<Integer>::ONE,
697  NumberTraits<Integer>::ONE,
698  NumberTraits<Quotient>::ONE,
699  NumberTraits<Quotient>::ZERO,
700  myZeroOverOne, myOneOverZero, 0, 0,
701  myOneOverOne );
702  myOneOverZero->ascendantLeft = myZeroOverOne;
703  myOneOverZero->descendantLeft = myOneOverOne;
704  myOneOverZero->inverse = myZeroOverOne;
705  myZeroOverOne->ascendantLeft = myZeroOverOne;
706  myZeroOverOne->descendantRight = myOneOverOne;
707  myOneOverOne->inverse = myOneOverOne;
708  nbFractions = 3;
709 }
710 //-----------------------------------------------------------------------------
711 template <typename TInteger, typename TQuotient>
712 inline
713 DGtal::SternBrocot<TInteger, TQuotient> &
714 DGtal::SternBrocot<TInteger, TQuotient>::instance()
715 {
716  if ( singleton == 0 )
717  singleton = new SternBrocot;
718  return *singleton;
719 }
720 
721 
722 //-----------------------------------------------------------------------------
723 template <typename TInteger, typename TQuotient>
724 inline
725 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
726 DGtal::SternBrocot<TInteger, TQuotient>::zeroOverOne()
727 {
728  return Fraction( instance().myZeroOverOne );
729 }
730 //-----------------------------------------------------------------------------
731 template <typename TInteger, typename TQuotient>
732 inline
733 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
734 DGtal::SternBrocot<TInteger, TQuotient>::oneOverZero()
735 {
736  return Fraction( instance().myOneOverZero );
737 }
738 
739 ///////////////////////////////////////////////////////////////////////////////
740 // Interface - public :
741 
742 /**
743  * Writes/Displays the object on an output stream.
744  * @param out the output stream where the object is written.
745  */
746 template <typename TInteger, typename TQuotient>
747 inline
748 void
749 DGtal::SternBrocot<TInteger, TQuotient>::display( std::ostream & out,
750  const Fraction & f )
751 {
752  if ( f.null() ) out << "[Fraction null]";
753  else
754  {
755  out << "[Fraction f=" << f.p()
756  << "/" << f.q()
757  << " u=" << f.u()
758  << " k=" << f.k()
759  << std::flush;
760  std::vector<Quotient> quotients;
761  if ( f.k() >= 0 )
762  {
763  f.getCFrac( quotients );
764  out << " [" << quotients[ 0 ];
765  for ( unsigned int i = 1; i < quotients.size(); ++i )
766  out << "," << quotients[ i ];
767  out << "]";
768  }
769  out << " ]";
770  }
771 }
772 
773 /**
774  * Checks the validity/consistency of the object.
775  * @return 'true' if the object is valid, 'false' otherwise.
776  */
777 template <typename TInteger, typename TQuotient>
778 inline
779 bool
780 DGtal::SternBrocot<TInteger, TQuotient>::isValid() const
781 {
782  return true;
783 }
784 
785 ///////////////////////////////////////////////////////////////////////////////
786 // class SternBrocot
787 ///////////////////////////////////////////////////////////////////////////////
788 template <typename TInteger, typename TQuotient>
789 inline
790 typename DGtal::SternBrocot<TInteger, TQuotient>::Fraction
791 DGtal::SternBrocot<TInteger, TQuotient>::fraction
792 ( Integer p, Integer q,
793  Fraction ancestor )
794 {
795  IntegerComputer<Integer> ic;
796  Integer g = ic.gcd( p, q );
797  if ( g != NumberTraits<Integer>::ZERO )
798  {
799  p /= g;
800  q /= g;
801  }
802  // special case 1/0
803  if ( ( p == NumberTraits<Integer>::ONE )
804  && ( q == NumberTraits<Integer>::ZERO ) ) return oneOverZero();
805  // other positive fractions
806  while ( ! ancestor.equals( p, q ) )
807  {
808  ASSERT( ( p + q ) >= ( ancestor.p() + ancestor.q() )
809  && "[ImaGene::SternBrocot::fraction] bad ancestor." );
810  ancestor = ancestor.lessThan( p, q )
811  ? ancestor.right()
812  : ancestor.left();
813  }
814  return ancestor;
815 }
816 
817 
818 ///////////////////////////////////////////////////////////////////////////////
819 // Implementation of inline functions //
820 
821 // JOL: invalid overloading
822 // template <typename TInteger, typename TQuotient>
823 // inline
824 // std::ostream&
825 // DGtal::operator<< ( std::ostream & out,
826 // const typename SternBrocot<TInteger, TQuotient>::Fraction & object )
827 // {
828 // typedef SternBrocot<TInteger,TQuotient> SB;
829 // SB::display( out, object );
830 // return out;
831 // }
832 
833 // //
834 ///////////////////////////////////////////////////////////////////////////////
835 
836