1 /** 2 * This module provides an `Array` type with deterministic memory usage not 3 * reliant on the GC, as an alternative to the built-in arrays. 4 * 5 * This module is a submodule of $(MREF std, container). 6 * 7 * Source: $(PHOBOSSRC std/container/array.d) 8 * 9 * Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 10 * 11 * License: Distributed under the Boost Software License, Version 1.0. 12 * (See accompanying file LICENSE_1_0.txt or copy at $(HTTP 13 * boost.org/LICENSE_1_0.txt)). 14 * 15 * Authors: $(HTTP erdani.com, Andrei Alexandrescu) 16 * 17 * $(SCRIPT inhibitQuickIndex = 1;) 18 */ 19 module std.container.array; 20 21 import core.exception : RangeError; 22 import std.range.primitives; 23 import std.traits; 24 25 public import std.container.util; 26 27 pure @system unittest 28 { 29 // We test multiple array lengths in order to ensure that the "a1.capacity == a0.length" test is meaningful 30 // for the version in which the constructor uses insertBack 31 // (because for some lengths, the test passes even without reserve). 32 for (size_t n = 0; n < 100; ++n) 33 { 34 float[] a0; 35 { 36 import std.range : iota; 37 import std.array : array; 38 import std.algorithm.iteration : map; 39 a0 = iota (0, n).map!(i => i * 1.1f).array; 40 } 41 42 auto a1 = Array!float(a0); 43 44 // We check that a1 has the same length and contents as a0: 45 { 46 assert(a1.length == a0.length); 47 48 // I wish that I could write "assert(a1[] == a0[]);", 49 // but the compiler complains: "Error: incompatible types for `(a1.opSlice()) == (a0[])`: `RangeT!(Array!float)` and `float[]`". 50 import std.algorithm.comparison : equal; 51 assert(equal(a1[], a0[])); 52 } 53 54 // We check that a1's constructor has called reserve (to maintain good performance): 55 assert(a1.capacity == a0.length); 56 } 57 } 58 59 pure @system unittest 60 { 61 // To avoid bad performance, we check that an Array constructed from an empty range 62 // does not initialize its RefCountedStore object, even after a call to "reserve(0)". 63 64 { 65 Array!float a1; 66 assert(! a1._data.refCountedStore.isInitialized); 67 a1.reserve(0); 68 assert(! a1._data.refCountedStore.isInitialized); 69 } 70 71 { 72 float[] a0 = []; 73 Array!float a1 = a0; 74 // [2021-09-26] TODO: Investigate RefCounted. 75 //assert(! a1._data.refCountedStore.isInitialized); 76 a1.reserve(0); 77 // [2021-09-26] TODO: Investigate RefCounted. 78 //assert(! a1._data.refCountedStore.isInitialized); 79 } 80 } 81 82 /// 83 pure @system unittest 84 { 85 auto arr = Array!int(0, 2, 3); 86 assert(arr[0] == 0); 87 assert(arr.front == 0); 88 assert(arr.back == 3); 89 90 // reserve space 91 arr.reserve(1000); 92 assert(arr.length == 3); 93 assert(arr.capacity >= 1000); 94 95 // insertion 96 arr.insertBefore(arr[1..$], 1); 97 assert(arr.front == 0); 98 assert(arr.length == 4); 99 100 arr.insertBack(4); 101 assert(arr.back == 4); 102 assert(arr.length == 5); 103 104 // set elements 105 arr[1] *= 42; 106 assert(arr[1] == 42); 107 } 108 109 /// 110 pure @system unittest 111 { 112 import std.algorithm.comparison : equal; 113 auto arr = Array!int(1, 2, 3); 114 115 // concat 116 auto b = Array!int(11, 12, 13); 117 arr ~= b; 118 assert(arr.length == 6); 119 120 // slicing 121 assert(arr[1 .. 3].equal([2, 3])); 122 123 // remove 124 arr.linearRemove(arr[1 .. 3]); 125 assert(arr[0 .. 2].equal([1, 11])); 126 } 127 128 /// `Array!bool` packs together values efficiently by allocating one bit per element 129 pure @system unittest 130 { 131 auto arr = Array!bool([true, true, false, true, false]); 132 assert(arr.length == 5); 133 } 134 135 private struct RangeT(A) 136 { 137 /* Workaround for https://issues.dlang.org/show_bug.cgi?id=13629 138 See also: http://forum.dlang.org/post/vbmwhzvawhnkoxrhbnyb@forum.dlang.org 139 */ 140 private A[1] _outer_; 141 private @property ref inout(A) _outer() inout { return _outer_[0]; } 142 143 private size_t _a, _b; 144 145 /* E is different from T when A is more restrictively qualified than T: 146 immutable(Array!int) => T == int, E = immutable(int) */ 147 alias E = typeof(_outer_[0]._data._payload[0]); 148 149 private this(ref A data, size_t a, size_t b) 150 { 151 _outer_ = data; 152 _a = a; 153 _b = b; 154 } 155 156 @property RangeT save() 157 { 158 return this; 159 } 160 161 @property bool empty() @safe pure nothrow const 162 { 163 return _a >= _b; 164 } 165 166 @property size_t length() @safe pure nothrow const 167 { 168 return _b - _a; 169 } 170 alias opDollar = length; 171 172 @property ref inout(E) front() inout 173 { 174 assert(!empty, "Attempting to access the front of an empty Array"); 175 return _outer[_a]; 176 } 177 @property ref inout(E) back() inout 178 { 179 assert(!empty, "Attempting to access the back of an empty Array"); 180 return _outer[_b - 1]; 181 } 182 183 void popFront() @safe @nogc pure nothrow 184 { 185 assert(!empty, "Attempting to popFront an empty Array"); 186 ++_a; 187 } 188 189 void popBack() @safe @nogc pure nothrow 190 { 191 assert(!empty, "Attempting to popBack an empty Array"); 192 --_b; 193 } 194 195 static if (isMutable!A) 196 { 197 import std.algorithm.mutation : move; 198 199 E moveFront() 200 { 201 assert(!empty, "Attempting to moveFront an empty Array"); 202 assert(_a < _outer.length, 203 "Attempting to moveFront using an out of bounds low index on an Array"); 204 return move(_outer._data._payload[_a]); 205 } 206 207 E moveBack() 208 { 209 assert(!empty, "Attempting to moveBack an empty Array"); 210 assert(_b - 1 < _outer.length, 211 "Attempting to moveBack using an out of bounds high index on an Array"); 212 return move(_outer._data._payload[_b - 1]); 213 } 214 215 E moveAt(size_t i) 216 { 217 assert(_a + i < _b, 218 "Attempting to moveAt using an out of bounds index on an Array"); 219 assert(_a + i < _outer.length, 220 "Cannot move past the end of the array"); 221 return move(_outer._data._payload[_a + i]); 222 } 223 } 224 225 ref inout(E) opIndex(size_t i) inout 226 { 227 assert(_a + i < _b, 228 "Attempting to fetch using an out of bounds index on an Array"); 229 return _outer[_a + i]; 230 } 231 232 RangeT opSlice() 233 { 234 return typeof(return)(_outer, _a, _b); 235 } 236 237 RangeT opSlice(size_t i, size_t j) 238 { 239 assert(i <= j && _a + j <= _b, 240 "Attempting to slice using an out of bounds indices on an Array"); 241 return typeof(return)(_outer, _a + i, _a + j); 242 } 243 244 RangeT!(const(A)) opSlice() const 245 { 246 return typeof(return)(_outer, _a, _b); 247 } 248 249 RangeT!(const(A)) opSlice(size_t i, size_t j) const 250 { 251 assert(i <= j && _a + j <= _b, 252 "Attempting to slice using an out of bounds indices on an Array"); 253 return typeof(return)(_outer, _a + i, _a + j); 254 } 255 256 static if (isMutable!A) 257 { 258 void opSliceAssign(E value) 259 { 260 assert(_b <= _outer.length, 261 "Attempting to assign using an out of bounds indices on an Array"); 262 _outer[_a .. _b] = value; 263 } 264 265 void opSliceAssign(E value, size_t i, size_t j) 266 { 267 assert(_a + j <= _b, 268 "Attempting to slice assign using an out of bounds indices on an Array"); 269 _outer[_a + i .. _a + j] = value; 270 } 271 272 void opSliceUnary(string op)() 273 if (op == "++" || op == "--") 274 { 275 assert(_b <= _outer.length, 276 "Attempting to slice using an out of bounds indices on an Array"); 277 mixin(op~"_outer[_a .. _b];"); 278 } 279 280 void opSliceUnary(string op)(size_t i, size_t j) 281 if (op == "++" || op == "--") 282 { 283 assert(_a + j <= _b, 284 "Attempting to slice using an out of bounds indices on an Array"); 285 mixin(op~"_outer[_a + i .. _a + j];"); 286 } 287 288 void opSliceOpAssign(string op)(E value) 289 { 290 assert(_b <= _outer.length, 291 "Attempting to slice using an out of bounds indices on an Array"); 292 mixin("_outer[_a .. _b] "~op~"= value;"); 293 } 294 295 void opSliceOpAssign(string op)(E value, size_t i, size_t j) 296 { 297 assert(_a + j <= _b, 298 "Attempting to slice using an out of bounds indices on an Array"); 299 mixin("_outer[_a + i .. _a + j] "~op~"= value;"); 300 } 301 } 302 } 303 304 @system unittest 305 { 306 enum : bool { display = false } 307 static if (display) 308 { 309 import std.stdio; 310 enum { nDigitsForPointer = 2 * size_t.sizeof, nDigitsForNObjects = 4 } 311 } 312 313 static struct S 314 { 315 static size_t s_nConstructed; 316 static size_t s_nDestroyed; 317 static void throwIfTooMany() 318 { 319 if (s_nConstructed >= 7) throw new Exception ("Ka-boom !"); 320 } 321 322 uint _i; 323 324 ~this() 325 { 326 static if (display) writefln("@%*Xh: Destroying.", nDigitsForPointer, &this); 327 ++s_nDestroyed; 328 } 329 330 this(uint i) 331 { 332 static if (display) writefln("@%*Xh: Constructing.", nDigitsForPointer, &this); 333 _i = i; 334 ++s_nConstructed; 335 throwIfTooMany(); 336 } 337 338 this(this) 339 { 340 static if (display) writefln("@%*Xh: Copying.", nDigitsForPointer, &this); 341 ++s_nConstructed; 342 throwIfTooMany(); 343 } 344 } 345 346 try 347 { 348 auto a = Array!S (S(0), S(1), S(2), S(3)); 349 static if (display) writefln("@%*Xh: This is where the array elements are.", nDigitsForPointer, &a [0]); 350 } 351 catch (Exception e) 352 { 353 static if (display) writefln("Exception caught !"); 354 } 355 356 static if (display) 357 { 358 writefln("s_nConstructed %*Xh.", nDigitsForNObjects, S.s_nConstructed); 359 writefln("s_nDestroyed %*Xh.", nDigitsForNObjects, S.s_nDestroyed); 360 writefln("s_nConstructed should be equal to s_nDestroyed."); 361 writefln(""); 362 } 363 364 assert(S.s_nDestroyed == S.s_nConstructed); 365 } 366 367 368 /** 369 * _Array type with deterministic control of memory. The memory allocated 370 * for the array is reclaimed as soon as possible; there is no reliance 371 * on the garbage collector. `Array` uses `malloc`, `realloc` and `free` 372 * for managing its own memory. 373 * 374 * This means that pointers to elements of an `Array` will become 375 * dangling as soon as the element is removed from the `Array`. On the other hand 376 * the memory allocated by an `Array` will be scanned by the GC and 377 * GC managed objects referenced from an `Array` will be kept alive. 378 * 379 * Note: 380 * 381 * When using `Array` with range-based functions like those in `std.algorithm`, 382 * `Array` must be sliced to get a range (for example, use `array[].map!` 383 * instead of `array.map!`). The container itself is not a range. 384 */ 385 struct Array(T) 386 if (!is(immutable T == immutable bool)) 387 { 388 import core.memory : free = pureFree; 389 import std.internal.memory : enforceMalloc, enforceRealloc; 390 import core.stdc.string : memcpy, memmove, memset; 391 392 import core.memory : GC; 393 394 import std.exception : enforce; 395 import std.typecons : RefCounted, RefCountedAutoInitialize; 396 397 // This structure is not copyable. 398 private struct Payload 399 { 400 size_t _capacity; 401 T[] _payload; 402 403 this(T[] p) { _capacity = p.length; _payload = p; } 404 405 // Destructor releases array memory 406 ~this() 407 { 408 // Warning: destroy would destroy also class instances. 409 // The hasElaborateDestructor protects us here. 410 static if (hasElaborateDestructor!T) 411 foreach (ref e; _payload) 412 .destroy(e); 413 414 static if (hasIndirections!T) 415 GC.removeRange(cast(void*) _payload.ptr); 416 417 free(cast(void*) _payload.ptr); 418 } 419 420 this(this) @disable; 421 422 void opAssign(Payload rhs) @disable; 423 424 @property size_t length() const 425 { 426 return _payload.length; 427 } 428 429 @property void length(size_t newLength) 430 { 431 if (length >= newLength) 432 { 433 // shorten 434 static if (hasElaborateDestructor!T) 435 foreach (ref e; _payload.ptr[newLength .. _payload.length]) 436 .destroy(e); 437 438 _payload = _payload.ptr[0 .. newLength]; 439 return; 440 } 441 442 static if (__traits(compiles, { static T _; })) 443 { 444 import std.algorithm.mutation : initializeAll; 445 446 immutable startEmplace = length; 447 reserve(newLength); 448 initializeAll(_payload.ptr[startEmplace .. newLength]); 449 _payload = _payload.ptr[0 .. newLength]; 450 } 451 else 452 { 453 assert(0, "Cannot add elements to array because `" ~ 454 fullyQualifiedName!T ~ ".this()` is annotated with " ~ 455 "`@disable`."); 456 } 457 } 458 459 @property size_t capacity() const 460 { 461 return _capacity; 462 } 463 464 void reserve(size_t elements) 465 { 466 if (elements <= capacity) return; 467 static if (T.sizeof == 1) 468 { 469 const sz = elements; 470 } 471 else 472 { 473 import core.checkedint : mulu; 474 bool overflow; 475 const sz = mulu(elements, T.sizeof, overflow); 476 if (overflow) 477 assert(false, "Overflow"); 478 } 479 static if (hasIndirections!T) 480 { 481 /* Because of the transactional nature of this 482 * relative to the garbage collector, ensure no 483 * threading bugs by using malloc/copy/free rather 484 * than realloc. 485 */ 486 immutable oldLength = length; 487 488 auto newPayloadPtr = cast(T*) enforceMalloc(sz); 489 auto newPayload = newPayloadPtr[0 .. oldLength]; 490 491 // copy old data over to new array 492 memcpy(cast(void*) newPayload.ptr, cast(void*) _payload.ptr, T.sizeof * oldLength); 493 // Zero out unused capacity to prevent gc from seeing false pointers 494 memset( cast(void*) (newPayload.ptr + oldLength), 495 0, 496 (elements - oldLength) * T.sizeof); 497 GC.addRange(cast(void*) newPayload.ptr, sz); 498 GC.removeRange(cast(void*) _payload.ptr); 499 free(cast(void*) _payload.ptr); 500 _payload = newPayload; 501 } 502 else 503 { 504 // These can't have pointers, so no need to zero unused region 505 auto newPayloadPtr = cast(T*) enforceRealloc(_payload.ptr, sz); 506 auto newPayload = newPayloadPtr[0 .. length]; 507 _payload = newPayload; 508 } 509 _capacity = elements; 510 } 511 512 // Insert one item 513 size_t insertBack(Elem)(Elem elem) 514 if (isImplicitlyConvertible!(Elem, T)) 515 { 516 import core.lifetime : emplace; 517 assert(_capacity >= length); 518 if (_capacity == length) 519 { 520 import core.checkedint : addu; 521 522 bool overflow; 523 immutable size_t newCapacity = addu(capacity, capacity / 2 + 1, overflow); 524 if (overflow) 525 assert(false, "Overflow"); 526 527 reserve(newCapacity); 528 } 529 assert(capacity > length && _payload.ptr, 530 "Failed to reserve memory"); 531 emplace(_payload.ptr + _payload.length, elem); 532 _payload = _payload.ptr[0 .. _payload.length + 1]; 533 return 1; 534 } 535 536 // Insert a range of items 537 size_t insertBack(Range)(Range r) 538 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T)) 539 { 540 immutable size_t oldLength = length; 541 542 static if (hasLength!Range) 543 { 544 immutable size_t rLength = r.length; 545 reserve(oldLength + rLength); 546 } 547 548 size_t result; 549 foreach (item; r) 550 { 551 insertBack(item); 552 ++result; 553 } 554 555 static if (hasLength!Range) 556 assert(result == rLength, "insertBack: range might have changed length"); 557 558 assert(length == oldLength + result, 559 "Failed to insertBack range"); 560 561 return result; 562 } 563 } 564 private alias Data = RefCounted!(Payload, RefCountedAutoInitialize.no); 565 private Data _data; 566 567 /** 568 * Constructor taking a number of items. 569 */ 570 this(U)(U[] values...) 571 if (isImplicitlyConvertible!(U, T)) 572 { 573 // [2021-07-17] Checking to see whether *always* calling ensureInitialized works-around-and/or-is-related-to https://issues.dlang.org/show_bug.cgihttps://issues.dlang.org/show_bug.cgi... 574 //if (values.length) 575 { 576 _data.refCountedStore.ensureInitialized(); 577 _data.reserve(values.length); 578 foreach (ref value; values) 579 { 580 // We do not simply write "_data.insertBack(value);" 581 // because that might perform, on each iteration, a now-redundant check of length vs capacity. 582 // Thanks to @dkorpel (https://github.com/dlang/phobos/pull/8162#discussion_r667479090). 583 584 import core.lifetime : emplace; 585 emplace(_data._payload.ptr + _data._payload.length, value); 586 587 // We increment the length after each iteration (as opposed to adjusting it just once, after the loop) 588 // in order to improve error-safety (in case one of the calls to emplace throws). 589 _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1]; 590 } 591 } 592 593 assert(length == values.length); // We check that all values have been inserted. 594 assert(capacity == values.length); // We check that reserve has been called before the loop. 595 } 596 597 /// ditto 598 // needed when T is an array and only one argument is passed 599 this(T single) { __ctor!T(single); } 600 601 /** 602 * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 603 */ 604 this(Range)(Range r) 605 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[])) 606 { 607 insertBack(r); 608 } 609 610 /** 611 * Comparison for equality. 612 */ 613 bool opEquals(const Array rhs) const 614 { 615 return opEquals(rhs); 616 } 617 618 // fix https://issues.dlang.org/show_bug.cgi?23140 619 private alias Unshared(T) = T; 620 private alias Unshared(T: shared U, U) = U; 621 622 /// ditto 623 bool opEquals(ref const Array rhs) const 624 { 625 if (empty) return rhs.empty; 626 if (rhs.empty) return false; 627 628 return cast(Unshared!(T)[]) _data._payload == cast(Unshared!(T)[]) rhs._data._payload; 629 } 630 631 /** 632 * Defines the array's primary range, which is a random-access range. 633 * 634 * `ConstRange` is a variant with `const` elements. 635 * `ImmutableRange` is a variant with `immutable` elements. 636 */ 637 alias Range = RangeT!Array; 638 639 /// ditto 640 alias ConstRange = RangeT!(const Array); 641 642 /// ditto 643 alias ImmutableRange = RangeT!(immutable Array); 644 645 /** 646 * Duplicates the array. The elements themselves are not transitively 647 * duplicated. 648 * 649 * Complexity: $(BIGOH length). 650 */ 651 @property Array dup() 652 { 653 if (!_data.refCountedStore.isInitialized) return this; 654 return Array(_data._payload); 655 } 656 657 /** 658 * Returns: `true` if and only if the array has no elements. 659 * 660 * Complexity: $(BIGOH 1) 661 */ 662 @property bool empty() const 663 { 664 return !_data.refCountedStore.isInitialized || _data._payload.empty; 665 } 666 667 /** 668 * Returns: The number of elements in the array. 669 * 670 * Complexity: $(BIGOH 1). 671 */ 672 @property size_t length() const 673 { 674 return _data.refCountedStore.isInitialized ? _data._payload.length : 0; 675 } 676 677 /// ditto 678 size_t opDollar() const 679 { 680 return length; 681 } 682 683 /** 684 * Returns: The maximum number of elements the array can store without 685 * reallocating memory and invalidating iterators upon insertion. 686 * 687 * Complexity: $(BIGOH 1) 688 */ 689 @property size_t capacity() 690 { 691 return _data.refCountedStore.isInitialized ? _data._capacity : 0; 692 } 693 694 /** 695 * Returns: the internal representation of the array. 696 * 697 * Complexity: $(BIGOH 1). 698 */ 699 700 inout(T)[] data() inout @system 701 { 702 return _data.refCountedStore.isInitialized ? _data._payload : []; 703 } 704 705 /** 706 * Ensures sufficient capacity to accommodate `e` _elements. 707 * If `e < capacity`, this method does nothing. 708 * 709 * Postcondition: `capacity >= e` 710 * 711 * Note: If the capacity is increased, one should assume that all 712 * iterators to the elements are invalidated. 713 * 714 * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1). 715 */ 716 void reserve(size_t elements) 717 { 718 if (elements > capacity) 719 { 720 _data.refCountedStore.ensureInitialized(); 721 _data.reserve(elements); 722 assert(capacity == elements); // Might need changing to ">=" if implementation of Payload.reserve is changed. 723 } 724 } 725 726 /** 727 * Returns: A range that iterates over elements of the array in 728 * forward order. 729 * 730 * Complexity: $(BIGOH 1) 731 */ 732 Range opSlice() 733 { 734 return typeof(return)(this, 0, length); 735 } 736 737 ConstRange opSlice() const 738 { 739 return typeof(return)(this, 0, length); 740 } 741 742 ImmutableRange opSlice() immutable 743 { 744 return typeof(return)(this, 0, length); 745 } 746 747 /** 748 * Returns: A range that iterates over elements of the array from 749 * index `i` up to (excluding) index `j`. 750 * 751 * Precondition: `i <= j && j <= length` 752 * 753 * Complexity: $(BIGOH 1) 754 */ 755 Range opSlice(size_t i, size_t j) 756 { 757 assert(i <= j && j <= length, "Invalid slice bounds"); 758 return typeof(return)(this, i, j); 759 } 760 761 ConstRange opSlice(size_t i, size_t j) const 762 { 763 assert(i <= j && j <= length, "Invalid slice bounds"); 764 return typeof(return)(this, i, j); 765 } 766 767 ImmutableRange opSlice(size_t i, size_t j) immutable 768 { 769 assert(i <= j && j <= length, "Invalid slice bounds"); 770 return typeof(return)(this, i, j); 771 } 772 773 /** 774 * Returns: The first element of the array. 775 * 776 * Precondition: `empty == false` 777 * 778 * Complexity: $(BIGOH 1) 779 */ 780 @property ref inout(T) front() inout 781 { 782 assert(_data.refCountedStore.isInitialized, 783 "Cannot get front of empty range"); 784 return _data._payload[0]; 785 } 786 787 /** 788 * Returns: The last element of the array. 789 * 790 * Precondition: `empty == false` 791 * 792 * Complexity: $(BIGOH 1) 793 */ 794 @property ref inout(T) back() inout 795 { 796 assert(_data.refCountedStore.isInitialized, 797 "Cannot get back of empty range"); 798 return _data._payload[$ - 1]; 799 } 800 801 /** 802 * Returns: The element or a reference to the element at the specified index. 803 * 804 * Precondition: `i < length` 805 * 806 * Complexity: $(BIGOH 1) 807 */ 808 ref inout(T) opIndex(size_t i) inout 809 { 810 assert(_data.refCountedStore.isInitialized, 811 "Cannot index empty range"); 812 return _data._payload[i]; 813 } 814 815 /** 816 * Slicing operators executing the specified operation on the entire slice. 817 * 818 * Precondition: `i < j && j < length` 819 * 820 * Complexity: $(BIGOH slice.length) 821 */ 822 void opSliceAssign(T value) 823 { 824 if (!_data.refCountedStore.isInitialized) return; 825 _data._payload[] = value; 826 } 827 828 /// ditto 829 void opSliceAssign(T value, size_t i, size_t j) 830 { 831 auto slice = _data.refCountedStore.isInitialized ? 832 _data._payload : 833 T[].init; 834 slice[i .. j] = value; 835 } 836 837 /// ditto 838 void opSliceUnary(string op)() 839 if (op == "++" || op == "--") 840 { 841 if (!_data.refCountedStore.isInitialized) return; 842 mixin(op~"_data._payload[];"); 843 } 844 845 /// ditto 846 void opSliceUnary(string op)(size_t i, size_t j) 847 if (op == "++" || op == "--") 848 { 849 auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init; 850 mixin(op~"slice[i .. j];"); 851 } 852 853 /// ditto 854 void opSliceOpAssign(string op)(T value) 855 { 856 if (!_data.refCountedStore.isInitialized) return; 857 mixin("_data._payload[] "~op~"= value;"); 858 } 859 860 /// ditto 861 void opSliceOpAssign(string op)(T value, size_t i, size_t j) 862 { 863 auto slice = _data.refCountedStore.isInitialized ? _data._payload : T[].init; 864 mixin("slice[i .. j] "~op~"= value;"); 865 } 866 867 private enum hasSliceWithLength(T) = is(typeof({ T t = T.init; t[].length; })); 868 869 /** 870 * Returns: A new array which is a concatenation of `this` and its argument. 871 * 872 * Complexity: 873 * $(BIGOH length + m), where `m` is the number of elements in `stuff`. 874 */ 875 Array opBinary(string op, Stuff)(Stuff stuff) 876 if (op == "~") 877 { 878 Array result; 879 880 static if (hasLength!Stuff || isNarrowString!Stuff) 881 result.reserve(length + stuff.length); 882 else static if (hasSliceWithLength!Stuff) 883 result.reserve(length + stuff[].length); 884 else static if (isImplicitlyConvertible!(Stuff, T)) 885 result.reserve(length + 1); 886 887 result.insertBack(this[]); 888 result ~= stuff; 889 return result; 890 } 891 892 /** 893 * Forwards to `insertBack`. 894 */ 895 void opOpAssign(string op, Stuff)(auto ref Stuff stuff) 896 if (op == "~") 897 { 898 static if (is(typeof(stuff[])) && isImplicitlyConvertible!(typeof(stuff[0]), T)) 899 { 900 insertBack(stuff[]); 901 } 902 else 903 { 904 insertBack(stuff); 905 } 906 } 907 908 /** 909 * Removes all the elements from the array and releases allocated memory. 910 * 911 * Postcondition: `empty == true && capacity == 0` 912 * 913 * Complexity: $(BIGOH length) 914 */ 915 void clear() 916 { 917 _data = Data.init; 918 } 919 920 /** 921 * Sets the number of elements in the array to `newLength`. If `newLength` 922 * is greater than `length`, the new elements are added to the end of the 923 * array and initialized with `T.init`. If `T` is a `struct` whose default 924 * constructor is annotated with `@disable`, `newLength` must be lower than 925 * or equal to `length`. 926 * 927 * Complexity: 928 * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`. 929 * If `capacity < newLength` the worst case is $(BIGOH newLength). 930 * 931 * Precondition: `__traits(compiles, { static T _; }) || newLength <= length` 932 * 933 * Postcondition: `length == newLength` 934 */ 935 @property void length(size_t newLength) 936 { 937 _data.refCountedStore.ensureInitialized(); 938 _data.length = newLength; 939 } 940 941 /** 942 * Removes the last element from the array and returns it. 943 * Both stable and non-stable versions behave the same and guarantee 944 * that ranges iterating over the array are never invalidated. 945 * 946 * Precondition: `empty == false` 947 * 948 * Returns: The element removed. 949 * 950 * Complexity: $(BIGOH 1). 951 * 952 * Throws: `Exception` if the array is empty. 953 */ 954 T removeAny() 955 { 956 auto result = back; 957 removeBack(); 958 return result; 959 } 960 961 /// ditto 962 alias stableRemoveAny = removeAny; 963 964 /** 965 * Inserts the specified elements at the back of the array. `stuff` can be 966 * a value convertible to `T` or a range of objects convertible to `T`. 967 * 968 * Returns: The number of elements inserted. 969 * 970 * Complexity: 971 * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m), 972 * where `m` is the number of elements in `stuff`. 973 */ 974 size_t insertBack(Stuff)(Stuff stuff) 975 if (isImplicitlyConvertible!(Stuff, T) || 976 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 977 { 978 _data.refCountedStore.ensureInitialized(); 979 return _data.insertBack(stuff); 980 } 981 982 /// ditto 983 alias insert = insertBack; 984 985 /** 986 * Removes the value from the back of the array. Both stable and non-stable 987 * versions behave the same and guarantee that ranges iterating over the 988 * array are never invalidated. 989 * 990 * Precondition: `empty == false` 991 * 992 * Complexity: $(BIGOH 1). 993 * 994 * Throws: `Exception` if the array is empty. 995 */ 996 void removeBack() 997 { 998 assert(!empty); 999 static if (hasElaborateDestructor!T) 1000 .destroy(_data._payload[$ - 1]); 1001 1002 _data._payload = _data._payload[0 .. $ - 1]; 1003 } 1004 1005 /// ditto 1006 alias stableRemoveBack = removeBack; 1007 1008 /** 1009 * Removes `howMany` values from the back of the array. 1010 * Unlike the unparameterized versions above, these functions 1011 * do not throw if they could not remove `howMany` elements. Instead, 1012 * if `howMany > n`, all elements are removed. The returned value is 1013 * the effective number of elements removed. Both stable and non-stable 1014 * versions behave the same and guarantee that ranges iterating over 1015 * the array are never invalidated. 1016 * 1017 * Returns: The number of elements removed. 1018 * 1019 * Complexity: $(BIGOH howMany). 1020 */ 1021 size_t removeBack(size_t howMany) 1022 { 1023 if (howMany > length) howMany = length; 1024 static if (hasElaborateDestructor!T) 1025 foreach (ref e; _data._payload[$ - howMany .. $]) 1026 .destroy(e); 1027 1028 _data._payload = _data._payload[0 .. $ - howMany]; 1029 return howMany; 1030 } 1031 1032 /// ditto 1033 alias stableRemoveBack = removeBack; 1034 1035 /** 1036 * Inserts `stuff` before, after, or instead range `r`, which must 1037 * be a valid range previously extracted from this array. `stuff` 1038 * can be a value convertible to `T` or a range of objects convertible 1039 * to `T`. Both stable and non-stable version behave the same and 1040 * guarantee that ranges iterating over the array are never invalidated. 1041 * 1042 * Returns: The number of values inserted. 1043 * 1044 * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`. 1045 * 1046 * Throws: `Exception` if `r` is not a range extracted from this array. 1047 */ 1048 size_t insertBefore(Stuff)(Range r, Stuff stuff) 1049 if (isImplicitlyConvertible!(Stuff, T)) 1050 { 1051 import core.lifetime : emplace; 1052 enforce(r._outer._data is _data && r._a <= length); 1053 reserve(length + 1); 1054 assert(_data.refCountedStore.isInitialized, 1055 "Failed to allocate capacity to insertBefore"); 1056 // Move elements over by one slot 1057 memmove(_data._payload.ptr + r._a + 1, 1058 _data._payload.ptr + r._a, 1059 T.sizeof * (length - r._a)); 1060 emplace(_data._payload.ptr + r._a, stuff); 1061 _data._payload = _data._payload.ptr[0 .. _data._payload.length + 1]; 1062 return 1; 1063 } 1064 1065 /// ditto 1066 size_t insertBefore(Stuff)(Range r, Stuff stuff) 1067 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 1068 { 1069 import core.lifetime : emplace; 1070 enforce(r._outer._data is _data && r._a <= length); 1071 static if (isForwardRange!Stuff) 1072 { 1073 // Can find the length in advance 1074 auto extra = walkLength(stuff); 1075 if (!extra) return 0; 1076 reserve(length + extra); 1077 assert(_data.refCountedStore.isInitialized, 1078 "Failed to allocate capacity to insertBefore"); 1079 // Move elements over by extra slots 1080 memmove(_data._payload.ptr + r._a + extra, 1081 _data._payload.ptr + r._a, 1082 T.sizeof * (length - r._a)); 1083 foreach (p; _data._payload.ptr + r._a .. 1084 _data._payload.ptr + r._a + extra) 1085 { 1086 emplace(p, stuff.front); 1087 stuff.popFront(); 1088 } 1089 _data._payload = 1090 _data._payload.ptr[0 .. _data._payload.length + extra]; 1091 return extra; 1092 } 1093 else 1094 { 1095 import std.algorithm.mutation : bringToFront; 1096 enforce(_data); 1097 immutable offset = r._a; 1098 enforce(offset <= length); 1099 auto result = insertBack(stuff); 1100 bringToFront(this[offset .. length - result], 1101 this[length - result .. length]); 1102 return result; 1103 } 1104 } 1105 1106 /// ditto 1107 alias stableInsertBefore = insertBefore; 1108 1109 /// ditto 1110 size_t insertAfter(Stuff)(Range r, Stuff stuff) 1111 if (isImplicitlyConvertible!(Stuff, T) || 1112 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 1113 { 1114 import std.algorithm.mutation : bringToFront; 1115 enforce(r._outer._data is _data); 1116 // TODO: optimize 1117 immutable offset = r._b; 1118 enforce(offset <= length); 1119 auto result = insertBack(stuff); 1120 bringToFront(this[offset .. length - result], 1121 this[length - result .. length]); 1122 return result; 1123 } 1124 1125 /// ditto 1126 size_t replace(Stuff)(Range r, Stuff stuff) 1127 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 1128 { 1129 enforce(r._outer._data is _data); 1130 size_t result; 1131 for (; !stuff.empty; stuff.popFront()) 1132 { 1133 if (r.empty) 1134 { 1135 // insert the rest 1136 return result + insertBefore(r, stuff); 1137 } 1138 r.front = stuff.front; 1139 r.popFront(); 1140 ++result; 1141 } 1142 // Remove remaining stuff in r 1143 linearRemove(r); 1144 return result; 1145 } 1146 1147 /// ditto 1148 size_t replace(Stuff)(Range r, Stuff stuff) 1149 if (isImplicitlyConvertible!(Stuff, T)) 1150 { 1151 enforce(r._outer._data is _data); 1152 if (r.empty) 1153 { 1154 insertBefore(r, stuff); 1155 } 1156 else 1157 { 1158 r.front = stuff; 1159 r.popFront(); 1160 linearRemove(r); 1161 } 1162 return 1; 1163 } 1164 1165 /** 1166 * Removes all elements belonging to `r`, which must be a range 1167 * obtained originally from this array. 1168 * 1169 * Returns: A range spanning the remaining elements in the array that 1170 * initially were right after `r`. 1171 * 1172 * Complexity: $(BIGOH length) 1173 * 1174 * Throws: `Exception` if `r` is not a valid range extracted from this array. 1175 */ 1176 Range linearRemove(Range r) 1177 { 1178 import std.algorithm.mutation : copy; 1179 1180 enforce(r._outer._data is _data); 1181 enforce(_data.refCountedStore.isInitialized); 1182 enforce(r._a <= r._b && r._b <= length); 1183 immutable offset1 = r._a; 1184 immutable offset2 = r._b; 1185 immutable tailLength = length - offset2; 1186 // Use copy here, not a[] = b[] because the ranges may overlap 1187 copy(this[offset2 .. length], this[offset1 .. offset1 + tailLength]); 1188 length = offset1 + tailLength; 1189 return this[length - tailLength .. length]; 1190 } 1191 } 1192 1193 @system unittest 1194 { 1195 Array!int a; 1196 assert(a.empty); 1197 } 1198 1199 @system unittest 1200 { 1201 Array!int a; 1202 a.length = 10; 1203 assert(a.length == 10); 1204 assert(a.capacity >= a.length); 1205 } 1206 1207 @system unittest 1208 { 1209 struct Dumb { int x = 5; } 1210 Array!Dumb a; 1211 a.length = 10; 1212 assert(a.length == 10); 1213 assert(a.capacity >= a.length); 1214 immutable cap = a.capacity; 1215 foreach (ref e; a) 1216 e.x = 10; 1217 a.length = 5; 1218 assert(a.length == 5); 1219 // do not realloc if length decreases 1220 assert(a.capacity == cap); 1221 foreach (ref e; a) 1222 assert(e.x == 10); 1223 1224 a.length = 8; 1225 assert(a.length == 8); 1226 // do not realloc if capacity sufficient 1227 assert(a.capacity == cap); 1228 assert(Dumb.init.x == 5); 1229 foreach (i; 0 .. 5) 1230 assert(a[i].x == 10); 1231 foreach (i; 5 .. a.length) 1232 assert(a[i].x == Dumb.init.x); 1233 1234 // realloc required, check if values properly copied 1235 a[] = Dumb(1); 1236 a.length = 20; 1237 assert(a.capacity >= 20); 1238 foreach (i; 0 .. 8) 1239 assert(a[i].x == 1); 1240 foreach (i; 8 .. a.length) 1241 assert(a[i].x == Dumb.init.x); 1242 1243 // check if overlapping elements properly initialized 1244 a.length = 1; 1245 a.length = 20; 1246 assert(a[0].x == 1); 1247 foreach (e; a[1 .. $]) 1248 assert(e.x == Dumb.init.x); 1249 } 1250 1251 @system unittest 1252 { 1253 Array!int a = Array!int(1, 2, 3); 1254 //a._data._refCountedDebug = true; 1255 auto b = a.dup; 1256 assert(b == Array!int(1, 2, 3)); 1257 b.front = 42; 1258 assert(b == Array!int(42, 2, 3)); 1259 assert(a == Array!int(1, 2, 3)); 1260 } 1261 1262 @system unittest 1263 { 1264 auto a = Array!int(1, 2, 3); 1265 assert(a.length == 3); 1266 } 1267 1268 @system unittest 1269 { 1270 const Array!int a = [1, 2]; 1271 1272 assert(a[0] == 1); 1273 assert(a.front == 1); 1274 assert(a.back == 2); 1275 1276 static assert(!__traits(compiles, { a[0] = 1; })); 1277 static assert(!__traits(compiles, { a.front = 1; })); 1278 static assert(!__traits(compiles, { a.back = 1; })); 1279 1280 auto r = a[]; 1281 size_t i; 1282 foreach (e; r) 1283 { 1284 assert(e == i + 1); 1285 i++; 1286 } 1287 } 1288 1289 @system unittest 1290 { 1291 import std.algorithm.comparison : equal; 1292 auto a = Array!string("test"); 1293 assert(a[].equal(["test"])); 1294 } 1295 1296 @safe unittest 1297 { 1298 // https://issues.dlang.org/show_bug.cgi?id=13621 1299 import std.container : Array, BinaryHeap; 1300 alias Heap = BinaryHeap!(Array!int); 1301 } 1302 1303 @system unittest 1304 { 1305 // https://issues.dlang.org/show_bug.cgi?id=18800 1306 static struct S { void* p; } 1307 Array!S a; 1308 a.length = 10; 1309 } 1310 1311 @system unittest 1312 { 1313 Array!int a; 1314 a.reserve(1000); 1315 assert(a.length == 0); 1316 assert(a.empty); 1317 assert(a.capacity >= 1000); 1318 auto p = a._data._payload.ptr; 1319 foreach (i; 0 .. 1000) 1320 { 1321 a.insertBack(i); 1322 } 1323 assert(p == a._data._payload.ptr); 1324 } 1325 1326 @system unittest 1327 { 1328 auto a = Array!int(1, 2, 3); 1329 a[1] *= 42; 1330 assert(a[1] == 84); 1331 } 1332 1333 @system unittest 1334 { 1335 auto a = Array!int(1, 2, 3); 1336 auto b = Array!int(11, 12, 13); 1337 auto c = a ~ b; 1338 assert(c == Array!int(1, 2, 3, 11, 12, 13)); 1339 assert(a ~ b[] == Array!int(1, 2, 3, 11, 12, 13)); 1340 assert(a ~ [4,5] == Array!int(1,2,3,4,5)); 1341 } 1342 1343 @system unittest 1344 { 1345 auto a = Array!int(1, 2, 3); 1346 auto b = Array!int(11, 12, 13); 1347 a ~= b; 1348 assert(a == Array!int(1, 2, 3, 11, 12, 13)); 1349 } 1350 1351 @system unittest 1352 { 1353 auto a = Array!int(1, 2, 3, 4); 1354 assert(a.removeAny() == 4); 1355 assert(a == Array!int(1, 2, 3)); 1356 } 1357 1358 @system unittest 1359 { 1360 auto a = Array!int(1, 2, 3, 4, 5); 1361 auto r = a[2 .. a.length]; 1362 assert(a.insertBefore(r, 42) == 1); 1363 assert(a == Array!int(1, 2, 42, 3, 4, 5)); 1364 r = a[2 .. 2]; 1365 assert(a.insertBefore(r, [8, 9]) == 2); 1366 assert(a == Array!int(1, 2, 8, 9, 42, 3, 4, 5)); 1367 } 1368 1369 @system unittest 1370 { 1371 auto a = Array!int(0, 1, 2, 3, 4, 5, 6, 7, 8); 1372 a.linearRemove(a[4 .. 6]); 1373 assert(a == Array!int(0, 1, 2, 3, 6, 7, 8)); 1374 } 1375 1376 // Give the Range object some testing. 1377 @system unittest 1378 { 1379 import std.algorithm.comparison : equal; 1380 import std.range : retro; 1381 auto a = Array!int(0, 1, 2, 3, 4, 5, 6)[]; 1382 auto b = Array!int(6, 5, 4, 3, 2, 1, 0)[]; 1383 alias A = typeof(a); 1384 1385 static assert(isRandomAccessRange!A); 1386 static assert(hasSlicing!A); 1387 static assert(hasAssignableElements!A); 1388 static assert(hasMobileElements!A); 1389 1390 assert(equal(retro(b), a)); 1391 assert(a.length == 7); 1392 assert(equal(a[1 .. 4], [1, 2, 3])); 1393 } 1394 1395 // https://issues.dlang.org/show_bug.cgi?id=5920 1396 @system unittest 1397 { 1398 struct structBug5920 1399 { 1400 int order; 1401 uint* pDestructionMask; 1402 ~this() 1403 { 1404 if (pDestructionMask) 1405 *pDestructionMask += 1 << order; 1406 } 1407 } 1408 1409 alias S = structBug5920; 1410 uint dMask; 1411 1412 auto arr = Array!S(cast(S[])[]); 1413 foreach (i; 0 .. 8) 1414 arr.insertBack(S(i, &dMask)); 1415 // don't check dMask now as S may be copied multiple times (it's ok?) 1416 { 1417 assert(arr.length == 8); 1418 dMask = 0; 1419 arr.length = 6; 1420 assert(arr.length == 6); // make sure shrinking calls the d'tor 1421 assert(dMask == 0b1100_0000); 1422 arr.removeBack(); 1423 assert(arr.length == 5); // make sure removeBack() calls the d'tor 1424 assert(dMask == 0b1110_0000); 1425 arr.removeBack(3); 1426 assert(arr.length == 2); // ditto 1427 assert(dMask == 0b1111_1100); 1428 arr.clear(); 1429 assert(arr.length == 0); // make sure clear() calls the d'tor 1430 assert(dMask == 0b1111_1111); 1431 } 1432 assert(dMask == 0b1111_1111); // make sure the d'tor is called once only. 1433 } 1434 1435 // Test for https://issues.dlang.org/show_bug.cgi?id=5792 1436 // (mainly just to check if this piece of code is compilable) 1437 @system unittest 1438 { 1439 auto a = Array!(int[])([[1,2],[3,4]]); 1440 a.reserve(4); 1441 assert(a.capacity >= 4); 1442 assert(a.length == 2); 1443 assert(a[0] == [1,2]); 1444 assert(a[1] == [3,4]); 1445 a.reserve(16); 1446 assert(a.capacity >= 16); 1447 assert(a.length == 2); 1448 assert(a[0] == [1,2]); 1449 assert(a[1] == [3,4]); 1450 } 1451 1452 // test replace!Stuff with range Stuff 1453 @system unittest 1454 { 1455 import std.algorithm.comparison : equal; 1456 auto a = Array!int([1, 42, 5]); 1457 a.replace(a[1 .. 2], [2, 3, 4]); 1458 assert(equal(a[], [1, 2, 3, 4, 5])); 1459 } 1460 1461 // test insertBefore and replace with empty Arrays 1462 @system unittest 1463 { 1464 import std.algorithm.comparison : equal; 1465 auto a = Array!int(); 1466 a.insertBefore(a[], 1); 1467 assert(equal(a[], [1])); 1468 } 1469 @system unittest 1470 { 1471 import std.algorithm.comparison : equal; 1472 auto a = Array!int(); 1473 a.insertBefore(a[], [1, 2]); 1474 assert(equal(a[], [1, 2])); 1475 } 1476 @system unittest 1477 { 1478 import std.algorithm.comparison : equal; 1479 auto a = Array!int(); 1480 a.replace(a[], [1, 2]); 1481 assert(equal(a[], [1, 2])); 1482 } 1483 @system unittest 1484 { 1485 import std.algorithm.comparison : equal; 1486 auto a = Array!int(); 1487 a.replace(a[], 1); 1488 assert(equal(a[], [1])); 1489 } 1490 // make sure that Array instances refuse ranges that don't belong to them 1491 @system unittest 1492 { 1493 import std.exception : assertThrown; 1494 1495 Array!int a = [1, 2, 3]; 1496 auto r = a.dup[]; 1497 assertThrown(a.insertBefore(r, 42)); 1498 assertThrown(a.insertBefore(r, [42])); 1499 assertThrown(a.insertAfter(r, 42)); 1500 assertThrown(a.replace(r, 42)); 1501 assertThrown(a.replace(r, [42])); 1502 assertThrown(a.linearRemove(r)); 1503 } 1504 @system unittest 1505 { 1506 auto a = Array!int([1, 1]); 1507 a[1] = 0; //Check Array.opIndexAssign 1508 assert(a[1] == 0); 1509 a[1] += 1; //Check Array.opIndexOpAssign 1510 assert(a[1] == 1); 1511 1512 //Check Array.opIndexUnary 1513 ++a[0]; 1514 //a[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed 1515 assert(a[0] == 2); 1516 assert(+a[0] == +2); 1517 assert(-a[0] == -2); 1518 assert(~a[0] == ~2); 1519 1520 auto r = a[]; 1521 r[1] = 0; //Check Array.Range.opIndexAssign 1522 assert(r[1] == 0); 1523 r[1] += 1; //Check Array.Range.opIndexOpAssign 1524 assert(r[1] == 1); 1525 1526 //Check Array.Range.opIndexUnary 1527 ++r[0]; 1528 //r[0]++ //op++ doesn't return, so this shouldn't work, even with 5044 fixed 1529 assert(r[0] == 3); 1530 assert(+r[0] == +3); 1531 assert(-r[0] == -3); 1532 assert(~r[0] == ~3); 1533 } 1534 1535 @system unittest 1536 { 1537 import std.algorithm.comparison : equal; 1538 1539 //Test "array-wide" operations 1540 auto a = Array!int([0, 1, 2]); //Array 1541 a[] += 5; 1542 assert(a[].equal([5, 6, 7])); 1543 ++a[]; 1544 assert(a[].equal([6, 7, 8])); 1545 a[1 .. 3] *= 5; 1546 assert(a[].equal([6, 35, 40])); 1547 a[0 .. 2] = 0; 1548 assert(a[].equal([0, 0, 40])); 1549 1550 //Test empty array 1551 auto a2 = Array!int.init; 1552 ++a2[]; 1553 ++a2[0 .. 0]; 1554 a2[] = 0; 1555 a2[0 .. 0] = 0; 1556 a2[] += 0; 1557 a2[0 .. 0] += 0; 1558 1559 //Test "range-wide" operations 1560 auto r = Array!int([0, 1, 2])[]; //Array.Range 1561 r[] += 5; 1562 assert(r.equal([5, 6, 7])); 1563 ++r[]; 1564 assert(r.equal([6, 7, 8])); 1565 r[1 .. 3] *= 5; 1566 assert(r.equal([6, 35, 40])); 1567 r[0 .. 2] = 0; 1568 assert(r.equal([0, 0, 40])); 1569 1570 //Test empty Range 1571 auto r2 = Array!int.init[]; 1572 ++r2[]; 1573 ++r2[0 .. 0]; 1574 r2[] = 0; 1575 r2[0 .. 0] = 0; 1576 r2[] += 0; 1577 r2[0 .. 0] += 0; 1578 } 1579 1580 // Test https://issues.dlang.org/show_bug.cgi?id=11194 1581 @system unittest 1582 { 1583 static struct S { 1584 int i = 1337; 1585 void* p; 1586 this(this) { assert(i == 1337); } 1587 ~this() { assert(i == 1337); } 1588 } 1589 Array!S arr; 1590 S s; 1591 arr ~= s; 1592 arr ~= s; 1593 } 1594 1595 // https://issues.dlang.org/show_bug.cgi?id=11459 1596 @safe unittest 1597 { 1598 static struct S 1599 { 1600 bool b; 1601 alias b this; 1602 } 1603 alias A = Array!S; 1604 alias B = Array!(shared bool); 1605 } 1606 1607 // https://issues.dlang.org/show_bug.cgi?id=11884 1608 @system unittest 1609 { 1610 import std.algorithm.iteration : filter; 1611 auto a = Array!int([1, 2, 2].filter!"true"()); 1612 } 1613 1614 // https://issues.dlang.org/show_bug.cgi?id=8282 1615 @safe unittest 1616 { 1617 auto arr = new Array!int; 1618 } 1619 1620 // https://issues.dlang.org/show_bug.cgi?id=6998 1621 @system unittest 1622 { 1623 static int i = 0; 1624 class C 1625 { 1626 int dummy = 1; 1627 this(){++i;} 1628 ~this(){--i;} 1629 } 1630 1631 assert(i == 0); 1632 auto c = new C(); 1633 assert(i == 1); 1634 1635 //scope 1636 { 1637 auto arr = Array!C(c); 1638 assert(i == 1); 1639 } 1640 //Array should not have destroyed the class instance 1641 assert(i == 1); 1642 1643 //Just to make sure the GC doesn't collect before the above test. 1644 assert(c.dummy == 1); 1645 } 1646 1647 //https://issues.dlang.org/show_bug.cgi?id=6998 (2) 1648 @system unittest 1649 { 1650 static class C {int i;} 1651 auto c = new C; 1652 c.i = 42; 1653 Array!C a; 1654 a ~= c; 1655 a.clear; 1656 assert(c.i == 42); //fails 1657 } 1658 1659 @safe unittest 1660 { 1661 static assert(is(Array!int.Range)); 1662 static assert(is(Array!int.ConstRange)); 1663 } 1664 1665 @system unittest // const/immutable Array and Ranges 1666 { 1667 static void test(A, R, E, S)() 1668 { 1669 A a; 1670 R r = a[]; 1671 assert(r.empty); 1672 assert(r.length == 0); 1673 static assert(is(typeof(r.front) == E)); 1674 static assert(is(typeof(r.back) == E)); 1675 static assert(is(typeof(r[0]) == E)); 1676 static assert(is(typeof(r[]) == S)); 1677 static assert(is(typeof(r[0 .. 0]) == S)); 1678 } 1679 1680 alias A = Array!int; 1681 1682 test!(A, A.Range, int, A.Range); 1683 test!(A, const A.Range, const int, A.ConstRange); 1684 1685 test!(const A, A.ConstRange, const int, A.ConstRange); 1686 test!(const A, const A.ConstRange, const int, A.ConstRange); 1687 1688 test!(immutable A, A.ImmutableRange, immutable int, A.ImmutableRange); 1689 test!(immutable A, const A.ImmutableRange, immutable int, A.ImmutableRange); 1690 test!(immutable A, immutable A.ImmutableRange, immutable int, 1691 A.ImmutableRange); 1692 } 1693 1694 // ensure @nogc 1695 @nogc @system unittest 1696 { 1697 Array!int ai; 1698 ai ~= 1; 1699 assert(ai.front == 1); 1700 1701 ai.reserve(10); 1702 assert(ai.capacity == 10); 1703 1704 static immutable arr = [1, 2, 3]; 1705 ai.insertBack(arr); 1706 } 1707 1708 /* 1709 * typeof may give wrong result in case of classes defining `opCall` operator 1710 * https://issues.dlang.org/show_bug.cgi?id=20589 1711 * 1712 * destructor std.container.array.Array!(MyClass).Array.~this is @system 1713 * so the unittest is @system too 1714 */ 1715 @system unittest 1716 { 1717 class MyClass 1718 { 1719 T opCall(T)(T p) 1720 { 1721 return p; 1722 } 1723 } 1724 1725 Array!MyClass arr; 1726 } 1727 1728 @system unittest 1729 { 1730 import std.algorithm.comparison : equal; 1731 auto a = Array!int([1,2,3,4,5]); 1732 assert(a.length == 5); 1733 1734 assert(a.insertAfter(a[0 .. 5], [7, 8]) == 2); 1735 assert(equal(a[], [1,2,3,4,5,7,8])); 1736 1737 assert(a.insertAfter(a[0 .. 5], 6) == 1); 1738 assert(equal(a[], [1,2,3,4,5,6,7,8])); 1739 } 1740 1741 // https://issues.dlang.org/show_bug.cgi?id=22105 1742 @system unittest 1743 { 1744 import core.exception : AssertError; 1745 import std.exception : assertThrown, assertNotThrown; 1746 1747 struct NoDefaultCtor 1748 { 1749 int i; 1750 @disable this(); 1751 this(int j) { i = j; } 1752 } 1753 1754 auto array = Array!NoDefaultCtor([NoDefaultCtor(1), NoDefaultCtor(2)]); 1755 assertNotThrown!AssertError(array.length = 1); 1756 assertThrown!AssertError(array.length = 5); 1757 } 1758 1759 // https://issues.dlang.org/show_bug.cgi?id=23140 1760 @system unittest 1761 { 1762 shared class C 1763 { 1764 } 1765 1766 Array!C ac; 1767 ac = Array!C([new C]); 1768 } 1769 //////////////////////////////////////////////////////////////////////////////// 1770 // Array!bool 1771 //////////////////////////////////////////////////////////////////////////////// 1772 1773 /** 1774 * _Array specialized for `bool`. Packs together values efficiently by 1775 * allocating one bit per element. 1776 */ 1777 struct Array(T) 1778 if (is(immutable T == immutable bool)) 1779 { 1780 import std.exception : enforce; 1781 import std.typecons : RefCounted, RefCountedAutoInitialize; 1782 1783 static immutable uint bitsPerWord = size_t.sizeof * 8; 1784 private static struct Data 1785 { 1786 Array!size_t.Payload _backend; 1787 size_t _length; 1788 } 1789 private RefCounted!(Data, RefCountedAutoInitialize.no) _store; 1790 1791 private @property ref size_t[] data() 1792 { 1793 assert(_store.refCountedStore.isInitialized, 1794 "Cannot get data of uninitialized Array"); 1795 return _store._backend._payload; 1796 } 1797 1798 /** 1799 * Defines the array's primary range. 1800 */ 1801 struct Range 1802 { 1803 private Array _outer; 1804 private size_t _a, _b; 1805 /// Range primitives 1806 @property Range save() 1807 { 1808 version (bug4437) 1809 { 1810 return this; 1811 } 1812 else 1813 { 1814 auto copy = this; 1815 return copy; 1816 } 1817 } 1818 /// Ditto 1819 @property bool empty() 1820 { 1821 return _a >= _b || _outer.length < _b; 1822 } 1823 /// Ditto 1824 @property T front() 1825 { 1826 assert(!empty, "Attempting to access the front of an empty Array"); 1827 return _outer[_a]; 1828 } 1829 /// Ditto 1830 @property void front(bool value) 1831 { 1832 assert(!empty, "Attempting to set the front of an empty Array"); 1833 _outer[_a] = value; 1834 } 1835 /// Ditto 1836 T moveFront() 1837 { 1838 assert(!empty, "Attempting to move the front of an empty Array"); 1839 return _outer.moveAt(_a); 1840 } 1841 /// Ditto 1842 void popFront() 1843 { 1844 assert(!empty, "Attempting to popFront an empty Array"); 1845 ++_a; 1846 } 1847 /// Ditto 1848 @property T back() 1849 { 1850 assert(!empty, "Attempting to access the back of an empty Array"); 1851 return _outer[_b - 1]; 1852 } 1853 /// Ditto 1854 @property void back(bool value) 1855 { 1856 assert(!empty, "Attempting to set the back of an empty Array"); 1857 _outer[_b - 1] = value; 1858 } 1859 /// Ditto 1860 T moveBack() 1861 { 1862 assert(!empty, "Attempting to move the back of an empty Array"); 1863 return _outer.moveAt(_b - 1); 1864 } 1865 /// Ditto 1866 void popBack() 1867 { 1868 assert(!empty, "Attempting to popBack an empty Array"); 1869 --_b; 1870 } 1871 /// Ditto 1872 T opIndex(size_t i) 1873 { 1874 return _outer[_a + i]; 1875 } 1876 /// Ditto 1877 void opIndexAssign(T value, size_t i) 1878 { 1879 _outer[_a + i] = value; 1880 } 1881 /// Ditto 1882 T moveAt(size_t i) 1883 { 1884 return _outer.moveAt(_a + i); 1885 } 1886 /// Ditto 1887 @property size_t length() const 1888 { 1889 assert(_a <= _b, "Invalid bounds"); 1890 return _b - _a; 1891 } 1892 alias opDollar = length; 1893 /// ditto 1894 Range opSlice(size_t low, size_t high) 1895 { 1896 // Note: indexes start at 0, which is equivalent to _a 1897 assert( 1898 low <= high && high <= (_b - _a), 1899 "Using out of bounds indexes on an Array" 1900 ); 1901 return Range(_outer, _a + low, _a + high); 1902 } 1903 } 1904 1905 /** 1906 * Constructor taking a number of items. 1907 */ 1908 this(U)(U[] values...) 1909 if (isImplicitlyConvertible!(U, T)) 1910 { 1911 reserve(values.length); 1912 foreach (i, v; values) 1913 { 1914 auto rem = i % bitsPerWord; 1915 if (rem) 1916 { 1917 // Fits within the current array 1918 if (v) 1919 { 1920 data[$ - 1] |= (cast(size_t) 1 << rem); 1921 } 1922 else 1923 { 1924 data[$ - 1] &= ~(cast(size_t) 1 << rem); 1925 } 1926 } 1927 else 1928 { 1929 // Need to add more data 1930 _store._backend.insertBack(v); 1931 } 1932 } 1933 _store._length = values.length; 1934 } 1935 1936 /** 1937 * Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 1938 */ 1939 this(Range)(Range r) 1940 if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[])) 1941 { 1942 insertBack(r); 1943 } 1944 1945 /** 1946 * Property returning `true` if and only if the array has 1947 * no elements. 1948 * 1949 * Complexity: $(BIGOH 1) 1950 */ 1951 @property bool empty() 1952 { 1953 return !length; 1954 } 1955 1956 /** 1957 * Returns: A duplicate of the array. 1958 * 1959 * Complexity: $(BIGOH length). 1960 */ 1961 @property Array dup() 1962 { 1963 Array result; 1964 result.insertBack(this[]); 1965 return result; 1966 } 1967 1968 /** 1969 * Returns the number of elements in the array. 1970 * 1971 * Complexity: $(BIGOH 1). 1972 */ 1973 @property size_t length() const 1974 { 1975 return _store.refCountedStore.isInitialized ? _store._length : 0; 1976 } 1977 alias opDollar = length; 1978 1979 /** 1980 * Returns: The maximum number of elements the array can store without 1981 * reallocating memory and invalidating iterators upon insertion. 1982 * 1983 * Complexity: $(BIGOH 1). 1984 */ 1985 @property size_t capacity() 1986 { 1987 return _store.refCountedStore.isInitialized 1988 ? cast(size_t) bitsPerWord * _store._backend.capacity 1989 : 0; 1990 } 1991 1992 /** 1993 * Ensures sufficient capacity to accommodate `e` _elements. 1994 * If `e < capacity`, this method does nothing. 1995 * 1996 * Postcondition: `capacity >= e` 1997 * 1998 * Note: If the capacity is increased, one should assume that all 1999 * iterators to the elements are invalidated. 2000 * 2001 * Complexity: at most $(BIGOH length) if `e > capacity`, otherwise $(BIGOH 1). 2002 */ 2003 void reserve(size_t e) 2004 { 2005 import std.conv : to; 2006 _store.refCountedStore.ensureInitialized(); 2007 _store._backend.reserve(to!size_t((e + bitsPerWord - 1) / bitsPerWord)); 2008 } 2009 2010 /** 2011 * Returns: A range that iterates over all elements of the array in forward order. 2012 * 2013 * Complexity: $(BIGOH 1) 2014 */ 2015 Range opSlice() 2016 { 2017 return Range(this, 0, length); 2018 } 2019 2020 2021 /** 2022 * Returns: A range that iterates the array between two specified positions. 2023 * 2024 * Complexity: $(BIGOH 1) 2025 */ 2026 Range opSlice(size_t a, size_t b) 2027 { 2028 enforce(a <= b && b <= length); 2029 return Range(this, a, b); 2030 } 2031 2032 /** 2033 * Returns: The first element of the array. 2034 * 2035 * Precondition: `empty == false` 2036 * 2037 * Complexity: $(BIGOH 1) 2038 * 2039 * Throws: `Exception` if the array is empty. 2040 */ 2041 @property bool front() 2042 { 2043 assert(!empty); 2044 return data.ptr[0] & 1; 2045 } 2046 2047 /// Ditto 2048 @property void front(bool value) 2049 { 2050 assert(!empty); 2051 if (value) data.ptr[0] |= 1; 2052 else data.ptr[0] &= ~cast(size_t) 1; 2053 } 2054 2055 /** 2056 * Returns: The last element of the array. 2057 * 2058 * Precondition: `empty == false` 2059 * 2060 * Complexity: $(BIGOH 1) 2061 * 2062 * Throws: `Exception` if the array is empty. 2063 */ 2064 @property bool back() 2065 { 2066 assert(!empty); 2067 return cast(bool)(data.back & (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord))); 2068 } 2069 2070 /// Ditto 2071 @property void back(bool value) 2072 { 2073 assert(!empty); 2074 if (value) 2075 { 2076 data.back |= (cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)); 2077 } 2078 else 2079 { 2080 data.back &= 2081 ~(cast(size_t) 1 << ((_store._length - 1) % bitsPerWord)); 2082 } 2083 } 2084 2085 /** 2086 * Indexing operators yielding or modifyng the value at the specified index. 2087 * 2088 * Precondition: `i < length` 2089 * 2090 * Complexity: $(BIGOH 1) 2091 */ 2092 bool opIndex(size_t i) 2093 { 2094 auto div = cast(size_t) (i / bitsPerWord); 2095 auto rem = i % bitsPerWord; 2096 enforce(div < data.length); 2097 return cast(bool)(data.ptr[div] & (cast(size_t) 1 << rem)); 2098 } 2099 2100 /// ditto 2101 void opIndexAssign(bool value, size_t i) 2102 { 2103 auto div = cast(size_t) (i / bitsPerWord); 2104 auto rem = i % bitsPerWord; 2105 enforce(div < data.length); 2106 if (value) data.ptr[div] |= (cast(size_t) 1 << rem); 2107 else data.ptr[div] &= ~(cast(size_t) 1 << rem); 2108 } 2109 2110 /// ditto 2111 void opIndexOpAssign(string op)(bool value, size_t i) 2112 { 2113 auto div = cast(size_t) (i / bitsPerWord); 2114 auto rem = i % bitsPerWord; 2115 enforce(div < data.length); 2116 auto oldValue = cast(bool) (data.ptr[div] & (cast(size_t) 1 << rem)); 2117 // Do the deed 2118 auto newValue = mixin("oldValue "~op~" value"); 2119 // Write back the value 2120 if (newValue != oldValue) 2121 { 2122 if (newValue) data.ptr[div] |= (cast(size_t) 1 << rem); 2123 else data.ptr[div] &= ~(cast(size_t) 1 << rem); 2124 } 2125 } 2126 2127 /// Ditto 2128 T moveAt(size_t i) 2129 { 2130 return this[i]; 2131 } 2132 2133 /** 2134 * Returns: A new array which is a concatenation of `this` and its argument. 2135 * 2136 * Complexity: 2137 * $(BIGOH length + m), where `m` is the number of elements in `stuff`. 2138 */ 2139 Array!bool opBinary(string op, Stuff)(Stuff rhs) 2140 if (op == "~") 2141 { 2142 Array!bool result; 2143 2144 static if (hasLength!Stuff) 2145 result.reserve(length + rhs.length); 2146 else static if (is(typeof(rhs[])) && hasLength!(typeof(rhs[]))) 2147 result.reserve(length + rhs[].length); 2148 else static if (isImplicitlyConvertible!(Stuff, bool)) 2149 result.reserve(length + 1); 2150 2151 result.insertBack(this[]); 2152 result ~= rhs; 2153 return result; 2154 } 2155 2156 /** 2157 * Forwards to `insertBack`. 2158 */ 2159 Array!bool opOpAssign(string op, Stuff)(Stuff stuff) 2160 if (op == "~") 2161 { 2162 static if (is(typeof(stuff[]))) insertBack(stuff[]); 2163 else insertBack(stuff); 2164 return this; 2165 } 2166 2167 /** 2168 * Removes all the elements from the array and releases allocated memory. 2169 * 2170 * Postcondition: `empty == true && capacity == 0` 2171 * 2172 * Complexity: $(BIGOH length) 2173 */ 2174 void clear() 2175 { 2176 this = Array(); 2177 } 2178 2179 /** 2180 * Sets the number of elements in the array to `newLength`. If `newLength` 2181 * is greater than `length`, the new elements are added to the end of the 2182 * array and initialized with `false`. 2183 * 2184 * Complexity: 2185 * Guaranteed $(BIGOH abs(length - newLength)) if `capacity >= newLength`. 2186 * If `capacity < newLength` the worst case is $(BIGOH newLength). 2187 * 2188 * Postcondition: `length == newLength` 2189 */ 2190 @property void length(size_t newLength) 2191 { 2192 import std.conv : to; 2193 _store.refCountedStore.ensureInitialized(); 2194 auto newDataLength = 2195 to!size_t((newLength + bitsPerWord - 1) / bitsPerWord); 2196 _store._backend.length = newDataLength; 2197 _store._length = newLength; 2198 } 2199 2200 /** 2201 * Removes the last element from the array and returns it. 2202 * Both stable and non-stable versions behave the same and guarantee 2203 * that ranges iterating over the array are never invalidated. 2204 * 2205 * Precondition: `empty == false` 2206 * 2207 * Returns: The element removed. 2208 * 2209 * Complexity: $(BIGOH 1). 2210 * 2211 * Throws: `Exception` if the array is empty. 2212 */ 2213 T removeAny() 2214 { 2215 auto result = back; 2216 removeBack(); 2217 return result; 2218 } 2219 2220 /// ditto 2221 alias stableRemoveAny = removeAny; 2222 2223 /** 2224 * Inserts the specified elements at the back of the array. `stuff` can be 2225 * a value convertible to `bool` or a range of objects convertible to `bool`. 2226 * 2227 * Returns: The number of elements inserted. 2228 * 2229 * Complexity: 2230 * $(BIGOH length + m) if reallocation takes place, otherwise $(BIGOH m), 2231 * where `m` is the number of elements in `stuff`. 2232 */ 2233 size_t insertBack(Stuff)(Stuff stuff) 2234 if (is(Stuff : bool)) 2235 { 2236 _store.refCountedStore.ensureInitialized(); 2237 auto rem = _store._length % bitsPerWord; 2238 if (rem) 2239 { 2240 // Fits within the current array 2241 if (stuff) 2242 { 2243 data[$ - 1] |= (cast(size_t) 1 << rem); 2244 } 2245 else 2246 { 2247 data[$ - 1] &= ~(cast(size_t) 1 << rem); 2248 } 2249 } 2250 else 2251 { 2252 // Need to add more data 2253 _store._backend.insertBack(stuff); 2254 } 2255 ++_store._length; 2256 return 1; 2257 } 2258 2259 /// ditto 2260 size_t insertBack(Stuff)(Stuff stuff) 2261 if (isInputRange!Stuff && is(ElementType!Stuff : bool)) 2262 { 2263 size_t result; 2264 static if (hasLength!Stuff) 2265 result = stuff.length; 2266 2267 for (; !stuff.empty; stuff.popFront()) 2268 { 2269 insertBack(stuff.front); 2270 static if (!hasLength!Stuff) ++result; 2271 } 2272 2273 return result; 2274 } 2275 2276 /// ditto 2277 alias stableInsertBack = insertBack; 2278 2279 /// ditto 2280 alias insert = insertBack; 2281 2282 /// ditto 2283 alias stableInsert = insertBack; 2284 2285 /// ditto 2286 alias linearInsert = insertBack; 2287 2288 /// ditto 2289 alias stableLinearInsert = insertBack; 2290 2291 /** 2292 * Removes the value from the back of the array. Both stable and non-stable 2293 * versions behave the same and guarantee that ranges iterating over the 2294 * array are never invalidated. 2295 * 2296 * Precondition: `empty == false` 2297 * 2298 * Complexity: $(BIGOH 1). 2299 * 2300 * Throws: `Exception` if the array is empty. 2301 */ 2302 void removeBack() 2303 { 2304 enforce(_store._length); 2305 if (_store._length % bitsPerWord) 2306 { 2307 // Cool, just decrease the length 2308 --_store._length; 2309 } 2310 else 2311 { 2312 // Reduce the allocated space 2313 --_store._length; 2314 _store._backend.length = _store._backend.length - 1; 2315 } 2316 } 2317 2318 /// ditto 2319 alias stableRemoveBack = removeBack; 2320 2321 /** 2322 * Removes `howMany` values from the back of the array. Unlike the 2323 * unparameterized versions above, these functions do not throw if 2324 * they could not remove `howMany` elements. Instead, if `howMany > n`, 2325 * all elements are removed. The returned value is the effective number 2326 * of elements removed. Both stable and non-stable versions behave the same 2327 * and guarantee that ranges iterating over the array are never invalidated. 2328 * 2329 * Returns: The number of elements removed. 2330 * 2331 * Complexity: $(BIGOH howMany). 2332 */ 2333 size_t removeBack(size_t howMany) 2334 { 2335 if (howMany >= length) 2336 { 2337 howMany = length; 2338 clear(); 2339 } 2340 else 2341 { 2342 length = length - howMany; 2343 } 2344 return howMany; 2345 } 2346 2347 /// ditto 2348 alias stableRemoveBack = removeBack; 2349 2350 /** 2351 * Inserts `stuff` before, after, or instead range `r`, which must 2352 * be a valid range previously extracted from this array. `stuff` 2353 * can be a value convertible to `bool` or a range of objects convertible 2354 * to `bool`. Both stable and non-stable version behave the same and 2355 * guarantee that ranges iterating over the array are never invalidated. 2356 * 2357 * Returns: The number of values inserted. 2358 * 2359 * Complexity: $(BIGOH length + m), where `m` is the length of `stuff`. 2360 */ 2361 size_t insertBefore(Stuff)(Range r, Stuff stuff) 2362 { 2363 import std.algorithm.mutation : bringToFront; 2364 // TODO: make this faster, it moves one bit at a time 2365 immutable inserted = stableInsertBack(stuff); 2366 immutable tailLength = length - inserted; 2367 bringToFront( 2368 this[r._a .. tailLength], 2369 this[tailLength .. length]); 2370 return inserted; 2371 } 2372 2373 /// ditto 2374 alias stableInsertBefore = insertBefore; 2375 2376 /// ditto 2377 size_t insertAfter(Stuff)(Range r, Stuff stuff) 2378 if (isImplicitlyConvertible!(Stuff, T) || 2379 isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 2380 { 2381 import std.algorithm.mutation : bringToFront; 2382 // TODO: make this faster, it moves one bit at a time 2383 immutable inserted = stableInsertBack(stuff); 2384 immutable tailLength = length - inserted; 2385 bringToFront( 2386 this[r._b .. tailLength], 2387 this[tailLength .. length]); 2388 return inserted; 2389 } 2390 2391 /// ditto 2392 alias stableInsertAfter = insertAfter; 2393 2394 /// ditto 2395 size_t replace(Stuff)(Range r, Stuff stuff) 2396 if (is(Stuff : bool)) 2397 { 2398 if (!r.empty) 2399 { 2400 // There is room 2401 r.front = stuff; 2402 r.popFront(); 2403 linearRemove(r); 2404 } 2405 else 2406 { 2407 // No room, must insert 2408 insertBefore(r, stuff); 2409 } 2410 return 1; 2411 } 2412 2413 /// ditto 2414 alias stableReplace = replace; 2415 2416 /** 2417 * Removes all elements belonging to `r`, which must be a range 2418 * obtained originally from this array. 2419 * 2420 * Returns: A range spanning the remaining elements in the array that 2421 * initially were right after `r`. 2422 * 2423 * Complexity: $(BIGOH length) 2424 */ 2425 Range linearRemove(Range r) 2426 { 2427 import std.algorithm.mutation : copy; 2428 copy(this[r._b .. length], this[r._a .. length]); 2429 length = length - r.length; 2430 return this[r._a .. length]; 2431 } 2432 } 2433 2434 @system unittest 2435 { 2436 import std.algorithm.comparison : equal; 2437 2438 auto a = Array!bool([true, true, false, false, true, false]); 2439 assert(equal(a[], [true, true, false, false, true, false])); 2440 } 2441 2442 // using Ranges 2443 @system unittest 2444 { 2445 import std.algorithm.comparison : equal; 2446 import std.range : retro; 2447 bool[] arr = [true, true, false, false, true, false]; 2448 2449 auto a = Array!bool(retro(arr)); 2450 assert(equal(a[], retro(arr))); 2451 } 2452 2453 @system unittest 2454 { 2455 Array!bool a; 2456 assert(a.empty); 2457 } 2458 2459 @system unittest 2460 { 2461 auto arr = Array!bool([false, false, false, false]); 2462 assert(arr.front == false); 2463 assert(arr.back == false); 2464 assert(arr[1] == false); 2465 auto slice = arr[]; 2466 slice = arr[0 .. $]; 2467 slice = slice[1 .. $]; 2468 slice.front = true; 2469 slice.back = true; 2470 slice[1] = true; 2471 slice = slice[0 .. $]; // https://issues.dlang.org/show_bug.cgi?id=19171 2472 assert(slice.front == true); 2473 assert(slice.back == true); 2474 assert(slice[1] == true); 2475 assert(slice.moveFront == true); 2476 assert(slice.moveBack == true); 2477 assert(slice.moveAt(1) == true); 2478 } 2479 2480 // uncomparable values are valid values for an array 2481 // https://issues.dlang.org/show_bug.cgi?id=16331 2482 @system unittest 2483 { 2484 double[] values = [double.nan, double.nan]; 2485 auto arr = Array!double(values); 2486 } 2487 2488 @nogc @system unittest 2489 { 2490 auto a = Array!int(0, 1, 2); 2491 int[3] b = [3, 4, 5]; 2492 short[3] ci = [0, 1, 0]; 2493 auto c = Array!short(ci); 2494 assert(Array!int(0, 1, 2, 0, 1, 2) == a ~ a); 2495 assert(Array!int(0, 1, 2, 3, 4, 5) == a ~ b); 2496 assert(Array!int(0, 1, 2, 3) == a ~ 3); 2497 assert(Array!int(0, 1, 2, 0, 1, 0) == a ~ c); 2498 } 2499 2500 @nogc @system unittest 2501 { 2502 auto a = Array!char('a', 'b'); 2503 assert(Array!char("abc") == a ~ 'c'); 2504 import std.utf : byCodeUnit; 2505 assert(Array!char("abcd") == a ~ "cd".byCodeUnit); 2506 } 2507 2508 @nogc @system unittest 2509 { 2510 auto a = Array!dchar("ąćę"d); 2511 assert(Array!dchar("ąćęϢϖ"d) == a ~ "Ϣϖ"d); 2512 wchar x = 'Ϣ'; 2513 assert(Array!dchar("ąćęϢz"d) == a ~ x ~ 'z'); 2514 } 2515 2516 @system unittest 2517 { 2518 Array!bool a; 2519 assert(a.empty); 2520 a.insertBack(false); 2521 assert(!a.empty); 2522 } 2523 2524 @system unittest 2525 { 2526 Array!bool a; 2527 assert(a.empty); 2528 auto b = a.dup; 2529 assert(b.empty); 2530 a.insertBack(true); 2531 assert(b.empty); 2532 } 2533 2534 @system unittest 2535 { 2536 import std.conv : to; 2537 Array!bool a; 2538 assert(a.length == 0); 2539 a.insert(true); 2540 assert(a.length == 1, to!string(a.length)); 2541 } 2542 2543 @system unittest 2544 { 2545 import std.conv : to; 2546 Array!bool a; 2547 assert(a.capacity == 0); 2548 foreach (i; 0 .. 100) 2549 { 2550 a.insert(true); 2551 assert(a.capacity >= a.length, to!string(a.capacity)); 2552 } 2553 } 2554 2555 @system unittest 2556 { 2557 Array!bool a; 2558 assert(a.capacity == 0); 2559 a.reserve(15657); 2560 assert(a.capacity >= 15657); 2561 a.reserve(100); 2562 assert(a.capacity >= 15657); 2563 } 2564 2565 @system unittest 2566 { 2567 auto a = Array!bool([true, false, true, true]); 2568 assert(a[0 .. 2].length == 2); 2569 } 2570 2571 @system unittest 2572 { 2573 auto a = Array!bool([true, false, true, true]); 2574 assert(a[].length == 4); 2575 } 2576 2577 @system unittest 2578 { 2579 auto a = Array!bool([true, false, true, true]); 2580 assert(a.front); 2581 a.front = false; 2582 assert(!a.front); 2583 } 2584 2585 @system unittest 2586 { 2587 auto a = Array!bool([true, false, true, true]); 2588 assert(a[].length == 4); 2589 } 2590 2591 @system unittest 2592 { 2593 auto a = Array!bool([true, false, true, true]); 2594 assert(a.back); 2595 a.back = false; 2596 assert(!a.back); 2597 } 2598 2599 @system unittest 2600 { 2601 auto a = Array!bool([true, false, true, true]); 2602 assert(a[0] && !a[1]); 2603 a[0] &= a[1]; 2604 assert(!a[0]); 2605 } 2606 2607 @system unittest 2608 { 2609 import std.algorithm.comparison : equal; 2610 auto a = Array!bool([true, false, true, true]); 2611 auto b = Array!bool([true, true, false, true]); 2612 assert(equal((a ~ b)[], 2613 [true, false, true, true, true, true, false, true])); 2614 assert((a ~ [true, false])[].equal([true, false, true, true, true, false])); 2615 Array!bool c; 2616 c.insertBack(true); 2617 assert((c ~ false)[].equal([true, false])); 2618 } 2619 @system unittest 2620 { 2621 import std.algorithm.comparison : equal; 2622 auto a = Array!bool([true, false, true, true]); 2623 auto b = Array!bool([false, true, false, true, true]); 2624 a ~= b; 2625 assert(equal( 2626 a[], 2627 [true, false, true, true, false, true, false, true, true])); 2628 } 2629 2630 @system unittest 2631 { 2632 auto a = Array!bool([true, false, true, true]); 2633 a.clear(); 2634 assert(a.capacity == 0); 2635 } 2636 2637 @system unittest 2638 { 2639 Array!bool a; 2640 a.length = 1057; 2641 assert(a.length == 1057); 2642 assert(a.capacity >= a.length); 2643 foreach (e; a) 2644 { 2645 assert(!e); 2646 } 2647 immutable cap = a.capacity; 2648 a.length = 100; 2649 assert(a.length == 100); 2650 // do not realloc if length decreases 2651 assert(a.capacity == cap); 2652 } 2653 2654 @system unittest 2655 { 2656 Array!bool a; 2657 a.length = 1057; 2658 assert(!a.removeAny()); 2659 assert(a.length == 1056); 2660 foreach (e; a) 2661 { 2662 assert(!e); 2663 } 2664 } 2665 2666 @system unittest 2667 { 2668 Array!bool a; 2669 for (int i = 0; i < 100; ++i) 2670 a.insertBack(true); 2671 foreach (e; a) 2672 assert(e); 2673 } 2674 2675 @system unittest 2676 { 2677 Array!bool a; 2678 a.length = 1057; 2679 assert(a.removeBack(1000) == 1000); 2680 assert(a.length == 57); 2681 foreach (e; a) 2682 { 2683 assert(!e); 2684 } 2685 } 2686 2687 @system unittest 2688 { 2689 import std.conv : to; 2690 Array!bool a; 2691 version (bugxxxx) 2692 { 2693 a._store.refCountedDebug = true; 2694 } 2695 a.insertBefore(a[], true); 2696 assert(a.length == 1, to!string(a.length)); 2697 a.insertBefore(a[], false); 2698 assert(a.length == 2, to!string(a.length)); 2699 a.insertBefore(a[1 .. $], true); 2700 import std.algorithm.comparison : equal; 2701 assert(a[].equal([false, true, true])); 2702 } 2703 2704 // https://issues.dlang.org/show_bug.cgi?id=21555 2705 @system unittest 2706 { 2707 import std.algorithm.comparison : equal; 2708 Array!bool arr; 2709 size_t len = arr.insertBack([false, true]); 2710 assert(len == 2); 2711 } 2712 2713 // https://issues.dlang.org/show_bug.cgi?id=21556 2714 @system unittest 2715 { 2716 import std.algorithm.comparison : equal; 2717 Array!bool a; 2718 a.insertBack([true, true, false, false, true]); 2719 assert(a.length == 5); 2720 2721 assert(a.insertAfter(a[0 .. 5], [false, false]) == 2); 2722 assert(equal(a[], [true, true, false, false, true, false, false])); 2723 2724 assert(a.insertAfter(a[0 .. 5], true) == 1); 2725 assert(equal(a[], [true, true, false, false, true, true, false, false])); 2726 } 2727 2728 @system unittest 2729 { 2730 import std.conv : to; 2731 Array!bool a; 2732 a.length = 10; 2733 a.insertAfter(a[0 .. 5], true); 2734 assert(a.length == 11, to!string(a.length)); 2735 assert(a[5]); 2736 } 2737 @system unittest 2738 { 2739 alias V3 = int[3]; 2740 V3 v = [1, 2, 3]; 2741 Array!V3 arr; 2742 arr ~= v; 2743 assert(arr[0] == [1, 2, 3]); 2744 } 2745 @system unittest 2746 { 2747 alias V3 = int[3]; 2748 V3[2] v = [[1, 2, 3], [4, 5, 6]]; 2749 Array!V3 arr; 2750 arr ~= v; 2751 assert(arr[0] == [1, 2, 3]); 2752 assert(arr[1] == [4, 5, 6]); 2753 } 2754 2755 // Change of length reallocates without calling GC. 2756 // https://issues.dlang.org/show_bug.cgi?id=13642 2757 @system unittest 2758 { 2759 import core.memory; 2760 class ABC { void func() { int x = 5; } } 2761 2762 Array!ABC arr; 2763 // Length only allocates if capacity is too low. 2764 arr.reserve(4); 2765 assert(arr.capacity == 4); 2766 2767 void func() @nogc 2768 { 2769 arr.length = 5; 2770 } 2771 func(); 2772 2773 foreach (ref b; arr) b = new ABC; 2774 GC.collect(); 2775 arr[1].func(); 2776 } 2777 2778 @system unittest 2779 { 2780 2781 Array!int arr = [1, 2, 4, 5]; 2782 int[] data = arr.data(); 2783 2784 const Array!int arr2 = [8, 9]; 2785 assert(arr2.data() == [8, 9]); 2786 2787 data[0] = 0; 2788 assert(arr[0] == 0); 2789 2790 arr.length = 0; 2791 assert(arr.data == []); 2792 2793 Array!int empty; 2794 assert(empty.data == []); 2795 }