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: David Weese <david.weese@fu-berlin.de>
33 // Author: Manuel Holtgrewe <manuel.holtgrewe@fu-berlin.de>
34 // ==========================================================================
35 
36 #ifndef SEQAN_HEADER_MODIFIER_REVERSE_H
37 #define SEQAN_HEADER_MODIFIER_REVERSE_H
38 
39 namespace seqan
40 {
41 
42 // ==========================================================================
43 // Forwards
44 // ==========================================================================
45 
46 // ==========================================================================
47 // Classes, Enums, Typedefs
48 // ==========================================================================
49 
50 // --------------------------------------------------------------------------
51 // Class ModReverse Iterator
52 // --------------------------------------------------------------------------
53 
54 /*!
55  * @class ModReverseIterator
56  * @extends ModifiedIterator
57  * @headerfile <seqan/modifier.h>
58  * @brief Mirror the characters from begin to end.
59  *
60  * @signature template <typename THost>
61  *            class ModifiedIterator<THost, ModReverse>;
62  *
63  * @tparam THost original iterator.
64  */
65 
66 /*!
67  * @class ModReverseString
68  * @extends ModifiedString
69  * @headerfile <seqan/modifier.h>
70  * @brief Mirror the characters from begin to end.
71  *
72  * @signature template <typename THost>
73  *            class ModifiedString<THost, ModReverse>;
74  *
75  * @tparam THost original string.
76  */
77 
78 struct ModReverse_;
79 typedef Tag<ModReverse_> ModReverse;
80 
81 // ==========================================================================
82 // Metafunctions
83 // ==========================================================================
84 
85 // --------------------------------------------------------------------------
86 // Metafunction Cargo                           [ModReverse ModifiedIterator]
87 // --------------------------------------------------------------------------
88 
89 template <typename THost>
90 struct Cargo<ModifiedIterator<THost, ModReverse> >
91 {
92     typedef Cargo Type;        // to reduce namespace pollution
93     bool _atEnd;
94 
95     Cargo() : _atEnd(false)
96     {}
97 };
98 
99 // --------------------------------------------------------------------------
100 // Metafunction Iterator                          [ModReverse ModifiedString]
101 // --------------------------------------------------------------------------
102 
103 template <typename THost>
104 struct Iterator<ModifiedString<THost, ModReverse>, Standard>
105 {
106     typedef ModifiedIterator<typename Iterator<THost, Rooted>::Type, ModReverse> Type;
107 };
108 
109 template <typename THost>
110 struct Iterator<ModifiedString<THost, ModReverse> const, Standard>
111 {
112     typedef ModifiedIterator<typename Iterator<THost, Rooted>::Type, ModReverse> Type;
113 };
114 
115 // --------------------------------------------------------------------------
116 // Metafunction DefaultIteratorSpec               [ModReverse ModifiedString]
117 // --------------------------------------------------------------------------
118 
119 template <typename THost>
120 struct DefaultIteratorSpec< ModifiedString<THost, ModReverse> >
121 {
122     typedef Rooted Type;
123 };
124 
125 // ==========================================================================
126 // Functions
127 // ==========================================================================
128 
129 // --------------------------------------------------------------------------
130 // Function goNext()                            [ModReverse ModifiedIterator]
131 // --------------------------------------------------------------------------
132 
133 template <typename THost>
134 inline void
135 goNext(ModifiedIterator<THost, ModReverse> & me)
136 {
137     if (atBegin(host(me)))
138         cargo(me)._atEnd = true;
139     else
140         goPrevious(host(me));
141 }
142 
143 // --------------------------------------------------------------------------
144 // Function goPrevious()                        [ModReverse ModifiedIterator]
145 // --------------------------------------------------------------------------
146 
147 template <typename THost>
148 inline void
149 goPrevious(ModifiedIterator<THost, ModReverse> & me)
150 {
151     if (cargo(me)._atEnd)
152         cargo(me)._atEnd = false;
153     else
154         goNext(host(me));
155 }
156 
157 // --------------------------------------------------------------------------
158 // Function goEnd()                             [ModReverse ModifiedIterator]
159 // --------------------------------------------------------------------------
160 
161 template <typename THost, typename TContainer>
162 inline void
163 goEnd(ModifiedIterator<THost, ModReverse> & me,
164       TContainer & container)
165 {
166     goBegin(host(me), host(container));
167     cargo(me)._atEnd = true;
168 }
169 
170 // --------------------------------------------------------------------------
171 // Function goBegin()                           [ModReverse ModifiedIterator]
172 // --------------------------------------------------------------------------
173 
174 template <typename THost, typename TContainer>
175 inline void
176 goBegin(ModifiedIterator<THost, ModReverse> & me,
177         TContainer & container)
178 {
179     typedef typename Host<TContainer>::Type THostContainer;
180     typename Parameter_<THostContainer>::Type hostContainer = host(container);
181     goEnd(host(me), hostContainer);
182     if (atBegin(host(me), hostContainer))
183     {
184         cargo(me)._atEnd = true;
185     }
186     else
187     {
188         cargo(me)._atEnd = false;
189         goPrevious(host(me));
190     }
191 }
192 
193 //template <typename THost>
194 //inline void
195 //goBegin(ModifiedIterator<THost, ModReverse> & me)
196 //{
197 //    goEnd(host(me));
198 //    if (atBegin(host(me)))
199 //    {
200 //        cargo(me)._atEnd = true;
201 //    }
202 //    else
203 //    {
204 //        cargo(me)._atEnd = false;
205 //        goPrevious(host(me));
206 //    }
207 //}
208 
209 // --------------------------------------------------------------------------
210 // Function operator+=()                        [ModReverse ModifiedIterator]
211 // --------------------------------------------------------------------------
212 
213 template <typename THost, typename TDelta>
214 inline ModifiedIterator<THost, ModReverse> &
215 operator+=(ModifiedIterator<THost, ModReverse> & me, TDelta delta_)
216 {
217     typedef ModifiedIterator<THost, ModReverse> TIterator;
218     typedef typename Position<TIterator>::Type TPosition;
219     TPosition delta = delta_;
220 
221     if (delta == 0)
222     {
223         return me;
224     }
225     if (delta > 0)
226     {
227         if (position(host(me)) < delta)
228         {
229             cargo(me)._atEnd = true;
230             --delta;
231         }
232         host(me) -= delta;
233     }
234     else
235     {
236         if (cargo(me)._atEnd)
237         {
238             cargo(me)._atEnd = false;
239             ++delta;
240         }
241         host(me) -= delta;
242     }
243     return me;
244 }
245 
246 // --------------------------------------------------------------------------
247 // Function operator-=()                        [ModReverse ModifiedIterator]
248 // --------------------------------------------------------------------------
249 
250 template <typename THost, typename TDelta>
251 inline ModifiedIterator<THost, ModReverse> &
252 operator-=(ModifiedIterator<THost, ModReverse> & me, TDelta delta)
253 {
254     typedef typename Position<THost>::Type TPos;
255     typedef typename MakeSigned<TPos>::Type TSignedPos;
256 
257     if (delta > 0)
258     {
259         if (cargo(me)._atEnd)
260         {
261             cargo(me)._atEnd = false;
262             --delta;
263         }
264         host(me) += delta;
265     }
266     else
267     {
268         if ((TSignedPos)position(host(me)) < -(TSignedPos)delta)
269         {
270             cargo(me)._atEnd = true;
271             ++delta;
272         }
273         host(me) -= -delta;
274     }
275     return me;
276 }
277 // --------------------------------------------------------------------------
278 // Function operator-()                         [ModReverse ModifiedIterator]
279 // --------------------------------------------------------------------------
280 
281 template <typename THost, typename TPos>
282 inline ModifiedIterator<THost, ModReverse>
283 operator-(ModifiedIterator<THost, ModReverse> me, TPos const i)
284 {
285     return me -= i;
286 }
287 
288 // --------------------------------------------------------------------------
289 // Function operator-()                         [ModReverse ModifiedIterator]
290 // --------------------------------------------------------------------------
291 
292 template <typename THost>
293 inline typename Difference< ModifiedIterator<THost, ModReverse> >::Type
294 operator-(ModifiedIterator<THost, ModReverse> const & a,
295           ModifiedIterator<THost, ModReverse> const & b)
296 {
297     typename Difference< ModifiedIterator<THost, ModReverse> >::Type diff = host(b) - host(a);
298     if (cargo(a)._atEnd)
299         ++diff;
300     if (cargo(b)._atEnd)
301         --diff;
302     return diff;
303 }
304 
305 // --------------------------------------------------------------------------
306 // Function position()                          [ModReverse ModifiedIterator]
307 // --------------------------------------------------------------------------
308 
309 template <typename THost>
310 inline typename Position<ModifiedIterator<THost, ModReverse> const>::Type
311 position(ModifiedIterator<THost, ModReverse> const & me)
312 {
313     if (cargo(me)._atEnd)
314         return length(container(host(me)));
315     else
316         return length(container(host(me))) - 1 - position(host(me));
317 }
318 
319 // rooted overload
320 template <typename TContainer1, typename TIterator, typename TSpec, typename TContainer2>
321 inline typename Position<ModifiedIterator<Iter<TContainer1, AdaptorIterator<TIterator, TSpec> >, ModReverse> const>::Type
322 position(ModifiedIterator<Iter<TContainer1, AdaptorIterator<TIterator, TSpec> >, ModReverse> const & me,
323          TContainer2 const &)
324 {
325     return position(me); // rooted has container
326 }
327 
328 template <typename THost, typename TContainer>
329 inline typename Position<ModifiedIterator<THost, ModReverse> const>::Type
330 position(ModifiedIterator<THost, ModReverse> const & me, TContainer const &cont)
331 {
332     if (cargo(me)._atEnd)
333         return length(cont);
334     else
335         return length(cont) - 1 - position(host(me), cont);
336 }
337 
338 // --------------------------------------------------------------------------
339 // Function setPosition()                       [ModReverse ModifiedIterator]
340 // --------------------------------------------------------------------------
341 
342 template <typename THost, typename TPosition>
343 inline void
344 setPosition(ModifiedIterator<THost, ModReverse> const & me, TPosition pos)
345 {
346     setPosition(host(me), length(container(host(me))) - 1 - pos);
347 }
348 
349 // --------------------------------------------------------------------------
350 // Function operator==()                        [ModReverse ModifiedIterator]
351 // --------------------------------------------------------------------------
352 
353 template <typename THost>
354 inline bool
355 operator==(ModifiedIterator<THost, ModReverse> const & a,
356            ModifiedIterator<THost, ModReverse> const & b)
357 {
358     return cargo(a)._atEnd == cargo(b)._atEnd && host(a) == host(b);
359 }
360 
361 // --------------------------------------------------------------------------
362 // Function operator<()                         [ModReverse ModifiedIterator]
363 // --------------------------------------------------------------------------
364 
365 template <typename THost>
366 inline bool
367 operator<(ModifiedIterator<THost, ModReverse> const & a,
368           ModifiedIterator<THost, ModReverse> const & b)
369  {
370     return (!cargo(a)._atEnd && cargo(b)._atEnd) ||
371             (!cargo(a)._atEnd && !cargo(b)._atEnd && host(a) > host(b));
372 }
373 
374 // --------------------------------------------------------------------------
375 // Function atEnd()                             [ModReverse ModifiedIterator]
376 // --------------------------------------------------------------------------
377 
378 template <typename THost, typename TContainer>
379 inline bool
380 atBegin(ModifiedIterator<THost, ModReverse> const & me,
381         TContainer const & container)
382 {
383     return position(me, container) == 0;
384 }
385 
386 template <typename THost>
387 inline bool
388 atBegin(ModifiedIterator<THost, ModReverse> const & me)
389 {
390     return position(me) == 0;
391 }
392 
393 // --------------------------------------------------------------------------
394 // Function atEnd()                             [ModReverse ModifiedIterator]
395 // --------------------------------------------------------------------------
396 
397 template <typename THost, typename TContainer>
398 inline bool
399 atEnd(ModifiedIterator<THost, ModReverse> const & me,
400       TContainer const & /*container*/)
401 {
402             return cargo(me)._atEnd;
403 }
404 
405 template <typename THost>
406 inline bool
407 atEnd(ModifiedIterator<THost, ModReverse> const & me)
408 {
409             return cargo(me)._atEnd;
410 }
411 
412 // --------------------------------------------------------------------------
413 // Function value()                               [ModReverse ModifiedString]
414 // --------------------------------------------------------------------------
415 
416 template <typename THost, typename TPos>
417 inline typename Reference<ModifiedString<THost, ModReverse> >::Type
418 value(ModifiedString<THost, ModReverse> & me, TPos pos)
419 {
420     return value(host(me), (length(host(me)) - 1) - pos);
421 }
422 
423 template <typename THost, typename TPos>
424 inline typename Reference<ModifiedString<THost, ModReverse> const>::Type
425 value(ModifiedString<THost, ModReverse> const & me, TPos pos)
426 {
427     return value(host(me), (length(host(me)) - 1) - pos);
428 }
429 
430 // --------------------------------------------------------------------------
431 // Function begin()                               [ModReverse ModifiedString]
432 // --------------------------------------------------------------------------
433 
434 template < typename THost>
435 inline typename Iterator< ModifiedString<THost, ModReverse> const >::Type
436 begin(ModifiedString<THost, ModReverse> const & me)
437 {
438     typename Iterator< ModifiedString<THost, ModReverse> const >::Type temp_(end(host(me), Rooted()));
439     _copyCargo(temp_, me);
440     goNext(temp_);
441     return temp_;
442 }
443 
444 template < typename THost >
445 inline typename Iterator< ModifiedString<THost, ModReverse> >::Type
446 begin(ModifiedString<THost, ModReverse> & me)
447 {
448     typename Iterator< ModifiedString<THost, ModReverse> >::Type temp_(end(host(me), Rooted()));
449     _copyCargo(temp_, me);
450     goNext(temp_);
451     return temp_;
452 }
453 
454 template < typename THost, typename TTagSpec >
455 inline typename Iterator< ModifiedString<THost, ModReverse> const, Tag<TTagSpec> const >::Type
456 begin(ModifiedString<THost, ModReverse> const & me, Tag<TTagSpec> const)
457 {
458     typename Iterator< ModifiedString<THost, ModReverse> const, Tag<TTagSpec> const >::Type temp_(end(host(me), Rooted()));
459     _copyCargo(temp_, me);
460     goNext(temp_);
461     return temp_;
462 }
463 
464 template < typename THost, typename TTagSpec >
465 inline typename Iterator< ModifiedString<THost, ModReverse>, Tag<TTagSpec> const >::Type
466 begin(ModifiedString<THost, ModReverse> & me, Tag<TTagSpec> const)
467 {
468     typedef typename Iterator< ModifiedString<THost, ModReverse>, Tag<TTagSpec> const >::Type TIterator;
469     TIterator temp_(end(host(me), Rooted()));
470     _copyCargo(temp_, me);
471     goNext(temp_);
472     return temp_;
473 }
474 
475 // --------------------------------------------------------------------------
476 // Function end()                                 [ModReverse ModifiedString]
477 // --------------------------------------------------------------------------
478 
479 template <typename THost >
480 inline typename Iterator<ModifiedString<THost, ModReverse> const >::Type
481 end(ModifiedString<THost, ModReverse> const & me)
482 {
483     typename Iterator<ModifiedString<THost, ModReverse> const >::Type temp_(begin(host(me), Rooted()));
484     _copyCargo(temp_, me);
485     goNext(temp_);
486     return temp_;
487 }
488 
489 template <typename THost >
490 inline typename Iterator<ModifiedString<THost, ModReverse> >::Type
491 end(ModifiedString<THost, ModReverse> & me)
492 {
493     typename Iterator<ModifiedString<THost, ModReverse> >::Type temp_(begin(host(me), Rooted()));
494     _copyCargo(temp_, me);
495     goNext(temp_);
496     return temp_;
497 }
498 
499 template <typename THost, typename TTagSpec >
500 inline typename Iterator<ModifiedString<THost, ModReverse> const, Tag<TTagSpec> const>::Type
501 end(ModifiedString<THost, ModReverse> const & me, Tag<TTagSpec> const)
502 {
503     typename Iterator<ModifiedString<THost, ModReverse> const, Tag<TTagSpec> const >::Type temp_(begin(host(me), Rooted()));
504     _copyCargo(temp_, me);
505     goNext(temp_);
506     return temp_;
507 }
508 
509 template <typename THost, typename TTagSpec >
510 inline typename Iterator<ModifiedString<THost, ModReverse>, Tag<TTagSpec> const>::Type
511 end(ModifiedString<THost, ModReverse> & me, Tag<TTagSpec> const)
512 {
513     typename Iterator<ModifiedString<THost, ModReverse>, Tag<TTagSpec> const >::Type temp_(begin(host(me), Rooted()));
514     _copyCargo(temp_, me);
515     goNext(temp_);
516     return temp_;
517 }
518 
519 // --------------------------------------------------------------------------
520 // Function reverse()
521 // --------------------------------------------------------------------------
522 
523 /*!
524  * @fn reverse
525  * @headerfile <seqan/modifier.h>
526  * @brief Reverse a container in-place.
527  *
528  * @signature void reverse(sequence);
529  * @signature void reverse(stringSet);
530  *
531  * @param[in,out] sequence  The sequence to reverse in-place.
532  * @param[in,out] stringSet The StringSet to reverse in-place.
533  *
534  * @section Remarks
535  *
536  * StringSet objects are reverse element-wise, i.e. the entries are reverse-complemented but their order itself
537  * remains the same.
538  */
539 
540 template <typename TValue>
541 inline bool
542 _reverseDoSequential(TValue size)
543 {
544     return size < (TValue)10000;
545 }
546 
547 inline bool
548 _reverseDoSequential(unsigned char)
549 {
550     return true;
551 }
552 
553 template < typename TSequence, typename TParallelTag >
554 inline void
555 reverse(TSequence & sequence, Tag<TParallelTag> parallelTag)
556 {
557     typedef typename Position<TSequence>::Type              TPos;
558     typedef typename Iterator<TSequence, Standard>::Type    TIter;
559 
560     TIter itBeg = begin(sequence, Standard());
561     TIter itEnd = end(sequence, Standard());
562     Splitter<TPos> splitter(0, length(sequence) / 2, parallelTag);
563 
564     // disable multi-threading if sequence is too small
565     // __uint64 cast is for 8bit size types for which comparison would be always true
566     if (IsSameType<Tag<TParallelTag>, Parallel>::VALUE && _reverseDoSequential(length(sequence)))
567         resize(splitter, 1);
568 
569     // (weese:) We have to cast the result of length to int to circumvent an internal gcc compiler error
570     SEQAN_OMP_PRAGMA(parallel for num_threads((int)length(splitter)) schedule(static))
571     for (int job = 0; job < (int)length(splitter); ++job)
572     {
573         TIter it1 = itBeg + splitter[job];
574         TIter it2 = itEnd - (splitter[job] + 1);
575         TIter it1End = itBeg + splitter[job + 1];
576         for (; it1 != it1End; ++it1, --it2)
577             std::swap(*it1, *it2);
578     }
579 }
580 
581 template < typename TSequence, typename TSpec, typename TParallelTag >
582 inline void
583 reverse(StringSet<TSequence, TSpec> & stringSet, Tag<TParallelTag>)
584 {
585     typedef typename Position<StringSet<TSequence, TSpec> >::Type   TPos;
586     typedef typename MakeSigned<TPos>::Type                         TSPos;
587 
588     TSPos seqCount = length(stringSet);
589     SEQAN_OMP_PRAGMA(parallel for if (IsSameType<Tag<TParallelTag>, Parallel>::VALUE))
590     for (TSPos seqNo = 0; seqNo < seqCount; ++seqNo)
591         reverse(stringSet[seqNo], Serial());
592 }
593 
594 template <typename TValue>
595 inline void
596 reverse(std::list<TValue> & list)
597 {
598     list.reverse();
599 }
600 
601 template < typename TText >
602 inline void
603 reverse(TText & text)
604 {
605     reverse(text, Parallel());
606 }
607 
608 // const variants for segments/modifiers
609 
610 template < typename TText >
611 inline void
612 reverse(TText const & text)
613 {
614     reverse(const_cast<TText &>(text), Parallel());
615 }
616 
617 template < typename TText, typename TParallelTag >
618 inline void
619 reverse(TText const & text, Tag<TParallelTag> parallelTag)
620 {
621     reverse(const_cast<TText &>(text), parallelTag);
622 }
623 
624 
625 // --------------------------------------------------------------------------
626 // Function reverseString()
627 // --------------------------------------------------------------------------
628 
629 template <typename THost>
630 inline ModifiedString<THost, ModReverse>
631 reverseString(THost & host)
632 {
633     return ModifiedString<THost, ModReverse>(host);
634 }
635 
636 }
637 
638 #endif
639