1 /*==========================================================================
2 SeqAn - The Library for Sequence Analysis
4 ============================================================================
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.
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.
17 ============================================================================
18 $Id: string_base.h,v 1.1 2008/08/25 16:20:04 langmead Exp $
19 ==========================================================================*/
21 #ifndef SEQAN_HEADER_SEQUENCE_ARRAY_BASE_H
22 #define SEQAN_HEADER_SEQUENCE_ARRAY_BASE_H
25 namespace SEQAN_NAMESPACE_MAIN
28 //////////////////////////////////////////////////////////////////////////////
30 //////////////////////////////////////////////////////////////////////////////
33 template <typename TSpec = void>
37 //////////////////////////////////////////////////////////////////////////////
38 //////////////////////////////////////////////////////////////////////////////
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
53 template <typename TValue, typename TSpec = Alloc<> >
59 //////////////////////////////////////////////////////////////////////////////
61 //////////////////////////////////////////////////////////////////////////////
63 ///.Metafunction.Iterator.param.T.type:Class.String
65 //////////////////////////////////////////////////////////////////////////////
67 template <typename TValue, typename TSpec>
68 struct Value<String<TValue, TSpec> >
72 template <typename TValue, typename TSpec>
73 struct Value<String<TValue, TSpec> const >:
74 public Value<String<TValue, TSpec> >
78 //////////////////////////////////////////////////////////////////////////////
80 ///.Metafunction.Spec.param.T.type:Class.String
82 template <typename TValue, typename TSpec>
83 struct Spec<String<TValue, TSpec> >
87 template <typename TValue, typename TSpec>
88 struct Spec<String<TValue, TSpec> const>:
89 public Spec<String<TValue, TSpec> >
93 //////////////////////////////////////////////////////////////////////////////
95 ///.Metafunction.IsSequence.param.T.type:Class.String
97 template <typename TValue, typename TSpec>
98 struct IsSequence<String<TValue, TSpec> > {
100 enum { VALUE = true };
103 //////////////////////////////////////////////////////////////////////////////
104 // Returns a Class that can be used to store a temporary copy of a String
106 template <typename T>
109 typedef typename Value<T>::Type TValue;
110 typedef typename _RemoveConst<TValue>::Type TValue_NotConst;
111 typedef String<TValue_NotConst, Alloc<> > Type;
114 //////////////////////////////////////////////////////////////////////////////
116 //////////////////////////////////////////////////////////////////////////////
118 ///.Function.id.param.object.type:Class.String
119 ///.Function.empty.param.object.type:Class.String
120 ///.Function.capacity.param.object.type:Class.String
123 //////////////////////////////////////////////////////////////////////////////
126 ///.Function.shareResources.param.sequence1, sequence2.type:Class.String
128 template <typename TValue, typename TSpec>
130 shareResources(String<TValue, TSpec> const & obj1,
134 return (begin(obj1) >= &obj2) && (end(obj1) <= &obj2);
137 template <typename TValue, typename TSpec>
139 shareResources(TValue const & obj1,
140 String<TValue, TSpec> const & obj2)
143 return (begin(obj2) >= &obj1) && (end(obj2) <= &obj1);
146 //////////////////////////////////////////////////////////////////////////////
148 ///.Function.begin.param.object.type:Class.String
149 ///.Function.end.param.object.type:Class.String
150 //////////////////////////////////////////////////////////////////////////////
152 ///.Function.value.param.container.type:Class.String
154 template <typename TValue, typename TSpec, typename TPos>
155 inline typename Reference< String<TValue, TSpec> >::Type
156 value(String<TValue, TSpec> & me,
160 return *(begin(me, Standard()) + pos);
163 template <typename TValue, typename TSpec, typename TPos>
164 inline typename Reference< String<TValue, TSpec> const >::Type
165 value(String<TValue, TSpec> const & me,
169 return *(begin(me, Standard()) + pos);
172 //////////////////////////////////////////////////////////////////////////////
174 ///.Function.length.param.object.type:Class.String
176 template <typename TValue, typename TSpec>
177 inline typename Size< String<TValue, TSpec> const>::Type
178 length(String<TValue, TSpec> const & me)
181 return end(me, Standard()) - begin(me, Standard());
184 //////////////////////////////////////////////////////////////////////////////
189 ..summary:Resets an object.
190 ..signature:clear(object)
191 ..param.object:The object that will be resetted.
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
201 template <typename TValue, typename TSpec>
203 clear(String<TValue, TSpec> & me)
206 arrayDestruct(begin(me, Standard()), end(me, Standard()));
210 //////////////////////////////////////////////////////////////////////////////
212 template <typename TExpand>
213 struct _ClearSpace_String_Base_
217 //____________________________________________________________________________
220 struct _ClearSpace_String_Base_<Insist>
222 template <typename T>
223 static inline typename Size<T>::Type
226 typename Size<T>::Type size)
229 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
230 _setLength(seq, size);
234 template <typename T>
235 static inline typename Size<T>::Type
238 typename Size<T>::Type size,
239 typename Size<T>::Type limit)
241 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
247 _setLength(seq, size);
251 template <typename T>
252 static inline typename Size<T>::Type
255 typename Size<T>::Type size,
256 typename Size<T>::Type start,
257 typename Size<T>::Type end)
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);
266 template <typename T>
267 static typename Size<T>::Type
270 typename Size<T>::Type size,
271 typename Size<T>::Type start,
272 typename Size<T>::Type end,
273 typename Size<T>::Type limit)
275 typename Value<T>::Type * seq_buffer = begin(seq);
276 typename Size<T>::Type seq_length = length(seq);
278 if (limit > start + size)
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)
286 arrayDestruct(seq_buffer + limit, seq_buffer + new_length);
287 seq_length -= new_length - limit;
289 arrayClearSpace(seq_buffer + start, seq_length - start, end - start, size);
290 _setLength(seq, new_length);
296 arrayDestruct(seq_buffer + start, seq_buffer + seq_length);
297 _setLength(seq, limit);
298 if (limit > start) return limit - start;
303 template <typename T>
304 static inline typename Size<T>::Type
307 typename Size<T>::Type size,
308 typename Iterator<T>::Type start,
309 typename Iterator<T>::Type end)
311 typename Iterator<T>::Type seq_begin = begin(seq);
312 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, Insist());
315 template <typename T>
316 static inline typename Size<T>::Type
319 typename Size<T>::Type size,
320 typename Iterator<T>::Type start,
321 typename Iterator<T>::Type end,
322 typename Size<T>::Type limit)
324 typename Iterator<T>::Type seq_begin = begin(seq);
325 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, Insist());
331 //____________________________________________________________________________
335 struct _ClearSpace_String_Base_<Limit>
338 template <typename T>
339 static inline typename Size<T>::Type
342 typename Size<T>::Type size)
345 return _clearSpace(seq, size, capacity(seq), Insist());
348 template <typename T>
349 static inline typename Size<T>::Type
352 typename Size<T>::Type size,
353 typename Size<T>::Type limit)
355 typename Size<T>::Type seq_capacity = capacity(seq);
356 if (limit > seq_capacity)
359 limit = seq_capacity;
361 return _clearSpace(seq, size, limit, Insist());
364 template <typename T>
365 static inline typename Size<T>::Type
368 typename Size<T>::Type size,
369 typename Size<T>::Type start,
370 typename Size<T>::Type end)
373 return _clearSpace(seq, size, start, end, capacity(seq), Insist());
376 template <typename T>
377 static typename Size<T>::Type
380 typename Size<T>::Type size,
381 typename Size<T>::Type start,
382 typename Size<T>::Type end,
383 typename Size<T>::Type limit)
385 typename Size<T>::Type seq_capacity = capacity(seq);
386 if (limit > seq_capacity)
389 limit = seq_capacity;
391 return _clearSpace(seq, size, start, end, limit, Insist());
395 template <typename T>
396 static inline typename Size<T>::Type
399 typename Size<T>::Type size,
400 typename Iterator<T>::Type start,
401 typename Iterator<T>::Type end)
403 typename Iterator<T>::Type seq_begin = begin(seq);
404 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, Insist());
407 template <typename T>
408 static inline typename Size<T>::Type
411 typename Size<T>::Type size,
412 typename Iterator<T>::Type start,
413 typename Iterator<T>::Type end,
414 typename Size<T>::Type limit)
416 typename Iterator<T>::Type seq_begin = begin(seq);
417 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, Insist());
422 //____________________________________________________________________________
424 template <typename TExpand>
425 struct _ClearSpace_Expand_String_Base_
427 template <typename T>
428 static inline typename Size<T>::Type
431 typename Size<T>::Type size)
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());
439 _deallocateStorage(seq, old_array, old_capacity);
441 _setLength(seq, size);
445 template <typename T>
446 static inline typename Size<T>::Type
449 typename Size<T>::Type size,
450 typename Size<T>::Type limit)
452 arrayDestruct(begin(seq, Standard()), end(seq, Standard()));
458 typename Size<T>::Type old_capacity = capacity(seq);
459 typename Value<T>::Type * old_array = _reallocateStorage(seq, size, limit, TExpand());
462 _deallocateStorage(seq, old_array, old_capacity);
464 _setLength(seq, size);
468 template <typename T>
469 static typename Size<T>::Type
472 typename Size<T>::Type size,
473 typename Size<T>::Type start,
474 typename Size<T>::Type end)
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;
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);
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);
494 arrayClearSpace(seq_array + start, old_length - start, removed_size, size);
497 _setLength(seq, new_length);
502 template <typename T>
503 static typename Size<T>::Type
506 typename Size<T>::Type size,
507 typename Size<T>::Type start,
508 typename Size<T>::Type end,
509 typename Size<T>::Type limit)
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;
515 typename Size<T>::Type new_length = need_length;
516 typename Size<T>::Type length_to_copy = old_length;
517 if (limit < need_length)
521 length_to_copy = new_length - size + removed_size;
524 bool keep_second_part = (new_length > start + size);
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);
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)
536 arrayConstructMove(old_array + end, old_array + length_to_copy, seq_array + start + size);
538 _deallocateStorage(seq, old_array, old_capacity);
542 if (keep_second_part)
544 arrayClearSpace(seq_array + start, length_to_copy - start, end - start, size);
545 if (length_to_copy < old_length)
547 arrayDestruct(seq_array + length_to_copy, seq_array + old_length);
552 arrayDestruct(seq_array + start, seq_array + old_length);
556 _setLength(seq, new_length);
558 if (keep_second_part) return size;
559 else if (new_length > start) return new_length - start;
564 template <typename T>
565 static inline typename Size<T>::Type
568 typename Size<T>::Type size,
569 typename Iterator<T>::Type start,
570 typename Iterator<T>::Type end)
572 typename Iterator<T>::Type seq_begin = begin(seq);
573 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, TExpand());
576 template <typename T>
577 static inline typename Size<T>::Type
580 typename Size<T>::Type size,
581 typename Iterator<T>::Type start,
582 typename Iterator<T>::Type end,
583 typename Size<T>::Type limit)
585 typename Iterator<T>::Type seq_begin = begin(seq);
586 return _clearSpace(seq, size, start - seq_begin, end - seq_begin, limit, TExpand());
591 //____________________________________________________________________________
594 struct _ClearSpace_String_Base_<Exact>:
595 _ClearSpace_Expand_String_Base_<Exact>
599 //____________________________________________________________________________
602 struct _ClearSpace_String_Base_<Generous>:
603 _ClearSpace_Expand_String_Base_<Generous>
607 //____________________________________________________________________________
609 .Internal._clearSpace:
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.
626 template<typename TValue, typename TSpec, typename TSize, typename TExpand>
627 inline typename Size< String<TValue, TSpec> >::Type
628 _clearSpace(String<TValue, TSpec> & me,
633 return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size);
636 template<typename TValue, typename TSpec, typename TSize, typename TExpand>
637 inline typename Size< String<TValue, TSpec> >::Type
638 _clearSpace(String<TValue, TSpec> & me,
644 return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, limit);
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,
656 return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end);
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,
669 return _ClearSpace_String_Base_<Tag<TExpand> const>::_clearSpace_(me, size, pos_begin, pos_end, limit);
672 //////////////////////////////////////////////////////////////////////////////
675 .Function.resizeSpace.param.object.type:Class.String
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,
684 Tag<TExpand> const tag)
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_);
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,
698 typename Size< String<TValue, TSpec> >::Type limit,
699 Tag<TExpand> const tag)
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_);
707 //////////////////////////////////////////////////////////////////////////////
709 //////////////////////////////////////////////////////////////////////////////
711 template <typename TValue, typename TSpec, typename TValue2>
713 assignValue(String<TValue, TSpec> & me,
714 TValue2 const & _value)
716 // assign(me, toString(_value)); ???TODO
719 //???TODO: moveValue (2)
721 //////////////////////////////////////////////////////////////////////////////
723 //////////////////////////////////////////////////////////////////////////////
725 ///.Function.assign.param.target.type:Class.String
726 ///.Function.assign.param.source.type:Class.String
728 //overload of binary version for strings:
730 template<typename TTargetValue, typename TTargetSpec, typename TSource>
732 assign(String<TTargetValue, TTargetSpec> & target,
736 typedef String<TTargetValue, TTargetSpec> TTarget;
737 assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
739 template<typename TTargetValue, typename TTargetSpec, typename TSource>
741 assign(String<TTargetValue, TTargetSpec> & target,
742 TSource const & source)
745 typedef String<TTargetValue, TTargetSpec> TTarget;
746 assign(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
749 //////////////////////////////////////////////////////////////////////////////
751 template <typename TExpand>
752 struct _Assign_String
754 template <typename TTarget, typename TSource>
760 if (!id(source) || !shareResources(target, source))
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()));
769 if ((void *) &target == (void *) &source) return;
771 typename _TempCopy<TSource>::Type temp(source, length(source));
772 assign(target, temp, TExpand());
776 template <typename TTarget, typename TSource>
781 typename Size<TTarget>::Type limit)
783 if (!id(source) || !shareResources(target, source))
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()));
792 if ((void *) &target == (void *) &source) return;
794 typename Size<TTarget>::Type source_length = length(source);
795 if (source_length > limit) source_length = limit;
797 typename _TempCopy<TSource>::Type temp(source, source_length);
798 assign(target, temp, TExpand());
803 //////////////////////////////////////////////////////////////////////////////
805 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
807 assign(String<TTargetValue, TTargetSpec> & target,
808 TSource const & source,
811 typedef String<TTargetValue, TTargetSpec> TTarget;
812 _Assign_String<Tag<TExpand> const>::assign_(target, source);
814 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TSize, typename TExpand>
816 assign(String<TTargetValue, TTargetSpec> & target,
817 TSource const & source,
821 typedef String<TTargetValue, TTargetSpec> TTarget;
822 _Assign_String<Tag<TExpand> const>::assign_(target, source, limit);
825 //____________________________________________________________________________
826 //this variant is a workaround for the "const array"-bug of VC++
828 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
830 assign(String<TTargetValue, TTargetSpec> & target,
831 TSourceValue const * source,
834 typedef String<TTargetValue, TTargetSpec> TTarget;
835 _Assign_String<Tag<TExpand> const>::assign_(target, source);
837 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TSize, typename TExpand>
839 assign(String<TTargetValue, TTargetSpec> & target,
840 TSourceValue const * source,
844 typedef String<TTargetValue, TTargetSpec> TTarget;
845 _Assign_String<Tag<TExpand> const>::assign_(target, source, limit);
848 //////////////////////////////////////////////////////////////////////////////
850 //////////////////////////////////////////////////////////////////////////////
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.
858 template <typename TTarget, typename TSource>
860 _moveContiguous(TTarget & target,
863 typedef typename Value<TSource>::Type TSourceValue;
864 typedef typename Value<TTarget>::Type TTargetValue;
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());
871 typename Size<TTarget>::Type size = sizeof(TSourceValue) * capacity(source);
872 if (size >= sizeof(TTargetValue))
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
879 typename Size<TTarget>::Type target_length = length(source);
880 if (target_length > target_capacity)
882 target_length = target_capacity;
885 if (sizeof(TSourceValue) >= sizeof(TTargetValue))
887 arrayMoveForward(source_begin, source_begin + target_length, target_begin);
891 arrayMoveBackward(source_begin, source_begin + target_length, target_begin);
894 _setBegin(target, target_begin);
895 _setLength(target, target_length);
896 _setCapacity(target, target_capacity);
898 _setBegin(source, 0);
899 _setLength(source, 0);
900 _setCapacity(source, 0);
907 //____________________________________________________________________________
909 //overload of binary version for strings:
911 template<typename TTargetValue, typename TTargetSpec, typename TSource>
913 move(String<TTargetValue, TTargetSpec> & target,
917 typedef String<TTargetValue, TTargetSpec> TTarget;
918 move(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
920 template<typename TTargetValue, typename TTargetSpec, typename TSource>
922 move(String<TTargetValue, TTargetSpec> & target,
923 TSource const & source)
926 typedef String<TTargetValue, TTargetSpec> TTarget;
927 move(target, source, typename DefaultOverflowImplicit<TTarget>::Type());
930 //____________________________________________________________________________
932 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TTag>
934 move(String<TTargetValue, TTargetSpec> & target,
939 assign(target, source, tag);
942 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TTag>
944 move(String<TTargetValue, TTargetSpec> & target,
945 TSource const & source,
949 assign(target, source, tag);
952 //////////////////////////////////////////////////////////////////////////////
953 // valueConstructMove:
954 // it is usually better for strings to default construct and move instead of
955 // copy construct strings
958 template <typename TIterator, typename TValue, typename TSpec>
960 valueConstructMove(TIterator it,
961 String<TValue, TSpec> const & value)
968 //////////////////////////////////////////////////////////////////////////////
970 //////////////////////////////////////////////////////////////////////////////
972 ///.Function.append.param.target.type:Class.String
973 ///.Function.append.param.source.type:Class.String
975 template <typename TExpand>
976 struct _Append_String
978 template <typename TTarget, typename TSource>
980 append_(TTarget & target,
983 if (!id(source) || !shareResources(target, source))
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);
993 typename _TempCopy<TSource>::Type temp(source, length(source));
994 assign(target, temp, TExpand());
998 template <typename TTarget, typename TSource>
1000 append_(TTarget & target,
1002 typename Size<TTarget>::Type limit)
1004 typename Iterator<TTarget, Standard>::Type target_begin = begin(target, Standard());
1005 if (!id(source) || !shareResources(target, source))
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);
1014 typename Size<TTarget>::Type target_length = length(target);
1015 if (target_length >= limit)
1018 arrayDestruct(target_begin + limit, target_begin + target_length);
1019 _setLength(target, limit);
1024 limit -= target_length;
1025 typename Size<TTarget>::Type source_length = length(source) ;
1026 if (source_length > limit) source_length = limit;
1028 typename _TempCopy<TSource>::Type temp(source, source_length);
1029 append(target, temp, TExpand());
1035 //////////////////////////////////////////////////////////////////////////////
1037 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1039 append(String<TTargetValue, TTargetSpec> & target,
1040 TSource const & source,
1044 typedef String<TTargetValue, TTargetSpec> TTarget;
1045 _Append_String<Tag<TExpand> const>::append_(target, source);
1048 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
1050 append(String<TTargetValue, TTargetSpec> & target,
1051 TSource const & source,
1052 typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1056 typedef String<TTargetValue, TTargetSpec> TTarget;
1057 _Append_String<Tag<TExpand> const>::append_(target, source, limit);
1060 //____________________________________________________________________________
1061 //this variant is a workaround for the "const array"-bug of VC++
1063 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1065 append(String<TTargetValue, TTargetSpec> & target,
1066 TSourceValue * source,
1070 typedef String<TTargetValue, TTargetSpec> TTarget;
1071 _Append_String<Tag<TExpand> const>::append_(target, source);
1074 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
1076 append(String<TTargetValue, TTargetSpec> & target,
1077 TSourceValue * source,
1078 typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1082 typedef String<TTargetValue, TTargetSpec> TTarget;
1083 _Append_String<Tag<TExpand> const>::append_(target, source, limit);
1088 //////////////////////////////////////////////////////////////////////////////
1090 //////////////////////////////////////////////////////////////////////////////
1092 template <typename TExpand>
1093 struct _Append_Value_2_String
1095 template <typename T, typename TValue>
1097 appendValue_(T & me,
1101 typename Position<T>::Type me_length = length(me);
1102 if (capacity(me) <= me_length)
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)
1108 valueConstruct(begin(me) + me_length, temp_copy); //??? this should be valueMoveConstruct
1113 valueConstruct(begin(me, Standard()) + me_length, _value);
1114 _setLength(me, me_length + 1);
1119 //____________________________________________________________________________
1121 template <typename TTargetValue, typename TTargetSpec, typename TValue, typename TExpand>
1123 appendValue(String<TTargetValue, TTargetSpec> & me,
1124 TValue const & _value,
1128 _Append_Value_2_String<Tag<TExpand> const>::appendValue_(me, _value);
1131 //////////////////////////////////////////////////////////////////////////////
1133 //////////////////////////////////////////////////////////////////////////////
1135 .Function.insertValue:
1138 template <typename TExpand>
1139 struct _Insert_Value_2_String
1141 template <typename T, typename TPosition, typename TValue>
1143 insertValue_(T & me,
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))
1152 moveValue(me, pos, temp_copy);
1157 //____________________________________________________________________________
1159 template <typename TTargetValue, typename TTargetSpec, typename TPosition, typename TValue, typename TExpand>
1161 insertValue(String<TTargetValue, TTargetSpec> & me,
1163 TValue const & _value,
1167 _Insert_Value_2_String<Tag<TExpand> const>::insertValue_(me, pos, _value);
1170 //////////////////////////////////////////////////////////////////////////////
1172 //////////////////////////////////////////////////////////////////////////////
1174 ///.Function.replace.param.target.type:Class.String
1175 ///.Function.replace.param.source.type:Class.String
1177 template <typename TExpand>
1178 struct _Replace_String
1180 template <typename TTarget, typename TSource>
1182 replace_(TTarget & target,
1183 typename Size<TTarget>::Type pos_begin,
1184 typename Size<TTarget>::Type pos_end,
1187 if (!id(source) || !shareResources(target, source))
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);
1196 typename _TempCopy<TSource>::Type temp(source, length(source));
1197 replace(target, pos_begin, pos_end, temp, TExpand());
1201 template <typename TTarget, typename TSource>
1203 replace_(TTarget & target,
1204 typename Size<TTarget>::Type pos_begin,
1205 typename Size<TTarget>::Type pos_end,
1207 typename Size<TTarget>::Type limit)
1209 if (!id(source) || !shareResources(target, source))
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);
1217 if (pos_begin >= limit)
1220 arrayDestruct(begin(target) + limit, end(target));
1221 _setLength(target, limit);
1227 typename Size<TTarget>::Type source_length = length(source) ;
1228 if (source_length > limit) source_length = limit;
1230 typename _TempCopy<TSource>::Type temp(source, source_length);
1231 replace(target, pos_begin, pos_end, temp, limit, TExpand());
1238 //////////////////////////////////////////////////////////////////////////////
1240 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
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,
1249 typedef String<TTargetValue, TTargetSpec> TTarget;
1250 _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source);
1253 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
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,
1263 typedef String<TTargetValue, TTargetSpec> TTarget;
1264 _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source, limit);
1267 //____________________________________________________________________________
1268 //this variant is a workaround for the "const array"-bug of VC++
1270 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
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,
1279 typedef String<TTargetValue, TTargetSpec> TTarget;
1280 _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source);
1283 template<typename TTargetValue, typename TTargetSpec, typename TSourceValue, typename TExpand>
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,
1293 typedef String<TTargetValue, TTargetSpec> TTarget;
1294 _Replace_String<Tag<TExpand> const>::replace_(target, pos_begin, pos_end, source, limit);
1297 //////////////////////////////////////////////////////////////////////////////
1298 // handling of iterators as begin and end
1301 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
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,
1307 Tag<TExpand> const tag)
1309 replace(target, position(pos_begin), position(pos_end), source, tag);
1312 template<typename TTargetValue, typename TTargetSpec, typename TSource, typename TExpand>
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,
1318 typename Size< String<TTargetValue, TTargetSpec> >::Type limit,
1319 Tag<TExpand> const tag)
1321 replace(target, position(pos_begin), position(pos_end), source, limit, tag);
1325 //////////////////////////////////////////////////////////////////////////////
1327 .Internal._reallocateStorage:
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.
1342 template <typename TValue, typename TSpec>
1343 inline typename Value<String<TValue, TSpec> >::Type *
1345 String<TValue, TSpec> & me,
1346 typename Size< String<TValue, TSpec> >::Type new_capacity,
1349 if (new_capacity <= capacity(me)) return 0;
1353 return _allocateStorage(me, new_capacity);
1357 template <typename TValue, typename TSpec>
1358 inline typename Value<String<TValue, TSpec> >::Type *
1360 String<TValue, TSpec> & me,
1361 typename Size< String<TValue, TSpec> >::Type new_capacity,
1362 typename Size< String<TValue, TSpec> >::Type limit,
1365 if (new_capacity <= capacity(me)) return 0;
1369 if (new_capacity > limit) new_capacity = limit;
1370 return _allocateStorage(me, new_capacity);
1374 template <typename TValue, typename TSpec>
1375 inline typename Value<String<TValue, TSpec> >::Type *
1377 String<TValue, TSpec> & me,
1378 typename Size< String<TValue, TSpec> >::Type new_capacity,
1381 if (new_capacity <= capacity(me)) return 0;
1385 new_capacity = computeGenerousCapacity(me, new_capacity);
1386 return _allocateStorage(me, new_capacity);
1390 template <typename TValue, typename TSpec>
1391 inline typename Value<String<TValue, TSpec> >::Type *
1393 String<TValue, TSpec> & me,
1394 typename Size< String<TValue, TSpec> >::Type new_capacity,
1395 typename Size< String<TValue, TSpec> >::Type limit,
1398 if (new_capacity <= capacity(me)) return 0;
1402 new_capacity = computeGenerousCapacity(me, new_capacity);
1403 if (new_capacity > limit) new_capacity = limit;
1404 return _allocateStorage(me, new_capacity);
1408 //////////////////////////////////////////////////////////////////////////////
1409 ///.Function.resize.param.object.type:Class.String
1411 template <typename TExpand>
1412 struct _Resize_String
1414 template <typename T>
1415 static inline typename Size<T>::Type
1418 typename Size<T>::Type new_length)
1420 typedef typename Size<T>::Type TSize;
1421 TSize me_length = length(me);
1422 if (new_length < me_length)
1425 arrayDestruct(begin(me, Standard()) + new_length, begin(me, Standard()) + me_length);
1429 typename Size<T>::Type me_capacity = capacity(me);
1430 if (new_length > me_capacity)
1433 TSize new_capacity = reserve(me, new_length, TExpand());
1434 if (new_capacity < new_length)
1436 new_length = new_capacity;
1439 if (new_length > me_length)
1442 arrayConstruct(begin(me, Standard()) + me_length, begin(me, Standard()) + new_length);
1446 _setLength(me, new_length);
1451 template <typename TValue, typename TSpec, typename TSize, typename TExpand>
1452 inline typename Size< String<TValue, TSpec> >::Type
1454 String<TValue, TSpec> & me,
1459 return _Resize_String<Tag<TExpand> const>::resize_(me, new_length);
1462 //////////////////////////////////////////////////////////////////////////////
1464 ///.Function.fill.param.object.type:Class.String
1466 template <typename TExpand>
1469 template <typename T, typename TValue>
1470 static inline typename Size<T>::Type
1473 typename Size<T>::Type new_length,
1476 typename Size<T>::Type me_length = length(me);
1477 if (new_length < me_length)
1480 arrayDestruct(begin(me, Standard()) + new_length, begin(me, Standard()) + me_length);
1484 typename Size<T>::Type me_capacity = capacity(me);
1485 if (new_length > me_capacity)
1488 new_length = reserve(me, new_length, TExpand());
1490 if (new_length > me_length)
1493 arrayConstruct(begin(me, Standard()) + me_length, begin(me, Standard()) + new_length, val);
1497 _setLength(me, new_length);
1502 template <typename TValue, typename TSpec, typename TSize, typename TValue2, typename TExpand>
1504 fill(String<TValue, TSpec> & me,
1506 TValue2 const & val,
1510 return _Fill_String<Tag<TExpand> const>::fill_(me, new_length, val);
1513 //////////////////////////////////////////////////////////////////////////////
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)
1521 append(left, right);
1525 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1526 String<TLeftValue, TLeftSpec> const &
1527 operator += (String<TLeftValue, TLeftSpec> & left,
1528 TRight const & right)
1530 append(left, right);
1534 template <typename TLeft, typename TRightValue, typename TRightSpec>
1536 operator += (TLeft & left,
1537 String<TRightValue, TRightSpec> const & right)
1539 append(left, right);
1544 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1545 String<TLeftValue, TLeftSpec> const &
1546 operator += (String<TLeftValue, TLeftSpec> & left,
1547 TRight const & right)
1550 append(left, right);
1554 //////////////////////////////////////////////////////////////////////////////
1556 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1558 operator == (String<TLeftValue, TLeftSpec> const & left,
1559 TRight const & right)
1562 typename Comparator<String<TLeftValue, TLeftSpec> >::Type _lex(left, right);
1563 return isEqual(_lex);
1566 //////////////////////////////////////////////////////////////////////////////
1568 template <typename TLeftValue, typename TLeftSpec, typename TRight >
1570 operator !=(String<TLeftValue, TLeftSpec> const & left,
1571 TRight const & right)
1574 typename Comparator<String<TLeftValue, TLeftSpec> >::Type _lex(left, right);
1575 return isNotEqual(_lex);
1578 //////////////////////////////////////////////////////////////////////////////
1580 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1582 operator < (String<TLeftValue, TLeftSpec> const & left,
1583 TRight const & right)
1586 return isLess(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1589 //////////////////////////////////////////////////////////////////////////////
1591 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1593 operator <= (String<TLeftValue, TLeftSpec> const & left,
1594 TRight const & right)
1597 return isLessOrEqual(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1599 //////////////////////////////////////////////////////////////////////////////
1601 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1603 operator > (String<TLeftValue, TLeftSpec> const & left,
1604 TRight const & right)
1607 return isGreater(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1610 //////////////////////////////////////////////////////////////////////////////
1612 template <typename TLeftValue, typename TLeftSpec, typename TRight>
1614 operator >= (String<TLeftValue, TLeftSpec> const & left,
1615 TRight const & right)
1618 return isGreaterOrEqual(left, right, typename DefaultPrefixOrder<String<TLeftValue, TLeftSpec> >::Type());
1621 //////////////////////////////////////////////////////////////////////////////
1623 //////////////////////////////////////////////////////////////////////////////
1625 template <typename TStream, typename TValue, typename TSpec>
1627 operator << (TStream & target,
1628 String<TValue, TSpec> const & source)
1631 write(target, source);
1635 //////////////////////////////////////////////////////////////////////////////
1637 template <typename TStream, typename TValue, typename TSpec>
1639 operator >> (TStream & source,
1640 String<TValue, TSpec> & target)
1643 read(source, target);
1648 //////////////////////////////////////////////////////////////////////////////
1651 //////////////////////////////////////////////////////////////////////////////
1653 //////////////////////////////////////////////////////////////////////////////
1655 template <typename TTarget, typename TSource, typename TSpec>
1656 struct Value<String<Convert<TTarget, TSource>, TSpec> >:
1657 Value< String<TSource, TSpec> >
1661 //////////////////////////////////////////////////////////////////////////////
1663 template <typename T, typename TAccessor, typename TConverter>
1664 struct _AccessorConverter
1668 template <typename T, typename TAccessor, typename TConverter>
1669 struct _AccessorConverter<T, TAccessor &, typename TConverter &>
1674 template <typename TTarget, typename TSource, typename TSpec>
1675 struct GetValue<String<Converter<TTarget, TSource>, TSpec> >:
1678 typename GetValue<String<TSource, TSpec> >::Type,
1679 typename Converter<TTarget, TSource>::Type
1685 //////////////////////////////////////////////////////////////////////////////
1689 //////////////////////////////////////////////////////////////////////////////
1691 } //namespace SEQAN_NAMESPACE_MAIN
1693 //////////////////////////////////////////////////////////////////////////////
1695 #endif //#ifndef SEQAN_HEADER_...