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