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 // TODO(holtgrew): Switch to Host interface.
37 
38 #ifndef SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_
39 #define SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_
40 
41 namespace seqan {
42 
43 // ============================================================================
44 // Forwards
45 // ============================================================================
46 
47 // Internally used tag for creating iterators at the begin of containers.
48 struct Begin__;
49 typedef Tag<Begin__> Begin_;
50 
51 // Internally used tag for creating iterators at the end of containers.
52 struct End__;
53 typedef Tag<End__> End_;
54 
55 // Internally used tag for creating iterators inside of containers.
56 struct Position__;
57 typedef Tag<Position__> Position_;
58 
59 // ============================================================================
60 // Tags, Classes, Enums
61 // ============================================================================
62 
63 /*!
64  * @class GapsIterator
65  * @implements RandomAccessIteratorConcept
66  *
67  * @brief Iterator class for @link Gaps @endlink.
68  *
69  * @signature template <typename TGaps, typename TSpec>
70  *            class Iter<TGaps, GapsIterator<TSpec> >;
71  *
72  * @tparam TGaps The @link Gaps @endlink object for the iterator.
73  * @tparam TSpec The specializing tag.
74  */
75 
76 template <typename TSpec>
77 struct GapsIterator;
78 
79 // ============================================================================
80 // Metafunctions
81 // ============================================================================
82 
83 // ----------------------------------------------------------------------------
84 // Metafunction Position
85 // ----------------------------------------------------------------------------
86 
87 template <typename TGaps, typename TSpec>
88 struct Position<Iter<TGaps, GapsIterator<TSpec> > > :
89             Position<TGaps>
90 {};
91 
92 template <typename TGaps, typename TSpec>
93 struct Position<Iter<TGaps, GapsIterator<TSpec> > const> :
94             Position<Iter<TGaps, GapsIterator<TSpec> > >
95 {};
96 
97 // ----------------------------------------------------------------------------
98 // Metafunction Difference
99 // ----------------------------------------------------------------------------
100 
101 template <typename TGaps, typename TSpec>
102 struct Difference<Iter<TGaps, GapsIterator<TSpec> > > :
103             Difference<TGaps>
104 {};
105 
106 template <typename TGaps, typename TSpec>
107 struct Difference<Iter<TGaps, GapsIterator<TSpec> > const> :
108             Difference<Iter<TGaps, GapsIterator<TSpec> > >
109 {};
110 
111 // ----------------------------------------------------------------------------
112 // Metafunction Source
113 // ----------------------------------------------------------------------------
114 
115 // TODO(holtgrew): Should this be Host? or SourceIterator?
116 
117 template <typename TGaps, typename TSpec>
118 struct Source<Iter<TGaps, GapsIterator<TSpec> > >
119 {
120     typedef typename Source<TGaps>::Type TSource_;
121     typedef typename Iterator<TSource_, Rooted>::Type Type;
122 };
123 
124 template <typename TGaps, typename TSpec>
125 struct Source<Iter<TGaps, GapsIterator<TSpec> > const>
126 {
127     typedef typename Source<TGaps>::Type TSource_;
128     typedef typename Iterator<TSource_, Rooted>::Type Type;
129 };
130 
131 // ----------------------------------------------------------------------------
132 // Metafunction Value
133 // ----------------------------------------------------------------------------
134 
135 template <typename TGaps, typename TSpec>
136 struct Value<Iter<TGaps, GapsIterator<TSpec> > >
137 {
138     typedef typename Source<Iter<TGaps, GapsIterator<TSpec> > >::Type TSource_;
139     typedef typename Value<TSource_>::Type TSourceValue_;
140     //typedef TSourceValue_ Type;
141     // TODO(holtgrew): We really want gapped values here but there are issues...
142     typedef typename GappedValueType<TSourceValue_>::Type Type;
143 };
144 
145 template <typename TGaps, typename TSpec>
146 struct Value<Iter<TGaps, GapsIterator<TSpec> > const> :
147             Value<Iter<TGaps, GapsIterator<TSpec> > > {};
148 
149 // ----------------------------------------------------------------------------
150 // Metafunction GetValue
151 // ----------------------------------------------------------------------------
152 
153 template <typename TGaps, typename TSpec>
154 struct GetValue<Iter<TGaps, GapsIterator<TSpec> > > :
155     Value<Iter<TGaps, GapsIterator<TSpec> > >
156 {
157 };
158 
159 template <typename TGaps, typename TSpec>
160 struct GetValue<Iter<TGaps, GapsIterator<TSpec> > const> :
161     Value<Iter<TGaps, GapsIterator<TSpec> > const>
162 {
163 };
164 
165 // ----------------------------------------------------------------------------
166 // Metafunction Reference
167 // ----------------------------------------------------------------------------
168 
169 template <typename TGaps, typename TSpec>
170 struct Reference<Iter<TGaps, GapsIterator<TSpec> > >
171 {
172     typedef Iter<TGaps, GapsIterator<TSpec> > TIterator_;
173     typedef Proxy<IteratorProxy<TIterator_> > Type;
174 };
175 
176 template <typename TGaps, typename TSpec>
177 struct Reference<Iter<TGaps, GapsIterator<TSpec> > const>
178 {
179     typedef Iter<TGaps, GapsIterator<TSpec> const > TIterator_;
180     typedef Proxy<IteratorProxy<TIterator_> > Type;
181 };
182 
183 // ============================================================================
184 // Functions
185 // ============================================================================
186 
187 // ----------------------------------------------------------------------------
188 // Function operator++
189 // ----------------------------------------------------------------------------
190 
191 // TODO(holtgrew): Could be general forward
192 
193 template <typename TGaps, typename TSpec>
194 inline Iter<TGaps, GapsIterator<TSpec> > &
195 operator++(Iter<TGaps, GapsIterator<TSpec> > & it)
196 {
197     goNext(it);
198     return it;
199 }
200 
201 template <typename TGaps, typename TSpec>
202 inline Iter<TGaps, GapsIterator<TSpec> >
203 operator++(Iter<TGaps, GapsIterator<TSpec> > & it, int)
204 {
205     Iter<TGaps, GapsIterator<TSpec> > ret = it;
206     goNext(it);
207     return ret;
208 }
209 
210 // ----------------------------------------------------------------------------
211 // Function operator--
212 // ----------------------------------------------------------------------------
213 
214 template <typename TGaps, typename TSpec>
215 inline Iter<TGaps, GapsIterator<TSpec> > &
216 operator--(Iter<TGaps, GapsIterator<TSpec> > & it)
217 {
218     goPrevious(it);
219     return it;
220 }
221 
222 template <typename TGaps, typename TSpec>
223 inline Iter<TGaps, GapsIterator<TSpec> >
224 operator--(Iter<TGaps, GapsIterator<TSpec> > & it, int)
225 {
226     Iter<TGaps, GapsIterator<TSpec> > ret = it;
227     goPrevious(it);
228     return ret;
229 }
230 
231 // ----------------------------------------------------------------------------
232 // Function insertGap()
233 // ----------------------------------------------------------------------------
234 
235 /*!
236  * @fn GapsIterator#insertGap
237  * @brief Insert gap at the current position.
238  *
239  * @signature void insertGap(it);
240  *
241  * @param[in,out] it The iterator to insert gaps at.
242  */
243 
244 // Forward to insertGaps() which has to be implemented by the specific gap
245 // iterator.
246 
247 template <typename TGaps, typename TSpec>
248 inline void
249 insertGap(Iter<TGaps, GapsIterator<TSpec> > & it)
250 {
251     insertGaps(it, 1);
252 }
253 
254 // ----------------------------------------------------------------------------
255 // Function isCharacter()
256 // ----------------------------------------------------------------------------
257 
258 /*!
259  * @fn GapsIterator#isCharacter
260  * @brief Query an iterator for being at a character
261  *
262  * @signature bool isCharacter(it);
263  *
264  * @param[in] it Iterator to query for pointing at a character.
265  *
266  * @return bool <tt>true</tt> if <tt>it</tt> is at a character and <tt>false</tt> otherwise.
267  */
268 
269 template <typename TGaps, typename TSpec>
270 bool isCharacter(Iter<TGaps, GapsIterator<TSpec> > const & it)
271 {
272     return !isGap(it);
273 }
274 
275 // ----------------------------------------------------------------------------
276 // Function countCharacters()
277 // ----------------------------------------------------------------------------
278 
279 /*!
280  * @fn GapsIterator#countCharacters
281  * @brief Count characters at iterator.
282  *
283  * @signature TSize countCharacters(it);
284  *
285  * @param[in] it Iterator for counting characters at.
286  *
287  * @return TSize Number of characters.
288  */
289 
290 // ----------------------------------------------------------------------------
291 // Function isGap()
292 // ----------------------------------------------------------------------------
293 
294 /*!
295  * @fn GapsIterator#isGap
296  * @brief Query an iterator for being at a gap
297  *
298  * @signature bool isGap(it);
299  *
300  * @param[in] it Iterator to query for pointing at a gap.
301  *
302  * @return bool <tt>true</tt> if <tt>it</tt> is at a gap and <tt>false</tt> otherwise.
303  */
304 
305 // ----------------------------------------------------------------------------
306 // Function countGaps()
307 // ----------------------------------------------------------------------------
308 
309 /*!
310  * @fn GapsIterator#countGaps
311  * @brief Count gaps at iterator.
312  *
313  * @signature TSize countGaps(it);
314  *
315  * @param[in] it Iterator for counting gaps at.
316  *
317  * @return TSize Number of gaps.
318  */
319 
320 // ----------------------------------------------------------------------------
321 // Function insertGaps()
322 // ----------------------------------------------------------------------------
323 
324 /*!
325  * @fn GapsIterator#insertGaps
326  * @brief Insert gaps at the current position.
327  *
328  * @signature void insertGaps(it, num);
329  *
330  * @param[in,out] it  Remove gap at the given position (if any).
331  * @param[in]     num Number of gaps to insert.
332  */
333 
334 // ----------------------------------------------------------------------------
335 // Function removeGap()
336 // ----------------------------------------------------------------------------
337 
338 /*!
339  * @fn GapsIterator#removeGap
340  * @brief Insert gap at the current position.
341  *
342  * @signature TSize removeGap(it);
343  *
344  * @param[in,out] it Remove gap at the given position (if any).
345  *
346  * @return TSize Number of removed gaps.
347  */
348 
349 // Forward to removeGaps() which has to be implemented by the specific gap
350 // iterator.
351 
352 template <typename TGaps, typename TSpec>
353 inline typename Size<TGaps>::Type
354 removeGap(Iter<TGaps, GapsIterator<TSpec> > & it)
355 {
356     return removeGaps(it, 1);
357 }
358 
359 // ----------------------------------------------------------------------------
360 // Function removeGaps()
361 // ----------------------------------------------------------------------------
362 
363 /*!
364  * @fn GapsIterator#removeGaps
365  * @brief Remove gaps from the current position.
366  *
367  * @signature TSize removeGaps(it, num);
368  *
369  * @param[in,out] it  Remove gap at the given position (if any).
370  * @param[in]     num Number of gaps to remove.
371  *
372  * @return TSize Number of removed gaps.
373  */
374 
375 // ----------------------------------------------------------------------------
376 // Function assignValue()
377 // ----------------------------------------------------------------------------
378 
379 // TODO(holtgrew): Const consistency problems.
380 
381 template <typename TGaps, typename TSpec, typename TValue>
382 inline void
383 assignValue(Iter<TGaps, GapsIterator<TSpec> > & me,
384             TValue const & val)
385 {
386     if (!isGap(me))
387     {
388         assignValue(source(me), val);
389     }
390     // TODO(holtgrew): Else, inserting gaps is problematic...
391 }
392 
393 template <typename TGaps, typename TSpec, typename TValue>
394 inline void
395 assignValue(Iter<TGaps, GapsIterator<TSpec> > const & me,
396             TValue const & val)
397 {
398     if (!isGap(me))
399     {
400         assignValue(source(me), val);
401     }
402 }
403 
404 // ----------------------------------------------------------------------------
405 // Function container()
406 // ----------------------------------------------------------------------------
407 
408 template <typename TGaps, typename TSpec>
409 inline TGaps &
410 container(Iter<TGaps, GapsIterator<TSpec> > & me)
411 {
412     return *me._container;
413 }
414 
415 template <typename TGaps, typename TSpec>
416 inline TGaps &
417 container(Iter<TGaps, GapsIterator<TSpec> > const & me)
418 {
419     return *me._container;
420 }
421 
422 // ----------------------------------------------------------------------------
423 // Function source
424 // ----------------------------------------------------------------------------
425 
426 // Returns host iterator.
427 
428 // TODO(holtgrew): Non-const version is superflous.
429 template <typename TGaps, typename TSpec>
430 inline typename Source<Iter<TGaps, GapsIterator<TSpec> > >::Type /*returns copy*/
431 source(Iter<TGaps, GapsIterator<TSpec> > & it)
432 {
433     return iter(container(it), toSourcePosition(container(it), position(it)));
434 }
435 
436 template <typename TGaps, typename TSpec>
437 inline typename Source<Iter<TGaps, GapsIterator<TSpec> > const>::Type /*returns copy*/
438 source(Iter<TGaps, GapsIterator<TSpec> > const & it)
439 {
440     return iter(container(source(it)), toSourcePosition(container(it), position(it)));
441 }
442 
443 // TODO(holtgrew): setSource? setContainer?
444 
445 // ----------------------------------------------------------------------------
446 // Function operator+=
447 // ----------------------------------------------------------------------------
448 
449 template <typename TGaps, typename TSpec, typename TDiff>
450 inline Iter<TGaps, GapsIterator<TSpec> > &
451 operator+=(Iter<TGaps, GapsIterator<TSpec> > & it, TDiff diff)
452 {
453     goFurther(it, diff);
454     return it;
455 }
456 
457 // ----------------------------------------------------------------------------
458 // Function operator-=
459 // ----------------------------------------------------------------------------
460 
461 template <typename TGaps, typename TSpec, typename TDiff>
462 inline Iter<TGaps, GapsIterator<TSpec> > &
463 operator-=(Iter<TGaps, GapsIterator<TSpec> > & it, TDiff diff)
464 {
465     goFurther(it, -(__int64)(diff));
466     return it;
467 }
468 
469 // ----------------------------------------------------------------------------
470 // Function goFurther
471 // ----------------------------------------------------------------------------
472 
473 // TODO(holtgrew): Implementation could be faster.
474 template <typename TGaps, typename TSpec, typename TDifference>
475 inline void
476 goFurther(Iter<TGaps, GapsIterator<TSpec> > & it,
477           TDifference steps)
478 {
479     typedef typename MakeSigned<TDifference>::Type TSignedDifference;
480     if (steps > TDifference(0))
481         for (; steps; --steps)
482             goNext(it);
483     else
484         for (; -static_cast<TSignedDifference>(steps); ++steps)
485             goPrevious(it);
486 }
487 
488 // ----------------------------------------------------------------------------
489 // Function isClipped()
490 // ----------------------------------------------------------------------------
491 
492 template <typename TGaps, typename TSpec>
493 inline bool
494 isClipped(Iter<TGaps, GapsIterator<TSpec> > const &)
495 {
496     return false;
497 }
498 
499 }  // namespace seqan
500 
501 #endif  // SEQAN_INCLUDE_SEQAN_ALIGN_GAPS_ITERATOR_BASE_H_
502