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