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