DGtal  0.6.devel
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
Pattern.ih
1 
30 
31 #include <cstdlib>
33 
35 // IMPLEMENTATION of inline methods.
37 
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( 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  ASSERT( ( 0 <= posA ) && ( posA < posB ) && ( posB <= l ) );
291  if ( slope().p() == 0 || slope().q() == 0 ) // trivial pattern
292  {
293  ASSERT( posA == 0 && posB == 1 );
294  subpattern = *this;
295  nb = 1;
296  startPos = Vector2I( NumberTraits<Integer>::ZERO,
297  NumberTraits<Integer>::ZERO );
298  different = false;
299  }
300  else if ( reversed ? slope().even() : slope().odd() )
301  { // Odd pattern: E(z_n) = E( z_{n-1} )^u E( z_{n-2} )
302  Self prevP = previousPattern();
303  Integer prevL = prevP.length();
304  Integer k1 = posA / prevL;
305  // Integer r1 = posA % prevL;
306  if ( posB > slope().u() * prevL )
307  { // B at extremity in the E( z_{n-2} ) part
308  nb = (int32_t)
309  ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
310  - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from A.
311  // subpattern is E( z_{n-1} )^nb E( z_{n-2} )
312  subpattern = Self( slope().father( nb ) );
313  nb = 1;
314  startPos = prevP.v() * k1;
315  different = k1 != 0;
316  }
317  else
318  { // B within some pattern E( z_{n-1} )
319  Integer k2 = ( posB + prevL - 1 ) / prevL;
320  nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
321  ASSERT( nb > 0 );
322  // subpattern is E( z_{n-1} )^nb
323  subpattern = prevP;
324  startPos = prevP.v() * k1;
325  different = true;
326  }
327  }
328  else // slope() is even
329  { // Even pattern: E(z_n) = E( z_{n-2} ) E( z_{n-1} )^u
330  Self prevP = previousPattern();
331  Integer prevL = prevP.length();
332  Integer k1 = ( l - posB ) / prevL;
333  // Integer r1 = ( l - posB ) % prevL;
334  if ( ( l - posA ) > slope().u() * prevL )
335  { // A at extremity in the E( z_{n-2} ) part
336  nb = (int32_t)
337  ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
338  - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from B.
339  // subpattern is E( z_{n-2} ) E( z_{n-1} )^nb
340  // slope().selfDisplay( std::cerr );
341  // std::cerr << " nb=" << nb << " ";
342  // slope().father( nb ).selfDisplay( std::cerr );
343  // std::cerr << std::endl;
344  subpattern = Self( slope().father( nb ) );
345  nb = 1;
346  startPos = Vector2I( NumberTraits<Integer>::ZERO,
347  NumberTraits<Integer>::ZERO );
348  different = k1 != 0;
349  }
350  else
351  { // A within some pattern E( z_{n-1} )
352  Integer k2 = ( l - posA + prevL - 1 ) / prevL;
353  nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
354  ASSERT( nb > 0 );
355  // subpattern is E( z_{n-1} )^nb
356  subpattern = prevP;
357  startPos = v() - prevP.v() * k2;
358  different = true;
359  }
360  }
361  return different;
362 }
363 
364 //-----------------------------------------------------------------------------
365 template <typename TFraction>
366 inline
367 bool
368 DGtal::Pattern<TFraction>::
369 getGreatestIncludedSubpattern( Pattern & subpattern,
370  Quotient & nb,
371  Vector2I & startPos,
372  Integer posA, Integer posB,
373  bool reversed ) const
374 {
375  bool null_pattern = false;
376  Integer l = length();
377  ASSERT( ( 0 <= posA ) && ( posA < posB ) && ( posB <= l ) );
378  if ( slope().p() == 0 || slope().q() == 0 ) // trivial pattern
379  {
380  ASSERT( posA == 0 && posB == 1 );
381  subpattern = *this;
382  nb = 1;
383  startPos = Vector2I( NumberTraits<Integer>::ZERO,
384  NumberTraits<Integer>::ZERO );
385  null_pattern = false;
386  }
387  else if ( reversed ? slope().even() : slope().odd() )
388  { // Odd pattern: E(z_n) = E( z_{n-1} )^u E( z_{n-2} )
389  Self prevP = previousPattern();
390  Integer prevL = prevP.length();
391  Integer k1 = ( posA + prevL - 1 ) / prevL;
392  if ( posB == l )
393  { // B at right extremity of the E( z_{n-2} ) part
394  if ( posA > slope().u() * prevL )
395  {
396  subpattern = Fraction();
397  nb = 0;
398  null_pattern = true;
399  }
400  else
401  { // subpattern is E( z_{n-1} )^nb E( z_{n-2} )
402  nb = (int32_t)
403  ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
404  - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from A.
405  subpattern = Self( slope().father( nb ) );
406  nb = 1;
407  startPos = prevP.v() * k1;
408  null_pattern = false;
409  }
410  }
411  else
412  { // B within some pattern E( z_{n-1} ) or strictly in E ( z_{n-2} )
413  Integer k2 = posB / prevL;
414  nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
415  // subpattern is E( z_{n-1} )^nb or null
416  if ( nb < 0 ) nb = 0;
417  subpattern = nb == 0 ? Pattern() : prevP;
418  startPos = prevP.v() * k1;
419  null_pattern = nb == 0;
420  }
421  }
422  else // slope() is even
423  { // Even pattern: E(z_n) = E( z_{n-2} ) E( z_{n-1} )^u
424  Self prevP = previousPattern();
425  Integer prevL = prevP.length();
426  Integer k1 = ( l - posB + prevL - 1 ) / prevL;
427  if ( posA == 0 )
428  { // A at left extremity of the E( z_{n-2} ) part
429  // subpattern is E( z_{n-2} ) E( z_{n-1} )^nb
430  if ( ( l - posB ) > slope().u() * prevL )
431  {
432  subpattern = Fraction();
433  nb = 0;
434  null_pattern = true;
435  }
436  else
437  {
438  nb = (int32_t)
439  ( NumberTraits<Quotient>::castToInt64_t( slope().u() )
440  - NumberTraits<Integer>::castToInt64_t( k1 ) ); // number of E( z_{n-1} ) from B.
441  subpattern = Self( slope().father( nb ) );
442  nb = 1;
443  startPos = Vector2I( NumberTraits<Integer>::ZERO,
444  NumberTraits<Integer>::ZERO );
445  null_pattern = false;
446  }
447  }
448  else
449  { // A within some pattern E( z_{n-1} ) or strictly in E ( z_{n-2} )
450  Integer k2 = ( l - posA ) / prevL;
451  nb = (int32_t) NumberTraits<Integer>::castToInt64_t( k2 - k1 );
452  // subpattern is E( z_{n-1} )^nb or null
453  if ( nb < 0 ) nb = 0;
454  subpattern = nb == 0 ? Pattern() : prevP;
455  startPos = v() - prevP.v() * k2;
456  null_pattern = nb == 0;
457  }
458  }
459 
460  return ! null_pattern;
461 }
462 
463 
464 
466 // Interface - public :
467 
472 template <typename TFraction>
473 inline
474 void
475 DGtal::Pattern<TFraction>::selfDisplay ( std::ostream & out ) const
476 {
477  out << "[Pattern] f=";
478  mySlope.selfDisplay( out );
479 }
480 
485 template <typename TFraction>
486 inline
487 bool
488 DGtal::Pattern<TFraction>::isValid() const
489 {
490  return true;
491 }
492 
493 
494 
496 // Implementation of inline functions //
497 
498 template <typename TFraction>
499 inline
500 std::ostream&
501 DGtal::operator<< ( std::ostream & out,
502  const Pattern<TFraction> & object )
503 {
504  object.selfDisplay( out );
505  return out;
506 }
507 
508 // //
510 
511 
Generated on Wed Dec 19 2012 19:10:32 for DGtal by   doxygen 1.8.1.1