1 // ==========================================================================
2 // SeqAn - The Library for Sequence Analysis
3 // ==========================================================================
4 // Copyright (c) 2006-2015, 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: Andreas Gogol-Doering <andreas.doering@mdc-berlin.de>
33 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
34 // ==========================================================================
35
36 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_ARRAY_H_
37 #define SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_ARRAY_H_
38
39 namespace seqan {
40
41 // ============================================================================
42 // Forwards
43 // ============================================================================
44
45 // ============================================================================
46 // Tags, Classes, Enums
47 // ============================================================================
48
49 template <typename TGaps>
50 class Iter<TGaps, GapsIterator<ArrayGaps> >
51 {
52 public:
53 // -----------------------------------------------------------------------
54 // Internal Typedefs
55 // -----------------------------------------------------------------------
56
57 typedef typename TGaps::TArrayPos_ TArrayPos_;
58 typedef typename TGaps::TArray_ TArray_;
59 typedef typename Value<TArray_>::Type TArrayValue_;
60 typedef typename Position<TGaps>::Type TGapsPos_;
61 typedef typename Source<TGaps>::Type TSource_;
62 typedef typename Position<TSource_>::Type TSourcePos_;
63
64 // -----------------------------------------------------------------------
65 // Member Variables
66 // -----------------------------------------------------------------------
67
68 // The following index and position members must be mutable since the
69 // insertion and deletion of gaps does not modify the iterator conceptually.
70
71 // Pointer to the iterated container / gaps object.
72 TGaps * _container;
73 // Index in the bucket array of the gaps object.
74 mutable TArrayPos_ _bucketIndex;
75 // Offset within the current bucket.
76 mutable TArrayValue_ _bucketOffset;
77 // Source position of the iterator.
78 mutable TSourcePos_ _sourcePosition;
79 // View position of the iterator.
80 mutable TGapsPos_ _unclippedViewPosition;
81
82 // -----------------------------------------------------------------------
83 // Constructors
84 // -----------------------------------------------------------------------
85
86 // Default constructor.
Iter()87 Iter() : _container(0), _bucketIndex(0), _bucketOffset(0), _sourcePosition(0), _unclippedViewPosition(0)
88 {}
89
90 // Copy constructor, required since we specify the one with complemented const below.
Iter(Iter const & other)91 Iter(Iter const & other) :
92 _container(other._container), _bucketIndex(other._bucketIndex), _bucketOffset(other._bucketOffset),
93 _sourcePosition(other._sourcePosition), _unclippedViewPosition(other._unclippedViewPosition)
94 {}
95
96 // Copy construtor for iterator -> const iterator conversion.
97 // TODO(holtgrew): Think of something smarter, to restrict source types?
98 template <typename TOtherIter>
Iter(TOtherIter const & other)99 Iter(TOtherIter const & other) :
100 _container(other._container), _bucketIndex(other._bucketIndex), _bucketOffset(other._bucketOffset),
101 _sourcePosition(other._sourcePosition), _unclippedViewPosition(other._unclippedViewPosition)
102 {}
103
104 // Create at begin of gaps.
Iter(TGaps & container_,Begin_ const &)105 Iter(TGaps & container_, Begin_ const &) :
106 _container(&container_), _bucketIndex(0), _bucketOffset(0), _sourcePosition(0),
107 _unclippedViewPosition(0)
108 {
109 if (_container->_array[0] == 0u)
110 _bucketIndex = 1;
111 // Go to beginning of clipping.
112 goFurther(*this, container_._clippingBeginPos);
113 }
114
115 // Create at end of gaps.
Iter(TGaps & container_,End_ const &)116 Iter(TGaps & container_, End_ const &) :
117 _container(&container_), _bucketIndex(0), _bucketOffset(0), _sourcePosition(0),
118 _unclippedViewPosition(0)
119 {
120 if (_container->_array[0] == 0u)
121 _bucketIndex = 1;
122 // Go to end of clipping position.
123 goFurther(*this, container_._clippingEndPos);
124 }
125
126 // Create with position.
127 // TODO(holtgrew): Chain constructor call to Begin_() here in C++11.
128 template <typename TPos>
Iter(TGaps & container_,TPos pos,Position_ const &)129 Iter(TGaps & container_, TPos pos, Position_ const &) :
130 _container(&container_), _bucketIndex(0), _bucketOffset(0), _sourcePosition(0),
131 _unclippedViewPosition(0)
132 {
133 if (_container->_array[0] == 0u)
134 _bucketIndex = 1;
135 // pos is an unclipped view position, make it clipped.
136 pos += container_._clippingBeginPos;
137 // Initialized for begin position. Now, advance.
138 goFurther(*this, pos);
139 }
140 };
141
142 // ============================================================================
143 // Metafunctions
144 // ============================================================================
145
146 // ============================================================================
147 // Functions
148 // ============================================================================
149
150 // ----------------------------------------------------------------------------
151 // Function isGap()
152 // ----------------------------------------------------------------------------
153
154 template <typename TGaps>
155 inline bool
isGap(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)156 isGap(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
157 {
158 return !(it._bucketIndex % 2);
159 }
160
161 // ----------------------------------------------------------------------------
162 // Function value()
163 // ----------------------------------------------------------------------------
164
165 template <typename TGaps>
166 inline typename Reference<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type
value(Iter<TGaps,GapsIterator<ArrayGaps>> & it)167 value(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
168 {
169 typedef typename Reference<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type TProxy;
170 return TProxy(it);
171 }
172
173 template <typename TGaps>
174 inline typename Reference<Iter<TGaps, GapsIterator<ArrayGaps> > const>::Type
value(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)175 value(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
176 {
177 typedef typename Reference<Iter<TGaps, GapsIterator<ArrayGaps> > const>::Type TProxy;
178 return TProxy(it);
179 }
180
181 // ----------------------------------------------------------------------------
182 // Function getValue()
183 // ----------------------------------------------------------------------------
184
185 // TODO(holtgrew): Ideally, we would only have one here.
186
187 template <typename TGaps>
188 inline typename GetValue<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type
getValue(Iter<TGaps,GapsIterator<ArrayGaps>> & it)189 getValue(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
190 {
191 typedef typename Value<TGaps>::Type TAlphabet;
192 if (isGap(it))
193 return gapValue<TAlphabet>();
194 else
195 return value(source(container(it)), it._sourcePosition);
196 }
197
198 template <typename TGaps>
199 inline typename GetValue<Iter<TGaps, GapsIterator<ArrayGaps> > const>::Type
getValue(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)200 getValue(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
201 {
202 typedef typename Value<TGaps>::Type TAlphabet;
203 if (isGap(it))
204 return gapValue<TAlphabet>();
205 else
206 return value(source(container(it)), it._sourcePosition);
207 }
208
209 // ----------------------------------------------------------------------------
210 // Function position()
211 // ----------------------------------------------------------------------------
212
213 // Returns clipped view position of gaps iterator.
214
215 template <typename TGaps>
216 inline typename Position<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type
position(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)217 position(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
218 {
219 if (it._container == 0)
220 return 0;
221
222 typedef Iter<TGaps, GapsIterator<ArrayGaps> > TIter;
223 typedef typename Position<TIter>::Type TPosition;
224 typedef typename TIter::TArrayPos_ TArrayPos;
225
226 TPosition unclippedViewPosition = 0;
227 for (TArrayPos i = 0; i < it._bucketIndex; ++i)
228 unclippedViewPosition += it._container->_array[i];
229 unclippedViewPosition += it._bucketOffset;
230
231 // TODO(holtgrew): Simply return it._unclippedViewPosition?
232 SEQAN_ASSERT_EQ(it._unclippedViewPosition, unclippedViewPosition);
233
234 return unclippedViewPosition - clippedBeginPosition(*it._container);
235 }
236
237 // ----------------------------------------------------------------------------
238 // Function countGaps()
239 // ----------------------------------------------------------------------------
240
241 template <typename TGaps>
242 inline typename Size<TGaps>::Type
countGaps(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)243 countGaps(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
244 {
245 if (!isGap(it) || atEnd(it))
246 return 0; // Not on a gap or at end, no gap here.
247
248 typedef typename Size<TGaps>::Type TSize;
249 TSize result = it._container->_array[it._bucketIndex] - it._bucketOffset;
250 // Check whether gaps reach behind the clipping and trim gaps for counting.
251 if ((TSize)(it._unclippedViewPosition + result) > (TSize)it._container->_clippingEndPos)
252 result = it._container->_clippingEndPos - it._unclippedViewPosition;
253 return result;
254 }
255
256 // ----------------------------------------------------------------------------
257 // Function countCharacters()
258 // ----------------------------------------------------------------------------
259
260 template <typename TGaps>
261 inline typename Size<TGaps>::Type
countCharacters(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)262 countCharacters(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
263 {
264 if (isGap(it) || atEnd(it))
265 return 0; // On a gap or at end, no characters here.
266
267 typedef typename Size<TGaps>::Type TSize;
268 TSize result = it._container->_array[it._bucketIndex] - it._bucketOffset;
269 // Check whether gaps reach behind the clipping and trim gaps for counting.
270 if ((TSize)(it._unclippedViewPosition + result) > (TSize)it._container->_clippingEndPos)
271 result = it._container->_clippingEndPos - it._unclippedViewPosition;
272 return result;
273 }
274
275 // ----------------------------------------------------------------------------
276 // Function goPrevious()
277 // ----------------------------------------------------------------------------
278
279 template <typename TGaps>
280 inline bool
goPrevious(Iter<TGaps,GapsIterator<ArrayGaps>> & it)281 goPrevious(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
282 {
283 typedef typename Position<TGaps>::Type TGapsPos;
284
285 if (atBegin(it)) // Handle case of being at the beginning of the gaps.
286 return false;
287
288 if (it._bucketOffset > TGapsPos(0))
289 {
290 // Not at the beginning of a bucket.
291 it._bucketOffset -= 1;
292 }
293 else
294 {
295 // At the beginning of a bucket.
296 it._bucketIndex -= 1;
297 SEQAN_ASSERT_GT(it._container->_array[it._bucketIndex], 0u);
298 it._bucketOffset = it._container->_array[it._bucketIndex] - 1;
299 }
300
301 // Adjust source position.
302 if (!isGap(it))
303 it._sourcePosition -= 1;
304 // Adjust clipped view position.
305 it._unclippedViewPosition -= 1;
306
307 return true;
308 }
309
310 // ----------------------------------------------------------------------------
311 // Function goNext()
312 // ----------------------------------------------------------------------------
313
314 template <typename TGaps>
315 inline bool
goNext(Iter<TGaps,GapsIterator<ArrayGaps>> & it)316 goNext(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
317 {
318 if (atEnd(it)) // Handle case of being at the end of the gaps.
319 return false;
320
321 // Adjust source position.
322 if (!isGap(it))
323 it._sourcePosition += 1;
324 // Adjust clipped view position.
325 it._unclippedViewPosition += 1;
326
327 if (it._bucketOffset + 1 != it._container->_array[it._bucketIndex])
328 {
329 // Not on last entry of a bucket.
330 it._bucketOffset += 1;
331 }
332 else
333 {
334 // On last entry of a bucket. If we are not in the last bucket then go
335 // to next bucket. Otherwise, go over the bucket, marks iterator-at-end.
336 if (it._bucketIndex + 1 != length(it._container->_array))
337 {
338 // Go to next.
339 it._bucketIndex += 1;
340 if (it._bucketIndex > length(it._container->_array))
341 SEQAN_ASSERT_GT(it._container->_array[it._bucketIndex], 0u);
342 it._bucketOffset = 0;
343 }
344 else
345 {
346 // Go to end of bucket.
347 it._bucketOffset += 1;
348 SEQAN_ASSERT_EQ(it._bucketIndex + 1, length(it._container->_array));
349 SEQAN_ASSERT_EQ(it._bucketOffset, back(it._container->_array));
350 }
351 }
352
353 return true;
354 }
355
356
357 // ----------------------------------------------------------------------------
358 // Function goNext()
359 // ----------------------------------------------------------------------------
360
361 template <typename TGaps, typename TDifference>
362 inline void
goFurther(Iter<TGaps,GapsIterator<ArrayGaps>> & it,TDifference delta)363 goFurther(Iter<TGaps, GapsIterator<ArrayGaps> > & it,
364 TDifference delta)
365 {
366 // TODO(holtgrew): Handle going backwards more efficiently.
367 if (delta == TDifference(0))
368 return;
369 if (isNegative(delta))
370 {
371 typedef typename MakeSigned<TDifference>::Type TSignedDifference;
372 for (; -static_cast<TSignedDifference>(delta); ++delta)
373 goPrevious(it);
374 return;
375 }
376
377 // Do nothing if we want are already at the end.
378 if (atEnd(it))
379 return;
380
381 // Case: Going forward.
382
383 // Get shortcut to new unclipped view position that we want to go to and
384 // limit this to the clipping end pos of the gaps object.
385 unsigned posEnd = it._unclippedViewPosition + delta;
386 if (posEnd > static_cast<unsigned>(it._container->_clippingEndPos))
387 posEnd = it._container->_clippingEndPos;
388
389 // The variable counter is the number of view positions to go forward.
390 for (unsigned counter = posEnd - it._unclippedViewPosition; counter > 0u;)
391 {
392 // Number of elements in bucket and number of remaining (behind offset in bucket).
393 unsigned count = it._container->_array[it._bucketIndex];
394 unsigned shift = count - it._bucketOffset;
395
396 if (shift < counter)
397 {
398 it._unclippedViewPosition += shift;
399 if (it._bucketIndex % 2)
400 it._sourcePosition += shift;
401 it._bucketOffset = 0;
402 it._bucketIndex += 1;
403 counter -= shift;
404 }
405 else if (shift == counter)
406 {
407 it._unclippedViewPosition += shift;
408 if (it._bucketIndex % 2)
409 it._sourcePosition += shift;
410
411 // On last entry of a bucket. If we are not in the last bucket then go to next bucket.
412 // Otherwise, go over the bucket, marks iterator-at-end.
413 if (it._bucketIndex + 1 != length(it._container->_array))
414 {
415 // Go to next.
416 it._bucketIndex += 1;
417 if (it._bucketIndex > length(it._container->_array))
418 SEQAN_ASSERT_GT(it._container->_array[it._bucketIndex], 0u);
419 it._bucketOffset = 0;
420 }
421 else
422 {
423 // Go to end of bucket.
424 it._bucketOffset += shift;
425 SEQAN_ASSERT_EQ(it._bucketIndex + 1, length(it._container->_array));
426 SEQAN_ASSERT_EQ(it._bucketOffset, back(it._container->_array));
427 }
428 counter = 0;
429 }
430 else // shift > counter
431 {
432 it._unclippedViewPosition += counter;
433 if (it._bucketIndex % 2)
434 it._sourcePosition += counter;
435 it._bucketOffset += counter;
436 counter = 0;
437 }
438 }
439 }
440
441 // ----------------------------------------------------------------------------
442 // Function atBegin()
443 // ----------------------------------------------------------------------------
444
445 // TODO(holtgrew): Non-const version is superflous :(
446 template <typename TGaps>
447 inline bool
atBegin(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)448 atBegin(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
449 {
450 return it._unclippedViewPosition == it._container->_clippingBeginPos;
451 }
452
453 template <typename TGaps>
454 inline bool
atBegin(Iter<TGaps,GapsIterator<ArrayGaps>> & it)455 atBegin(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
456 {
457 return it._unclippedViewPosition == it._container->_clippingBeginPos;
458 }
459
460 // ----------------------------------------------------------------------------
461 // Function atEnd()
462 // ----------------------------------------------------------------------------
463
464 // TODO(holtgrew): Non-const version is superflous :(
465 template <typename TGaps>
466 inline bool
atEnd(Iter<TGaps,GapsIterator<ArrayGaps>> const & it)467 atEnd(Iter<TGaps, GapsIterator<ArrayGaps> > const & it)
468 {
469 return it._unclippedViewPosition == it._container->_clippingEndPos;
470 }
471
472 template <typename TGaps>
473 inline bool
atEnd(Iter<TGaps,GapsIterator<ArrayGaps>> & it)474 atEnd(Iter<TGaps, GapsIterator<ArrayGaps> > & it)
475 {
476 return it._unclippedViewPosition == it._container->_clippingEndPos;
477 }
478
479 // ----------------------------------------------------------------------------
480 // Function insertGaps()
481 // ----------------------------------------------------------------------------
482
483 template <typename TGaps, typename TCount>
484 inline void
insertGaps(Iter<TGaps,GapsIterator<ArrayGaps>> const & it,TCount count)485 insertGaps(Iter<TGaps, GapsIterator<ArrayGaps> > const & it,
486 TCount count)
487 {
488 if (count == TCount(0))
489 return; // Do nothing!
490
491 typedef typename TGaps::TArray_ TArray;
492 typedef typename Position<TArray>::Type TArrayPos;
493
494 // Get shortcut to gaps.
495 TGaps & gaps = *it._container;
496 TArrayPos idx = it._bucketIndex;
497
498 // Handle case of being at the start of a character bucket.
499 if (idx % 2 && it._bucketOffset == 0)
500 {
501 idx -= 1;
502 it._bucketIndex -= 1;
503 it._bucketOffset = gaps._array[idx];
504 }
505
506 // Insert gaps, simple and fast if we are in a gaps bucket, a bit harder
507 // otherwise.
508 if (idx % 2) // character bucket
509 {
510 if (gaps._array[idx] > it._bucketOffset) // In the middle of the bucket.
511 {
512 TArray arr;
513 resize(arr, 2, 0);
514 arr[0] = count;
515 arr[1] = gaps._array[idx] - it._bucketOffset;
516 gaps._array[idx] = it._bucketOffset;
517 insert(gaps._array, idx + 1, arr);
518
519 // Update iterator.
520 it._bucketIndex += 1;
521 it._bucketOffset = 0;
522 }
523 else // At the end of the bucket.
524 {
525 if (idx + 1 < length(gaps._array)) // Not at end of array.
526 {
527 gaps._array[idx + 1] += count;
528 }
529 else // At end of array.
530 {
531 resize(gaps._array, length(gaps._array) + 2, 0);
532 gaps._array[idx + 1] = count;
533 gaps._array[idx + 2] = 0;
534 }
535 }
536 }
537 else // gap bucket
538 {
539 gaps._array[idx] += count;
540 }
541
542 // Adjust clipping information.
543 gaps._clippingEndPos += count;
544 }
545
546 // ----------------------------------------------------------------------------
547 // Function removeGaps()
548 // ----------------------------------------------------------------------------
549
550 template <typename TGaps, typename TCount>
551 inline typename Size<TGaps>::Type
removeGaps(Iter<TGaps,GapsIterator<ArrayGaps>> const & it,TCount count)552 removeGaps(Iter<TGaps, GapsIterator<ArrayGaps> > const & it, TCount count)
553 {
554 typedef typename TGaps::TArray_ TArray;
555 typedef typename Position<TArray>::Type TArrayPos;
556 typedef typename Value<TArray>::Type TArrayValue;
557 typedef typename Source<TGaps>::Type TSource;
558 typedef typename Position<TSource>::Type TSeqPos;
559
560 if (count == TCount(0))
561 return 0; // Do nothing!
562
563 // Get shortcuts.
564 TGaps & gaps = *it._container;
565 TArrayPos idx = it._bucketIndex;
566 TSeqPos offset = it._bucketOffset;
567
568 // If we are inside a non-gap bucket then we cannot remove any gaps.
569 if (idx % 2)
570 return 0;
571
572 // Otherwise, we can remove gaps right of the current position but not
573 // more than there are.
574 TSeqPos toRemove = count;
575 if (toRemove > gaps._array[idx] - offset)
576 toRemove = gaps._array[idx] - offset;
577 gaps._array[idx] -= toRemove;
578 // TODO(holtgrew): We have to decrement idx and adjust offset in case of merging!
579 // In some cases, we remove the whole gap and merge the character buckets.
580 if (gaps._array[idx] == TArrayValue(0))
581 {
582 // No merging for leading and trailing gap.
583 if (idx == TArrayPos(0) || idx == TArrayPos(length(gaps._array) - 1))
584 {
585 gaps._array[idx - 1] += gaps._array[idx + 1];
586 erase(gaps._array, idx, idx + 2);
587 }
588 }
589
590 // Also update the right clipping position.
591 gaps._clippingEndPos -= toRemove;
592
593 // Finally, return number of removed gaps.
594 return toRemove;
595 }
596
597 // ----------------------------------------------------------------------------
598 // Function operator<()
599 // ----------------------------------------------------------------------------
600
601 template <typename TGaps>
602 inline bool
603 operator<(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
604 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
605 {
606 return lhs._bucketIndex < rhs._bucketIndex ||
607 (lhs._bucketIndex == rhs._bucketIndex && lhs._bucketOffset < rhs._bucketOffset);
608 }
609
610 // ----------------------------------------------------------------------------
611 // Function operator>()
612 // ----------------------------------------------------------------------------
613
614 template <typename TGaps>
615 inline bool
616 operator>(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
617 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
618 {
619 return lhs._bucketIndex > rhs._bucketIndex ||
620 (lhs._bucketIndex == rhs._bucketIndex && lhs._bucketOffset > rhs._bucketOffset);
621 }
622
623 // ----------------------------------------------------------------------------
624 // Function operator<=()
625 // ----------------------------------------------------------------------------
626
627 template <typename TGaps>
628 inline bool
629 operator<=(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
630 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
631 {
632 return !(lhs > rhs);
633 }
634
635 // ----------------------------------------------------------------------------
636 // Function operator>=()
637 // ----------------------------------------------------------------------------
638
639 template <typename TGaps>
640 inline bool
641 operator>=(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
642 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
643 {
644 return !(lhs < rhs);
645 }
646
647 // ----------------------------------------------------------------------------
648 // Function operator==()
649 // ----------------------------------------------------------------------------
650
651 template <typename TGaps>
652 inline bool
653 operator==(Iter<TGaps, GapsIterator<ArrayGaps> > const & _lhs,
654 Iter<TGaps, GapsIterator<ArrayGaps> > const & _rhs)
655 {
656 return _lhs._container == _rhs._container &&
657 _lhs._bucketIndex == _rhs._bucketIndex &&
658 _lhs._bucketOffset == _rhs._bucketOffset;
659 }
660
661 // ----------------------------------------------------------------------------
662 // Function operator!=()
663 // ----------------------------------------------------------------------------
664
665 template <typename TGaps>
666 inline bool
667 operator!=(Iter<TGaps, GapsIterator<ArrayGaps> > const & _lhs,
668 Iter<TGaps, GapsIterator<ArrayGaps> > const & _rhs)
669 {
670 return _lhs._container != _rhs._container ||
671 _lhs._bucketIndex != _rhs._bucketIndex ||
672 _lhs._bucketOffset != _rhs._bucketOffset;
673 }
674
675 // ----------------------------------------------------------------------------
676 // Function difference()
677 // ----------------------------------------------------------------------------
678
679 template <typename TGaps>
680 inline typename Difference<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type
difference(Iter<TGaps,GapsIterator<ArrayGaps>> const & lhs,Iter<TGaps,GapsIterator<ArrayGaps>> const & rhs)681 difference(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
682 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
683 {
684 // TODO(holtgrew): Implementation could be more efficient.
685 // We only need to solve the case lhs < rhs.
686 if (lhs > rhs)
687 return -difference(rhs, lhs);
688 if (lhs == rhs)
689 return 0;
690 SEQAN_ASSERT(lhs < rhs); // Makes code below simpler.
691
692 typedef Iter<TGaps, GapsIterator<ArrayGaps> > TIter;
693 typedef typename Difference<TIter>::Type TDifference;
694 TDifference d = 0;
695 for (TIter it = lhs; it != rhs; ++it)
696 ++d;
697
698 return -d;
699 }
700
701 // ----------------------------------------------------------------------------
702 // Function operator-() [difference]
703 // ----------------------------------------------------------------------------
704
705 template <typename TGaps>
706 inline typename Difference<Iter<TGaps, GapsIterator<ArrayGaps> > >::Type
707 operator-(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs,
708 Iter<TGaps, GapsIterator<ArrayGaps> > const & rhs)
709 {
710 return difference(lhs, rhs);
711 }
712
713 // ----------------------------------------------------------------------------
714 // Function operator-() [copy movement]
715 // ----------------------------------------------------------------------------
716
717 template <typename TGaps, typename TDifference>
718 inline Iter<TGaps, GapsIterator<ArrayGaps> >
719 operator-(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs, TDifference d)
720 {
721 Iter<TGaps, GapsIterator<ArrayGaps> > result = lhs;
722 result -= d;
723 return result;
724 }
725
726 // ----------------------------------------------------------------------------
727 // Function operator+() [copy movement]
728 // ----------------------------------------------------------------------------
729
730 template <typename TGaps, typename TDifference>
731 inline Iter<TGaps, GapsIterator<ArrayGaps> >
732 operator+(Iter<TGaps, GapsIterator<ArrayGaps> > const & lhs, TDifference d)
733 {
734 Iter<TGaps, GapsIterator<ArrayGaps> > result = lhs;
735 result += d;
736 return result;
737 }
738
739 } // namespace seqan
740
741 #endif // SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_ARRAY_H_
742