SeqAn-1.1/seqan/basic/basic_alphabet_interface.h

   1  /*==========================================================================
   2                 SeqAn - The Library for Sequence Analysis
   3                           http://www.seqan.de
   4  ============================================================================
   5   Copyright (C) 2007
   6
   7   This library is free software; you can redistribute it and/or
   8   modify it under the terms of the GNU Lesser General Public
   9   License as published by the Free Software Foundation; either
  10   version 3 of the License, or (at your option) any later version.
  11
  12   This library is distributed in the hope that it will be useful,
  13   but WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17  ============================================================================
  18   $Id: basic_alphabet_interface.h,v 1.1 2008/08/25 16:20:01 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_BASIC_ALPHABET_INTERFACE_H
  22 #define SEQAN_HEADER_BASIC_ALPHABET_INTERFACE_H
  23
  24 #include <new>
  25
  26 namespace SEQAN_NAMESPACE_MAIN
  27 {
  28 //////////////////////////////////////////////////////////////////////////////
  29 //IsSimple
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 /**
  33 .Metafunction.IsSimple:
  34 ..summary:Tests type to be simple.
  35 ..signature:IsSimple<T>::Type
  36 ..param.T:Type that is tested.
  37 ..returns.param.Type:@Tag.Logical Values.True@, if $T$ is a simple type, @Tag.Logical Values.False@ otherwise.
  38 ...default:@Tag.Logical Values.False@
  39 ..remarks:A simple type is a type that does not need constructors to be created,
  40 a destructor to be destroyed, and copy assignment operators or copy constructors
  41 to be copied. All POD ("plain old data") types are simple, but some
  42 non-POD types could be simple too, e.g. some specializations of @Class.SimpleType@.
  43 ..see:Class.SimpleType
  44 */
  45
  46 template <typename T>
  47 struct _IsSimple {
  48         typedef False Type;
  49 };
  50
  51 template <typename T>
  52 struct IsSimple:
  53         public _IsSimple<T> {};
  54 template <typename T>
  55 struct IsSimple<T const>:
  56         public IsSimple<T> {};
  57
  58 //////////////////////////////////////////////////////////////////////////////
  59 //very basic Alphabets
  60
  61 typedef char Ascii;
  62 typedef unsigned char Byte;
  63 typedef wchar_t Unicode;
  64
  65 //////////////////////////////////////////////////////////////////////////////
  66
  67 /**
  68 .Function.valueConstruct:
  69 ..cat:Content Manipulation
  70 ..summary:Constructs an object at specified position.
  71 ..signature:valueConstruct(iterator [, param [, move_tag] ])
  72 ..param.iterator:Pointer or iterator to position where the object should be constructed.
  73 ..param.param:Parameter that is forwarded to constructor. (optional)
  74 ..param.move_tag:Instance of the @Tag.Move Switch.move switch tag@. (optional)
  75 ...remarks:If the @Tag.Move Switch.move switch tag@ is specified, it is forwarded to the constructor,
  76 so the constructed object must support move construction.
  77 ..remarks:The type of the destructed object is the @Metafunction.Value.value type@ of $iterator$.
  78 */
  79
  80 struct _ValueConstructor
  81 {
  82         template <typename TIterator>
  83         static inline void
  84         construct(TIterator it)
  85         {
  86                 typedef typename Value<TIterator>::Type TValue;
  87                 new( & value(it) ) TValue;
  88         }
  89
  90         template <typename TIterator, typename TParam>
  91         static inline void
  92         construct(TIterator it,
  93                           TParam const & param_)
  94         {
  95                 typedef typename Value<TIterator>::Type TValue;
  96                 new( & value(it) ) TValue(param_);
  97         }
  98
  99         template <typename TIterator, typename TParam>
 100         static inline void
 101         construct(TIterator it,
 102                           TParam const & param_,
 103                           Move tag)
 104         {
 105                 typedef typename Value<TIterator>::Type TValue;
 106                 new( & value(it) ) TValue(param_, tag);
 107         }
 108 };
 109
 110 struct _ValueConstructorProxy
 111 {
 112         template <typename TIterator>
 113         static inline void construct(TIterator) {}
 114
 115         template <typename TIterator, typename TParam>
 116         static inline void construct(TIterator, TParam const &) {}
 117
 118         template <typename TIterator, typename TParam>
 119         static inline void construct(TIterator, TParam const &, Move) {}
 120 };
 121
 122 //____________________________________________________________________________
 123
 124 struct _ValueDestructor
 125 {
 126         template <typename TIterator>
 127         static inline void
 128         destruct(TIterator it)
 129         {
 130                 typedef typename Value<TIterator>::Type TValue;
 131                 value(it).~TValue();
 132         }
 133 };
 134 struct _ValueDestructorProxy
 135 {
 136         template <typename TIterator>
 137         static inline void destruct(TIterator) {}
 138 };
 139
 140 //____________________________________________________________________________
 141
 142 template <typename TIterator>
 143 inline void
 144 valueConstruct(TIterator it)
 145 {
 146 SEQAN_CHECKPOINT
 147         typedef typename IF<
 148                 TYPECMP<
 149                         typename Value<TIterator>::Type &,
 150                         typename Reference<TIterator>::Type
 151                 >::VALUE,
 152         // THEN
 153                 _ValueConstructor,                      // true,  types are equal
 154         // ELSE
 155                 _ValueConstructorProxy          // false, types differ -> value() returns a proxy
 156         >::Type TConstructor;
 157
 158         TConstructor::construct(it);
 159 }
 160
 161 template <typename TIterator, typename TParam>
 162 inline void
 163 valueConstruct(TIterator it,
 164                            TParam const & param_)
 165 {
 166 SEQAN_CHECKPOINT
 167         typedef typename IF<
 168                 TYPECMP<
 169                         typename Value<TIterator>::Type &,
 170                         typename Reference<TIterator>::Type
 171                 >::VALUE,
 172         // THEN
 173                 _ValueConstructor,                      // true,  types are equal
 174         // ELSE
 175                 _ValueConstructorProxy          // false, types differ -> value() returns a proxy
 176         >::Type TConstructor;
 177
 178         TConstructor::construct(it, param_);
 179 }
 180
 181 template <typename TIterator, typename TParam>
 182 inline void
 183 valueConstruct(TIterator it,
 184                            TParam const & param_,
 185                            Move tag)
 186 {
 187 SEQAN_CHECKPOINT
 188         typedef typename IF<
 189                 TYPECMP<
 190                         typename Value<TIterator>::Type &,
 191                         typename Reference<TIterator>::Type
 192                 >::VALUE,
 193         // THEN
 194                 _ValueConstructor,                      // true,  types are equal
 195         // ELSE
 196                 _ValueConstructorProxy          // false, types differ -> value() returns a proxy
 197         >::Type TConstructor;
 198
 199         TConstructor::construct(it, param_, tag);
 200 }
 201
 202 //////////////////////////////////////////////////////////////////////////////
 203
 204 /**
 205 .Function.valueDestruct:
 206 ..cat:Content Manipulation
 207 ..summary:Destoys an object at specified position.
 208 ..signature:valueDestruct(iterator)
 209 ..param.iterator:Pointer or iterator to position where the object should be constructed.
 210 ..remarks:The type of the constructed object is the @Metafunction.Value.value type@ of $iterator$.
 211 ..see:Function.valueConstruct
 212 */
 213 template <typename TIterator>
 214 inline void
 215 valueDestruct(TIterator it)
 216 {
 217 SEQAN_CHECKPOINT
 218         typedef typename IF<
 219                 TYPECMP<
 220                         typename Value<TIterator>::Type &,
 221                         typename Reference<TIterator>::Type
 222                 >::VALUE,
 223         // THEN
 224                 _ValueDestructor,                       // true,  types are equal
 225         // ELSE
 226                 _ValueDestructorProxy           // false, types differ -> value() returns a proxy
 227         >::Type TDestructor;
 228
 229         TDestructor::destruct(it);
 230 }
 231
 232
 233 //////////////////////////////////////////////////////////////////////////////
 234
 235 /**
 236 .Function.valueConstructMove:
 237 ..cat:Content Manipulation
 238 ..summary:Move constructs an object at specified position.
 239 ..signature:valueConstructMove(iterator, param)
 240 ..param.iterator:Pointer or iterator to position where the object should be constructed.
 241 ..param.param:Parameter that is moved to the new constructed object.
 242 ..remarks:The type of the destructed object is the @Metafunction.Value.value type@ of $iterator$.
 243 ..remarks:The default implementation just calls @Function.valueConstruct@.
 244 */
 245 template <typename TIterator, typename TValue>
 246 inline void
 247 valueConstructMove(TIterator it, TValue const & value)
 248 {
 249         valueConstruct(it, value);
 250 }
 251
 252
 253 //////////////////////////////////////////////////////////////////////////////
 254 //////////////////////////////////////////////////////////////////////////////
 255 //////////////////////////////////////////////////////////////////////////////
 256 //arrayConstruct
 257 //////////////////////////////////////////////////////////////////////////////
 258 /**
 259 .Function.arrayConstruct:
 260 ..cat:Array Handling
 261 ..summary:Construct objects in a given memory buffer.
 262 ..signature:arrayConstruct(begin, end [, value])
 263 ..param.begin:Iterator to the begin of the range that is to be constructed.
 264 ..param.end:Iterator behind the end of the range.
 265 ..param.value:Argument that is forwarded to the constructor. (optional)
 266 ...text:An appropriate constructor is required.
 267 If $value$ is not specified, the default constructor is used.
 268 ..remarks:The type of the constructed Objects is the @Metafunction.Value.value type@
 269 of $begin$ and $end$.
 270 ..see:Function.arrayDestruct
 271 ..see:Function.arrayConstructCopy
 272 ..see:Function.arrayFill
 273 ..see:Class.SimpleType
 274 ..see:Function.valueConstruct
 275 */
 276 template<typename TIterator1, typename TIterator2>
 277 inline void
 278 _arrayConstruct_Default(TIterator1 begin_,
 279                                                 TIterator2 end_)
 280 {
 281 SEQAN_CHECKPOINT
 282         while (begin_ != end_)
 283         {
 284                 valueConstruct(begin_);
 285                 ++begin_;
 286         }
 287 }
 288 template<typename TIterator1, typename TIterator2>
 289 inline void
 290 arrayConstruct(TIterator1 begin_,
 291                            TIterator2 end_)
 292 {
 293 SEQAN_CHECKPOINT
 294         _arrayConstruct_Default(begin_, end_);
 295 }
 296
 297 //____________________________________________________________________________
 298
 299 template<typename TIterator1, typename TIterator2, typename TParam>
 300 inline void
 301 _arrayConstruct_Default(TIterator1 begin_,
 302                                                 TIterator2 end_,
 303                                                 TParam const & param_)
 304 {
 305 SEQAN_CHECKPOINT
 306         while (begin_ != end_)
 307         {
 308                 valueConstruct(begin_, param_);
 309                 ++begin_;
 310         }
 311 }
 312 template<typename TIterator1, typename TIterator2, typename TParam>
 313 inline void
 314 arrayConstruct(TIterator1 begin_,
 315                            TIterator2 end_,
 316                            TParam const & param_)
 317 {
 318 SEQAN_CHECKPOINT
 319         _arrayConstruct_Default(begin_, end_, param_);
 320 }
 321
 322 //////////////////////////////////////////////////////////////////////////////
 323 //arrayConstructCopy
 324 //////////////////////////////////////////////////////////////////////////////
 325
 326 /**
 327 .Function.arrayConstructCopy:
 328 ..cat:Array Handling
 329 ..summary:Copy constructs an array of objects into in a given memory buffer.
 330 ..signature:arrayConstructCopy(source_begin, source_end, target)
 331 ..param.source_begin:Iterator to the first element of the source range.
 332 ..param.source_end:Iterator behind the last element of the source range.
 333 ...text:$source_end$ should have the same type as $source_begin$.
 334 ..param.target:Pointer to the memory block the new objects will be constructed in.
 335 ...text:The type of $target$ specifies the type of the constructed objects:
 336 If $T*$ is the type of $target$, then the function constructs objects of type $T$.
 337 ...text:The memory buffer should be large enough to store $source_end$ - $source_begin$ objects.
 338 An appropriate (copy-) constructor that constructs an target objects given a source object is required.
 339 ..see:Function.arrayDestruct
 340 ..see:Function.arrayCopyForward
 341 ..see:Function.arrayCopy
 342 ..see:Function.valueConstruct
 343 */
 344 template<typename TTarget, typename TSource1, typename TSource2>
 345 inline void
 346 _arrayConstructCopy_Default(TSource1 source_begin,
 347                                                         TSource2 source_end,
 348                                                         TTarget target_begin)
 349 {
 350 SEQAN_CHECKPOINT
 351         while (source_begin != source_end)
 352         {
 353                 valueConstruct(target_begin, *source_begin);
 354                 ++source_begin;
 355                 ++target_begin;
 356         }
 357 }
 358
 359 template<typename TTarget, typename TSource1, typename TSource2>
 360 inline void
 361 arrayConstructCopy(TSource1 source_begin,
 362                                    TSource2 source_end,
 363                                    TTarget target_begin)
 364 {
 365 SEQAN_CHECKPOINT
 366         _arrayConstructCopy_Default(source_begin, source_end, target_begin);
 367 }
 368
 369 //////////////////////////////////////////////////////////////////////////////
 370 //arrayConstructMove
 371 //////////////////////////////////////////////////////////////////////////////
 372
 373 /**
 374 .Function.arrayConstructMove:
 375 ..cat:Array Handling
 376 ..summary:Move constructs an array of objects into in a given memory buffer.
 377 ..signature:arrayConstructMove(source_begin, source_end, target)
 378 ..param.source_begin:Iterator to the first element of the source range.
 379 ..param.source_end:Iterator behind the last element of the source range.
 380 ...text:$source_end$ should have the same type as $source_begin$.
 381 ..param.target:Pointer to the memory block the new objects will be constructed in.
 382 ...text:The type of $target$ specifies the type of the constructed objects:
 383 If $T*$ is the type of $target$, then the function constructs objects of type $T$.
 384 ...text:The memory buffer should be large enough to store $source_end$ - $source_begin$ objects.
 385 An appropriate move constructor that constructs an target objects given a source object is required.
 386 ..see:Function.arrayDestruct
 387 ..see:Function.arrayConstructCopy
 388 ..see:Function.arrayMoveForward
 389 ..see:Function.arrayMove
 390 ..see:Function.valueConstruct
 391 */
 392 template<typename TTarget, typename TSource1, typename TSource2>
 393 inline void
 394 _arrayConstructMove_Default(TSource1 source_begin,
 395                                                         TSource2 source_end,
 396                                                         TTarget target_begin)
 397 {
 398 SEQAN_CHECKPOINT
 399         while (source_begin < source_end)
 400         {
 401                 valueConstructMove(target_begin, *source_begin);
 402                 ++source_begin;
 403                 ++target_begin;
 404         }
 405 }
 406
 407 template<typename TTarget, typename TSource1, typename TSource2>
 408 inline void
 409 arrayConstructMove(TSource1 source_begin,
 410                                    TSource2 source_end,
 411                                    TTarget target_begin)
 412 {
 413 SEQAN_CHECKPOINT
 414         _arrayMoveConstruct_Default(source_begin, source_end, target_begin);
 415 }
 416
 417 //////////////////////////////////////////////////////////////////////////////
 418 //arrayDestruct
 419 //////////////////////////////////////////////////////////////////////////////
 420
 421 /**
 422 .Function.arrayDestruct:
 423 ..cat:Array Handling
 424 ..summary:Destroys an array of objects.
 425 ..signature:arrayDestruct(begin, end)
 426 ..param.begin:Iterator to the begin of the range that is to be destructed.
 427 ..param.end:Iterator behind the end of the range.
 428 ..remarks:This function does not deallocates the memory.
 429 ..see:Class.SimpleType
 430 ..see:Function.valueDestruct
 431 */
 432 template<typename TIterator1, typename TIterator2>
 433 inline void
 434 _arrayDestruct_Default(TIterator1 begin_,
 435                                            TIterator2 end_)
 436 {
 437 SEQAN_CHECKPOINT
 438         while (begin_ != end_)
 439         {
 440                 valueDestruct(begin_);
 441                 ++begin_;
 442         }
 443 }
 444 template<typename TIterator1, typename TIterator2>
 445 inline void
 446 arrayDestruct(TIterator1 begin_,
 447                           TIterator2 end_)
 448 {
 449 SEQAN_CHECKPOINT
 450         _arrayDestruct_Default(begin_, end_);
 451 }
 452
 453 //////////////////////////////////////////////////////////////////////////////
 454 //arrayFill
 455 //////////////////////////////////////////////////////////////////////////////
 456
 457 /**
 458 .Function.arrayFill:
 459 ..cat:Array Handling
 460 ..summary:Assigns one object to each element of a range.
 461 ..signature:arrayFill(begin, end, value)
 462 ..param.begin:Iterator to the begin of the range that is to be filled.
 463 ..param.end:Iterator behind the end of the range.
 464 ..param.value:Argument that is assigned to all $count$ objects in $array$.
 465 ..remarks:All objects $target_begin[0]$ to $target_begin[count-1]$ are set to $value$.
 466 ..see:Function.arrayCopy
 467 ..see:Function.arrayCopyForward
 468 */
 469 template<typename TIterator1, typename TIterator2, typename TValue>
 470 inline void
 471 arrayFill(TIterator1 begin_,
 472                   TIterator2 end_,
 473                   TValue const & value)
 474 {
 475 SEQAN_CHECKPOINT
 476         ::std::fill_n(begin_, end_ - begin_, value);
 477 }
 478
 479 //////////////////////////////////////////////////////////////////////////////
 480 //arrayCopyForward
 481 //////////////////////////////////////////////////////////////////////////////
 482
 483 /**
 484 .Function.arrayCopyForward:
 485 ..cat:Array Handling
 486 ..summary:Copies a range of objects into another range of objects starting from the first element.
 487 ..signature:arrayCopyForward(source_begin, source_end, target)
 488 ..param.source_begin:Iterator to the first element of the source array.
 489 ..param.source_end:Iterator behind the last element of the source array.
 490 ...text:$source_end$ must have the same type as $source_begin$.
 491 ..param.target:Iterator to the first element of the target array.
 492 ...text:The target capacity should be at least as long as the source range.
 493 ..remarks.note:Be careful if source and target range overlap, because in this case
 494         some source elements could be accidently overwritten before they are moved.
 495 ..remarks:If there is no need for the source elements to persist, consider to use
 496 @Function.arrayMoveForward@ instead to improve performance.
 497 ..see:Class.SimpleType
 498 */
 499 template<typename TTarget, typename TSource1, typename TSource2>
 500 inline void
 501 _arrayCopyForward_Default(TSource1 source_begin,
 502                                                   TSource2 source_end,
 503                                                   TTarget target_begin)
 504 {
 505 SEQAN_CHECKPOINT
 506         ::std::copy(source_begin, source_end, target_begin);
 507 }
 508 template<typename TTarget, typename TSource1, typename TSource2>
 509 inline void
 510 arrayCopyForward(TSource1 source_begin,
 511                                  TSource2 source_end,
 512                                  TTarget target_begin)
 513 {
 514 SEQAN_CHECKPOINT
 515         _arrayCopyForward_Default(source_begin, source_end, target_begin);
 516 }
 517
 518 //////////////////////////////////////////////////////////////////////////////
 519 //arrayCopyBackward
 520 //////////////////////////////////////////////////////////////////////////////
 521
 522 /**
 523 .Function.arrayCopyBackward:
 524 ..cat:Array Handling
 525 ..summary:Copies a range of objects into another range of objects starting from the last element.
 526 ..signature:arrayCopyBackward(source_begin, source_end, target)
 527 ..param.source_begin:Iterator to the first element of the source array.
 528 ..param.source_end:Iterator behind the last element of the source array.
 529 ...text:$source_end$ must have the same type as $source_begin$.
 530 ..param.target:Iterator to the first element of the target array.
 531 ...text:The target capacity should be at least as long as the source range.
 532 ..remarks.note:Be careful if source and target range overlap, because in this case
 533         some source elements could be accidently overwritten before they are moved.
 534 ..remarks.text:If source and target do not overlap, consider to use the function
 535 @Function.arrayCopyForward@ instead that is faster in some cases.
 536 ..remarks:If there is no need for the source elements to persist, consider to use
 537 @Function.arrayMoveBackward@ instead to improve performance.
 538 ..remarks.note:The semantic of this function's argument $target$ differ from the arguments of $::std::copy_backward$.
 539 ..see:Function.arrayCopyForward
 540 ..see:Class.SimpleType
 541 */
 542 template<typename TTarget, typename TSource1, typename TSource2>
 543 inline void
 544 _arrayCopyBackward_Default(TSource1 source_begin,
 545                                                    TSource2 source_end,
 546                                                    TTarget target_begin)
 547 {
 548 SEQAN_CHECKPOINT
 549         ::std::copy_backward(source_begin, source_end, target_begin + (source_end - source_begin));
 550 }
 551 template<typename TTarget, typename TSource1, typename TSource2>
 552 inline void
 553 arrayCopyBackward(TSource1 source_begin,
 554                                   TSource2 source_end,
 555                                   TTarget target_begin)
 556 {
 557 SEQAN_CHECKPOINT
 558         _arrayCopyBackward_Default(source_begin, source_end, target_begin);
 559 }
 560
 561
 562 //////////////////////////////////////////////////////////////////////////////
 563 //arrayCopy
 564 //////////////////////////////////////////////////////////////////////////////
 565
 566 /**
 567 .Function.arrayCopy:
 568 ..cat:Array Handling
 569 ..summary:Copies a range of objects into another range of objects.
 570 ..signature:arrayCopy(source_begin, source_end, target)
 571 ..param.source_begin:Iterator to the first element of the source range.
 572 ..param.source_end:Iterator behind the last element of the source range.
 573 ...text:$source_end$ must have the same type as $source_begin$.
 574 ..param.target:Iterator to the first element of the target range.
 575 ...text:The target capacity should be at least as long as the source range.
 576 ..remarks.text:If source and target range do not overlap, consider to use
 577         @Function.arrayCopyForward@ instead to improve performance.
 578 ..remarks:If there is no need for the source elements to persist, consider to use
 579         @Function.arrayMoveForward@ instead to improve performance.
 580 ..DISABLED.remarks.note:Be careful if source and target range overlap and the size of the
 581         source elements differ from the size of target elements, because in this case
 582         some source elements could be accidently overwritten before they are moved.
 583 ..see:Function.arrayCopyForward
 584 ..see:Function.arrayCopyBackward
 585 ..see:Class.SimpleType
 586 */
 587 template<typename TTarget, typename TSource1, typename TSource2>
 588 inline void arrayCopy(TSource1 source_begin,
 589                                           TSource2 source_end,
 590                                           TTarget target_begin)
 591 {
 592         if ((void *) source_begin >= (void *) target_begin)
 593         {
 594 SEQAN_CHECKPOINT
 595                 arrayCopyForward(source_begin, source_end, target_begin);
 596         }
 597         else
 598         {
 599 SEQAN_CHECKPOINT
 600                 arrayCopyBackward(source_begin, source_end, target_begin);
 601         }
 602 }
 603
 604 //////////////////////////////////////////////////////////////////////////////
 605 //arrayMoveForward
 606 //////////////////////////////////////////////////////////////////////////////
 607
 608 /**
 609 .Function.arrayMoveForward:
 610 ..cat:Array Handling
 611 ..summary:Moves a range of objects into another range of objects starting from the first element.
 612 ..signature:arrayMoveForward(source_begin, source_end, target)
 613 ..param.source_begin:Iterator to the first element of the source array.
 614 ..param.source_end:Iterator behind the last element of the source array.
 615 ...text:$source_end$ must have the same type as $source_begin$.
 616 ..param.target:Iterator to the first element of the target array.
 617 ...text:The target capacity should be at least as long as the source range.
 618 ..remarks:The function possibly clears (but does not destroy) the source elements.
 619         If source elements must persist, consider to use @Function.arrayCopyForward@ instead.
 620 ..remarks.note:Be careful if source and target range overlap, because in this case
 621         some source elements could be accidently overwritten before they are moved.
 622 ..see:Function.arrayCopyForward
 623 ..see:Class.SimpleType
 624 */
 625 template<typename TTarget, typename TSource1, typename TSource2>
 626 inline void
 627 _arrayMoveForward_Default(TSource1 source_begin,
 628                                                   TSource2 source_end,
 629                                                   TTarget target_begin)
 630 {
 631 SEQAN_CHECKPOINT
 632         while (source_begin != source_end)
 633         {
 634                 move(*target_begin, *source_begin);
 635                 ++source_begin;
 636                 ++target_begin;
 637         }
 638 }
 639 template<typename TTarget, typename TSource1, typename TSource2>
 640 inline void
 641 arrayMoveForward(TSource1 source_begin,
 642                                  TSource2 source_end,
 643                                  TTarget target_begin)
 644 {
 645 SEQAN_CHECKPOINT
 646         _arrayMoveForward_Default(source_begin, source_end, target_begin);
 647 }
 648
 649 //////////////////////////////////////////////////////////////////////////////
 650 //arrayMoveBackward
 651 //////////////////////////////////////////////////////////////////////////////
 652
 653 /**
 654 .Function.arrayMoveBackward:
 655 ..cat:Array Handling
 656 ..summary:Moves a range of objects into another range of objects starting from the last element.
 657 ..signature:arrayMoveBackward(source_begin, source_end, target)
 658 ..param.source_begin:Iterator to the first element of the source array.
 659 ..param.source_end:Iterator behind the last element of the source array.
 660 ...text:$source_end$ must have the same type as $source_begin$.
 661 ..param.target:Iterator to the first element of the target array.
 662 ...text:The target capacity should be at least as long as the source range.
 663 ..remarks:The function possibly clears (but does not destroy) the source elements.
 664         If source elements must persist, consider to use @Function.arrayCopyBackward@ instead.
 665 ..remarks.note:Be careful if source and target range overlap, because in this case
 666         some source elements could be accidently overwritten before they are moved.
 667 ..remarks.text:If source and target do not overlap, consider to use the function
 668 @Function.arrayMoveForward@ instead that is faster in some cases.
 669 ..remarks.note:The semantic of this function's argument $target$ differ from the arguments of $::std::copy_backward$.
 670 ..see:Function.arrayMoveForward
 671 ..see:Function.arrayCopyBackward
 672 ..see:Class.SimpleType
 673 */
 674 template<typename TTarget, typename TSource1, typename TSource2>
 675 inline void
 676 _arrayMoveBackward_Default(TSource1 source_begin,
 677                                                    TSource2 source_end,
 678                                                    TTarget target_begin)
 679 {
 680 SEQAN_CHECKPOINT
 681         target_begin += (source_end - source_begin);
 682         while (source_end != source_begin)
 683         {
 684                 --source_end;
 685                 --target_begin;
 686                 move(*target_begin, *source_end);
 687         }
 688 }
 689 template<typename TTarget, typename TSource1, typename TSource2>
 690 inline void
 691 arrayMoveBackward(TSource1 source_begin,
 692                                   TSource2 source_end,
 693                                   TTarget target_begin)
 694 {
 695 SEQAN_CHECKPOINT
 696         _arrayMoveBackward_Default(source_begin, source_end, target_begin);
 697 }
 698
 699 //////////////////////////////////////////////////////////////////////////////
 700 //arrayMove
 701 //////////////////////////////////////////////////////////////////////////////
 702
 703 /**
 704 .Function.arrayMove:
 705 ..cat:Array Handling
 706 ..summary:Moves a range of objects into another range of objects.
 707 ..signature:arrayMove(source_begin, source_end, target)
 708 ..param.source_begin:Iterator to the first element of the source range.
 709 ..param.source_end:Iterator behind the last element of the source range.
 710 ...text:$source_end$ must have the same type as $source_begin$.
 711 ..param.target:Iterator to the first element of the target range.
 712 ...text:The target capacity should be at least as long as the source range.
 713 ..remarks:The function possibly clears (but does not destroy) the source elements.
 714         If source elements must persist, consider to use @Function.arrayCopy@ instead.
 715 ..remarks.text:If source and target range do not overlap, consider to use
 716         @Function.arrayMoveForward@ instead to improve performance.
 717 ..DISABLED.remarks.note:Be careful if source and target range overlap and the size of the
 718         source elements differ from the size of target elements, because in this case
 719         some source elements could be accidently overwritten before they are moved.
 720 ..remarks.note:Don't confuse this function with the standard $move$ function that
 721 resembles @Function.arrayCopy@.
 722 ..see:Function.arrayMoveForward
 723 ..see:Function.arrayMoveBackward
 724 ..see:Function.arrayCopy
 725 ..see:Class.SimpleType
 726 */
 727 template<typename TTarget, typename TSource1, typename TSource2>
 728 inline void
 729 arrayMove(TSource1 source_begin,
 730                   TSource2 source_end,
 731                   TTarget target_begin)
 732 {
 733         if ((void *) source_begin >= (void *) target_begin)
 734         {
 735 SEQAN_CHECKPOINT
 736                 arrayMoveForward(source_begin, source_end, target_begin);
 737         }
 738         else
 739         {
 740 SEQAN_CHECKPOINT
 741                 arrayMoveBackward(source_begin, source_end, target_begin);
 742         }
 743 }
 744
 745 //////////////////////////////////////////////////////////////////////////////
 746 //arrayClearSpace
 747 //////////////////////////////////////////////////////////////////////////////
 748
 749 /**
 750 .Function.arrayClearSpace:
 751 ..cat:Array Handling
 752 ..summary:Destroys the begin of an array and keeps the rest.
 753 ..signature:arrayClearSpace(arr_begin, arr_length, keep_from, move_to)
 754 ..param.arr_begin:Pointer to the first element of the array.
 755 ..param.arr_length:Length of the array.
 756 ..param.keep_from:Offset of the first object that will be kept.
 757 ..param.move_to:Offset the first kept object will get at the end of the function.
 758 ..remarks.text:The objects $arr[keep_from]$ to $arr[arr_length-1]$
 759 are moved to the area beginning at positions $move_to$.
 760 All objects in $arr[0]$ to $arr[keep_from-1]$ are destroyed.
 761 After this function, the first $move_to$ positions of the array
 762 are free and dont contain objects.
 763 ..remarks.text:The array must have at least enough space to store $arr_length + move_to - keep_from$ objects.
 764 ..see:Function.arrayCopy
 765 ..see:Function.arrayDestruct
 766 ..see:Function.arrayCopyForward
 767 ..see:Class.SimpleType
 768 */
 769 template <typename TIterator>
 770 void _arrayClearSpace_Default(TIterator array_begin,
 771                                                           size_t array_length,
 772                                                           size_t keep_from,
 773                                                           size_t move_to)
 774 {
 775         if (keep_from == array_length)
 776         {
 777                 arrayDestruct(array_begin, array_begin + array_length);
 778                 return;
 779         }
 780
 781         SEQAN_ASSERT(keep_from < array_length)
 782
 783         if (keep_from == move_to)
 784         {
 785                 arrayDestruct(array_begin, array_begin + move_to);
 786         }
 787         else if (keep_from < move_to)
 788         {
 789                 if (array_length > move_to)
 790                 {
 791 SEQAN_CHECKPOINT
 792                         size_t middle = array_length - (move_to - keep_from);
 793                         arrayConstructMove(array_begin + middle, array_begin + array_length, array_begin + array_length);
 794                         arrayMove(array_begin + keep_from, array_begin + middle, array_begin + move_to);
 795                         arrayDestruct(array_begin, array_begin + move_to);
 796                 }
 797                 else
 798                 {
 799 SEQAN_CHECKPOINT
 800                         arrayConstructMove(array_begin + keep_from, array_begin + array_length, array_begin + move_to);
 801                         arrayDestruct(array_begin, array_begin + array_length);
 802                 }
 803         }
 804         else
 805         {
 806 SEQAN_CHECKPOINT
 807                 arrayMove(array_begin + keep_from, array_begin + array_length, array_begin + move_to);
 808                 arrayDestruct(array_begin, array_begin + move_to);
 809                 arrayDestruct(array_begin + array_length - (keep_from - move_to), array_begin + array_length);
 810         }
 811 }
 812
 813 template <typename TIterator>
 814 void arrayClearSpace(TIterator array_begin,
 815                                          size_t array_length,
 816                                          size_t keep_from,
 817                                          size_t move_to)
 818 {
 819         _arrayClearSpace_Default(array_begin, array_length, keep_from, move_to);
 820 }
 821
 822
 823 //////////////////////////////////////////////////////////////////////////////
 824 //BitsPerValue
 825 //////////////////////////////////////////////////////////////////////////////
 826 /**
 827 .Metafunction.BitsPerValue:
 828 ..summary:Number of bits needed to store a value.
 829 ..signature:BitsPerValue<T>::VALUE
 830 ..param.T:A class.
 831 ..returns.param.VALUE:Number of bits needed to store $T$.
 832 ...default:$sizeof<T> * 8$
 833 ..see:Metafunction.ValueSize
 834 */
 835 template <typename TValue>
 836 struct BitsPerValue
 837 {
 838         enum { VALUE = sizeof(TValue) * 8 };
 839 };
 840 template <typename TValue>
 841 struct BitsPerValue<TValue const>:
 842         public BitsPerValue<TValue> {};
 843
 844 //////////////////////////////////////////////////////////////////////////////
 845 //ValueSize
 846 //////////////////////////////////////////////////////////////////////////////
 847 /**
 848 .Metafunction.ValueSize:
 849 ..summary:Number of different values a value type object can have.
 850 ..signature:ValueSize<T>::VALUE
 851 ..param.T:A class.
 852 ..returns.param.VALUE:Value size of $T$.
 853 ..remarks
 854 ...text:This function is only defined for integral types like $unsigned int$, $double$ or @Spec.Dna@.
 855 ..see:Metafunction.Value
 856 */
 857 template <typename T>
 858 struct ValueSize
 859 {
 860         enum { VALUE = 1 << BitsPerValue<T>::VALUE };
 861 };
 862 template <typename TValue>
 863 struct ValueSize<TValue const>:
 864         public ValueSize<TValue> {};
 865
 866
 867
 868 template < typename T >
 869 struct _SupremumValueUnsigned { static const T VALUE; };
 870 template < typename T >
 871 struct _SupremumValueSigned {   static const T VALUE; };
 872
 873 template < typename T >
 874 struct _InfimumValueUnsigned {  static const T VALUE; };
 875 template < typename T >
 876 struct _InfimumValueSigned {    static const T VALUE; };
 877
 878
 879
 880 template < typename T >
 881 const T _SupremumValueUnsigned<T>::VALUE = ~(T)0;
 882 template < typename T >
 883 const T _SupremumValueSigned<T>::VALUE = ( (((T)1 << (BitsPerValue<T>::VALUE - 2)) - 1) << 1) + 1;
 884
 885 template < typename T >
 886 const T _InfimumValueUnsigned<T>::VALUE = 0;
 887 template < typename T >
 888 const T _InfimumValueSigned<T>::VALUE = ~(T)_SupremumValueSigned<T>::VALUE;
 889
 890
 891
 892 template <
 893         typename T,
 894         typename TParent = typename IF<
 895                 TYPECMP< typename _MakeSigned<T>::Type, T >::VALUE,
 896                 _SupremumValueSigned<T>,
 897                 _SupremumValueUnsigned<T> >::Type >
 898 struct SupremumValue:
 899         public TParent
 900 {
 901 };
 902
 903 template <
 904         typename T,
 905         typename TParent = typename IF<
 906                 TYPECMP< typename _MakeSigned<T>::Type, T >::VALUE,
 907                 _InfimumValueSigned<T>,
 908                 _InfimumValueUnsigned<T> >::Type >
 909 struct InfimumValue:
 910         public TParent
 911 {
 912 };
 913
 914 //////////////////////////////////////////////////////////////////////////////
 915 }// namespace SEQAN_NAMESPACE_MAIN
 916
 917 #endif //#ifndef SEQAN_HEADER_...