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