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