1 // Written in the D programming language.
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic mutation algorithms.
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
10 If `a = [1, 2, 3]` and `b = [4, 5, 6, 7]`,
11 `bringToFront(a, b)` leaves `a = [4, 5, 6]` and
14 Copies a range to another. If
15 `a = [1, 2, 3]` and `b = new int[5]`, then `copy(a, b)`
16 leaves `b = [1, 2, 3, 0, 0]` and returns `b[3 .. $]`.)
18 Fills a range with a pattern,
19 e.g., if `a = new int[3]`, then `fill(a, 4)`
20 leaves `a = [4, 4, 4]` and `fill(a, [3, 4])` leaves
23 If `a = [1.2, 3.4]`, then `initializeAll(a)` leaves
24 `a = [double.init, double.init]`.)
26 `move(a, b)` moves `a` into `b`. `move(a)` reads `a`
27 destructively when necessary.)
29 Similar to `move` but assumes `target` is uninitialized.)
31 Moves all elements from one range to another.)
33 Similar to `moveAll` but assumes all elements in `target` are uninitialized.)
35 Moves as many elements as possible from one range to another.)
37 Similar to `moveSome` but assumes all elements in `target` are uninitialized.)
39 Removes elements from a range in-place, and returns the shortened
42 If `a = [1, 2, 3]`, `reverse(a)` changes it to `[3, 2, 1]`.)
44 Strips all leading and trailing elements equal to a value, or that
46 If `a = [1, 1, 0, 1, 1]`, then `strip(a, 1)` and
47 `strip!(e => e == 1)(a)` returns `[0]`.)
49 Strips all leading elements equal to a value, or that satisfy a
50 predicate. If `a = [1, 1, 0, 1, 1]`, then `stripLeft(a, 1)` and
51 `stripLeft!(e => e == 1)(a)` returns `[0, 1, 1]`.)
53 Strips all trailing elements equal to a value, or that satisfy a
55 If `a = [1, 1, 0, 1, 1]`, then `stripRight(a, 1)` and
56 `stripRight!(e => e == 1)(a)` returns `[1, 1, 0]`.)
60 Swaps two values by indices.)
62 Swaps all elements of two ranges.)
63 $(T2 uninitializedFill,
64 Fills a range (assumed uninitialized) with a value.)
67 Copyright: Andrei Alexandrescu 2008-.
69 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
71 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
73 Source: $(PHOBOSSRC std/algorithm/mutation.d)
76 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
78 module std.algorithm.mutation;
80 import std.range.primitives;
81 import std.traits : isArray, isAssignable, isBlitAssignable, isNarrowString,
82 Unqual, isSomeChar, isMutable;
83 import std.meta : allSatisfy;
84 import std.typecons : tuple, Tuple;
88 `bringToFront` takes two ranges `front` and `back`, which may
89 be of different types. Considering the concatenation of `front` and
90 `back` one unified range, `bringToFront` rotates that unified
91 range such that all elements in `back` are brought to the beginning
92 of the unified range. The relative ordering of elements in `front`
93 and `back`, respectively, remains unchanged.
95 The `bringToFront` function treats strings at the code unit
96 level and it is not concerned with Unicode character integrity.
97 `bringToFront` is designed as a function for moving elements
98 in ranges, not as a string function.
100 Performs $(BIGOH max(front.length, back.length)) evaluations of $(D
103 The `bringToFront` function can rotate elements in one buffer left or right, swap
104 buffers of equal length, and even move elements across disjoint
105 buffers of different types and different lengths.
109 Either `front` and `back` are disjoint, or `back` is
110 reachable from `front` and `front` is not reachable from $(D
114 front = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
115 back = a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
118 The number of elements brought to the front, i.e., the length of `back`.
121 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/rotate, STL's `rotate`)
123 size_t bringToFront(InputRange, ForwardRange)(InputRange front, ForwardRange back)
124 if (isInputRange!InputRange && isForwardRange!ForwardRange)
126 import std.string : representation;
128 static if (isNarrowString!InputRange)
130 auto frontW = representation(front);
134 alias frontW = front;
136 static if (isNarrowString!ForwardRange)
138 auto backW = representation(back);
145 return bringToFrontImpl(frontW, backW);
149 The simplest use of `bringToFront` is for rotating elements in a
154 auto arr = [4, 5, 6, 7, 1, 2, 3];
155 auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);
156 assert(p == arr.length - 4);
157 assert(arr == [ 1, 2, 3, 4, 5, 6, 7 ]);
161 The `front` range may actually "step over" the `back`
162 range. This is very useful with forward ranges that cannot compute
163 comfortably right-bounded subranges like `arr[0 .. 4]` above. In
164 the example below, `r2` is a right subrange of `r1`.
168 import std.algorithm.comparison : equal;
169 import std.container : SList;
170 import std.range.primitives : popFrontN;
172 auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
174 auto r2 = list[]; popFrontN(r2, 4);
175 assert(equal(r2, [ 1, 2, 3 ]));
176 bringToFront(r1, r2);
177 assert(equal(list[], [ 1, 2, 3, 4, 5, 6, 7 ]));
181 Elements can be swapped across ranges of different types:
185 import std.algorithm.comparison : equal;
186 import std.container : SList;
188 auto list = SList!(int)(4, 5, 6, 7);
189 auto vec = [ 1, 2, 3 ];
190 bringToFront(list[], vec);
191 assert(equal(list[], [ 1, 2, 3, 4 ]));
192 assert(equal(vec, [ 5, 6, 7 ]));
196 Unicode integrity is not preserved:
200 import std.string : representation;
201 auto ar = representation("a".dup);
202 auto br = representation("รง".dup);
204 bringToFront(ar, br);
206 auto a = cast(char[]) ar;
207 auto b = cast(char[]) br;
212 assert(b == "\247a");
215 private size_t bringToFrontImpl(InputRange, ForwardRange)(InputRange front, ForwardRange back)
216 if (isInputRange!InputRange && isForwardRange!ForwardRange)
218 import std.array : sameHead;
219 import std.range : take, Take;
220 enum bool sameHeadExists = is(typeof(front.sameHead(back)));
223 for (bool semidone; !front.empty && !back.empty; )
225 static if (sameHeadExists)
227 if (front.sameHead(back)) break; // shortcut
229 // Swap elements until front and/or back ends.
230 auto back0 = back.save;
234 static if (sameHeadExists)
236 // Detect the stepping-over condition.
237 if (front.sameHead(back0)) back0 = back.save;
239 swapFront(front, back);
244 while (!front.empty && !back.empty);
246 if (!semidone) result += nswaps;
248 // Now deal with the remaining elements.
251 if (front.empty) break;
252 // Right side was shorter, which means that we've brought
253 // all the back elements to the front.
255 // Next pass: bringToFront(front, back0) to adjust the rest.
260 assert(front.empty, "Expected front to be empty");
261 // Left side was shorter. Let's step into the back.
262 static if (is(InputRange == Take!ForwardRange))
264 front = take(back0, nswaps);
268 immutable subresult = bringToFront(take(back0, nswaps),
270 if (!semidone) result += subresult;
280 import std.algorithm.comparison : equal;
281 import std.conv : text;
282 import std.random : Random = Xorshift, uniform;
284 // a more elaborate test
286 auto rnd = Random(123_456_789);
287 int[] a = new int[uniform(100, 200, rnd)];
288 int[] b = new int[uniform(100, 200, rnd)];
289 foreach (ref e; a) e = uniform(-100, 100, rnd);
290 foreach (ref e; b) e = uniform(-100, 100, rnd);
292 // writeln("a= ", a);
293 // writeln("b= ", b);
294 auto n = bringToFront(c[0 .. a.length], c[a.length .. $]);
296 assert(n == b.length);
297 assert(c == b ~ a, text(c, "\n", a, "\n", b));
299 // different types, moveFront, no sameHead
307 R save() { return this; }
308 bool empty() { return i >= data.length; }
309 T front() { return data[i]; }
310 T front(real e) { return data[i] = cast(T) e; }
312 void popFront() { ++i; }
314 auto a = R!int([1, 2, 3, 4, 5]);
315 auto b = R!real([6, 7, 8, 9]);
316 auto n = bringToFront(a, b);
318 assert(a.data == [6, 7, 8, 9, 1]);
319 assert(b.data == [2, 3, 4, 5]);
321 // front steps over back
326 arr = [4, 5, 6, 7, 1, 2, 3];
329 bringToFront(r1, r2) == 3 || assert(0);
330 assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));
333 arr = [5, 6, 7, 1, 2, 3, 4];
336 bringToFront(r1, r2) == 4 || assert(0);
337 assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));
340 // https://issues.dlang.org/show_bug.cgi?id=16959
341 auto arr = ['4', '5', '6', '7', '1', '2', '3'];
342 auto p = bringToFront(arr[0 .. 4], arr[4 .. $]);
344 assert(p == arr.length - 4);
345 assert(arr == ['1', '2', '3', '4', '5', '6', '7']);
348 // Tests if types are arrays and support slice assign.
349 private enum bool areCopyCompatibleArrays(T1, T2) =
350 isArray!T1 && isArray!T2 && is(typeof(T2.init[] = T1.init[]));
354 Copies the content of `source` into `target` and returns the
355 remaining (unfilled) part of `target`.
357 Preconditions: `target` shall have enough room to accommodate
358 the entirety of `source`.
361 source = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
362 target = an output range
365 The unfilled part of target
367 TargetRange copy(SourceRange, TargetRange)(SourceRange source, TargetRange target)
368 if (isInputRange!SourceRange && isOutputRange!(TargetRange, ElementType!SourceRange))
370 static if (areCopyCompatibleArrays!(SourceRange, TargetRange))
372 const tlen = target.length;
373 const slen = source.length;
375 "Cannot copy a source range into a smaller target range.");
377 immutable overlaps = () @trusted {
378 return source.ptr < target.ptr + tlen &&
379 target.ptr < source.ptr + slen; }();
383 if (source.ptr < target.ptr)
385 foreach_reverse (idx; 0 .. slen)
386 target[idx] = source[idx];
390 foreach (idx; 0 .. slen)
391 target[idx] = source[idx];
393 return target[slen .. tlen];
397 // Array specialization. This uses optimized memory copying
398 // routines under the hood and is about 10-20x faster than the
399 // generic implementation.
400 target[0 .. slen] = source[];
401 return target[slen .. $];
406 // Specialize for 2 random access ranges.
407 // Typically 2 random access ranges are faster iterated by common
408 // index than by x.popFront(), y.popFront() pair
409 static if (isRandomAccessRange!SourceRange &&
410 hasLength!SourceRange &&
411 hasSlicing!TargetRange &&
412 isRandomAccessRange!TargetRange &&
413 hasLength!TargetRange)
415 auto len = source.length;
416 foreach (idx; 0 .. len)
417 target[idx] = source[idx];
418 return target[len .. target.length];
422 foreach (element; source)
423 put(target, element);
434 int[] buf = new int[](a.length + b.length + 10);
435 auto rem = a.copy(buf); // copy a into buf
436 rem = b.copy(rem); // copy b into remainder of buf
437 assert(buf[0 .. a.length + b.length] == [1, 5, 9, 8]);
438 assert(rem.length == 10); // unused slots in buf
442 As long as the target range elements support assignment from source
443 range elements, different types of ranges are accepted:
447 float[] src = [ 1.0f, 5 ];
448 double[] dest = new double[src.length];
453 To _copy at most `n` elements from a range, you may want to use
454 $(REF take, std,range):
459 int[] src = [ 1, 5, 8, 9, 10 ];
460 auto dest = new int[](3);
461 src.take(dest.length).copy(dest);
462 assert(dest == [ 1, 5, 8 ]);
466 To _copy just those elements from a range that satisfy a predicate,
471 import std.algorithm.iteration : filter;
472 int[] src = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
473 auto dest = new int[src.length];
475 .filter!(a => (a & 1) == 1)
477 assert(dest[0 .. $ - rem.length] == [ 1, 5, 9, 1 ]);
481 $(REF retro, std,range) can be used to achieve behavior similar to
482 $(LINK2 http://en.cppreference.com/w/cpp/algorithm/copy_backward, STL's `copy_backward`'):
486 import std.algorithm, std.range;
487 int[] src = [1, 2, 4];
488 int[] dest = [0, 0, 0, 0, 0];
489 src.retro.copy(dest.retro);
490 assert(dest == [0, 0, 1, 2, 4]);
496 enum c = copy([1,2,3], [4,5,6,7]);
503 import std.algorithm.iteration : filter;
508 auto e = copy(filter!("a > 1")(a), b);
509 assert(b[0] == 5 && e.length == 1);
513 int[] a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
514 copy(a[5 .. 10], a[4 .. 9]);
515 assert(a[4 .. 9] == [6, 7, 8, 9, 10]);
518 // https://issues.dlang.org/show_bug.cgi?id=21724
520 int[] a = [1, 2, 3, 4];
521 copy(a[0 .. 2], a[1 .. 3]);
522 assert(a == [1, 1, 2, 4]);
525 // https://issues.dlang.org/show_bug.cgi?id=7898
529 import std.algorithm;
530 int[] arr1 = [10, 20, 30, 40, 50];
531 int[] arr2 = arr1.dup;
539 // https://issues.dlang.org/show_bug.cgi?id=13650
542 import std.meta : AliasSeq;
543 static foreach (Char; AliasSeq!(char, wchar, dchar))
546 Char[6] a2 = "456789";
547 assert(copy(a1[], a2[]) is a2[3..$]);
548 assert(a1[] == "123");
549 assert(a2[] == "123789");
553 // https://issues.dlang.org/show_bug.cgi?id=18804
556 static struct NullSink
564 @property bool empty() { return line == 1; }
565 void popFront() { line = 1; }
573 Assigns `value` to each element of input range `range`.
575 Alternatively, instead of using a single `value` to fill the `range`,
576 a `filter` $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
577 can be provided. The length of `filler` and `range` do not need to match, but
578 `filler` must not be empty.
582 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
583 that exposes references to its elements and has assignable
585 value = Assigned to each element of range
587 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
588 representing the _fill pattern.
590 Throws: If `filler` is empty.
593 $(LREF uninitializedFill)
594 $(LREF initializeAll)
596 void fill(Range, Value)(auto ref Range range, auto ref Value value)
597 if ((isInputRange!Range && is(typeof(range.front = value)) ||
598 isSomeChar!Value && is(typeof(range[] = value))))
600 alias T = ElementType!Range;
602 static if (is(typeof(range[] = value)))
606 else static if (is(typeof(range[] = T(value))))
612 for ( ; !range.empty; range.popFront() )
622 int[] a = [ 1, 2, 3, 4 ];
624 assert(a == [ 5, 5, 5, 5 ]);
627 // test fallback on mutable narrow strings
628 // https://issues.dlang.org/show_bug.cgi?id=16342
631 char[] chars = ['a', 'b'];
633 assert(chars == "cc");
635 char[2] chars2 = ['a', 'b'];
637 assert(chars2 == "cc");
639 wchar[] wchars = ['a', 'b'];
640 fill(wchars, wchar('c'));
641 assert(wchars == "cc"w);
643 dchar[] dchars = ['a', 'b'];
644 fill(dchars, dchar('c'));
645 assert(dchars == "cc"d);
651 assert(chars.length == 0);
652 static assert(!__traits(compiles, fill(chars, 'c')));
654 assert(wchars.length == 0);
655 static assert(!__traits(compiles, fill(wchars, wchar('c'))));
662 assert(chars == ""c);
667 shared(char)[] chrs = ['r'];
669 assert(chrs == [shared(char)('c')]);
674 struct Str(size_t len)
676 private char[len] _data;
677 void opIndexAssign(char value) @safe @nogc
682 assert(str._data == "::");
687 char[] chars = ['a','b','c','d'];
688 chars[1 .. 3].fill(':');
689 assert(chars == "a::d");
691 // end https://issues.dlang.org/show_bug.cgi?id=16342
695 import std.conv : text;
696 import std.internal.test.dummyrange;
698 int[] a = [ 1, 2, 3 ];
700 assert(a == [ 6, 6, 6 ], text(a));
704 foreach (i; 0 .. 1000)
706 foreach (ref e; a) e = 6;
709 void fun1() { foreach (i; 0 .. 1000) fill(a, 6); }
711 // fill should accept InputRange
712 alias InputRange = DummyRange!(ReturnBy.Reference, Length.No, RangeType.Input);
713 enum filler = uint.max;
716 foreach (value; range.arr)
717 assert(value == filler);
722 //ER8638_1 IS_NOT self assignable
723 static struct ER8638_1
728 //ER8638_1 IS self assignable
729 static struct ER8638_2
731 void opAssign(ER8638_2){}
735 auto er8638_1 = new ER8638_1[](10);
736 auto er8638_2 = new ER8638_2[](10);
737 er8638_1.fill(5); //generic case
738 er8638_2.fill(5); //opSlice(T.init) case
745 immutable(int) b = 0;
747 assert(a == [0, 0, 0]);
750 double[] a = [1, 2, 3];
751 immutable(int) b = 0;
753 assert(a == [0, 0, 0]);
758 void fill(InputRange, ForwardRange)(InputRange range, ForwardRange filler)
759 if (isInputRange!InputRange
760 && (isForwardRange!ForwardRange
761 || (isInputRange!ForwardRange && isInfinite!ForwardRange))
762 && is(typeof(InputRange.init.front = ForwardRange.init.front)))
764 static if (isInfinite!ForwardRange)
766 //ForwardRange is infinite, no need for bounds checking or saving
767 static if (hasSlicing!ForwardRange && hasLength!InputRange
768 && is(typeof(filler[0 .. range.length])))
770 copy(filler[0 .. range.length], range);
775 for ( ; !range.empty; range.popFront(), filler.popFront())
777 range.front = filler.front;
783 import std.exception : enforce;
785 enforce(!filler.empty, "Cannot fill range with an empty filler");
787 static if (hasLength!InputRange && hasLength!ForwardRange
788 && is(typeof(range.length > filler.length)))
790 //Case we have access to length
791 immutable len = filler.length;
792 //Start by bulk copies
793 while (range.length > len)
795 range = copy(filler.save, range);
798 //and finally fill the partial range. No need to save here.
799 static if (hasSlicing!ForwardRange && is(typeof(filler[0 .. range.length])))
802 auto len2 = range.length;
803 range = copy(filler[0 .. len2], range);
807 //iterate. No need to check filler, it's length is longer than range's
808 for (; !range.empty; range.popFront(), filler.popFront())
810 range.front = filler.front;
817 auto bck = filler.save;
818 for (; !range.empty; range.popFront(), filler.popFront())
820 if (filler.empty) filler = bck.save;
821 range.front = filler.front;
830 int[] a = [ 1, 2, 3, 4, 5 ];
833 assert(a == [ 8, 9, 8, 9, 8 ]);
838 import std.exception : assertThrown;
839 import std.internal.test.dummyrange;
841 int[] a = [ 1, 2, 3, 4, 5 ];
844 assert(a == [ 1, 2, 1, 2, 1 ]);
846 // fill should accept InputRange
847 alias InputRange = DummyRange!(ReturnBy.Reference, Length.No, RangeType.Input);
850 foreach (i,value;range.arr)
851 assert(value == (i%2 == 0?1:2));
853 //test with a input being a "reference forward" range
854 fill(a, new ReferenceForwardRange!int([8, 9]));
855 assert(a == [8, 9, 8, 9, 8]);
857 //test with a input being an "infinite input" range
858 fill(a, new ReferenceInfiniteInputRange!int());
859 assert(a == [0, 1, 2, 3, 4]);
862 assertThrown(fill(a, a[$..$]));
866 Initializes all elements of `range` with their `.init` value.
867 Assumes that the elements of the range are uninitialized.
871 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
872 that exposes references to its elements and has assignable
877 $(LREF uninitializeFill)
879 void initializeAll(Range)(Range range)
880 if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range)
882 import core.stdc.string : memset, memcpy;
883 import std.traits : hasElaborateAssign, isDynamicArray;
885 alias T = ElementType!Range;
886 static if (hasElaborateAssign!T)
888 import std.algorithm.internal : addressOf;
889 //Elaborate opAssign. Must go the memcpy road.
890 //We avoid calling emplace here, because our goal is to initialize to
891 //the static state of T.init,
892 //So we want to avoid any un-necassarilly CC'ing of T.init
893 static if (!__traits(isZeroInit, T))
895 auto p = typeid(T).initializer();
896 for ( ; !range.empty ; range.popFront() )
898 static if (__traits(isStaticArray, T))
900 // static array initializer only contains initialization
901 // for one element of the static array.
902 auto elemp = cast(void *) addressOf(range.front);
903 auto endp = elemp + T.sizeof;
906 memcpy(elemp, p.ptr, p.length);
912 memcpy(addressOf(range.front), p.ptr, T.sizeof);
917 static if (isDynamicArray!Range)
918 memset(range.ptr, 0, range.length * T.sizeof);
920 for ( ; !range.empty ; range.popFront() )
921 memset(addressOf(range.front), 0, T.sizeof);
928 void initializeAll(Range)(Range range)
929 if (is(Range == char[]) || is(Range == wchar[]))
931 alias T = ElementEncodingType!Range;
938 import core.stdc.stdlib : malloc, free;
945 auto s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
947 assert(s == [S(10), S(10), S(10), S(10), S(10)]);
949 scope(exit) free(s.ptr);
954 import std.algorithm.iteration : filter;
955 import std.meta : AliasSeq;
956 import std.traits : hasElaborateAssign;
959 //Must work on narrow strings.
963 assert(a[] == [char.init, char.init, char.init]);
965 assert(!__traits(compiles, s.initializeAll()));
966 assert(!__traits(compiles, s.initializeAll()));
969 //Note: Cannot call uninitializedFill on narrow strings
973 b1[].initializeAll();
974 assert(b1[] == [e.e1, e.e1, e.e1]);
976 b2[].uninitializedFill(e.e2);
977 assert(b2[] == [e.e2, e.e2, e.e2]);
997 static assert(!hasElaborateAssign!S1);
998 static assert(!hasElaborateAssign!S2);
999 static assert( hasElaborateAssign!S3);
1000 static assert( hasElaborateAssign!S4);
1001 assert(!typeid(S1).initializer().ptr);
1002 assert( typeid(S2).initializer().ptr);
1003 assert(!typeid(S3).initializer().ptr);
1004 assert( typeid(S4).initializer().ptr);
1006 static foreach (S; AliasSeq!(S1, S2, S3, S4))
1012 ss1[].initializeAll();
1013 assert(ss1[] == [S.init, S.init, S.init]);
1017 auto sf = ss2[].filter!"true"();
1020 assert(ss2[] == [S.init, S.init, S.init]);
1026 ss1[].uninitializedFill(S(2));
1027 assert(ss1[] == [S(2), S(2), S(2)]);
1031 auto sf = ss2[].filter!"true"();
1032 sf.uninitializedFill(S(2));
1033 assert(ss2[] == [S(2), S(2), S(2)]);
1038 // test that initializeAll works for arrays of static arrays of structs with
1039 // elaborate assigns.
1046 Int[2] xs = [Int(1), Int(2)];
1049 bool empty() { return done; }
1050 ref Int[2] front() { return xs; }
1051 void popFront() { done = true; }
1054 assert(xs[0].x == 3);
1055 assert(xs[1].x == 3);
1060 Moves `source` into `target`, via a destructive copy when necessary.
1062 If `T` is a struct with a destructor or postblit defined, source is reset
1063 to its `.init` value after it is moved into target, otherwise it is
1067 If source has internal pointers that point to itself and doesn't define
1068 opPostMove, it cannot be moved, and will trigger an assertion failure.
1071 source = Data to copy.
1072 target = Where to copy into. The destructor, if any, is invoked before the
1075 void move(T)(ref T source, ref T target)
1077 moveImpl(target, source);
1080 /// For non-struct types, `move` just performs `target = source`:
1083 Object obj1 = new Object;
1088 assert(obj3 is obj1);
1090 assert(obj2 is obj1);
1094 pure nothrow @safe @nogc unittest
1096 // Structs without destructors are simply copied
1102 S1 s11 = { 10, 11 };
1107 assert(s12 == S1(10, 11));
1110 // But structs with destructors or postblits are reset to their .init value
1111 // after copying to the target.
1117 ~this() pure nothrow @safe @nogc { }
1124 assert(s21 == S2(1, 2));
1125 assert(s22 == S2(3, 4));
1130 import std.exception : assertCTFEable;
1134 Object obj1 = new Object;
1138 assert(obj3 is obj1);
1140 static struct S1 { int a = 1, b = 2; }
1141 S1 s11 = { 10, 11 };
1144 assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11);
1146 static struct S2 { int a = 1; int * b; }
1147 S2 s21 = { 10, null };
1153 // https://issues.dlang.org/show_bug.cgi?id=5661 test(1)
1156 static struct X { int n = 0; ~this(){n = 0;} }
1159 static assert(hasElaborateDestructor!S3);
1163 assert(s31.x.n == 0);
1164 assert(s32.x.n == 1);
1166 // https://issues.dlang.org/show_bug.cgi?id=5661 test(2)
1169 static struct X { int n = 0; this(this){n = 0;} }
1172 static assert(hasElaborateCopyConstructor!S4);
1176 assert(s41.x.n == 0);
1177 assert(s42.x.n == 1);
1179 // https://issues.dlang.org/show_bug.cgi?id=13990 test
1190 T move(T)(return scope ref T source)
1192 return moveImpl(source);
1195 /// Non-copyable structs can still be moved:
1196 pure nothrow @safe @nogc unittest
1201 @disable this(this);
1202 ~this() pure nothrow @safe @nogc {}
1211 /// `opPostMove` will be called if defined:
1212 pure nothrow @safe @nogc unittest
1217 void opPostMove(const ref S old)
1229 // https://issues.dlang.org/show_bug.cgi?id=20869
1230 // `move` should propagate the attributes of `opPostMove`
1235 void opPostMove(const ref S old) nothrow @system
1238 new int(i++); // Force @gc impure @system
1242 alias T = void function() @system nothrow;
1243 static assert(is(typeof({ S s; move(s); }) == T));
1244 static assert(is(typeof({ S s; move(s, s); }) == T));
1247 private void moveImpl(T)(ref scope T target, ref return scope T source)
1249 import std.traits : hasElaborateDestructor;
1251 static if (is(T == struct))
1253 // Unsafe when compiling without -dip1000
1254 if ((() @trusted => &source == &target)()) return;
1256 // Destroy target before overwriting it
1257 static if (hasElaborateDestructor!T) target.__xdtor();
1259 // move and emplace source into target
1260 moveEmplaceImpl(target, source);
1263 private T moveImpl(T)(ref return scope T source)
1265 // Properly infer safety from moveEmplaceImpl as the implementation below
1266 // might void-initialize pointers in result and hence needs to be @trusted
1267 if (false) moveEmplaceImpl(source, source);
1269 return trustedMoveImpl(source);
1272 private T trustedMoveImpl(T)(ref return scope T source) @trusted
1275 moveEmplaceImpl(result, source);
1281 import std.exception : assertCTFEable;
1285 Object obj1 = new Object;
1287 Object obj3 = move(obj2);
1288 assert(obj3 is obj1);
1290 static struct S1 { int a = 1, b = 2; }
1291 S1 s11 = { 10, 11 };
1293 assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11);
1295 static struct S2 { int a = 1; int * b; }
1296 S2 s21 = { 10, null };
1302 // https://issues.dlang.org/show_bug.cgi?id=5661 test(1)
1305 static struct X { int n = 0; ~this(){n = 0;} }
1308 static assert(hasElaborateDestructor!S3);
1312 assert(s31.x.n == 0);
1313 assert(s32.x.n == 1);
1315 // https://issues.dlang.org/show_bug.cgi?id=5661 test(2)
1318 static struct X { int n = 0; this(this){n = 0;} }
1321 static assert(hasElaborateCopyConstructor!S4);
1325 assert(s41.x.n == 0);
1326 assert(s42.x.n == 1);
1328 // https://issues.dlang.org/show_bug.cgi?id=13990 test
1340 static struct S { int n = 0; ~this() @system { n = 0; } }
1342 static assert(!__traits(compiles, () @safe { move(a, b); }));
1343 static assert(!__traits(compiles, () @safe { move(a); }));
1345 () @trusted { move(a, b); }();
1348 () @trusted { move(a); }();
1352 // https://issues.dlang.org/show_bug.cgi?id=6217
1355 import std.algorithm.iteration : map;
1356 auto x = map!"a"([1,2,3]);
1360 // https://issues.dlang.org/show_bug.cgi?id=8055
1381 // https://issues.dlang.org/show_bug.cgi?id=8057
1390 // Access to enclosing scope
1396 // Move nested struct
1404 // Regression https://issues.dlang.org/show_bug.cgi?id=8171
1405 static struct Array(T)
1407 // nested struct has no member
1413 Array!int.Payload x = void;
1418 private void moveEmplaceImpl(T)(ref scope T target, ref return scope T source)
1420 import core.stdc.string : memcpy, memset;
1421 import std.traits : hasAliasing, hasElaborateAssign,
1422 hasElaborateCopyConstructor, hasElaborateDestructor,
1424 isAssignable, isStaticArray;
1426 static if (!is(T == class) && hasAliasing!T) if (!__ctfe)
1428 import std.exception : doesPointTo;
1429 assert(!(doesPointTo(source, source) && !hasElaborateMove!T),
1430 "Cannot move object with internal pointer unless `opPostMove` is defined.");
1433 static if (is(T == struct))
1435 // Unsafe when compiling without -dip1000
1436 assert((() @trusted => &source !is &target)(), "source and target must not be identical");
1438 static if (hasElaborateAssign!T || !isAssignable!T)
1439 () @trusted { memcpy(&target, &source, T.sizeof); }();
1443 static if (hasElaborateMove!T)
1444 __move_post_blt(target, source);
1446 // If the source defines a destructor or a postblit hook, we must obliterate the
1447 // object in order to avoid double freeing and undue aliasing
1448 static if (hasElaborateDestructor!T || hasElaborateCopyConstructor!T)
1450 // If T is nested struct, keep original context pointer
1451 static if (__traits(isNested, T))
1452 enum sz = T.sizeof - (void*).sizeof;
1456 static if (__traits(isZeroInit, T))
1457 () @trusted { memset(&source, 0, sz); }();
1460 auto init = typeid(T).initializer();
1461 () @trusted { memcpy(&source, init.ptr, sz); }();
1465 else static if (isStaticArray!T)
1467 for (size_t i = 0; i < source.length; ++i)
1468 move(source[i], target[i]);
1472 // Primitive data (including pointers and arrays) or class -
1473 // assignment works great
1479 * Similar to $(LREF move) but assumes `target` is uninitialized. This
1480 * is more efficient because `source` can be blitted over `target`
1481 * without destroying or initializing it first.
1484 * source = value to be moved into target
1485 * target = uninitialized value to be filled by source
1487 void moveEmplace(T)(ref T source, ref T target) pure @system
1489 moveEmplaceImpl(target, source);
1493 pure nothrow @nogc @system unittest
1498 this(int* ptr) { _ptr = ptr; }
1499 ~this() { if (_ptr) ++*_ptr; }
1504 Foo foo1 = void; // uninitialized
1505 auto foo2 = Foo(&val); // initialized
1506 assert(foo2._ptr is &val);
1508 // Using `move(foo2, foo1)` would have an undefined effect because it would destroy
1509 // the uninitialized foo1.
1510 // moveEmplace directly overwrites foo1 without destroying or initializing it first.
1511 moveEmplace(foo2, foo1);
1512 assert(foo1._ptr is &val);
1513 assert(foo2._ptr is null);
1517 // https://issues.dlang.org/show_bug.cgi?id=18913
1520 static struct NoCopy
1524 @disable this(this);
1527 static void f(NoCopy[2]) { }
1529 NoCopy[2] ncarray = [ NoCopy(1), NoCopy(2) ];
1531 static assert(!__traits(compiles, f(ncarray)));
1537 Calls `move(a, b)` for each element `a` in `src` and the corresponding
1538 element `b` in `tgt`, in increasing order.
1541 `walkLength(src) <= walkLength(tgt)`.
1542 This precondition will be asserted. If you cannot ensure there is enough room in
1543 `tgt` to accommodate all of `src` use $(LREF moveSome) instead.
1546 src = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1548 tgt = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1549 elements that elements from `src` can be moved into.
1551 Returns: The leftover portion of `tgt` after all elements from `src` have
1554 InputRange2 moveAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt)
1555 if (isInputRange!InputRange1 && isInputRange!InputRange2
1556 && is(typeof(move(src.front, tgt.front))))
1558 return moveAllImpl!move(src, tgt);
1562 pure nothrow @safe @nogc unittest
1564 int[3] a = [ 1, 2, 3 ];
1566 assert(moveAll(a[], b[]) is b[3 .. $]);
1567 assert(a[] == b[0 .. 3]);
1568 int[3] cmp = [ 1, 2, 3 ];
1569 assert(a[] == cmp[]);
1573 * Similar to $(LREF moveAll) but assumes all elements in `tgt` are
1574 * uninitialized. Uses $(LREF moveEmplace) to move elements from
1575 * `src` over elements from `tgt`.
1577 InputRange2 moveEmplaceAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) @system
1578 if (isInputRange!InputRange1 && isInputRange!InputRange2
1579 && is(typeof(moveEmplace(src.front, tgt.front))))
1581 return moveAllImpl!moveEmplace(src, tgt);
1585 pure nothrow @nogc @system unittest
1589 ~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
1592 int[3] refs = [0, 1, 2];
1593 Foo[3] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2])];
1596 auto tail = moveEmplaceAll(src[], dst[]); // move 3 value from src over dst
1597 assert(tail.length == 2); // returns remaining uninitialized values
1598 initializeAll(tail);
1600 import std.algorithm.searching : all;
1601 assert(src[].all!(e => e._ptr is null));
1602 assert(dst[0 .. 3].all!(e => e._ptr !is null));
1609 ref int front() { return data[0]; }
1610 void popFront() { data.popFront; }
1611 bool empty() { return data.empty; }
1614 auto a = InputRange([ 1, 2, 3 ]);
1615 auto b = InputRange(new int[5]);
1617 assert(a.data == b.data[0 .. 3]);
1618 assert(a.data == [ 1, 2, 3 ]);
1621 private InputRange2 moveAllImpl(alias moveOp, InputRange1, InputRange2)(
1622 ref InputRange1 src, ref InputRange2 tgt)
1624 import std.exception : enforce;
1626 static if (isRandomAccessRange!InputRange1 && hasLength!InputRange1 && hasLength!InputRange2
1627 && hasSlicing!InputRange2 && isRandomAccessRange!InputRange2)
1629 auto toMove = src.length;
1630 assert(toMove <= tgt.length, "Source buffer needs to be smaller or equal to the target buffer.");
1631 foreach (idx; 0 .. toMove)
1632 moveOp(src[idx], tgt[idx]);
1633 return tgt[toMove .. tgt.length];
1637 for (; !src.empty; src.popFront(), tgt.popFront())
1639 assert(!tgt.empty, "Source buffer needs to be smaller or equal to the target buffer.");
1640 moveOp(src.front, tgt.front);
1648 Calls `move(a, b)` for each element `a` in `src` and the corresponding
1649 element `b` in `tgt`, in increasing order, stopping when either range has been
1653 src = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1655 tgt = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1656 elements that elements from `src` can be moved into.
1658 Returns: The leftover portions of the two ranges after one or the other of the
1659 ranges have been exhausted.
1661 Tuple!(InputRange1, InputRange2) moveSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt)
1662 if (isInputRange!InputRange1 && isInputRange!InputRange2
1663 && is(typeof(move(src.front, tgt.front))))
1665 return moveSomeImpl!move(src, tgt);
1669 pure nothrow @safe @nogc unittest
1671 int[5] a = [ 1, 2, 3, 4, 5 ];
1673 assert(moveSome(a[], b[])[0] is a[3 .. $]);
1674 assert(a[0 .. 3] == b);
1675 assert(a == [ 1, 2, 3, 4, 5 ]);
1679 * Same as $(LREF moveSome) but assumes all elements in `tgt` are
1680 * uninitialized. Uses $(LREF moveEmplace) to move elements from
1681 * `src` over elements from `tgt`.
1683 Tuple!(InputRange1, InputRange2) moveEmplaceSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) @system
1684 if (isInputRange!InputRange1 && isInputRange!InputRange2
1685 && is(typeof(move(src.front, tgt.front))))
1687 return moveSomeImpl!moveEmplace(src, tgt);
1691 pure nothrow @nogc @system unittest
1695 ~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
1698 int[4] refs = [0, 1, 2, 3];
1699 Foo[4] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2]), Foo(&refs[3])];
1702 auto res = moveEmplaceSome(src[], dst[]);
1703 assert(res.length == 2);
1705 import std.algorithm.searching : all;
1706 assert(src[0 .. 3].all!(e => e._ptr is null));
1707 assert(src[3]._ptr !is null);
1708 assert(dst[].all!(e => e._ptr !is null));
1711 private Tuple!(InputRange1, InputRange2) moveSomeImpl(alias moveOp, InputRange1, InputRange2)(
1712 ref InputRange1 src, ref InputRange2 tgt)
1714 for (; !src.empty && !tgt.empty; src.popFront(), tgt.popFront())
1715 moveOp(src.front, tgt.front);
1716 return tuple(src, tgt);
1722 Defines the swapping strategy for algorithms that need to swap
1723 elements in a range (such as partition and sort). The strategy
1724 concerns the swapping of elements that are not the core concern of the
1725 algorithm. For example, consider an algorithm that sorts $(D [ "abc",
1726 "b", "aBc" ]) according to `toUpper(a) < toUpper(b)`. That
1727 algorithm might choose to swap the two equivalent strings `"abc"`
1728 and `"aBc"`. That does not affect the sorting since both
1729 `["abc", "aBc", "b" ]` and `[ "aBc", "abc", "b" ]` are valid
1732 Some situations require that the algorithm must NOT ever change the
1733 relative ordering of equivalent elements (in the example above, only
1734 `[ "abc", "aBc", "b" ]` would be the correct result). Such
1735 algorithms are called $(B stable). If the ordering algorithm may swap
1736 equivalent elements discretionarily, the ordering is called $(B
1739 Yet another class of algorithms may choose an intermediate tradeoff by
1740 being stable only on a well-defined subrange of the range. There is no
1741 established terminology for such behavior; this library calls it $(B
1744 Generally, the `stable` ordering strategy may be more costly in
1745 time and/or space than the other two because it imposes additional
1746 constraints. Similarly, `semistable` may be costlier than $(D
1747 unstable). As (semi-)stability is not needed very often, the ordering
1748 algorithms in this module parameterized by `SwapStrategy` all
1749 choose `SwapStrategy.unstable` as the default.
1755 Allows freely swapping of elements as long as the output
1756 satisfies the algorithm's requirements.
1760 In algorithms partitioning ranges in two, preserve relative
1761 ordering of elements only to the left of the partition point.
1765 Preserve the relative ordering of elements to the largest
1766 extent allowed by the algorithm's requirements.
1774 int[] a = [0, 1, 2, 3];
1775 assert(remove!(SwapStrategy.stable)(a, 1) == [0, 2, 3]);
1777 assert(remove!(SwapStrategy.unstable)(a, 1) == [0, 3, 2]);
1783 import std.algorithm.sorting : partition;
1785 // Put stuff greater than 3 on the left
1786 auto arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1787 assert(partition!(a => a > 3, SwapStrategy.stable)(arr) == [1, 2, 3]);
1788 assert(arr == [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]);
1790 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1791 assert(partition!(a => a > 3, SwapStrategy.semistable)(arr) == [2, 3, 1]);
1792 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1]);
1794 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1795 assert(partition!(a => a > 3, SwapStrategy.unstable)(arr) == [3, 2, 1]);
1796 assert(arr == [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]);
1799 private template isValidIntegralTuple(T)
1801 import std.traits : isIntegral;
1802 import std.typecons : isTuple;
1803 static if (isTuple!T)
1805 enum isValidIntegralTuple = T.length == 2 &&
1806 isIntegral!(typeof(T.init[0])) && isIntegral!(typeof(T.init[0]));
1810 enum isValidIntegralTuple = isIntegral!T;
1816 Eliminates elements at given offsets from `range` and returns the shortened
1819 For example, here is how to remove a single element from an array:
1822 string[] a = [ "a", "b", "c", "d" ];
1823 a = a.remove(1); // remove element at offset 1
1824 assert(a == [ "a", "c", "d"]);
1827 Note that `remove` does not change the length of the original range directly;
1828 instead, it returns the shortened range. If its return value is not assigned to
1829 the original range, the original range will retain its original length, though
1830 its contents will have changed:
1833 int[] a = [ 3, 5, 7, 8 ];
1834 assert(remove(a, 1) == [ 3, 7, 8 ]);
1835 assert(a == [ 3, 7, 8, 8 ]);
1838 The element at offset `1` has been removed and the rest of the elements have
1839 shifted up to fill its place, however, the original array remains of the same
1840 length. This is because all functions in `std.algorithm` only change $(I
1841 content), not $(I topology). The value `8` is repeated because $(LREF move) was
1842 invoked to rearrange elements, and on integers `move` simply copies the source
1843 to the destination. To replace `a` with the effect of the removal, simply
1844 assign the slice returned by `remove` to it, as shown in the first example.
1846 Multiple indices can be passed into `remove`. In that case,
1847 elements at the respective indices are all removed. The indices must
1848 be passed in increasing order, otherwise an exception occurs.
1851 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
1852 assert(remove(a, 1, 3, 5) ==
1853 [ 0, 2, 4, 6, 7, 8, 9, 10 ]);
1856 (Note that all indices refer to slots in the $(I original) array, not
1857 in the array as it is being progressively shortened.)
1859 Tuples of two integral offsets can be used to remove an indices range:
1862 int[] a = [ 3, 4, 5, 6, 7];
1863 assert(remove(a, 1, tuple(1, 3), 9) == [ 3, 6, 7 ]);
1866 The tuple passes in a range closed to the left and open to
1867 the right (consistent with built-in slices), e.g. `tuple(1, 3)`
1868 means indices `1` and `2` but not `3`.
1870 Finally, any combination of integral offsets and tuples composed of two integral
1871 offsets can be passed in:
1874 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
1875 assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 5, 6, 7, 8, 10 ]);
1878 In this case, the slots at positions 1, 3, 4, and 9 are removed from
1881 If the need is to remove some elements in the range but the order of
1882 the remaining elements does not have to be preserved, you may want to
1883 pass `SwapStrategy.unstable` to `remove`.
1886 int[] a = [ 0, 1, 2, 3 ];
1887 assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);
1890 In the case above, the element at slot `1` is removed, but replaced
1891 with the last element of the range. Taking advantage of the relaxation
1892 of the stability requirement, `remove` moved elements from the end
1893 of the array over the slots to be removed. This way there is less data
1894 movement to be done which improves the execution time of the function.
1896 The function `remove` works on bidirectional ranges that have assignable
1897 lvalue elements. The moving strategy is (listed from fastest to slowest):
1900 $(LI If $(D s == SwapStrategy.unstable && isRandomAccessRange!Range &&
1901 hasLength!Range && hasLvalueElements!Range), then elements are moved from the
1902 end of the range into the slots to be filled. In this case, the absolute
1903 minimum of moves is performed.)
1904 $(LI Otherwise, if $(D s ==
1905 SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range
1906 && hasLvalueElements!Range), then elements are still moved from the
1907 end of the range, but time is spent on advancing between slots by repeated
1908 calls to `range.popFront`.)
1909 $(LI Otherwise, elements are moved
1910 incrementally towards the front of `range`; a given element is never
1911 moved several times, but more elements are moved than in the previous
1916 s = a SwapStrategy to determine if the original order needs to be preserved
1917 range = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1918 with a length member
1919 offset = which element(s) to remove
1922 A range containing all of the elements of range with offset removed.
1925 (SwapStrategy s = SwapStrategy.stable, Range, Offset ...)
1926 (Range range, Offset offset)
1927 if (Offset.length >= 1 && allSatisfy!(isValidIntegralTuple, Offset))
1929 // Activate this check when the deprecation of non-integral tuples is over
1930 //import std.traits : isIntegral;
1931 //import std.typecons : isTuple;
1932 //static foreach (T; Offset)
1934 //static if (isTuple!T)
1936 //static assert(T.length == 2 &&
1937 //isIntegral!(typeof(T.init[0])) && isIntegral!(typeof(T.init[0])),
1938 //"Each offset must be an integral or a tuple of two integrals." ~
1939 //"Use `arr.remove(pos1, pos2)` or `arr.remove(tuple(start, begin))`");
1943 //static assert(isIntegral!T,
1944 //"Each offset must be an integral or a tuple of two integrals." ~
1945 //"Use `arr.remove(pos1, pos2)` or `arr.remove(tuple(start, begin))`");
1948 return removeImpl!s(range, offset);
1951 deprecated("Use of non-integral tuples is deprecated. Use remove(tuple(start, end).")
1953 (SwapStrategy s = SwapStrategy.stable, Range, Offset ...)
1954 (Range range, Offset offset)
1955 if (Offset.length >= 1 && !allSatisfy!(isValidIntegralTuple, Offset))
1957 return removeImpl!s(range, offset);
1963 import std.typecons : tuple;
1965 auto a = [ 0, 1, 2, 3, 4, 5 ];
1966 assert(remove!(SwapStrategy.stable)(a, 1) == [ 0, 2, 3, 4, 5 ]);
1967 a = [ 0, 1, 2, 3, 4, 5 ];
1968 assert(remove!(SwapStrategy.stable)(a, 1, 3) == [ 0, 2, 4, 5] );
1969 a = [ 0, 1, 2, 3, 4, 5 ];
1970 assert(remove!(SwapStrategy.stable)(a, 1, tuple(3, 6)) == [ 0, 2 ]);
1972 a = [ 0, 1, 2, 3, 4, 5 ];
1973 assert(remove!(SwapStrategy.unstable)(a, 1) == [0, 5, 2, 3, 4]);
1974 a = [ 0, 1, 2, 3, 4, 5 ];
1975 assert(remove!(SwapStrategy.unstable)(a, tuple(1, 4)) == [0, 5, 4]);
1981 import std.typecons : tuple;
1984 assert([4, 5, 6].remove(1) == [4, 6]);
1986 // Delete multiple indices
1987 assert([4, 5, 6, 7, 8].remove(1, 3) == [4, 6, 8]);
1989 // Use an indices range
1990 assert([4, 5, 6, 7, 8].remove(tuple(1, 3)) == [4, 7, 8]);
1992 // Use an indices range and individual indices
1993 assert([4, 5, 6, 7, 8].remove(0, tuple(1, 3), 4) == [7]);
1996 /// `SwapStrategy.unstable` is faster, but doesn't guarantee the same order of the original array
1999 assert([5, 6, 7, 8].remove!(SwapStrategy.stable)(1) == [5, 7, 8]);
2000 assert([5, 6, 7, 8].remove!(SwapStrategy.unstable)(1) == [5, 8, 7]);
2003 private auto removeImpl(SwapStrategy s, Range, Offset...)(Range range, Offset offset)
2005 static if (isNarrowString!Range)
2007 static assert(isMutable!(typeof(range[0])),
2008 "Elements must be mutable to remove");
2009 static assert(s == SwapStrategy.stable,
2010 "Only stable removing can be done for character arrays");
2011 return removeStableString(range, offset);
2015 static assert(isBidirectionalRange!Range,
2016 "Range must be bidirectional");
2017 static assert(hasLvalueElements!Range,
2018 "Range must have Lvalue elements (see std.range.hasLvalueElements)");
2020 static if (s == SwapStrategy.unstable)
2022 static assert(hasLength!Range,
2023 "Range must have `length` for unstable remove");
2024 return removeUnstable(range, offset);
2026 else static if (s == SwapStrategy.stable)
2027 return removeStable(range, offset);
2029 static assert(false,
2030 "Only SwapStrategy.stable and SwapStrategy.unstable are supported");
2036 import std.exception : assertThrown;
2039 // https://issues.dlang.org/show_bug.cgi?id=10173
2040 int[] test = iota(0, 10).array();
2041 assertThrown(remove!(SwapStrategy.stable)(test, tuple(2, 4), tuple(1, 3)));
2042 assertThrown(remove!(SwapStrategy.unstable)(test, tuple(2, 4), tuple(1, 3)));
2043 assertThrown(remove!(SwapStrategy.stable)(test, 2, 4, 1, 3));
2044 assertThrown(remove!(SwapStrategy.unstable)(test, 2, 4, 1, 3));
2050 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2051 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2052 assert(remove!(SwapStrategy.stable)(a, 1) ==
2053 [ 0, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]);
2055 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2056 assert(remove!(SwapStrategy.unstable)(a, 0, 10) ==
2057 [ 9, 1, 2, 3, 4, 5, 6, 7, 8 ]);
2059 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2060 assert(remove!(SwapStrategy.unstable)(a, 0, tuple(9, 11)) ==
2061 [ 8, 1, 2, 3, 4, 5, 6, 7 ]);
2062 // https://issues.dlang.org/show_bug.cgi?id=5224
2064 assert(remove!(SwapStrategy.unstable)(a, 2) ==
2067 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2068 assert(remove!(SwapStrategy.stable)(a, 1, 5) ==
2069 [ 0, 2, 3, 4, 6, 7, 8, 9, 10 ]);
2071 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2072 assert(remove!(SwapStrategy.stable)(a, 1, 3, 5)
2073 == [ 0, 2, 4, 6, 7, 8, 9, 10]);
2074 a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2075 assert(remove!(SwapStrategy.stable)(a, 1, tuple(3, 5))
2076 == [ 0, 2, 5, 6, 7, 8, 9, 10]);
2078 a = iota(0, 10).array();
2079 assert(remove!(SwapStrategy.unstable)(a, tuple(1, 4), tuple(6, 7))
2080 == [0, 9, 8, 7, 4, 5]);
2083 // https://issues.dlang.org/show_bug.cgi?id=11576
2087 arr = arr.remove!(SwapStrategy.unstable)(2);
2088 assert(arr == [1,2]);
2092 // https://issues.dlang.org/show_bug.cgi?id=12889
2096 int[1][] arr = [[0], [1], [2], [3], [4], [5], [6]];
2097 auto orig = arr.dup;
2098 foreach (i; iota(arr.length))
2100 assert(orig == arr.remove!(SwapStrategy.unstable)(tuple(i,i)));
2101 assert(orig == arr.remove!(SwapStrategy.stable)(tuple(i,i)));
2107 char[] chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
2109 assert(chars == ['a', 'b', 'c', 'd', 'f', 'g', 'h', 'h']);
2111 char[] bigChars = "โลโยฌรฉหหฦรฉโรยกยก".dup;
2112 assert(remove(bigChars, tuple(4, 6), 8) == ("โลโยฌหฦโรยกยก"));
2114 import std.exception : assertThrown;
2115 assertThrown(remove(bigChars.dup, 1, 0));
2116 assertThrown(remove(bigChars.dup, tuple(4, 3)));
2119 private Range removeUnstable(Range, Offset...)(Range range, Offset offset)
2121 Tuple!(size_t, "pos", size_t, "len")[offset.length] blackouts;
2122 foreach (i, v; offset)
2124 static if (is(typeof(v[0]) : size_t) && is(typeof(v[1]) : size_t))
2126 blackouts[i].pos = v[0];
2127 blackouts[i].len = v[1] - v[0];
2131 static assert(is(typeof(v) : size_t), typeof(v).stringof);
2132 blackouts[i].pos = v;
2133 blackouts[i].len = 1;
2137 import std.exception : enforce;
2139 enforce(blackouts[i - 1].pos + blackouts[i - 1].len
2140 <= blackouts[i].pos,
2141 "remove(): incorrect ordering of elements to remove");
2145 size_t left = 0, right = offset.length - 1;
2146 auto tgt = range.save;
2149 while (left <= right)
2151 // Look for a blackout on the right
2152 if (blackouts[right].pos + blackouts[right].len >= range.length)
2154 range.popBackExactly(blackouts[right].len);
2156 // Since right is unsigned, we must check for this case, otherwise
2157 // we might turn it into size_t.max and the loop condition will not
2158 // fail when it should.
2167 // Advance to next blackout on the left
2168 assert(blackouts[left].pos >= tgtPos, "Next blackout on the left shouldn't appear before the target.");
2169 tgt.popFrontExactly(blackouts[left].pos - tgtPos);
2170 tgtPos = blackouts[left].pos;
2172 // Number of elements to the right of blackouts[right]
2173 immutable tailLen = range.length - (blackouts[right].pos + blackouts[right].len);
2174 size_t toMove = void;
2175 if (tailLen < blackouts[left].len)
2178 blackouts[left].pos += toMove;
2179 blackouts[left].len -= toMove;
2183 toMove = blackouts[left].len;
2187 foreach (i; 0 .. toMove)
2189 move(range.back, tgt.front);
2198 private Range removeStable(Range, Offset...)(Range range, Offset offset)
2200 auto result = range;
2201 auto src = range, tgt = range;
2203 foreach (pass, i; offset)
2205 static if (is(typeof(i[0])) && is(typeof(i[1])))
2207 auto from = i[0], delta = i[1] - i[0];
2215 static if (pass > 0)
2217 import std.exception : enforce;
2218 enforce(pos <= from,
2219 "remove(): incorrect ordering of elements to remove");
2221 for (; pos < from; ++pos, src.popFront(), tgt.popFront())
2223 move(src.front, tgt.front);
2228 src.popFrontExactly(from);
2229 tgt.popFrontExactly(from);
2232 // now skip source to the "to" position
2233 src.popFrontExactly(delta);
2234 result.popBackExactly(delta);
2242 private Range removeStableString(Range, Offset...)(Range range, Offset offsets)
2244 import std.utf : stride;
2246 size_t dcharIdx = 0;
2247 size_t charShift = 0;
2251 charIdx += stride(range[charIdx .. $]);
2257 auto encodedLen = stride(range[charIdx .. $]);
2258 foreach (j; charIdx .. charIdx + encodedLen)
2259 range[j - charShift] = range[j];
2260 charIdx += encodedLen;
2264 foreach (pass, i; offsets)
2266 static if (is(typeof(i[0])) && is(typeof(i[1])))
2269 auto delta = i[1] - i[0];
2277 import std.exception : enforce;
2278 enforce(dcharIdx <= from && delta >= 0,
2279 "remove(): incorrect ordering of elements to remove");
2281 while (dcharIdx < from)
2282 static if (pass == 0)
2287 auto mark = charIdx;
2288 while (dcharIdx < from + delta)
2290 charShift += charIdx - mark;
2293 foreach (i; charIdx .. range.length)
2294 range[i - charShift] = range[i];
2296 return range[0 .. $ - charShift];
2299 // Use of dynamic arrays as offsets is too error-prone
2300 // https://issues.dlang.org/show_bug.cgi?id=12086
2301 // Activate these tests once the deprecation period of remove with non-integral tuples is over
2304 //static assert(!__traits(compiles, [0, 1, 2, 3, 4].remove([1, 3]) == [0, 3, 4]));
2305 static assert(__traits(compiles, [0, 1, 2, 3, 4].remove(1, 3) == [0, 2, 4]));
2306 //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove([1, 3, 4]) == [0, 3, 4])));
2307 //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove(tuple(1, 3, 4)) == [0, 3, 4])));
2309 import std.range : only;
2310 //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove(only(1, 3)) == [0, 3, 4])));
2311 static assert(__traits(compiles, assert([0, 1, 2, 3, 4].remove(1, 3) == [0, 2, 4])));
2315 Reduces the length of the
2316 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives) `range` by removing
2317 elements that satisfy `pred`. If `s = SwapStrategy.unstable`,
2318 elements are moved from the right end of the range over the elements
2319 to eliminate. If `s = SwapStrategy.stable` (the default),
2320 elements are moved progressively to front such that their relative
2321 order is preserved. Returns the filtered range.
2324 range = a bidirectional ranges with lvalue elements
2325 or mutable character arrays
2328 the range with all of the elements where `pred` is `true`
2331 Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range)
2333 import std.functional : unaryFun;
2334 alias pred_ = unaryFun!pred;
2335 static if (isNarrowString!Range)
2337 static assert(isMutable!(typeof(range[0])),
2338 "Elements must be mutable to remove");
2339 static assert(s == SwapStrategy.stable,
2340 "Only stable removing can be done for character arrays");
2341 return removePredString!pred_(range);
2345 static assert(isBidirectionalRange!Range,
2346 "Range must be bidirectional");
2347 static assert(hasLvalueElements!Range,
2348 "Range must have Lvalue elements (see std.range.hasLvalueElements)");
2349 static if (s == SwapStrategy.unstable)
2350 return removePredUnstable!pred_(range);
2351 else static if (s == SwapStrategy.stable)
2352 return removePredStable!pred_(range);
2354 static assert(false,
2355 "Only SwapStrategy.stable and SwapStrategy.unstable are supported");
2362 static immutable base = [1, 2, 3, 2, 4, 2, 5, 2];
2364 int[] arr = base[].dup;
2366 // using a string-based predicate
2367 assert(remove!("a == 2")(arr) == [ 1, 3, 4, 5 ]);
2369 // The original array contents have been modified,
2370 // so we need to reset it to its original state.
2371 // The length is unmodified however.
2374 // using a lambda predicate
2375 assert(remove!(a => a == 2)(arr) == [ 1, 3, 4, 5 ]);
2380 int[] a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
2381 assert(remove!("a == 2", SwapStrategy.unstable)(a) ==
2382 [ 1, 6, 3, 5, 3, 4, 5 ]);
2383 a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
2384 assert(remove!("a == 2", SwapStrategy.stable)(a) ==
2385 [ 1, 3, 3, 4, 5, 5, 6 ]);
2388 @nogc @safe unittest
2391 static int[] arr = [0,1,2,3,4,5,6,7,8,9];
2392 alias pred = e => e < 5;
2394 auto r = arr[].remove!(SwapStrategy.unstable)(0);
2395 r = r.remove!(SwapStrategy.stable)(0);
2396 r = r.remove!(pred, SwapStrategy.unstable);
2397 r = r.remove!(pred, SwapStrategy.stable);
2402 import std.algorithm.comparison : min;
2403 import std.algorithm.searching : all, any;
2404 import std.algorithm.sorting : isStrictlyMonotonic;
2405 import std.array : array;
2406 import std.meta : AliasSeq;
2407 import std.range : iota, only;
2408 import std.typecons : Tuple;
2409 alias E = Tuple!(int, int);
2410 alias S = Tuple!(E);
2412 foreach (start; 0 .. 5)
2413 foreach (end; min(start+1,5) .. 5)
2414 soffsets ~= S(E(start,end));
2415 alias D = Tuple!(E, E);
2417 foreach (start1; 0 .. 10)
2418 foreach (end1; min(start1+1,10) .. 10)
2419 foreach (start2; end1 .. 10)
2420 foreach (end2; min(start2+1,10) .. 10)
2421 doffsets ~= D(E(start1,end1),E(start2,end2));
2422 alias T = Tuple!(E, E, E);
2424 foreach (start1; 0 .. 15)
2425 foreach (end1; min(start1+1,15) .. 15)
2426 foreach (start2; end1 .. 15)
2427 foreach (end2; min(start2+1,15) .. 15)
2428 foreach (start3; end2 .. 15)
2429 foreach (end3; min(start3+1,15) .. 15)
2430 toffsets ~= T(E(start1,end1),E(start2,end2),E(start3,end3));
2432 static void verify(O...)(int[] r, int len, int removed, bool stable, O offsets)
2434 assert(r.length == len - removed);
2435 assert(!stable || r.isStrictlyMonotonic);
2436 assert(r.all!(e => all!(o => e < o[0] || e >= o[1])(offsets.only)));
2439 static foreach (offsets; AliasSeq!(soffsets,doffsets,toffsets))
2440 foreach (os; offsets)
2442 int len = 5*os.length;
2443 auto w = iota(0, len).array;
2447 alias pred = e => any!(o => o[0] <= e && e < o[1])(only(os.expand));
2448 w = w.remove!(SwapStrategy.unstable)(os.expand);
2449 x = x.remove!(SwapStrategy.stable)(os.expand);
2450 y = y.remove!(pred, SwapStrategy.unstable);
2451 z = z.remove!(pred, SwapStrategy.stable);
2454 removed += o[1] - o[0];
2455 verify(w, len, removed, false, os[]);
2456 verify(x, len, removed, true, os[]);
2457 verify(y, len, removed, false, os[]);
2458 verify(z, len, removed, true, os[]);
2466 char[] chars = "abcdefg".dup;
2467 assert(chars.remove!(dc => dc == 'c' || dc == 'f') == "abdeg");
2468 assert(chars == "abdegfg");
2470 assert(chars.remove!"a == 'd'" == "abegfg");
2472 char[] bigChars = "ยฅ^ยจ^ยฉรฉโโฯ".dup;
2473 assert(bigChars.remove!(dc => dc == "ยจ"d[0] || dc == "รฉ"d[0]) == "ยฅ^^ยฉโโฯ");
2476 private Range removePredUnstable(alias pred, Range)(Range range)
2478 auto result = range;
2479 for (;!range.empty;)
2481 if (!pred(range.front))
2486 move(range.back, range.front);
2493 private Range removePredStable(alias pred, Range)(Range range)
2495 auto result = range;
2497 for (; !range.empty; range.popFront())
2499 if (pred(range.front))
2506 move(range.front, tgt.front);
2512 private Range removePredString(alias pred, SwapStrategy s = SwapStrategy.stable, Range)
2515 import std.utf : decode;
2516 import std.functional : unaryFun;
2518 alias pred_ = unaryFun!pred;
2521 size_t charShift = 0;
2522 while (charIdx < range.length)
2524 size_t start = charIdx;
2525 if (pred_(decode(range, charIdx)))
2527 charShift += charIdx - start;
2531 while (charIdx < range.length)
2533 size_t start = charIdx;
2534 auto doRemove = pred_(decode(range, charIdx));
2535 auto encodedLen = charIdx - start;
2537 charShift += encodedLen;
2539 foreach (i; start .. charIdx)
2540 range[i - charShift] = range[i];
2543 return range[0 .. $ - charShift];
2548 Reverses `r` in-place. Performs `r.length / 2` evaluations of `swap`.
2549 UTF sequences consisting of multiple code units are preserved properly.
2552 r = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
2553 with either swappable elements, a random access range with a length member,
2559 When passing a string with unicode modifiers on characters, such as `\u0301`,
2560 this function will not properly keep the position of the modifier. For example,
2561 reversing `ba\u0301d` ("bรกd") will result in d\u0301ab ("dฬab") instead of
2562 `da\u0301b` ("dรกb").
2564 See_Also: $(REF retro, std,range) for a lazy reverse without changing `r`
2566 Range reverse(Range)(Range r)
2567 if (isBidirectionalRange!Range &&
2568 (hasSwappableElements!Range ||
2569 (hasAssignableElements!Range && hasLength!Range && isRandomAccessRange!Range) ||
2570 (isNarrowString!Range && isAssignable!(ElementType!Range))))
2572 static if (isRandomAccessRange!Range && hasLength!Range)
2574 //swapAt is in fact the only way to swap non lvalue ranges
2575 immutable last = r.length - 1;
2576 immutable steps = r.length / 2;
2577 for (size_t i = 0; i < steps; i++)
2579 r.swapAt(i, last - i);
2583 else static if (isNarrowString!Range && isAssignable!(ElementType!Range))
2585 import std.string : representation;
2586 import std.utf : stride;
2588 auto raw = representation(r);
2589 for (size_t i = 0; i < r.length;)
2591 immutable step = stride(r, i);
2594 .reverse(raw[i .. i + step]);
2609 swap(r.front, r.back);
2621 int[] arr = [ 1, 2, 3 ];
2622 assert(arr.reverse == [ 3, 2, 1 ]);
2631 assert(range == [1]);
2634 assert(range == [2, 1]);
2636 assert(range.reverse == [3, 2, 1]);
2642 char[] arr = "hello\U00010143\u0100\U00010143".dup;
2643 assert(arr.reverse == "\U00010143\u0100\U00010143olleh");
2648 void test(string a, string b)
2652 assert(c == b, c ~ " != " ~ b);
2657 test("\u2029", "\u2029");
2658 test("\u0100", "\u0100");
2659 test("\u0430", "\u0430");
2660 test("\U00010143", "\U00010143");
2661 test("abcdefcdef", "fedcfedcba");
2662 test("hello\U00010143\u0100\U00010143", "\U00010143\u0100\U00010143olleh");
2666 The strip group of functions allow stripping of either leading, trailing,
2667 or both leading and trailing elements.
2669 The `stripLeft` function will strip the `front` of the range,
2670 the `stripRight` function will strip the `back` of the range,
2671 while the `strip` function will strip both the `front` and `back`
2674 Note that the `strip` and `stripRight` functions require the range to
2675 be a $(LREF BidirectionalRange) range.
2677 All of these functions come in two varieties: one takes a target element,
2678 where the range will be stripped as long as this element can be found.
2679 The other takes a lambda predicate, where the range will be stripped as
2680 long as the predicate returns true.
2683 range = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
2684 or $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
2685 element = the elements to remove
2688 a Range with all of range except element at the start and end
2690 Range strip(Range, E)(Range range, E element)
2691 if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool))
2693 return range.stripLeft(element).stripRight(element);
2697 Range strip(alias pred, Range)(Range range)
2698 if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool))
2700 return range.stripLeft!pred().stripRight!pred();
2704 Range stripLeft(Range, E)(Range range, E element)
2705 if (isInputRange!Range && is(typeof(range.front == element) : bool))
2707 import std.algorithm.searching : find;
2708 return find!((auto ref a) => a != element)(range);
2712 Range stripLeft(alias pred, Range)(Range range)
2713 if (isInputRange!Range && is(typeof(pred(range.front)) : bool))
2715 import std.algorithm.searching : find;
2716 import std.functional : not;
2718 return find!(not!pred)(range);
2722 Range stripRight(Range, E)(Range range, E element)
2723 if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool))
2725 for (; !range.empty; range.popBack())
2727 if (range.back != element)
2734 Range stripRight(alias pred, Range)(Range range)
2735 if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool))
2737 for (; !range.empty; range.popBack())
2739 if (!pred(range.back))
2745 /// Strip leading and trailing elements equal to the target element.
2748 assert(" foobar ".strip(' ') == "foobar");
2749 assert("00223.444500".strip('0') == "223.4445");
2750 assert("รซรซรชรฉรผลลpรฉรชรซรซ".strip('รซ') == "รชรฉรผลลpรฉรช");
2751 assert([1, 1, 0, 1, 1].strip(1) == [0]);
2752 assert([0.0, 0.01, 0.01, 0.0].strip(0).length == 2);
2755 /// Strip leading and trailing elements while the predicate returns true.
2758 assert(" foobar ".strip!(a => a == ' ')() == "foobar");
2759 assert("00223.444500".strip!(a => a == '0')() == "223.4445");
2760 assert("รซรซรชรฉรผลลpรฉรชรซรซ".strip!(a => a == 'รซ')() == "รชรฉรผลลpรฉรช");
2761 assert([1, 1, 0, 1, 1].strip!(a => a == 1)() == [0]);
2762 assert([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length == 2);
2765 /// Strip leading elements equal to the target element.
2768 assert(" foobar ".stripLeft(' ') == "foobar ");
2769 assert("00223.444500".stripLeft('0') == "223.444500");
2770 assert("ลฏลฏลฑniรงodรชรฉรฉ".stripLeft('ลฏ') == "ลฑniรงodรชรฉรฉ");
2771 assert([1, 1, 0, 1, 1].stripLeft(1) == [0, 1, 1]);
2772 assert([0.0, 0.01, 0.01, 0.0].stripLeft(0).length == 3);
2775 /// Strip leading elements while the predicate returns true.
2778 assert(" foobar ".stripLeft!(a => a == ' ')() == "foobar ");
2779 assert("00223.444500".stripLeft!(a => a == '0')() == "223.444500");
2780 assert("ลฏลฏลฑniรงodรชรฉรฉ".stripLeft!(a => a == 'ลฏ')() == "ลฑniรงodรชรฉรฉ");
2781 assert([1, 1, 0, 1, 1].stripLeft!(a => a == 1)() == [0, 1, 1]);
2782 assert([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length == 2);
2785 /// Strip trailing elements equal to the target element.
2788 assert(" foobar ".stripRight(' ') == " foobar");
2789 assert("00223.444500".stripRight('0') == "00223.4445");
2790 assert("รนniรงodรชรฉรฉ".stripRight('รฉ') == "รนniรงodรช");
2791 assert([1, 1, 0, 1, 1].stripRight(1) == [1, 1, 0]);
2792 assert([0.0, 0.01, 0.01, 0.0].stripRight(0).length == 3);
2795 /// Strip trailing elements while the predicate returns true.
2798 assert(" foobar ".stripRight!(a => a == ' ')() == " foobar");
2799 assert("00223.444500".stripRight!(a => a == '0')() == "00223.4445");
2800 assert("รนniรงodรชรฉรฉ".stripRight!(a => a == 'รฉ')() == "รนniรงodรช");
2801 assert([1, 1, 0, 1, 1].stripRight!(a => a == 1)() == [1, 1, 0]);
2802 assert([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length == 3);
2807 Swaps `lhs` and `rhs`. The instances `lhs` and `rhs` are moved in
2808 memory, without ever calling `opAssign`, nor any other function. `T`
2809 need not be assignable at all to be swapped.
2811 If `lhs` and `rhs` reference the same instance, then nothing is done.
2813 `lhs` and `rhs` must be mutable. If `T` is a struct or union, then
2814 its fields must also all be (recursively) mutable.
2817 lhs = Data to be swapped with `rhs`.
2818 rhs = Data to be swapped with `lhs`.
2820 void swap(T)(ref T lhs, ref T rhs) @trusted pure nothrow @nogc
2821 if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))))
2823 import std.traits : hasAliasing, hasElaborateAssign, isAssignable,
2825 static if (hasAliasing!T) if (!__ctfe)
2827 import std.exception : doesPointTo;
2828 assert(!doesPointTo(lhs, lhs), "Swap: lhs internal pointer.");
2829 assert(!doesPointTo(rhs, rhs), "Swap: rhs internal pointer.");
2830 assert(!doesPointTo(lhs, rhs), "Swap: lhs points to rhs.");
2831 assert(!doesPointTo(rhs, lhs), "Swap: rhs points to lhs.");
2834 static if (hasElaborateAssign!T || !isAssignable!T)
2838 // For structs with non-trivial assignment, move memory directly
2839 ubyte[T.sizeof] t = void;
2840 auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof];
2841 auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof];
2849 //Avoid assigning overlapping arrays. Dynamic arrays are fine, because
2850 //it's their ptr and length properties which get assigned rather
2851 //than their elements when assigning them, but static arrays are value
2852 //types and therefore all of their elements get copied as part of
2853 //assigning them, which would be assigning overlapping arrays if lhs
2854 //and rhs were the same array.
2855 static if (isStaticArray!T)
2857 if (lhs.ptr == rhs.ptr)
2861 // For non-elaborate-assign types, suffice to do the classic swap
2862 static if (__traits(hasCopyConstructor, T))
2864 // don't invoke any elaborate constructors either
2878 // Swapping POD (plain old data) types:
2881 assert(a == 34 && b == 42);
2883 // Swapping structs with indirection:
2884 static struct S { int x; char c; int[] y; }
2885 S s1 = { 0, 'z', [ 1, 2 ] };
2886 S s2 = { 42, 'a', [ 4, 6 ] };
2889 assert(s1.c == 'a');
2890 assert(s1.y == [ 4, 6 ]);
2893 assert(s2.c == 'z');
2894 assert(s2.y == [ 1, 2 ]);
2896 // Immutables cannot be swapped:
2897 immutable int imm1 = 1, imm2 = 2;
2898 static assert(!__traits(compiles, swap(imm1, imm2)));
2910 // Non-copyable types can still be swapped.
2911 static struct NoCopy
2913 this(this) { assert(0); }
2918 nc1.n = 127; nc1.s = "abc";
2919 nc2.n = 513; nc2.s = "uvwxyz";
2922 assert(nc1.n == 513 && nc1.s == "uvwxyz");
2923 assert(nc2.n == 127 && nc2.s == "abc");
2927 assert(nc1.n == 513 && nc1.s == "uvwxyz");
2928 assert(nc2.n == 127 && nc2.s == "abc");
2930 // Types containing non-copyable fields can also be swapped.
2931 static struct NoCopyHolder
2935 NoCopyHolder h1, h2;
2936 h1.noCopy.n = 31; h1.noCopy.s = "abc";
2937 h2.noCopy.n = 65; h2.noCopy.s = null;
2940 assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
2941 assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
2945 assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
2946 assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
2948 // Const types cannot be swapped.
2949 const NoCopy const1, const2;
2950 assert(const1.n == 0 && const2.n == 0);
2951 static assert(!__traits(compiles, swap(const1, const2)));
2954 // https://issues.dlang.org/show_bug.cgi?id=4789
2960 int[3] a = [1, 2, 3];
2962 assert(a == [1, 3, 2]);
2967 static struct NoAssign
2970 void opAssign(NoAssign) @disable;
2972 auto s1 = NoAssign(1);
2973 auto s2 = NoAssign(2);
2988 static assert(!__traits(compiles, swap(s, s)));
2994 // https://issues.dlang.org/show_bug.cgi?id=11853
2997 import std.traits : isAssignable;
2998 alias T = Tuple!(int, double);
2999 static assert(isAssignable!T);
3002 // https://issues.dlang.org/show_bug.cgi?id=12024
3005 import std.datetime;
3010 // https://issues.dlang.org/show_bug.cgi?id=9975
3013 import std.exception : doesPointTo, mayPointTo;
3024 assert(!doesPointTo(a, b));
3025 assert( mayPointTo(a, b));
3028 //Note: we can catch an error here, because there is no RAII in this test
3029 import std.exception : assertThrown;
3032 assertThrown!Error(move(p));
3033 assertThrown!Error(move(p, pp));
3034 assertThrown!Error(swap(p, pp));
3042 this(this) { x = new int; }
3050 void opAssign(B) { x = new int; }
3062 this(scope ref return const A other)
3066 // note, struct functions inside @safe functions infer ALL
3067 // attributes, so the following 3 lines are meant to prevent this.
3068 new int; // prevent @nogc inference
3069 writeln("impure"); // prevent pure inference
3070 throw new Exception(""); // prevent nothrow inference
3082 void swap(T)(ref T lhs, ref T rhs)
3083 if (is(typeof(lhs.proxySwap(rhs))))
3089 Swaps two elements in-place of a range `r`,
3090 specified by their indices `i1` and `i2`.
3093 r = a range with swappable elements
3097 void swapAt(R)(auto ref R r, size_t i1, size_t i2)
3099 static if (is(typeof(&r.swapAt)))
3103 else static if (is(typeof(&r[i1])))
3109 if (i1 == i2) return;
3110 auto t1 = r.moveAt(i1);
3111 auto t2 = r.moveAt(i2);
3118 pure @safe nothrow unittest
3120 import std.algorithm.comparison : equal;
3123 assert(a.equal([1, 3, 2]));
3126 pure @safe nothrow unittest
3128 import std.algorithm.comparison : equal;
3131 assert(a.equal([4, 5, 6]));
3134 pure @safe nothrow unittest
3136 // test non random access ranges
3137 import std.algorithm.comparison : equal;
3138 import std.array : array;
3140 char[] b = ['a', 'b', 'c'];
3142 assert(b.equal(['a', 'c', 'b']));
3144 int[3] c = [1, 2, 3];
3146 assert(c.array.equal([1, 3, 2]));
3148 // opIndex returns lvalue
3149 struct RandomIndexType(T)
3153 @property ref auto opIndex(size_t i)
3159 auto d = RandomIndexType!(int[])([4, 5, 6]);
3161 assert(d.payload.equal([4, 6, 5]));
3163 // custom moveAt and opIndexAssign
3164 struct RandomMoveAtType(T)
3168 ElementType!T moveAt(size_t i)
3170 return payload.moveAt(i);
3173 void opIndexAssign(ElementType!T val, size_t idx)
3178 auto e = RandomMoveAtType!(int[])([7, 8, 9]);
3180 assert(e.payload.equal([7, 9, 8]));
3184 struct RandomSwapAtType(T)
3188 void swapAt(size_t i)
3190 return payload.swapAt(i);
3193 auto f = RandomMoveAtType!(int[])([10, 11, 12]);
3195 assert(f.payload.equal([10, 12, 11]));
3198 private void swapFront(R1, R2)(R1 r1, R2 r2)
3199 if (isInputRange!R1 && isInputRange!R2)
3201 static if (is(typeof(swap(r1.front, r2.front))))
3203 swap(r1.front, r2.front);
3207 auto t1 = moveFront(r1), t2 = moveFront(r2);
3208 r1.front = move(t2);
3209 r2.front = move(t1);
3215 Swaps all elements of `r1` with successive elements in `r2`.
3216 Returns a tuple containing the remainder portions of `r1` and $(D
3217 r2) that were not swapped (one of them will be empty). The ranges may
3218 be of different types but must have the same element type and support
3222 r1 = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3223 with swappable elements
3224 r2 = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3225 with swappable elements
3228 Tuple containing the remainder portions of r1 and r2 that were not swapped
3230 Tuple!(InputRange1, InputRange2)
3231 swapRanges(InputRange1, InputRange2)(InputRange1 r1, InputRange2 r2)
3232 if (hasSwappableElements!InputRange1 && hasSwappableElements!InputRange2
3233 && is(ElementType!InputRange1 == ElementType!InputRange2))
3235 for (; !r1.empty && !r2.empty; r1.popFront(), r2.popFront())
3237 swap(r1.front, r2.front);
3239 return tuple(r1, r2);
3245 import std.range : empty;
3246 int[] a = [ 100, 101, 102, 103 ];
3247 int[] b = [ 0, 1, 2, 3 ];
3248 auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
3249 assert(c[0].empty && c[1].empty);
3250 assert(a == [ 100, 2, 3, 103 ]);
3251 assert(b == [ 0, 1, 101, 102 ]);
3255 Initializes each element of `range` with `value`.
3256 Assumes that the elements of the range are uninitialized.
3257 This is of interest for structs that
3258 define copy constructors (for all other types, $(LREF fill) and
3259 uninitializedFill are equivalent).
3263 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3264 that exposes references to its elements and has assignable
3266 value = Assigned to each element of range
3270 $(LREF initializeAll)
3272 void uninitializedFill(Range, Value)(Range range, Value value)
3273 if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = value)))
3275 import std.traits : hasElaborateAssign;
3277 alias T = ElementType!Range;
3278 static if (hasElaborateAssign!T)
3280 import core.internal.lifetime : emplaceRef;
3282 // Must construct stuff by the book
3283 for (; !range.empty; range.popFront())
3284 emplaceRef!T(range.front, value);
3287 // Doesn't matter whether fill is initialized or not
3288 return fill(range, value);
3292 nothrow @system unittest
3294 import core.stdc.stdlib : malloc, free;
3296 auto s = (cast(int*) malloc(5 * int.sizeof))[0 .. 5];
3297 uninitializedFill(s, 42);
3298 assert(s == [ 42, 42, 42, 42, 42 ]);
3300 scope(exit) free(s.ptr);