1 // ========================================================================== 2 // SeqAn - The Library for Sequence Analysis 3 // ========================================================================== 4 // Copyright (c) 2006-2018, Knut Reinert, FU Berlin 5 // All rights reserved. 6 // 7 // Redistribution and use in source and binary forms, with or without 8 // modification, are permitted provided that the following conditions are met: 9 // 10 // * Redistributions of source code must retain the above copyright 11 // notice, this list of conditions and the following disclaimer. 12 // * Redistributions in binary form must reproduce the above copyright 13 // notice, this list of conditions and the following disclaimer in the 14 // documentation and/or other materials provided with the distribution. 15 // * Neither the name of Knut Reinert or the FU Berlin nor the names of 16 // its contributors may be used to endorse or promote products derived 17 // from this software without specific prior written permission. 18 // 19 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 20 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 // ARE DISCLAIMED. IN NO EVENT SHALL KNUT REINERT OR THE FU BERLIN BE LIABLE 23 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 25 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 26 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH 29 // DAMAGE. 30 // 31 // ========================================================================== 32 // Author: Andreas Gogol-Döring <andreas.doering@mdc-berlin.de> 33 // ========================================================================== 34 // Functions for destructing and several ways of constructing (e.g. copy, 35 // move) values or arrays of values. 36 // ========================================================================== 37 38 // TODO(holtgrew): Order of parameters should be (target1, target2, ..., source1, source2, ...). 39 // TODO(holtgrew): Can we maybe replace at least part with http://www.cplusplus.com/reference/std/memory/? 40 // TODO(holtgrew): The metafunction should go into the alphabet submodule, the functions into the sequence/string module. 41 42 #include <new> 43 44 #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ARRAY_CONSTRUCT_DESTRUCT_H_ 45 #define SEQAN_INCLUDE_SEQAN_BASIC_ARRAY_CONSTRUCT_DESTRUCT_H_ 46 47 namespace seqan { 48 49 // ============================================================================ 50 // Forwards 51 // ============================================================================ 52 53 // ============================================================================ 54 // Tags, Classes, Enums 55 // ============================================================================ 56 57 // ============================================================================ 58 // Metafunctions 59 // ============================================================================ 60 61 // ---------------------------------------------------------------------------- 62 // Metafunction IsSimple 63 // ---------------------------------------------------------------------------- 64 65 // TODO(holtgrew): This has to go to alphabet sub module, storage section, adaption. 66 67 /*! 68 * @mfn IsSimple 69 * @headerfile <seqan/basic.h> 70 * @brief Tests type to be simple. 71 * 72 * @signature IsSimple<T>::Type; 73 * 74 * @tparam T Type that is tested. 75 * 76 * @return Type Either True or False, depending on T being a "POD" type. 77 * 78 * A simple type is a type that does not need constructors to be created, a destructor to be destroyed, and copy 79 * assignment operators or copy constructors to be copied. All POD ("plain old data") types are simple, but some 80 * non-POD types could be simple too, e.g. some specializations of SimpleType. 81 * 82 * @see SimpleType 83 */ 84 85 template <typename T> 86 struct IsSimple_ 87 { 88 typedef False Type; 89 enum { VALUE = 0 }; 90 }; 91 92 // ---------------------------------------------------------------------------- 93 // Metafunction IsSimple 94 // ---------------------------------------------------------------------------- 95 96 template <> struct IsSimple_<bool> { typedef True Type; }; 97 template <> struct IsSimple_<char> { typedef True Type; }; 98 99 template <> struct IsSimple_<unsigned char> { typedef True Type; }; 100 template <> struct IsSimple_<unsigned short> { typedef True Type; }; 101 template <> struct IsSimple_<unsigned int> { typedef True Type; }; 102 template <> struct IsSimple_<unsigned long> { typedef True Type; }; 103 104 template <> struct IsSimple_<signed char> { typedef True Type; }; 105 template <> struct IsSimple_<signed short> { typedef True Type; }; 106 template <> struct IsSimple_<signed int> { typedef True Type; }; 107 template <> struct IsSimple_<signed long> { typedef True Type; }; 108 109 template <> struct IsSimple_<float> { typedef True Type; }; 110 template <> struct IsSimple_<double> { typedef True Type; }; 111 template <> struct IsSimple_<long double> { typedef True Type; }; 112 113 template <typename T> 114 struct IsSimple 115 { 116 typedef typename IsSimple_<T>::Type Type; 117 enum { VALUE = Type::VALUE }; 118 }; 119 120 // user defined types (re-specializations are allowed here) 121 template <> struct IsSimple<wchar_t> { typedef True Type; }; 122 template <> struct IsSimple<int64_t> { typedef True Type; }; 123 template <> struct IsSimple<uint64_t> { typedef True Type; }; 124 125 template <typename T> 126 struct IsSimple<T const> : public IsSimple<T> {}; 127 128 // ---------------------------------------------------------------------------- 129 // Metafunction Value 130 // ---------------------------------------------------------------------------- 131 132 // TODO(holtgrew): This should probably to into sequence module along with this header. 133 134 template <typename TValue> 135 struct Value<TValue *> 136 { 137 typedef TValue Type; 138 }; 139 140 template <typename TValue> 141 struct Value<TValue * const> 142 { 143 typedef TValue Type; 144 }; 145 146 // TODO(holtgrew): Is this still a problem with dropped 2003 support of VC++? 147 148 //The next two metafunctions dont work in VC++ due to a compiler bug. 149 //(the default implementation in common_type.h is called instead) 150 //work-around: convert arrays to pointers. 151 template <typename TValue, size_t SIZE> 152 struct Value<TValue [SIZE]> 153 { 154 typedef TValue Type; 155 }; 156 157 template <typename TValue, size_t SIZE> 158 struct Value<TValue const [SIZE]> 159 { 160 typedef TValue Type; 161 }; 162 163 // ---------------------------------------------------------------------------- 164 // Metafunction Reference 165 // ---------------------------------------------------------------------------- 166 167 // TODO(holtgrew): This should probably to into sequence module along with this header. 168 169 template <typename TValue> 170 struct Reference<TValue *> 171 { 172 typedef TValue & Type; 173 }; 174 175 template <typename TValue> 176 struct Reference<TValue * const> 177 { 178 typedef TValue const & Type; 179 }; 180 181 // ============================================================================ 182 // Functions 183 // ============================================================================ 184 185 // ---------------------------------------------------------------------------- 186 // Function value() for pointers. 187 // ---------------------------------------------------------------------------- 188 189 // TODO(holtgrew): This has to go to iterator module, adaption of pointers to iterators. 190 191 template <typename T> 192 inline T & 193 value(T * me) 194 { 195 return *me; 196 } 197 198 // ---------------------------------------------------------------------------- 199 // Function getValue() for pointers. 200 // ---------------------------------------------------------------------------- 201 202 // TODO(holtgrew): This has to go to iterator module, adaption of pointers to iterators. 203 204 template <typename T> 205 inline T & 206 getValue(T * me) 207 { 208 return value(me); 209 } 210 211 // TODO(holtgrew): All of the helper structs could be replaced by global functions. 212 213 // TODO(holtgrew): First, the generic versions for iterators are defined. Below are the versions for pointers. 214 215 // ---------------------------------------------------------------------------- 216 // Function valueConstruct() using iterators 217 // ---------------------------------------------------------------------------- 218 219 /*! 220 * @fn valueConstruct 221 * @headerfile <seqan/basic.h> 222 * @brief Constructs an object at specified position. 223 * 224 * @signature void valueConstruct(iterator [, param [, move_tag]]); 225 * 226 * @param[in,out] iterator Pointer or iterator to position where the object should be constructed. 227 * @param[in] param Parameter that is forwarded to constructor. 228 * @param[in] moveTag Instance of the move tag. If the tag is specified, it is forwarded to the constructor, 229 * so the constructed object must support move construction. 230 * 231 * The type of the destructed object is the value type of <tt>iterator</tt>. 232 */ 233 234 // Helper code for constructing values behind iterators that do not return 235 // proxies from their value() functions but references. 236 struct ValueConstructor_ 237 { 238 template <typename TIterator> 239 static inline void 240 construct(TIterator it) 241 { 242 typedef typename Value<TIterator>::Type TValue; 243 typedef typename RemoveConst<TValue>::Type TNonConstValue; 244 new( (void*) & value(it) ) TNonConstValue; 245 } 246 247 template <typename TIterator, typename TParam> 248 static inline void 249 construct(TIterator it, 250 TParam && param_) 251 { 252 typedef typename Value<TIterator>::Type TValue; 253 typedef typename RemoveConst<TValue>::Type TNonConstValue; 254 new( (void*) & value(it) ) TNonConstValue(std::forward<TParam>(param_)); 255 } 256 }; 257 258 // Helper code for constructing values behind iterators that return proxies 259 // from their value() function. 260 // 261 // TODO(holtgrew): These implementations are empty and to be overwritten. Should we have dynamic/static asserstions here? 262 struct ValueConstructorProxy_ 263 { 264 template <typename TIterator> 265 static inline void construct(TIterator) {} 266 267 template <typename TIterator, typename TParam> 268 static inline void construct(TIterator, TParam &&) {} 269 }; 270 271 template <typename TIterator> 272 inline void 273 valueConstruct(TIterator it) 274 { 275 typedef typename IfC< 276 IsSameType< 277 typename Value<TIterator>::Type &, 278 typename Reference<TIterator>::Type 279 >::VALUE, 280 // THEN 281 ValueConstructor_, // true, types are equal 282 // ELSE 283 ValueConstructorProxy_ // false, types differ -> value() returns a proxy 284 >::Type TConstructor; 285 286 TConstructor::construct(it); 287 } 288 289 template <typename TIterator, typename TParam> 290 inline void 291 valueConstruct(TIterator it, 292 TParam && param_) 293 { 294 typedef typename IfC< 295 IsSameType< 296 typename Value<TIterator>::Type &, 297 typename Reference<TIterator>::Type 298 >::VALUE, 299 // THEN 300 ValueConstructor_, // true, types are equal 301 // ELSE 302 ValueConstructorProxy_ // false, types differ -> value() returns a proxy 303 >::Type TConstructor; 304 305 TConstructor::construct(it, std::forward<TParam>(param_)); 306 } 307 308 // ---------------------------------------------------------------------------- 309 // Function valueDestruct() using iterators 310 // ---------------------------------------------------------------------------- 311 312 // Helper code for destructing values behind iterators that do not return 313 // proxies from their value() function but references. 314 struct ValueDestructor_ 315 { 316 template <typename TValue> 317 static inline void 318 _destruct(TValue * p) 319 { 320 p->~TValue(); 321 } 322 323 template <typename TIterator> 324 static inline void 325 destruct(TIterator it) 326 { 327 _destruct(&value(it)); 328 } 329 }; 330 331 // Helper code for destructing values behind iterators that return proxies 332 // from their value() function. 333 // 334 // TODO(holtgrew): These implementations are empty and to be overwritten. Should we have dynamic/static asserstions here? 335 struct ValueDestructorProxy_ 336 { 337 template <typename TIterator> 338 static inline void destruct(TIterator) {} 339 }; 340 341 /*! 342 * @fn valueDestruct 343 * @headerfile <seqan/basic.h> 344 * @brief Destroys an object at specified position. 345 * 346 * @signature void valueDestruct(iterator); 347 * 348 * @param[in,out] iterator Pointer or iterator to position where the object should be destructed. 349 * 350 * The type of the constructed object is the value type of <tt>iterator</tt>. 351 */ 352 353 template <typename TIterator> 354 inline void 355 valueDestruct(TIterator it) 356 { 357 typedef typename IfC< 358 IsSameType< 359 typename Value<TIterator>::Type &, 360 typename Reference<TIterator>::Type 361 >::VALUE, 362 // THEN 363 ValueDestructor_, // true, types are equal 364 // ELSE 365 ValueDestructorProxy_ // false, types differ -> value() returns a proxy 366 >::Type TDestructor; 367 368 TDestructor::destruct(it); 369 } 370 371 // ---------------------------------------------------------------------------- 372 // Function arrayConstruct() using iterators 373 // ---------------------------------------------------------------------------- 374 375 /*! 376 * @fn arrayConstruct 377 * @headerfile <seqan/basic.h> 378 * @brief Construct objects in a given memory buffer. 379 * 380 * @signature void arrayConstruct(begin, end[, value]); 381 * 382 * @param[in] begin Iterator to the begin of the range that is to be constructed. 383 * @param[in] end Iterator behind the end of the range. 384 * @param[in] value Argument that is forwarded to the constructor. An appropriate constructor is required. If 385 * <tt>value</tt> is not specified, the default constructor is used. 386 * 387 * The type of the constructed Objects is the value type of <tt>begin</tt> and <tt>end</tt>. 388 */ 389 390 // NOTE(holtgrew): Of course, it does not make sense to declare this in a move version! 391 392 template<typename TIterator1, typename TIterator2> 393 inline void 394 _arrayConstructDefault(TIterator1 begin_, 395 TIterator2 end_) 396 { 397 while (begin_ != end_) 398 { 399 valueConstruct(begin_); 400 ++begin_; 401 } 402 } 403 404 template<typename TIterator1, typename TIterator2> 405 inline void 406 arrayConstruct(TIterator1 begin_, 407 TIterator2 end_) 408 { 409 _arrayConstructDefault(begin_, end_); 410 } 411 412 template<typename TIterator1, typename TIterator2, typename TParam> 413 inline void 414 _arrayConstructDefault(TIterator1 begin_, 415 TIterator2 end_, 416 TParam const & param_) 417 { 418 while (begin_ != end_) 419 { 420 valueConstruct(begin_, param_); 421 ++begin_; 422 } 423 } 424 425 template<typename TIterator1, typename TIterator2, typename TParam> 426 inline void 427 arrayConstruct(TIterator1 begin_, 428 TIterator2 end_, 429 TParam const & param_) 430 { 431 _arrayConstructDefault(begin_, end_, param_); 432 } 433 434 // ---------------------------------------------------------------------------- 435 // Function arrayConstructCopy() using iterators 436 // ---------------------------------------------------------------------------- 437 438 /*! 439 * @fn arrayConstructCopy 440 * @headerfile <seqan/basic.h> 441 * @brief Copy constructs an array of objects into in a given memory buffer. 442 * 443 * @signature void arrayConstructCopy(sourceBegin, sourceEnd, target); 444 * 445 * @param[in] sourceBegin Iterator to the first element of the source range. 446 * @param[in] sourceEnd Iterator behind the last element of the source range. <tt>sourceEnd</tt> should have the same 447 * type as <tt>sourceBegin</tt>. 448 * @param[in] target Pointer to the memory block the new objects will be constructed in. The type of <tt>target</tt> 449 * specifies the type of the constructed objects: If <tt>T*</tt> is the type of <tt>target</tt>, then 450 * the function constructs objects of type <tt>T</tt>. The memory buffer should be large enough to 451 * store <tt>sourceEnd</tt> - <tt>sourceBegin</tt> objects. An appropriate (copy-) constructor that 452 * constructs an target objects given a source object is required. 453 */ 454 455 template<typename TTarget, typename TSource1, typename TSource2> 456 inline void 457 _arrayConstructCopyDefault(TSource1 source_begin, 458 TSource2 source_end, 459 TTarget target_begin) 460 { 461 while (source_begin != source_end) 462 { 463 valueConstruct(target_begin, *source_begin); 464 ++source_begin; 465 ++target_begin; 466 } 467 } 468 469 template<typename TTarget, typename TSource1, typename TSource2> 470 inline void 471 arrayConstructCopy(TSource1 source_begin, 472 TSource2 source_end, 473 TTarget target_begin) 474 { 475 _arrayConstructCopyDefault(source_begin, source_end, target_begin); 476 } 477 478 // ---------------------------------------------------------------------------- 479 // Function arrayConstructMove() using iterators 480 // ---------------------------------------------------------------------------- 481 482 /*! 483 * @fn arrayConstructMove 484 * @headerfile <seqan/basic.h> 485 * @brief Move constructs an array of objects into in a given memory buffer. 486 * 487 * @signature void arrayConstructMove(sourceBegin, sourceEnd, target); 488 * 489 * @param[in] sourceEnd Iterator behind the last element of the source range. <tt>sourceEnd</tt> should have the same 490 * type as <tt>sourceBegin</tt>. 491 * @param[in] sourceBegin Iterator to the first element of the source range. 492 * @param[in] target Pointer to the memory block the new objects will be constructed in. The type of <tt>target</tt> 493 * specifies the type of the constructed objects: If <tt>T*</tt> is the type of <tt>target</tt>, then 494 * the function constructs objects of type <tt>T</tt>. The memory buffer should be large enough to 495 * store <tt>sourceEnd</tt> - <tt>sourceBegin</tt> objects. An appropriate move constructor that 496 * constructs an target objects given a source object is required. 497 */ 498 499 template<typename TTarget, typename TSource1, typename TSource2> 500 inline void 501 _arrayConstructMoveDefault(TSource1 source_begin, 502 TSource2 source_end, 503 TTarget target_begin) 504 { 505 while (source_begin < source_end) 506 { 507 // NOTE(holtgrew): Using value() here, used to be getValue() but 508 // cannot move from const reference or proxy. 509 // valueConstruct(target_begin, value(source_begin), Move()); 510 // TODO(holtgrew): We need a "has move constructor" metafunction to switch between move/copy constructing before we can use the line here. 511 valueConstruct(target_begin, std::move<decltype(*source_begin)>(*source_begin)); 512 ++source_begin; 513 ++target_begin; 514 } 515 } 516 517 template<typename TTarget, typename TSource1, typename TSource2> 518 inline void 519 arrayConstructMove(TSource1 source_begin, 520 TSource2 source_end, 521 TTarget target_begin) 522 { 523 _arrayConstructMoveDefault(source_begin, source_end, target_begin); 524 } 525 526 // ---------------------------------------------------------------------------- 527 // Function arrayDestruct() using iterators 528 // ---------------------------------------------------------------------------- 529 530 /*! 531 * @fn arrayDestruct 532 * @headerfile <seqan/basic.h> 533 * @brief Destroys an array of objects. 534 * 535 * @signature void arrayDestruct(begin, end); 536 * 537 * @param[in] begin Iterator to the begin of the range that is to be destructed. 538 * @param[in] end Iterator behind the end of the range. 539 * 540 * This function does not deallocates the memory. 541 */ 542 543 template<typename TIterator1, typename TIterator2> 544 inline void 545 _arrayDestructDefault(TIterator1 begin_, 546 TIterator2 end_) 547 { 548 while (begin_ != end_) 549 { 550 valueDestruct(begin_); 551 ++begin_; 552 } 553 } 554 555 template<typename TIterator1, typename TIterator2> 556 inline void 557 arrayDestruct(TIterator1 begin_, 558 TIterator2 end_) 559 { 560 _arrayDestructDefault(begin_, end_); 561 } 562 563 // ---------------------------------------------------------------------------- 564 // Function arrayFill() using iterators 565 // ---------------------------------------------------------------------------- 566 567 // TODO(holtgrew): What is the advantage over arrayConstruct() with prototype? 568 569 /*! 570 * @fn arrayFill 571 * @headerfile <seqan/basic.h> 572 * @brief Assigns one object to each element of a range. 573 * 574 * @signature void arrayFill(begin, end, value[, parallelTag]); 575 * 576 * @param[in] begin Iterator to the begin of the range that is to be filled. 577 * @param[in] end Iterator behind the end of the range. 578 * @param[in] value Argument that is assigned to all <tt>count</tt> objects in <tt>array</tt>. 579 * @param[in] parallelTag Tag to enable/disable parallelism. Types: Serial, Parallel 580 * 581 * All objects <tt>target_begin[0]</tt> to <tt>target_begin[count-1]</tt> are set to <tt>value</tt>. 582 */ 583 584 // TODO(holtgrew): Redirects to fill_n. What are the exact semantics here? Do the array elements have to be initialized already? fill_n uses assignment, not copy construction! 585 586 template <typename TIterator, typename TValue> 587 inline void 588 arrayFill(TIterator begin_, 589 TIterator end_, 590 TValue const & value) 591 { 592 std::fill_n(begin_, end_ - begin_, value); 593 } 594 595 template <typename TIterator, typename TValue> 596 inline void 597 arrayFill(TIterator begin_, 598 TIterator end_, 599 TValue const & value, 600 Serial) 601 { 602 arrayFill(begin_, end_, value); 603 } 604 605 // ---------------------------------------------------------------------------- 606 // Function arrayCopyForward() using iterators 607 // ---------------------------------------------------------------------------- 608 609 /*! 610 * @fn arrayCopyForward 611 * @headerfile <seqan/basic.h> 612 * @brief Copies a range of objects into another range of objects starting from the first element. 613 * 614 * @signature void arrayCopyForward(sourceBegin, sourceEnd, target); 615 * 616 * @param[in] sourceEnd Iterator behind the last element of the source array. <tt>sourceEnd</tt> must have the same type 617 * as <tt>sourceBegin</tt>. 618 * @param[in] sourceBegin Iterator to the first element of the source array. 619 * @param[in] target Iterator to the first element of the target array. The target capacity should be at least as 620 * long as the source range. 621 * 622 * Be careful if source and target range overlap, because in this case some source elements could be accidently 623 * overwritten before they are copied. 624 * 625 * If there is no need for the source elements to persist, consider to use arrayMoveForward instead to improve 626 * performance. 627 */ 628 629 template<typename TTarget, typename TSource1, typename TSource2> 630 inline void 631 _arrayCopyForwardDefault(TSource1 source_begin, 632 TSource2 source_end, 633 TTarget target_begin) 634 { 635 std::copy(source_begin, source_end, target_begin); 636 } 637 638 template<typename TTarget, typename TSource1, typename TSource2> 639 inline void 640 arrayCopyForward(TSource1 source_begin, 641 TSource2 source_end, 642 TTarget target_begin) 643 { 644 _arrayCopyForwardDefault(source_begin, source_end, target_begin); 645 } 646 647 // ---------------------------------------------------------------------------- 648 // Function arrayCopyBackward() using iterators 649 // ---------------------------------------------------------------------------- 650 651 /*! 652 * @fn arrayCopyBackward 653 * @headerfile <seqan/basic.h> 654 * @brief Copies a range of objects into another range of objects starting from the last element. 655 * 656 * @signature void arrayCopyBackward(source_begin, source_end, target); 657 * 658 * @param[in] sourceBegin Iterator to the first element of the source array. 659 * @param[in] sourceEnd Iterator behind the last element of the source array. <tt>sourceEnd</tt> must have the same type 660 * as <tt>source_begin</tt>. 661 * @param[in] target Iterator to the first element of the target array. The target capacity should be at least as 662 * long as the source range. 663 * 664 * Be careful if source and target range overlap, because in this case some source elements could be accidently 665 * overwritten before they are moved. 666 * 667 * If source and target do not overlap, consider to use the function arrayCopyForward instead that is faster in some 668 * cases. 669 * 670 * If there is no need for the source elements to persist, consider to use arrayMoveBackward instead to improve 671 * performance. 672 * 673 * The semantic of this function's argument <tt>target</tt> differ from the arguments of <tt>std::copy_backward</tt>. 674 */ 675 676 template<typename TTarget, typename TSource1, typename TSource2> 677 inline void 678 _arrayCopyBackwardDefault(TSource1 source_begin, 679 TSource2 source_end, 680 TTarget target_begin) 681 { 682 std::copy_backward(source_begin, source_end, target_begin + (source_end - source_begin)); 683 } 684 685 template<typename TTarget, typename TSource1, typename TSource2> 686 inline void 687 arrayCopyBackward(TSource1 source_begin, 688 TSource2 source_end, 689 TTarget target_begin) 690 { 691 _arrayCopyBackwardDefault(source_begin, source_end, target_begin); 692 } 693 694 // ---------------------------------------------------------------------------- 695 // Function arrayCopy() using iterators 696 // ---------------------------------------------------------------------------- 697 698 /*! 699 * @fn arrayCopy 700 * 701 * @headerfile <seqan/basic.h> 702 * 703 * @brief Copies a range of objects into another range of objects. 704 * 705 * @signature void arrayCopy(sourceBegin, sourceEnd, target); 706 * 707 * @param[in] sourceEnd Iterator behind the last element of the source range. <tt>sourceEnd</tt> must have the same type 708 * as <tt>sourceBegin</tt>. 709 * @param[in] sourceBegin Iterator to the first element of the source range. 710 * @param[in] target Iterator to the first element of the target range.The target capacity should be at least as long 711 * as the source range. 712 * 713 * If source and target range do not overlap, consider to use arrayCopyForward instead to improve performance. 714 * 715 * If there is no need for the source elements to persist, consider to use arrayMoveForward instead to improve 716 * performance. 717 */ 718 719 template<typename TTarget, typename TSource1, typename TSource2> 720 inline void arrayCopy(TSource1 source_begin, 721 TSource2 source_end, 722 TTarget target_begin) 723 { 724 if (target_begin <= source_begin) 725 arrayCopyForward(source_begin, source_end, target_begin); 726 else 727 arrayCopyBackward(source_begin, source_end, target_begin); 728 } 729 730 // ---------------------------------------------------------------------------- 731 // Function arrayMoveForward() using iterators 732 // ---------------------------------------------------------------------------- 733 734 /*! 735 * @fn arrayMoveForward 736 * @headerfile <seqan/basic.h> 737 * @brief Moves a range of objects into another range of objects starting from the first element. 738 * 739 * @signature void arrayMoveForward(sourceBegin, sourceEnd, target); 740 * 741 * @param[in] sourceEnd Iterator behind the last element of the source array. <tt>sourceEnd</tt> must have the same type 742 * as <tt>sourceBegin</tt>. 743 * @param[in] sourceBegin Iterator to the first element of the source array. 744 * @param[in] target Iterator to the first element of the target array. The target capacity should be at least as 745 * long as the source range. 746 * 747 * The function possibly clears (but does not destroy) the source elements. If source elements must persist, consider 748 * to use arrayCopyForward instead. 749 * 750 * Be careful if source and target range overlap, because in this case some source elements could be accidently 751 * overwritten before they are moved. 752 */ 753 754 template<typename TTarget, typename TSource1, typename TSource2> 755 inline void 756 _arrayMoveForwardDefault(TSource1 source_begin, 757 TSource2 source_end, 758 TTarget target_begin) 759 { 760 std::move(source_begin, source_end, target_begin); 761 } 762 763 template<typename TTarget, typename TSource1, typename TSource2> 764 inline void 765 arrayMoveForward(TSource1 source_begin, 766 TSource2 source_end, 767 TTarget target_begin) 768 { 769 _arrayMoveForwardDefault(source_begin, source_end, target_begin); 770 } 771 772 // ---------------------------------------------------------------------------- 773 // Function arrayMoveBackward() using iterators 774 // ---------------------------------------------------------------------------- 775 776 /*! 777 * @fn arrayMoveBackward 778 * @headerfile <seqan/basic.h> 779 * @brief Moves a range of objects into another range of objects starting from the last element. 780 * 781 * @signature void arrayMoveBackward(sourceBegin, sourceEnd, target); 782 * 783 * @param[in] sourceEnd Iterator behind the last element of the source array. <tt>sourceEnd</tt> must have the same type 784 * as <tt>sourceBegin</tt>. 785 * @param[in] sourceBegin Iterator to the first element of the source array. 786 * @param[in] target Iterator to the first element of the target array.The target capacity should be at least as long 787 * as the source range. 788 * 789 * The function possibly clears (but does not destroy) the source elements. If source elements must persist, consider 790 * to use arrayCopyBackward instead. 791 * 792 * Be careful if source and target range overlap, because in this case some source elements could be accidently 793 * overwritten before they are moved. 794 * 795 * If source and target do not overlap, consider to use the function arrayMoveForward instead that is faster in some 796 * cases. 797 * 798 * The semantic of this function's argument <tt>target</tt> differ from the arguments of <tt>std::copy_backward</tt>. 799 */ 800 801 template<typename TTarget, typename TSource1, typename TSource2> 802 inline void 803 _arrayMoveBackwardDefault(TSource1 source_begin, 804 TSource2 source_end, 805 TTarget target_begin) 806 { 807 std::move_backward(source_begin, source_end, target_begin + (source_end - source_begin)); 808 } 809 810 template<typename TTarget, typename TSource1, typename TSource2> 811 inline void 812 arrayMoveBackward(TSource1 source_begin, 813 TSource2 source_end, 814 TTarget target_begin) 815 { 816 _arrayMoveBackwardDefault(source_begin, source_end, target_begin); 817 } 818 819 // ---------------------------------------------------------------------------- 820 // Function arrayMove using iterators 821 // ---------------------------------------------------------------------------- 822 823 /*! 824 * @fn arrayMove 825 * @headerfile <seqan/basic.h> 826 * @brief Moves a range of objects into another range of objects. 827 * 828 * @signature void arrayMove(sourceBegin, sourceEnd, target); 829 * 830 * @param[in] sourceBegin Iterator to the first element of the source range. 831 * @param[in] sourceEnd Iterator behind the last element of the source range. <tt>sourceEnd</tt> must have the same type 832 * as <tt>sourceBegin</tt>. 833 * @param[in] target Iterator to the first element of the target range. The target capacity should be at least as 834 * long as the source range. 835 * 836 * The function possibly clears (but does not destroy) the source elements. If source elements must persist, consider 837 * to use arrayCopy instead. 838 * 839 * If source and target range do not overlap, consider to use arrayMoveForward instead to improve performance. 840 * 841 * Don't confuse this function with the standard <tt>move</tt> function that resembles arrayCopy. 842 */ 843 844 template<typename TTarget, typename TSource1, typename TSource2> 845 inline void 846 arrayMove(TSource1 source_begin, 847 TSource2 source_end, 848 TTarget target_begin) 849 { 850 if (target_begin <= source_begin) 851 arrayMoveForward(source_begin, source_end, target_begin); 852 else 853 arrayMoveBackward(source_begin, source_end, target_begin); 854 } 855 856 // ---------------------------------------------------------------------------- 857 // Function arrayClearSpace() using iterators 858 // ---------------------------------------------------------------------------- 859 860 /*! 861 * @fn arrayClearSpace 862 * @headerfile <seqan/basic.h> 863 * @brief Destroys the begin of an array and keeps the rest. 864 * 865 * @signature void arrayClearSpace(arrBegin, arrLength, keepFrom, moveTo); 866 * 867 * @param[in] arrBegin Pointer to the first element of the array. 868 * @param[in] keepFrom Offset of the first object that will be kept. 869 * @param[in] arrLength Length of the array. 870 * @param[in] moveTo Offset the first kept object will get at the end of the function. 871 * 872 * The objects <tt>arr[keep_from]</tt> to <tt>arr[arr_length-1]</tt> are moved to the area beginning at positions 873 * <tt>move_to</tt>. All objects in <tt>arr[0]</tt> to <tt>arr[keep_from-1]</tt> are destroyed. After this function, the 874 * first <tt>move_to</tt> positions of the array are free and dont contain objects. 875 * 876 * The array must have at least enough space to store <tt>arr_length + move_to - keep_from</tt> objects. 877 * 878 * The objects from <tt>arr[0]</tt> to <tt>arr[array_length-1]</tt> have to be initialized/constructed, arrays beyond 879 * <tt>arr[array_length-1]</tt> are assumed not to be constructed. If this assumption is violated, memory might leak. 880 */ 881 882 // TODO(holtgrew): The feature that the range [0, array_begin) is deleted is used nowhere. Can this be removed to simplify behaviour? 883 884 template <typename TIterator> 885 void _arrayClearSpaceDefault(TIterator array_begin, 886 size_t array_length, 887 size_t keep_from, 888 size_t move_to) 889 { 890 if (keep_from == array_length) { 891 // In the simplest case, we only destruct elements. 892 arrayDestruct(array_begin, array_begin + array_length); 893 return; 894 } 895 896 // Otherwise, we will perform the destruction & movement. 897 SEQAN_ASSERT_LT(keep_from, array_length); 898 if (keep_from == move_to) { 899 // Case 1: No movement, just destroy elements. 900 arrayDestruct(array_begin, array_begin + move_to); 901 return; 902 } else if (keep_from < move_to) { 903 // Case 2: Move to the right. 904 if (array_length > move_to) { 905 // Case 2a: Moving right of array_length, i.e. we can move a part 906 // of the objects and have to move-construct the rest. 907 size_t middle = array_length - (move_to - keep_from); 908 arrayConstructMove(array_begin + middle, array_begin + array_length, array_begin + array_length); 909 arrayMove(array_begin + keep_from, array_begin + middle, array_begin + move_to); 910 arrayDestruct(array_begin, array_begin + move_to); 911 } else { 912 // Case 2b: We have to move-construct all target objects. 913 arrayConstructMove(array_begin + keep_from, array_begin + array_length, array_begin + move_to); 914 arrayDestruct(array_begin, array_begin + array_length); 915 } 916 } else { 917 // Case 3: Move to the left. 918 arrayMove(array_begin + keep_from, array_begin + array_length, array_begin + move_to); 919 arrayDestruct(array_begin, array_begin + move_to); 920 arrayDestruct(array_begin + array_length - (keep_from - move_to), array_begin + array_length); 921 } 922 } 923 924 template <typename TIterator> 925 void arrayClearSpace(TIterator array_begin, 926 size_t array_length, 927 size_t keep_from, 928 size_t move_to) 929 { 930 _arrayClearSpaceDefault(array_begin, array_length, keep_from, move_to); 931 } 932 933 // ---------------------------------------------------------------------------- 934 // Function arrayConstruct() using pointers 935 // ---------------------------------------------------------------------------- 936 937 template<typename TIterator> 938 inline void 939 _arrayConstructPointer(TIterator, 940 TIterator, 941 True) 942 { 943 //nothing to do 944 } 945 946 template<typename TIterator> 947 inline void 948 _arrayConstructPointer(TIterator begin_, 949 TIterator end_, 950 False) 951 { 952 _arrayConstructDefault(begin_, end_); 953 } 954 955 template <typename TValue> 956 inline void 957 arrayConstruct(TValue * begin_, 958 TValue * end_) 959 { 960 _arrayConstructPointer(begin_, end_, typename IsSimple<TValue>::Type() ); 961 } 962 963 template <typename TValue, typename TParam> 964 inline void 965 _arrayConstructPointer(TValue * begin_, 966 TValue * end_, 967 TParam const & param_, 968 True) 969 { 970 arrayFill(begin_, end_, static_cast<TValue>(param_)); 971 } 972 973 template <typename TValue, typename TParam> 974 inline void 975 _arrayConstructPointer(TValue * begin_, 976 TValue * end_, 977 TParam const & param_, 978 False) 979 { 980 _arrayConstructDefault(begin_, end_, param_); 981 } 982 983 template<typename TValue, typename TParam> 984 inline void 985 arrayConstruct(TValue * begin_, 986 TValue * end_, 987 TParam const & param_) 988 { 989 _arrayConstructPointer(begin_, end_, param_, typename IsSimple<TValue>::Type()); 990 } 991 992 // ---------------------------------------------------------------------------- 993 // Function arrayConstructCopy() using pointers 994 // ---------------------------------------------------------------------------- 995 996 template<typename TValueSource, typename TValueTarget> 997 inline void 998 _arrayConstructCopyPointer(TValueSource * source_begin, 999 TValueSource * source_end, 1000 TValueTarget * target_begin, 1001 True) 1002 { 1003 arrayCopyForward(source_begin, source_end, target_begin); 1004 } 1005 1006 template<typename TValueSource, typename TValueTarget> 1007 inline void 1008 _arrayConstructCopyPointer(TValueSource * source_begin, 1009 TValueSource * source_end, 1010 TValueTarget const* target_begin, 1011 True) 1012 { 1013 arrayCopyForward(source_begin, source_end, const_cast<TValueTarget *>(target_begin)); 1014 } 1015 1016 template<typename TValueSource, typename TValueTarget> 1017 inline void 1018 _arrayConstructCopyPointer(TValueSource * source_begin, 1019 TValueSource * source_end, 1020 TValueTarget * target_begin, 1021 False) 1022 { 1023 _arrayConstructCopyDefault(source_begin, source_end, target_begin); 1024 } 1025 template<typename TValueSource, typename TValueTarget> 1026 inline void 1027 arrayConstructCopy(TValueSource * source_begin, 1028 TValueSource * source_end, 1029 TValueTarget * target_begin) 1030 { 1031 _arrayConstructCopyPointer(source_begin, source_end, target_begin, typename IsSimple<TValueTarget>::Type() ); 1032 } 1033 1034 // ---------------------------------------------------------------------------- 1035 // Function arrayConstructMove() using pointers 1036 // ---------------------------------------------------------------------------- 1037 1038 template<typename TValue> 1039 inline void 1040 _arrayConstructMovePointer(TValue * source_begin, 1041 TValue * source_end, 1042 TValue * target_begin, 1043 True) 1044 { 1045 arrayMoveForward(source_begin, source_end, target_begin); 1046 } 1047 1048 template<typename TValue> 1049 inline void 1050 _arrayConstructMovePointer(TValue * source_begin, 1051 TValue * source_end, 1052 TValue * target_begin, 1053 False) 1054 { 1055 _arrayConstructMoveDefault(source_begin, source_end, target_begin); 1056 } 1057 1058 template<typename TValue> 1059 inline void 1060 arrayConstructMove(TValue * source_begin, 1061 TValue * source_end, 1062 TValue * target_begin) 1063 { 1064 _arrayConstructMovePointer(source_begin, source_end, target_begin, typename IsSimple<TValue>::Type() ); 1065 } 1066 1067 // ---------------------------------------------------------------------------- 1068 // Function arrayDestruct() using pointers 1069 // ---------------------------------------------------------------------------- 1070 1071 template<typename TValue> 1072 inline void 1073 _arrayDestructPointer(TValue * /*begin_*/, 1074 TValue * /*end_*/, 1075 True) 1076 { 1077 //do nothing 1078 } 1079 1080 template<typename TValue> 1081 inline void 1082 _arrayDestructPointer(TValue * begin_, 1083 TValue * end_, 1084 False) 1085 { 1086 _arrayDestructDefault(begin_, end_); 1087 } 1088 1089 template<typename TValue> 1090 inline void 1091 arrayDestruct(TValue * begin_, 1092 TValue * end_) 1093 { 1094 _arrayDestructPointer(begin_, end_, typename IsSimple<TValue>::Type() ); 1095 } 1096 1097 // ---------------------------------------------------------------------------- 1098 // Function arrayFill() using pointers 1099 // ---------------------------------------------------------------------------- 1100 1101 // TODO(holtgrew): Missing? 1102 1103 //no specializiation for pointer to simple 1104 1105 // ---------------------------------------------------------------------------- 1106 // Function arrayCopyBackward() using pointers 1107 // ---------------------------------------------------------------------------- 1108 1109 template<typename TValue> 1110 inline void 1111 _arrayCopyForwardPointer(TValue * source_begin, 1112 TValue * source_end, 1113 TValue * target_begin, 1114 True) 1115 { 1116 std::memmove(target_begin, source_begin, (source_end - source_begin) * sizeof(TValue)); 1117 } 1118 1119 template<typename TValue> 1120 inline void 1121 _arrayCopyForwardPointer(TValue * source_begin, 1122 TValue * source_end, 1123 TValue * target_begin, 1124 False) 1125 { 1126 _arrayCopyForwardDefault(source_begin, source_end, target_begin); 1127 } 1128 1129 template<typename TValue> 1130 inline void 1131 arrayCopyForward(TValue * source_begin, 1132 TValue * source_end, 1133 TValue * target_begin) 1134 { 1135 _arrayCopyForwardPointer(source_begin, source_end, target_begin, typename IsSimple<TValue>::Type() ); 1136 } 1137 1138 template <typename TValue> 1139 inline void 1140 _arrayCopyBackwardPointer(TValue * source_begin, 1141 TValue * source_end, 1142 TValue * target_begin, 1143 True) 1144 { 1145 std::memmove(target_begin, source_begin, (source_end - source_begin) * sizeof(TValue)); 1146 } 1147 1148 template <typename TValue> 1149 inline void 1150 _arrayCopyBackwardPointer(TValue * source_begin, 1151 TValue * source_end, 1152 TValue * target_begin, 1153 False) 1154 { 1155 _arrayCopyBackwardDefault(source_begin, source_end, target_begin); 1156 } 1157 1158 template<typename TValue> 1159 inline void 1160 arrayCopyBackward(TValue * source_begin, 1161 TValue * source_end, 1162 TValue * target_begin) 1163 { 1164 _arrayCopyBackwardPointer(source_begin, source_end, target_begin, typename IsSimple<TValue>::Type() ); 1165 } 1166 1167 // ---------------------------------------------------------------------------- 1168 // Function arrayMoveBackward() using pointers 1169 // ---------------------------------------------------------------------------- 1170 1171 template<typename TValue> 1172 inline void 1173 _arrayMoveForwardPointer(TValue * source_begin, 1174 TValue * source_end, 1175 TValue * target_begin, 1176 True) 1177 { 1178 std::memmove(target_begin, source_begin, (source_end - source_begin) * sizeof(TValue)); 1179 } 1180 1181 template<typename TValue> 1182 inline void 1183 _arrayMoveForwardPointer(TValue * source_begin, 1184 TValue * source_end, 1185 TValue * target_begin, 1186 False) 1187 { 1188 _arrayMoveForwardDefault(source_begin, source_end, target_begin); 1189 } 1190 1191 template<typename TValue> 1192 inline void 1193 arrayMoveForward(TValue * source_begin, 1194 TValue * source_end, 1195 TValue * target_begin) 1196 { 1197 _arrayMoveForwardPointer(source_begin, source_end, target_begin, typename IsSimple<TValue>::Type() ); 1198 } 1199 1200 template <typename TValue> 1201 inline void 1202 _arrayMoveBackwardPointer(TValue * source_begin, 1203 TValue * source_end, 1204 TValue * target_begin, 1205 True) 1206 { 1207 std::memmove(target_begin, source_begin, (source_end - source_begin) * sizeof(TValue)); 1208 } 1209 template <typename TValue> 1210 inline void 1211 _arrayMoveBackwardPointer(TValue * source_begin, 1212 TValue * source_end, 1213 TValue * target_begin, 1214 False) 1215 { 1216 _arrayMoveBackwardDefault(source_begin, source_end, target_begin); 1217 } 1218 1219 template<typename TValue> 1220 inline void 1221 arrayMoveBackward(TValue * source_begin, 1222 TValue * source_end, 1223 TValue * target_begin) 1224 { 1225 _arrayMoveBackwardPointer(source_begin, source_end, target_begin, typename IsSimple<TValue>::Type() ); 1226 } 1227 1228 // ---------------------------------------------------------------------------- 1229 // Function arrayClearSpace() using pointers 1230 // ---------------------------------------------------------------------------- 1231 1232 // clearSpace() on simple type using pointers. 1233 template <typename TValue> 1234 inline void 1235 _arrayClearSpacePointer(TValue * array_begin, 1236 size_t array_length, 1237 size_t keep_from, 1238 size_t move_to, 1239 True const & /*isSimple*/) 1240 { 1241 if (keep_from == move_to) return; 1242 // TODO(holtgrew): arrayCopy is more appropriate here since we are dealing with the IsSimple case. 1243 arrayMove(array_begin + keep_from, array_begin + array_length, array_begin + move_to); 1244 } 1245 1246 // clearSpace() on non-simple type using pointers. 1247 template <typename TValue> 1248 inline void 1249 _arrayClearSpacePointer(TValue * array_begin, 1250 size_t array_length, 1251 size_t keep_from, 1252 size_t move_to, 1253 False const & /*isSimple*/) 1254 { 1255 _arrayClearSpaceDefault(array_begin, array_length, keep_from, move_to); 1256 } 1257 1258 template <typename TValue> 1259 void arrayClearSpace(TValue * array_begin, 1260 size_t array_length, 1261 size_t keep_from, 1262 size_t move_to) 1263 { 1264 _arrayClearSpacePointer(array_begin, array_length, keep_from, move_to, typename IsSimple<TValue>::Type()); 1265 } 1266 1267 1268 } // namespace seqan 1269 1270 #endif // #ifndef SEQAN_INCLUDE_SEQAN_BASIC_ARRAY_CONSTRUCT_DESTRUCT_H_ 1271