DGtal  1.5.beta
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( 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 //-----------------------------------------------------------------------------
117 template <typename TFraction>
118 inline
119 std::string
120 DGtal::Pattern<TFraction>::
121 rEs( 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 //-----------------------------------------------------------------------------
158 template <typename TFraction>
159 inline
160 typename DGtal::Pattern<TFraction>::Fraction
161 DGtal::Pattern<TFraction>::
162 slope() const
163 {
164  return mySlope;
165 }
166 //-----------------------------------------------------------------------------
167 template <typename TFraction>
168 inline
169 typename DGtal::Pattern<TFraction>::Integer
170 DGtal::Pattern<TFraction>::
171 length() const
172 {
173  return mySlope.p() + mySlope.q();
174 }
175 //-----------------------------------------------------------------------------
176 template <typename TFraction>
177 inline
178 typename DGtal::Pattern<TFraction>::Integer
179 DGtal::Pattern<TFraction>::
180 posU( 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 //-----------------------------------------------------------------------------
188 template <typename TFraction>
189 inline
190 typename DGtal::Pattern<TFraction>::Integer
191 DGtal::Pattern<TFraction>::
192 posL( 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 //-----------------------------------------------------------------------------
202 template <typename TFraction>
203 inline
204 typename DGtal::Pattern<TFraction>::Point2I
205 DGtal::Pattern<TFraction>::
206 U( 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 //-----------------------------------------------------------------------------
220 template <typename TFraction>
221 inline
222 typename DGtal::Pattern<TFraction>::Point2I
223 DGtal::Pattern<TFraction>::
224 L( 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 //-----------------------------------------------------------------------------
236 template <typename TFraction>
237 inline
238 typename DGtal::Pattern<TFraction>::Vector2I
239 DGtal::Pattern<TFraction>::
240 bezout() const
241 {
242  return slope().odd()
243  ? U( 1 ) - previousPattern().U( 1 )
244  : previousPattern().U( 1 );
245 }
246 //-----------------------------------------------------------------------------
247 template <typename TFraction>
248 inline
249 typename DGtal::Pattern<TFraction>::Vector2I
250 DGtal::Pattern<TFraction>::
251 v() const
252 {
253  return Vector2I( slope().q(), slope().p() );
254 }
255 //-----------------------------------------------------------------------------
256 template <typename TFraction>
257 inline
258 DGtal::Pattern<TFraction>
259 DGtal::Pattern<TFraction>::
260 previousPattern() 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 //-----------------------------------------------------------------------------
274 template <typename TFraction>
275 inline
276 bool
277 DGtal::Pattern<TFraction>::
278 getSmallestCoveringSubpattern( 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 //-----------------------------------------------------------------------------
362 template <typename TFraction>
363 inline
364 bool
365 DGtal::Pattern<TFraction>::
366 getGreatestIncludedSubpattern( 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  */
469 template <typename TFraction>
470 inline
471 void
472 DGtal::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  */
482 template <typename TFraction>
483 inline
484 bool
485 DGtal::Pattern<TFraction>::isValid() const
486 {
487  return true;
488 }
489 
490 
491 
492 ///////////////////////////////////////////////////////////////////////////////
493 // Implementation of inline functions //
494 
495 template <typename TFraction>
496 inline
497 std::ostream&
498 DGtal::operator<< ( std::ostream & out,
499  const Pattern<TFraction> & object )
500 {
501  object.selfDisplay( out );
502  return out;
503 }
504 
505 // //
506 ///////////////////////////////////////////////////////////////////////////////
507 
508