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