1 // ==========================================================================
2 //                 SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin
5 // All rights reserved.
6 //
7 // Redistribution and use in source and binary forms, with or without
8 // modification, are permitted provided that the following conditions are met:
9 //
10 //     * Redistributions of source code must retain the above copyright
11 //       notice, this list of conditions and the following disclaimer.
12 //     * Redistributions in binary form must reproduce the above copyright
13 //       notice, this list of conditions and the following disclaimer in the
14 //       documentation and/or other materials provided with the distribution.
15 //     * Neither the name of Knut Reinert or the FU Berlin nor the names of
16 //       its contributors may be used to endorse or promote products derived
17 //       from this software without specific prior written permission.
18 //
19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE
23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH
29 // DAMAGE.
30 //
31 // ==========================================================================
32 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
33 // ==========================================================================
34 // Code for the Journaled string iterator.
35 // ==========================================================================
36 
37 #ifndef SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_ITERATOR_H_
38 #define SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_ITERATOR_H_
39 
40 namespace seqan {
41 
42 // ============================================================================
43 // Tags, Classes
44 // ============================================================================
45 
46 struct CommonSegmentIterator_;
47 typedef Tag<CommonSegmentIterator_> CommonSegmentIterator;
48 
49 template <typename TJournaledStringSpec>
50 struct JournaledStringIterSpec;
51 
52 template <typename TJournaledString, typename TJournalSpec>
53 class Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >
54 {
55 public:
56     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
57     typedef typename JournalType<TJournaledString>::Type TJournalEntries;
58     // We need a rooted iterator for iterating the journal tree since we need atEnd().
59     typedef typename Iterator<TJournalEntries, Standard>::Type TJournalEntriesIterator;
60     typedef typename Host<TJournaledString>::Type THost;
61     typedef typename Iterator<THost, Standard>::Type THostIterator;
62     typedef typename InsertionBuffer<TJournaledString>::Type TInsertionBuffer;
63     typedef typename Iterator<TInsertionBuffer, Standard>::Type TInsertionBufferIterator;
64 
65     // The journal string we iterate over.
66     TJournaledString * _journalStringPtr;
67     // Iterator over the segments in the journal tree.
68     TJournalEntriesIterator _journalEntriesIterator;
69     // Begin and end iterator in the host string of the journal string.
70     THostIterator _hostSegmentBegin;
71     THostIterator _hostSegmentEnd;
72     // Current iterator in the host segment.
73     THostIterator _currentHostIt;
74     // Begin and end iterator in the insertion buffer of the journal string.
75     TInsertionBufferIterator _insertionBufferSegmentBegin;
76     TInsertionBufferIterator _insertionBufferSegmentEnd;
77     // Current iterator in the insertion buffer.
78     TInsertionBufferIterator _currentInsertionBufferIt;
79 
Iter()80     Iter() :
81         _journalStringPtr(), _journalEntriesIterator(), _hostSegmentBegin(), _hostSegmentEnd(),
82         _currentHostIt(), _insertionBufferSegmentBegin(), _insertionBufferSegmentEnd(),
83         _currentInsertionBufferIt()
84     {}
85 
Iter(TIterator const & other)86     Iter(TIterator const & other)
87             : _journalStringPtr(other._journalStringPtr),
88               _journalEntriesIterator(other._journalEntriesIterator),
89               _hostSegmentBegin(other._hostSegmentBegin),
90               _hostSegmentEnd(other._hostSegmentEnd),
91               _currentHostIt(other._currentHostIt),
92               _insertionBufferSegmentBegin(other._insertionBufferSegmentBegin),
93               _insertionBufferSegmentEnd(other._insertionBufferSegmentEnd),
94               _currentInsertionBufferIt(other._currentInsertionBufferIt)
95     {
96     }
97 
Iter(typename IterComplementConst<TIterator>::Type const & other)98     Iter(typename IterComplementConst<TIterator>::Type const & other)
99             : _journalStringPtr(other._journalStringPtr),
100               _journalEntriesIterator(other._journalEntriesIterator),
101               _hostSegmentBegin(other._hostSegmentBegin),
102               _hostSegmentEnd(other._hostSegmentEnd),
103               _currentHostIt(other._currentHostIt),
104               _insertionBufferSegmentBegin(other._insertionBufferSegmentBegin),
105               _insertionBufferSegmentEnd(other._insertionBufferSegmentEnd),
106               _currentInsertionBufferIt(other._currentInsertionBufferIt)
107     {
108     }
109 
110     // TODO(holtgrew): Commented out because of weird ambiguities with other constructor.
111     // explicit
112     // Iter(TJournaledString & journalString)
113     // {
114     //     _initJournaledStringIterator(*this, journalString);
115     // }
116 
117     Iter & operator=(TIterator const & other)
118     {
119         if (this != &other)
120         {
121             _journalStringPtr = other._journalStringPtr;
122             _journalEntriesIterator = other._journalEntriesIterator;
123             _hostSegmentBegin = other._hostSegmentBegin;
124             _hostSegmentEnd = other._hostSegmentEnd;
125             _currentHostIt = other._currentHostIt;
126             _insertionBufferSegmentBegin = other._insertionBufferSegmentBegin;
127             _insertionBufferSegmentEnd = other._insertionBufferSegmentEnd;
128             _currentInsertionBufferIt = other._currentInsertionBufferIt;
129         }
130         return *this;
131     }
132 
133     Iter & operator=(typename IterComplementConst<TIterator>::Type const & other)
134     {
135         if (this != &other)
136         {
137             _journalStringPtr = other._journalStringPtr;
138             _journalEntriesIterator = other._journalEntriesIterator;
139             _hostSegmentBegin = other._hostSegmentBegin;
140             _hostSegmentEnd = other._hostSegmentEnd;
141             _currentHostIt = other._currentHostIt;
142             _insertionBufferSegmentBegin = other._insertionBufferSegmentBegin;
143             _insertionBufferSegmentEnd = other._insertionBufferSegmentEnd;
144             _currentInsertionBufferIt = other._currentInsertionBufferIt;
145         }
146         return *this;
147     }
148 };
149 
150 // Implement concept
151 template <typename TJournaledString, typename TJournalSpec>
152 SEQAN_CONCEPT_IMPL((Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const), (RootedRandomAccessIteratorConcept));
153 
154 template <typename TJournaledString, typename TJournalSpec>
155 SEQAN_CONCEPT_IMPL((Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >), (MutableRootedRandomAccessIteratorConcept));
156 
157 // ============================================================================
158 // Metafunctions
159 // ============================================================================
160 
161 // For String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >
162 
163 // ----------------------------------------------------------------------------
164 // Metafunction Iterator                                             [Standard]
165 // ----------------------------------------------------------------------------
166 
167 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
168 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Standard>
169 {
170     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, JournaledStringIterSpec<TJournalSpec> > Type;
171 };
172 
173 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
174 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Standard>
175 {
176     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, JournaledStringIterSpec<TJournalSpec> > Type;
177 };
178 
179 // ----------------------------------------------------------------------------
180 // Metafunction Iterator                      [Standard, CommonSegmentIterator]
181 // ----------------------------------------------------------------------------
182 
183 template <typename TValue, typename THostSpec, typename TJournalSpec>
184 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> >, Standard>
185 {
186     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> >, JournaledStringIterSpec<CommonSegmentIterator> > Type;
187 };
188 
189 template <typename TValue, typename THostSpec, typename TJournalSpec>
190 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> > const, Standard>
191 {
192     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> > const, JournaledStringIterSpec<CommonSegmentIterator> > Type;
193 };
194 
195 // ----------------------------------------------------------------------------
196 // Metafunction Iterator                                               [Rooted]
197 // ----------------------------------------------------------------------------
198 
199 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
200 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Rooted>
201 {
202     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, JournaledStringIterSpec<TJournalSpec> > Type;
203 };
204 
205 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
206 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Rooted>
207 {
208     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, JournaledStringIterSpec<TJournalSpec> > Type;
209 };
210 
211 // ----------------------------------------------------------------------------
212 // Metafunction Iterator                        [Rooted, CommonSegmentIterator]
213 // ----------------------------------------------------------------------------
214 
215 template <typename TValue, typename THostSpec, typename TJournalSpec>
216 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> >, Rooted>
217 {
218     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> >, JournaledStringIterSpec<CommonSegmentIterator> > Type;
219 };
220 
221 template <typename TValue, typename THostSpec, typename TJournalSpec>
222 struct Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> > const, Rooted>
223 {
224     typedef Iter<String<TValue, Journaled<THostSpec, TJournalSpec, THostSpec> > const, JournaledStringIterSpec<CommonSegmentIterator> > Type;
225 };
226 
227 // ----------------------------------------------------------------------------
228 // Metafunction Value
229 // ----------------------------------------------------------------------------
230 
231 template <typename TJournaledString, typename TJournaledStringIterSpec>
232 struct Value<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > >
233 {
234     typedef typename GetValue<TJournaledString>::Type Type;
235 };
236 
237 template <typename TJournaledString, typename TJournaledStringIterSpec>
238 struct Value<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > const>
239         : Value<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > > {};
240 
241 // ----------------------------------------------------------------------------
242 // Metafunction GetValue
243 // ----------------------------------------------------------------------------
244 
245 // For Iter<TJournaledString, TJournaledStringIterSpec>
246 template <typename TJournaledString, typename TJournaledStringIterSpec>
247 struct GetValue<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > >
248 {
249     typedef typename GetValue<TJournaledString>::Type Type;
250 };
251 
252 template <typename TJournaledString, typename TJournaledStringIterSpec>
253 struct GetValue<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > const>
254         : GetValue<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > > {};
255 
256 // ----------------------------------------------------------------------------
257 // Metafunction Reference
258 // ----------------------------------------------------------------------------
259 
260 template <typename TJournaledString, typename TJournaledStringIterSpec>
261 struct Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > >
262 {
263     typedef typename Reference<TJournaledString>::Type Type;
264 };
265 
266 template <typename TJournaledString, typename TJournaledStringIterSpec>
267 struct Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > const>
268 {
269     typedef typename Reference<TJournaledString>::Type Type;
270 };
271 
272 // ----------------------------------------------------------------------------
273 // Metafunction Container
274 // ----------------------------------------------------------------------------
275 
276 template <typename TJournaledString, typename TJournaledStringIterSpec>
277 struct Container<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > >
278 {
279     typedef TJournaledString Type;
280 };
281 
282 template <typename TJournaledString, typename TJournaledStringIterSpec>
283 struct Container<Iter<TJournaledString, JournaledStringIterSpec<TJournaledStringIterSpec> > const>
284 {
285     typedef TJournaledString const Type;
286 };
287 
288 // ============================================================================
289 // Functions
290 // ============================================================================
291 
292 // For String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >
293 // ----------------------------------------------------------------------------
294 // Function begin                                                    [Standard]
295 // ----------------------------------------------------------------------------
296 
297 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
298 inline
299 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Standard>::Type
300 begin(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journalString, Standard const &)
301 {
302     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Standard>::Type TResult;
303     TResult result;
304     _initJournaledStringIterator(result, journalString);
305     return result;
306 }
307 
308 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
309 inline
310 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Standard>::Type
311 begin(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journalString, Standard const &)
312 {
313     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Standard>::Type TResult;
314     TResult result;
315     _initJournaledStringIterator(result, journalString);
316     return result;
317 }
318 
319 // ----------------------------------------------------------------------------
320 // Function begin                                                      [Rooted]
321 // ----------------------------------------------------------------------------
322 
323 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
324 inline
325 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Rooted>::Type
326 begin(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journalString, Rooted const &)
327 {
328     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Rooted>::Type TResult;
329     TResult result;
330     _initJournaledStringIterator(result, journalString);
331     return result;
332 }
333 
334 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
335 inline
336 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Rooted>::Type
337 begin(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journalString, Rooted const &)
338 {
339     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Rooted>::Type TResult;
340     TResult result;
341     _initJournaledStringIterator(result, journalString);
342     return result;
343 }
344 
345 // ----------------------------------------------------------------------------
346 // Function end                                                      [Standard]
347 // ----------------------------------------------------------------------------
348 
349 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
350 inline
351 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Standard>::Type
352 end(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journalString, Standard const &)
353 {
354     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Standard>::Type TResult;
355     TResult result;
356     result._journalStringPtr = &journalString;
357     _initJournaledStringIteratorEnd(result);
358     return result;
359 }
360 
361 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
362 inline
363 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Standard>::Type
364 end(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journalString, Standard const &)
365 {
366     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Standard>::Type TResult;
367     TResult result;
368     result._journalStringPtr = &journalString;
369     _initJournaledStringIteratorEnd(result);
370     return result;
371 }
372 
373 // ----------------------------------------------------------------------------
374 // Function end                                                        [Rooted]
375 // ----------------------------------------------------------------------------
376 
377 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
378 inline
379 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Rooted>::Type
380 end(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const & journalString, Rooted const &)
381 {
382     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > const, Rooted>::Type TResult;
383     TResult result;
384     result._journalStringPtr = &journalString;
385     _initJournaledStringIteratorEnd(result);
386     return result;
387 }
388 
389 template <typename TValue, typename THostSpec, typename TJournalSpec, typename TBufferSpec>
390 inline
391 typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Rooted>::Type
392 end(String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> > & journalString, Rooted const &)
393 {
394     typedef typename Iterator<String<TValue, Journaled<THostSpec, TJournalSpec, TBufferSpec> >, Rooted>::Type TResult;
395     TResult result;
396     result._journalStringPtr = &journalString;
397     _initJournaledStringIteratorEnd(result);
398     return result;
399 }
400 
401 // ----------------------------------------------------------------------------
402 // Function _initJournaledStringIterator()
403 // ----------------------------------------------------------------------------
404 
405 // For Iter<TJournaledString, JournaledStringIterSpec>
406 
407 template <typename TJournaledString, typename TJournalSpec>
408 inline
409 void
410 _initJournaledStringIterator(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator,
411                            TJournaledString & journalString)
412 {
413     iterator._journalStringPtr = &journalString;
414     iterator._journalEntriesIterator = begin(journalString._journalEntries);
415     // Update iterators on the segment.
416     _updateSegmentIterators(iterator);
417 }
418 
419 // ----------------------------------------------------------------------------
420 // Function _initJournaledStringIteratorEnd()
421 // ----------------------------------------------------------------------------
422 
423 template <typename TJournaledString, typename TJournalSpec>
424 inline
425 void
426 _initJournaledStringIteratorEnd(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
427 {
428     iterator._journalEntriesIterator = end(iterator._journalStringPtr->_journalEntries, Standard()) - 1;
429     _updateSegmentIteratorsLeft(iterator);
430     if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_PATCH)
431         ++iterator._currentInsertionBufferIt;
432     else
433         ++iterator._currentHostIt;
434 }
435 
436 // TODO(rmaerker): Rename to _updateSegmentIteratorsRight().
437 template <typename TJournaledString, typename TJournalSpec>
438 inline
439 void
440 _updateSegmentIterators(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
441 {
442     if (atEnd(iterator._journalEntriesIterator, _journalEntries(container(iterator))))
443     {
444         _initJournaledStringIteratorEnd(iterator);
445         return;
446     }
447     switch (value(iterator._journalEntriesIterator).segmentSource) {
448         case SOURCE_ORIGINAL:
449             iterator._hostSegmentBegin = begin(host(*iterator._journalStringPtr), Standard()) + value(iterator._journalEntriesIterator).physicalPosition;
450             iterator._hostSegmentEnd = iterator._hostSegmentBegin + value(iterator._journalEntriesIterator).length;
451             iterator._currentHostIt = iterator._hostSegmentBegin;
452             break;
453         case SOURCE_PATCH:
454             iterator._insertionBufferSegmentBegin = begin(iterator._journalStringPtr->_insertionBuffer, Standard()) + value(iterator._journalEntriesIterator).physicalPosition;
455             iterator._insertionBufferSegmentEnd = iterator._insertionBufferSegmentBegin + value(iterator._journalEntriesIterator).length;
456             iterator._currentInsertionBufferIt = iterator._insertionBufferSegmentBegin;
457             break;
458         default:
459             SEQAN_ASSERT_FAIL("Invalid segment source!");
460     }
461 }
462 
463 // ----------------------------------------------------------------------------
464 // Function _updateSegmentIteratorsLeft()
465 // ----------------------------------------------------------------------------
466 
467 template <typename TJournaledString, typename TJournalSpec>
468 inline
469 void
470 _updateSegmentIteratorsLeft(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
471 {
472     switch (value(iterator._journalEntriesIterator).segmentSource) {
473         case SOURCE_ORIGINAL:
474             iterator._hostSegmentBegin = begin(host(*iterator._journalStringPtr), Standard()) + value(iterator._journalEntriesIterator).physicalPosition;
475             iterator._hostSegmentEnd = iterator._hostSegmentBegin + value(iterator._journalEntriesIterator).length;
476             iterator._currentHostIt = iterator._hostSegmentEnd - 1;
477             break;
478         case SOURCE_PATCH:
479             iterator._insertionBufferSegmentBegin = begin(iterator._journalStringPtr->_insertionBuffer, Standard()) + value(iterator._journalEntriesIterator).physicalPosition;
480             iterator._insertionBufferSegmentEnd = iterator._insertionBufferSegmentBegin + value(iterator._journalEntriesIterator).length;
481             iterator._currentInsertionBufferIt = iterator._insertionBufferSegmentEnd - 1;
482             break;
483         default:
484             SEQAN_ASSERT_FAIL("Invalid segment source!");
485     }
486 }
487 
488 // ----------------------------------------------------------------------------
489 // Function value()
490 // ----------------------------------------------------------------------------
491 
492 template <typename TJournaledString, typename TJournalSpec>
493 inline typename Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type
494 value(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me)
495 {
496     typedef typename Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type TReference;
497     TReference res(me);
498     return res;
499 }
500 
501 template <typename TJournaledString, typename TJournalSpec>
502 inline typename Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
503 value(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & me)
504 {
505     typedef typename Reference<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type TReference;
506     TReference res(me);
507     return res;
508 }
509 
510 // ----------------------------------------------------------------------------
511 // Function atBegin
512 // ----------------------------------------------------------------------------
513 
514 template <typename TJournaledString, typename TJournalSpec>
515 inline bool
516 atBegin(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & me)
517 {
518     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
519     TIterator tmpIt = begin(*me._journalStringPtr, Standard());
520     return me == tmpIt;
521 }
522 
523 // ----------------------------------------------------------------------------
524 // Function atEnd
525 // ----------------------------------------------------------------------------
526 
527 template <typename TJournaledString, typename TJournalSpec>
528 inline bool
529 atEnd(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & me)
530 {
531     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
532     TIterator tmpIt = end(*me._journalStringPtr, Standard());
533     return me == tmpIt;
534 }
535 
536 // ----------------------------------------------------------------------------
537 // Function goBegin
538 // ----------------------------------------------------------------------------
539 
540 template <typename TJournaledString, typename TJournalSpec>
541 inline void
542 goBegin(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me)
543 {
544     me = begin(container(me), Standard());
545 }
546 
547 // ----------------------------------------------------------------------------
548 // Function goEnd
549 // ----------------------------------------------------------------------------
550 
551 template <typename TJournaledString, typename TJournalSpec>
552 inline void
553 goEnd(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me)
554 {
555     me = end(container(me), Standard());
556 }
557 
558 // assignValue
559 
560 template <typename TJournaledString, typename TJournalSpec, typename TValue>
561 inline void
562 assignValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me,
563             TValue const & _value)
564 {
565     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
566     assignValue(static_cast<TIterator const>(me), _value);
567 }
568 
569 template <typename TJournaledString, typename TJournalSpec, typename TValue>
570 inline void
571 assignValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator,
572             TValue const & _value)
573 {
574     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
575     typename Value<TIterator>::Type _temp_value = _value; //conversion
576     assignValue(*iterator._journalStringPtr, position(iterator), _temp_value);
577 }
578 
579 // moveValue
580 
581 template <typename TJournaledString, typename TJournalSpec, typename TValue>
582 inline void
583 moveValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me,
584           TValue const & _value)
585 {
586     // TODO(holtgrew): Copied from packed string. Actually, why no real move?
587     assignValue(me, _value);
588 }
589 
590 template <typename TJournaledString, typename TJournalSpec, typename TValue>
591 inline void
592 moveValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & me,
593           TValue const & _value)
594 {
595     // TODO(holtgrew): Copied from packed string. Actually, why no real move?
596     assignValue(me, _value);
597 }
598 
599 // valueConstruct
600 
601 template <typename TJournaledString, typename TJournalSpec>
602 inline void
603 valueConstruct(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & /*it*/)
604 {
605     // TODO(holtgrew): Intentionally left blank? Alphabet elements must be default-constructable.
606 }
607 
608 template <typename TJournaledString, typename TJournalSpec, typename TParam>
609 inline void
610 valueConstruct(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & it,
611                TParam const & param_)
612 {
613     assignValue(it, param_);
614 }
615 
616 template <typename TJournaledString, typename TJournalSpec, typename TParam>
617 inline void
618 valueConstruct(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & it,
619                TParam & param_,
620                Move const & /*tag*/)
621 {
622     moveValue(it, param_);
623 }
624 
625 // valueDestruct
626 
627 template <typename TJournaledString, typename TJournalSpec>
628 inline void
629 valueDestruct(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & /*it*/)
630 {
631     // TODO(holtgrew): Intentionally left blank? Copied from packed string, leads to problems with non-POD contents!
632 }
633 
634 // ----------------------------------------------------------------------------
635 // Function _localEntryPosition
636 // ----------------------------------------------------------------------------
637 
638 // TODO(rmaerker): Write documentation!
639 template <typename TJournaledString, typename TJournalSpec>
640 inline typename Position<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
641 _localEntryPosition(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
642 {
643     switch (value(iterator._journalEntriesIterator).segmentSource)
644     {
645         case SOURCE_ORIGINAL:
646             return iterator._currentHostIt - iterator._hostSegmentBegin;
647             break;
648         case SOURCE_PATCH:
649             return iterator._currentInsertionBufferIt - iterator._insertionBufferSegmentBegin;
650             break;
651         default:
652             SEQAN_ASSERT_FAIL("Invalid segment source!");
653             return 0;
654     }
655 }
656 
657 // ----------------------------------------------------------------------------
658 // Function _physicalPosition()
659 // ----------------------------------------------------------------------------
660 
661 template <typename TJournaledString, typename TJournalSpec>
662 inline typename Position<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
663 _physicalPosition(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
664 {
665     return value(iterator._journalEntriesIterator).physicalPosition + _localEntryPosition(iterator);
666 }
667 
668 // ----------------------------------------------------------------------------
669 // Function _physicalOriginPosition()
670 // ----------------------------------------------------------------------------
671 
672 template <typename TJournaledString, typename TJournalSpec>
673 inline typename Position<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
674 _physicalOriginPosition(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
675 {
676     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const TJournalIter;
677     typedef typename TJournalIter::TJournalEntriesIterator TEntriesIt;
678 
679     if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL)
680         return value(iterator._journalEntriesIterator).physicalOriginPosition + _localEntryPosition(iterator);
681 
682     SEQAN_ASSERT_EQ(value(iterator._journalEntriesIterator).segmentSource, SOURCE_PATCH);
683 
684     TEntriesIt tmp = iterator._journalEntriesIterator;
685     while (value(tmp).segmentSource == SOURCE_PATCH)
686     {
687         if (tmp == begin(_journalEntries(*iterator._journalStringPtr), Standard()))
688         {
689             if (value(tmp).segmentSource == SOURCE_PATCH)
690                 return 0;
691             break;
692         }
693         --tmp;
694     }
695     SEQAN_ASSERT_EQ(tmp->segmentSource, SOURCE_ORIGINAL);
696     return value(tmp).physicalOriginPosition + value(tmp).length;
697 
698 }
699 
700 // ----------------------------------------------------------------------------
701 // Function _virtualPosition()
702 // ----------------------------------------------------------------------------
703 
704 template <typename TJournaledString, typename TJournalSpec>
705 inline typename Position<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
706 _virtualPosition(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
707 {
708     return value(iterator._journalEntriesIterator).virtualPosition + _localEntryPosition(iterator);
709 }
710 
711 // ----------------------------------------------------------------------------
712 // Function position()
713 // ----------------------------------------------------------------------------
714 
715 template <typename TJournaledString, typename TJournalSpec>
716 inline typename Position<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type
717 position(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
718 {
719     return _virtualPosition(iterator);
720 }
721 
722 // ----------------------------------------------------------------------------
723 // Function setPosition
724 // ----------------------------------------------------------------------------
725 
726 // TODO(rmaerker): Write documentation!
727 template <typename TJournaledString, typename TJournalSpec, typename TPosition>
728 inline void
729 setPosition(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & me,
730             TPosition pos)
731 {
732     SEQAN_ASSERT_GEQ(pos, static_cast<TPosition>(0));
733 
734     // Handle case where pos points behind the container.
735     if (pos >= static_cast<TPosition>(length(container(me))))
736         goEnd(me);
737 
738     // Use binary search to find corresponding node.
739     me._journalEntriesIterator = findInJournalEntries(container(me)._journalEntries, pos);
740 
741     int offset = pos - value(me._journalEntriesIterator).virtualPosition;  // The offset within the current node.
742     switch (value(me._journalEntriesIterator).segmentSource)
743     {
744         case SOURCE_ORIGINAL:
745             me._currentHostIt = begin(host(container(me)), Standard()) +
746                                 value(me._journalEntriesIterator).physicalPosition + offset;
747             me._hostSegmentBegin = me._currentHostIt - offset;
748             me._hostSegmentEnd = me._hostSegmentBegin + value(me._journalEntriesIterator).length;
749             break;
750         case SOURCE_PATCH:
751             me._currentInsertionBufferIt = begin(container(me)._insertionBuffer, Standard()) +
752                                            value(me._journalEntriesIterator).physicalPosition + offset;
753             me._insertionBufferSegmentBegin = me._currentInsertionBufferIt - offset;
754             me._insertionBufferSegmentEnd = me._insertionBufferSegmentBegin + value(me._journalEntriesIterator).length;
755             break;
756         default:
757             SEQAN_ASSERT_FAIL("Unknown segment source!");
758     }
759 }
760 
761 // ----------------------------------------------------------------------------
762 // Function setContainer
763 // ----------------------------------------------------------------------------
764 
765 template <typename TJournaledString, typename TJournalSpec>
766 inline void
767 setContainer(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iter,
768              typename Container<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type & container)
769 {
770     iter._journalStringPtr = &container;
771 }
772 
773 // ----------------------------------------------------------------------------
774 // Function container
775 // ----------------------------------------------------------------------------
776 
777 template <typename TJournaledString, typename TJournalSpec>
778 inline typename Container<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type &
779 container(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iter)
780 {
781     return *iter._journalStringPtr;
782 }
783 
784 template <typename TJournaledString, typename TJournalSpec>
785 inline typename Container<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const>::Type &
786 container(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iter)
787 {
788     return *iter._journalStringPtr;
789 }
790 
791 // getValue
792 template <typename TJournaledString, typename TJournalSpec>
793 inline
794 typename GetValue<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type
795 getValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
796 {
797     if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL) {
798         return getValue(iterator._currentHostIt);
799     } else {
800         SEQAN_ASSERT_EQ(value(iterator._journalEntriesIterator).segmentSource, SOURCE_PATCH);
801         return getValue(iterator._currentInsertionBufferIt);
802     }
803 }
804 
805 template <typename TJournaledString, typename TJournalSpec>
806 inline
807 typename GetValue<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type
808 getValue(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
809 {
810     if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL) {
811         return getValue(iterator._currentHostIt);
812     } else {
813         SEQAN_ASSERT_EQ(value(iterator._journalEntriesIterator).segmentSource, SOURCE_PATCH);
814         return getValue(iterator._currentInsertionBufferIt);
815     }
816 }
817 
818 template <typename TJournaledString, typename TJournalSpec>
819 inline
820 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > &
821 operator++(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
822 {
823     switch (value(iterator._journalEntriesIterator).segmentSource) {
824         case SOURCE_ORIGINAL:
825             ++iterator._currentHostIt;
826             if (iterator._currentHostIt == iterator._hostSegmentEnd) {
827                 ++iterator._journalEntriesIterator;
828                 _updateSegmentIterators(iterator);
829             }
830             break;
831         case SOURCE_PATCH:
832             ++iterator._currentInsertionBufferIt;
833             if (iterator._currentInsertionBufferIt == iterator._insertionBufferSegmentEnd) {
834                 ++iterator._journalEntriesIterator;
835                 _updateSegmentIterators(iterator);
836             }
837             break;
838         default:
839             SEQAN_ASSERT_FAIL("Invalid Segment Source");
840     }
841     return iterator;
842 }
843 
844 template <typename TJournaledString, typename TJournalSpec>
845 inline
846 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >
847 operator++(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator, int /*postfix*/)
848 {
849     Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > temp(iterator);
850     ++iterator;
851     return temp;
852 }
853 
854 // ----------------------------------------------------------------------------
855 // Function operator--()                                               [prefix]
856 // ----------------------------------------------------------------------------
857 
858 template <typename TJournaledString, typename TJournalSpec>
859 inline
860 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > &
861 operator--(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
862 {
863         switch (value(iterator._journalEntriesIterator).segmentSource) {
864             case SOURCE_ORIGINAL:
865                 if (iterator._currentHostIt == iterator._hostSegmentBegin) {
866                     --iterator._journalEntriesIterator;
867                     _updateSegmentIteratorsLeft(iterator);
868                 }
869                 else
870                     --iterator._currentHostIt;
871                 break;
872             case SOURCE_PATCH:
873                 if (iterator._currentInsertionBufferIt == iterator._insertionBufferSegmentBegin) {
874                     --iterator._journalEntriesIterator;
875                     _updateSegmentIteratorsLeft(iterator);
876                 }
877                 else
878                     --iterator._currentInsertionBufferIt;
879                 break;
880             default:
881             {
882                 SEQAN_ASSERT_FAIL("Invalid segment source!");
883             }
884         }
885     return iterator;
886 }
887 
888 // ----------------------------------------------------------------------------
889 // Function operator--()                                              [postfix]
890 // ----------------------------------------------------------------------------
891 
892 template <typename TJournaledString, typename TJournalSpec>
893 inline
894 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >
895 operator--(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator,
896             int /*postfix*/)
897 {
898     Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > temp(iterator);
899     --iterator;
900     return temp;
901 }
902 
903 template <typename TJournaledString, typename TJournalSpec>
904 inline
905 typename Reference<TJournaledString>::Type
906 operator*(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator)
907 {
908     return value(iterator);
909 }
910 
911 template <typename TJournaledString, typename TJournalSpec>
912 inline
913 typename Reference<TJournaledString>::Type
914 operator*(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator)
915 {
916     return value(iterator);
917 }
918 
919 template <typename TJournaledString, typename TJournalSpec, typename TLen>
920 inline
921 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > &
922 operator+=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator,
923            TLen len_)
924 {
925 
926     SEQAN_ASSERT_GEQ(len_, static_cast<TLen>(0));
927 
928     TLen remaining;
929     if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL)
930         remaining = iterator._hostSegmentEnd - iterator._currentHostIt;
931     else
932         remaining = iterator._insertionBufferSegmentEnd - iterator._currentInsertionBufferIt;
933     while (len_ > 0 && remaining != 0)
934     {
935         SEQAN_ASSERT_GT(remaining, static_cast<TLen>(0));
936         if (len_ >= remaining) {
937             len_ -= remaining;
938             ++iterator._journalEntriesIterator;
939             _updateSegmentIterators(iterator);
940             if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL)
941                 remaining = iterator._hostSegmentEnd - iterator._currentHostIt;
942             else
943                 remaining = iterator._insertionBufferSegmentEnd - iterator._currentInsertionBufferIt;
944         }
945         else
946         {
947             if (value(iterator._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL)
948                 iterator._currentHostIt += len_;
949             else
950                 iterator._currentInsertionBufferIt += len_;
951             len_ = 0;
952         }
953     }
954     return iterator;
955 }
956 
957 template <typename TJournaledString, typename TJournalSpec>
958 inline
959 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >
960 operator+(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator,
961           typename Size<TJournaledString>::Type const & len)
962 {
963     Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > temp(iterator);
964     temp += len;
965     return temp;
966 }
967 
968 // ----------------------------------------------------------------------------
969 // Function operator-=()
970 // ----------------------------------------------------------------------------
971 
972 template <typename TJournaledString, typename TJournalSpec, typename TLen>
973 inline
974 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > &
975 operator-=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > & iterator,
976             TLen len_)
977 {
978     typedef Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > TIterator;
979     typedef typename Position<TIterator>::Type TPosition;
980 
981     // TODO(holtgrew): Handle case where len_ < 0?!
982     SEQAN_ASSERT_GEQ(len_, static_cast<TLen>(0));
983     size_t len = len_;
984 
985     // Handle bad case of len_ pointing before begin.
986     if (position(iterator) <= static_cast<TPosition>(len_)) {
987         iterator = TIterator(begin(*iterator._journalStringPtr));
988         return iterator;
989     }
990 
991     // Handle other case.
992     typedef typename Size<TJournaledString>::Type TSize;
993     while (len > 0) {
994         TSize relNodePos;
995         switch (value(iterator._journalEntriesIterator).segmentSource) {
996             case SOURCE_ORIGINAL:
997                 relNodePos = iterator._currentHostIt - iterator._hostSegmentBegin;
998                 if (len > relNodePos) {
999                     len -= (relNodePos + 1);
1000                     --iterator._journalEntriesIterator;
1001                     _updateSegmentIteratorsLeft(iterator);
1002                 }
1003                 else
1004                 {
1005                     iterator._currentHostIt -= len;
1006                     len = 0;
1007                 }
1008                 break;
1009             case SOURCE_PATCH:
1010                 relNodePos = iterator._currentInsertionBufferIt - iterator._insertionBufferSegmentBegin;
1011                 if (len > relNodePos) {
1012                     len -= (relNodePos + 1);
1013                     --iterator._journalEntriesIterator;
1014                     _updateSegmentIteratorsLeft(iterator);
1015                 } else {
1016                     iterator._currentInsertionBufferIt -= len;
1017                     len = 0;
1018                 }
1019                 break;
1020             default:
1021             {
1022                 SEQAN_ASSERT_FAIL("Invalid segment source!");
1023             }
1024         }
1025     }
1026     return iterator;
1027 }
1028 
1029 // ----------------------------------------------------------------------------
1030 // Function operator-()
1031 // ----------------------------------------------------------------------------
1032 
1033 template <typename TJournaledString, typename TJournalSpec>
1034 inline
1035 Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> >
1036 operator-(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & iterator,
1037            typename Size<TJournaledString>::Type const & len)
1038 {
1039     Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > temp(iterator);
1040     temp -= len;
1041     return temp;
1042 }
1043 
1044 template <typename TJournaledString, typename TJournalSpec>
1045 inline
1046 typename Difference<TJournaledString>::Type
1047 operator-(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & it1,
1048           Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & it2)
1049 {
1050     typedef typename Difference<TJournaledString>::Type TResult;
1051 
1052     // First, handle the cases where it1 or it2 are at the end.
1053     bool it1AtEnd = atEnd(it1._journalEntriesIterator, _journalEntries(container(it1)));
1054     bool it2AtEnd = atEnd(it2._journalEntriesIterator, _journalEntries(container(it2)));
1055     if (it1AtEnd && it2AtEnd) {
1056         return 0;
1057     } else if (it1AtEnd) {
1058         TResult len = length(*it1._journalStringPtr);
1059         TResult vPos = value(it2._journalEntriesIterator).virtualPosition;
1060         switch (value(it2._journalEntriesIterator).segmentSource) {
1061             case SOURCE_ORIGINAL:
1062                 vPos += it2._currentHostIt - it2._hostSegmentBegin;
1063                 break;
1064             case SOURCE_PATCH:
1065                 vPos += it2._currentInsertionBufferIt - it2._insertionBufferSegmentBegin;
1066                 break;
1067             default:
1068                 SEQAN_ASSERT_FAIL("Invalid segment source!");
1069         }
1070         SEQAN_ASSERT_LT(vPos, len);
1071         return len - vPos;
1072     } else if (it2AtEnd) {
1073         TResult len = length(*it1._journalStringPtr);
1074         TResult vPos = value(it1._journalEntriesIterator).virtualPosition;
1075         switch (value(it1._journalEntriesIterator).segmentSource) {
1076             case SOURCE_ORIGINAL:
1077                 vPos += it1._currentHostIt - it1._hostSegmentBegin;
1078                 break;
1079             case SOURCE_PATCH:
1080                 vPos += it1._currentInsertionBufferIt - it1._insertionBufferSegmentBegin;
1081                 break;
1082             default:
1083                 SEQAN_ASSERT_FAIL("Invalid segment source!");
1084         }
1085         SEQAN_ASSERT_LT(vPos, len);
1086         return vPos - len;
1087     }
1088 
1089     // Otherwise, we can simply subtract the virtual positions.
1090     TResult vPos1 = value(it1._journalEntriesIterator).virtualPosition;
1091     switch (value(it1._journalEntriesIterator).segmentSource) {
1092         case SOURCE_ORIGINAL:
1093             vPos1 += it1._currentHostIt - it1._hostSegmentBegin;
1094             break;
1095         case SOURCE_PATCH:
1096             vPos1 += it1._currentInsertionBufferIt - it1._insertionBufferSegmentBegin;
1097             break;
1098         default:
1099             SEQAN_ASSERT_FAIL("Invalid segment source!");
1100     }
1101     TResult vPos2 = value(it2._journalEntriesIterator).virtualPosition;
1102     switch (value(it2._journalEntriesIterator).segmentSource) {
1103         case SOURCE_ORIGINAL:
1104             vPos2 += it2._currentHostIt - it2._hostSegmentBegin;
1105             break;
1106         case SOURCE_PATCH:
1107             vPos2 += it2._currentInsertionBufferIt - it2._insertionBufferSegmentBegin;
1108             break;
1109         default:
1110             SEQAN_ASSERT_FAIL("Invalid segment source!");
1111     }
1112     return vPos1 - vPos2;
1113 }
1114 
1115 template <typename TJournaledString, typename TJournalSpec>
1116 inline
1117 bool
1118 operator==(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1119            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1120 {
1121     if (a._journalEntriesIterator != b._journalEntriesIterator)
1122         return false;
1123     if (value(a._journalEntriesIterator).segmentSource == SOURCE_ORIGINAL) {
1124         if (a._currentHostIt != b._currentHostIt)
1125             return false;
1126     } else {
1127         SEQAN_ASSERT_EQ(value(a._journalEntriesIterator).segmentSource, SOURCE_PATCH);
1128         if (a._currentInsertionBufferIt != b._currentInsertionBufferIt)
1129             return false;
1130     }
1131     return true;
1132 }
1133 
1134 template <typename TJournaledString, typename TJournalSpec>
1135 inline
1136 bool
1137 operator==(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1138            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1139 {
1140     typedef typename IterMakeConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type TConstIter;
1141     return static_cast<TConstIter>(a) == static_cast<TConstIter>(b);
1142 }
1143 
1144 template <typename TJournaledString, typename TJournalSpec>
1145 inline
1146 bool
1147 operator!=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1148            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1149 {
1150     return !(a == b);
1151 }
1152 
1153 template <typename TJournaledString, typename TJournalSpec>
1154 inline
1155 bool
1156 operator!=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1157            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1158 {
1159     return !(a == b);
1160 }
1161 
1162 template <typename TJournaledString, typename TJournalSpec>
1163 inline
1164 bool
1165 operator<(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1166            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1167 {
1168     return position(a) < position(b);
1169 }
1170 
1171 template <typename TJournaledString, typename TJournalSpec>
1172 inline
1173 bool
1174 operator<(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1175            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1176 {
1177     return position(a) < position(b);
1178 }
1179 
1180 template <typename TJournaledString, typename TJournalSpec>
1181 inline
1182 bool
1183 operator<=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1184            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1185 {
1186     return position(a) <= position(b);
1187 }
1188 
1189 template <typename TJournaledString, typename TJournalSpec>
1190 inline
1191 bool
1192 operator<=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1193            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1194 {
1195     return position(a) <= position(b);
1196 }
1197 
1198 template <typename TJournaledString, typename TJournalSpec>
1199 inline
1200 bool
1201 operator>(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1202            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1203 {
1204     return position(a) > position(b);
1205 }
1206 
1207 template <typename TJournaledString, typename TJournalSpec>
1208 inline
1209 bool
1210 operator>(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1211            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1212 {
1213     return position(a) > position(b);
1214 }
1215 
1216 template <typename TJournaledString, typename TJournalSpec>
1217 inline
1218 bool
1219 operator>=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1220            Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & b)
1221 {
1222     return position(a) >= position(b);
1223 }
1224 
1225 template <typename TJournaledString, typename TJournalSpec>
1226 inline
1227 bool
1228 operator>=(Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > const & a,
1229            typename IterComplementConst<Iter<TJournaledString, JournaledStringIterSpec<TJournalSpec> > >::Type const & b)
1230 {
1231     return position(a) >= position(b);
1232 }
1233 
1234 }  // namespace seqan
1235 
1236 #endif  // SEQAN_SEQUENCE_JOURNAL_SEQUENCE_JOURNAL_ITERATOR_H_
1237