SeqAn-1.1/seqan/sequence/string_base.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: string_base.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
  19  ==========================================================================*/
  20
  21 #ifndef SEQAN_HEADER_SEQUENCE_ARRAY_BASE_H
  22 #define SEQAN_HEADER_SEQUENCE_ARRAY_BASE_H
  23
  24
  25 namespace SEQAN_NAMESPACE_MAIN
  26 {
  27
  28 //////////////////////////////////////////////////////////////////////////////
  29 // Tags
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32
  33 template <typename TSpec = void>
  34 struct Alloc;
  35
  36
  37 //////////////////////////////////////////////////////////////////////////////
  38 //////////////////////////////////////////////////////////////////////////////
  39 /**
  40 .Class.String:
  41 ..cat:Sequences
  42 ..summary:General purpose container for sequences.
  43 ..signature:String<TValue, TSpec>
  44 ..param.TValue:The value type, that is the type of the items/characters stored in the string.
  45 ...metafunction:Metafunction.Value
  46 ..param.TSpec:The specializing type.
  47 ...metafunction:Metafunction.Spec
  48 ...default:$Alloc<>$, see @Spec.Alloc String@.
  49 ..implements:Concept.Container
  50 ..include:sequence.h
  51 */
  52
  53 template <typename TValue, typename TSpec = Alloc<> >
  54 class String;
  55
  56
  57
  58
  59 //////////////////////////////////////////////////////////////////////////////
  60 // METAFUNCTIONS
  61 //////////////////////////////////////////////////////////////////////////////
  62
  63 ///.Metafunction.Iterator.param.T.type:Class.String
  64
  65 //////////////////////////////////////////////////////////////////////////////
  66
  67 template <typename TValue, typename TSpec>
  68 struct Value<String<TValue, TSpec> >
  69 {
  70         typedef TValue Type;
  71 };
  72 template <typename TValue, typename TSpec>
  73 struct Value<String<TValue, TSpec> const >:
  74         public Value<String<TValue, TSpec> >
  75 {
  76 };
  77
  78 //////////////////////////////////////////////////////////////////////////////
  79
  80 ///.Metafunction.Spec.param.T.type:Class.String
  81
  82 template <typename TValue, typename TSpec>
  83 struct Spec<String<TValue, TSpec> >
  84 {
  85         typedef TSpec Type;
  86 };
  87 template <typename TValue, typename TSpec>
  88 struct Spec<String<TValue, TSpec> const>:
  89         public Spec<String<TValue, TSpec> >
  90 {
  91 };
  92
  93 //////////////////////////////////////////////////////////////////////////////
  94
  95 ///.Metafunction.IsSequence.param.T.type:Class.String
  96
  97 template <typename TValue, typename TSpec>
  98 struct IsSequence<String<TValue, TSpec> > {
  99     typedef True Type;
 100         enum { VALUE = true };
 101 };
 102
 103 //////////////////////////////////////////////////////////////////////////////
 104 // Returns a Class that can be used to store a temporary copy of a String
 105
 106 template <typename T>
 107 struct _TempCopy
 108 {
 109         typedef typename Value<T>::Type TValue;
 110         typedef typename _RemoveConst<TValue>::Type TValue_NotConst;
 111         typedef String<TValue_NotConst, Alloc<> > Type;
 112 };
 113
 114 //////////////////////////////////////////////////////////////////////////////
 115 // FUNCTIONS
 116 //////////////////////////////////////////////////////////////////////////////
 117
 118 ///.Function.id.param.object.type:Class.String
 119 ///.Function.empty.param.object.type:Class.String
 120 ///.Function.capacity.param.object.type:Class.String
 121
 122
 123 //////////////////////////////////////////////////////////////////////////////
 124 //shareResources
 125
 126 ///.Function.shareResources.param.sequence1, sequence2.type:Class.String
 127
 128 template <typename TValue, typename TSpec>
 129 inline bool
 130 shareResources(String<TValue, TSpec> const & obj1,
 131                                         TValue const & obj2)
 132 {
 133 SEQAN_CHECKPOINT
 134         return (begin(obj1) >= &obj2) && (end(obj1) <= &obj2);
 135 }
 136
 137 template <typename TValue, typename TSpec>
 138 inline bool
 139 shareResources(TValue const & obj1,
 140                                         String<TValue, TSpec> const & obj2)
 141 {
 142 SEQAN_CHECKPOINT
 143         return (begin(obj2) >= &obj1) && (end(obj2) <= &obj1);
 144 }
 145
 146 //////////////////////////////////////////////////////////////////////////////
 147
 148 ///.Function.begin.param.object.type:Class.String
 149 ///.Function.end.param.object.type:Class.String
 150 //////////////////////////////////////////////////////////////////////////////
 151
 152 ///.Function.value.param.container.type:Class.String
 153
 154 template <typename TValue, typename TSpec, typename TPos>
 155 inline typename Reference< String<TValue, TSpec> >::Type
 156 value(String<TValue, TSpec> & me,
 157           TPos pos)
 158 {
 159 SEQAN_CHECKPOINT
 160         return *(begin(me, Standard()) + pos);
 161 }
 162
 163 template <typename TValue, typename TSpec, typename TPos>
 164 inline typename Reference< String<TValue, TSpec> const >::Type
 165 value(String<TValue, TSpec> const & me,
 166           TPos pos)
 167 {
 168 SEQAN_CHECKPOINT
 169         return *(begin(me, Standard()) + pos);
 170 }
 171
 172 //////////////////////////////////////////////////////////////////////////////
 173
 174 ///.Function.length.param.object.type:Class.String
 175
 176 template <typename TValue, typename TSpec>
 177 inline typename Size< String<TValue, TSpec> const>::Type
 178 length(String<TValue, TSpec> const & me)
 179 {
 180 SEQAN_CHECKPOINT
 181         return end(me, Standard()) - begin(me, Standard());
 182 }
 183
 184 //////////////////////////////////////////////////////////////////////////////
 185
 186 /**
 187 .Function.clear:
 188 ..cat:Containers
 189 ..summary:Resets an object.
 190 ..signature:clear(object)
 191 ..param.object:The object that will be resetted.
 192 ...type:Class.String
 193 ..remarks:$object$ is set to a state that is equivalent to a default constructed object of the same type.
 194 ..remarks:If $object$ is a container, then all elements are removed from this container.
 195 The length is set to 0.
 196 The capacity can be changed, depending on the implementation.
 197 ..see:Function.resize
 198 ..see:Function.length
 199 */
 200
 201 template <typename TValue, typename TSpec>
 202 inline void
 203 clear(String<TValue, TSpec> & me)
 204 {
 205 SEQAN_CHECKPOINT
 206         arrayDestruct(begin(me, Standard()), end(me, Standard()));
 207         _setLength(me, 0);
 208 }
 209
 210 //////////////////////////////////////////////////////////////////////////////
 211
 212 template <typename TExpand>
 213 struct _ClearSpace_String_Base_
 214 {
 215 };
 216
 217 //____________________________________________________________________________
 218
 219 template <>
 220 struct _ClearSpace_String_Base_<Insist>
 221 {
 222         template <typename T>
 223         static inline typename Size<T>::Type
 224         _clearSpace_(
 225                 T & seq,
 226                 typename Size<T>::Type size)
 227         {
 228 SEQAN_CHECKPOINT
 229                 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
 230                 _setLength(seq, size);
 231                 return size;
 232         }
 233
 234         template <typename T>
 235         static inline typename Size<T>::Type
 236         _clearSpace_(
 237                 T & seq,
 238                 typename Size<T>::Type size,
 239                 typename Size<T>::Type limit)
 240         {
 241                 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
 242                 if (limit < size)
 243                 {
 244 SEQAN_CHECKPOINT
 245                         size = limit;
 246                 }
 247                 _setLength(seq, size);
 248                 return size;
 249         }
 250
 251         template <typename T>
 252         static inline typename Size<T>::Type
 253         _clearSpace_(
 254                 T & seq,
 255                 typename Size<T>::Type size,
 256                 typename Size<T>::Type start,
 257                 typename Size<T>::Type end)
 258         {
 259 SEQAN_CHECKPOINT
 260                 typename Size<T>::Type new_length = length(seq) + size - (end - start);
 261                 arrayClearSpace(begin(seq, Standard()) + start, length(seq) - start, end - start, size);
 262                 _setLength(seq, new_length);
 263                 return size;
 264         }
 265
 266         template <typename T>
 267         static typename Size<T>::Type
 268         _clearSpace_(
 269                 T & seq,
 270                 typename Size<T>::Type size,
 271                 typename Size<T>::Type start,
 272                 typename Size<T>::Type end,
 273                 typename Size<T>::Type limit)
 274         {
 275                 typename Value<T>::Type * seq_buffer = begin(seq);
 276                 typename Size<T>::Type seq_length = length(seq);
 277
 278                 if (limit > start + size)
 279                 {
 280 SEQAN_CHECKPOINT
 281                         typename Size<T>::Type removed_size = end - start;
 282                         typename Size<T>::Type new_length = seq_length - removed_size + size;
 283                         if (limit < new_length)
 284                         {
 285 SEQAN_CHECKPOINT
 286                                 arrayDestruct(seq_buffer + limit, seq_buffer + new_length);
 287                                 seq_length -= new_length - limit;
 288                         }
 289                         arrayClearSpace(seq_buffer + start, seq_length - start, end - start, size);
 290                         _setLength(seq, new_length);
 291                         return size;
 292                 }
 293                 else
 294                 {
 295 SEQAN_CHECKPOINT
 296                         arrayDestruct(seq_buffer + start, seq_buffer + seq_length);
 297                         _setLength(seq, limit);
 298                         if (limit > start) return limit - start;
 299                         else return 0;
 300                 }
 301         }
 302 /*
 303         template <typename T>
 304         static inline typename Size<T>::Type
 305         _clearSpace_(
 306                 T & seq,
 307                 typename Size<T>::Type size,
 308                 typename Iterator<T>::Type start,
 309                 typename Iterator<T>::Type end)
 310         {
 311                 typename Iterator<T>::Type seq_begin = begin(seq);
 312                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, Insist());
 313         }
 314
 315         template <typename T>
 316         static inline typename Size<T>::Type
 317         _clearSpace_(
 318                 T & seq,
 319                 typename Size<T>::Type size,
 320                 typename Iterator<T>::Type start,
 321                 typename Iterator<T>::Type end,
 322                 typename Size<T>::Type limit)
 323         {
 324                 typename Iterator<T>::Type seq_begin = begin(seq);
 325                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, Insist());
 326         }
 327 */
 328 };
 329
 330
 331 //____________________________________________________________________________
 332
 333
 334 template <>
 335 struct _ClearSpace_String_Base_<Limit>
 336 {
 337
 338         template <typename T>
 339         static inline typename Size<T>::Type
 340         _clearSpace_(
 341                 T & seq,
 342                 typename Size<T>::Type size)
 343         {
 344 SEQAN_CHECKPOINT
 345                 return _clearSpace(seq, size, capacity(seq), Insist());
 346         }
 347
 348         template <typename T>
 349         static inline typename Size<T>::Type
 350         _clearSpace_(
 351                 T & seq,
 352                 typename Size<T>::Type size,
 353                 typename Size<T>::Type limit)
 354         {
 355                 typename Size<T>::Type seq_capacity = capacity(seq);
 356                 if (limit > seq_capacity)
 357                 {
 358 SEQAN_CHECKPOINT
 359                         limit = seq_capacity;
 360                 }
 361                 return _clearSpace(seq, size, limit, Insist());
 362         }
 363
 364         template <typename T>
 365         static inline typename Size<T>::Type
 366         _clearSpace_(
 367                 T & seq,
 368                 typename Size<T>::Type size,
 369                 typename Size<T>::Type start,
 370                 typename Size<T>::Type end)
 371         {
 372 SEQAN_CHECKPOINT
 373                 return _clearSpace(seq, size, start, end, capacity(seq), Insist());
 374         }
 375
 376         template <typename T>
 377         static typename Size<T>::Type
 378         _clearSpace_(
 379                 T & seq,
 380                 typename Size<T>::Type size,
 381                 typename Size<T>::Type start,
 382                 typename Size<T>::Type end,
 383                 typename Size<T>::Type limit)
 384         {
 385                 typename Size<T>::Type seq_capacity = capacity(seq);
 386                 if (limit > seq_capacity)
 387                 {
 388 SEQAN_CHECKPOINT
 389                         limit = seq_capacity;
 390                 }
 391                 return _clearSpace(seq, size, start, end, limit, Insist());
 392         }
 393
 394 /*
 395         template <typename T>
 396         static inline typename Size<T>::Type
 397         _clearSpace_(
 398                 T & seq,
 399                 typename Size<T>::Type size,
 400                 typename Iterator<T>::Type start,
 401                 typename Iterator<T>::Type end)
 402         {
 403                 typename Iterator<T>::Type seq_begin = begin(seq);
 404                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, Insist());
 405         }
 406
 407         template <typename T>
 408         static inline typename Size<T>::Type
 409         _clearSpace_(
 410                 T & seq,
 411                 typename Size<T>::Type size,
 412                 typename Iterator<T>::Type start,
 413                 typename Iterator<T>::Type end,
 414                 typename Size<T>::Type limit)
 415         {
 416                 typename Iterator<T>::Type seq_begin = begin(seq);
 417                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, Insist());
 418         }
 419 */
 420 };
 421
 422 //____________________________________________________________________________
 423
 424 template <typename TExpand>
 425 struct _ClearSpace_Expand_String_Base_
 426 {
 427         template <typename T>
 428         static inline typename Size<T>::Type
 429         _clearSpace_(
 430                 T & seq,
 431                 typename Size<T>::Type size)
 432         {
 433                 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
 434                 typename Size<T>::Type old_capacity = capacity(seq);
 435                 typename Value<T>::Type * old_array = _reallocateStorage(seq, size, TExpand());
 436                 if (old_array)
 437                 {
 438 SEQAN_CHECKPOINT
 439                         _deallocateStorage(seq, old_array, old_capacity);
 440                 }
 441                 _setLength(seq, size);
 442                 return size;
 443         }
 444
 445         template <typename T>
 446         static inline typename Size<T>::Type
 447         _clearSpace_(
 448                 T & seq,
 449                 typename Size<T>::Type size,
 450                 typename Size<T>::Type limit)
 451         {
 452                 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
 453                 if (limit < size)
 454                 {
 455 SEQAN_CHECKPOINT
 456                         size = limit;
 457                 }
 458                 typename Size<T>::Type old_capacity = capacity(seq);
 459                 typename Value<T>::Type * old_array = _reallocateStorage(seq, size, limit, TExpand());
 460                 if (old_array)
 461                 {
 462                         _deallocateStorage(seq, old_array, old_capacity);
 463                 }
 464                 _setLength(seq, size);
 465                 return size;
 466         }
 467
 468         template <typename T>
 469         static typename Size<T>::Type
 470         _clearSpace_(
 471                 T & seq,
 472                 typename Size<T>::Type size,
 473                 typename Size<T>::Type start,
 474                 typename Size<T>::Type end)
 475         {
 476                 typename Size<T>::Type old_length = length(seq);
 477                 typename Size<T>::Type removed_size = end - start;
 478                 typename Size<T>::Type new_length = old_length - removed_size + size;
 479
 480                 typename Size<T>::Type old_capacity = capacity(seq);
 481                 typename Value<T>::Type * old_array = _reallocateStorage(seq, new_length, TExpand());
 482                 typename Value<T>::Type * seq_array = begin(seq);
 483
 484                 if (old_array)
 485                 {
 486 SEQAN_CHECKPOINT
 487                         arrayConstructMove(old_array, old_array + start, seq_array);
 488                         arrayConstructMove(old_array + end, old_array + old_length, seq_array + start + size);
 489                         _deallocateStorage(seq, old_array, old_capacity);
 490                 }
 491                 else
 492                 {
 493 SEQAN_CHECKPOINT
 494                         arrayClearSpace(seq_array + start, old_length - start, removed_size, size);
 495                 }
 496
 497                 _setLength(seq, new_length);
 498
 499                 return size;
 500         }
 501
 502         template <typename T>
 503         static typename Size<T>::Type
 504         _clearSpace_(
 505                 T & seq,
 506                 typename Size<T>::Type size,
 507                 typename Size<T>::Type start,
 508                 typename Size<T>::Type end,
 509                 typename Size<T>::Type limit)
 510         {
 511                 typename Size<T>::Type old_length = length(seq);
 512                 typename Size<T>::Type removed_size = end - start;
 513                 typename Size<T>::Type need_length = old_length - removed_size + size;
 514
 515                 typename Size<T>::Type new_length = need_length;
 516                 typename Size<T>::Type length_to_copy = old_length;
 517                 if (limit < need_length)
 518                 {
 519 SEQAN_CHECKPOINT
 520                         new_length = limit;
 521                         length_to_copy = new_length - size + removed_size;
 522                 }
 523
 524                 bool keep_second_part = (new_length > start + size);
 525
 526                 typename Size<T>::Type old_capacity = capacity(seq);
 527                 typename Value<T>::Type * old_array = _reallocateStorage(seq, new_length, limit, TExpand());
 528                 typename Value<T>::Type * seq_array = begin(seq);
 529
 530                 if (old_array)
 531                 {//new buffer allocated
 532                  //so old_length < limit, so start <= limit
 533                         arrayConstructMove(old_array, old_array + start, seq_array);
 534                         if (keep_second_part)
 535                         {
 536                                 arrayConstructMove(old_array + end, old_array + length_to_copy, seq_array + start + size);
 537                         }
 538                         _deallocateStorage(seq, old_array, old_capacity);
 539                 }
 540                 else
 541                 {
 542                         if (keep_second_part)
 543                         {
 544                                 arrayClearSpace(seq_array + start, length_to_copy - start, end - start, size);
 545                                 if (length_to_copy < old_length)
 546                                 {
 547                                         arrayDestruct(seq_array + length_to_copy, seq_array + old_length);
 548                                 }
 549                         }
 550                         else
 551                         {
 552                                 arrayDestruct(seq_array + start, seq_array + old_length);
 553                         }
 554                 }
 555
 556                 _setLength(seq, new_length);
 557
 558                 if (keep_second_part) return size;
 559                 else if (new_length > start) return new_length - start;
 560                 else return 0;
 561         }
 562
 563 /*
 564         template <typename T>
 565         static inline typename Size<T>::Type
 566         _clearSpace_(
 567                 T & seq,
 568                 typename Size<T>::Type size,
 569                 typename Iterator<T>::Type start,
 570                 typename Iterator<T>::Type end)
 571         {
 572                 typename Iterator<T>::Type seq_begin = begin(seq);
 573                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, TExpand());
 574         }
 575
 576         template <typename T>
 577         static inline typename Size<T>::Type
 578         _clearSpace_(
 579                 T & seq,
 580                 typename Size<T>::Type size,
 581                 typename Iterator<T>::Type start,
 582                 typename Iterator<T>::Type end,
 583                 typename Size<T>::Type limit)
 584         {
 585                 typename Iterator<T>::Type seq_begin = begin(seq);
 586                 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, TExpand());
 587         }
 588 */
 589 };
 590
 591 //____________________________________________________________________________
 592
 593 template <>
 594 struct _ClearSpace_String_Base_<Exact>:
 595         _ClearSpace_Expand_String_Base_<Exact>
 596 {
 597 };
 598
 599 //____________________________________________________________________________
 600
 601 template <>
 602 struct _ClearSpace_String_Base_<Generous>:
 603         _ClearSpace_Expand_String_Base_<Generous>
 604 {
 605 };
 606
 607 //____________________________________________________________________________
 608 /**
 609 .Internal._clearSpace:
 610 ..cat:Functions
 611 ..summary:Makes space in container
 612 ..signature:_clearSpace(object, size [, pos_begin, pos_end] [, limit], resize_tag)
 613 ..param.object:The container.
 614 ..param.size:Length of the freed space.
 615 ..param.pos_begin:Position of the first item in $object$ that is to be destroyed. (optional)
 616 ..param.pos_end:Position behind the last item in $object$ that is to be destroyed. (optional)
 617 ...remarks:If $pos_end == pos_begin$, no item in $object$ will be destroyed.
 618 ..param.limit:Maximal length $object$ can get after this operation. (optional)
 619 ..param.resize_tag:Strategy that is applied if $object$ has not enough capacity to store the complete content.
 620 ..returns:The number of free characters.
 621 ...remarks:Depeding on the @Tag.Overflow Strategy.overflow strategy@ specified by $resize_tag$,
 622 this could be $size$ or less than $size$ if $object$ has not enough @Function.capacity@.
 623 ..remarks:This function is similar to @Function.resizeSpace@ and @Function.fillSpace@.
 624 The main difference is that $_clearSpace$ does not construct objects in the new created space.
 625 */
 626 template<typename TValue, typename TSpec, typename TSize, typename TExpand>
 627 inline typename Size< String<TValue, TSpec> >::Type
 628 _clearSpace(String<TValue, TSpec> & me,
 629                 TSize size,
 630                 Tag<TExpand> const)
 631 {
 632 SEQAN_CHECKPOINT
 633         return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size);
 634 }
 635
 636 template<typename TValue, typename TSpec, typename TSize, typename TExpand>
 637 inline typename Size< String<TValue, TSpec> >::Type
 638 _clearSpace(String<TValue, TSpec> & me,
 639                 TSize size,
 640                 TSize limit,
 641                 Tag<TExpand> const)
 642 {
 643 SEQAN_CHECKPOINT
 644         return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, limit);
 645 }
 646
 647 template<typename TValue, typename TSpec, typename TSize, typename TPosition, typename TExpand>
 648 inline typename Size< String<TValue, TSpec> >::Type
 649 _clearSpace(String<TValue, TSpec> & me,
 650                         TSize size,
 651                         TPosition pos_begin,
 652                         TPosition pos_end,
 653                         Tag<TExpand> const)
 654 {
 655 SEQAN_CHECKPOINT
 656         return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end);
 657 }
 658
 659 template<typename TValue, typename TSpec, typename TSize, typename TPosition, typename TExpand>
 660 inline typename Size< String<TValue, TSpec> >::Type
 661 _clearSpace(String<TValue, TSpec> & me,
 662                         TSize size,
 663                         TPosition pos_begin,
 664                         TPosition pos_end,
 665                         TSize limit,
 666                         Tag<TExpand> const)
 667 {
 668 SEQAN_CHECKPOINT
 669         return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end, limit);
 670 }
 671
 672 //////////////////////////////////////////////////////////////////////////////
 673
 674 /**
 675 .Function.resizeSpace.param.object.type:Class.String
 676 */
 677
 678 template<typename TValue, typename TSpec, typename TPosition, typename TExpand>
 679 inline typename Size< String<TValue, TSpec> >::Type
 680 resizeSpace(String<TValue, TSpec> & me,
 681                         typename Size< String<TValue, TSpec> >::Type size,
 682                         TPosition pos_begin,
 683                         TPosition pos_end,
 684                         Tag<TExpand> const tag)
 685 {
 686 SEQAN_CHECKPOINT
 687         typename Size<String<TValue, TSpec> >::Type ret_ =_clearSpace(me, size, pos_begin, pos_end, tag);
 688         arrayConstruct(iter(me, pos_begin), iter(me, pos_begin) + ret_);
 689         return ret_;
 690 }
 691
 692 template<typename TValue, typename TSpec, typename TPosition, typename TExpand>
 693 inline typename Size< String<TValue, TSpec> >::Type
 694 resizeSpace(String<TValue, TSpec> & me,
 695                         typename Size< String<TValue, TSpec> >::Type size,
 696                         TPosition pos_begin,
 697                         TPosition pos_end,
 698                         typename Size< String<TValue, TSpec> >::Type limit,
 699                         Tag<TExpand> const tag)
 700 {
 701 SEQAN_CHECKPOINT
 702         typename Size<String<TValue, TSpec> >::Type ret_ =_clearSpace(me, size, pos_begin, pos_end, limit, tag);
 703         arrayConstruct(iter(me, pos_begin), iter(me, pos_begin) + ret_);
 704         return ret_;
 705 }
 706
 707 //////////////////////////////////////////////////////////////////////////////
 708 // assignValue (2)
 709 //////////////////////////////////////////////////////////////////////////////
 710
 711 template <typename TValue, typename TSpec, typename TValue2>
 712 inline void
 713 assignValue(String<TValue, TSpec> & me,
 714                         TValue2 const & _value)
 715 {
 716 //      assign(me, toString(_value)); ???TODO
 717 }
 718
 719 //???TODO: moveValue (2)
 720
 721 //////////////////////////////////////////////////////////////////////////////
 722 // assign
 723 //////////////////////////////////////////////////////////////////////////////
 724
 725 ///.Function.assign.param.target.type:Class.String
 726 ///.Function.assign.param.source.type:Class.String
 727
 728 //overload of binary version for strings:
 729
 730 template<typename TTargetValue, typename TTargetSpec, typename TSource>
 731 inline void
 732 assign(String<TTargetValue, TTargetSpec> & target,
 733           TSource & source)
 734 {
 735 SEQAN_CHECKPOINT
 736         typedef String<TTargetValue, TTargetSpec> TTarget;
 737         assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
 738 }
 739 template<typename TTargetValue, typename TTargetSpec, typename TSource>
 740 inline void
 741 assign(String<TTargetValue, TTargetSpec> & target,
 742           TSource const & source)
 743 {
 744 SEQAN_CHECKPOINT
 745         typedef String<TTargetValue, TTargetSpec> TTarget;
 746         assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
 747 }
 748
 749 //////////////////////////////////////////////////////////////////////////////
 750
 751 template <typename TExpand>
 752 struct _Assign_String
 753 {
 754         template <typename TTarget, typename TSource>
 755         static inline void
 756         assign_(
 757                 TTarget & target,
 758                 TSource & source)
 759         {
 760                 if (!id(source) || !shareResources(target, source))
 761                 {
 762 SEQAN_CHECKPOINT
 763                         typename Size<TTarget>::Type part_length = _clearSpace(target, length(source), TExpand());
 764                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()));
 765                 }
 766                 else
 767                 {
 768 SEQAN_CHECKPOINT
 769                         if ((void *) &target == (void *) &source) return;
 770
 771                         typename _TempCopy<TSource>::Type temp(source, length(source));
 772                         assign(target, temp, TExpand());
 773                 }
 774         }
 775
 776         template <typename TTarget, typename TSource>
 777         static inline void
 778         assign_(
 779                 TTarget & target,
 780                 TSource & source,
 781                 typename Size<TTarget>::Type limit)
 782         {
 783                 if (!id(source) || !shareResources(target, source))
 784                 {
 785 SEQAN_CHECKPOINT
 786                         typename Size<TTarget>::Type part_length = _clearSpace(target, typename Size<TTarget>::Type(length(source)), limit, TExpand());
 787                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()));
 788                 }
 789                 else
 790                 {
 791 SEQAN_CHECKPOINT
 792                         if ((void *) &target == (void *) &source) return;
 793
 794                         typename Size<TTarget>::Type source_length = length(source);
 795                         if (source_length > limit) source_length = limit;
 796
 797                         typename _TempCopy<TSource>::Type temp(source, source_length);
 798                         assign(target, temp, TExpand());
 799                 }
 800         }
 801 };
 802
 803 //////////////////////////////////////////////////////////////////////////////
 804
 805 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
 806 inline void
 807 assign(String<TTargetValue, TTargetSpec> & target,
 808            TSource const & source,
 809            Tag<TExpand> const)
 810 {
 811         typedef String<TTargetValue, TTargetSpec> TTarget;
 812         _Assign_String<Tag<TExpand> const>::assign_(target, source);
 813 }
 814 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TSize, typename TExpand>
 815 inline void
 816 assign(String<TTargetValue, TTargetSpec> & target,
 817            TSource const & source,
 818            TSize limit,
 819            Tag<TExpand> const)
 820 {
 821         typedef String<TTargetValue, TTargetSpec> TTarget;
 822         _Assign_String<Tag<TExpand> const>::assign_(target, source, limit);
 823 }
 824
 825 //____________________________________________________________________________
 826 //this variant is a workaround for the "const array"-bug of VC++
 827
 828 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
 829 inline void
 830 assign(String<TTargetValue, TTargetSpec> & target,
 831            TSourceValue const * source,
 832            Tag<TExpand> const)
 833 {
 834         typedef String<TTargetValue, TTargetSpec> TTarget;
 835         _Assign_String<Tag<TExpand> const>::assign_(target, source);
 836 }
 837 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TSize, typename TExpand>
 838 inline void
 839 assign(String<TTargetValue, TTargetSpec> & target,
 840            TSourceValue const * source,
 841            TSize limit,
 842            Tag<TExpand> const)
 843 {
 844         typedef String<TTargetValue, TTargetSpec> TTarget;
 845         _Assign_String<Tag<TExpand> const>::assign_(target, source, limit);
 846 }
 847
 848 //////////////////////////////////////////////////////////////////////////////
 849 // move
 850 //////////////////////////////////////////////////////////////////////////////
 851
 852 //____________________________________________________________________________
 853 //implementation of move for contiguous sequences
 854 //note: there is a problem, if sizeof(TSourceValue) and sizeof(TTargetValue) are not a multiple
 855 //      of each other, since in this case the correct size cannot be determined afterwards
 856 //      when calling the deallocate function.
 857 //      ???TODO
 858 template <typename TTarget, typename TSource>
 859 void
 860 _moveContiguous(TTarget & target,
 861                                 TSource & source)
 862 {
 863         typedef typename Value<TSource>::Type TSourceValue;
 864         typedef typename Value<TTarget>::Type TTargetValue;
 865
 866         clear(target);
 867
 868         typename Iterator<TSource, Standard>::Type source_begin = begin(source, Standard());
 869         typename Iterator<TTarget, Standard>::Type target_begin = (typename Iterator<TTarget, Standard>::Type) begin(source, Standard());
 870
 871         typename Size<TTarget>::Type size = sizeof(TSourceValue) * capacity(source);
 872         if (size >=  sizeof(TTargetValue))
 873         {
 874 SEQAN_CHECKPOINT
 875                 if (sizeof(TSourceValue) <= 2) ++size; //regard the "end of string termination" case
 876                 typename Size<TTarget>::Type target_capacity = size / sizeof(TTargetValue);
 877                 if (sizeof(TTargetValue) <= 2) --target_capacity; //regard the "end of string termination" case
 878
 879                 typename Size<TTarget>::Type target_length = length(source);
 880                 if (target_length > target_capacity)
 881                 {
 882                         target_length = target_capacity;
 883                 }
 884
 885                 if (sizeof(TSourceValue) >= sizeof(TTargetValue))
 886                 {
 887                         arrayMoveForward(source_begin, source_begin + target_length, target_begin);
 888                 }
 889                 else
 890                 {
 891                         arrayMoveBackward(source_begin, source_begin + target_length, target_begin);
 892                 }
 893
 894                 _setBegin(target, target_begin);
 895                 _setLength(target, target_length);
 896                 _setCapacity(target, target_capacity);
 897
 898                 _setBegin(source, 0);
 899                 _setLength(source, 0);
 900                 _setCapacity(source, 0);
 901         }
 902         else
 903         {
 904                 clear(source);
 905         }
 906 }
 907 //____________________________________________________________________________
 908
 909 //overload of binary version for strings:
 910
 911 template<typename TTargetValue, typename TTargetSpec, typename TSource>
 912 inline void
 913 move(String<TTargetValue, TTargetSpec> & target,
 914          TSource & source)
 915 {
 916 SEQAN_CHECKPOINT
 917         typedef String<TTargetValue, TTargetSpec> TTarget;
 918         move(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
 919 }
 920 template<typename TTargetValue, typename TTargetSpec, typename TSource>
 921 inline void
 922 move(String<TTargetValue, TTargetSpec> & target,
 923          TSource const & source)
 924 {
 925 SEQAN_CHECKPOINT
 926         typedef String<TTargetValue, TTargetSpec> TTarget;
 927         move(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
 928 }
 929
 930 //____________________________________________________________________________
 931
 932 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TTag>
 933 inline void
 934 move(String<TTargetValue, TTargetSpec> & target,
 935          TSource & source,
 936          Tag<TTag> const tag)
 937 {
 938 SEQAN_CHECKPOINT
 939         assign(target, source, tag);
 940 }
 941
 942 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TTag>
 943 inline void
 944 move(String<TTargetValue, TTargetSpec> & target,
 945          TSource const & source,
 946          Tag<TTag> const tag)
 947 {
 948 SEQAN_CHECKPOINT
 949         assign(target, source, tag);
 950 }
 951
 952 //////////////////////////////////////////////////////////////////////////////
 953 // valueConstructMove:
 954 // it is usually better for strings to default construct and move instead of
 955 // copy construct strings
 956
 957 /*
 958 template <typename TIterator, typename TValue, typename TSpec>
 959 inline void
 960 valueConstructMove(TIterator it,
 961                                    String<TValue, TSpec> const & value)
 962 {
 963         valueConstruct(it);
 964         move(*it, value);
 965 }
 966 */
 967
 968 //////////////////////////////////////////////////////////////////////////////
 969 // append
 970 //////////////////////////////////////////////////////////////////////////////
 971
 972 ///.Function.append.param.target.type:Class.String
 973 ///.Function.append.param.source.type:Class.String
 974
 975 template <typename TExpand>
 976 struct _Append_String
 977 {
 978         template <typename TTarget, typename TSource>
 979         static inline void
 980         append_(TTarget & target,
 981                         TSource & source)
 982         {
 983                 if (!id(source) || !shareResources(target, source))
 984                 {
 985 SEQAN_CHECKPOINT
 986                         typename Size<TTarget>::Type target_length = length(target);
 987                         typename Size<TTarget>::Type part_length = _clearSpace(target, length(source), target_length, target_length, TExpand());
 988                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()) + target_length);
 989                 }
 990                 else
 991                 {
 992 SEQAN_CHECKPOINT
 993                         typename _TempCopy<TSource>::Type temp(source, length(source));
 994                         assign(target, temp, TExpand());
 995                 }
 996         }
 997
 998         template <typename TTarget, typename TSource>
 999         static inline void
1000         append_(TTarget & target,
1001                         TSource & source,
1002                         typename Size<TTarget>::Type limit)
1003         {
1004                 typename Iterator<TTarget, Standard>::Type target_begin = begin(target, Standard());
1005                 if (!id(source) || !shareResources(target, source))
1006                 {
1007 SEQAN_CHECKPOINT
1008                         typename Size<TTarget>::Type target_length = length(target);
1009                         typename Size<TTarget>::Type part_length = _clearSpace(target, length(source), target_length, target_length, limit, TExpand());
1010                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()) + target_length);
1011                 }
1012                 else
1013                 {
1014                         typename Size<TTarget>::Type target_length = length(target);
1015                         if (target_length >= limit)
1016                         {
1017 SEQAN_CHECKPOINT
1018                                 arrayDestruct(target_begin + limit, target_begin + target_length);
1019                                 _setLength(target, limit);
1020                         }
1021                         else
1022                         {
1023 SEQAN_CHECKPOINT
1024                                 limit -= target_length;
1025                                 typename Size<TTarget>::Type source_length = length(source) ;
1026                                 if (source_length > limit) source_length = limit;
1027
1028                                 typename _TempCopy<TSource>::Type temp(source, source_length);
1029                                 append(target, temp, TExpand());
1030                         }
1031                 }
1032         }
1033 };
1034
1035 //////////////////////////////////////////////////////////////////////////////
1036
1037 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1038 inline void
1039 append(String<TTargetValue, TTargetSpec> & target,
1040            TSource const & source,
1041            Tag<TExpand> const)
1042 {
1043 SEQAN_CHECKPOINT
1044         typedef String<TTargetValue, TTargetSpec> TTarget;
1045         _Append_String<Tag<TExpand> const>::append_(target, source);
1046 }
1047
1048 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1049 inline void
1050 append(String<TTargetValue, TTargetSpec> & target,
1051            TSource const & source,
1052            typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1053            Tag<TExpand> const)
1054 {
1055 SEQAN_CHECKPOINT
1056         typedef String<TTargetValue, TTargetSpec> TTarget;
1057         _Append_String<Tag<TExpand> const>::append_(target, source, limit);
1058 }
1059
1060 //____________________________________________________________________________
1061 //this variant is a workaround for the "const array"-bug of VC++
1062
1063 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1064 inline void
1065 append(String<TTargetValue, TTargetSpec> & target,
1066            TSourceValue * source,
1067            Tag<TExpand> const)
1068 {
1069 SEQAN_CHECKPOINT
1070         typedef String<TTargetValue, TTargetSpec> TTarget;
1071         _Append_String<Tag<TExpand> const>::append_(target, source);
1072 }
1073
1074 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1075 inline void
1076 append(String<TTargetValue, TTargetSpec> & target,
1077            TSourceValue * source,
1078            typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1079            Tag<TExpand> const)
1080 {
1081 SEQAN_CHECKPOINT
1082         typedef String<TTargetValue, TTargetSpec> TTarget;
1083         _Append_String<Tag<TExpand> const>::append_(target, source, limit);
1084 }
1085
1086
1087
1088 //////////////////////////////////////////////////////////////////////////////
1089 // appendValue
1090 //////////////////////////////////////////////////////////////////////////////
1091
1092 template <typename TExpand>
1093 struct _Append_Value_2_String
1094 {
1095         template <typename T, typename TValue>
1096         static inline void
1097         appendValue_(T & me,
1098                                 TValue & _value)
1099         {
1100 SEQAN_CHECKPOINT
1101                 typename Position<T>::Type me_length = length(me);
1102                 if (capacity(me) <= me_length)
1103                 {
1104                         typename Value<T>::Type temp_copy(_value); //temp copy because resize could invalidate _value
1105                         typename Size<T>::Type new_length = resize(me, me_length + 1, TExpand());
1106                         if (me_length < new_length)
1107                         {
1108                                 valueConstruct(begin(me) + me_length, temp_copy); //??? this should be valueMoveConstruct
1109                         }
1110                 }
1111                 else
1112                 {
1113                         valueConstruct(begin(me, Standard()) + me_length, _value);
1114                         _setLength(me, me_length + 1);
1115                 }
1116         }
1117 };
1118
1119 //____________________________________________________________________________
1120
1121 template <typename TTargetValue, typename TTargetSpec, typename TValue, typename TExpand>
1122 inline void
1123 appendValue(String<TTargetValue, TTargetSpec> & me,
1124                         TValue const & _value,
1125                         Tag<TExpand> const)
1126 {
1127 SEQAN_CHECKPOINT
1128         _Append_Value_2_String<Tag<TExpand> const>::appendValue_(me, _value);
1129 }
1130
1131 //////////////////////////////////////////////////////////////////////////////
1132 // insertValue
1133 //////////////////////////////////////////////////////////////////////////////
1134 /**
1135 .Function.insertValue:
1136 */
1137
1138 template <typename TExpand>
1139 struct _Insert_Value_2_String
1140 {
1141         template <typename T, typename TPosition, typename TValue>
1142         static inline void
1143         insertValue_(T & me,
1144                                 TPosition pos,
1145                                 TValue & _value)
1146         {
1147 SEQAN_CHECKPOINT
1148                 typename Value<T>::Type temp_copy = _value; //temp copy because resizeSpace could invalidate _value
1149                 resizeSpace(me, 1, pos, pos, TExpand());
1150                 if ((typename Size<T>::Type) pos < length(me))
1151                 {
1152                         moveValue(me, pos, temp_copy);
1153                 }
1154         }
1155 };
1156
1157 //____________________________________________________________________________
1158
1159 template <typename TTargetValue, typename TTargetSpec, typename TPosition, typename TValue, typename TExpand>
1160 inline void
1161 insertValue(String<TTargetValue, TTargetSpec> & me,
1162                         TPosition pos,
1163                         TValue const & _value,
1164                         Tag<TExpand> const)
1165 {
1166 SEQAN_CHECKPOINT
1167         _Insert_Value_2_String<Tag<TExpand> const>::insertValue_(me, pos, _value);
1168 }
1169
1170 //////////////////////////////////////////////////////////////////////////////
1171 // replace
1172 //////////////////////////////////////////////////////////////////////////////
1173
1174 ///.Function.replace.param.target.type:Class.String
1175 ///.Function.replace.param.source.type:Class.String
1176
1177 template <typename TExpand>
1178 struct _Replace_String
1179 {
1180         template <typename TTarget, typename TSource>
1181         static inline void
1182         replace_(TTarget & target,
1183                          typename Size<TTarget>::Type pos_begin,
1184                          typename Size<TTarget>::Type pos_end,
1185                          TSource & source)
1186         {
1187                 if (!id(source) || !shareResources(target, source))
1188                 {
1189 SEQAN_CHECKPOINT
1190                         typename Size<TTarget>::Type part_length = _clearSpace(target, length(source), pos_begin, pos_end, TExpand());
1191                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()) + pos_begin);
1192                 }
1193                 else
1194                 {
1195 SEQAN_CHECKPOINT
1196                         typename _TempCopy<TSource>::Type temp(source, length(source));
1197                         replace(target, pos_begin, pos_end, temp, TExpand());
1198                 }
1199         }
1200
1201         template <typename TTarget, typename TSource>
1202         static inline void
1203         replace_(TTarget & target,
1204                          typename Size<TTarget>::Type pos_begin,
1205                          typename Size<TTarget>::Type pos_end,
1206                          TSource & source,
1207                          typename Size<TTarget>::Type limit)
1208         {
1209                 if (!id(source) || !shareResources(target, source))
1210                 {
1211 SEQAN_CHECKPOINT
1212                         typename Size<TTarget>::Type part_length = _clearSpace(target, length(source), pos_begin, pos_end, limit, TExpand());
1213                         arrayConstructCopy(begin(source, Standard()), begin(source, Standard()) + part_length, begin(target, Standard()) + pos_begin);
1214                 }
1215                 else
1216                 {
1217                         if (pos_begin >= limit)
1218                         {
1219 SEQAN_CHECKPOINT
1220                                 arrayDestruct(begin(target) + limit, end(target));
1221                                 _setLength(target, limit);
1222                         }
1223                         else
1224                         {
1225 SEQAN_CHECKPOINT
1226                                 limit -= pos_begin;
1227                                 typename Size<TTarget>::Type source_length = length(source) ;
1228                                 if (source_length > limit) source_length = limit;
1229
1230                                 typename _TempCopy<TSource>::Type temp(source, source_length);
1231                                 replace(target, pos_begin, pos_end, temp, limit, TExpand());
1232                         }
1233                 }
1234         }
1235
1236 };
1237
1238 //////////////////////////////////////////////////////////////////////////////
1239
1240 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1241 inline void
1242 replace(String<TTargetValue, TTargetSpec> & target,
1243                  typename Size< String<TTargetValue, TTargetSpec> >::Type pos_begin,
1244                  typename Size< String<TTargetValue, TTargetSpec> >::Type pos_end,
1245                  TSource const & source,
1246                  Tag<TExpand> const)
1247 {
1248 SEQAN_CHECKPOINT
1249         typedef String<TTargetValue, TTargetSpec> TTarget;
1250         _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source);
1251 }
1252
1253 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1254 inline void
1255 replace(String<TTargetValue, TTargetSpec> & target,
1256                  typename Size< String<TTargetValue, TTargetSpec> >::Type pos_begin,
1257                  typename Size< String<TTargetValue, TTargetSpec> >::Type pos_end,
1258                  TSource const & source,
1259                  typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1260                  Tag<TExpand> const)
1261 {
1262 SEQAN_CHECKPOINT
1263         typedef String<TTargetValue, TTargetSpec> TTarget;
1264         _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source, limit);
1265 }
1266
1267 //____________________________________________________________________________
1268 //this variant is a workaround for the "const array"-bug of VC++
1269
1270 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1271 inline void
1272 replace(String<TTargetValue, TTargetSpec> & target,
1273                 typename Size< String<TTargetValue, TTargetSpec> >::Type pos_begin,
1274                 typename Size< String<TTargetValue, TTargetSpec> >::Type pos_end,
1275                 TSourceValue const * source,
1276                 Tag<TExpand> const)
1277 {
1278 SEQAN_CHECKPOINT
1279         typedef String<TTargetValue, TTargetSpec> TTarget;
1280         _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source);
1281 }
1282
1283 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1284 inline void
1285 replace(String<TTargetValue, TTargetSpec> & target,
1286                 typename Size< String<TTargetValue, TTargetSpec> >::Type pos_begin,
1287                 typename Size< String<TTargetValue, TTargetSpec> >::Type pos_end,
1288                 TSourceValue const * source,
1289                 typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1290                 Tag<TExpand> const)
1291 {
1292 SEQAN_CHECKPOINT
1293         typedef String<TTargetValue, TTargetSpec> TTarget;
1294         _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source, limit);
1295 }
1296
1297 //////////////////////////////////////////////////////////////////////////////
1298 // handling of iterators as begin and end
1299
1300 /*
1301 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1302 inline void
1303 replace(String<TTargetValue, TTargetSpec> & target,
1304                 typename Iterator< String<TTargetValue, TTargetSpec>, Rooted >::Type pos_begin,
1305                 typename Iterator< String<TTargetValue, TTargetSpec>, Rooted >::Type pos_end,
1306                 TSource & source,
1307                 Tag<TExpand> const tag)
1308 {
1309         replace(target, position(pos_begin), position(pos_end), source, tag);
1310 }
1311
1312 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1313 inline void
1314 replace(String<TTargetValue, TTargetSpec> & target,
1315                 typename Iterator< String<TTargetValue, TTargetSpec>, Rooted >::Type pos_begin,
1316                 typename Iterator< String<TTargetValue, TTargetSpec>, Rooted >::Type pos_end,
1317                 TSource & source,
1318                 typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1319                 Tag<TExpand> const tag)
1320 {
1321         replace(target, position(pos_begin), position(pos_end), source, limit, tag);
1322 }
1323 */
1324
1325 //////////////////////////////////////////////////////////////////////////////
1326 /**
1327 .Internal._reallocateStorage:
1328 ..cat:Functions
1329 ..summary:Allocates a new buffer if needed.
1330 ..signature:_reallocateStorage(object, new_capacity, resize_tag)
1331 ..param.object:A container for which the buffer is reallocated.
1332 ...type:Class.String
1333 ..param.new_capacity:The capacity $object$ will get after reallocating the buffer.
1334 ..param.resize_tag:Strategy that is used for changing the capacity.
1335 ..returns:Returns the old buffer, if a new buffer has been allocated, $0$ otherwise.
1336 ..remarks:This function only allocates a new buffer if the current capacity is less then $new_capacity$.
1337 A new buffer is not filled with any content, all copy operations must be done by the caller.
1338 ..remarks:If $object$ never had a buffer, or the buffer is not changed by the function,
1339 the returned pointer is 0.
1340 */
1341
1342 template <typename TValue, typename TSpec>
1343 inline typename Value<String<TValue, TSpec> >::Type *
1344 _reallocateStorage(
1345         String<TValue, TSpec> & me,
1346         typename Size< String<TValue, TSpec> >::Type new_capacity,
1347         Exact)
1348 {
1349         if (new_capacity <= capacity(me)) return 0;
1350         else
1351         {
1352 SEQAN_CHECKPOINT
1353                 return _allocateStorage(me, new_capacity);
1354         }
1355 }
1356
1357 template <typename TValue, typename TSpec>
1358 inline typename Value<String<TValue, TSpec> >::Type *
1359 _reallocateStorage(
1360         String<TValue, TSpec> & me,
1361         typename Size< String<TValue, TSpec> >::Type new_capacity,
1362         typename Size< String<TValue, TSpec> >::Type limit,
1363         Exact)
1364 {
1365         if (new_capacity <= capacity(me)) return 0;
1366         else
1367         {
1368 SEQAN_CHECKPOINT
1369                 if (new_capacity > limit) new_capacity = limit;
1370                 return _allocateStorage(me, new_capacity);
1371         }
1372 }
1373
1374 template <typename TValue, typename TSpec>
1375 inline typename Value<String<TValue, TSpec> >::Type *
1376 _reallocateStorage(
1377         String<TValue, TSpec> & me,
1378         typename Size< String<TValue, TSpec> >::Type new_capacity,
1379         Generous)
1380 {
1381         if (new_capacity <= capacity(me)) return 0;
1382         else
1383         {
1384 SEQAN_CHECKPOINT
1385                 new_capacity = computeGenerousCapacity(me, new_capacity);
1386                 return _allocateStorage(me, new_capacity);
1387         }
1388 }
1389
1390 template <typename TValue, typename TSpec>
1391 inline typename Value<String<TValue, TSpec> >::Type *
1392 _reallocateStorage(
1393         String<TValue, TSpec> & me,
1394         typename Size< String<TValue, TSpec> >::Type new_capacity,
1395         typename Size< String<TValue, TSpec> >::Type limit,
1396         Generous)
1397 {
1398         if (new_capacity <= capacity(me)) return 0;
1399         else
1400         {
1401 SEQAN_CHECKPOINT
1402                 new_capacity = computeGenerousCapacity(me, new_capacity);
1403                 if (new_capacity > limit) new_capacity = limit;
1404                 return _allocateStorage(me, new_capacity);
1405         }
1406 }
1407
1408 //////////////////////////////////////////////////////////////////////////////
1409 ///.Function.resize.param.object.type:Class.String
1410
1411 template <typename TExpand>
1412 struct _Resize_String
1413 {
1414         template <typename T>
1415         static inline typename Size<T>::Type
1416         resize_(
1417                 T & me,
1418                 typename Size<T>::Type new_length)
1419         {
1420                 typedef typename Size<T>::Type TSize;
1421                 TSize me_length = length(me);
1422                 if (new_length < me_length)
1423                 {
1424 SEQAN_CHECKPOINT
1425                         arrayDestruct(begin(me, Standard()) + new_length, begin(me, Standard()) + me_length);
1426                 }
1427                 else
1428                 {
1429                         typename Size<T>::Type me_capacity = capacity(me);
1430                         if (new_length > me_capacity)
1431                         {
1432 SEQAN_CHECKPOINT
1433                                 TSize new_capacity = reserve(me, new_length, TExpand());
1434                                 if (new_capacity < new_length)
1435                                 {
1436                                         new_length = new_capacity;
1437                                 }
1438                         }
1439                         if (new_length > me_length)
1440                         {
1441 SEQAN_CHECKPOINT
1442                                 arrayConstruct(begin(me, Standard()) + me_length, begin(me, Standard()) + new_length);
1443                         }
1444                 }
1445
1446                 _setLength(me, new_length);
1447                 return new_length;
1448         }
1449 };
1450
1451 template <typename TValue, typename TSpec, typename TSize, typename TExpand>
1452 inline typename Size< String<TValue, TSpec> >::Type
1453 resize(
1454         String<TValue, TSpec> & me,
1455         TSize new_length,
1456         Tag<TExpand> const)
1457 {
1458 SEQAN_CHECKPOINT
1459         return _Resize_String<Tag<TExpand> const>::resize_(me, new_length);
1460 }
1461
1462 //////////////////////////////////////////////////////////////////////////////
1463
1464 ///.Function.fill.param.object.type:Class.String
1465
1466 template <typename TExpand>
1467 struct _Fill_String
1468 {
1469         template <typename T, typename TValue>
1470         static inline typename Size<T>::Type
1471         fill_(
1472                 T & me,
1473                 typename Size<T>::Type new_length,
1474                 TValue const & val)
1475         {
1476                 typename Size<T>::Type me_length = length(me);
1477                 if (new_length < me_length)
1478                 {
1479 SEQAN_CHECKPOINT
1480                         arrayDestruct(begin(me, Standard()) + new_length, begin(me, Standard()) + me_length);
1481                 }
1482                 else
1483                 {
1484                         typename Size<T>::Type me_capacity = capacity(me);
1485                         if (new_length > me_capacity)
1486                         {
1487 SEQAN_CHECKPOINT
1488                                 new_length = reserve(me, new_length, TExpand());
1489                         }
1490                         if (new_length > me_length)
1491                         {
1492 SEQAN_CHECKPOINT
1493                                 arrayConstruct(begin(me, Standard()) + me_length, begin(me, Standard()) + new_length, val);
1494                         }
1495                 }
1496
1497                 _setLength(me, new_length);
1498                 return new_length;
1499         }
1500 };
1501
1502 template <typename TValue, typename TSpec, typename TSize, typename TValue2, typename TExpand>
1503 inline TSize
1504 fill(String<TValue, TSpec> & me,
1505          TSize new_length,
1506          TValue2 const & val,
1507          Tag<TExpand> const)
1508 {
1509 SEQAN_CHECKPOINT
1510         return _Fill_String<Tag<TExpand> const>::fill_(me, new_length, val);
1511 }
1512
1513 //////////////////////////////////////////////////////////////////////////////
1514
1515 /*
1516 template <typename TLeftValue, typename TLeftSpec, typename TRightValue, typename TRightSpec>
1517 String<TLeftValue, TLeftSpec> const &
1518 operator += (String<TLeftValue, TLeftSpec> & left,
1519                          String<TRightValue, TRightSpec> const & right)
1520 {
1521         append(left, right);
1522         return left;
1523 }
1524
1525 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1526 String<TLeftValue, TLeftSpec> const &
1527 operator += (String<TLeftValue, TLeftSpec> & left,
1528                          TRight const & right)
1529 {
1530         append(left, right);
1531         return left;
1532 }
1533
1534 template <typename TLeft, typename TRightValue, typename TRightSpec>
1535 TLeft const &
1536 operator += (TLeft & left,
1537                          String<TRightValue, TRightSpec> const & right)
1538 {
1539         append(left, right);
1540         return left;
1541 }
1542 */
1543
1544 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1545 String<TLeftValue, TLeftSpec> const &
1546 operator += (String<TLeftValue, TLeftSpec> & left,
1547                          TRight const & right)
1548 {
1549 SEQAN_CHECKPOINT
1550         append(left, right);
1551         return left;
1552 }
1553
1554 //////////////////////////////////////////////////////////////////////////////
1555
1556 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1557 inline bool
1558 operator == (String<TLeftValue, TLeftSpec> const & left,
1559                         TRight const & right)
1560 {
1561 SEQAN_CHECKPOINT
1562         typename Comparator<String<TLeftValue, TLeftSpec> >::Type _lex(left, right);
1563     return isEqual(_lex);
1564 }
1565
1566 //////////////////////////////////////////////////////////////////////////////
1567
1568 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1569 inline bool
1570 operator !=(String<TLeftValue, TLeftSpec> const & left,
1571                         TRight const & right)
1572 {
1573 SEQAN_CHECKPOINT
1574         typename Comparator<String<TLeftValue, TLeftSpec> >::Type _lex(left, right);
1575     return isNotEqual(_lex);
1576 }
1577
1578 //////////////////////////////////////////////////////////////////////////////
1579
1580 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1581 inline bool
1582 operator < (String<TLeftValue, TLeftSpec> const & left,
1583                         TRight const & right)
1584 {
1585 SEQAN_CHECKPOINT
1586         return isLess(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1587 }
1588
1589 //////////////////////////////////////////////////////////////////////////////
1590
1591 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1592 inline bool
1593 operator <= (String<TLeftValue, TLeftSpec> const & left,
1594                          TRight const & right)
1595 {
1596 SEQAN_CHECKPOINT
1597         return isLessOrEqual(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1598 }
1599 //////////////////////////////////////////////////////////////////////////////
1600
1601 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1602 inline bool
1603 operator > (String<TLeftValue, TLeftSpec> const & left,
1604                 TRight const & right)
1605 {
1606 SEQAN_CHECKPOINT
1607         return isGreater(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1608 }
1609
1610 //////////////////////////////////////////////////////////////////////////////
1611
1612 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1613 inline bool
1614 operator >= (String<TLeftValue, TLeftSpec> const & left,
1615                 TRight const & right)
1616 {
1617 SEQAN_CHECKPOINT
1618         return isGreaterOrEqual(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1619 }
1620
1621 //////////////////////////////////////////////////////////////////////////////
1622 // stream operators
1623 //////////////////////////////////////////////////////////////////////////////
1624
1625 template <typename TStream, typename TValue, typename TSpec>
1626 inline TStream &
1627 operator << (TStream & target,
1628                          String<TValue, TSpec> const & source)
1629 {
1630 SEQAN_CHECKPOINT
1631         write(target, source);
1632         return target;
1633 }
1634
1635 //////////////////////////////////////////////////////////////////////////////
1636
1637 template <typename TStream, typename TValue, typename TSpec>
1638 inline TStream &
1639 operator >> (TStream & source,
1640                          String<TValue, TSpec> & target)
1641 {
1642 SEQAN_CHECKPOINT
1643         read(source, target);
1644         return source;
1645 }
1646
1647
1648 //////////////////////////////////////////////////////////////////////////////
1649
1650 /*
1651 //////////////////////////////////////////////////////////////////////////////
1652 // Converter
1653 //////////////////////////////////////////////////////////////////////////////
1654
1655 template <typename TTarget, typename TSource, typename TSpec>
1656 struct Value<String<Convert<TTarget, TSource>, TSpec> >:
1657         Value< String<TSource, TSpec> >
1658 {
1659 };
1660
1661 //////////////////////////////////////////////////////////////////////////////
1662
1663 template <typename T, typename TAccessor, typename TConverter>
1664 struct _AccessorConverter
1665 {
1666         typedef T Type;
1667 };
1668 template <typename T, typename TAccessor, typename TConverter>
1669 struct _AccessorConverter<T, TAccessor &, typename TConverter &>
1670 {
1671         typedef T & Type;
1672 };
1673
1674 template <typename TTarget, typename TSource, typename TSpec>
1675 struct GetValue<String<Converter<TTarget, TSource>, TSpec> >:
1676         _AccessorConverter<
1677                 TTarget,
1678                 typename GetValue<String<TSource, TSpec> >::Type,
1679                 typename Converter<TTarget, TSource>::Type
1680         >
1681 {
1682 };
1683 */
1684
1685 //////////////////////////////////////////////////////////////////////////////
1686
1687
1688
1689 //////////////////////////////////////////////////////////////////////////////
1690
1691 } //namespace SEQAN_NAMESPACE_MAIN
1692
1693 //////////////////////////////////////////////////////////////////////////////
1694
1695 #endif //#ifndef SEQAN_HEADER_...