DGtal  1.5.beta
LightSternBrocot.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 LightSternBrocot.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, typename TMap>
42 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>*
43 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::singleton = 0;
44 
45 ///////////////////////////////////////////////////////////////////////////////
46 // IMPLEMENTATION of inline methods.
47 ///////////////////////////////////////////////////////////////////////////////
48 
49 ///////////////////////////////////////////////////////////////////////////////
50 // ----------------------- Standard services ------------------------------
51 
52 ///////////////////////////////////////////////////////////////////////////////
53 // DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Node
54 //-----------------------------------------------------------------------------
55 template <typename TInteger, typename TQuotient, typename TMap>
56 inline
57 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Node::
58 Node( Integer p1, Integer q1, Quotient u1, Quotient k1,
59  Node* _ascendant )
60  : p( p1 ), q( q1 ), u( u1 ), k( k1 ),
61  ascendant( _ascendant )
62 {
63  // if ( k == 0 )
64  //std::cerr << "(" << p1 << "/" << q1 << "," << u1 << "," << k1 << ")";
65 }
66 
67 ///////////////////////////////////////////////////////////////////////////////
68 // DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
69 //-----------------------------------------------------------------------------
70 template <typename TInteger, typename TQuotient, typename TMap>
71 inline
72 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
73 Fraction( Integer aP, Integer aQ, Fraction )
74 {
75  // special case 1/0
76  if ( ( aP == NumberTraits<Integer>::ONE )
77  && ( aQ == NumberTraits<Integer>::ZERO ) )
78  this->operator=( oneOverZero() );
79  else
80  {
81  Fraction f = zeroOverOne();
82  bool sup1 = aP > aQ;
83  if ( sup1 ) std::swap( aP, aQ );
84  Integer _quot, _rem;
85  IntegerComputer<Integer> ic;
86  Quotient v;
87  bool prec_was_one = false;
88  Quotient j = NumberTraits<Quotient>::ZERO;
89  while ( aQ != NumberTraits<Integer>::ZERO )
90  {
91  ic.getEuclideanDiv( _quot, _rem, aP, aQ );
92  v = (Quotient)NumberTraits<Integer>::castToInt64_t( _quot );
93  if ( f.k() == j )
94  f = f.next( v );
95  else
96  f = f.next1( v );
97  if ( v != 0 ) ++j;
98  aP = aQ;
99  aQ = _rem;
100  }
101  if ( prec_was_one ) f = f.next( NumberTraits<Quotient>::ONE );
102  this->operator=( sup1 ? f.inverse() : f );
103  }
104 }
105 //-----------------------------------------------------------------------------
106 template <typename TInteger, typename TQuotient, typename TMap>
107 inline
108 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
109 Fraction( Node* sb_node, bool sup1 )
110  : myNode( sb_node ), mySup1( sup1 )
111 {
112 }
113 //-----------------------------------------------------------------------------
114 template <typename TInteger, typename TQuotient, typename TMap>
115 inline
116 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
117 Fraction( const Self & other )
118  : myNode( other.myNode ), mySup1( other.mySup1 )
119 {
120 }
121 //-----------------------------------------------------------------------------
122 template <typename TInteger, typename TQuotient, typename TMap>
123 inline
124 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction &
125 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
126 operator=( const Self & other )
127 {
128  if ( this != &other )
129  {
130  myNode = other.myNode;
131  mySup1 = other.mySup1;
132  }
133  return *this;
134 }
135 //-----------------------------------------------------------------------------
136 template <typename TInteger, typename TQuotient, typename TMap>
137 inline
138 bool
139 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
140 null() const
141 {
142  return myNode == 0;
143 }
144 //-----------------------------------------------------------------------------
145 template <typename TInteger, typename TQuotient, typename TMap>
146 inline
147 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Integer
148 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
149 p() const
150 {
151  return myNode ? ( mySup1 ? myNode->q : myNode->p ) : 0;
152 }
153 //-----------------------------------------------------------------------------
154 template <typename TInteger, typename TQuotient, typename TMap>
155 inline
156 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Integer
157 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
158 q() const
159 {
160  return myNode ? ( mySup1 ? myNode->p : myNode->q ) : 0;
161 }
162 //-----------------------------------------------------------------------------
163 template <typename TInteger, typename TQuotient, typename TMap>
164 inline
165 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Quotient
166 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
167 u() const
168 {
169  ASSERT( myNode != 0 );
170  return myNode->u;
171 }
172 //-----------------------------------------------------------------------------
173 template <typename TInteger, typename TQuotient, typename TMap>
174 inline
175 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Quotient
176 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
177 k() const
178 {
179  ASSERT( myNode != 0 );
180  if ( mySup1 )
181  {
182  // if ( ( myNode->k == 0 )
183  // && ( myNode != instance().myZeroOverOne )
184  // && ( myNode != instance().myOneOverOne ) )
185  // {
186  // std::cerr << "****ERROR**** "
187  // << " sup1=" << mySup1
188  // << " p=" << myNode->p
189  // << " q=" << myNode->q
190  // << " k=" << myNode->k
191  // << " u=" << myNode->u;
192  // std::cerr << std::endl;
193  // }
194  ASSERT( ( myNode->k != 0 )
195  || ( myNode == instance().myZeroOverOne )
196  || ( myNode == instance().myOneOverOne ) );
197  ASSERT( ( myNode->k != -1 )
198  || ( myNode == instance().myOneOverZero ) );
199  if ( myNode->k == -NumberTraits<Quotient>::ONE )
200  return NumberTraits<Quotient>::ZERO;
201  if ( myNode == instance().myZeroOverOne )
202  return -NumberTraits<Quotient>::ONE;
203  else if ( myNode == instance().myOneOverOne )
204  return NumberTraits<Quotient>::ZERO;
205  else
206  return myNode->k - NumberTraits<Quotient>::ONE;
207  }
208  return myNode->k;
209 }
210 //-----------------------------------------------------------------------------
211 template <typename TInteger, typename TQuotient, typename TMap>
212 inline
213 bool
214 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
215 equals( Integer p1, Integer q1 ) const
216 {
217  return ( this->p() == p1 ) && ( this->q() == q1 );
218 }
219 //-----------------------------------------------------------------------------
220 template <typename TInteger, typename TQuotient, typename TMap>
221 inline
222 bool
223 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
224 lessThan( Integer p1, Integer q1 ) const
225 {
226  Integer d = p() * q1 - q() * p1;
227  return d < NumberTraits<Integer>::ZERO;
228 }
229 //-----------------------------------------------------------------------------
230 template <typename TInteger, typename TQuotient, typename TMap>
231 inline
232 bool
233 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
234 moreThan( Integer p1, Integer q1 ) const
235 {
236  Integer d = p() * q1 - q() * p1;
237  return d > NumberTraits<Integer>::ZERO;
238 }
239 //-----------------------------------------------------------------------------
240 template <typename TInteger, typename TQuotient, typename TMap>
241 inline
242 bool
243 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
244 operator==( const Fraction & other ) const
245 {
246  if ( mySup1 == other.mySup1 )
247  return ( myNode == other.myNode );
248  else
249  return ( ( myNode->p == other.myNode->q )
250  && ( myNode->q == other.myNode->p ) );
251 }
252 //-----------------------------------------------------------------------------
253 template <typename TInteger, typename TQuotient, typename TMap>
254 inline
255 bool
256 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
257 operator!=( const Fraction & other ) const
258 {
259  return ! this->operator==( other );
260 }
261 //-----------------------------------------------------------------------------
262 template <typename TInteger, typename TQuotient, typename TMap>
263 inline
264 bool
265 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
266 operator<( const Fraction & other ) const
267 {
268  return this->lessThan( other.p(), other.q() );
269 }
270 //-----------------------------------------------------------------------------
271 template <typename TInteger, typename TQuotient, typename TMap>
272 inline
273 bool
274 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
275 operator>( const Fraction & other ) const
276 {
277  return this->moreThan( other.p(), other.q() );
278 }
279 //-----------------------------------------------------------------------------
280 /// @return the fraction [u_0, ..., u_n, v] if [u_0, ..., u_n]
281 /// is the current fraction. Construct it if it does not exist yet.
282 template <typename TInteger, typename TQuotient, typename TMap>
283 inline
284 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
285 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
286 next( Quotient v ) const
287 {
288  typedef typename MapQuotientToNode::iterator Iterator;
289  ASSERT( ! this->null() );
290  if ( v == NumberTraits<Quotient>::ZERO )
291  return *this;
292  else if ( ( v == NumberTraits<Quotient>::ONE )
293  && ( this->myNode != instance().myZeroOverOne ) )
294  { // Specific case: same depth.
295  v += u();
296  bool anc_direct = isAncestorDirect();
297  Iterator itkey = anc_direct
298  ? myNode->ascendant->descendant.find( v )
299  : myNode->ascendant->descendant2.find( v );
300  Iterator itend = anc_direct
301  ? myNode->ascendant->descendant.end()
302  : myNode->ascendant->descendant2.end();
303  if ( itkey != itend ) // found
304  return Fraction( itkey->second, mySup1 );
305  Node* new_node = new Node( myNode->p + myNode->ascendant->p,
306  myNode->q + myNode->ascendant->q,
307  v, myNode->k, myNode->ascendant );
308  if (anc_direct ) myNode->ascendant->descendant[ v ] = new_node;
309  else myNode->ascendant->descendant2[ v ] = new_node;
310  ++( instance().nbFractions );
311  return Fraction( new_node, mySup1 );
312  }
313  else
314  {
315  Iterator itkey = myNode->descendant.find( v );
316  if ( itkey != myNode->descendant.end() ) // found
317  {
318  return Fraction( itkey->second, mySup1 );
319  }
320  Node* new_node =
321  new Node( myNode->p * v + myNode->ascendant->p,
322  myNode->q * v + myNode->ascendant->q,
323  v, myNode->k + 1, myNode );
324  myNode->descendant[ v ] = new_node;
325  ++( instance().nbFractions );
326  return Fraction( new_node, mySup1 );
327  }
328 }
329 //-----------------------------------------------------------------------------
330 /// @return the fraction [u_0, ..., u_n -1, 1, v] if [u_0, ..., u_n]
331 /// is the current fraction. Construct it if it does not exist yet.
332 template <typename TInteger, typename TQuotient, typename TMap>
333 inline
334 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
335 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
336 next1( Quotient v ) const
337 {
338  typedef typename MapQuotientToNode::iterator Iterator;
339  ASSERT( ! this->null() );
340  if ( v == NumberTraits<Quotient>::ZERO )
341  return *this;
342  else if ( v == NumberTraits<Quotient>::ONE )
343  { // Specific case: depth + 1. [u_0, ..., u_n] => [u_0, ..., u_n -1, 2]
344  Fraction f = father();
345  if ( f.myNode->k == myNode->k )
346  return father().next( 2 );
347  else
348  return father().next1( 2 );
349  }
350  else
351  { // Gen case: [u_0, ..., u_n] => [u_0, ..., u_n -1, 1, v]
352  Iterator itkey = myNode->descendant2.find( v );
353  if ( itkey != myNode->descendant2.end() ) // found
354  return Fraction( itkey->second, mySup1 );
355  Node* new_node
356  = new Node( myNode->p * v + myNode->p - myNode->ascendant->p,
357  myNode->q * v + myNode->q - myNode->ascendant->q,
358  v, myNode->k + 2, myNode );
359  myNode->descendant2[ v ] = new_node;
360  ++( instance().nbFractions );
361  return Fraction( new_node, mySup1 );
362  }
363 }
364 //-----------------------------------------------------------------------------
365 template <typename TInteger, typename TQuotient, typename TMap>
366 inline
367 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
368 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
369 left() const
370 {
371  if ( myNode->isSameDepthLeft() )
372  // Use the fact that [...,u_n,1] = [...,u_n + 1]
373  return next( NumberTraits<Quotient>::ONE );
374  else
375  return next1( NumberTraits<Quotient>::ONE );
376 }
377 //-----------------------------------------------------------------------------
378 template <typename TInteger, typename TQuotient, typename TMap>
379 inline
380 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
381 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
382 right() const
383 {
384  if ( ! myNode->isSameDepthLeft() )
385  // Use the fact that [...,u_n,1] = [...,u_n + 1]
386  return next( NumberTraits<Quotient>::ONE );
387  else
388  return next1( NumberTraits<Quotient>::ONE );
389 }
390 //-----------------------------------------------------------------------------
391 template <typename TInteger, typename TQuotient, typename TMap>
392 inline
393 bool
394 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
395 even() const
396 {
397  return NumberTraits<Quotient>::even( k() );
398 }
399 //-----------------------------------------------------------------------------
400 template <typename TInteger, typename TQuotient, typename TMap>
401 inline
402 bool
403 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
404 odd() const
405 {
406  return NumberTraits<Quotient>::odd( k() );
407 }
408 //-----------------------------------------------------------------------------
409 template <typename TInteger, typename TQuotient, typename TMap>
410 inline
411 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
412 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
413 ancestor() const
414 {
415  return Fraction( myNode->ascendant, mySup1 );
416 }
417 //-----------------------------------------------------------------------------
418 template <typename TInteger, typename TQuotient, typename TMap>
419 inline
420 bool
421 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
422 isAncestorDirect() const
423 {
424  return myNode->k == myNode->ascendant->k + NumberTraits<Quotient>::ONE;
425 }
426 //-----------------------------------------------------------------------------
427 template <typename TInteger, typename TQuotient, typename TMap>
428 inline
429 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
430 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
431 father() const
432 {
433  if ( isAncestorDirect() )
434  return ancestor().next( u() - NumberTraits<Quotient>::ONE );
435  else
436  return ancestor().next1( u() - NumberTraits<Quotient>::ONE );
437 }
438 //-----------------------------------------------------------------------------
439 template <typename TInteger, typename TQuotient, typename TMap>
440 inline
441 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
442 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
443 father( Quotient m ) const
444 {
445  if ( m >= NumberTraits<Quotient>::ONE ) // >= 1
446  {
447  return isAncestorDirect()
448  ? ancestor().next( m )
449  : ancestor().next1( m );
450  }
451  else // == 0
452  return reduced( 2 );
453  // isAncestorDirect()
454  // ? ancestor().ancestor()
455  // : ancestor();
456 }
457 //-----------------------------------------------------------------------------
458 template <typename TInteger, typename TQuotient, typename TMap>
459 inline
460 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
461 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
462 previousPartial() const
463 {
464  return ancestor();
465 }
466 //-----------------------------------------------------------------------------
467 template <typename TInteger, typename TQuotient, typename TMap>
468 inline
469 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
470 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
471 inverse() const
472 {
473  return Fraction( myNode, ! mySup1 );
474 }
475 //-----------------------------------------------------------------------------
476 template <typename TInteger, typename TQuotient, typename TMap>
477 inline
478 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
479 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
480 partial( Quotient kp ) const
481 {
482  ASSERT( ( ((Quotient)-2) <= kp ) && ( kp <= myNode->k ) );
483  return reduced( myNode->k - kp );
484 }
485 //-----------------------------------------------------------------------------
486 template <typename TInteger, typename TQuotient, typename TMap>
487 inline
488 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
489 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
490 reduced( Quotient i ) const
491 {
492  ASSERT( ( ((Quotient)0) <= i ) && ( i <= ( myNode->k+((Quotient)2) ) ) );
493  Fraction f( *this );
494  Quotient j = myNode->k;
495  for ( ; i != NumberTraits<Quotient>::ZERO; --i )
496  {
497  f = ( j == f.myNode->k ) ? f.ancestor() : f.father();
498  --j;
499  }
500  return f;
501 }
502 //-----------------------------------------------------------------------------
503 template <typename TInteger, typename TQuotient, typename TMap>
504 inline
505 void
506 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
507 push_back( const std::pair<Quotient, Quotient> & quotient )
508 {
509  pushBack( quotient );
510 }
511 //-----------------------------------------------------------------------------
512 template <typename TInteger, typename TQuotient, typename TMap>
513 inline
514 void
515 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
516 pushBack( const std::pair<Quotient, Quotient> & ) //quotient )
517 {
518  ASSERT( false
519  && "UNIMPLEMENTED. Use SternBrocot::Fraction or LighterSternBrocot::Fraction instead." );
520 }
521 //-----------------------------------------------------------------------------
522 template <typename TInteger, typename TQuotient, typename TMap>
523 inline
524 void
525 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
526 getSplit( Fraction & f1, Fraction & f2 ) const
527 {
528  if ( odd() )
529  {
530  f1 = ancestor();
531  f2 = father();
532  }
533  else
534  {
535  f1 = father();
536  f2 = ancestor();
537  }
538 }
539 //-----------------------------------------------------------------------------
540 template <typename TInteger, typename TQuotient, typename TMap>
541 inline
542 void
543 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
544 getSplitBerstel( Fraction & f1, Quotient & nb1,
545  Fraction & f2, Quotient & nb2 ) const
546 {
547  // TODO
548  if ( odd() )
549  {
550  f1 = ancestor();
551  f2 = reduced( 2 );
552  nb1 = this->u();
553  nb2 = 1;
554  }
555  else
556  {
557  f1 = reduced( 2 );
558  f2 = ancestor();
559  nb1 = 1;
560  nb2 = this->u();
561  }
562 }
563 //-----------------------------------------------------------------------------
564 template <typename TInteger, typename TQuotient, typename TMap>
565 inline
566 void
567 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
568 getCFrac( std::vector<Quotient> & quotients ) const
569 {
570  ASSERT( myNode->k >= NumberTraits<Quotient>::ZERO );
571  int64_t i = NumberTraits<Quotient>::castToInt64_t( myNode->k );
572  if ( null() ) return;
573  if ( mySup1 && ( i > 0 ) ) --i;
574  quotients.resize( i + 1 );
575  Fraction f( *this );
576  Quotient j = myNode->k;
577  while ( i >= 0 && ( f.myNode->k >= 0 ) )
578  {
579  quotients[ i ] = ( j == f.myNode->k ) ? f.u() : NumberTraits<Quotient>::ONE;
580  f = ( j == f.myNode->k ) ? f.ancestor() : f.father();
581  --i, --j;
582  }
583 }
584 //-----------------------------------------------------------------------------
585 template <typename TInteger, typename TQuotient, typename TMap>
586 inline
587 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::ConstIterator
588 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
589 begin() const
590 {
591  CFracSequence* seq = new CFracSequence;
592  this->getCFrac( *seq );
593  return ConstIterator( seq, seq->begin() );
594 }
595 //-----------------------------------------------------------------------------
596 template <typename TInteger, typename TQuotient, typename TMap>
597 inline
598 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::ConstIterator
599 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
600 end() const
601 {
602  static CFracSequence dummy;
603  return ConstIterator( 0, dummy.end() );
604 }
605 //-----------------------------------------------------------------------------
606 template <typename TInteger, typename TQuotient, typename TMap>
607 inline
608 void
609 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction::
610 selfDisplay( std::ostream & out ) const
611 {
612  if ( this->null() ) out << "[Fraction null]";
613  else
614  {
615  out << "[Fraction f=" << this->p()
616  << "/" << this->q()
617  << " u=" << this->u()
618  << " k=" << this->k()
619  << std::flush;
620  std::vector<Quotient> quotients;
621  if ( this->k() >= 0 )
622  {
623  this->getCFrac( quotients );
624  out << " [" << quotients[ 0 ];
625  for ( unsigned int i = 1; i < quotients.size(); ++i )
626  out << "," << quotients[ i ];
627  out << "]";
628  }
629  out << " ]";
630  }
631 }
632 
633 ///////////////////////////////////////////////////////////////////////////////
634 // DGtal::LightSternBrocot<TInteger, TQuotient, TMap>
635 
636 //-----------------------------------------------------------------------------
637 template <typename TInteger, typename TQuotient, typename TMap>
638 inline
639 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::~LightSternBrocot()
640 {
641  if ( myZeroOverOne != 0 ) delete myZeroOverOne;
642  if ( myOneOverZero != 0 ) delete myOneOverZero;
643  if ( myOneOverOne != 0 ) delete myOneOverOne;
644 }
645 //-----------------------------------------------------------------------------
646 template <typename TInteger, typename TQuotient, typename TMap>
647 inline
648 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::LightSternBrocot()
649 {
650  // // Version 1/1 has depth 0.
651  // myOneOverZero = new Node( NumberTraits<Integer>::ONE,
652  // NumberTraits<Integer>::ZERO,
653  // NumberTraits<Quotient>::ZERO,
654  // -NumberTraits<Quotient>::ONE,
655  // 0 );
656  // myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
657  // NumberTraits<Integer>::ONE,
658  // NumberTraits<Quotient>::ZERO,
659  // NumberTraits<Quotient>::ZERO,
660  // myOneOverZero );
661  // myOneOverZero->ascendant = 0; //myZeroOverOne;
662  // myOneOverOne = new Node( NumberTraits<Integer>::ONE,
663  // NumberTraits<Integer>::ONE,
664  // NumberTraits<Quotient>::ONE,
665  // NumberTraits<Quotient>::ZERO,
666  // myOneOverZero );
667  // myOneOverZero->descendant[ NumberTraits<Quotient>::ZERO ] = myZeroOverOne;
668  // myOneOverZero->descendant[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
669  // nbFractions = 3;
670 
671  // Version 1/1 has depth 1.
672  myOneOverZero = new Node( NumberTraits<Integer>::ONE,
673  NumberTraits<Integer>::ZERO,
674  NumberTraits<Quotient>::ZERO,
675  -NumberTraits<Quotient>::ONE,
676  0 );
677  myZeroOverOne = new Node( NumberTraits<Integer>::ZERO,
678  NumberTraits<Integer>::ONE,
679  NumberTraits<Quotient>::ZERO,
680  NumberTraits<Quotient>::ZERO,
681  myOneOverZero );
682  myOneOverZero->ascendant = 0;
683  myOneOverOne = new Node( NumberTraits<Integer>::ONE,
684  NumberTraits<Integer>::ONE,
685  NumberTraits<Quotient>::ONE,
686  NumberTraits<Quotient>::ONE,
687  myZeroOverOne );
688  myZeroOverOne->descendant[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
689  myOneOverZero->descendant[ NumberTraits<Quotient>::ZERO ] = myZeroOverOne;
690  myOneOverZero->descendant[ NumberTraits<Quotient>::ONE ] = myZeroOverOne;
691  myOneOverZero->descendant2[ NumberTraits<Quotient>::ONE ] = myOneOverOne;
692  nbFractions = 3;
693 }
694 //-----------------------------------------------------------------------------
695 template <typename TInteger, typename TQuotient, typename TMap>
696 inline
697 DGtal::LightSternBrocot<TInteger, TQuotient, TMap> &
698 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::instance()
699 {
700  if ( singleton == 0 )
701  singleton = new LightSternBrocot;
702  return *singleton;
703 }
704 
705 //-----------------------------------------------------------------------------
706 template <typename TInteger, typename TQuotient, typename TMap>
707 inline
708 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
709 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::zeroOverOne()
710 {
711  return Fraction( instance().myZeroOverOne, false );
712 }
713 //-----------------------------------------------------------------------------
714 template <typename TInteger, typename TQuotient, typename TMap>
715 inline
716 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
717 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::oneOverZero()
718 {
719  return Fraction( instance().myZeroOverOne, true );
720 }
721 
722 ///////////////////////////////////////////////////////////////////////////////
723 // Interface - public :
724 
725 /**
726  * Writes/Displays the object on an output stream.
727  * @param out the output stream where the object is written.
728  */
729 template <typename TInteger, typename TQuotient, typename TMap>
730 inline
731 void
732 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::display( std::ostream & out,
733  const Fraction & f )
734 {
735  if ( f.null() ) out << "[Fraction null]";
736  else
737  {
738  out << "[Fraction f=" << f.p()
739  << "/" << f.q()
740  << " u=" << f.u()
741  << " k=" << f.k()
742  // << " s1=" << f.isSup1()
743  << std::flush;
744  std::vector<Quotient> quotients;
745  if ( f.k() >= 0 )
746  {
747  f.getCFrac( quotients );
748  out << " [" << quotients[ 0 ];
749  for ( unsigned int i = 1; i < quotients.size(); ++i )
750  out << "," << quotients[ i ];
751  out << "]";
752  }
753  out << " ]";
754  }
755 }
756 
757 /**
758  * Checks the validity/consistency of the object.
759  * @return 'true' if the object is valid, 'false' otherwise.
760  */
761 template <typename TInteger, typename TQuotient, typename TMap>
762 inline
763 bool
764 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::isValid() const
765 {
766  return true;
767 }
768 
769 ///////////////////////////////////////////////////////////////////////////////
770 // class LightSternBrocot
771 ///////////////////////////////////////////////////////////////////////////////
772 template <typename TInteger, typename TQuotient, typename TMap>
773 inline
774 typename DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::Fraction
775 DGtal::LightSternBrocot<TInteger, TQuotient, TMap>::fraction
776 ( Integer p, Integer q,
777  Fraction // ancestor
778  )
779 {
780  return Fraction( p, q );
781  // // special case 1/0
782  // if ( ( p == NumberTraits<Integer>::ONE )
783  // && ( q == NumberTraits<Integer>::ZERO ) )
784  // return oneOverZero();
785  // Fraction f = zeroOverOne();
786  // bool sup1 = p > q;
787  // if ( sup1 ) std::swap( p, q );
788  // Integer _quot, _rem;
789  // IntegerComputer<Integer> ic;
790  // Quotient v;
791  // bool prec_was_one = false;
792  // Quotient j = NumberTraits<Quotient>::ZERO;
793  // while ( q != NumberTraits<Integer>::ZERO )
794  // {
795  // ic.getEuclideanDiv( _quot, _rem, p, q );
796  // v = NumberTraits<Integer>::castToInt64_t( _quot );
797  // if ( f.k() == j )
798  // f = f.next( v );
799  // else
800  // f = f.next1( v );
801  // if ( v != 0 ) ++j;
802  // p = q;
803  // q = _rem;
804  // }
805  // if ( prec_was_one ) f = f.next( NumberTraits<Quotient>::ONE );
806  // return sup1 ? f.inverse() : f;
807 }
808 
809 
810 ///////////////////////////////////////////////////////////////////////////////
811 // Implementation of inline functions //
812 
813 // JOL: invalid overloading
814 // template <typename TInteger, typename TQuotient, typename TMap>
815 // inline
816 // std::ostream&
817 // DGtal::operator<< ( std::ostream & out,
818 // const typename LightSternBrocot<TInteger, TQuotient, TMap>::Fraction & object )
819 // {
820 // typedef LightSternBrocot<TInteger, TQuotient, TMap> SB;
821 // SB::display( out, object );
822 // return out;
823 // }
824 
825 // //
826 ///////////////////////////////////////////////////////////////////////////////