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