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