DGtal 1.4.2
Loading...
Searching...
No Matches
Pattern.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 Pattern.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 *
22 * @date 2012/03/07
23 *
24 * Implementation of inline methods defined in Pattern.h
25 *
26 * This file is part of the DGtal library.
27 */
28
29
30//////////////////////////////////////////////////////////////////////////////
31#include <cstdlib>
32//////////////////////////////////////////////////////////////////////////////
33
34///////////////////////////////////////////////////////////////////////////////
35// IMPLEMENTATION of inline methods.
36///////////////////////////////////////////////////////////////////////////////
37
38///////////////////////////////////////////////////////////////////////////////
39// ----------------------- Standard services ------------------------------
40
41//-----------------------------------------------------------------------------
42template <typename TFraction>
43inline
44DGtal::Pattern<TFraction>::~Pattern()
45{
46}
47//-----------------------------------------------------------------------------
48template <typename TFraction>
49inline
50DGtal::Pattern<TFraction>::Pattern( Fraction f )
51 : mySlope( f )
52{
53}
54//-----------------------------------------------------------------------------
55template <typename TFraction>
56inline
57DGtal::Pattern<TFraction>::Pattern( const Self & other )
58 : mySlope( other.mySlope )
59{
60}
61//-----------------------------------------------------------------------------
62template <typename TFraction>
63inline
64typename DGtal::Pattern<TFraction> &
65DGtal::Pattern<TFraction>::operator=( const Self & other )
66{
67 mySlope = other.mySlope;
68 return *this;
69}
70//-----------------------------------------------------------------------------
71template <typename TFraction>
72inline
73DGtal::Pattern<TFraction>::Pattern( Integer p, Integer q )
74{
75 IntegerComputer<Integer> ic;
76 Integer g = ic.gcd( p, q );
77 p /= g;
78 q /= g;
79 mySlope = Fraction( p, q );
80}
81//-----------------------------------------------------------------------------
82template <typename TFraction>
83inline
84std::string
85DGtal::Pattern<TFraction>::
86rE() const
87{
88 if ( mySlope.null() ) return "eps";
89 else if ( mySlope.k() == -2 )
90 {
91 return "0";
92 }
93 else if ( mySlope.k() == -NumberTraits<Quotient>::ONE )
94 {
95 return "1";
96 }
97 else if ( mySlope.k() == NumberTraits<Quotient>::ZERO )
98 {
99 std::string s( static_cast<int32_t>(NumberTraits<Integer>::castToInt64_t( mySlope.p() )),
100 '1' );
101 return '0' + s;
102 }
103 else
104 {
105 Fraction f1, f2;
106 Quotient nb1, nb2;
107 mySlope.getSplitBerstel( f1, nb1, f2, nb2 );
108 std::string s;
109 Self p1( f1 );
110 Self p2( f2 );
111 for ( Quotient i = 0; i < nb1; ++i ) s += p1.rE();
112 for ( Quotient i = 0; i < nb2; ++i ) s += p2.rE();
113 return s;
114 }
115}
116//-----------------------------------------------------------------------------
117template <typename TFraction>
118inline
119std::string
120DGtal::Pattern<TFraction>::
121rEs( const std::string & seps ) const
122{
123 if ( mySlope.null() ) return "eps";
124 else if ( mySlope.k() == -2 )
125 {
126 return "0";
127 }
128 else if ( mySlope.k() == -NumberTraits<Quotient>::ONE )
129 {
130 return "1";
131 }
132 else if ( mySlope.k() == NumberTraits<Quotient>::ZERO )
133 {
134 std::string s( static_cast<int32_t>(NumberTraits<Integer>::castToInt64_t( mySlope.p() )), '1' );
135 return '0' + s;
136 }
137 // else if ( mySlope.k() == NumberTraits<Quotient>::ONE )
138 // {
139 // std::string s( NumberTraits<Quotient>::castToInt64_t( mySlope.u() ), '0' );
140 // return s + '1';
141 // }
142 else
143 {
144 Fraction f1, f2;
145 Quotient nb1, nb2;
146 mySlope.getSplitBerstel( f1, nb1, f2, nb2 );
147 std::string s( 1, seps[ 0 ] );
148 Self p1( f1 );
149 Self p2( f2 );
150 for ( Quotient i = 0; i < nb1; ++i ) s += p1.rEs( seps );
151 s += seps[ 1 ];
152 for ( Quotient i = 0; i < nb2; ++i ) s += p2.rEs( seps );
153 s += seps[ 2 ];
154 return s;
155 }
156}
157//-----------------------------------------------------------------------------
158template <typename TFraction>
159inline
160typename DGtal::Pattern<TFraction>::Fraction
161DGtal::Pattern<TFraction>::
162slope() const
163{
164 return mySlope;
165}
166//-----------------------------------------------------------------------------
167template <typename TFraction>
168inline
169typename DGtal::Pattern<TFraction>::Integer
170DGtal::Pattern<TFraction>::
171length() const
172{
173 return mySlope.p() + mySlope.q();
174}
175//-----------------------------------------------------------------------------
176template <typename TFraction>
177inline
178typename DGtal::Pattern<TFraction>::Integer
179DGtal::Pattern<TFraction>::
180posU( Quotient k ) const
181{
182 ASSERT( ! slope().null() );
183 if ( k == NumberTraits<Quotient>::ZERO ) return NumberTraits<Integer>::ZERO;
184 else if ( k == NumberTraits<Quotient>::ONE ) return length();
185 else return length() * ((Integer) k);
186}
187//-----------------------------------------------------------------------------
188template <typename TFraction>
189inline
190typename DGtal::Pattern<TFraction>::Integer
191DGtal::Pattern<TFraction>::
192posL( Quotient k ) const
193{
194 ASSERT( ! slope().null() );
195 Integer pL = slope().odd() ? length() - previousPattern().length()
196 : previousPattern().length();
197 if ( k == NumberTraits<Quotient>::ZERO ) return pL;
198 else if ( k == NumberTraits<Quotient>::ONE ) return pL + length();
199 else return pL + length() * ((Integer) k);
200}
201//-----------------------------------------------------------------------------
202template <typename TFraction>
203inline
204typename DGtal::Pattern<TFraction>::Point2I
205DGtal::Pattern<TFraction>::
206U( Quotient k ) const
207{
208 ASSERT( ! slope().null() );
209 if ( k == NumberTraits<Quotient>::ZERO )
210 return Point2I( NumberTraits<Integer>::ZERO,
211 NumberTraits<Integer>::ZERO );
212 else if ( k == NumberTraits<Quotient>::ONE )
213 return Point2I( slope().q(),
214 slope().p() );
215 else
216 return Point2I( slope().q() * ((Integer) k ),
217 slope().p() * ((Integer) k) );
218}
219//-----------------------------------------------------------------------------
220template <typename TFraction>
221inline
222typename DGtal::Pattern<TFraction>::Point2I
223DGtal::Pattern<TFraction>::
224L( Quotient k ) const
225{
226 ASSERT( ! slope().null() );
227 Point2I pL( NumberTraits<Integer>::ONE,
228 -NumberTraits<Integer>::ONE ); // (1,-1)
229 pL += bezout();
230 if ( k == NumberTraits<Quotient>::ZERO )
231 return pL;
232 else
233 return pL + U( k );
234}
235//-----------------------------------------------------------------------------
236template <typename TFraction>
237inline
238typename DGtal::Pattern<TFraction>::Vector2I
239DGtal::Pattern<TFraction>::
240bezout() const
241{
242 return slope().odd()
243 ? U( 1 ) - previousPattern().U( 1 )
244 : previousPattern().U( 1 );
245}
246//-----------------------------------------------------------------------------
247template <typename TFraction>
248inline
249typename DGtal::Pattern<TFraction>::Vector2I
250DGtal::Pattern<TFraction>::
251v() const
252{
253 return Vector2I( slope().q(), slope().p() );
254}
255//-----------------------------------------------------------------------------
256template <typename TFraction>
257inline
258DGtal::Pattern<TFraction>
259DGtal::Pattern<TFraction>::
260previousPattern() const
261{
262 ASSERT( ( ! slope().null() ) );
263 // && ( slope().p() != NumberTraits<Quotient>::ZERO ) );
264 return Self( slope().previousPartial() );
265
266 // if ( slope().k() > NumberTraits<Quotient>::ZERO )
267 // return Self( slope().previousPartial() );
268 // else // if ( slope().k() == NumberTraits<Quotient>::ZERO )
269 // return ( slope().p() == NumberTraits<Quotient>::ZERO )
270 // ? Self( Fraction( 1, 0 ) )
271 // : Self( Fraction( 0, 1 ) );
272}
273//-----------------------------------------------------------------------------
274template <typename TFraction>
275inline
276bool
277DGtal::Pattern<TFraction>::
278getSmallestCoveringSubpattern( Pattern & subpattern,
279 Quotient & nb,
280 Vector2I & startPos,
281 Integer posA, Integer posB,
282 bool reversed ) const
283{
284 bool different = false;
285 Integer l = length();
286
287 ASSERT( ( 0 <= posA ) && ( posA < posB ) && ( posB <= l ) );
288 if ( slope().p() == 0 || slope().q() == 0 ) // trivial pattern
289 {
290 ASSERT( posA == 0 && posB == 1 );
291 subpattern = *this;
292 nb = 1;
293 startPos = Vector2I( NumberTraits<Integer>::ZERO,
294 NumberTraits<Integer>::ZERO );
295 different = false;
296 }
297 else if ( reversed ? slope().even() : slope().odd() )
298 { // Odd pattern: E(z_n) = E( z_{n-1} )^u E( z_{n-2} )
299 Self prevP = previousPattern();
300 Integer prevL = prevP.length();
301 Integer k1 = posA / prevL;
302 // Integer r1 = posA % prevL;
303 if ( posB > slope().u() * prevL )
304 { // B at extremity in the E( z_{n-2} ) part
305 nb = (int32_t)
306 ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
307 - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from A.
308 // subpattern is E( z_{n-1} )^nb E( z_{n-2} )
309 subpattern = Self( slope().father( nb ) );
310 nb = 1;
311 startPos = prevP.v() * k1;
312 different = k1 != 0;
313 }
314 else
315 { // B within some pattern E( z_{n-1} )
316 Integer k2 = ( posB + prevL - 1 ) / prevL;
317 nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
318 ASSERT( nb > 0 );
319 // subpattern is E( z_{n-1} )^nb
320 subpattern = prevP;
321 startPos = prevP.v() * k1;
322 different = true;
323 }
324 }
325 else // slope() is even
326 { // Even pattern: E(z_n) = E( z_{n-2} ) E( z_{n-1} )^u
327 Self prevP = previousPattern();
328 Integer prevL = prevP.length();
329 Integer k1 = ( l - posB ) / prevL;
330 // Integer r1 = ( l - posB ) % prevL;
331 if ( ( l - posA ) > slope().u() * prevL )
332 { // A at extremity in the E( z_{n-2} ) part
333 nb = (int32_t)
334 ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
335 - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from B.
336 // subpattern is E( z_{n-2} ) E( z_{n-1} )^nb
337 // slope().selfDisplay( std::cerr );
338 // std::cerr << " nb=" << nb << " ";
339 // slope().father( nb ).selfDisplay( std::cerr );
340 // std::cerr << std::endl;
341 subpattern = Self( slope().father( nb ) );
342 nb = 1;
343 startPos = Vector2I( NumberTraits<Integer>::ZERO,
344 NumberTraits<Integer>::ZERO );
345 different = k1 != 0;
346 }
347 else
348 { // A within some pattern E( z_{n-1} )
349 Integer k2 = ( l - posA + prevL - 1 ) / prevL;
350 nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
351 ASSERT( nb > 0 );
352 // subpattern is E( z_{n-1} )^nb
353 subpattern = prevP;
354 startPos = v() - prevP.v() * k2;
355 different = true;
356 }
357 }
358 return different;
359}
360
361//-----------------------------------------------------------------------------
362template <typename TFraction>
363inline
364bool
365DGtal::Pattern<TFraction>::
366getGreatestIncludedSubpattern( Pattern & subpattern,
367 Quotient & nb,
368 Vector2I & startPos,
369 Integer posA, Integer posB,
370 bool reversed ) const
371{
372 bool null_pattern = false;
373 Integer l = length();
374 ASSERT( ( 0 <= posA ) && ( posA < posB ) && ( posB <= l ) );
375 if ( slope().p() == 0 || slope().q() == 0 ) // trivial pattern
376 {
377 ASSERT( posA == 0 && posB == 1 );
378 subpattern = *this;
379 nb = 1;
380 startPos = Vector2I( NumberTraits<Integer>::ZERO,
381 NumberTraits<Integer>::ZERO );
382 null_pattern = false;
383 }
384 else if ( reversed ? slope().even() : slope().odd() )
385 { // Odd pattern: E(z_n) = E( z_{n-1} )^u E( z_{n-2} )
386 Self prevP = previousPattern();
387 Integer prevL = prevP.length();
388 Integer k1 = ( posA + prevL - 1 ) / prevL;
389 if ( posB == l )
390 { // B at right extremity of the E( z_{n-2} ) part
391 if ( posA > slope().u() * prevL )
392 {
393 subpattern = Fraction();
394 nb = 0;
395 null_pattern = true;
396 }
397 else
398 { // subpattern is E( z_{n-1} )^nb E( z_{n-2} )
399 nb = (int32_t)
400 ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
401 - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from A.
402 subpattern = Self( slope().father( nb ) );
403 nb = 1;
404 startPos = prevP.v() * k1;
405 null_pattern = false;
406 }
407 }
408 else
409 { // B within some pattern E( z_{n-1} ) or strictly in E ( z_{n-2} )
410 Integer k2 = posB / prevL;
411 nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
412 // subpattern is E( z_{n-1} )^nb or null
413 if ( nb < 0 ) nb = 0;
414 subpattern = nb == 0 ? Pattern() : prevP;
415 startPos = prevP.v() * k1;
416 null_pattern = nb == 0;
417 }
418 }
419 else // slope() is even
420 { // Even pattern: E(z_n) = E( z_{n-2} ) E( z_{n-1} )^u
421 Self prevP = previousPattern();
422 Integer prevL = prevP.length();
423 Integer k1 = ( l - posB + prevL - 1 ) / prevL;
424 if ( posA == 0 )
425 { // A at left extremity of the E( z_{n-2} ) part
426 // subpattern is E( z_{n-2} ) E( z_{n-1} )^nb
427 if ( ( l - posB ) > slope().u() * prevL )
428 {
429 subpattern = Fraction();
430 nb = 0;
431 null_pattern = true;
432 }
433 else
434 {
435 nb = (int32_t)
436 ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
437 - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from B.
438 subpattern = Self( slope().father( nb ) );
439 nb = 1;
440 startPos = Vector2I( NumberTraits<Integer>::ZERO,
441 NumberTraits<Integer>::ZERO );
442 null_pattern = false;
443 }
444 }
445 else
446 { // A within some pattern E( z_{n-1} ) or strictly in E ( z_{n-2} )
447 Integer k2 = ( l - posA ) / prevL;
448 nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
449 // subpattern is E( z_{n-1} )^nb or null
450 if ( nb < 0 ) nb = 0;
451 subpattern = nb == 0 ? Pattern() : prevP;
452 startPos = v() - prevP.v() * k2;
453 null_pattern = nb == 0;
454 }
455 }
456
457 return ! null_pattern;
458}
459
460
461
462///////////////////////////////////////////////////////////////////////////////
463// Interface - public :
464
465/**
466 * Writes/Displays the object on an output stream.
467 * @param out the output stream where the object is written.
468 */
469template <typename TFraction>
470inline
471void
472DGtal::Pattern<TFraction>::selfDisplay ( std::ostream & out ) const
473{
474 out << "[Pattern] f=";
475 mySlope.selfDisplay( out );
476}
477
478/**
479 * Checks the validity/consistency of the object.
480 * @return 'true' if the object is valid, 'false' otherwise.
481 */
482template <typename TFraction>
483inline
484bool
485DGtal::Pattern<TFraction>::isValid() const
486{
487 return true;
488}
489
490
491
492///////////////////////////////////////////////////////////////////////////////
493// Implementation of inline functions //
494
495template <typename TFraction>
496inline
497std::ostream&
498DGtal::operator<< ( std::ostream & out,
499 const Pattern<TFraction> & object )
500{
501 object.selfDisplay( out );
502 return out;
503}
504
505// //
506///////////////////////////////////////////////////////////////////////////////
507
508