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