DGtal  1.5.beta
OneBalancedWordComputer.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 OneBalancedWordComputer.ih
19  * @author Xavier Provençal (\c xavier.provencal@univ-savoie.fr )
20  * Laboratory of Mathematics (CNRS, UMR 5807), University of Savoie, France
21  *
22  * @date 2011/04/29
23  *
24  * Implementation of inline methods defined in OneBalancedWordComputer.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 
40 ///////////////////////////////////////////////////////////////////////////////
41 // ----------------------- Standard services ------------------------------
42 
43 // ------------------------------------------------------------------------
44 template < typename TConstIterator, typename TInteger >
45 inline
46 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::OneBalancedWordComputer()
47 { }
48 
49 
50 // ------------------------------------------------------------------------
51 template < typename TConstIterator, typename TInteger >
52 inline
53 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::~OneBalancedWordComputer()
54 { }
55 
56 
57 
58 
59 // ------------------------------------------------------------------------
60 template < typename TConstIterator, typename TInteger >
61 inline
62 void
63 DGtal::OneBalancedWordComputer<TConstIterator, TInteger>::init(
64  const ConstIterator & it,
65  const Point & start,
66  Vector (*displacements) (Code) )
67 {
68  myCodeHandler.init( it );
69  myFirstLetter = 0;
70 
71  myBegin = it;
72  myEnd = it;
73  ++myEnd;
74 
75  myLastLetter = 0;
76  myPatternBegin = 0;
77  myPatternEnd = 0;
78  myLeftPatternLength = 0;
79  myNextBefore =0;
80  myNextAfter = 0;
81  myNbRepeat = 1;
82 
83  myDisplacements = displacements;
84 
85  myFirstPoint = start;
86  myLastPoint = myFirstPoint + displacement( getCode( myFirstLetter) );
87 
88 }
89 
90 
91 
92 // ------------------------------------------------------------------------
93 template < typename TConstIterator, typename TInteger >
94 inline
95 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::init(const ConstPointIterator & i)
96 {
97  *this = *( i.getDSS() );
98 }
99 
100 
101 
102 // ------------------------------------------------------------------------
103 template < typename TConstIterator, typename TInteger >
104 inline
105 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::init(const FreemanChainCode & fc)
106 {
107  init( fc.chain.begin(), fc.firstPoint(), FreemanChainCode::displacement );
108 }
109 
110 
111 
112 // ------------------------------------------------------------------------
113 template < typename TConstIterator, typename TInteger >
114 inline
115 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::init(const typename FreemanChainCode::ConstIterator& it)
116 {
117  std::string::const_iterator string_it = it.getChain()->chain.begin();
118  string_it += it.position();
119  init( string_it, *it, FreemanChainCode::displacement );
120 }
121 
122 // ------------------------------------------------------------------------
123 template < typename TConstIterator, typename TInteger >
124 inline
125 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::OneBalancedWordComputer ( const Self & other ) :
126  myCodeHandler ( other.myCodeHandler ),
127  myBegin ( other.myBegin ),
128  myEnd ( other.myEnd ),
129  myFirstPoint ( other.myFirstPoint ),
130  myLastPoint ( other.myLastPoint ),
131  myFirstLetter ( other.myFirstLetter ),
132  myLastLetter ( other.myLastLetter ),
133  myNbRepeat ( other.myNbRepeat ),
134  myPatternBegin ( other.myPatternBegin ),
135  myPatternEnd ( other.myPatternEnd ),
136  myLeftPatternLength ( other.myLeftPatternLength ),
137  myNextBefore ( other.myNextBefore ),
138  myNextAfter ( other.myNextAfter ),
139  myDisplacements ( other.myDisplacements )
140 {}
141 
142 
143 // ------------------------------------------------------------------------
144 template < typename TConstIterator, typename TInteger >
145 inline
146 DGtal::OneBalancedWordComputer<TConstIterator,TInteger> &
147 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::operator= ( const Self & other )
148 {
149  myCodeHandler = other.myCodeHandler;
150  myBegin = other.myBegin;
151  myEnd = other.myEnd;
152  myFirstPoint = other.myFirstPoint;
153  myLastPoint = other.myLastPoint;
154  myFirstLetter = other.myFirstLetter;
155  myLastLetter = other.myLastLetter;
156  myNbRepeat = other.myNbRepeat;
157  myPatternBegin = other.myPatternBegin ;
158  myPatternEnd = other.myPatternEnd;
159  myLeftPatternLength = other.myLeftPatternLength;
160  myNextBefore = other.myNextBefore;
161  myNextAfter = other.myNextAfter;
162  myDisplacements = other.myDisplacements;
163  return *this;
164 }
165 
166 
167 // ------------------------------------------------------------------------
168 template < typename TConstIterator, typename TInteger >
169 inline
170 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Self
171 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getSelf( ) const
172 {
173  return OneBalancedWordComputer( );
174 }
175 
176 // ------------------------------------------------------------------------
177 template < typename TConstIterator, typename TInteger >
178 inline
179 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::operator==( const Self & other ) const
180 {
181  return ( ( begin() == other.begin() ) && ( end() == other.end() ) );
182 }
183 
184 
185 // ------------------------------------------------------------------------
186 template < typename TConstIterator, typename TInteger >
187 inline
188 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::operator!=( const Self & other ) const
189 {
190  return !(*this == other);
191 }
192 
193 
194 // ------------------------------------------------------------------------
195 template < typename TConstIterator, typename TInteger >
196 inline
197 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Reverse
198 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getReverse() const
199 {
200  return Reverse();
201 }
202 
203 
204 
205 // ------------------------------------------------------------------------
206 template < typename TConstIterator, typename TInteger >
207 inline
208 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::extendFront()
209 {
210  Code letterRead = getCode( myLastLetter + 1 );
211  Code letterExpected = getCode( myNextAfter );
212 
213  // Test if the new letter forms a longer prefix of the main pattern
214  // If the new letter is not what was expected, either the main pattern
215  // has to grow or either the DSS may not be extended.
216  if ( letterRead == letterExpected ) {
217  // Test if it is a complete repetition of the main pattern
218  if ( myNextAfter == myPatternEnd ) {
219  ++myNbRepeat;
220  myNextAfter = myPatternBegin;
221  } else {
222  ++myNextAfter;
223  }
224 
225  } else if ( isTrivial() ) {
226  myLeftPatternLength = 1;
227  myNbRepeat = 1;
228  myPatternEnd = myLastLetter + 1;
229  myNextBefore = myPatternEnd;
230 
231  } else if ( nextIsLL( myNextAfter ) && ( letterRead == getBigLetter() ) ) {
232  // The previous main pattern is now the left subpattern
233  myLeftPatternLength = mainPatternLength();
234  myNbRepeat = 1;
235  Size myOldSuffixLength = suffixLength();
236  myPatternEnd = myLastLetter + 1;
237  myNextBefore = myPatternEnd - myOldSuffixLength;
238  myNextAfter = myPatternBegin;
239 
240  } else if ( isUL( myNextAfter ) && ( letterRead == getSmallLetter() ) ) {
241  //In this case thw whole main pattern is modified! Not only complexified.
242  Size myOldLeftPatternLength = myLeftPatternLength;
243  Size myOldSuffixLength = suffixLength();
244  myNbRepeat = 1;
245  myLeftPatternLength = mainPatternLength();
246  myPatternEnd = myLastLetter + 1;
247 
248  // test if the suffix is long enough to contain the new first upper
249  // leaning point (beginning of the main pattern)
250  if ( myOldSuffixLength < myOldLeftPatternLength ) {
251  myPatternBegin = myPatternBegin + myLeftPatternLength
252  - myOldLeftPatternLength;
253  myNextBefore = myPatternEnd - myLeftPatternLength +
254  myOldLeftPatternLength - myOldSuffixLength;
255  } else {
256  //TODO : test this!
257  myPatternBegin = myPatternBegin - myOldLeftPatternLength;
258  myNextBefore = myPatternEnd - (myOldSuffixLength - myOldLeftPatternLength);
259  }
260  myNextAfter = myPatternBegin;
261 
262  } else {
263  return false;
264  }
265  ++myEnd;
266  ++myLastLetter;
267  myLastPoint += displacement( getCode( myLastLetter ) );
268  return true;
269 }
270 
271 
272 // ------------------------------------------------------------------------
273 template < typename TConstIterator, typename TInteger >
274 inline
275 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::extendBack()
276 {
277  Code letterRead = getCode( myFirstLetter - 1 );
278  Code letterExpected = getCode( myNextBefore );
279 
280  // Test if the new letter forms a longer suffix of the main pattern
281  // If the new letter is not what was expected, either the main pattern
282  // has to grow or either the DSS may not be extended.
283  if ( letterRead == letterExpected ) {
284  // Test if it forms a complete repetition of the main pattern
285  if ( myNextBefore == myPatternBegin ) {
286  //cout << "Case 1" << endl;
287  ++myNbRepeat;
288  // Move main pattern one iteration backward, nb 'myNextBefore' is
289  // already one iteration before.
290  Size mpl = mainPatternLength();
291  myPatternBegin -= mpl;
292  myPatternEnd -= mpl;
293  myNextAfter -= mpl;
294  myNextBefore = myPatternEnd;
295  } else {
296  --myNextBefore;
297  //cout << "Case 2" << endl;
298  }
299 
300 
301  } else if ( isTrivial() ) {
302  //cout << "Case 3" << endl;
303  myLeftPatternLength = myNbRepeat;
304  myPatternEnd += myNbRepeat-1;
305  myNbRepeat = 1;
306  myPatternBegin = myFirstLetter - 1;
307  myNextBefore = myPatternEnd;
308  myNextAfter = myPatternBegin;
309 
310  } else if ( previousIsLL( myNextBefore ) && ( letterRead == getSmallLetter() ) ) {
311  //cout << "Case 4" << endl;
312  // The previous main pattern is now the left subpattern
313  Size myOldMainPatternLength = mainPatternLength();
314  Size myOldLeftPatternLength = myLeftPatternLength;
315  //Size myOldRightPatternLength = myOldMainPatternLength - myOldLeftPatternLength;
316 
317  myPatternBegin = myFirstLetter - 1;
318  myPatternEnd += (myNbRepeat-1) * myOldMainPatternLength;
319  myLeftPatternLength = mainPatternLength() - myOldMainPatternLength;
320  myNbRepeat = 1;
321  myNextBefore = myPatternEnd;
322  myNextAfter -= myOldLeftPatternLength;
323 
324  } else if ( isUL( myNextBefore ) && ( letterRead == getBigLetter() ) ) {
325  //In this case the whole main pattern is modified! Not only complexified.
326  Size myOldMainPatternLength = mainPatternLength();
327  Size myOldRightPatternLength = myOldMainPatternLength - myLeftPatternLength;
328  Size myOldPrefixLength = prefixLength();
329 
330  myPatternBegin = myFirstLetter - 1;
331 
332  // test if the prefix is long enough to contain the new Last Upper
333  // Leaning point
334  if ( myOldPrefixLength < myOldRightPatternLength ) {
335  //cout << "Case 5" << endl;
336  myNextAfter = myNextAfter - myOldMainPatternLength + myLeftPatternLength;
337  myPatternEnd = myPatternEnd
338  + (myNbRepeat - 1)*myOldMainPatternLength
339  - myLeftPatternLength;
340 
341  } else {
342  //cout << "Case 6" << endl;
343  myNextAfter = myNextAfter - myOldMainPatternLength - myOldRightPatternLength;
344  myPatternEnd = myPatternEnd
345  + myNbRepeat*myOldMainPatternLength
346  - myLeftPatternLength;
347  }
348  myNbRepeat = 1;
349  myNextBefore = myPatternEnd;
350  myLeftPatternLength = mainPatternLength() - myOldMainPatternLength;
351 
352  } else {
353  //cout << "Case 7" << endl;
354  return false;
355  }
356  --myBegin;
357  --myFirstLetter;
358  myFirstPoint -= displacement( getCode( myFirstLetter ) );
359  return true;
360 }
361 
362 
363 
364 // ------------------------------------------------------------------------
365 template < typename TConstIterator, typename TInteger >
366 inline
367 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::retractBack()
368 {
369 
370  if ( myNextBefore != myPatternEnd ) {
371  //Normal case
372  //cout << "Case 1" << endl;
373  ++myNextBefore;
374 
375  } else if ( isTrivial() ) {
376  // In this case, it can be shorten only if there is more than one
377  // repetition.
378  //cout << "Case 2" << endl;
379  if ( myNbRepeat == 1 ) return false;
380  myPatternBegin = myPatternEnd = myNextBefore = ++myNextAfter;
381  --myNbRepeat;
382 
383  } else if ( myNbRepeat >= 2 ) {
384  // Got more than one repetition, it suffices to consider the next
385  // repetition of the main pattern with one less repetition.
386  //cout << "Case 3" << endl;
387  Size myOldMainPatternLength = mainPatternLength();
388  myPatternBegin += myOldMainPatternLength;
389  myPatternEnd += myOldMainPatternLength;
390  myNextAfter += myOldMainPatternLength;
391  myNextBefore = myPatternBegin;
392  --myNbRepeat;
393 
394  } else {
395  //Only one repetition, the slope is modified.
396  Size myOldMainPatternLength = mainPatternLength();
397  Size myOldLeftPatternLength = myLeftPatternLength;
398  Size myOldRightPatternLength = myOldMainPatternLength - myOldLeftPatternLength;
399 
400  if ( prefixLength() >= myOldRightPatternLength ) {
401  // A second Lower Leaning Point has been read in the prefix at
402  // the end of the main pattern. The slope is simply reversed.
403  //cout << "Case 4" << endl;
404  myLeftPatternLength = myOldRightPatternLength;
405  myPatternBegin += myOldRightPatternLength;
406  myPatternEnd += myOldRightPatternLength;
407  myNextBefore = myPatternEnd - myOldRightPatternLength + 1;
408 
409  } else if ( myOldLeftPatternLength < myOldRightPatternLength ) {
410  // Remove one repetition of the left Berstel pattern.
411  //cout << "Case 5" << endl;
412  myPatternBegin += myOldLeftPatternLength;
413  myNextBefore -= ( myOldLeftPatternLength - 1 );
414  myNextAfter += myOldLeftPatternLength;
415 
416  } else if ( myOldLeftPatternLength > myOldRightPatternLength ) {
417  // The complexity of the slope is modified.
418  //cout << "Case 6" << endl;
419  Size myNbBerstelRight = (myOldRightPatternLength > 1) ?
420  myOldMainPatternLength / myOldRightPatternLength :
421  myOldMainPatternLength - 1;
422  Size myBerstelLeftLength = myOldMainPatternLength -
423  ( myNbBerstelRight * myOldRightPatternLength );
424  // Right subpattern becomes the main pattern
425  myNbRepeat = myNbBerstelRight;
426  myPatternBegin += myBerstelLeftLength;
427  myPatternEnd = myPatternBegin + myOldRightPatternLength - 1;
428  myNextBefore = myPatternEnd - myBerstelLeftLength + 1;
429  myNextAfter += myBerstelLeftLength;
430  myLeftPatternLength = (myPatternBegin == myPatternEnd) ?
431  0 : myBerstelLeftLength;
432 
433  } else {
434  // Special case of slope 1/1 with no prefix read, only a trivial
435  // DSS remains.
436  //cout << "Case 7" << endl;
437  myNextBefore = myNextAfter = myPatternBegin = myPatternEnd;
438  myLeftPatternLength = 0;
439  }
440  }
441 
442  ++myBegin;
443  myFirstPoint += displacement( getCode( myFirstLetter ) );
444  ++myFirstLetter;
445  return true;
446 }
447 
448 
449 // ------------------------------------------------------------------------
450 template < typename TConstIterator, typename TInteger >
451 inline
452 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::retractFront()
453 {
454  if ( myNextAfter != myPatternBegin ) {
455  // Normal case
456  //cout << "Case 1" << endl;
457  --myNextAfter;
458 
459  } else if ( isTrivial() ) {
460  // In this case, it can be shorten only if there is more than one
461  // repetition.
462  //cout << "Case 2" << endl;
463  if ( myNbRepeat == 1 ) return false;
464  --myNbRepeat;
465 
466  } else if ( myNbRepeat >= 2 ) {
467  // Got more than one repetition, it suffices to consider the next
468  // repetition of the main pattern with one less repetition.
469  //cout << "Case 3" << endl;
470  --myNbRepeat;
471  myNextAfter = myPatternEnd;
472 
473  } else {
474  //Only one repetition, the slope is modified.
475  Size myOldMainPatternLength = mainPatternLength();
476  Size myOldLeftPatternLength = myLeftPatternLength;
477  Size myOldRightPatternLength = myOldMainPatternLength -
478  myOldLeftPatternLength;
479 
480  if ( suffixLength() >= myOldLeftPatternLength ) {
481  // A second Lower Leaning Point has been read in the suffix at
482  // the front of the main pattern. The slope is simply reversed.
483  //cout << "Case 4" << endl;
484  myLeftPatternLength = myOldRightPatternLength;
485  myPatternBegin -= myOldLeftPatternLength;
486  myPatternEnd -= myOldLeftPatternLength;
487  myNextAfter = myPatternBegin + myOldLeftPatternLength - 1;
488 
489  } else if ( myOldLeftPatternLength > myOldRightPatternLength ) {
490  // Remove one repetition of the right Berstel pattern.
491  //cout << "Case 5" << endl;
492  myPatternEnd -= myOldRightPatternLength;
493  myNextAfter += ( myOldRightPatternLength - 1 );
494  myNextBefore -= myOldRightPatternLength;
495  myLeftPatternLength -= myOldRightPatternLength;
496 
497  } else if ( myOldLeftPatternLength < myOldRightPatternLength ) {
498  // The complexity of the slope is modified.
499  //cout << "Case 6" << endl;
500  Size myNbBerstelLeft = (myOldLeftPatternLength > 1) ?
501  myOldMainPatternLength / myOldLeftPatternLength :
502  myOldMainPatternLength - 1;
503  Size myBerstelRightLength = myOldMainPatternLength -
504  ( myNbBerstelLeft * myOldLeftPatternLength );
505  Size myOldSuffixLength = suffixLength();
506 
507  // Left subpattern becomes the main pattern.
508  myNbRepeat = myNbBerstelLeft;
509  myLeftPatternLength = myOldLeftPatternLength - myBerstelRightLength;
510  myPatternEnd = myPatternBegin + myOldLeftPatternLength - 1;
511  myNextBefore = myPatternEnd - myOldSuffixLength;
512  myNextAfter = myPatternBegin + myBerstelRightLength - 1;
513 
514  } else {
515  // Special case of slope 1/1 with no prefix read, only a trivial
516  // DSS remains.
517  //cout << "Case 7" << endl;
518  myNextBefore = myNextAfter = myPatternEnd = myPatternBegin;
519  myLeftPatternLength = 0;
520  }
521  }
522  --myEnd;
523  myLastPoint -= displacement( getCode( myLastLetter ) );
524  --myLastLetter;
525  return true;
526 }
527 
528 
529 // ------------------------------------------------------------------------
530 template < typename TConstIterator, typename TInteger >
531 inline
532 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isExtendableFront()
533 {
534  Code letterRead = getCode( myLastLetter + 1 );
535  Code letterExpected = getCode( myNextAfter );
536  if ( letterRead == letterExpected )
537  {
538  return true;
539  }
540  else if ( isTrivial() )
541  {
542  return true;
543  }
544  else if ( nextIsLL( myNextAfter ) && ( letterRead == getBigLetter() ) )
545  {
546  return true;
547  }
548  else if ( isUL( myNextAfter ) && ( letterRead == getSmallLetter() ) )
549  {
550  return true;
551  }
552  return false;
553 }
554 
555 
556 
557 // ------------------------------------------------------------------------
558 template < typename TConstIterator, typename TInteger >
559 inline
560 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isExtendableBack()
561 {
562  Code letterRead = getCode( myFirstLetter - 1);
563  Code letterExpected = getCode( myNextBefore );
564  if ( letterRead == letterExpected )
565  {
566  return true;
567  }
568  else if ( isTrivial() )
569  {
570  return true;
571  }
572  else if ( previousIsLL( myNextBefore ) && ( letterRead == getSmallLetter() ) )
573  {
574  return true;
575  }
576  else if ( isUL( myNextBefore ) && ( letterRead == getBigLetter() ) )
577  {
578  return true;
579  }
580  return false;
581 }
582 
583 // ------------------------------------------------------------------------
584 template < typename TConstIterator, typename TInteger >
585 inline
586 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::setPosition(
587  const typename DGtal::OneBalancedWordComputer<TConstIterator, TInteger>::Point & p )
588 {
589  Vector v = myLastPoint - myFirstPoint;
590  myFirstPoint = p;
591  myLastPoint = p+v;
592 }
593 
594 
595 // ------------------------------------------------------------------------
596 template < typename TConstIterator, typename TInteger >
597 inline
598 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::translate(
599  const typename DGtal::OneBalancedWordComputer<TConstIterator, TInteger>::Vector & v )
600 {
601  myFirstPoint += v;
602  myLastPoint += v;
603 }
604 
605 
606 // ------------------------------------------------------------------------
607 template < typename TConstIterator, typename TInteger >
608 inline
609 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isValid() const
610 {
611  return (
612  ( myFirstLetter <= myPatternBegin ) &&
613  ( myPatternBegin <= myPatternEnd ) &&
614  ( myPatternEnd <= myLastLetter ) &&
615  ( myNextBefore >= myPatternBegin ) &&
616  ( myNextBefore <= myPatternEnd ) &&
617  ( myNextAfter >= myPatternBegin ) &&
618  ( myNextAfter <= myPatternEnd ) &&
619  ( (myLeftPatternLength == 0 ) ||
620  (myLeftPatternLength < mainPatternLength() ) ) );
621 }
622 
623 ///////////////////////////////////////////////////////////////////////////////
624 // Interface - public :
625 
626 // ------------------------------------------------------------------------
627 template < typename TConstIterator, typename TInteger >
628 inline
629 void
630 DGtal::OneBalancedWordComputer<TConstIterator, TInteger >::selfDisplay ( std::ostream & out ) const
631 {
632  std::string s;
633  for (int i=myFirstLetter; i<= myLastLetter; i++)
634  s += getCode( i );
635  s += ".";
636  for (int i=myLastLetter+1; i<myLastLetter+4 ; i++)
637  s += getCode( i );
638  out << "[OneBalancedWordComputer]\n";
639  out << "myCodes = " << s << "\n";
640  out << "myFirstPoint = " << myFirstPoint << "\n";
641  out << "myLastPoint = " << myLastPoint << "\n";
642  out << "myFirstLetter = " << myFirstLetter << "\n";
643  out << "myLastLetter = " << myLastLetter << "\n";
644  out << "myNbRepeat = " << myNbRepeat << "\n";
645  out << "myPatternBegin = " << myPatternBegin << "\n";
646  out << "myPatternEnd = " << myPatternEnd << "\n";
647  out << "myLeftPatternLength = " << myLeftPatternLength << "\n";
648  out << "myNextBefore = " << myNextBefore << "\n";
649  out << "myNextAfter = " << myNextAfter << "\n";
650  DSL d = getArithmeticalDescription();
651  out << "(a,b,mu,omega) = (" << d.a() << ", " << d.b() << ", "
652  << d.mu() << ", " << d.omega() << ")\n";
653  out << "[End OneBalancedWordComputer]" << std::endl;
654 }
655 
656 
657 // ------------------------------------------------------------------------
658 template < typename TConstIterator, typename TInteger >
659 inline
660 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
661 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getSmallLetter() const
662 {
663  return getCode( myPatternBegin );
664 }
665 
666 
667 // ------------------------------------------------------------------------
668 template < typename TConstIterator, typename TInteger >
669 inline
670 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
671 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getBigLetter() const
672 {
673  return getCode( myPatternEnd );
674 }
675 
676 
677 
678 // ------------------------------------------------------------------------
679 template < typename TConstIterator, typename TInteger >
680 inline
681 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
682 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getCode(Index pos)
683 {
684  return myCodeHandler.getCode( pos );
685 }
686 
687 // ------------------------------------------------------------------------
688 template < typename TConstIterator, typename TInteger >
689 inline
690 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
691 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getCode(Index pos) const
692 {
693  return myCodeHandler.getCode( pos );
694 }
695 
696 
697 
698 // ------------------------------------------------------------------------
699 template < typename TConstIterator, typename TInteger >
700 inline
701 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
702 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::mainPatternLength() const
703 {
704  return myPatternEnd - myPatternBegin + 1;
705 }
706 
707 template < typename TConstIterator, typename TInteger >
708 inline
709 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Vector
710 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::mainPatternVector() const
711 {
712  ConstPointIterator it = pointBegin();
713  while ( ! isUL ( it.getIndex() ) )
714  ++it;
715  Point p_uf = *it;
716  ++it; /* At least one letter in the pattern */
717  if ( ! isTrivial() )
718  {
719  while ( ! isUL ( it.getIndex() ) )
720  ++it;
721  ++it;
722  }
723  return *it - p_uf;
724 }
725 
726 
727 // ------------------------------------------------------------------------
728 template < typename TConstIterator, typename TInteger >
729 inline
730 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
731 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::suffixLength() const
732 {
733  return ( myPatternEnd - myNextBefore );
734 }
735 
736 
737 // ------------------------------------------------------------------------
738 template < typename TConstIterator, typename TInteger >
739 inline
740 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
741 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::prefixLength() const
742 {
743  return ( myNextAfter - myPatternBegin );
744 }
745 
746 // ------------------------------------------------------------------------
747 template < typename TConstIterator, typename TInteger >
748 inline
749 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isUL ( Index pos ) const
750 {
751  return ( (pos == myPatternBegin) || ( pos == myPatternEnd ) );
752 }
753 
754 
755 
756 // ------------------------------------------------------------------------
757 template < typename TConstIterator, typename TInteger >
758 inline
759 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::nextIsLL ( Index pos ) const
760 {
761  return ( (pos - myPatternBegin) == mainPatternLength() - myLeftPatternLength - 1) ;
762 }
763 
764 // ------------------------------------------------------------------------
765 template < typename TConstIterator, typename TInteger >
766 inline
767 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::previousIsLL ( Index pos ) const
768 {
769  return ( (pos - myPatternBegin) == mainPatternLength() - myLeftPatternLength ) ;
770 }
771 
772 
773 // ------------------------------------------------------------------------
774 template < typename TConstIterator, typename TInteger >
775 inline
776 bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isTrivial() const
777 {
778  // If there is no left subpattern, then the DSS is trivial.
779  return ( myLeftPatternLength == 0 );
780 }
781 
782 
783 // ------------------------------------------------------------------------
784 template < typename TConstIterator, typename TInteger >
785 inline
786 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstIterator
787 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::begin() const
788 {
789  return myBegin;
790 }
791 
792 // ------------------------------------------------------------------------
793 template < typename TConstIterator, typename TInteger >
794 inline
795 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstIterator
796 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::end() const
797 {
798  return myEnd;
799 }
800 
801 
802 // ------------------------------------------------------------------------
803 template < typename TConstIterator, typename TInteger >
804 inline
805 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstPointIterator
806 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::pointBegin() const
807 {
808  return ConstPointIterator( this, myFirstLetter, myFirstPoint );
809 }
810 
811 
812 // ------------------------------------------------------------------------
813 template < typename TConstIterator, typename TInteger >
814 inline
815 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstPointIterator
816 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::pointEnd() const
817 {
818  ConstPointIterator it ( this, myLastLetter+1, myLastPoint );
819  return ++it;
820 }
821 
822 
823 
824 
825 // ------------------------------------------------------------------------
826 template < typename TConstIterator, typename TInteger >
827 inline
828 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
829 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getA() const
830 {
831  return getArithmeticalDescription().a();
832 }
833 
834 // ------------------------------------------------------------------------
835 template < typename TConstIterator, typename TInteger >
836 inline
837 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
838 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getB() const
839 {
840  return getArithmeticalDescription().b();
841 }
842 
843 
844 // ------------------------------------------------------------------------
845 template < typename TConstIterator, typename TInteger >
846 inline
847 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
848 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getMu() const
849 {
850  return getArithmeticalDescription().mu();
851 }
852 
853 
854 // ------------------------------------------------------------------------
855 template < typename TConstIterator, typename TInteger >
856 inline
857 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
858 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getOmega() const
859 {
860  return getArithmeticalDescription().omega();
861 }
862 
863 
864 // ------------------------------------------------------------------------
865 template < typename TConstIterator, typename TInteger >
866 inline
867 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::DSL
868 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getArithmeticalDescription() const
869 {
870  DGtal::IntegerComputer<TInteger> ic;
871 
872  ConstPointIterator itBegin = pointBegin();
873  while ( itBegin.getIndex() != myPatternBegin )
874  itBegin++;
875  ConstPointIterator itEnd = pointEnd();
876  while ( itEnd.getIndex() != myPatternEnd+1 )
877  itEnd--;
878  ConstPointIterator it;
879  Size myRightPatternLenght = mainPatternLength() - myLeftPatternLength;
880  it = itBegin;
881  for (int i=0; i<myRightPatternLenght; i++)
882  it++;
883  Point pb = *itBegin;
884  Point pe = *itEnd;
885  Point po = *it;
886  Vector v = pe - pb;
887 
888  Integer r1 = v[1]*pb[0] - v[0]*pb[1];
889  Integer r2 = v[1]*po[0] - v[0]*po[1];
890  Integer bound = ic.min (r1, r2);
891 
892  return DSL(v[1], v[0], bound);
893 }
894 
895 
896 // ------------------------------------------------------------------------
897 template < typename TConstIterator, typename TInteger >
898 inline
899 void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::computeLeaningPoints(
900  Point & uf, Point & ul,
901  Point & lf, Point & ll ) const
902 {
903  ConstPointIterator it = pointBegin();
904  while ( ! isUL ( it.getIndex() ) )
905  ++it;
906  uf = *it;
907 
908  Vector v = mainPatternVector();
909  ul = uf + v*static_cast<Integer>(myNbRepeat);
910 
911  while ( ! previousIsLL ( it.getIndex() ) )
912  ++it;
913  lf = ( suffixLength() >= myLeftPatternLength ) ? *it - mainPatternVector() : *it;
914 
915  int nbLowerRepeats = ( prefixLength() >= mainPatternLength() - myLeftPatternLength )
916  ? myNbRepeat : myNbRepeat - 1;
917  ll = *it + v*nbLowerRepeats;
918 
919  if ( remainder( uf ) > remainder( lf ) )
920  {
921  swap ( uf, lf );
922  swap ( ul, ll );
923  }
924 }
925 
926 
927 
928 
929 // ------------------------------------------------------------------------
930 template < typename TConstIterator, typename TInteger >
931 inline
932 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
933 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Uf() const
934 {
935  Point uf, ul, lf, ll;
936  computeLeaningPoints( uf, ul, lf, ll );
937  return uf;
938 }
939 
940 // ------------------------------------------------------------------------
941 template < typename TConstIterator, typename TInteger >
942 inline
943 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
944 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Ul() const
945 {
946  Point uf, ul, lf, ll;
947  computeLeaningPoints( uf, ul, lf, ll );
948  return ul;
949 }
950 
951 // ------------------------------------------------------------------------
952 template < typename TConstIterator, typename TInteger >
953 inline
954 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
955 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Lf() const
956 {
957  Point uf, ul, lf, ll;
958  computeLeaningPoints( uf, ul, lf, ll );
959  return lf;
960 }
961 
962 
963 // ------------------------------------------------------------------------
964 template < typename TConstIterator, typename TInteger >
965 inline
966 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
967 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Ll() const
968 {
969  Point uf, ul, lf, ll;
970  computeLeaningPoints( uf, ul, lf, ll );
971  return ll;
972 }
973 
974 
975 // ------------------------------------------------------------------------
976 template < typename TConstIterator, typename TInteger >
977 inline
978 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Vector
979 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::displacement( Code c ) const
980 {
981  return this->myDisplacements( c );
982 }
983 
984 
985 // ------------------------------------------------------------------------
986 template < typename TConstIterator, typename TInteger >
987 inline
988 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
989 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::remainder(const Point & aPoint) const
990 {
991  DSL d = getArithmeticalDescription();
992  return (d.a()*aPoint[0] - d.b()*aPoint[1]);
993 }
994 
995 
996 // ----------------------- Accessors --------------------------------------
997 
998 
999 template < typename TConstIterator, typename TInteger >
1000 inline
1001 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
1002 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::back() const
1003 {
1004  return myFirstPoint;
1005 }
1006 
1007 
1008 // ------------------------------------------------------------------------
1009 template < typename TConstIterator, typename TInteger >
1010 inline
1011 typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
1012 DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::front() const
1013 {
1014  return myLastPoint;
1015 }
1016 
1017 
1018 ///////////////////////////////////////////////////////////////////////////////
1019 // Implementation of inline functions //
1020 
1021 template < typename TConstIterator, typename TInteger >
1022 inline
1023 std::ostream&
1024 DGtal::operator<< ( std::ostream & out,
1025  const OneBalancedWordComputer<TConstIterator, TInteger> & object )
1026 {
1027  object.selfDisplay( out );
1028  return out;
1029 }
1030 
1031 // //
1032 ///////////////////////////////////////////////////////////////////////////////