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