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