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