DGtal 1.3.0
Loading...
Searching...
No Matches
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// ------------------------------------------------------------------------
44template < typename TConstIterator, typename TInteger >
45inline
46DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::OneBalancedWordComputer()
47{ }
48
49
50// ------------------------------------------------------------------------
51template < typename TConstIterator, typename TInteger >
52inline
53DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::~OneBalancedWordComputer()
54{ }
55
56
57
58
59// ------------------------------------------------------------------------
60template < typename TConstIterator, typename TInteger >
61inline
62void
63DGtal::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// ------------------------------------------------------------------------
93template < typename TConstIterator, typename TInteger >
94inline
95void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::init(const ConstPointIterator & i)
96{
97 *this = *( i.getDSS() );
98}
99
100
101
102// ------------------------------------------------------------------------
103template < typename TConstIterator, typename TInteger >
104inline
105void DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::init(const FreemanChainCode & fc)
106{
107 init( fc.chain.begin(), fc.firstPoint(), FreemanChainCode::displacement );
108}
109
110
111
112// ------------------------------------------------------------------------
113template < typename TConstIterator, typename TInteger >
114inline
115void 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// ------------------------------------------------------------------------
123template < typename TConstIterator, typename TInteger >
124inline
125DGtal::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// ------------------------------------------------------------------------
144template < typename TConstIterator, typename TInteger >
145inline
146DGtal::OneBalancedWordComputer<TConstIterator,TInteger> &
147DGtal::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// ------------------------------------------------------------------------
168template < typename TConstIterator, typename TInteger >
169inline
170typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Self
171DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getSelf( ) const
172{
173 return OneBalancedWordComputer( );
174}
175
176// ------------------------------------------------------------------------
177template < typename TConstIterator, typename TInteger >
178inline
179bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::operator==( const Self & other ) const
180{
181 return ( ( begin() == other.begin() ) && ( end() == other.end() ) );
182}
183
184
185// ------------------------------------------------------------------------
186template < typename TConstIterator, typename TInteger >
187inline
188bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::operator!=( const Self & other ) const
189{
190 return !(*this == other);
191}
192
193
194// ------------------------------------------------------------------------
195template < typename TConstIterator, typename TInteger >
196inline
197typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Reverse
198DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getReverse() const
199{
200 return Reverse();
201}
202
203
204
205// ------------------------------------------------------------------------
206template < typename TConstIterator, typename TInteger >
207inline
208bool 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// ------------------------------------------------------------------------
273template < typename TConstIterator, typename TInteger >
274inline
275bool 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// ------------------------------------------------------------------------
365template < typename TConstIterator, typename TInteger >
366inline
367bool 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// ------------------------------------------------------------------------
450template < typename TConstIterator, typename TInteger >
451inline
452bool 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// ------------------------------------------------------------------------
530template < typename TConstIterator, typename TInteger >
531inline
532bool 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// ------------------------------------------------------------------------
558template < typename TConstIterator, typename TInteger >
559inline
560bool 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// ------------------------------------------------------------------------
584template < typename TConstIterator, typename TInteger >
585inline
586void 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// ------------------------------------------------------------------------
596template < typename TConstIterator, typename TInteger >
597inline
598void 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// ------------------------------------------------------------------------
607template < typename TConstIterator, typename TInteger >
608inline
609bool 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// ------------------------------------------------------------------------
627template < typename TConstIterator, typename TInteger >
628inline
629void
630DGtal::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// ------------------------------------------------------------------------
658template < typename TConstIterator, typename TInteger >
659inline
660typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
661DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getSmallLetter() const
662{
663 return getCode( myPatternBegin );
664}
665
666
667// ------------------------------------------------------------------------
668template < typename TConstIterator, typename TInteger >
669inline
670typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
671DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getBigLetter() const
672{
673 return getCode( myPatternEnd );
674}
675
676
677
678// ------------------------------------------------------------------------
679template < typename TConstIterator, typename TInteger >
680inline
681typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
682DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getCode(Index pos)
683{
684 return myCodeHandler.getCode( pos );
685}
686
687// ------------------------------------------------------------------------
688template < typename TConstIterator, typename TInteger >
689inline
690typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Code
691DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getCode(Index pos) const
692{
693 return myCodeHandler.getCode( pos );
694}
695
696
697
698// ------------------------------------------------------------------------
699template < typename TConstIterator, typename TInteger >
700inline
701typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
702DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::mainPatternLength() const
703{
704 return myPatternEnd - myPatternBegin + 1;
705}
706
707template < typename TConstIterator, typename TInteger >
708inline
709typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Vector
710DGtal::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// ------------------------------------------------------------------------
728template < typename TConstIterator, typename TInteger >
729inline
730typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
731DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::suffixLength() const
732{
733 return ( myPatternEnd - myNextBefore );
734}
735
736
737// ------------------------------------------------------------------------
738template < typename TConstIterator, typename TInteger >
739inline
740typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Size
741DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::prefixLength() const
742{
743 return ( myNextAfter - myPatternBegin );
744}
745
746// ------------------------------------------------------------------------
747template < typename TConstIterator, typename TInteger >
748inline
749bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::isUL ( Index pos ) const
750{
751 return ( (pos == myPatternBegin) || ( pos == myPatternEnd ) );
752}
753
754
755
756// ------------------------------------------------------------------------
757template < typename TConstIterator, typename TInteger >
758inline
759bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::nextIsLL ( Index pos ) const
760{
761 return ( (pos - myPatternBegin) == mainPatternLength() - myLeftPatternLength - 1) ;
762}
763
764// ------------------------------------------------------------------------
765template < typename TConstIterator, typename TInteger >
766inline
767bool DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::previousIsLL ( Index pos ) const
768{
769 return ( (pos - myPatternBegin) == mainPatternLength() - myLeftPatternLength ) ;
770}
771
772
773// ------------------------------------------------------------------------
774template < typename TConstIterator, typename TInteger >
775inline
776bool 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// ------------------------------------------------------------------------
784template < typename TConstIterator, typename TInteger >
785inline
786typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstIterator
787DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::begin() const
788{
789 return myBegin;
790}
791
792// ------------------------------------------------------------------------
793template < typename TConstIterator, typename TInteger >
794inline
795typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstIterator
796DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::end() const
797{
798 return myEnd;
799}
800
801
802// ------------------------------------------------------------------------
803template < typename TConstIterator, typename TInteger >
804inline
805typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstPointIterator
806DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::pointBegin() const
807{
808 return ConstPointIterator( this, myFirstLetter, myFirstPoint );
809}
810
811
812// ------------------------------------------------------------------------
813template < typename TConstIterator, typename TInteger >
814inline
815typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::ConstPointIterator
816DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::pointEnd() const
817{
818 ConstPointIterator it ( this, myLastLetter+1, myLastPoint );
819 return ++it;
820}
821
822
823
824
825// ------------------------------------------------------------------------
826template < typename TConstIterator, typename TInteger >
827inline
828typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
829DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getA() const
830{
831 return getArithmeticalDescription().a();
832}
833
834// ------------------------------------------------------------------------
835template < typename TConstIterator, typename TInteger >
836inline
837typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
838DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getB() const
839{
840 return getArithmeticalDescription().b();
841}
842
843
844// ------------------------------------------------------------------------
845template < typename TConstIterator, typename TInteger >
846inline
847typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
848DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getMu() const
849{
850 return getArithmeticalDescription().mu();
851}
852
853
854// ------------------------------------------------------------------------
855template < typename TConstIterator, typename TInteger >
856inline
857typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
858DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::getOmega() const
859{
860 return getArithmeticalDescription().omega();
861}
862
863
864// ------------------------------------------------------------------------
865template < typename TConstIterator, typename TInteger >
866inline
867typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::DSL
868DGtal::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// ------------------------------------------------------------------------
897template < typename TConstIterator, typename TInteger >
898inline
899void 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// ------------------------------------------------------------------------
930template < typename TConstIterator, typename TInteger >
931inline
932typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
933DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Uf() const
934{
935 Point uf, ul, lf, ll;
936 computeLeaningPoints( uf, ul, lf, ll );
937 return uf;
938}
939
940// ------------------------------------------------------------------------
941template < typename TConstIterator, typename TInteger >
942inline
943typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
944DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Ul() const
945{
946 Point uf, ul, lf, ll;
947 computeLeaningPoints( uf, ul, lf, ll );
948 return ul;
949}
950
951// ------------------------------------------------------------------------
952template < typename TConstIterator, typename TInteger >
953inline
954typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
955DGtal::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// ------------------------------------------------------------------------
964template < typename TConstIterator, typename TInteger >
965inline
966typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
967DGtal::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// ------------------------------------------------------------------------
976template < typename TConstIterator, typename TInteger >
977inline
978typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Vector
979DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::displacement( Code c ) const
980{
981 return this->myDisplacements( c );
982}
983
984
985// ------------------------------------------------------------------------
986template < typename TConstIterator, typename TInteger >
987inline
988typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Integer
989DGtal::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
999template < typename TConstIterator, typename TInteger >
1000inline
1001typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
1002DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::back() const
1003{
1004 return myFirstPoint;
1005}
1006
1007
1008// ------------------------------------------------------------------------
1009template < typename TConstIterator, typename TInteger >
1010inline
1011typename DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::Point
1012DGtal::OneBalancedWordComputer<TConstIterator,TInteger>::front() const
1013{
1014 return myLastPoint;
1015}
1016
1017
1018///////////////////////////////////////////////////////////////////////////////
1019// Implementation of inline functions //
1020
1021template < typename TConstIterator, typename TInteger >
1022inline
1023std::ostream&
1024DGtal::operator<< ( std::ostream & out,
1025 const OneBalancedWordComputer<TConstIterator, TInteger> & object )
1026{
1027 object.selfDisplay( out );
1028 return out;
1029}
1030
1031// //
1032///////////////////////////////////////////////////////////////////////////////
Generated on Sun Nov 27 2022 15:15:36 for DGtal by doxygen 1.9.5