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