The OpenD Programming Language

1 // Written in the D programming language.
2 /**
3 This is a submodule of $(MREF std, algorithm).
4 It contains generic mutation algorithms.
5 
6 $(SCRIPT inhibitQuickIndex = 1;)
7 $(BOOKTABLE Cheat Sheet,
8 $(TR $(TH Function Name) $(TH Description))
9 $(T2 bringToFront,
10         If `a = [1, 2, 3]` and `b = [4, 5, 6, 7]`,
11         `bringToFront(a, b)` leaves `a = [4, 5, 6]` and
12         `b = [7, 1, 2, 3]`.)
13 $(T2 copy,
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 .. $]`.)
17 $(T2 fill,
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
21         `a = [3, 4, 3]`.)
22 $(T2 initializeAll,
23         If `a = [1.2, 3.4]`, then `initializeAll(a)` leaves
24         `a = [double.init, double.init]`.)
25 $(T2 move,
26         `move(a, b)` moves `a` into `b`. `move(a)` reads `a`
27         destructively when necessary.)
28 $(T2 moveEmplace,
29         Similar to `move` but assumes `target` is uninitialized.)
30 $(T2 moveAll,
31         Moves all elements from one range to another.)
32 $(T2 moveEmplaceAll,
33         Similar to `moveAll` but assumes all elements in `target` are uninitialized.)
34 $(T2 moveSome,
35         Moves as many elements as possible from one range to another.)
36 $(T2 moveEmplaceSome,
37         Similar to `moveSome` but assumes all elements in `target` are uninitialized.)
38 $(T2 remove,
39         Removes elements from a range in-place, and returns the shortened
40         range.)
41 $(T2 reverse,
42         If `a = [1, 2, 3]`, `reverse(a)` changes it to `[3, 2, 1]`.)
43 $(T2 strip,
44         Strips all leading and trailing elements equal to a value, or that
45         satisfy a predicate.
46         If `a = [1, 1, 0, 1, 1]`, then `strip(a, 1)` and
47         `strip!(e => e == 1)(a)` returns `[0]`.)
48 $(T2 stripLeft,
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]`.)
52 $(T2 stripRight,
53         Strips all trailing elements equal to a value, or that satisfy a
54         predicate.
55         If `a = [1, 1, 0, 1, 1]`, then `stripRight(a, 1)` and
56         `stripRight!(e => e == 1)(a)` returns `[1, 1, 0]`.)
57 $(T2 swap,
58         Swaps two values.)
59 $(T2 swapAt,
60         Swaps two values by indices.)
61 $(T2 swapRanges,
62         Swaps all elements of two ranges.)
63 $(T2 uninitializedFill,
64         Fills a range (assumed uninitialized) with a value.)
65 )
66 
67 Copyright: Andrei Alexandrescu 2008-.
68 
69 License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0).
70 
71 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
72 
73 Source: $(PHOBOSSRC std/algorithm/mutation.d)
74 
75 Macros:
76 T2=$(TR $(TDNW $(LREF $1)) $(TD $+))
77  */
78 module std.algorithm.mutation;
79 
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;
85 
86 // bringToFront
87 /**
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.
94 
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.
99 
100 Performs $(BIGOH max(front.length, back.length)) evaluations of $(D
101 swap).
102 
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.
106 
107 Preconditions:
108 
109 Either `front` and `back` are disjoint, or `back` is
110 reachable from `front` and `front` is not reachable from $(D
111 back).
112 
113 Params:
114     front = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
115     back = a $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
116 
117 Returns:
118     The number of elements brought to the front, i.e., the length of `back`.
119 
120 See_Also:
121     $(LINK2 http://en.cppreference.com/w/cpp/algorithm/rotate, STL's `rotate`)
122 */
123 size_t bringToFront(InputRange, ForwardRange)(InputRange front, ForwardRange back)
124 if (isInputRange!InputRange && isForwardRange!ForwardRange)
125 {
126     import std.string : representation;
127 
128     static if (isNarrowString!InputRange)
129     {
130         auto frontW = representation(front);
131     }
132     else
133     {
134         alias frontW = front;
135     }
136     static if (isNarrowString!ForwardRange)
137     {
138         auto backW = representation(back);
139     }
140     else
141     {
142         alias backW = back;
143     }
144 
145     return bringToFrontImpl(frontW, backW);
146 }
147 
148 /**
149 The simplest use of `bringToFront` is for rotating elements in a
150 buffer. For example:
151 */
152 @safe unittest
153 {
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 ]);
158 }
159 
160 /**
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`.
165 */
166 @safe unittest
167 {
168     import std.algorithm.comparison : equal;
169     import std.container : SList;
170     import std.range.primitives : popFrontN;
171 
172     auto list = SList!(int)(4, 5, 6, 7, 1, 2, 3);
173     auto r1 = list[];
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 ]));
178 }
179 
180 /**
181 Elements can be swapped across ranges of different types:
182 */
183 @safe unittest
184 {
185     import std.algorithm.comparison : equal;
186     import std.container : SList;
187 
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 ]));
193 }
194 
195 /**
196 Unicode integrity is not preserved:
197 */
198 @safe unittest
199 {
200     import std.string : representation;
201     auto ar = representation("a".dup);
202     auto br = representation("ç".dup);
203 
204     bringToFront(ar, br);
205 
206     auto a = cast(char[]) ar;
207     auto b = cast(char[]) br;
208 
209     // Illegal UTF-8
210     assert(a == "\303");
211     // Illegal UTF-8
212     assert(b == "\247a");
213 }
214 
215 private size_t bringToFrontImpl(InputRange, ForwardRange)(InputRange front, ForwardRange back)
216 if (isInputRange!InputRange && isForwardRange!ForwardRange)
217 {
218     import std.array : sameHead;
219     import std.range : take, Take;
220     enum bool sameHeadExists = is(typeof(front.sameHead(back)));
221     size_t result;
222 
223     for (bool semidone; !front.empty && !back.empty; )
224     {
225         static if (sameHeadExists)
226         {
227             if (front.sameHead(back)) break; // shortcut
228         }
229         // Swap elements until front and/or back ends.
230         auto back0 = back.save;
231         size_t nswaps;
232         do
233         {
234             static if (sameHeadExists)
235             {
236                 // Detect the stepping-over condition.
237                 if (front.sameHead(back0)) back0 = back.save;
238             }
239             swapFront(front, back);
240             ++nswaps;
241             front.popFront();
242             back.popFront();
243         }
244         while (!front.empty && !back.empty);
245 
246         if (!semidone) result += nswaps;
247 
248         // Now deal with the remaining elements.
249         if (back.empty)
250         {
251             if (front.empty) break;
252             // Right side was shorter, which means that we've brought
253             // all the back elements to the front.
254             semidone = true;
255             // Next pass: bringToFront(front, back0) to adjust the rest.
256             back = back0;
257         }
258         else
259         {
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))
263             {
264                 front = take(back0, nswaps);
265             }
266             else
267             {
268                 immutable subresult = bringToFront(take(back0, nswaps),
269                                                    back);
270                 if (!semidone) result += subresult;
271                 break; // done
272             }
273         }
274     }
275     return result;
276 }
277 
278 @safe unittest
279 {
280     import std.algorithm.comparison : equal;
281     import std.conv : text;
282     import std.random : Random = Xorshift, uniform;
283 
284     // a more elaborate test
285     {
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);
291         int[] c = a ~ b;
292         // writeln("a= ", a);
293         // writeln("b= ", b);
294         auto n = bringToFront(c[0 .. a.length], c[a.length .. $]);
295         //writeln("c= ", c);
296         assert(n == b.length);
297         assert(c == b ~ a, text(c, "\n", a, "\n", b));
298     }
299     // different types, moveFront, no sameHead
300     {
301         static struct R(T)
302         {
303             T[] data;
304             size_t i;
305             @property
306             {
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; }
311             }
312             void popFront() { ++i; }
313         }
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);
317         assert(n == 4);
318         assert(a.data == [6, 7, 8, 9, 1]);
319         assert(b.data == [2, 3, 4, 5]);
320     }
321     // front steps over back
322     {
323         int[] arr, r1, r2;
324 
325         // back is shorter
326         arr = [4, 5, 6, 7, 1, 2, 3];
327         r1 = arr;
328         r2 = arr[4 .. $];
329         bringToFront(r1, r2) == 3 || assert(0);
330         assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));
331 
332         // front is shorter
333         arr = [5, 6, 7, 1, 2, 3, 4];
334         r1 = arr;
335         r2 = arr[3 .. $];
336         bringToFront(r1, r2) == 4 || assert(0);
337         assert(equal(arr, [1, 2, 3, 4, 5, 6, 7]));
338     }
339 
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 .. $]);
343 
344     assert(p == arr.length - 4);
345     assert(arr == ['1', '2', '3', '4', '5', '6', '7']);
346 }
347 
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[]));
351 
352 // copy
353 /**
354 Copies the content of `source` into `target` and returns the
355 remaining (unfilled) part of `target`.
356 
357 Preconditions: `target` shall have enough room to accommodate
358 the entirety of `source`.
359 
360 Params:
361     source = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
362     target = an output range
363 
364 Returns:
365     The unfilled part of target
366  */
367 TargetRange copy(SourceRange, TargetRange)(SourceRange source, TargetRange target)
368 if (isInputRange!SourceRange && isOutputRange!(TargetRange, ElementType!SourceRange))
369 {
370     static if (areCopyCompatibleArrays!(SourceRange, TargetRange))
371     {
372         const tlen = target.length;
373         const slen = source.length;
374         assert(tlen >= slen,
375                 "Cannot copy a source range into a smaller target range.");
376 
377         immutable overlaps = () @trusted {
378             return source.ptr < target.ptr + tlen &&
379                 target.ptr < source.ptr + slen; }();
380 
381         if (overlaps)
382         {
383             if (source.ptr < target.ptr)
384             {
385                 foreach_reverse (idx; 0 .. slen)
386                     target[idx] = source[idx];
387             }
388             else
389             {
390                 foreach (idx; 0 .. slen)
391                     target[idx] = source[idx];
392             }
393             return target[slen .. tlen];
394         }
395         else
396         {
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 .. $];
402         }
403     }
404     else
405     {
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)
414         {
415             auto len = source.length;
416             foreach (idx; 0 .. len)
417                 target[idx] = source[idx];
418             return target[len .. target.length];
419         }
420         else
421         {
422             foreach (element; source)
423                 put(target, element);
424             return target;
425         }
426     }
427 }
428 
429 ///
430 @safe unittest
431 {
432     int[] a = [ 1, 5 ];
433     int[] b = [ 9, 8 ];
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
439 }
440 
441 /**
442 As long as the target range elements support assignment from source
443 range elements, different types of ranges are accepted:
444 */
445 @safe unittest
446 {
447     float[] src = [ 1.0f, 5 ];
448     double[] dest = new double[src.length];
449     src.copy(dest);
450 }
451 
452 /**
453 To _copy at most `n` elements from a range, you may want to use
454 $(REF take, std,range):
455 */
456 @safe unittest
457 {
458     import 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 ]);
463 }
464 
465 /**
466 To _copy just those elements from a range that satisfy a predicate,
467 use $(LREF filter):
468 */
469 @safe unittest
470 {
471     import std.algorithm.iteration : filter;
472     int[] src = [ 1, 5, 8, 9, 10, 1, 2, 0 ];
473     auto dest = new int[src.length];
474     auto rem = src
475         .filter!(a => (a & 1) == 1)
476         .copy(dest);
477     assert(dest[0 .. $ - rem.length] == [ 1, 5, 9, 1 ]);
478 }
479 
480 /**
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`'):
483 */
484 @safe unittest
485 {
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]);
491 }
492 
493 // Test CTFE copy.
494 @safe unittest
495 {
496     enum c = copy([1,2,3], [4,5,6,7]);
497     assert(c == [7]);
498 }
499 
500 
501 @safe unittest
502 {
503     import std.algorithm.iteration : filter;
504 
505     {
506         int[] a = [ 1, 5 ];
507         int[] b = [ 9, 8 ];
508         auto e = copy(filter!("a > 1")(a), b);
509         assert(b[0] == 5 && e.length == 1);
510     }
511 
512     {
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]);
516     }
517 
518     // https://issues.dlang.org/show_bug.cgi?id=21724
519     {
520         int[] a = [1, 2, 3, 4];
521         copy(a[0 .. 2], a[1 .. 3]);
522         assert(a == [1, 1, 2, 4]);
523     }
524 
525     // https://issues.dlang.org/show_bug.cgi?id=7898
526     {
527         enum v =
528         {
529             import std.algorithm;
530             int[] arr1 = [10, 20, 30, 40, 50];
531             int[] arr2 = arr1.dup;
532             copy(arr1, arr2);
533             return 35;
534         }();
535         assert(v == 35);
536     }
537 }
538 
539 // https://issues.dlang.org/show_bug.cgi?id=13650
540 @safe unittest
541 {
542     import std.meta : AliasSeq;
543     static foreach (Char; AliasSeq!(char, wchar, dchar))
544     {{
545         Char[3] a1 = "123";
546         Char[6] a2 = "456789";
547         assert(copy(a1[], a2[]) is a2[3..$]);
548         assert(a1[] == "123");
549         assert(a2[] == "123789");
550     }}
551 }
552 
553 // https://issues.dlang.org/show_bug.cgi?id=18804
554 @safe unittest
555 {
556     static struct NullSink
557     {
558         void put(E)(E) {}
559     }
560     int line = 0;
561     struct R
562     {
563         int front;
564         @property bool empty() { return line == 1; }
565         void popFront() { line = 1; }
566     }
567     R r;
568     copy(r, NullSink());
569     assert(line == 1);
570 }
571 
572 /**
573 Assigns `value` to each element of input range `range`.
574 
575 Alternatively, instead of using a single `value` to fill the `range`,
576 a `filler` $(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.
579 
580 Params:
581         range = An
582                 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
583                 that exposes references to its elements and has assignable
584                 elements
585         value = Assigned to each element of range
586         filler = A
587                 $(REF_ALTTEXT forward range, isForwardRange, std,range,primitives)
588                 representing the _fill pattern.
589 
590 Throws: If `filler` is empty.
591 
592 See_Also:
593         $(LREF uninitializedFill)
594         $(LREF initializeAll)
595  */
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))))
599 {
600     alias T = ElementType!Range;
601 
602     static if (is(typeof(range[] = value)))
603     {
604         range[] = value;
605     }
606     else static if (is(typeof(range[] = T(value))))
607     {
608         range[] = T(value);
609     }
610     else
611     {
612         for ( ; !range.empty; range.popFront() )
613         {
614             range.front = value;
615         }
616     }
617 }
618 
619 ///
620 @safe unittest
621 {
622     int[] a = [ 1, 2, 3, 4 ];
623     fill(a, 5);
624     assert(a == [ 5, 5, 5, 5 ]);
625 }
626 
627 // test fallback on mutable narrow strings
628 // https://issues.dlang.org/show_bug.cgi?id=16342
629 @safe unittest
630 {
631     char[] chars = ['a', 'b'];
632     fill(chars, 'c');
633     assert(chars == "cc");
634 
635     char[2] chars2 = ['a', 'b'];
636     fill(chars2, 'c');
637     assert(chars2 == "cc");
638 
639     wchar[] wchars = ['a', 'b'];
640     fill(wchars, wchar('c'));
641     assert(wchars == "cc"w);
642 
643     dchar[] dchars = ['a', 'b'];
644     fill(dchars, dchar('c'));
645     assert(dchars == "cc"d);
646 }
647 
648 @nogc @safe unittest
649 {
650     const(char)[] chars;
651     assert(chars.length == 0);
652     static assert(!__traits(compiles, fill(chars, 'c')));
653     wstring wchars;
654     assert(wchars.length == 0);
655     static assert(!__traits(compiles, fill(wchars, wchar('c'))));
656 }
657 
658 @nogc @safe unittest
659 {
660     char[] chars;
661     fill(chars, 'c');
662     assert(chars == ""c);
663 }
664 
665 @safe unittest
666 {
667     shared(char)[] chrs = ['r'];
668     fill(chrs, 'c');
669     assert(chrs == [shared(char)('c')]);
670 }
671 
672 @nogc @safe unittest
673 {
674     struct Str(size_t len)
675     {
676         private char[len] _data;
677         void opIndexAssign(char value) @safe @nogc
678         {_data[] = value;}
679     }
680     Str!2 str;
681     str.fill(':');
682     assert(str._data == "::");
683 }
684 
685 @safe unittest
686 {
687     char[] chars = ['a','b','c','d'];
688     chars[1 .. 3].fill(':');
689     assert(chars == "a::d");
690 }
691 // end https://issues.dlang.org/show_bug.cgi?id=16342
692 
693 @safe unittest
694 {
695     import std.conv : text;
696     import std.internal.test.dummyrange;
697 
698     int[] a = [ 1, 2, 3 ];
699     fill(a, 6);
700     assert(a == [ 6, 6, 6 ], text(a));
701 
702     void fun0()
703     {
704         foreach (i; 0 .. 1000)
705         {
706             foreach (ref e; a) e = 6;
707         }
708     }
709     void fun1() { foreach (i; 0 .. 1000) fill(a, 6); }
710 
711     // fill should accept InputRange
712     alias InputRange = DummyRange!(ReturnBy.Reference, Length.No, RangeType.Input);
713     enum filler = uint.max;
714     InputRange range;
715     fill(range, filler);
716     foreach (value; range.arr)
717         assert(value == filler);
718 }
719 
720 @safe unittest
721 {
722     //ER8638_1 IS_NOT self assignable
723     static struct ER8638_1
724     {
725         void opAssign(int){}
726     }
727 
728     //ER8638_1 IS self assignable
729     static struct ER8638_2
730     {
731         void opAssign(ER8638_2){}
732         void opAssign(int){}
733     }
734 
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
739 }
740 
741 @safe unittest
742 {
743     {
744         int[] a = [1, 2, 3];
745         immutable(int) b = 0;
746         a.fill(b);
747         assert(a == [0, 0, 0]);
748     }
749     {
750         double[] a = [1, 2, 3];
751         immutable(int) b = 0;
752         a.fill(b);
753         assert(a == [0, 0, 0]);
754     }
755 }
756 
757 /// ditto
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)))
763 {
764     static if (isInfinite!ForwardRange)
765     {
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])))
769         {
770             copy(filler[0 .. range.length], range);
771         }
772         else
773         {
774             //manual feed
775             for ( ; !range.empty; range.popFront(), filler.popFront())
776             {
777                 range.front = filler.front;
778             }
779         }
780     }
781     else
782     {
783         import std.exception : enforce;
784 
785         enforce(!filler.empty, "Cannot fill range with an empty filler");
786 
787         static if (hasLength!InputRange && hasLength!ForwardRange
788             && is(typeof(range.length > filler.length)))
789         {
790             //Case we have access to length
791             immutable len = filler.length;
792             //Start by bulk copies
793             while (range.length > len)
794             {
795                 range = copy(filler.save, range);
796             }
797 
798             //and finally fill the partial range. No need to save here.
799             static if (hasSlicing!ForwardRange && is(typeof(filler[0 .. range.length])))
800             {
801                 //use a quick copy
802                 auto len2 = range.length;
803                 range = copy(filler[0 .. len2], range);
804             }
805             else
806             {
807                 //iterate. No need to check filler, it's length is longer than range's
808                 for (; !range.empty; range.popFront(), filler.popFront())
809                 {
810                     range.front = filler.front;
811                 }
812             }
813         }
814         else
815         {
816             //Most basic case.
817             auto bck = filler.save;
818             for (; !range.empty; range.popFront(), filler.popFront())
819             {
820                 if (filler.empty) filler = bck.save;
821                 range.front = filler.front;
822             }
823         }
824     }
825 }
826 
827 ///
828 @safe unittest
829 {
830     int[] a = [ 1, 2, 3, 4, 5 ];
831     int[] b = [ 8, 9 ];
832     fill(a, b);
833     assert(a == [ 8, 9, 8, 9, 8 ]);
834 }
835 
836 @safe unittest
837 {
838     import std.exception : assertThrown;
839     import std.internal.test.dummyrange;
840 
841     int[] a = [ 1, 2, 3, 4, 5 ];
842     int[] b = [1, 2];
843     fill(a, b);
844     assert(a == [ 1, 2, 1, 2, 1 ]);
845 
846     // fill should accept InputRange
847     alias InputRange = DummyRange!(ReturnBy.Reference, Length.No, RangeType.Input);
848     InputRange range;
849     fill(range,[1,2]);
850     foreach (i,value;range.arr)
851     assert(value == (i%2 == 0?1:2));
852 
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]);
856 
857     //test with a input being an "infinite input" range
858     fill(a, new ReferenceInfiniteInputRange!int());
859     assert(a == [0, 1, 2, 3, 4]);
860 
861     //empty filler test
862     assertThrown(fill(a, a[$..$]));
863 }
864 
865 /**
866 Initializes all elements of `range` with their `.init` value.
867 Assumes that the elements of the range are uninitialized.
868 
869 This function is unavailable if `T` is a `struct` and  `T.this()` is annotated
870 with `@disable`.
871 
872 Params:
873         range = An
874                 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
875                 that exposes references to its elements and has assignable
876                 elements
877 
878 See_Also:
879         $(LREF fill)
880         $(LREF uninitializedFill)
881  */
882 void initializeAll(Range)(Range range)
883 if (isInputRange!Range && hasLvalueElements!Range && hasAssignableElements!Range
884     && __traits(compiles, { static ElementType!Range _; }))
885 {
886     import core.stdc.string : memset, memcpy;
887     import std.traits : hasElaborateAssign, isDynamicArray;
888 
889     alias T = ElementType!Range;
890     static if (hasElaborateAssign!T)
891     {
892         import std.algorithm.internal : addressOf;
893         //Elaborate opAssign. Must go the memcpy/memset road.
894         static if (!__traits(isZeroInit, T))
895         {
896             for ( ; !range.empty ; range.popFront() )
897             {
898                 import core.internal.lifetime : emplaceInitializer;
899                 emplaceInitializer(range.front);
900             }
901         }
902         else
903             static if (isDynamicArray!Range)
904                 memset(range.ptr, 0, range.length * T.sizeof);
905             else
906                 for ( ; !range.empty ; range.popFront() )
907                     memset(addressOf(range.front), 0, T.sizeof);
908     }
909     else
910         fill(range, T.init);
911 }
912 
913 /// ditto
914 void initializeAll(Range)(Range range)
915 if (is(Range == char[]) || is(Range == wchar[]))
916 {
917     alias T = ElementEncodingType!Range;
918     range[] = T.init;
919 }
920 
921 ///
922 @system unittest
923 {
924     import core.stdc.stdlib : malloc, free;
925 
926     struct S
927     {
928         int a = 10;
929     }
930 
931     auto s = (cast(S*) malloc(5 * S.sizeof))[0 .. 5];
932     initializeAll(s);
933     assert(s == [S(10), S(10), S(10), S(10), S(10)]);
934 
935     scope(exit) free(s.ptr);
936 }
937 
938 @system unittest
939 {
940     import std.algorithm.iteration : filter;
941     import std.meta : AliasSeq;
942     import std.traits : hasElaborateAssign;
943 
944     //Test strings:
945     //Must work on narrow strings.
946     //Must reject const
947     char[3] a = void;
948     a[].initializeAll();
949     assert(a[] == [char.init, char.init, char.init]);
950     string s;
951     assert(!__traits(compiles, s.initializeAll()));
952     assert(!__traits(compiles, s.initializeAll()));
953     assert(s.empty);
954 
955     //Note: Cannot call uninitializedFill on narrow strings
956 
957     enum e {e1, e2}
958     e[3] b1 = void;
959     b1[].initializeAll();
960     assert(b1[] == [e.e1, e.e1, e.e1]);
961     e[3] b2 = void;
962     b2[].uninitializedFill(e.e2);
963     assert(b2[] == [e.e2, e.e2, e.e2]);
964 
965     static struct S1
966     {
967         int i;
968     }
969     static struct S2
970     {
971         int i = 1;
972     }
973     static struct S3
974     {
975         int i;
976         this(this){}
977     }
978     static struct S4
979     {
980         int i = 1;
981         this(this){}
982     }
983     static assert(!hasElaborateAssign!S1);
984     static assert(!hasElaborateAssign!S2);
985     static assert( hasElaborateAssign!S3);
986     static assert( hasElaborateAssign!S4);
987     assert(!typeid(S1).initializer().ptr);
988     assert( typeid(S2).initializer().ptr);
989     assert(!typeid(S3).initializer().ptr);
990     assert( typeid(S4).initializer().ptr);
991 
992     static foreach (S; AliasSeq!(S1, S2, S3, S4))
993     {
994         //initializeAll
995         {
996             //Array
997             S[3] ss1 = void;
998             ss1[].initializeAll();
999             assert(ss1[] == [S.init, S.init, S.init]);
1000 
1001             //Not array
1002             S[3] ss2 = void;
1003             auto sf = ss2[].filter!"true"();
1004 
1005             sf.initializeAll();
1006             assert(ss2[] == [S.init, S.init, S.init]);
1007         }
1008         //uninitializedFill
1009         {
1010             //Array
1011             S[3] ss1 = void;
1012             ss1[].uninitializedFill(S(2));
1013             assert(ss1[] == [S(2), S(2), S(2)]);
1014 
1015             //Not array
1016             S[3] ss2 = void;
1017             auto sf = ss2[].filter!"true"();
1018             sf.uninitializedFill(S(2));
1019             assert(ss2[] == [S(2), S(2), S(2)]);
1020         }
1021     }
1022 }
1023 
1024 // test that initializeAll works for arrays of static arrays of structs with
1025 // elaborate assigns.
1026 @system unittest
1027 {
1028     struct Int {
1029         ~this() {}
1030         int x = 3;
1031     }
1032     Int[2] xs = [Int(1), Int(2)];
1033     struct R {
1034         bool done;
1035         bool empty() { return done; }
1036         ref Int[2] front() { return xs; }
1037         void popFront() { done = true; }
1038     }
1039     initializeAll(R());
1040     assert(xs[0].x == 3);
1041     assert(xs[1].x == 3);
1042 }
1043 
1044 // https://issues.dlang.org/show_bug.cgi?id=22105
1045 @system unittest
1046 {
1047     struct NoDefaultCtor
1048     {
1049         @disable this();
1050     }
1051 
1052     NoDefaultCtor[1] array = void;
1053     static assert(!__traits(compiles, array[].initializeAll));
1054 }
1055 
1056 // move
1057 /**
1058 Moves `source` into `target`, via a destructive copy when necessary.
1059 
1060 If `T` is a struct with a destructor or postblit defined, source is reset
1061 to its `.init` value after it is moved into target, otherwise it is
1062 left unchanged.
1063 
1064 Preconditions:
1065 If source has internal pointers that point to itself and doesn't define
1066 opPostMove, it cannot be moved, and will trigger an assertion failure.
1067 
1068 Params:
1069     source = Data to copy.
1070     target = Where to copy into. The destructor, if any, is invoked before the
1071         copy is performed.
1072 */
1073 void move(T)(ref T source, ref T target)
1074 {
1075     moveImpl(target, source);
1076 }
1077 
1078 /// For non-struct types, `move` just performs `target = source`:
1079 @safe unittest
1080 {
1081     Object obj1 = new Object;
1082     Object obj2 = obj1;
1083     Object obj3;
1084 
1085     move(obj2, obj3);
1086     assert(obj3 is obj1);
1087     // obj2 unchanged
1088     assert(obj2 is obj1);
1089 }
1090 
1091 ///
1092 pure nothrow @safe @nogc unittest
1093 {
1094     // Structs without destructors are simply copied
1095     struct S1
1096     {
1097         int a = 1;
1098         int b = 2;
1099     }
1100     S1 s11 = { 10, 11 };
1101     S1 s12;
1102 
1103     move(s11, s12);
1104 
1105     assert(s12 == S1(10, 11));
1106     assert(s11 == s12);
1107 
1108     // But structs with destructors or postblits are reset to their .init value
1109     // after copying to the target.
1110     struct S2
1111     {
1112         int a = 1;
1113         int b = 2;
1114 
1115         ~this() pure nothrow @safe @nogc { }
1116     }
1117     S2 s21 = { 3, 4 };
1118     S2 s22;
1119 
1120     move(s21, s22);
1121 
1122     assert(s21 == S2(1, 2));
1123     assert(s22 == S2(3, 4));
1124 }
1125 
1126 @safe unittest
1127 {
1128     import std.exception : assertCTFEable;
1129     import std.traits;
1130 
1131     assertCTFEable!((){
1132         Object obj1 = new Object;
1133         Object obj2 = obj1;
1134         Object obj3;
1135         move(obj2, obj3);
1136         assert(obj3 is obj1);
1137 
1138         static struct S1 { int a = 1, b = 2; }
1139         S1 s11 = { 10, 11 };
1140         S1 s12;
1141         move(s11, s12);
1142         assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11);
1143 
1144         static struct S2 { int a = 1; int * b; }
1145         S2 s21 = { 10, null };
1146         s21.b = new int;
1147         S2 s22;
1148         move(s21, s22);
1149         assert(s21 == s22);
1150     });
1151     // https://issues.dlang.org/show_bug.cgi?id=5661 test(1)
1152     static struct S3
1153     {
1154         static struct X { int n = 0; ~this(){n = 0;} }
1155         X x;
1156     }
1157     static assert(hasElaborateDestructor!S3);
1158     S3 s31, s32;
1159     s31.x.n = 1;
1160     move(s31, s32);
1161     assert(s31.x.n == 0);
1162     assert(s32.x.n == 1);
1163 
1164     // https://issues.dlang.org/show_bug.cgi?id=5661 test(2)
1165     static struct S4
1166     {
1167         static struct X { int n = 0; this(this){n = 0;} }
1168         X x;
1169     }
1170     static assert(hasElaborateCopyConstructor!S4);
1171     S4 s41, s42;
1172     s41.x.n = 1;
1173     move(s41, s42);
1174     assert(s41.x.n == 0);
1175     assert(s42.x.n == 1);
1176 
1177     // https://issues.dlang.org/show_bug.cgi?id=13990 test
1178     class S5;
1179 
1180     S5 s51;
1181     S5 s52 = s51;
1182     S5 s53;
1183     move(s52, s53);
1184     assert(s53 is s51);
1185 }
1186 
1187 /// Ditto
1188 T move(T)(return scope ref T source)
1189 {
1190     return moveImpl(source);
1191 }
1192 
1193 /// Non-copyable structs can still be moved:
1194 pure nothrow @safe @nogc unittest
1195 {
1196     struct S
1197     {
1198         int a = 1;
1199         @disable this(this);
1200         ~this() pure nothrow @safe @nogc {}
1201     }
1202     S s1;
1203     s1.a = 2;
1204     S s2 = move(s1);
1205     assert(s1.a == 1);
1206     assert(s2.a == 2);
1207 }
1208 
1209 /// `opPostMove` will be called if defined:
1210 pure nothrow @safe @nogc unittest
1211 {
1212     struct S
1213     {
1214         int a;
1215         void opPostMove(const ref S old)
1216         {
1217             assert(a == old.a);
1218             a++;
1219         }
1220     }
1221     S s1;
1222     s1.a = 41;
1223     S s2 = move(s1);
1224     assert(s2.a == 42);
1225 }
1226 
1227 // https://issues.dlang.org/show_bug.cgi?id=20869
1228 // `move` should propagate the attributes of `opPostMove`
1229 @system unittest
1230 {
1231     static struct S
1232     {
1233         void opPostMove(const ref S old) nothrow @system
1234         {
1235             __gshared int i;
1236             new int(i++); // Force @gc impure @system
1237         }
1238     }
1239 
1240     alias T = void function() @system nothrow;
1241     static assert(is(typeof({ S s; move(s); }) == T));
1242     static assert(is(typeof({ S s; move(s, s); }) == T));
1243 }
1244 
1245 private void moveImpl(T)(ref scope T target, ref return scope T source)
1246 {
1247     import std.traits : hasElaborateDestructor;
1248 
1249     static if (is(T == struct))
1250     {
1251         //  Unsafe when compiling without -dip1000
1252         if ((() @trusted => &source == &target)()) return;
1253 
1254         // Destroy target before overwriting it
1255         static if (hasElaborateDestructor!T) target.__xdtor();
1256     }
1257     // move and emplace source into target
1258     moveEmplaceImpl(target, source);
1259 }
1260 
1261 private T moveImpl(T)(ref return scope T source)
1262 {
1263     // Properly infer safety from moveEmplaceImpl as the implementation below
1264     // might void-initialize pointers in result and hence needs to be @trusted
1265     if (false) moveEmplaceImpl(source, source);
1266 
1267     return trustedMoveImpl(source);
1268 }
1269 
1270 private T trustedMoveImpl(T)(ref return scope T source) @trusted
1271 {
1272     T result = void;
1273     moveEmplaceImpl(result, source);
1274     return result;
1275 }
1276 
1277 @safe unittest
1278 {
1279     import std.exception : assertCTFEable;
1280     import std.traits;
1281 
1282     assertCTFEable!((){
1283         Object obj1 = new Object;
1284         Object obj2 = obj1;
1285         Object obj3 = move(obj2);
1286         assert(obj3 is obj1);
1287 
1288         static struct S1 { int a = 1, b = 2; }
1289         S1 s11 = { 10, 11 };
1290         S1 s12 = move(s11);
1291         assert(s11.a == 10 && s11.b == 11 && s12.a == 10 && s12.b == 11);
1292 
1293         static struct S2 { int a = 1; int * b; }
1294         S2 s21 = { 10, null };
1295         s21.b = new int;
1296         S2 s22 = move(s21);
1297         assert(s21 == s22);
1298     });
1299 
1300     // https://issues.dlang.org/show_bug.cgi?id=5661 test(1)
1301     static struct S3
1302     {
1303         static struct X { int n = 0; ~this(){n = 0;} }
1304         X x;
1305     }
1306     static assert(hasElaborateDestructor!S3);
1307     S3 s31;
1308     s31.x.n = 1;
1309     S3 s32 = move(s31);
1310     assert(s31.x.n == 0);
1311     assert(s32.x.n == 1);
1312 
1313     // https://issues.dlang.org/show_bug.cgi?id=5661 test(2)
1314     static struct S4
1315     {
1316         static struct X { int n = 0; this(this){n = 0;} }
1317         X x;
1318     }
1319     static assert(hasElaborateCopyConstructor!S4);
1320     S4 s41;
1321     s41.x.n = 1;
1322     S4 s42 = move(s41);
1323     assert(s41.x.n == 0);
1324     assert(s42.x.n == 1);
1325 
1326     // https://issues.dlang.org/show_bug.cgi?id=13990 test
1327     class S5;
1328 
1329     S5 s51;
1330     S5 s52 = s51;
1331     S5 s53;
1332     s53 = move(s52);
1333     assert(s53 is s51);
1334 }
1335 
1336 @system unittest
1337 {
1338     static struct S { int n = 0; ~this() @system { n = 0; } }
1339     S a, b;
1340     static assert(!__traits(compiles, () @safe { move(a, b); }));
1341     static assert(!__traits(compiles, () @safe { move(a); }));
1342     a.n = 1;
1343     () @trusted { move(a, b); }();
1344     assert(a.n == 0);
1345     a.n = 1;
1346     () @trusted { move(a); }();
1347     assert(a.n == 0);
1348 }
1349 
1350 // https://issues.dlang.org/show_bug.cgi?id=6217
1351 @safe unittest
1352 {
1353     import std.algorithm.iteration : map;
1354     auto x = map!"a"([1,2,3]);
1355     x = move(x);
1356 }
1357 
1358 // https://issues.dlang.org/show_bug.cgi?id=8055
1359 @safe unittest
1360 {
1361     static struct S
1362     {
1363         int x;
1364         ~this()
1365         {
1366             assert(x == 0);
1367         }
1368     }
1369     S foo(S s)
1370     {
1371         return move(s);
1372     }
1373     S a;
1374     a.x = 0;
1375     auto b = foo(a);
1376     assert(b.x == 0);
1377 }
1378 
1379 // https://issues.dlang.org/show_bug.cgi?id=8057
1380 @system unittest
1381 {
1382     int n = 10;
1383     struct S
1384     {
1385         int x;
1386         ~this()
1387         {
1388             // Access to enclosing scope
1389             assert(n == 10);
1390         }
1391     }
1392     S foo(S s)
1393     {
1394         // Move nested struct
1395         return move(s);
1396     }
1397     S a;
1398     a.x = 1;
1399     auto b = foo(a);
1400     assert(b.x == 1);
1401 
1402     // Regression https://issues.dlang.org/show_bug.cgi?id=8171
1403     static struct Array(T)
1404     {
1405         // nested struct has no member
1406         struct Payload
1407         {
1408             ~this() {}
1409         }
1410     }
1411     Array!int.Payload x = void;
1412     move(x);
1413     move(x, x);
1414 }
1415 
1416 private void moveEmplaceImpl(T)(ref scope T target, ref return scope T source)
1417 {
1418     import core.stdc.string : memcpy, memset;
1419     import std.traits : hasAliasing, hasElaborateAssign,
1420                         hasElaborateCopyConstructor, hasElaborateDestructor,
1421                         hasElaborateMove,
1422                         isAssignable, isStaticArray;
1423 
1424     static if (!is(T == class) && hasAliasing!T) if (!__ctfe)
1425     {
1426         import std.exception : doesPointTo;
1427         assert(!(doesPointTo(source, source) && !hasElaborateMove!T),
1428             "Cannot move object of type " ~ T.stringof ~ " with internal pointer unless `opPostMove` is defined.");
1429     }
1430 
1431     static if (is(T == struct))
1432     {
1433         //  Unsafe when compiling without -dip1000
1434         assert((() @trusted => &source !is &target)(), "source and target must not be identical");
1435 
1436         static if (hasElaborateAssign!T || !isAssignable!T)
1437             () @trusted { memcpy(&target, &source, T.sizeof); }();
1438         else
1439             target = source;
1440 
1441         static if (hasElaborateMove!T)
1442             __move_post_blt(target, source);
1443 
1444         // If the source defines a destructor or a postblit hook, we must obliterate the
1445         // object in order to avoid double freeing and undue aliasing
1446         static if (hasElaborateDestructor!T || hasElaborateCopyConstructor!T)
1447         {
1448             // If T is nested struct, keep original context pointer
1449             static if (__traits(isNested, T))
1450                 enum sz = T.sizeof - (void*).sizeof;
1451             else
1452                 enum sz = T.sizeof;
1453 
1454             static if (__traits(isZeroInit, T))
1455                 () @trusted { memset(&source, 0, sz); }();
1456             else
1457                 () @trusted { memcpy(&source, __traits(initSymbol, T).ptr, sz); }();
1458         }
1459     }
1460     else static if (isStaticArray!T)
1461     {
1462         for (size_t i = 0; i < source.length; ++i)
1463             move(source[i], target[i]);
1464     }
1465     else
1466     {
1467         // Primitive data (including pointers and arrays) or class -
1468         // assignment works great
1469         target = source;
1470     }
1471 }
1472 
1473 /**
1474  * Similar to $(LREF move) but assumes `target` is uninitialized. This
1475  * is more efficient because `source` can be blitted over `target`
1476  * without destroying or initializing it first.
1477  *
1478  * Params:
1479  *   source = value to be moved into target
1480  *   target = uninitialized value to be filled by source
1481  */
1482 void moveEmplace(T)(ref T source, ref T target) pure @system
1483 {
1484     moveEmplaceImpl(target, source);
1485 }
1486 
1487 ///
1488 pure nothrow @nogc @system unittest
1489 {
1490     static struct Foo
1491     {
1492     pure nothrow @nogc:
1493         this(int* ptr) { _ptr = ptr; }
1494         ~this() { if (_ptr) ++*_ptr; }
1495         int* _ptr;
1496     }
1497 
1498     int val;
1499     Foo foo1 = void; // uninitialized
1500     auto foo2 = Foo(&val); // initialized
1501     assert(foo2._ptr is &val);
1502 
1503     // Using `move(foo2, foo1)` would have an undefined effect because it would destroy
1504     // the uninitialized foo1.
1505     // moveEmplace directly overwrites foo1 without destroying or initializing it first.
1506     moveEmplace(foo2, foo1);
1507     assert(foo1._ptr is &val);
1508     assert(foo2._ptr is null);
1509     assert(val == 0);
1510 }
1511 
1512 // https://issues.dlang.org/show_bug.cgi?id=18913
1513 @safe unittest
1514 {
1515     static struct NoCopy
1516     {
1517         int payload;
1518         ~this() { }
1519         @disable this(this);
1520     }
1521 
1522     static void f(NoCopy[2]) { }
1523 
1524     NoCopy[2] ncarray = [ NoCopy(1), NoCopy(2) ];
1525 
1526     static assert(!__traits(compiles, f(ncarray)));
1527     f(move(ncarray));
1528 }
1529 
1530 // moveAll
1531 /**
1532 Calls `move(a, b)` for each element `a` in `src` and the corresponding
1533 element `b` in `tgt`, in increasing order.
1534 
1535 Preconditions:
1536 `walkLength(src) <= walkLength(tgt)`.
1537 This precondition will be asserted. If you cannot ensure there is enough room in
1538 `tgt` to accommodate all of `src` use $(LREF moveSome) instead.
1539 
1540 Params:
1541     src = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1542         movable elements.
1543     tgt = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1544         elements that elements from `src` can be moved into.
1545 
1546 Returns: The leftover portion of `tgt` after all elements from `src` have
1547 been moved.
1548  */
1549 InputRange2 moveAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt)
1550 if (isInputRange!InputRange1 && isInputRange!InputRange2
1551         && is(typeof(move(src.front, tgt.front))))
1552 {
1553     return moveAllImpl!move(src, tgt);
1554 }
1555 
1556 ///
1557 pure nothrow @safe @nogc unittest
1558 {
1559     int[3] a = [ 1, 2, 3 ];
1560     int[5] b;
1561     assert(moveAll(a[], b[]) is b[3 .. $]);
1562     assert(a[] == b[0 .. 3]);
1563     int[3] cmp = [ 1, 2, 3 ];
1564     assert(a[] == cmp[]);
1565 }
1566 
1567 /**
1568  * Similar to $(LREF moveAll) but assumes all elements in `tgt` are
1569  * uninitialized. Uses $(LREF moveEmplace) to move elements from
1570  * `src` over elements from `tgt`.
1571  */
1572 InputRange2 moveEmplaceAll(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) @system
1573 if (isInputRange!InputRange1 && isInputRange!InputRange2
1574         && is(typeof(moveEmplace(src.front, tgt.front))))
1575 {
1576     return moveAllImpl!moveEmplace(src, tgt);
1577 }
1578 
1579 ///
1580 pure nothrow @nogc @system unittest
1581 {
1582     static struct Foo
1583     {
1584         ~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
1585         int* _ptr;
1586     }
1587     int[3] refs = [0, 1, 2];
1588     Foo[3] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2])];
1589     Foo[5] dst = void;
1590 
1591     auto tail = moveEmplaceAll(src[], dst[]); // move 3 value from src over dst
1592     assert(tail.length == 2); // returns remaining uninitialized values
1593     initializeAll(tail);
1594 
1595     import std.algorithm.searching : all;
1596     assert(src[].all!(e => e._ptr is null));
1597     assert(dst[0 .. 3].all!(e => e._ptr !is null));
1598 }
1599 
1600 @system unittest
1601 {
1602     struct InputRange
1603     {
1604         ref int front() { return data[0]; }
1605         void popFront() { data.popFront; }
1606         bool empty() { return data.empty; }
1607         int[] data;
1608     }
1609     auto a = InputRange([ 1, 2, 3 ]);
1610     auto b = InputRange(new int[5]);
1611     moveAll(a, b);
1612     assert(a.data == b.data[0 .. 3]);
1613     assert(a.data == [ 1, 2, 3 ]);
1614 }
1615 
1616 private InputRange2 moveAllImpl(alias moveOp, InputRange1, InputRange2)(
1617     ref InputRange1 src, ref InputRange2 tgt)
1618 {
1619     import std.exception : enforce;
1620 
1621     static if (isRandomAccessRange!InputRange1 && hasLength!InputRange1 && hasLength!InputRange2
1622          && hasSlicing!InputRange2 && isRandomAccessRange!InputRange2)
1623     {
1624         auto toMove = src.length;
1625         assert(toMove <= tgt.length, "Source buffer needs to be smaller or equal to the target buffer.");
1626         foreach (idx; 0 .. toMove)
1627             moveOp(src[idx], tgt[idx]);
1628         return tgt[toMove .. tgt.length];
1629     }
1630     else
1631     {
1632         for (; !src.empty; src.popFront(), tgt.popFront())
1633         {
1634             assert(!tgt.empty, "Source buffer needs to be smaller or equal to the target buffer.");
1635             moveOp(src.front, tgt.front);
1636         }
1637         return tgt;
1638     }
1639 }
1640 
1641 // moveSome
1642 /**
1643 Calls `move(a, b)` for each element `a` in `src` and the corresponding
1644 element `b` in `tgt`, in increasing order, stopping when either range has been
1645 exhausted.
1646 
1647 Params:
1648     src = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1649         movable elements.
1650     tgt = An $(REF_ALTTEXT input range, isInputRange, std,range,primitives) with
1651         elements that elements from `src` can be moved into.
1652 
1653 Returns: The leftover portions of the two ranges after one or the other of the
1654 ranges have been exhausted.
1655  */
1656 Tuple!(InputRange1, InputRange2) moveSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt)
1657 if (isInputRange!InputRange1 && isInputRange!InputRange2
1658         && is(typeof(move(src.front, tgt.front))))
1659 {
1660     return moveSomeImpl!move(src, tgt);
1661 }
1662 
1663 ///
1664 pure nothrow @safe @nogc unittest
1665 {
1666     int[5] a = [ 1, 2, 3, 4, 5 ];
1667     int[3] b;
1668     assert(moveSome(a[], b[])[0] is a[3 .. $]);
1669     assert(a[0 .. 3] == b);
1670     assert(a == [ 1, 2, 3, 4, 5 ]);
1671 }
1672 
1673 /**
1674  * Same as $(LREF moveSome) but assumes all elements in `tgt` are
1675  * uninitialized. Uses $(LREF moveEmplace) to move elements from
1676  * `src` over elements from `tgt`.
1677  */
1678 Tuple!(InputRange1, InputRange2) moveEmplaceSome(InputRange1, InputRange2)(InputRange1 src, InputRange2 tgt) @system
1679 if (isInputRange!InputRange1 && isInputRange!InputRange2
1680         && is(typeof(move(src.front, tgt.front))))
1681 {
1682     return moveSomeImpl!moveEmplace(src, tgt);
1683 }
1684 
1685 ///
1686 pure nothrow @nogc @system unittest
1687 {
1688     static struct Foo
1689     {
1690         ~this() pure nothrow @nogc { if (_ptr) ++*_ptr; }
1691         int* _ptr;
1692     }
1693     int[4] refs = [0, 1, 2, 3];
1694     Foo[4] src = [Foo(&refs[0]), Foo(&refs[1]), Foo(&refs[2]), Foo(&refs[3])];
1695     Foo[3] dst = void;
1696 
1697     auto res = moveEmplaceSome(src[], dst[]);
1698     assert(res.length == 2);
1699 
1700     import std.algorithm.searching : all;
1701     assert(src[0 .. 3].all!(e => e._ptr is null));
1702     assert(src[3]._ptr !is null);
1703     assert(dst[].all!(e => e._ptr !is null));
1704 }
1705 
1706 private Tuple!(InputRange1, InputRange2) moveSomeImpl(alias moveOp, InputRange1, InputRange2)(
1707     ref InputRange1 src, ref InputRange2 tgt)
1708 {
1709     for (; !src.empty && !tgt.empty; src.popFront(), tgt.popFront())
1710         moveOp(src.front, tgt.front);
1711     return tuple(src, tgt);
1712  }
1713 
1714 
1715 // SwapStrategy
1716 /**
1717 Defines the swapping strategy for algorithms that need to swap
1718 elements in a range (such as partition and sort). The strategy
1719 concerns the swapping of elements that are not the core concern of the
1720 algorithm. For example, consider an algorithm that sorts $(D [ "abc",
1721 "b", "aBc" ]) according to `toUpper(a) < toUpper(b)`. That
1722 algorithm might choose to swap the two equivalent strings `"abc"`
1723 and `"aBc"`. That does not affect the sorting since both
1724 `["abc", "aBc", "b" ]` and `[ "aBc", "abc", "b" ]` are valid
1725 outcomes.
1726 
1727 Some situations require that the algorithm must NOT ever change the
1728 relative ordering of equivalent elements (in the example above, only
1729 `[ "abc", "aBc", "b" ]` would be the correct result). Such
1730 algorithms are called $(B stable). If the ordering algorithm may swap
1731 equivalent elements discretionarily, the ordering is called $(B
1732 unstable).
1733 
1734 Yet another class of algorithms may choose an intermediate tradeoff by
1735 being stable only on a well-defined subrange of the range. There is no
1736 established terminology for such behavior; this library calls it $(B
1737 semistable).
1738 
1739 Generally, the `stable` ordering strategy may be more costly in
1740 time and/or space than the other two because it imposes additional
1741 constraints. Similarly, `semistable` may be costlier than $(D
1742 unstable). As (semi-)stability is not needed very often, the ordering
1743 algorithms in this module parameterized by `SwapStrategy` all
1744 choose `SwapStrategy.unstable` as the default.
1745 */
1746 
1747 enum SwapStrategy
1748 {
1749     /**
1750        Allows freely swapping of elements as long as the output
1751        satisfies the algorithm's requirements.
1752     */
1753     unstable,
1754     /**
1755        In algorithms partitioning ranges in two, preserve relative
1756        ordering of elements only to the left of the partition point.
1757     */
1758     semistable,
1759     /**
1760        Preserve the relative ordering of elements to the largest
1761        extent allowed by the algorithm's requirements.
1762     */
1763     stable,
1764 }
1765 
1766 ///
1767 @safe unittest
1768 {
1769     int[] a = [0, 1, 2, 3];
1770     assert(remove!(SwapStrategy.stable)(a, 1) == [0, 2, 3]);
1771     a = [0, 1, 2, 3];
1772     assert(remove!(SwapStrategy.unstable)(a, 1) == [0, 3, 2]);
1773 }
1774 
1775 ///
1776 @safe unittest
1777 {
1778     import std.algorithm.sorting : partition;
1779 
1780     // Put stuff greater than 3 on the left
1781     auto arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1782     assert(partition!(a => a > 3, SwapStrategy.stable)(arr) == [1, 2, 3]);
1783     assert(arr == [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]);
1784 
1785     arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1786     assert(partition!(a => a > 3, SwapStrategy.semistable)(arr) == [2, 3, 1]);
1787     assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1]);
1788 
1789     arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
1790     assert(partition!(a => a > 3, SwapStrategy.unstable)(arr) == [3, 2, 1]);
1791     assert(arr == [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]);
1792 }
1793 
1794 private template isValidIntegralTuple(T)
1795 {
1796     import std.traits : isIntegral;
1797     import std.typecons : isTuple;
1798     static if (isTuple!T)
1799     {
1800         enum isValidIntegralTuple = T.length == 2 &&
1801                 isIntegral!(typeof(T.init[0])) && isIntegral!(typeof(T.init[0]));
1802     }
1803     else
1804     {
1805         enum isValidIntegralTuple = isIntegral!T;
1806     }
1807 }
1808 
1809 
1810 /**
1811 Eliminates elements at given offsets from `range` and returns the shortened
1812 range.
1813 
1814 For example, here is how to remove a single element from an array:
1815 
1816 ----
1817 string[] a = [ "a", "b", "c", "d" ];
1818 a = a.remove(1); // remove element at offset 1
1819 assert(a == [ "a", "c", "d"]);
1820 ----
1821 
1822 Note that `remove` does not change the length of the original range directly;
1823 instead, it returns the shortened range. If its return value is not assigned to
1824 the original range, the original range will retain its original length, though
1825 its contents will have changed:
1826 
1827 ----
1828 int[] a = [ 3, 5, 7, 8 ];
1829 assert(remove(a, 1) == [ 3, 7, 8 ]);
1830 assert(a == [ 3, 7, 8, 8 ]);
1831 ----
1832 
1833 The element at offset `1` has been removed and the rest of the elements have
1834 shifted up to fill its place, however, the original array remains of the same
1835 length. This is because all functions in `std.algorithm` only change $(I
1836 content), not $(I topology). The value `8` is repeated because $(LREF move) was
1837 invoked to rearrange elements, and on integers `move` simply copies the source
1838 to the destination.  To replace `a` with the effect of the removal, simply
1839 assign the slice returned by `remove` to it, as shown in the first example.
1840 
1841 Multiple indices can be passed into `remove`. In that case,
1842 elements at the respective indices are all removed. The indices must
1843 be passed in increasing order, otherwise an exception occurs.
1844 
1845 ----
1846 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
1847 assert(remove(a, 1, 3, 5) ==
1848     [ 0, 2, 4, 6, 7, 8, 9, 10 ]);
1849 ----
1850 
1851 (Note that all indices refer to slots in the $(I original) array, not
1852 in the array as it is being progressively shortened.)
1853 
1854 Tuples of two integral offsets can be used to remove an indices range:
1855 
1856 ----
1857 int[] a = [ 3, 4, 5, 6, 7];
1858 assert(remove(a, 1, tuple(1, 3), 9) == [ 3, 6, 7 ]);
1859 ----
1860 
1861 The tuple passes in a range closed to the left and open to
1862 the right (consistent with built-in slices), e.g. `tuple(1, 3)`
1863 means indices `1` and `2` but not `3`.
1864 
1865 Finally, any combination of integral offsets and tuples composed of two integral
1866 offsets can be passed in:
1867 
1868 ----
1869 int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
1870 assert(remove(a, 1, tuple(3, 5), 9) == [ 0, 2, 5, 6, 7, 8, 10 ]);
1871 ----
1872 
1873 In this case, the slots at positions 1, 3, 4, and 9 are removed from
1874 the array.
1875 
1876 If the need is to remove some elements in the range but the order of
1877 the remaining elements does not have to be preserved, you may want to
1878 pass `SwapStrategy.unstable` to `remove`.
1879 
1880 ----
1881 int[] a = [ 0, 1, 2, 3 ];
1882 assert(remove!(SwapStrategy.unstable)(a, 1) == [ 0, 3, 2 ]);
1883 ----
1884 
1885 In the case above, the element at slot `1` is removed, but replaced
1886 with the last element of the range. Taking advantage of the relaxation
1887 of the stability requirement, `remove` moved elements from the end
1888 of the array over the slots to be removed. This way there is less data
1889 movement to be done which improves the execution time of the function.
1890 
1891 The function `remove` works on bidirectional ranges that have assignable
1892 lvalue elements. The moving strategy is (listed from fastest to slowest):
1893 
1894 $(UL
1895         $(LI If $(D s == SwapStrategy.unstable && isRandomAccessRange!Range &&
1896 hasLength!Range && hasLvalueElements!Range), then elements are moved from the
1897 end of the range into the slots to be filled. In this case, the absolute
1898 minimum of moves is performed.)
1899         $(LI Otherwise, if $(D s ==
1900 SwapStrategy.unstable && isBidirectionalRange!Range && hasLength!Range
1901 && hasLvalueElements!Range), then elements are still moved from the
1902 end of the range, but time is spent on advancing between slots by repeated
1903 calls to `range.popFront`.)
1904         $(LI Otherwise, elements are moved
1905 incrementally towards the front of `range`; a given element is never
1906 moved several times, but more elements are moved than in the previous
1907 cases.)
1908 )
1909 
1910 Params:
1911     s = a SwapStrategy to determine if the original order needs to be preserved
1912     range = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
1913     with a length member
1914     offset = which element(s) to remove
1915 
1916 Returns:
1917     A range containing all of the elements of range with offset removed.
1918 */
1919 Range remove
1920 (SwapStrategy s = SwapStrategy.stable, Range, Offset ...)
1921 (Range range, Offset offset)
1922 if (Offset.length >= 1 && allSatisfy!(isValidIntegralTuple, Offset))
1923 {
1924     // Activate this check when the deprecation of non-integral tuples is over
1925     //import std.traits : isIntegral;
1926     //import std.typecons : isTuple;
1927     //static foreach (T; Offset)
1928     //{
1929         //static if (isTuple!T)
1930         //{
1931             //static assert(T.length == 2 &&
1932                     //isIntegral!(typeof(T.init[0])) && isIntegral!(typeof(T.init[0])),
1933                 //"Each offset must be an integral or a tuple of two integrals." ~
1934                 //"Use `arr.remove(pos1, pos2)` or `arr.remove(tuple(start, begin))`");
1935         //}
1936         //else
1937         //{
1938             //static assert(isIntegral!T,
1939                 //"Each offset must be an integral or a tuple of two integrals." ~
1940                 //"Use `arr.remove(pos1, pos2)` or `arr.remove(tuple(start, begin))`");
1941         //}
1942     //}
1943     return removeImpl!s(range, offset);
1944 }
1945 
1946 /// ditto
1947 deprecated("Use of non-integral tuples is deprecated. Use remove(tuple(start, end).")
1948 Range remove
1949 (SwapStrategy s = SwapStrategy.stable, Range, Offset ...)
1950 (Range range, Offset offset)
1951 if (Offset.length >= 1 && !allSatisfy!(isValidIntegralTuple, Offset))
1952 {
1953     return removeImpl!s(range, offset);
1954 }
1955 
1956 ///
1957 @safe pure unittest
1958 {
1959     import std.typecons : tuple;
1960 
1961     auto a = [ 0, 1, 2, 3, 4, 5 ];
1962     assert(remove!(SwapStrategy.stable)(a, 1) == [ 0, 2, 3, 4, 5 ]);
1963     a = [ 0, 1, 2, 3, 4, 5 ];
1964     assert(remove!(SwapStrategy.stable)(a, 1, 3) == [ 0, 2, 4, 5] );
1965     a = [ 0, 1, 2, 3, 4, 5 ];
1966     assert(remove!(SwapStrategy.stable)(a, 1, tuple(3, 6)) == [ 0, 2 ]);
1967 
1968     a = [ 0, 1, 2, 3, 4, 5 ];
1969     assert(remove!(SwapStrategy.unstable)(a, 1) == [0, 5, 2, 3, 4]);
1970     a = [ 0, 1, 2, 3, 4, 5 ];
1971     assert(remove!(SwapStrategy.unstable)(a, tuple(1, 4)) == [0, 5, 4]);
1972 }
1973 
1974 ///
1975 @safe pure unittest
1976 {
1977     import std.typecons : tuple;
1978 
1979     // Delete an index
1980     assert([4, 5, 6].remove(1) == [4, 6]);
1981 
1982     // Delete multiple indices
1983     assert([4, 5, 6, 7, 8].remove(1, 3) == [4, 6, 8]);
1984 
1985     // Use an indices range
1986     assert([4, 5, 6, 7, 8].remove(tuple(1, 3)) == [4, 7, 8]);
1987 
1988     // Use an indices range and individual indices
1989     assert([4, 5, 6, 7, 8].remove(0, tuple(1, 3), 4) == [7]);
1990 }
1991 
1992 /// `SwapStrategy.unstable` is faster, but doesn't guarantee the same order of the original array
1993 @safe pure unittest
1994 {
1995     assert([5, 6, 7, 8].remove!(SwapStrategy.stable)(1) == [5, 7, 8]);
1996     assert([5, 6, 7, 8].remove!(SwapStrategy.unstable)(1) == [5, 8, 7]);
1997 }
1998 
1999 private auto removeImpl(SwapStrategy s, Range, Offset...)(Range range, Offset offset)
2000 {
2001     static if (isNarrowString!Range)
2002     {
2003         static assert(isMutable!(typeof(range[0])),
2004                 "Elements must be mutable to remove");
2005         static assert(s == SwapStrategy.stable,
2006                 "Only stable removing can be done for character arrays");
2007         return removeStableString(range, offset);
2008     }
2009     else
2010     {
2011         static assert(isBidirectionalRange!Range,
2012                 "Range must be bidirectional");
2013         static assert(hasLvalueElements!Range,
2014                 "Range must have Lvalue elements (see std.range.hasLvalueElements)");
2015 
2016         static if (s == SwapStrategy.unstable)
2017         {
2018             static assert(hasLength!Range,
2019                     "Range must have `length` for unstable remove");
2020             return removeUnstable(range, offset);
2021         }
2022         else static if (s == SwapStrategy.stable)
2023             return removeStable(range, offset);
2024         else
2025             static assert(false,
2026                     "Only SwapStrategy.stable and SwapStrategy.unstable are supported");
2027     }
2028 }
2029 
2030 @safe unittest
2031 {
2032     import std.exception : assertThrown;
2033     import std.range;
2034 
2035     // https://issues.dlang.org/show_bug.cgi?id=10173
2036     int[] test = iota(0, 10).array();
2037     assertThrown(remove!(SwapStrategy.stable)(test, tuple(2, 4), tuple(1, 3)));
2038     assertThrown(remove!(SwapStrategy.unstable)(test, tuple(2, 4), tuple(1, 3)));
2039     assertThrown(remove!(SwapStrategy.stable)(test, 2, 4, 1, 3));
2040     assertThrown(remove!(SwapStrategy.unstable)(test, 2, 4, 1, 3));
2041 }
2042 
2043 @safe unittest
2044 {
2045     import std.range;
2046     int[] a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2047     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2048     assert(remove!(SwapStrategy.stable)(a, 1) ==
2049         [ 0, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]);
2050 
2051     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2052     assert(remove!(SwapStrategy.unstable)(a, 0, 10) ==
2053            [ 9, 1, 2, 3, 4, 5, 6, 7, 8 ]);
2054 
2055     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2056     assert(remove!(SwapStrategy.unstable)(a, 0, tuple(9, 11)) ==
2057             [ 8, 1, 2, 3, 4, 5, 6, 7 ]);
2058     // https://issues.dlang.org/show_bug.cgi?id=5224
2059     a = [ 1, 2, 3, 4 ];
2060     assert(remove!(SwapStrategy.unstable)(a, 2) ==
2061            [ 1, 2, 4 ]);
2062 
2063     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2064     assert(remove!(SwapStrategy.stable)(a, 1, 5) ==
2065         [ 0, 2, 3, 4, 6, 7, 8, 9, 10 ]);
2066 
2067     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2068     assert(remove!(SwapStrategy.stable)(a, 1, 3, 5)
2069             == [ 0, 2, 4, 6, 7, 8, 9, 10]);
2070     a = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
2071     assert(remove!(SwapStrategy.stable)(a, 1, tuple(3, 5))
2072             == [ 0, 2, 5, 6, 7, 8, 9, 10]);
2073 
2074     a = iota(0, 10).array();
2075     assert(remove!(SwapStrategy.unstable)(a, tuple(1, 4), tuple(6, 7))
2076             == [0, 9, 8, 7, 4, 5]);
2077 }
2078 
2079 // https://issues.dlang.org/show_bug.cgi?id=11576
2080 @safe unittest
2081 {
2082     auto arr = [1,2,3];
2083     arr = arr.remove!(SwapStrategy.unstable)(2);
2084     assert(arr == [1,2]);
2085 
2086 }
2087 
2088 // https://issues.dlang.org/show_bug.cgi?id=12889
2089 @safe unittest
2090 {
2091     import std.range;
2092     int[1][] arr = [[0], [1], [2], [3], [4], [5], [6]];
2093     auto orig = arr.dup;
2094     foreach (i; iota(arr.length))
2095     {
2096         assert(orig == arr.remove!(SwapStrategy.unstable)(tuple(i,i)));
2097         assert(orig == arr.remove!(SwapStrategy.stable)(tuple(i,i)));
2098     }
2099 }
2100 
2101 @safe unittest
2102 {
2103     char[] chars = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
2104     remove(chars, 4);
2105     assert(chars == ['a', 'b', 'c', 'd', 'f', 'g', 'h', 'h']);
2106 
2107     char[] bigChars = "∑œ∆¬é˚˙ƒé∂ß¡¡".dup;
2108     assert(remove(bigChars, tuple(4, 6), 8) == ("∑œ∆¬˙ƒ∂ß¡¡"));
2109 
2110     import std.exception : assertThrown;
2111     assertThrown(remove(bigChars.dup, 1, 0));
2112     assertThrown(remove(bigChars.dup, tuple(4, 3)));
2113 }
2114 
2115 private Range removeUnstable(Range, Offset...)(Range range, Offset offset)
2116 {
2117     Tuple!(size_t, "pos", size_t, "len")[offset.length] blackouts;
2118     foreach (i, v; offset)
2119     {
2120         static if (is(typeof(v[0]) : size_t) && is(typeof(v[1]) : size_t))
2121         {
2122             blackouts[i].pos = v[0];
2123             blackouts[i].len = v[1] - v[0];
2124         }
2125         else
2126         {
2127             static assert(is(typeof(v) : size_t), typeof(v).stringof);
2128             blackouts[i].pos = v;
2129             blackouts[i].len = 1;
2130         }
2131         static if (i > 0)
2132         {
2133             import std.exception : enforce;
2134 
2135             enforce(blackouts[i - 1].pos + blackouts[i - 1].len
2136                     <= blackouts[i].pos,
2137                 "remove(): incorrect ordering of elements to remove");
2138         }
2139     }
2140 
2141     size_t left = 0, right = offset.length - 1;
2142     auto tgt = range.save;
2143     size_t tgtPos = 0;
2144 
2145     while (left <= right)
2146     {
2147         // Look for a blackout on the right
2148         if (blackouts[right].pos + blackouts[right].len >= range.length)
2149         {
2150             range.popBackExactly(blackouts[right].len);
2151 
2152             // Since right is unsigned, we must check for this case, otherwise
2153             // we might turn it into size_t.max and the loop condition will not
2154             // fail when it should.
2155             if (right > 0)
2156             {
2157                 --right;
2158                 continue;
2159             }
2160             else
2161                 break;
2162         }
2163         // Advance to next blackout on the left
2164         assert(blackouts[left].pos >= tgtPos, "Next blackout on the left shouldn't appear before the target.");
2165         tgt.popFrontExactly(blackouts[left].pos - tgtPos);
2166         tgtPos = blackouts[left].pos;
2167 
2168         // Number of elements to the right of blackouts[right]
2169         immutable tailLen = range.length - (blackouts[right].pos + blackouts[right].len);
2170         size_t toMove = void;
2171         if (tailLen < blackouts[left].len)
2172         {
2173             toMove = tailLen;
2174             blackouts[left].pos += toMove;
2175             blackouts[left].len -= toMove;
2176         }
2177         else
2178         {
2179             toMove = blackouts[left].len;
2180             ++left;
2181         }
2182         tgtPos += toMove;
2183         foreach (i; 0 .. toMove)
2184         {
2185             move(range.back, tgt.front);
2186             range.popBack();
2187             tgt.popFront();
2188         }
2189     }
2190 
2191     return range;
2192 }
2193 
2194 private Range removeStable(Range, Offset...)(Range range, Offset offset)
2195 {
2196     auto result = range;
2197     auto src = range, tgt = range;
2198     size_t pos;
2199     foreach (pass, i; offset)
2200     {
2201         static if (is(typeof(i[0])) && is(typeof(i[1])))
2202         {
2203             auto from = i[0], delta = i[1] - i[0];
2204         }
2205         else
2206         {
2207             auto from = i;
2208             enum delta = 1;
2209         }
2210 
2211         static if (pass > 0)
2212         {
2213             import std.exception : enforce;
2214             enforce(pos <= from,
2215                     "remove(): incorrect ordering of elements to remove");
2216 
2217             for (; pos < from; ++pos, src.popFront(), tgt.popFront())
2218             {
2219                 move(src.front, tgt.front);
2220             }
2221         }
2222         else
2223         {
2224             src.popFrontExactly(from);
2225             tgt.popFrontExactly(from);
2226             pos = from;
2227         }
2228         // now skip source to the "to" position
2229         src.popFrontExactly(delta);
2230         result.popBackExactly(delta);
2231         pos += delta;
2232     }
2233     // leftover move
2234     moveAll(src, tgt);
2235     return result;
2236 }
2237 
2238 private Range removeStableString(Range, Offset...)(Range range, Offset offsets)
2239 {
2240     import std.utf : stride;
2241     size_t charIdx = 0;
2242     size_t dcharIdx = 0;
2243     size_t charShift = 0;
2244 
2245     void skipOne()
2246     {
2247         charIdx += stride(range[charIdx .. $]);
2248         ++dcharIdx;
2249     }
2250 
2251     void copyBackOne()
2252     {
2253         auto encodedLen = stride(range[charIdx .. $]);
2254         foreach (j; charIdx .. charIdx + encodedLen)
2255             range[j - charShift] = range[j];
2256         charIdx += encodedLen;
2257         ++dcharIdx;
2258     }
2259 
2260     foreach (pass, i; offsets)
2261     {
2262         static if (is(typeof(i[0])) && is(typeof(i[1])))
2263         {
2264             auto from = i[0];
2265             auto delta = i[1] - i[0];
2266         }
2267         else
2268         {
2269             auto from = i;
2270             enum delta = 1;
2271         }
2272 
2273         import std.exception : enforce;
2274         enforce(dcharIdx <= from && delta >= 0,
2275                 "remove(): incorrect ordering of elements to remove");
2276 
2277         while (dcharIdx < from)
2278             static if (pass == 0)
2279                 skipOne();
2280             else
2281                 copyBackOne();
2282 
2283         auto mark = charIdx;
2284         while (dcharIdx < from + delta)
2285             skipOne();
2286         charShift += charIdx - mark;
2287     }
2288 
2289     foreach (i; charIdx .. range.length)
2290         range[i - charShift] = range[i];
2291 
2292     return range[0 .. $ - charShift];
2293 }
2294 
2295 // Use of dynamic arrays as offsets is too error-prone
2296 // https://issues.dlang.org/show_bug.cgi?id=12086
2297 // Activate these tests once the deprecation period of remove with non-integral tuples is over
2298 @safe unittest
2299 {
2300     //static assert(!__traits(compiles, [0, 1, 2, 3, 4].remove([1, 3]) == [0, 3, 4]));
2301     static assert(__traits(compiles, [0, 1, 2, 3, 4].remove(1, 3) == [0, 2, 4]));
2302     //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove([1, 3, 4]) == [0, 3, 4])));
2303     //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove(tuple(1, 3, 4)) == [0, 3, 4])));
2304 
2305     import std.range : only;
2306     //static assert(!__traits(compiles, assert([0, 1, 2, 3, 4].remove(only(1, 3)) == [0, 3, 4])));
2307     static assert(__traits(compiles, assert([0, 1, 2, 3, 4].remove(1, 3) == [0, 2, 4])));
2308 }
2309 
2310 /**
2311 Reduces the length of the
2312 $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives) `range` by removing
2313 elements that satisfy `pred`. If `s = SwapStrategy.unstable`,
2314 elements are moved from the right end of the range over the elements
2315 to eliminate. If `s = SwapStrategy.stable` (the default),
2316 elements are moved progressively to front such that their relative
2317 order is preserved. Returns the filtered range.
2318 
2319 Params:
2320     range = a bidirectional ranges with lvalue elements
2321         or mutable character arrays
2322 
2323 Returns:
2324     the range with all of the elements where `pred` is `true`
2325     removed
2326 */
2327 Range remove(alias pred, SwapStrategy s = SwapStrategy.stable, Range)(Range range)
2328 {
2329     import std.functional : unaryFun;
2330     alias pred_ = unaryFun!pred;
2331     static if (isNarrowString!Range)
2332     {
2333         static assert(isMutable!(typeof(range[0])),
2334                 "Elements must be mutable to remove");
2335         static assert(s == SwapStrategy.stable,
2336                 "Only stable removing can be done for character arrays");
2337         return removePredString!pred_(range);
2338     }
2339     else
2340     {
2341         static assert(isBidirectionalRange!Range,
2342                 "Range must be bidirectional");
2343         static assert(hasLvalueElements!Range,
2344                 "Range must have Lvalue elements (see std.range.hasLvalueElements)");
2345         static if (s == SwapStrategy.unstable)
2346             return removePredUnstable!pred_(range);
2347         else static if (s == SwapStrategy.stable)
2348             return removePredStable!pred_(range);
2349         else
2350             static assert(false,
2351                     "Only SwapStrategy.stable and SwapStrategy.unstable are supported");
2352     }
2353 }
2354 
2355 ///
2356 @safe unittest
2357 {
2358     static immutable base = [1, 2, 3, 2, 4, 2, 5, 2];
2359 
2360     int[] arr = base[].dup;
2361 
2362     // using a string-based predicate
2363     assert(remove!("a == 2")(arr) == [ 1, 3, 4, 5 ]);
2364 
2365     // The original array contents have been modified,
2366     // so we need to reset it to its original state.
2367     // The length is unmodified however.
2368     arr[] = base[];
2369 
2370     // using a lambda predicate
2371     assert(remove!(a => a == 2)(arr) == [ 1, 3, 4, 5 ]);
2372 }
2373 
2374 @safe unittest
2375 {
2376     int[] a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
2377     assert(remove!("a == 2", SwapStrategy.unstable)(a) ==
2378             [ 1, 6, 3, 5, 3, 4, 5 ]);
2379     a = [ 1, 2, 3, 2, 3, 4, 5, 2, 5, 6 ];
2380     assert(remove!("a == 2", SwapStrategy.stable)(a) ==
2381             [ 1, 3, 3, 4, 5, 5, 6 ]);
2382 }
2383 
2384 @nogc @safe unittest
2385 {
2386     // @nogc test
2387     static int[] arr = [0,1,2,3,4,5,6,7,8,9];
2388     alias pred = e => e < 5;
2389 
2390     auto r = arr[].remove!(SwapStrategy.unstable)(0);
2391     r = r.remove!(SwapStrategy.stable)(0);
2392     r = r.remove!(pred, SwapStrategy.unstable);
2393     r = r.remove!(pred, SwapStrategy.stable);
2394 }
2395 
2396 @safe unittest
2397 {
2398     import std.algorithm.comparison : min;
2399     import std.algorithm.searching : all, any;
2400     import std.algorithm.sorting : isStrictlyMonotonic;
2401     import std.array : array;
2402     import std.meta : AliasSeq;
2403     import std.range : iota, only;
2404     import std.typecons : Tuple;
2405     alias E = Tuple!(int, int);
2406     alias S = Tuple!(E);
2407     S[] soffsets;
2408     foreach (start; 0 .. 5)
2409     foreach (end; min(start+1,5) .. 5)
2410           soffsets ~= S(E(start,end));
2411     alias D = Tuple!(E, E);
2412     D[] doffsets;
2413     foreach (start1; 0 .. 10)
2414     foreach (end1; min(start1+1,10) .. 10)
2415     foreach (start2; end1 .. 10)
2416     foreach (end2; min(start2+1,10) .. 10)
2417           doffsets ~= D(E(start1,end1),E(start2,end2));
2418     alias T = Tuple!(E, E, E);
2419     T[] toffsets;
2420     foreach (start1; 0 .. 15)
2421     foreach (end1; min(start1+1,15) .. 15)
2422     foreach (start2; end1 .. 15)
2423     foreach (end2; min(start2+1,15) .. 15)
2424     foreach (start3; end2 .. 15)
2425     foreach (end3; min(start3+1,15) .. 15)
2426             toffsets ~= T(E(start1,end1),E(start2,end2),E(start3,end3));
2427 
2428     static void verify(O...)(int[] r, int len, int removed, bool stable, O offsets)
2429     {
2430         assert(r.length == len - removed);
2431         assert(!stable || r.isStrictlyMonotonic);
2432         assert(r.all!(e => all!(o => e < o[0] || e >= o[1])(offsets.only)));
2433     }
2434 
2435     static foreach (offsets; AliasSeq!(soffsets,doffsets,toffsets))
2436     foreach (os; offsets)
2437     {
2438         int len = 5*os.length;
2439         auto w = iota(0, len).array;
2440         auto x = w.dup;
2441         auto y = w.dup;
2442         auto z = w.dup;
2443         alias pred = e => any!(o => o[0] <= e && e < o[1])(only(os.expand));
2444         w = w.remove!(SwapStrategy.unstable)(os.expand);
2445         x = x.remove!(SwapStrategy.stable)(os.expand);
2446         y = y.remove!(pred, SwapStrategy.unstable);
2447         z = z.remove!(pred, SwapStrategy.stable);
2448         int removed;
2449         foreach (o; os)
2450             removed += o[1] - o[0];
2451         verify(w, len, removed, false, os[]);
2452         verify(x, len, removed, true, os[]);
2453         verify(y, len, removed, false, os[]);
2454         verify(z, len, removed, true, os[]);
2455         assert(w == y);
2456         assert(x == z);
2457     }
2458 }
2459 
2460 @safe unittest
2461 {
2462     char[] chars = "abcdefg".dup;
2463     assert(chars.remove!(dc => dc == 'c' || dc == 'f') == "abdeg");
2464     assert(chars == "abdegfg");
2465 
2466     assert(chars.remove!"a == 'd'" == "abegfg");
2467 
2468     char[] bigChars = "¥^¨^©é√∆π".dup;
2469     assert(bigChars.remove!(dc => dc == "¨"d[0] || dc == "é"d[0]) ==  "¥^^©√∆π");
2470 }
2471 
2472 private Range removePredUnstable(alias pred, Range)(Range range)
2473 {
2474     auto result = range;
2475     for (;!range.empty;)
2476     {
2477         if (!pred(range.front))
2478         {
2479             range.popFront();
2480             continue;
2481         }
2482         move(range.back, range.front);
2483         range.popBack();
2484         result.popBack();
2485     }
2486     return result;
2487 }
2488 
2489 private Range removePredStable(alias pred, Range)(Range range)
2490 {
2491     auto result = range;
2492     auto tgt = range;
2493     for (; !range.empty; range.popFront())
2494     {
2495         if (pred(range.front))
2496         {
2497             // yank this guy
2498             result.popBack();
2499             continue;
2500         }
2501         // keep this guy
2502         move(range.front, tgt.front);
2503         tgt.popFront();
2504     }
2505     return result;
2506 }
2507 
2508 private Range removePredString(alias pred, SwapStrategy s = SwapStrategy.stable, Range)
2509 (Range range)
2510 {
2511     import std.utf : decode;
2512     import std.functional : unaryFun;
2513 
2514     alias pred_ = unaryFun!pred;
2515 
2516     size_t charIdx = 0;
2517     size_t charShift = 0;
2518     while (charIdx < range.length)
2519     {
2520         size_t start = charIdx;
2521         if (pred_(decode(range, charIdx)))
2522         {
2523             charShift += charIdx - start;
2524             break;
2525         }
2526     }
2527     while (charIdx < range.length)
2528     {
2529         size_t start = charIdx;
2530         auto doRemove = pred_(decode(range, charIdx));
2531         auto encodedLen = charIdx - start;
2532         if (doRemove)
2533             charShift += encodedLen;
2534         else
2535             foreach (i; start .. charIdx)
2536                 range[i - charShift] = range[i];
2537     }
2538 
2539     return range[0 .. $ - charShift];
2540 }
2541 
2542 // reverse
2543 /**
2544 Reverses `r` in-place.  Performs `r.length / 2` evaluations of `swap`.
2545 UTF sequences consisting of multiple code units are preserved properly.
2546 
2547 Params:
2548     r = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
2549         with either swappable elements, a random access range with a length member,
2550         or a narrow string
2551 
2552 Returns: `r`
2553 
2554 Note:
2555     When passing a string with unicode modifiers on characters, such as `\u0301`,
2556     this function will not properly keep the position of the modifier. For example,
2557     reversing `ba\u0301d` ("bád") will result in d\u0301ab ("d́ab") instead of
2558     `da\u0301b` ("dáb").
2559 
2560 See_Also: $(REF retro, std,range) for a lazy reverse without changing `r`
2561 */
2562 Range reverse(Range)(Range r)
2563 if (isBidirectionalRange!Range &&
2564         (hasSwappableElements!Range ||
2565          (hasAssignableElements!Range && hasLength!Range && isRandomAccessRange!Range) ||
2566          (isNarrowString!Range && isAssignable!(ElementType!Range))))
2567 {
2568     static if (isRandomAccessRange!Range && hasLength!Range)
2569     {
2570         //swapAt is in fact the only way to swap non lvalue ranges
2571         immutable last = r.length - 1;
2572         immutable steps = r.length / 2;
2573         for (size_t i = 0; i < steps; i++)
2574         {
2575             r.swapAt(i, last - i);
2576         }
2577         return r;
2578     }
2579     else static if (isNarrowString!Range && isAssignable!(ElementType!Range))
2580     {
2581         import std.string : representation;
2582         import std.utf : stride;
2583 
2584         auto raw = representation(r);
2585         for (size_t i = 0; i < r.length;)
2586         {
2587             immutable step = stride(r, i);
2588             if (step > 1)
2589             {
2590                 .reverse(raw[i .. i + step]);
2591                 i += step;
2592             }
2593             else
2594             {
2595                 ++i;
2596             }
2597         }
2598         reverse(raw);
2599         return r;
2600     }
2601     else
2602     {
2603         while (!r.empty)
2604         {
2605             swap(r.front, r.back);
2606             r.popFront();
2607             if (r.empty) break;
2608             r.popBack();
2609         }
2610         return r;
2611     }
2612 }
2613 
2614 ///
2615 @safe unittest
2616 {
2617     int[] arr = [ 1, 2, 3 ];
2618     assert(arr.reverse == [ 3, 2, 1 ]);
2619 }
2620 
2621 @safe unittest
2622 {
2623     int[] range = null;
2624     reverse(range);
2625     range = [ 1 ];
2626     reverse(range);
2627     assert(range == [1]);
2628     range = [1, 2];
2629     reverse(range);
2630     assert(range == [2, 1]);
2631     range = [1, 2, 3];
2632     assert(range.reverse == [3, 2, 1]);
2633 }
2634 
2635 ///
2636 @safe unittest
2637 {
2638     char[] arr = "hello\U00010143\u0100\U00010143".dup;
2639     assert(arr.reverse == "\U00010143\u0100\U00010143olleh");
2640 }
2641 
2642 @safe unittest
2643 {
2644     void test(string a, string b)
2645     {
2646         auto c = a.dup;
2647         reverse(c);
2648         assert(c == b, c ~ " != " ~ b);
2649     }
2650 
2651     test("a", "a");
2652     test(" ", " ");
2653     test("\u2029", "\u2029");
2654     test("\u0100", "\u0100");
2655     test("\u0430", "\u0430");
2656     test("\U00010143", "\U00010143");
2657     test("abcdefcdef", "fedcfedcba");
2658     test("hello\U00010143\u0100\U00010143", "\U00010143\u0100\U00010143olleh");
2659 }
2660 
2661 /**
2662     The strip group of functions allow stripping of either leading, trailing,
2663     or both leading and trailing elements.
2664 
2665     The `stripLeft` function will strip the `front` of the range,
2666     the `stripRight` function will strip the `back` of the range,
2667     while the `strip` function will strip both the `front` and `back`
2668     of the range.
2669 
2670     Note that the `strip` and `stripRight` functions require the range to
2671     be a $(LREF BidirectionalRange) range.
2672 
2673     All of these functions come in two varieties: one takes a target element,
2674     where the range will be stripped as long as this element can be found.
2675     The other takes a lambda predicate, where the range will be stripped as
2676     long as the predicate returns true.
2677 
2678     Params:
2679         range = a $(REF_ALTTEXT bidirectional range, isBidirectionalRange, std,range,primitives)
2680         or $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
2681         element = the elements to remove
2682 
2683     Returns:
2684         a Range with all of range except element at the start and end
2685 */
2686 Range strip(Range, E)(Range range, E element)
2687 if (isBidirectionalRange!Range && is(typeof(range.front == element) : bool))
2688 {
2689     return range.stripLeft(element).stripRight(element);
2690 }
2691 
2692 /// ditto
2693 Range strip(alias pred, Range)(Range range)
2694 if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool))
2695 {
2696     return range.stripLeft!pred().stripRight!pred();
2697 }
2698 
2699 /// ditto
2700 Range stripLeft(Range, E)(Range range, E element)
2701 if (isInputRange!Range && is(typeof(range.front == element) : bool))
2702 {
2703     import std.algorithm.searching : find;
2704     return find!((auto ref a) => a != element)(range);
2705 }
2706 
2707 /// ditto
2708 Range stripLeft(alias pred, Range)(Range range)
2709 if (isInputRange!Range && is(typeof(pred(range.front)) : bool))
2710 {
2711     import std.algorithm.searching : find;
2712     import std.functional : not;
2713 
2714     return find!(not!pred)(range);
2715 }
2716 
2717 /// ditto
2718 Range stripRight(Range, E)(Range range, E element)
2719 if (isBidirectionalRange!Range && is(typeof(range.back == element) : bool))
2720 {
2721     for (; !range.empty; range.popBack())
2722     {
2723         if (range.back != element)
2724             break;
2725     }
2726     return range;
2727 }
2728 
2729 /// ditto
2730 Range stripRight(alias pred, Range)(Range range)
2731 if (isBidirectionalRange!Range && is(typeof(pred(range.back)) : bool))
2732 {
2733     for (; !range.empty; range.popBack())
2734     {
2735         if (!pred(range.back))
2736             break;
2737     }
2738     return range;
2739 }
2740 
2741 /// Strip leading and trailing elements equal to the target element.
2742 @safe pure unittest
2743 {
2744     assert("  foobar  ".strip(' ') == "foobar");
2745     assert("00223.444500".strip('0') == "223.4445");
2746     assert("ëëêéüŗōpéêëë".strip('ë') == "êéüŗōpéê");
2747     assert([1, 1, 0, 1, 1].strip(1) == [0]);
2748     assert([0.0, 0.01, 0.01, 0.0].strip(0).length == 2);
2749 }
2750 
2751 /// Strip leading and trailing elements while the predicate returns true.
2752 @safe pure unittest
2753 {
2754     assert("  foobar  ".strip!(a => a == ' ')() == "foobar");
2755     assert("00223.444500".strip!(a => a == '0')() == "223.4445");
2756     assert("ëëêéüŗōpéêëë".strip!(a => a == 'ë')() == "êéüŗōpéê");
2757     assert([1, 1, 0, 1, 1].strip!(a => a == 1)() == [0]);
2758     assert([0.0, 0.01, 0.5, 0.6, 0.01, 0.0].strip!(a => a < 0.4)().length == 2);
2759 }
2760 
2761 /// Strip leading elements equal to the target element.
2762 @safe pure unittest
2763 {
2764     assert("  foobar  ".stripLeft(' ') == "foobar  ");
2765     assert("00223.444500".stripLeft('0') == "223.444500");
2766     assert("ůůűniçodêéé".stripLeft('ů') == "űniçodêéé");
2767     assert([1, 1, 0, 1, 1].stripLeft(1) == [0, 1, 1]);
2768     assert([0.0, 0.01, 0.01, 0.0].stripLeft(0).length == 3);
2769 }
2770 
2771 /// Strip leading elements while the predicate returns true.
2772 @safe pure unittest
2773 {
2774     assert("  foobar  ".stripLeft!(a => a == ' ')() == "foobar  ");
2775     assert("00223.444500".stripLeft!(a => a == '0')() == "223.444500");
2776     assert("ůůűniçodêéé".stripLeft!(a => a == 'ů')() == "űniçodêéé");
2777     assert([1, 1, 0, 1, 1].stripLeft!(a => a == 1)() == [0, 1, 1]);
2778     assert([0.0, 0.01, 0.10, 0.5, 0.6].stripLeft!(a => a < 0.4)().length == 2);
2779 }
2780 
2781 /// Strip trailing elements equal to the target element.
2782 @safe pure unittest
2783 {
2784     assert("  foobar  ".stripRight(' ') == "  foobar");
2785     assert("00223.444500".stripRight('0') == "00223.4445");
2786     assert("ùniçodêéé".stripRight('é') == "ùniçodê");
2787     assert([1, 1, 0, 1, 1].stripRight(1) == [1, 1, 0]);
2788     assert([0.0, 0.01, 0.01, 0.0].stripRight(0).length == 3);
2789 }
2790 
2791 /// Strip trailing elements while the predicate returns true.
2792 @safe pure unittest
2793 {
2794     assert("  foobar  ".stripRight!(a => a == ' ')() == "  foobar");
2795     assert("00223.444500".stripRight!(a => a == '0')() == "00223.4445");
2796     assert("ùniçodêéé".stripRight!(a => a == 'é')() == "ùniçodê");
2797     assert([1, 1, 0, 1, 1].stripRight!(a => a == 1)() == [1, 1, 0]);
2798     assert([0.0, 0.01, 0.10, 0.5, 0.6].stripRight!(a => a > 0.4)().length == 3);
2799 }
2800 
2801 // swap
2802 /**
2803 Swaps `lhs` and `rhs`. The instances `lhs` and `rhs` are moved in
2804 memory, without ever calling `opAssign`, nor any other function. `T`
2805 need not be assignable at all to be swapped.
2806 
2807 If `lhs` and `rhs` reference the same instance, then nothing is done.
2808 
2809 `lhs` and `rhs` must be mutable. If `T` is a struct or union, then
2810 its fields must also all be (recursively) mutable.
2811 
2812 Params:
2813     lhs = Data to be swapped with `rhs`.
2814     rhs = Data to be swapped with `lhs`.
2815 */
2816 void swap(T)(ref T lhs, ref T rhs) @trusted pure nothrow @nogc
2817 if (isBlitAssignable!T && !is(typeof(lhs.proxySwap(rhs))))
2818 {
2819     import std.traits : hasAliasing, hasElaborateAssign, isAssignable,
2820                         isStaticArray;
2821     static if (hasAliasing!T) if (!__ctfe)
2822     {
2823         import std.exception : doesPointTo;
2824         assert(!doesPointTo(lhs, lhs), "Swap: lhs internal pointer.");
2825         assert(!doesPointTo(rhs, rhs), "Swap: rhs internal pointer.");
2826         assert(!doesPointTo(lhs, rhs), "Swap: lhs points to rhs.");
2827         assert(!doesPointTo(rhs, lhs), "Swap: rhs points to lhs.");
2828     }
2829 
2830     static if (hasElaborateAssign!T || !isAssignable!T)
2831     {
2832         if (&lhs != &rhs)
2833         {
2834             // For structs with non-trivial assignment, move memory directly
2835             ubyte[T.sizeof] t = void;
2836             auto a = (cast(ubyte*) &lhs)[0 .. T.sizeof];
2837             auto b = (cast(ubyte*) &rhs)[0 .. T.sizeof];
2838             t[] = a[];
2839             a[] = b[];
2840             b[] = t[];
2841         }
2842     }
2843     else
2844     {
2845         //Avoid assigning overlapping arrays. Dynamic arrays are fine, because
2846         //it's their ptr and length properties which get assigned rather
2847         //than their elements when assigning them, but static arrays are value
2848         //types and therefore all of their elements get copied as part of
2849         //assigning them, which would be assigning overlapping arrays if lhs
2850         //and rhs were the same array.
2851         static if (isStaticArray!T)
2852         {
2853             if (lhs.ptr == rhs.ptr)
2854                 return;
2855         }
2856 
2857         // For non-elaborate-assign types, suffice to do the classic swap
2858         static if (__traits(hasCopyConstructor, T))
2859         {
2860             // don't invoke any elaborate constructors either
2861             T tmp = void;
2862             tmp = lhs;
2863         }
2864         else
2865             auto tmp = lhs;
2866         lhs = rhs;
2867         rhs = tmp;
2868     }
2869 }
2870 
2871 ///
2872 @safe unittest
2873 {
2874     // Swapping POD (plain old data) types:
2875     int a = 42, b = 34;
2876     swap(a, b);
2877     assert(a == 34 && b == 42);
2878 
2879     // Swapping structs with indirection:
2880     static struct S { int x; char c; int[] y; }
2881     S s1 = { 0, 'z', [ 1, 2 ] };
2882     S s2 = { 42, 'a', [ 4, 6 ] };
2883     swap(s1, s2);
2884     assert(s1.x == 42);
2885     assert(s1.c == 'a');
2886     assert(s1.y == [ 4, 6 ]);
2887 
2888     assert(s2.x == 0);
2889     assert(s2.c == 'z');
2890     assert(s2.y == [ 1, 2 ]);
2891 
2892     // Immutables cannot be swapped:
2893     immutable int imm1 = 1, imm2 = 2;
2894     static assert(!__traits(compiles, swap(imm1, imm2)));
2895 
2896     int c = imm1 + 0;
2897     int d = imm2 + 0;
2898     swap(c, d);
2899     assert(c == 2);
2900     assert(d == 1);
2901 }
2902 
2903 ///
2904 @safe unittest
2905 {
2906     // Non-copyable types can still be swapped.
2907     static struct NoCopy
2908     {
2909         this(this) { assert(0); }
2910         int n;
2911         string s;
2912     }
2913     NoCopy nc1, nc2;
2914     nc1.n = 127; nc1.s = "abc";
2915     nc2.n = 513; nc2.s = "uvwxyz";
2916 
2917     swap(nc1, nc2);
2918     assert(nc1.n == 513 && nc1.s == "uvwxyz");
2919     assert(nc2.n == 127 && nc2.s == "abc");
2920 
2921     swap(nc1, nc1);
2922     swap(nc2, nc2);
2923     assert(nc1.n == 513 && nc1.s == "uvwxyz");
2924     assert(nc2.n == 127 && nc2.s == "abc");
2925 
2926     // Types containing non-copyable fields can also be swapped.
2927     static struct NoCopyHolder
2928     {
2929         NoCopy noCopy;
2930     }
2931     NoCopyHolder h1, h2;
2932     h1.noCopy.n = 31; h1.noCopy.s = "abc";
2933     h2.noCopy.n = 65; h2.noCopy.s = null;
2934 
2935     swap(h1, h2);
2936     assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
2937     assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
2938 
2939     swap(h1, h1);
2940     swap(h2, h2);
2941     assert(h1.noCopy.n == 65 && h1.noCopy.s == null);
2942     assert(h2.noCopy.n == 31 && h2.noCopy.s == "abc");
2943 
2944     // Const types cannot be swapped.
2945     const NoCopy const1, const2;
2946     assert(const1.n == 0 && const2.n == 0);
2947     static assert(!__traits(compiles, swap(const1, const2)));
2948 }
2949 
2950 // https://issues.dlang.org/show_bug.cgi?id=4789
2951 @safe unittest
2952 {
2953     int[1] s = [1];
2954     swap(s, s);
2955 
2956     int[3] a = [1, 2, 3];
2957     swap(a[1], a[2]);
2958     assert(a == [1, 3, 2]);
2959 }
2960 
2961 @safe unittest
2962 {
2963     static struct NoAssign
2964     {
2965         int i;
2966         void opAssign(NoAssign) @disable;
2967     }
2968     auto s1 = NoAssign(1);
2969     auto s2 = NoAssign(2);
2970     swap(s1, s2);
2971     assert(s1.i == 2);
2972     assert(s2.i == 1);
2973 }
2974 
2975 @safe unittest
2976 {
2977     struct S
2978     {
2979         const int i;
2980         int i2 = 2;
2981         int i3 = 3;
2982     }
2983     S s;
2984     static assert(!__traits(compiles, swap(s, s)));
2985     swap(s.i2, s.i3);
2986     assert(s.i2 == 3);
2987     assert(s.i3 == 2);
2988 }
2989 
2990 // https://issues.dlang.org/show_bug.cgi?id=11853
2991 @safe unittest
2992 {
2993     import std.traits : isAssignable;
2994     alias T = Tuple!(int, double);
2995     static assert(isAssignable!T);
2996 }
2997 
2998 // https://issues.dlang.org/show_bug.cgi?id=12024
2999 @safe unittest
3000 {
3001     import std.datetime;
3002     SysTime a, b;
3003     swap(a, b);
3004 }
3005 
3006 // https://issues.dlang.org/show_bug.cgi?id=9975
3007 @system unittest
3008 {
3009     import std.exception : doesPointTo, mayPointTo;
3010     static struct S2
3011     {
3012         union
3013         {
3014             size_t sz;
3015             string s;
3016         }
3017     }
3018     S2 a , b;
3019     a.sz = -1;
3020     assert(!doesPointTo(a, b));
3021     assert( mayPointTo(a, b));
3022     swap(a, b);
3023 
3024     //Note: we can catch an error here, because there is no RAII in this test
3025     import std.exception : assertThrown;
3026     void* p, pp;
3027     p = &p;
3028     assertThrown!Error(move(p));
3029     assertThrown!Error(move(p, pp));
3030     assertThrown!Error(swap(p, pp));
3031 }
3032 
3033 @system unittest
3034 {
3035     static struct A
3036     {
3037         int* x;
3038         this(this) { x = new int; }
3039     }
3040     A a1, a2;
3041     swap(a1, a2);
3042 
3043     static struct B
3044     {
3045         int* x;
3046         void opAssign(B) { x = new int; }
3047     }
3048     B b1, b2;
3049     swap(b1, b2);
3050 }
3051 
3052 // https://issues.dlang.org/show_bug.cgi?id=20732
3053 @safe unittest
3054 {
3055     static struct A
3056     {
3057         int x;
3058         this(scope ref return const A other)
3059         {
3060             import std.stdio;
3061             x = other.x;
3062             // note, struct functions inside @safe functions infer ALL
3063             // attributes, so the following 3 lines are meant to prevent this.
3064             new int; // prevent @nogc inference
3065             writeln("impure"); // prevent pure inference
3066             throw new Exception(""); // prevent nothrow inference
3067         }
3068     }
3069 
3070     A a1, a2;
3071     swap(a1, a2);
3072 
3073     A[1] a3, a4;
3074     swap(a3, a4);
3075 }
3076 
3077 /// ditto
3078 void swap(T)(ref T lhs, ref T rhs)
3079 if (is(typeof(lhs.proxySwap(rhs))))
3080 {
3081     lhs.proxySwap(rhs);
3082 }
3083 
3084 /**
3085 Swaps two elements in-place of a range `r`,
3086 specified by their indices `i1` and `i2`.
3087 
3088 Params:
3089     r  = a range with swappable elements
3090     i1 = first index
3091     i2 = second index
3092 */
3093 void swapAt(R)(auto ref R r, size_t i1, size_t i2)
3094 {
3095     static if (is(typeof(&r.swapAt)))
3096     {
3097         r.swapAt(i1, i2);
3098     }
3099     else static if (is(typeof(&r[i1])))
3100     {
3101         swap(r[i1], r[i2]);
3102     }
3103     else
3104     {
3105         if (i1 == i2) return;
3106         auto t1 = r.moveAt(i1);
3107         auto t2 = r.moveAt(i2);
3108         r[i2] = t1;
3109         r[i1] = t2;
3110     }
3111 }
3112 
3113 ///
3114 pure @safe nothrow unittest
3115 {
3116     import std.algorithm.comparison : equal;
3117     auto a = [1, 2, 3];
3118     a.swapAt(1, 2);
3119     assert(a.equal([1, 3, 2]));
3120 }
3121 
3122 pure @safe nothrow unittest
3123 {
3124     import std.algorithm.comparison : equal;
3125     auto a = [4, 5, 6];
3126     a.swapAt(1, 1);
3127     assert(a.equal([4, 5, 6]));
3128 }
3129 
3130 pure @safe nothrow unittest
3131 {
3132     // test non random access ranges
3133     import std.algorithm.comparison : equal;
3134     import std.array : array;
3135 
3136     char[] b = ['a', 'b', 'c'];
3137     b.swapAt(1, 2);
3138     assert(b.equal(['a', 'c', 'b']));
3139 
3140     int[3] c = [1, 2, 3];
3141     c.swapAt(1, 2);
3142     assert(c.array.equal([1, 3, 2]));
3143 
3144     // opIndex returns lvalue
3145     struct RandomIndexType(T)
3146     {
3147         T payload;
3148 
3149         @property ref auto opIndex(size_t i)
3150         {
3151            return payload[i];
3152         }
3153 
3154     }
3155     auto d = RandomIndexType!(int[])([4, 5, 6]);
3156     d.swapAt(1, 2);
3157     assert(d.payload.equal([4, 6, 5]));
3158 
3159     // custom moveAt and opIndexAssign
3160     struct RandomMoveAtType(T)
3161     {
3162         T payload;
3163 
3164         ElementType!T moveAt(size_t i)
3165         {
3166            return payload.moveAt(i);
3167         }
3168 
3169         void opIndexAssign(ElementType!T val, size_t idx)
3170         {
3171             payload[idx] = val;
3172         }
3173     }
3174     auto e = RandomMoveAtType!(int[])([7, 8, 9]);
3175     e.swapAt(1, 2);
3176     assert(e.payload.equal([7, 9, 8]));
3177 
3178 
3179     // custom swapAt
3180     struct RandomSwapAtType(T)
3181     {
3182         T payload;
3183 
3184         void swapAt(size_t i)
3185         {
3186            return payload.swapAt(i);
3187         }
3188     }
3189     auto f = RandomMoveAtType!(int[])([10, 11, 12]);
3190     swapAt(f, 1, 2);
3191     assert(f.payload.equal([10, 12, 11]));
3192 }
3193 
3194 private void swapFront(R1, R2)(R1 r1, R2 r2)
3195 if (isInputRange!R1 && isInputRange!R2)
3196 {
3197     static if (is(typeof(swap(r1.front, r2.front))))
3198     {
3199         swap(r1.front, r2.front);
3200     }
3201     else
3202     {
3203         auto t1 = moveFront(r1), t2 = moveFront(r2);
3204         r1.front = move(t2);
3205         r2.front = move(t1);
3206     }
3207 }
3208 
3209 // swapRanges
3210 /**
3211 Swaps all elements of `r1` with successive elements in `r2`.
3212 Returns a tuple containing the remainder portions of `r1` and $(D
3213 r2) that were not swapped (one of them will be empty). The ranges may
3214 be of different types but must have the same element type and support
3215 swapping.
3216 
3217 Params:
3218     r1 = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3219          with swappable elements
3220     r2 = an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3221          with swappable elements
3222 
3223 Returns:
3224     Tuple containing the remainder portions of r1 and r2 that were not swapped
3225 */
3226 Tuple!(InputRange1, InputRange2)
3227 swapRanges(InputRange1, InputRange2)(InputRange1 r1, InputRange2 r2)
3228 if (hasSwappableElements!InputRange1 && hasSwappableElements!InputRange2
3229     && is(ElementType!InputRange1 == ElementType!InputRange2))
3230 {
3231     for (; !r1.empty && !r2.empty; r1.popFront(), r2.popFront())
3232     {
3233         swap(r1.front, r2.front);
3234     }
3235     return tuple(r1, r2);
3236 }
3237 
3238 ///
3239 @safe unittest
3240 {
3241     import std.range : empty;
3242     int[] a = [ 100, 101, 102, 103 ];
3243     int[] b = [ 0, 1, 2, 3 ];
3244     auto c = swapRanges(a[1 .. 3], b[2 .. 4]);
3245     assert(c[0].empty && c[1].empty);
3246     assert(a == [ 100, 2, 3, 103 ]);
3247     assert(b == [ 0, 1, 101, 102 ]);
3248 }
3249 
3250 /**
3251 Initializes each element of `range` with `value`.
3252 Assumes that the elements of the range are uninitialized.
3253 This is of interest for structs that
3254 define copy constructors (for all other types, $(LREF fill) and
3255 uninitializedFill are equivalent).
3256 
3257 Params:
3258         range = An
3259                 $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
3260                 that exposes references to its elements and has assignable
3261                 elements
3262         value = Assigned to each element of range
3263 
3264 See_Also:
3265         $(LREF fill)
3266         $(LREF initializeAll)
3267  */
3268 void uninitializedFill(Range, Value)(Range range, Value value)
3269 if (isInputRange!Range && hasLvalueElements!Range && is(typeof(range.front = value)))
3270 {
3271     import std.traits : hasElaborateAssign;
3272 
3273     alias T = ElementType!Range;
3274     static if (hasElaborateAssign!T)
3275     {
3276         import core.internal.lifetime : emplaceRef;
3277 
3278         // Must construct stuff by the book
3279         for (; !range.empty; range.popFront())
3280             emplaceRef!T(range.front, value);
3281     }
3282     else
3283         // Doesn't matter whether fill is initialized or not
3284         return fill(range, value);
3285 }
3286 
3287 ///
3288 nothrow @system unittest
3289 {
3290     import core.stdc.stdlib : malloc, free;
3291 
3292     auto s = (cast(int*) malloc(5 * int.sizeof))[0 .. 5];
3293     uninitializedFill(s, 42);
3294     assert(s == [ 42, 42, 42, 42, 42 ]);
3295 
3296     scope(exit) free(s.ptr);
3297 }