1 /** Array container(s) with optional sortedness via template-parameter 2 * `Ordering` and optional use of GC via `useGCAllocation`. 3 * 4 * TODO UniqueArray!(const(E)) where E has indirections 5 * 6 * TODO Support for constructing from r-value range (container) of non-copyable 7 * elements. 8 * 9 * TODO Add some way to implement lazy sorting either for the whole array (via 10 * bool flag) or completeSort at a certain offset (extra member). 11 * 12 * TODO Replace ` = void` with construction or emplace 13 * 14 * TODO Break out common logic into private `DynamicArray` and reuse with `alias 15 * this` to express StandardArray, SortedArray, SortedSetArray 16 * 17 * TODO Use std.array.insertInPlace in insert()? 18 * TODO Use std.array.replaceInPlace? 19 * 20 * TODO Use `std.algorithm.mutation.move` and `std.range.primitives.moveAt` 21 * when moving internal sub-slices 22 * 23 * TODO Add `c.insertAfter(r, x)` where `c` is a collection, `r` is a range 24 * previously extracted from `c`, and `x` is a value convertible to 25 * collection's element type. See_Also: 26 * https://forum.dlang.org/post/n3qq6e$2bis$1@digitalmars.com 27 * 28 * TODO replace qcmeman with std.experimental.allocator parameter defaulting to 29 * `Mallocator` 30 * 31 * TODO use `integer_sorting.radixSort` when element type `isSigned` or `isUnsigned` and 32 * above or below a certain threshold calculated by my benchmarks 33 * 34 * TODO Remove explicit moves when DMD std.algorithm.mutation.move calls these 35 * members for us (if they exist) 36 */ 37 module nxt.array_ex; 38 39 /// Array element ordering. 40 enum Ordering 41 { 42 unsorted, // unsorted array 43 sortedValues, // sorted array with possibly duplicate values 44 sortedUniqueSet, // sorted array with unique values 45 } 46 47 /// Is `true` iff `ordering` is sorted. 48 enum isOrdered(Ordering ordering) = ordering != Ordering.unsorted; 49 50 version(unittest) 51 { 52 import std.algorithm.iteration : map, filter; 53 import std.algorithm.comparison : equal; 54 import std.conv : to; 55 import std.meta : AliasSeq; 56 import core.internal.traits : Unqual; 57 import nxt.dbgio : dbg; 58 import nxt.array_help : s; 59 } 60 61 import nxt.container_traits : ContainerElementType, needsMove; 62 63 /// Is `true` iff `C` is an instance of an `Array` container. 64 template isArrayContainer(C) 65 { 66 import std.traits : isInstanceOf; 67 enum isArrayContainer = isInstanceOf!(Array, C); 68 } 69 70 /// Semantics of copy construction and copy assignment. 71 enum Assignment 72 { 73 disabled, /// for reference counting use `std.typecons.RefCounted`. for safe slicing use `borrown` 74 move, /// only move construction allowed 75 copy /// always copy (often not the desirable) 76 } 77 78 /** Array of value types `E` with optional sortedness/ordering. 79 * 80 * Always `@safe pure nothrow @nogc` when possible. 81 * 82 * `Assignment` either 83 * - is disabled 84 * - does Rust-style move, or 85 * - does C++-style copying 86 * 87 * Params: 88 * GCAllocation = `true` iff `GC.malloc` is used for store allocation, 89 * otherwise C's `{m,ce,re}alloc()` is used. 90 */ 91 private struct Array(E, 92 // TODO merge these flags into one to reduce template bloat 93 Assignment assignment = Assignment.disabled, 94 Ordering ordering = Ordering.unsorted, 95 bool useGCAllocation = false, 96 CapacityType = size_t, // see also https://github.com/izabera/s 97 alias less = "a < b") // TODO move out of this definition and support only for the case when `ordering` is not `Ordering.unsorted` 98 if (is(CapacityType == ulong) || // 3 64-bit words 99 is(CapacityType == uint)) // 2 64-bit words 100 { 101 import core.internal.traits : hasElaborateDestructor; 102 import core.lifetime : emplace, move, moveEmplace; 103 import std.algorithm.mutation : moveEmplaceAll; 104 import std.range.primitives : isInputRange, isInfinite, ElementType; 105 import std.traits : isIterable, isAssignable, Unqual, isArray, isScalarType, hasIndirections, TemplateOf; 106 import std.functional : binaryFun; 107 import std.meta : allSatisfy; 108 109 import nxt.qcmeman : malloc, calloc, realloc, free, gc_addRange, gc_removeRange; 110 111 private template shouldAddGCRange(T) 112 { 113 import std.traits : hasIndirections, isInstanceOf; 114 enum shouldAddGCRange = hasIndirections!T && !isInstanceOf!(Array, T); // TODO unify to container_traits.shouldAddGCRange 115 } 116 117 /// Mutable element type. 118 private alias MutableE = Unqual!E; 119 120 /// Template for type of `this`. 121 private alias ThisTemplate = TemplateOf!(typeof(this)); 122 123 /// Same type as this but with mutable element type. 124 private alias MutableThis = ThisTemplate!(MutableE, assignment, ordering, useGCAllocation, CapacityType, less); 125 126 static if (useGCAllocation || // either we asked for allocation 127 shouldAddGCRange!E) // or we need GC ranges 128 { 129 import core.memory : GC; 130 } 131 132 /// Is `true` iff `Array` can be interpreted as a narrow D `string` or `wstring`. 133 private enum isNarrowString = (is(MutableE == char) || 134 is(MutableE == wchar)); 135 136 static if (isOrdered!ordering) 137 { 138 static assert(!isNarrowString, "A narrow string cannot be an ordered array because it's not random access'"); 139 } 140 141 alias comp = binaryFun!less; //< comparison 142 143 /// Create a empty array. 144 // this(typeof(null)) nothrow 145 // { 146 // version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 147 // // nothing needed, rely on default initialization of data members 148 // } 149 150 /// Returns: an array of length `initialLength` with all elements default-initialized to `ElementType.init`. 151 static typeof(this) withLength(size_t initialLength) 152 @trusted 153 { 154 version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 155 156 debug { typeof(return) that; } 157 else { typeof(return) that = void; } 158 159 // TODO functionize: 160 if (initialLength > smallCapacity) 161 { 162 emplace!Large(&that._large, initialLength, initialLength, true); // no elements so we need to zero 163 } 164 else 165 { 166 that._small.length = cast(ubyte)initialLength; 167 } 168 169 version(showCtors) dbg("EXITING: ", __PRETTY_FUNCTION__); 170 return that; 171 } 172 173 /// Returns: an array with initial capacity `initialCapacity`. 174 static typeof(this) withCapacity(size_t initialCapacity) 175 @trusted 176 { 177 version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 178 179 debug { typeof(return) that; } 180 else { typeof(return) that = void; } 181 182 if (initialCapacity > smallCapacity) 183 { 184 emplace!Large(&that._large, initialCapacity, 0, false); 185 } 186 else 187 { 188 that._small.length = 0; 189 } 190 191 version(showCtors) dbg("EXITING: ", __PRETTY_FUNCTION__); 192 return that; 193 } 194 195 /// Returns: an array of one element `element`. 196 static typeof(this) withElement(E element) 197 @trusted 198 { 199 version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 200 201 debug { typeof(return) that; } 202 else { typeof(return) that = void; } 203 204 // TODO functionize: 205 enum initialLength = 1; 206 if (initialLength > smallCapacity) 207 { 208 emplace!Large(&that._large, initialLength, initialLength, false); 209 } 210 else 211 { 212 emplace!Small(&that._small, initialLength, false); 213 } 214 215 // move element 216 static if (__traits(isCopyable, E)) 217 { 218 that._mptr[0] = element; 219 } 220 else static if (!shouldAddGCRange!E) 221 { 222 moveEmplace(*cast(MutableE*)&element, // TODO can we prevent this cast? 223 that._mptr[0]); // safe to cast away constness when no indirections 224 } 225 else 226 { 227 moveEmplace(element, that._mptr[0]); // TODO remove `move` when compiler does it for us 228 } 229 230 return that; 231 } 232 233 /// Returns: an array of `Us.length` number of elements set to `elements`. 234 static typeof(this) withElements(Us...)(Us elements) 235 @trusted 236 { 237 version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 238 239 debug { typeof(return) that; } 240 else { typeof(return) that = void; } 241 242 // TODO functionize: 243 enum initialLength = Us.length; 244 if (initialLength > smallCapacity) 245 { 246 emplace!Large(&that._large, initialLength, initialLength, false); 247 } 248 else 249 { 250 emplace!Small(&that._small, initialLength, false); 251 } 252 253 // move elements 254 foreach (immutable i, ref element; elements) 255 { 256 static if (!shouldAddGCRange!E) 257 { 258 moveEmplace(*cast(MutableE*)&element, 259 that._mptr[i]); // safe to cast away constness when no indirections 260 } 261 else 262 { 263 moveEmplace(element, that._mptr[i]); // TODO remove `move` when compiler does it for us 264 } 265 } 266 267 static if (isOrdered!ordering) 268 { 269 that.sortElements!comp(); 270 } 271 272 return that; 273 } 274 275 static if (assignment == Assignment.copy) 276 { 277 /// Copy construction. 278 this(this) @trusted 279 { 280 version(showCtors) dbg("Copy ctor: ", typeof(this).stringof); 281 if (isLarge) // only large case needs special treatment 282 { 283 auto rhs_storePtr = _large.ptr; // save store pointer 284 _large.setCapacity(this.length); // pack by default 285 // _large.length already copied 286 _large.ptr = allocate(this.length, false); 287 foreach (immutable i; 0 .. this.length) 288 { 289 _large.ptr[i] = rhs_storePtr[i]; 290 } 291 } 292 } 293 294 /// Copy assignment. 295 void opAssign(typeof(this) rhs) @trusted 296 { 297 version(showCtors) dbg("Copy assign: ", typeof(this).stringof); 298 // self-assignment may happen when assigning derefenced pointer 299 if (isLarge) // large = ... 300 { 301 if (rhs.isLarge) // large = large 302 { 303 // TODO functionize to Large.opAssign(Large rhs): 304 if (_large.ptr != rhs._large.ptr) // if not self assignment 305 { 306 _large.length = rhs._large.length; 307 reserve(rhs._large.length); 308 foreach (immutable i; 0 .. rhs._large.length) 309 { 310 _large.ptr[i] = rhs._large.ptr[i]; 311 } 312 } 313 } 314 else // large = small 315 { 316 { // make it small 317 clear(); // clear large storage 318 _large.isLarge = false; // TODO needed? 319 } 320 _small = rhs._small; // small 321 } 322 } 323 else // small = ... 324 { 325 if (rhs.isLarge) // small = large 326 { 327 { // make it large 328 clear(); // clear small storage 329 _large.isLarge = true; // TODO needed? 330 } 331 // TODO functionize to Large.opAssign(Large rhs): 332 if (_large.ptr != rhs._large.ptr) // if not self assignment 333 { 334 _large.length = rhs._large.length; 335 reserve(rhs._large.length); 336 foreach (immutable i; 0 .. rhs._large.length) 337 { 338 _large.ptr[i] = rhs._large.ptr[i]; 339 } 340 } 341 } 342 else // small = small 343 { 344 _small = rhs._small; 345 } 346 } 347 } 348 } 349 else static if (assignment == Assignment.disabled) 350 { 351 @disable this(this); 352 } 353 else static if (assignment == Assignment.move) 354 { 355 /// Copy ctor moves. 356 this(typeof(this) rhs) @trusted 357 { 358 version(showCtors) dbg("Copying: ", typeof(this).stringof); 359 assert(!isBorrowed); 360 moveEmplace(rhs, this); // TODO remove `move` when compiler does it for us 361 } 362 363 /// Assignment moves. 364 void opAssign(typeof(this) rhs) @trusted 365 { 366 assert(!isBorrowed); 367 import std.algorith.mutation : move; 368 move(rhs, this); // TODO remove `move` when compiler does it for us 369 } 370 } 371 372 static if (__traits(isCopyable, E)) 373 { 374 /// Returns: shallow duplicate of `this`. 375 @property MutableThis dup() const @trusted // `MutableThis` mimics behaviour of `dup` for builtin D arrays 376 { 377 debug { typeof(return) that; } 378 else { typeof(return) that = void; } 379 380 if (isLarge) 381 { 382 emplace!(that.Large)(&that._large, _large.length, _large.length, false); 383 foreach (immutable i; 0 .. _large.length) 384 { 385 // TODO is there a more standardized way of solving this other than this hacky cast? 386 that._large.ptr[i] = (cast(E*)_large.ptr)[i]; 387 } 388 } 389 else 390 { 391 emplace!(that.Small)(&that._small, _small.length, false); 392 // TODO is there a more standardized way of solving this other than this hacky cast? 393 that._small.elms[0 .. _small.length] = (cast(E[_small.elms.length])_small.elms)[0 .. _small.length]; // copy elements 394 } 395 return that; 396 } 397 } 398 399 bool opEquals(in ref typeof(this) rhs) const 400 @trusted 401 { 402 static if (__traits(isCopyable, E)) 403 { 404 return this[] == rhs[]; // TODO fix DMD to make this work for non-copyable aswell 405 } 406 else 407 { 408 if (this.length != rhs.length) { return false; } 409 foreach (immutable i; 0 .. this.length) 410 { 411 if (this.ptr[i] != rhs.ptr[i]) { return false; } 412 } 413 return true; 414 } 415 } 416 bool opEquals(in typeof(this) rhs) const 417 @trusted 418 { 419 static if (__traits(isCopyable, E)) 420 { 421 return this[] == rhs[]; // TODO fix DMD to make this work for non-copyable aswell 422 } 423 else 424 { 425 if (this.length != rhs.length) { return false; } 426 foreach (immutable i; 0 .. this.length) 427 { 428 if (this.ptr[i] != rhs.ptr[i]) { return false; } 429 } 430 return true; 431 } 432 } 433 434 /// Compare with range `R` with comparable element type. 435 pragma(inline, true) 436 bool opEquals(R)(R rhs) const 437 if (isInputRange!R && !isInfinite!R) 438 { 439 return opSlice.equal(rhs); 440 } 441 442 /// Calculate D associative array (AA) key hash. 443 hash_t toHash() const // cannot currently be template-lazy 444 nothrow @trusted 445 { 446 pragma(msg, "WARNING: using toHash() when we should use toDigest instead"); 447 import core.internal.hash : hashOf; 448 static if (__traits(isCopyable, E)) 449 { 450 return this.length ^ hashOf(slice()); 451 } 452 else 453 { 454 typeof(return) hash = this.length; 455 foreach (immutable i; 0 .. this.length) 456 { 457 hash ^= this.ptr[i].hashOf; 458 } 459 return hash; 460 } 461 } 462 463 /** Construct from InputRange `values`. 464 If `values` are sorted `assumeSortedParameter` is `true`. 465 466 TODO Have `assumeSortedParameter` only when `isOrdered!ordering` is true 467 */ 468 this(R)(R values, bool assumeSortedParameter = false) 469 @trusted 470 @("complexity", "O(n*log(n))") 471 if (isIterable!R) 472 { 473 version(showCtors) dbg("ENTERING: smallCapacity:", smallCapacity, " @", __PRETTY_FUNCTION__); 474 475 // append new data 476 import std.range.primitives : hasLength; 477 static if (hasLength!R) 478 { 479 // TODO choose large or small depending on values.length 480 _small.isLarge = false; 481 _small.length = 0; 482 483 reserve(values.length); // fast reserve 484 setOnlyLength(values.length); 485 486 // static if (__traits(isRef)) 487 // { 488 // // TODO dup elements 489 // } 490 // else 491 // { 492 // // TODO move elements 493 // } 494 495 size_t i = 0; 496 foreach (ref value; move(values)) // TODO remove `move` when compiler does it for us 497 { 498 // TODO functionize: 499 static if (needsMove!(typeof(value))) 500 moveEmplace(value, _mptr[i++]); 501 else 502 _mptr[i++] = value; 503 } 504 } 505 else 506 { 507 // always start small 508 _small.isLarge = false; 509 _small.length = 0; 510 511 size_t i = 0; 512 foreach (ref value; move(values)) // TODO remove `move` when compiler does it for us 513 { 514 reserve(i + 1); // slower reserve 515 // TODO functionize: 516 static if (needsMove!(typeof(value))) 517 moveEmplace(value, _mptr[i++]); 518 else 519 _mptr[i++] = value; 520 setOnlyLength(i); // must be set here because correct length is needed in reserve call above in this same scope 521 } 522 } 523 524 if (!assumeSortedParameter) 525 { 526 static if (isOrdered!ordering) 527 sortElements!comp(); 528 static if (ordering == Ordering.sortedUniqueSet) 529 { 530 import std.algorithm.iteration : uniq; 531 size_t j = 0; 532 foreach (ref e; uniq(slice)) 533 { 534 auto ePtr = &e; 535 const separate = ePtr != &_mptr[j]; 536 if (separate) 537 move(*cast(MutableE*)ePtr, _mptr[j]); 538 ++j; 539 } 540 shrinkTo(j); 541 } 542 } 543 544 version(showCtors) dbg("EXITING: ", __PRETTY_FUNCTION__); 545 } 546 547 /// Sort all elements in-place regardless of `ordering`. 548 private void sortElements(alias comp_)() 549 @trusted 550 { 551 import std.algorithm.sorting : sort; 552 sort!comp_(_mptr[0 .. length]); 553 } 554 555 /// Reserve room for `newCapacity`. 556 void reserve(size_t newCapacity) 557 pure @trusted 558 { 559 assert(!isBorrowed); 560 if (newCapacity <= capacity) 561 return; 562 if (isLarge) 563 { 564 static if (shouldAddGCRange!E) 565 gc_removeRange(_mptr); 566 import std.math : nextPow2; 567 reallocateLargeStoreAndSetCapacity(newCapacity.nextPow2); 568 static if (shouldAddGCRange!E) 569 gc_addRange(_mptr, _large.capacity * E.sizeof); 570 } 571 else 572 { 573 if (newCapacity > smallCapacity) // convert to large 574 { 575 auto tempLarge = Large(newCapacity, length, false); 576 577 // move small to temporary large 578 foreach (immutable i; 0 .. length) 579 moveEmplace(_small._mptr[i], 580 tempLarge._mptr[i]); 581 582 static if (hasElaborateDestructor!E) 583 destroyElements(); 584 585 // TODO functionize: 586 { // make this large 587 moveEmplace(tempLarge, _large); 588 } 589 590 assert(isLarge); 591 } 592 else 593 { 594 // staying small 595 } 596 } 597 } 598 599 /// Pack/Compress storage. 600 void compress() 601 pure @trusted 602 { 603 assert(!isBorrowed); 604 if (isLarge) 605 { 606 if (this.length) 607 { 608 if (this.length <= smallCapacity) 609 { 610 Small tempSmall = Small(length, false); 611 612 // move elements to temporary small. TODO make moveEmplaceAll work on char[],char[] and use 613 foreach (immutable i; 0 .. length) 614 moveEmplace(_large._mptr[i], 615 tempSmall._mptr[i]); 616 617 // free existing large data 618 static if (shouldAddGCRange!E) 619 gc_removeRange(_mptr); 620 621 static if (useGCAllocation) 622 GC.free(_mptr); 623 else 624 free(_mptr); 625 626 moveEmplace(tempSmall, _small); 627 } 628 else 629 { 630 if (_large.capacity != this.length) 631 { 632 static if (shouldAddGCRange!E) 633 gc_removeRange(_mptr); 634 reallocateLargeStoreAndSetCapacity(this.length); 635 static if (shouldAddGCRange!E) 636 gc_addRange(_mptr, _large.capacity * E.sizeof); 637 } 638 } 639 } 640 else // if empty 641 { 642 // free data 643 static if (shouldAddGCRange!E) 644 gc_removeRange(_mptr); 645 646 static if (useGCAllocation) 647 GC.free(_mptr); 648 else 649 free(_mptr); 650 651 _large.capacity = 0; 652 _large.ptr = null; 653 } 654 } 655 } 656 /// ditto 657 alias pack = compress; 658 659 /// Reallocate storage. TODO move to Large.reallocateAndSetCapacity 660 private void reallocateLargeStoreAndSetCapacity(size_t newCapacity) pure @trusted 661 { 662 version(D_Coverage) {} else pragma(inline, true); 663 _large.setCapacity(newCapacity); 664 static if (useGCAllocation) 665 _large.ptr = cast(E*)GC.realloc(_mptr, E.sizeof * _large.capacity); 666 else // @nogc 667 { 668 _large.ptr = cast(E*)realloc(_mptr, E.sizeof * _large.capacity); 669 assert(_large.ptr, "Reallocation failed"); 670 } 671 } 672 673 /// Destruct. 674 ~this() @trusted @nogc 675 { 676 version(D_Coverage) {} else pragma(inline, true); 677 assert(!isBorrowed); 678 if (isLarge) 679 debug assert(_large.ptr != _ptrMagic, "Double free."); // trigger fault for double frees 680 release(); 681 if (isLarge) 682 debug _large.ptr = _ptrMagic; // tag as freed 683 } 684 685 /// Empty. 686 void clear() @nogc 687 { 688 version(D_Coverage) {} else pragma(inline, true); 689 assert(!isBorrowed); 690 release(); 691 resetInternalData(); 692 } 693 /// ditto 694 pragma(inline, true) 695 void opAssign(typeof(null)) 696 { 697 clear(); 698 } 699 700 /// Destroy elements. 701 static if (hasElaborateDestructor!E) 702 { 703 private void destroyElements() @trusted 704 { 705 foreach (immutable i; 0 .. this.length) 706 .destroy(_mptr[i]); 707 } 708 } 709 710 /// Release internal store. 711 private void release() @trusted @nogc 712 { 713 static if (hasElaborateDestructor!E) 714 destroyElements(); 715 if (isLarge) 716 { 717 static if (shouldAddGCRange!E) 718 gc_removeRange(_large.ptr); 719 720 static if (useGCAllocation) 721 GC.free(_large.ptr); 722 else // @nogc 723 { 724 static if (!shouldAddGCRange!E) 725 free(cast(MutableE*)_large.ptr); // safe to case away constness 726 else 727 free(_large.ptr); 728 } 729 } 730 } 731 732 /// Reset internal data. 733 pragma(inline, true) 734 private void resetInternalData() @trusted pure @nogc 735 { 736 if (isLarge) 737 { 738 _large.ptr = null; 739 _large.length = 0; 740 _large.capacity = 0; 741 } 742 else 743 _small.length = 0; // fast discardal 744 } 745 746 /// Is `true` if `U` can be assign to the element type `E` of `this`. 747 enum isElementAssignable(U) = isAssignable!(E, U); 748 749 /** Removal doesn't need to care about ordering. */ 750 ContainerElementType!(typeof(this), E) removeAt(size_t index) 751 @trusted 752 @("complexity", "O(length)") 753 { 754 assert(!isBorrowed); 755 assert(index < this.length); 756 auto value = move(_mptr[index]); 757 758 // TODO use this instead: 759 // immutable si = index + 1; // source index 760 // immutable ti = index; // target index 761 // immutable restLength = this.length - (index + 1); 762 // moveEmplaceAll(_mptr[si .. si + restLength], 763 // _mptr[ti .. ti + restLength]); 764 765 foreach (immutable i; 0 .. this.length - (index + 1)) // each element index that needs to be moved 766 { 767 immutable si = index + i + 1; // source index 768 immutable ti = index + i; // target index 769 moveEmplace(_mptr[si], // TODO remove `move` when compiler does it for us 770 _mptr[ti]); 771 } 772 773 decOnlyLength(); 774 return move(value); // TODO remove `move` when compiler does it for us 775 } 776 777 /** Removal doesn't need to care about ordering. */ 778 pragma(inline, true) 779 ContainerElementType!(typeof(this), E) popFront() 780 @trusted 781 @("complexity", "O(length)") 782 { 783 return removeAt(0); 784 } 785 786 /** Removal doesn't need to care about ordering. */ 787 pragma(inline) 788 void popBack() @("complexity", "O(1)") 789 { 790 assert(!isBorrowed); 791 assert(!empty); 792 decOnlyLength(); 793 } 794 795 /** Pop back element and return it. */ 796 pragma(inline) 797 E backPop() 798 @trusted 799 { 800 assert(!isBorrowed); 801 assert(!empty); 802 decOnlyLength(); 803 // TODO functionize: 804 static if (needsMove!E) 805 return move(_mptr[this.length]); // move is indeed need here 806 else 807 return _mptr[this.length]; // no move needed 808 } 809 810 /** Pop last `count` back elements. */ 811 pragma(inline, true) 812 void popBackN(size_t count) @("complexity", "O(1)") 813 { 814 assert(!isBorrowed); 815 shrinkTo(this.length - count); 816 } 817 818 static if (!isOrdered!ordering) // for unsorted arrays 819 { 820 /// Push back (append) `values`. 821 pragma(inline) void insertBack(Us...)(Us values) 822 @trusted 823 @("complexity", "O(1)") 824 if (values.length >= 1 && 825 allSatisfy!(isElementAssignable, Us)) 826 { 827 assert(!isBorrowed); 828 immutable newLength = this.length + values.length; 829 reserve(newLength); 830 foreach (immutable i, ref value; values) // `ref` so we can `move` 831 { 832 // TODO functionize: 833 static if (needsMove!(typeof(value))) 834 moveEmplace(*cast(MutableE*)&value, _mptr[this.length + i]); 835 else 836 _mptr[this.length + i] = value; 837 } 838 setOnlyLength(this.length + values.length); 839 } 840 841 /// ditto 842 void insertBack(R)(R values) @("complexity", "O(values.length)") @trusted 843 if (isInputRange!R && !isInfinite!R && 844 !(isArray!R) && 845 !(isArrayContainer!R) && 846 isElementAssignable!(ElementType!R)) 847 { 848 assert(!isBorrowed); 849 import std.range.primitives : hasLength; 850 static if (hasLength!R) 851 { 852 const nextLength = this.length + values.length; 853 reserve(nextLength); 854 size_t i = 0; 855 foreach (ref value; values) // `ref` so we can `move` 856 { 857 // TODO functionize: 858 static if (needsMove!(typeof(value))) 859 moveEmplace(*cast(Mutable!E*)&value, _mptr[this.length + i]); 860 else 861 _mptr[this.length + i] = value; 862 ++i; 863 } 864 setOnlyLength(nextLength); 865 } 866 else 867 { 868 foreach (ref value; values) // `ref` so we can `move` 869 insertBack(value); 870 } 871 } 872 873 /// ditto. 874 void insertBack(A)(A values) @trusted @("complexity", "O(values.length)") 875 if (isArray!A && 876 (is(MutableE == Unqual!(typeof(A.init[0]))) || // for narrow strings 877 isElementAssignable!(ElementType!A))) 878 { 879 assert(!isBorrowed); 880 static if (is(A == immutable(E)[])) 881 { 882 // immutable array cannot overlap with mutable array container 883 // data; no need to check for overlap with `overlaps()` 884 reserve(this.length + values.length); 885 _mptr[this.length .. this.length + values.length] = values[]; 886 setOnlyLength(this.length + values.length); 887 } 888 else 889 { 890 import nxt.overlapping : overlaps; 891 if (this.ptr == values[].ptr) // called for instances as: `this ~= this` 892 { 893 reserve(2*this.length); 894 foreach (immutable i; 0 .. this.length) 895 _mptr[this.length + i] = ptr[i]; // needs copying 896 setOnlyLength(2 * this.length); 897 } 898 else if (overlaps(this[], values[])) 899 assert(0, `TODO Handle overlapping arrays`); 900 else 901 { 902 reserve(this.length + values.length); 903 static if (is(MutableE == Unqual!(ElementType!A))) // TODO also when `E[]` is `A[]` 904 _mptr[this.length .. this.length + values.length] = values[]; 905 else 906 foreach (immutable i, ref value; values) 907 _mptr[this.length + i] = value; 908 setOnlyLength(this.length + values.length); 909 } 910 } 911 } 912 913 /// ditto. 914 void insertBack(A)(in ref A values) @trusted @("complexity", "O(values.length)") // TODO `in` parameter qualifier doesn't work here. Compiler bug? 915 if (isArrayContainer!A && 916 (is(MutableE == Unqual!(typeof(A.init[0]))) || // for narrow strings 917 isElementAssignable!(ElementType!A))) 918 { 919 insertBack(values[]); 920 } 921 alias put = insertBack; // OutputRange support 922 923 924 // NOTE these separate overloads of opOpAssign are needed because one 925 // `const ref`-parameter-overload doesn't work because of compiler bug 926 // with: `this(this) @disable` 927 pragma(inline) 928 void opOpAssign(string op, Us...)(Us values) 929 if (op == "~" && 930 values.length >= 1 && 931 allSatisfy!(isElementAssignable, Us)) 932 { 933 assert(!isBorrowed); 934 insertBack(move(values)); // TODO remove `move` when compiler does it for us 935 // static if (values.length == 1) 936 // { 937 // import std.traits : hasIndirections; 938 // static if (hasIndirections!(Us[0])) 939 // { 940 // insertBack(move(values)); // TODO remove `move` when compiler does it for us 941 // } 942 // else 943 // { 944 // insertBack(move(cast(Unqual!(Us[0]))values[0])); // TODO remove `move` when compiler does it for us 945 // } 946 // } 947 // else 948 // { 949 // insertBack(move(values)); // TODO remove `move` when compiler does it for us 950 // } 951 } 952 953 pragma(inline) 954 void opOpAssign(string op, R)(R values) 955 if (op == "~" && 956 isInputRange!R && 957 !isInfinite!R && 958 allSatisfy!(isElementAssignable, ElementType!R)) 959 { 960 assert(!isBorrowed); 961 // TODO use move(values) 962 insertBack(values); // TODO remove `move` when compiler does it for us 963 } 964 965 pragma(inline, true) 966 void opOpAssign(string op, A)(ref A values) 967 if (op == "~" && 968 isArrayContainer!A && 969 isElementAssignable!(ElementType!A)) 970 { 971 assert(!isBorrowed); 972 insertBack(values); 973 } 974 } 975 976 import searching_ex : containsStoreIndex; // TODO this is redundant but elides rdmd dependency error for array_ex.d 977 978 static if (isOrdered!ordering) 979 { 980 import std.range : SearchPolicy, assumeSorted; 981 982 /// Returns: `true` iff this contains `value`. 983 bool contains(U)(U value) const @nogc @("complexity", "O(log(length))") 984 { 985 return this[].contains(value); // reuse `SortedRange.contains` 986 } 987 988 /** Wrapper for `std.range.SortedRange.lowerBound` when this `ordering` is sorted. */ 989 auto lowerBound(SearchPolicy sp = SearchPolicy.binarySearch, U)(U e) inout @("complexity", "O(log(length))") 990 { 991 return this[].lowerBound!sp(e); // reuse `SortedRange.lowerBound` 992 } 993 994 /** Wrapper for `std.range.SortedRange.upperBound` when this `ordering` is sorted. */ 995 auto upperBound(SearchPolicy sp = SearchPolicy.binarySearch, U)(U e) inout @("complexity", "O(log(length))") 996 { 997 return this[].upperBound!sp(e); // reuse `SortedRange.upperBound` 998 } 999 1000 static if (ordering == Ordering.sortedUniqueSet) 1001 { 1002 /** Inserts several `values` into `this` ordered set. 1003 1004 Returns: `bool`-array with same length as `values`, where i:th 1005 `bool` value is set if `value[i]` wasn't previously in `this`. 1006 */ 1007 bool[Us.length] insertMany(SearchPolicy sp = SearchPolicy.binarySearch, Us...)(Us values) @("complexity", "O(length)") 1008 if (values.length >= 1 && 1009 allSatisfy!(isElementAssignable, Us)) 1010 in 1011 { 1012 assert(!isBorrowed); 1013 1014 // assert no duplicates in `values` 1015 import std.range.primitives : empty; 1016 import std.algorithm.searching : findAdjacent; 1017 import std.algorithm.sorting : sort; 1018 1019 // TODO functionize or use other interface in pushing `values` 1020 import std.traits : CommonType; 1021 CommonType!Us[Us.length] valuesArray; 1022 foreach (immutable i, const ref value; values) 1023 valuesArray[i] = value; 1024 assert(sort(valuesArray[]).findAdjacent.empty, 1025 "Parameter `values` must not contain duplicate elements"); 1026 } 1027 do 1028 { 1029 static if (values.length == 1) // faster because `contains()` followed by `completeSort()` searches array twice 1030 { 1031 import nxt.searching_ex : containsStoreIndex; 1032 size_t index; 1033 if (slice.assumeSorted!comp.containsStoreIndex!sp(values, index)) // faster than `completeSort` for single value 1034 return [false]; 1035 else 1036 { 1037 insertAtIndexHelper(index, values); 1038 return [true]; 1039 } 1040 } 1041 else 1042 { 1043 import std.algorithm.sorting : completeSort; 1044 1045 debug { typeof(return) hits; } 1046 else { typeof(return) hits = void; } 1047 1048 size_t expandedLength = 0; 1049 immutable initialLength = this.length; 1050 foreach (immutable i, ref value; values) 1051 { 1052 // TODO reuse completeSort with uniqueness handling? 1053 static if (values.length == 1) 1054 { 1055 // TODO reuse single parameter overload linearUniqueInsert() and return 1056 } 1057 else 1058 { 1059 // TODO reuse completeSort with uniqueness handling? 1060 } 1061 hits[i] = !this[0 .. initialLength].contains(value); 1062 if (hits[i]) 1063 { 1064 insertBackHelper(value); // NOTE: append but don't yet sort 1065 ++expandedLength; 1066 } 1067 } 1068 1069 if (expandedLength != 0) 1070 { 1071 immutable ix = this.length - expandedLength; 1072 // TODO use `_mptr` here instead and functionize to @trusted helper function 1073 completeSort!comp(slice[0 .. ix].assumeSorted!comp, 1074 slice[ix .. this.length]); 1075 } 1076 return hits; 1077 } 1078 } 1079 } 1080 else static if (ordering == Ordering.sortedValues) 1081 { 1082 /** Inserts `values`. */ 1083 void insertMany(SearchPolicy sp = SearchPolicy.binarySearch, Us...)(Us values) @("complexity", "O(log(length))") 1084 if (values.length >= 1 && 1085 allSatisfy!(isElementAssignable, Us)) 1086 { 1087 assert(!isBorrowed); 1088 1089 // TODO add optimization for values.length == 2 1090 static if (values.length == 1) 1091 { 1092 import nxt.searching_ex : containsStoreIndex; 1093 size_t index; 1094 if (!slice.assumeSorted!comp.containsStoreIndex!sp(values, index)) // faster than `completeSort` for single value 1095 insertAtIndexHelper(index, values); 1096 } 1097 else 1098 { 1099 insertBackHelper(values); // simpler because duplicates are allowed 1100 immutable ix = this.length - values.length; 1101 import std.algorithm.sorting : completeSort; 1102 completeSort!comp(_mptr[0 .. ix].assumeSorted!comp, 1103 _mptr[ix .. this.length]); 1104 } 1105 } 1106 } 1107 } 1108 else 1109 { 1110 /** Insert element(s) `values` at array offset `index`. */ 1111 pragma(inline, true) 1112 void insertAtIndex(Us...)(size_t index, Us values) @("complexity", "O(length)") 1113 if (values.length >= 1 && 1114 allSatisfy!(isElementAssignable, Us)) 1115 { 1116 assert(!isBorrowed); 1117 insertAtIndexHelper(index, values); 1118 } 1119 1120 /** Insert element(s) `values` at the beginning. */ 1121 pragma(inline, true) 1122 void pushFront(Us...)(Us values) @("complexity", "O(length)") 1123 if (values.length >= 1 && 1124 allSatisfy!(isElementAssignable, Us)) 1125 { 1126 insertAtIndex(0, values); 1127 } 1128 1129 alias prepend = pushFront; 1130 1131 import nxt.traits_ex : isComparable; 1132 static if (__traits(isCopyable, E) && 1133 !is(E == char) && 1134 !is(E == wchar) && 1135 isComparable!E) 1136 { 1137 /// Returns: a sorted array copy. 1138 Array!(E, assignment, ordering.sortedValues, useGCAllocation, CapacityType, less_) toSortedArray(alias less_ = "a < b")() const 1139 { 1140 return typeof(return)(slice); 1141 } 1142 /// Returns: a sorted set array copy. 1143 Array!(E, assignment, ordering.sortedUniqueSet, useGCAllocation, CapacityType, less_) toSortedSetArray(alias less_ = "a < b")() const 1144 { 1145 return typeof(return)(slice); 1146 } 1147 } 1148 } 1149 1150 /** Helper function used externally for unsorted and internally for sorted. */ 1151 private void insertAtIndexHelper(Us...)(size_t index, Us values) @trusted @("complexity", "O(length)") 1152 { 1153 reserve(this.length + values.length); 1154 1155 // TODO factor this to robustCopy. It uses copy when no overlaps (my algorithm_em), iteration otherwise 1156 enum usePhobosCopy = false; 1157 static if (usePhobosCopy) 1158 { 1159 // TODO why does this fail? 1160 import std.algorithm.mutation : copy; 1161 copy(ptr[index .. 1162 this.length], // source 1163 _mptr[index + values.length .. 1164 this.length + values.length]); // target 1165 } 1166 else 1167 { 1168 // move second part in reverse 1169 // TODO functionize move 1170 foreach (immutable i; 0 .. this.length - index) // each element index that needs to be moved 1171 { 1172 immutable si = this.length - 1 - i; // source index 1173 immutable ti = si + values.length; // target index 1174 _mptr[ti] = ptr[si]; // TODO move construct? 1175 } 1176 } 1177 1178 // set new values 1179 foreach (immutable i, ref value; values) 1180 { 1181 ptr[index + i] = value; // TODO use range algorithm instead? 1182 } 1183 1184 setOnlyLength(this.length + values.length); 1185 } 1186 1187 private void insertBackHelper(Us...)(Us values) 1188 @trusted 1189 @("complexity", "O(1)") 1190 { 1191 const newLength = this.length + values.length; 1192 reserve(newLength); 1193 foreach (immutable i, ref value; values) 1194 { 1195 // TODO functionize: 1196 static if (needsMove!(typeof(value))) 1197 moveEmplace(*cast(MutableE*)&value, 1198 _mptr[this.length + i]); 1199 else 1200 _mptr[this.length + i] = value; 1201 } 1202 setOnlyLength(newLength); 1203 } 1204 1205 @property @("complexity", "O(1)") 1206 pragma(inline): 1207 1208 /// ditto 1209 static if (isOrdered!ordering) 1210 { 1211 const pure: // indexing and slicing must be `const` when ordered 1212 1213 /// Slice operator must be const when ordered. 1214 auto opSlice() return scope @trusted // TODO remove @trusted? 1215 { 1216 static if (is(E == class)) 1217 { 1218 // TODO remove this workaround when else branch works for classes 1219 return (cast(E[])slice).assumeSorted!comp; 1220 } 1221 else 1222 { 1223 return (cast(const(E)[])slice).assumeSorted!comp; 1224 } 1225 } 1226 /// ditto 1227 auto opSlice(this This)(size_t i, size_t j) return scope @trusted // TODO remove @trusted? 1228 { 1229 import std.range : assumeSorted; 1230 return (cast(const(E)[])slice[i .. j]).assumeSorted!comp; 1231 } 1232 private alias This = typeof(this); 1233 1234 /// Index operator must be const to preserve ordering. 1235 ref const(E) opIndex(size_t i) return scope @nogc @trusted 1236 { 1237 assert(i < this.length); 1238 return ptr[i]; 1239 } 1240 1241 /// Get front element (as constant reference to preserve ordering). 1242 ref const(E) front() return scope @nogc @trusted 1243 { 1244 assert(!empty); 1245 return ptr[0]; 1246 } 1247 1248 /// Get back element (as constant reference to preserve ordering). 1249 ref const(E) back() return scope @nogc @trusted 1250 { 1251 assert(!empty); 1252 return ptr[this.length - 1]; 1253 } 1254 } 1255 else 1256 { 1257 /// Set length to `newLength`. 1258 @property void length(size_t newLength) 1259 { 1260 if (newLength < length) 1261 { 1262 shrinkTo(newLength); 1263 } 1264 else 1265 { 1266 reserve(newLength); 1267 setOnlyLength(newLength); 1268 } 1269 } 1270 1271 @nogc: 1272 1273 /// Index assign operator. 1274 ref E opIndexAssign(V)(V value, size_t i) 1275 @trusted return scope 1276 { 1277 assert(!isBorrowed); 1278 assert(i < this.length); 1279 static if (isScalarType!E) 1280 ptr[i] = value; 1281 else 1282 move(*(cast(MutableE*)(&value)), _mptr[i]); // TODO is this correct? 1283 return ptr[i]; 1284 } 1285 1286 /// Slice assign operator. 1287 static if (__traits(isCopyable, E)) 1288 { 1289 void opSliceAssign(V)(V value, size_t i, size_t j) 1290 @trusted return scope 1291 { 1292 assert(!isBorrowed); 1293 assert(i <= j); 1294 assert(j <= this.length); 1295 foreach (immutable i; 0 .. this.length) 1296 { 1297 ptr[i] = value; 1298 } 1299 } 1300 } 1301 1302 pure inout: // indexing and slicing has mutable access only when unordered 1303 1304 /// Slice operator. 1305 pragma(inline) 1306 inout(E)[] opSlice() return 1307 { 1308 return this.opSlice(0, this.length); 1309 } 1310 /// ditto 1311 inout(E)[] opSlice(size_t i, size_t j) 1312 @trusted return scope 1313 { 1314 assert(i <= j); 1315 assert(j <= this.length); 1316 return ptr[i .. j]; 1317 } 1318 1319 @trusted: 1320 1321 /// Index operator. 1322 ref inout(E) opIndex(size_t i) return scope 1323 { 1324 assert(i < this.length); 1325 return ptr[i]; 1326 } 1327 1328 /// Get front element reference. 1329 ref inout(E) front() return scope 1330 { 1331 assert(!empty); 1332 return ptr[0]; 1333 } 1334 1335 /// Get back element reference. 1336 ref inout(E) back() return scope 1337 { 1338 assert(!empty); 1339 return ptr[this.length - 1]; 1340 } 1341 } 1342 1343 alias data = opSlice; // `std.array.Appender` compatibility 1344 1345 // static if (__traits(isCopyable, E)) 1346 // { 1347 // string toString() const @property @trusted pure 1348 // { 1349 // import std.array : Appender; 1350 // import std.conv : to; 1351 // Appender!string s = "["; 1352 // foreach (immutable i; 0 .. this.length) 1353 // { 1354 // if (i) { s.put(','); } 1355 // s.put(ptr[i].to!string); 1356 // } 1357 // s.put("]"); 1358 // return s.data; 1359 // } 1360 // } 1361 1362 pure: 1363 1364 /** Allocate heap regionwith `newCapacity` number of elements of type `E`. 1365 If `zero` is `true` they will be zero-initialized. 1366 */ 1367 private static MutableE* allocate(size_t newCapacity, bool zero = false) 1368 { 1369 typeof(return) ptr = null; 1370 static if (useGCAllocation) 1371 { 1372 if (zero) { ptr = cast(typeof(return))GC.calloc(newCapacity, E.sizeof); } 1373 else { ptr = cast(typeof(return))GC.malloc(newCapacity * E.sizeof); } 1374 } 1375 else // @nogc 1376 { 1377 if (zero) { ptr = cast(typeof(return))calloc(newCapacity, E.sizeof); } 1378 else { ptr = cast(typeof(return))malloc(newCapacity * E.sizeof); } 1379 assert(ptr, "Allocation failed"); 1380 } 1381 static if (shouldAddGCRange!E) 1382 { 1383 gc_addRange(ptr, newCapacity * E.sizeof); 1384 } 1385 return ptr; 1386 } 1387 1388 @nogc: 1389 1390 /// Check if empty. 1391 bool empty() const { return this.length == 0; } 1392 1393 /// Get length. 1394 size_t length() 1395 const @trusted 1396 { 1397 if (isLarge) 1398 { 1399 return _large.length; 1400 } 1401 else 1402 { 1403 return _small.length; 1404 } 1405 } 1406 alias opDollar = length; /// ditto 1407 1408 /// Decrease only length. 1409 private void decOnlyLength() 1410 @trusted 1411 { 1412 if (isLarge) 1413 { 1414 assert(_large.length); 1415 _large.length = _large.length - 1; 1416 } 1417 else 1418 { 1419 assert(_small.length); 1420 _small.length = cast(SmallLengthType)(_small.length - 1); 1421 } 1422 } 1423 1424 /// Set only length. 1425 private void setOnlyLength(size_t newLength) 1426 @trusted 1427 { 1428 if (isLarge) 1429 { 1430 _large.length = newLength; // TODO compress? 1431 } 1432 else 1433 { 1434 assert(newLength <= SmallLengthType.max); 1435 _small.length = cast(SmallLengthType)newLength; 1436 } 1437 } 1438 1439 /// Get reserved capacity of store. 1440 size_t capacity() 1441 const 1442 @trusted 1443 { 1444 if (isLarge) 1445 { 1446 return _large.capacity; 1447 } 1448 else 1449 { 1450 return smallCapacity; 1451 } 1452 } 1453 1454 /** Shrink length to `newLength`. 1455 * 1456 * If `newLength` >= `length` operation has no effect. 1457 */ 1458 pragma(inline) 1459 void shrinkTo(size_t newLength) 1460 { 1461 assert(!isBorrowed); 1462 if (newLength < length) 1463 { 1464 static if (hasElaborateDestructor!E) 1465 { 1466 dbg(length, " => ", newLength, " ", E.stringof); 1467 foreach (immutable i; newLength .. length) 1468 { 1469 .destroy(_mptr[i]); 1470 } 1471 } 1472 setOnlyLength(newLength); 1473 } 1474 } 1475 1476 /// Get internal pointer. 1477 inout(E*) ptr() 1478 inout 1479 @trusted return scope // array access is @trusted 1480 { 1481 // TODO Use cast(ET[])?: alias ET = ContainerElementType!(typeof(this), E); 1482 if (isLarge) 1483 { 1484 return _large.ptr; 1485 } 1486 else 1487 { 1488 return _small.elms.ptr; 1489 } 1490 } 1491 1492 /// Get internal pointer to mutable content. Doesn't need to be qualified with `scope`. 1493 private MutableE* _mptr() 1494 const return scope 1495 { 1496 if (isLarge) 1497 { 1498 return _large._mptr; 1499 } 1500 else 1501 { 1502 return _small._mptr; 1503 } 1504 } 1505 1506 /// Get internal slice. 1507 private auto slice() inout 1508 @trusted return scope 1509 { 1510 return ptr[0 .. this.length]; 1511 } 1512 1513 /** Magic pointer value used to detect double calls to `free`. 1514 1515 Cannot conflict with return value from `malloc` because the least 1516 significant bit is set (when the value ends with a one). 1517 */ 1518 debug private enum _ptrMagic = cast(E*)0x0C6F3C6c0f3a8471; 1519 1520 /// Returns: `true` if `this` currently uses large array storage. 1521 bool isLarge() 1522 const @trusted // trusted access to anonymous union 1523 { 1524 assert(_large.isLarge == _small.isLarge); // must always be same 1525 return _large.isLarge; 1526 } 1527 1528 /// Returns: `true` if `this` currently uses small (packed) array storage. 1529 bool isSmall() const { return !isLarge; } 1530 1531 private 1532 { 1533 private alias SmallLengthType = ubyte; 1534 1535 private enum largeSmallLengthDifference = Large.sizeof - SmallLengthType.sizeof; 1536 private enum smallCapacity = largeSmallLengthDifference / E.sizeof; 1537 private enum smallPadSize = largeSmallLengthDifference - smallCapacity*E.sizeof; 1538 } 1539 1540 /** Tag `this` borrowed. 1541 Used by wrapper logic in owned.d and borrowed.d 1542 */ 1543 void tagAsBorrowed() 1544 @trusted 1545 { 1546 if (isLarge) { _large.isBorrowed = true; } 1547 else { _small.isBorrowed = true; } 1548 } 1549 1550 /** Tag `this` as not borrowed. 1551 Used by wrapper logic in owned.d and borrowed.d 1552 */ 1553 void untagAsNotBorrowed() 1554 @trusted 1555 { 1556 if (isLarge) { _large.isBorrowed = false; } 1557 else { _small.isBorrowed = false; } 1558 } 1559 1560 /// Returns: `true` if this is borrowed 1561 bool isBorrowed() 1562 @trusted 1563 { 1564 if (isLarge) { return _large.isBorrowed; } 1565 else { return _small.isBorrowed; } 1566 } 1567 1568 private: // data 1569 enum useAlignedTaggedPointer = false; // TODO make this work when true 1570 static struct Large 1571 { 1572 static if (useAlignedTaggedPointer) 1573 { 1574 private enum lengthMax = CapacityType.max; 1575 version(LittleEndian) // see: http://forum.dlang.org/posting/zifyahfohbwavwkwbgmw 1576 { 1577 import std.bitmanip : taggedPointer; 1578 mixin(taggedPointer!(uint*, "_uintptr", // GC-allocated store pointer. See_Also: http://forum.dlang.org/post/iubialncuhahhxsfvbbg@forum.dlang.org 1579 bool, "isLarge", 1, // bit 0 1580 bool, "isBorrowed", 1, // bit 1 1581 )); 1582 1583 pragma(inline, true): 1584 @property void ptr(E* c) 1585 { 1586 assert((cast(ulong)c & 0b11) == 0); 1587 _uintptr = cast(uint*)c; 1588 } 1589 1590 @property inout(E)* ptr() inout 1591 { 1592 return cast(E*)_uintptr; 1593 } 1594 1595 CapacityType capacity; // store capacity 1596 CapacityType length; // store length 1597 } 1598 else 1599 { 1600 static assert(0, "BigEndian support and test"); 1601 } 1602 } 1603 else 1604 { 1605 private enum lengthBits = 8*CapacityType.sizeof - 2; 1606 private enum lengthMax = 2^^lengthBits - 1; 1607 1608 static if (useGCAllocation) 1609 { 1610 E* ptr; // GC-allocated store pointer. See_Also: http://forum.dlang.org/post/iubialncuhahhxsfvbbg@forum.dlang.org 1611 } 1612 else 1613 { 1614 @nogc E* ptr; // non-GC-allocated store pointer 1615 } 1616 1617 CapacityType capacity; // store capacity 1618 1619 import std.bitmanip : bitfields; // TODO replace with own logic cause this mixin costs compilation speed 1620 mixin(bitfields!(CapacityType, "length", lengthBits, 1621 bool, "isBorrowed", 1, 1622 bool, "isLarge", 1, 1623 )); 1624 } 1625 1626 pragma(inline) 1627 this(size_t initialCapacity, size_t initialLength, bool zero) 1628 { 1629 assert(initialCapacity <= lengthMax); 1630 assert(initialLength <= lengthMax); 1631 1632 setCapacity(initialCapacity); 1633 this.capacity = cast(CapacityType)initialCapacity; 1634 this.ptr = allocate(initialCapacity, zero); 1635 this.length = initialLength; 1636 this.isLarge = true; 1637 this.isBorrowed = false; 1638 } 1639 1640 pragma(inline, true): 1641 1642 void setCapacity(size_t newCapacity) 1643 { 1644 assert(newCapacity <= capacity.max); 1645 capacity = cast(CapacityType)newCapacity; 1646 } 1647 1648 MutableE* _mptr() const 1649 @trusted 1650 { 1651 return cast(typeof(return))ptr; 1652 } 1653 } 1654 1655 /// Small string storage. 1656 static struct Small 1657 { 1658 enum capacity = smallCapacity; 1659 private enum lengthBits = 8*SmallLengthType.sizeof - 2; 1660 private enum lengthMax = 2^^lengthBits - 1; 1661 1662 import std.bitmanip : bitfields; // TODO replace with own logic cause this mixin costs compilation speed 1663 static if (useAlignedTaggedPointer) 1664 { 1665 mixin(bitfields!(bool, "isLarge", 1, // defaults to false 1666 bool, "isBorrowed", 1, // default to false 1667 SmallLengthType, "length", lengthBits, 1668 )); 1669 static if (smallPadSize) { ubyte[smallPadSize] _ignoredPadding; } 1670 E[capacity] elms; 1671 } 1672 else 1673 { 1674 E[capacity] elms; 1675 static if (smallPadSize) { ubyte[smallPadSize] _ignoredPadding; } 1676 mixin(bitfields!(SmallLengthType, "length", lengthBits, 1677 bool, "isBorrowed", 1, // default to false 1678 bool, "isLarge", 1, // defaults to false 1679 )); 1680 } 1681 1682 pragma(inline) 1683 this(size_t initialLength, bool zero) 1684 { 1685 assert(initialLength <= lengthMax); 1686 1687 this.length = cast(SmallLengthType)initialLength; 1688 this.isLarge = false; 1689 this.isBorrowed = false; 1690 if (zero) 1691 { 1692 elms[] = E.init; 1693 } 1694 } 1695 1696 pragma(inline, true) 1697 MutableE* _mptr() const 1698 @trusted 1699 { 1700 return cast(typeof(return))(elms.ptr); 1701 } 1702 } 1703 1704 static assert(Large.sizeof == 1705 Small.sizeof); 1706 1707 static if (E.sizeof == 1 && 1708 size_t.sizeof == 8 && // 64-bit 1709 Small.capacity == 23) 1710 { 1711 static assert(Large.sizeof == 24); 1712 static assert(Small.sizeof == 24); 1713 } 1714 1715 union 1716 { 1717 Large _large; // indirected storage 1718 Small _small; // non-indirected storage 1719 } 1720 } 1721 1722 import std.traits : hasMember, isDynamicArray; 1723 1724 /** Return an instance of `R` with capacity `capacity`. */ 1725 R withCapacityMake(R)(size_t capacity) 1726 if (hasMember!(R, "withCapacity")) 1727 { 1728 return R.withCapacity(capacity); 1729 } 1730 /// ditto 1731 R withCapacityMake(R)(size_t capacity) 1732 if (isDynamicArray!R) 1733 { 1734 R r; 1735 // See http://forum.dlang.org/post/nupffaitocqjlamffuqi@forum.dlang.org 1736 r.reserve(capacity); 1737 return r; 1738 } 1739 1740 @safe pure nothrow unittest 1741 { 1742 immutable capacity = 10; 1743 auto x = capacity.withCapacityMake!(int[]); 1744 assert(x.capacity >= capacity); 1745 } 1746 1747 /** Return an instance of `R` of length `length`. */ 1748 R withLengthMake(R)(size_t length) 1749 if (hasMember!(R, "withLength")) 1750 { 1751 return R.withLength(length); 1752 } 1753 /// ditto 1754 R withLengthMake(R)(size_t length) 1755 if (isDynamicArray!R) 1756 { 1757 R r; 1758 r.length = length; 1759 return r; 1760 } 1761 1762 /** Return an instance of `R` containing a single element `e`. */ 1763 R withElementMake(R)(typeof(R.init[0]) e) 1764 if (hasMember!(R, "withElement")) 1765 { 1766 return R.withElement(e); 1767 } 1768 /// ditto 1769 R withElementMake(R)(typeof(R.init[0]) e) 1770 if (isDynamicArray!R) 1771 { 1772 return [e]; 1773 } 1774 1775 alias UniqueArray(E, bool useGCAllocation = false) = Array!(E, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1776 alias CopyingArray(E, bool useGCAllocation = false) = Array!(E, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1777 1778 alias SortedCopyingArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.copy, Ordering.sortedValues, useGCAllocation, size_t, less); 1779 alias SortedSetCopyingArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.copy, Ordering.sortedUniqueSet, useGCAllocation, size_t, less); 1780 1781 alias SortedUniqueArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.disabled, Ordering.sortedValues, useGCAllocation, size_t, less); 1782 alias SortedSetUniqueArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.disabled, Ordering.sortedUniqueSet, useGCAllocation, size_t, less); 1783 1784 // string aliases 1785 alias UniqueString(bool useGCAllocation = false) = Array!(char, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1786 alias CopyingString(bool useGCAllocation = false) = Array!(char, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1787 alias UniqueWString(bool useGCAllocation = false) = Array!(wchar, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1788 alias CopyingWString(bool useGCAllocation = false) = Array!(wchar, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1789 alias UniqueDString(bool useGCAllocation = false) = Array!(dchar, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1790 alias CopyingDString(bool useGCAllocation = false) = Array!(dchar, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1791 1792 @safe pure unittest 1793 { 1794 auto c = UniqueString!false(); 1795 auto w = UniqueWString!false(); 1796 auto d = UniqueDString!false(); 1797 } 1798 1799 @safe pure unittest 1800 { 1801 auto c = CopyingString!false(); 1802 auto w = CopyingWString!false(); 1803 auto d = CopyingDString!false(); 1804 } 1805 1806 @safe pure unittest 1807 { 1808 import std.conv : to; 1809 foreach (assignment; AliasSeq!(Assignment.disabled, Assignment.copy)) 1810 { 1811 foreach (Ch; AliasSeq!(char, wchar, dchar)) 1812 { 1813 alias Str = Array!(Ch, assignment); 1814 Str str_as = Str.withElement('a'); 1815 Str str_as2 = 'a'.withElementMake!Str; 1816 Str str_as3 = 'a'.withElementMake!(Ch[]); 1817 assert(str_as == str_as2); 1818 assert(str_as2 == str_as3); 1819 str_as ~= Ch('_'); 1820 assert(str_as[].equal("a_")); 1821 } 1822 } 1823 } 1824 1825 static void tester(Ordering ordering, bool supportGC, alias less)() 1826 { 1827 import std.functional : binaryFun; 1828 import std.range : iota, chain, repeat, only, ElementType; 1829 import std.algorithm : filter, map; 1830 import std.algorithm.sorting : isSorted, sort; 1831 import std.exception : assertThrown, assertNotThrown; 1832 import std.traits : isInstanceOf; 1833 import core.internal.traits : Unqual; 1834 1835 enum assignment = Assignment.copy; 1836 alias comp = binaryFun!less; //< comparison 1837 1838 alias E = int; 1839 1840 { 1841 alias A = SortedUniqueArray!E; 1842 auto x = A.withElements(0, 3, 2, 1); 1843 assert(x[].equal([0, 1, 2, 3].s[])); 1844 } 1845 1846 foreach (Ch; AliasSeq!(char, wchar, dchar)) 1847 { 1848 static if (!isOrdered!ordering || // either not ordered 1849 is(Ch == dchar)) // or not a not a narrow string 1850 { 1851 alias Str = Array!(Ch, assignment, ordering, supportGC, size_t, less); 1852 auto y = Str.withElements('a', 'b', 'c'); 1853 static assert(is(Unqual!(ElementType!Str) == Ch)); 1854 y = Str.init; 1855 1856 const(Ch)[] xs; 1857 { 1858 // immutable 1859 immutable x = Str.withElements('a', 'b', 'c'); 1860 static if (!isOrdered!ordering) 1861 { 1862 xs = x[]; // TODO should fail with DIP-1000 scope 1863 } 1864 } 1865 } 1866 } 1867 1868 foreach (Ch; AliasSeq!(char)) 1869 { 1870 static if (!isOrdered!ordering) 1871 { 1872 alias Str = Array!(Ch, assignment, ordering, supportGC, size_t, less); 1873 auto str = Str.withElements('a', 'b', 'c'); 1874 1875 static if (isOrdered!ordering) 1876 { 1877 static assert(is(Unqual!(ElementType!Str) == Ch)); 1878 } 1879 else 1880 { 1881 static assert(is(ElementType!Str == Ch)); 1882 assert(str[] == `abc`); // TODO this fails for wchar and dchar 1883 } 1884 } 1885 } 1886 1887 { 1888 alias A = Array!(int, assignment, ordering, supportGC, size_t, less); 1889 foreach (immutable n; [0, 1, 2, 3, 4, 5]) 1890 { 1891 assert(A.withLength(n).isSmall); 1892 } 1893 assert(!(A.withLength(6).isSmall)); 1894 assert((A.withLength(6).isLarge)); 1895 } 1896 1897 // test move construction 1898 { 1899 immutable maxLength = 1024; 1900 foreach (immutable n; 0 .. maxLength) 1901 { 1902 auto x = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(n); 1903 1904 // test resize 1905 static if (!isOrdered!ordering) 1906 { 1907 assert(x.length == n); 1908 x.length = n + 1; 1909 assert(x.length == n + 1); 1910 x.length = n; 1911 } 1912 1913 const ptr = x.ptr; 1914 immutable capacity = x.capacity; 1915 assert(x.length == n); 1916 1917 import std.algorithm.mutation : move; 1918 auto y = Array!(E, assignment, ordering, supportGC, size_t, less)(); 1919 move(x, y); 1920 1921 assert(x.length == 0); 1922 assert(x.capacity == x.smallCapacity); 1923 1924 assert(y.length == n); 1925 assert(y.capacity == capacity); 1926 } 1927 } 1928 1929 foreach (immutable n; chain(0.only, iota(0, 10).map!(x => 2^^x))) 1930 { 1931 import std.array : array; 1932 import std.range : radial; 1933 1934 immutable zi = cast(int)0; // zero index 1935 immutable ni = cast(int)n; // number index 1936 1937 auto fw = iota(zi, ni); // 0, 1, 2, ..., n-1 1938 1939 auto bw = fw.array.radial; 1940 1941 Array!(E, assignment, ordering, supportGC, size_t, less) ss0 = bw; // reversed 1942 static assert(is(Unqual!(ElementType!(typeof(ss0))) == E)); 1943 static assert(isInstanceOf!(Array, typeof(ss0))); 1944 assert(ss0.length == n); 1945 1946 static if (isOrdered!ordering) 1947 { 1948 if (!ss0.empty) { assert(ss0[0] == ss0[0]); } // trigger use of opindex 1949 assert(ss0[].equal(fw.array 1950 .sort!comp)); 1951 assert(ss0[].isSorted!comp); 1952 } 1953 1954 Array!(E, assignment, ordering, supportGC, size_t, less) ss1 = fw; // ordinary 1955 assert(ss1.length == n); 1956 1957 static if (isOrdered!ordering) 1958 { 1959 assert(ss1[].equal(fw.array 1960 .sort!comp)); 1961 assert(ss1[].isSorted!comp); 1962 } 1963 1964 Array!(E, assignment, ordering, supportGC, size_t, less) ss2 = fw.filter!(x => x & 1); 1965 assert(ss2.length == n/2); 1966 1967 static if (isOrdered!ordering) 1968 { 1969 assert(ss2[].equal(fw.filter!(x => x & 1) 1970 .array 1971 .sort!comp)); 1972 assert(ss2[].isSorted!comp); 1973 } 1974 1975 auto ssA = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 1976 static if (isOrdered!ordering) 1977 { 1978 static if (less == "a < b") 1979 { 1980 alias A = Array!(E, assignment, ordering, supportGC, size_t, less); 1981 const A x = [1, 2, 3, 4, 5, 6]; 1982 assert(x.front == 1); 1983 assert(x.back == 6); 1984 assert(x.lowerBound(3).equal([1, 2].s[])); 1985 assert(x.upperBound(3).equal([4, 5, 6].s[])); 1986 assert(x[].equal(x[])); // already sorted 1987 } 1988 1989 foreach (i; bw) 1990 { 1991 static if (ordering == Ordering.sortedUniqueSet) 1992 { 1993 assert(ssA.insertMany(i)[].equal([true].s[])); 1994 assert(ssA.insertMany(i)[].equal([false].s[])); 1995 } 1996 else 1997 { 1998 ssA.insertMany(i); 1999 } 2000 } 2001 assert(ssA[].equal(sort!comp(fw.array))); 2002 2003 auto ssB = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2004 static if (ordering == Ordering.sortedUniqueSet) 2005 { 2006 assert(ssB.insertMany(1, 7, 4, 9)[].equal(true.repeat(4))); 2007 assert(ssB.insertMany(3, 6, 8, 5, 1, 9)[].equal([true, true, true, true, false, false].s[])); 2008 assert(ssB.insertMany(3, 0, 2, 10, 11, 5)[].equal([false, true, true, true, true, false].s[])); 2009 assert(ssB.insertMany(0, 2, 10, 11)[].equal(false.repeat(4))); // false becuse already inserted 2010 assert(ssB.capacity == 16); 2011 } 2012 else 2013 { 2014 ssB.insertMany(1, 7, 4, 9); 2015 ssB.insertMany(3, 6, 8, 5); 2016 ssB.insertMany(0, 2, 10, 11); 2017 assert(ssB.capacity == 16); 2018 } 2019 2020 auto ssI = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].sort!comp; // values 2021 immutable ssO = [12, 13]; // values not range 2022 2023 assert(ssB[].equal(ssI)); 2024 2025 foreach (s; ssI) { assert(ssB.contains(s)); } 2026 foreach (s; ssO) { assert(!ssB.contains(s)); } 2027 2028 ssB.compress(); 2029 assert(ssB.capacity == 12); 2030 } 2031 else 2032 { 2033 { 2034 alias A = Array!(E, assignment, ordering, supportGC); 2035 A x = [1, 2, 3]; 2036 x ~= x; 2037 assert(x[].equal([1, 2, 3, 2038 1, 2, 3].s[])); 2039 x ~= x[]; 2040 assert(x[].equal([1, 2, 3, 1, 2, 3, 2041 1, 2, 3, 1, 2, 3].s[])); 2042 } 2043 2044 ssA ~= 3; 2045 ssA ~= 2; 2046 ssA ~= 1; 2047 assert(ssA[].equal([3, 2, 1].s[])); 2048 2049 ssA.compress(); 2050 2051 // popBack 2052 ssA[0] = 1; 2053 ssA[1] = 2; 2054 assert(ssA[].equal([1, 2, 1].s[])); 2055 assert(!ssA.empty); 2056 assert(ssA.front == 1); 2057 assert(ssA.back == 1); 2058 2059 assertNotThrown(ssA.popBack()); 2060 assert(ssA[].equal([1, 2].s[])); 2061 assert(!ssA.empty); 2062 assert(ssA.front == 1); 2063 assert(ssA.back == 2); 2064 2065 assertNotThrown(ssA.popBack()); 2066 assert(ssA[].equal([1].s[])); 2067 assert(!ssA.empty); 2068 assert(ssA.front == 1); 2069 assert(ssA.back == 1); 2070 2071 assertNotThrown(ssA.popBack()); 2072 assert(ssA.length == 0); 2073 assert(ssA.empty); 2074 assert(ssA.capacity != 0); 2075 2076 ssA.compress(); 2077 assert(ssA.length == 0); 2078 assert(ssA.empty); 2079 2080 // insertAt 2081 ssA ~= 1; 2082 ssA ~= 2; 2083 ssA ~= 3; 2084 ssA ~= 4; 2085 ssA ~= 5; 2086 ssA ~= 6; 2087 ssA ~= 7; 2088 ssA ~= 8; 2089 assert(ssA[].equal([1, 2, 3, 4, 5, 6, 7, 8].s[])); 2090 ssA.insertAtIndex(3, 100, 101); 2091 assert(ssA[].equal([1, 2, 3, 100, 101, 4, 5, 6, 7, 8].s[])); 2092 assertNotThrown(ssA.popFront()); 2093 assert(ssA[].equal([2, 3, 100, 101, 4, 5, 6, 7, 8].s[])); 2094 assertNotThrown(ssA.popFront()); 2095 assert(ssA[].equal([3, 100, 101, 4, 5, 6, 7, 8].s[])); 2096 assertNotThrown(ssA.popFront()); 2097 assert(ssA[].equal([100, 101, 4, 5, 6, 7, 8].s[])); 2098 assertNotThrown(ssA.popFront()); 2099 assertNotThrown(ssA.popFront()); 2100 assertNotThrown(ssA.popFront()); 2101 assertNotThrown(ssA.popFront()); 2102 assertNotThrown(ssA.popFront()); 2103 assertNotThrown(ssA.popFront()); 2104 assertNotThrown(ssA.popFront()); 2105 assert(ssA.empty); 2106 ssA.compress(); 2107 2108 // removeAt 2109 ssA ~= 1; 2110 ssA ~= 2; 2111 ssA ~= 3; 2112 ssA ~= 4; 2113 ssA ~= 5; 2114 assertNotThrown(ssA.removeAt(2)); 2115 assert(ssA[].equal([1, 2, 4, 5].s[])); 2116 2117 // insertBack and assignment from slice 2118 auto ssB = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2119 ssB.insertBack([1, 2, 3, 4, 5].s[]); 2120 ssB.insertBack([6, 7]); 2121 assert(ssB[].equal([1, 2, 3, 4, 5, 6, 7].s[])); 2122 assert(ssB.backPop() == 7); 2123 assert(ssB.backPop() == 6); 2124 assert(ssB.backPop() == 5); 2125 assert(ssB.backPop() == 4); 2126 assert(ssB.backPop() == 3); 2127 assert(ssB.backPop() == 2); 2128 assert(ssB.backPop() == 1); 2129 assert(ssB.empty); 2130 2131 // insertBack(Array) 2132 { 2133 immutable s = [1, 2, 3]; 2134 Array!(E, assignment, ordering, supportGC, size_t, less) s1 = s; 2135 Array!(E, assignment, ordering, supportGC, size_t, less) s2 = s1[]; 2136 assert(s1[].equal(s)); 2137 s1 ~= s1; 2138 assert(s1[].equal(chain(s, s))); 2139 s1 ~= s2; 2140 assert(s1[].equal(chain(s, s, s))); 2141 } 2142 2143 // immutable ss_ = Array!(E, assignment, ordering, supportGC, size_t, less)(null); 2144 // assert(ss_.empty); 2145 2146 auto ssC = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2147 immutable int[5] i5_ = [1, 2, 3, 4, 5]; 2148 immutable(int)[] i5 = i5_[]; 2149 ssC.insertBack(i5); 2150 assert(i5 == [1, 2, 3, 4, 5].s[]); 2151 assert(ssC[].equal(i5)); 2152 2153 auto ssCc = ssC; // copy it 2154 assert(ssCc[].equal(i5)); 2155 2156 ssC.shrinkTo(4); 2157 assert(ssC[].equal([1, 2, 3, 4].s[])); 2158 2159 ssC.shrinkTo(3); 2160 assert(ssC[].equal([1, 2, 3].s[])); 2161 2162 ssC.shrinkTo(2); 2163 assert(ssC[].equal([1, 2].s[])); 2164 2165 ssC.shrinkTo(1); 2166 assert(ssC[].equal([1].s[])); 2167 2168 ssC.shrinkTo(0); 2169 assert(ssC[].length == 0); 2170 assert(ssC.empty); 2171 2172 ssC.insertBack(i5); 2173 ssC.popBackN(3); 2174 assert(ssC[].equal([1, 2].s[])); 2175 2176 auto ssD = ssC; 2177 ssC.clear(); 2178 assert(ssC.empty); 2179 2180 assert(!ssD.empty); 2181 ssD = null; 2182 assert(ssD.empty); 2183 assert(ssD == typeof(ssD).init); 2184 2185 assert(ssCc[].equal(i5)); 2186 2187 ssCc = ssCc; // self assignment 2188 } 2189 } 2190 } 2191 2192 /// disabled copying 2193 @safe pure nothrow @nogc unittest 2194 { 2195 alias E = ubyte; 2196 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2197 A a; 2198 immutable n = ubyte.max; 2199 size_t i = 0; 2200 foreach (ubyte e; 0 .. n) 2201 { 2202 a ~= e; 2203 // assert(a.back == e.to!E); 2204 assert(a.length == i + 1); 2205 ++i; 2206 } 2207 const b = a.dup; 2208 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2209 assert(b.length == a.length); 2210 assert(a !is b); 2211 assert(a == b); 2212 } 2213 2214 /// disabled copying 2215 @safe pure nothrow unittest 2216 { 2217 alias E = string; 2218 2219 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2220 A a; 2221 immutable n = 100_000; 2222 size_t i = 0; 2223 foreach (const ref e; 0 .. n) 2224 { 2225 a ~= e.to!E; 2226 // assert(a.back == e.to!E); 2227 assert(a.length == i + 1); 2228 ++i; 2229 } 2230 const b = a.dup; 2231 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2232 assert(b.length == a.length); 2233 assert(a !is b); 2234 assert(a == b); 2235 } 2236 2237 /// disabled copying 2238 @safe pure nothrow unittest 2239 { 2240 alias E = string; 2241 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2242 A a; 2243 immutable n = 100_000; 2244 size_t i = 0; 2245 foreach (const ref e; 0 .. n) 2246 { 2247 a ~= e.to!E; 2248 assert(a.length == i + 1); 2249 ++i; 2250 } 2251 const b = a.dup; 2252 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2253 assert(a[] == b[]); 2254 } 2255 2256 /// disabled copying 2257 @safe pure nothrow @nogc unittest 2258 { 2259 import std.traits : isAssignable; 2260 2261 alias E = string; 2262 2263 alias A = Array!E; 2264 static assert(!__traits(isCopyable, A)); 2265 2266 alias CA = CopyingArray!E; 2267 static assert(__traits(isCopyable, CA)); 2268 2269 // import std.traits : isRvalueAssignable, isLvalueAssignable; 2270 // static assert(isRvalueAssignable!(A)); 2271 // static assert(isLvalueAssignable!(A)); 2272 2273 static assert(isAssignable!(A)); 2274 2275 // import std.range.primitives : hasSlicing; 2276 // TODO make this evaluate to `true` 2277 // static assert(hasSlicing!A); 2278 2279 alias AA = Array!A; 2280 2281 AA aa; 2282 A a; 2283 a ~= "string"; 2284 aa ~= A.init; 2285 2286 assert(aa == aa); 2287 assert(AA.withLength(3) == AA.withLength(3)); 2288 assert(AA.withCapacity(3) == AA.withCapacity(3)); 2289 assert(AA.withLength(3).length == 3); 2290 assert(aa != AA.init); 2291 } 2292 2293 /// 2294 @safe pure nothrow @nogc unittest 2295 { 2296 alias E = int; 2297 alias A = Array!E; 2298 A a; 2299 import std.range : iota; 2300 import std.container.util : make; 2301 foreach (n; 0 .. 100) 2302 { 2303 const e = iota(0, n).make!Array; 2304 assert(e[].equal(iota(0, n))); 2305 } 2306 } 2307 2308 version(unittest) 2309 { 2310 import std.traits : EnumMembers; 2311 } 2312 2313 /// use GC 2314 pure nothrow unittest 2315 { 2316 foreach (ordering; EnumMembers!Ordering) 2317 { 2318 tester!(ordering, true, "a < b"); // use GC 2319 tester!(ordering, true, "a > b"); // use GC 2320 } 2321 } 2322 2323 /// don't use GC 2324 pure nothrow /+TODO @nogc+/ unittest 2325 { 2326 foreach (ordering; EnumMembers!Ordering) 2327 { 2328 tester!(ordering, false, "a < b"); // don't use GC 2329 tester!(ordering, false, "a > b"); // don't use GC 2330 } 2331 } 2332 2333 @safe pure nothrow unittest 2334 { 2335 alias E = int; 2336 alias A = Array!E; 2337 A[string] map; 2338 map["a"] = A.init; 2339 map["B"] = A.withLength(42); 2340 2341 auto aPtr = "a" in map; 2342 assert(aPtr); 2343 assert(A.init == *aPtr); 2344 assert(*aPtr == A.init); 2345 2346 assert("z" !in map); 2347 auto zPtr = "z" in map; 2348 assert(!zPtr); 2349 } 2350 2351 /// test withElement and withElements 2352 @safe pure nothrow @nogc unittest 2353 { 2354 import std.algorithm.mutation : move; 2355 import std.range.primitives : ElementType; 2356 2357 alias A = Array!int; 2358 alias AA = Array!A; 2359 alias AAA = Array!AA; 2360 2361 foreach (A_; AliasSeq!(A, AA, AAA)) 2362 { 2363 alias E = ElementType!A_; 2364 A_ x = A_.withElement(E.init); 2365 A_ y = A_.withElements(E.init, E.init); 2366 assert(x.length == 1); 2367 assert(y.length == 2); 2368 immutable n = 100; 2369 foreach (_; 0 .. n) 2370 { 2371 auto e = E.init; 2372 x ~= move(e); 2373 y ~= E.init; 2374 } 2375 foreach (_; 0 .. n) 2376 { 2377 assert(x.backPop() == E.init); 2378 assert(y.backPop() == E.init); 2379 } 2380 assert(x.length == 1); 2381 assert(y.length == 2); 2382 2383 import std.algorithm : swap; 2384 swap(x, y); 2385 assert(x.length == 2); 2386 assert(y.length == 1); 2387 2388 swap(x[0], y[0]); 2389 } 2390 2391 } 2392 2393 /// assert same behaviour of `dup` as for builtin arrays 2394 @safe pure nothrow unittest 2395 { 2396 struct Vec { int x, y; } 2397 class Db { int* _ptr; } 2398 struct Node { int x; class Db; } 2399 // struct Node1 { const(int) x; class Db; } 2400 foreach (E; AliasSeq!(int, const(int), Vec, Node// , Node1 2401 )) 2402 { 2403 alias DA = E[]; // builtin D array/slice 2404 immutable DA da = [E.init]; // construct from array 2405 auto daCopy = da.dup; // duplicate 2406 daCopy[] = E.init; // opSliceAssign 2407 2408 alias CA = Array!E; // container array 2409 immutable ca = CA.withElement(E.init); 2410 2411 auto caCopy = ca.dup; 2412 2413 import std.traits : hasIndirections; 2414 static if (!hasIndirections!E) 2415 { 2416 const(E)[2] x = [E.init, E.init]; 2417 // TODO caCopy ~= E.init; 2418 caCopy ~= x[]; 2419 assert(caCopy.length == 3); 2420 assert(caCopy[1 .. $] == x[]); 2421 } 2422 2423 // should have same element type 2424 static assert(is(typeof(caCopy[0]) == 2425 typeof(daCopy[0]))); 2426 2427 } 2428 } 2429 2430 /// array as AA key type 2431 @safe pure nothrow unittest 2432 { 2433 struct E { int x, y; } 2434 foreach (A; AliasSeq!(Array!E, 2435 CopyingArray!E)) 2436 { 2437 int[A] x; 2438 immutable n = 100; 2439 foreach (immutable i; 0 .. n) 2440 { 2441 assert(x.length == i); 2442 assert(A.withElement(E(i, 2*i)) !in x); 2443 x[A.withElement(E(i, 2*i))] = 42; 2444 assert(x.length == i + 1); 2445 auto a = A.withElement(E(i, 2*i)); 2446 import std.traits : isCopyable; 2447 static if (__traits(isCopyable, A)) 2448 { 2449 // TODO why do these fail when `A` is uncopyable? 2450 assert(a in x); 2451 assert(A.withElement(E(i, 2*i)) in x); 2452 assert(x[A.withElement(E(i, 2*i))] == 42); 2453 } 2454 } 2455 } 2456 } 2457 2458 /// init and append to empty array as AA value type 2459 @safe pure nothrow unittest 2460 { 2461 alias Key = string; 2462 alias A = Array!int; 2463 2464 A[Key] x; 2465 2466 assert("a" !in x); 2467 2468 x["a"] = A.init; // if this init is removed.. 2469 x["a"] ~= 42; // ..then this fails 2470 2471 assert(x["a"] == A.withElement(42)); 2472 } 2473 2474 /// compress 2475 @safe pure nothrow @nogc unittest 2476 { 2477 alias A = Array!string; 2478 A a; 2479 2480 a.compress(); 2481 2482 a ~= "a"; 2483 a ~= "b"; 2484 a ~= "c"; 2485 2486 assert(a.length == 3); 2487 assert(a.capacity == 4); 2488 2489 a.compress(); 2490 2491 assert(a.capacity == a.length); 2492 } 2493 2494 /// 2495 @safe pure nothrow @nogc unittest 2496 { 2497 alias Key = UniqueArray!char; 2498 alias Value = UniqueArray!int; 2499 struct E 2500 { 2501 Key key; 2502 Value value; 2503 E dup() @safe pure nothrow @nogc 2504 { 2505 return E(key.dup, value.dup); 2506 } 2507 } 2508 E e; 2509 e.key = Key.withElement('a'); 2510 e.value = Value.withElement(42); 2511 2512 auto f = e.dup; 2513 assert(e == f); 2514 2515 e.key = Key.withElement('b'); 2516 assert(e != f); 2517 2518 e.key = Key.withElement('a'); 2519 assert(e == f); 2520 2521 e.value = Value.withElement(43); 2522 assert(e != f); 2523 2524 e.value = Value.withElement(42); 2525 assert(e == f); 2526 2527 } 2528 2529 /// append to empty to array as AA value type 2530 @safe pure nothrow @nogc unittest 2531 { 2532 import std.exception: assertThrown; 2533 import core.exception : RangeError; 2534 2535 alias Key = string; 2536 alias A = Array!int; 2537 2538 A[Key] x; 2539 // assertThrown!RangeError({ x["a"] ~= 42; }); // TODO make this work 2540 } 2541 2542 /// map array of uncopyable 2543 @safe pure nothrow unittest 2544 { 2545 import std.range.primitives : isInputRange; 2546 import std.array : array; 2547 2548 alias A = UniqueArray!int; 2549 auto y = A.init[].map!(_ => _^^2).array; 2550 2551 A z = y.dup; // check that dup returns same type 2552 z = A.init; 2553 const w = [0, 1].s; 2554 z.insertBack(w[]); 2555 assert(z[].equal(w[])); 2556 } 2557 2558 /// 2559 version(none) 2560 @safe pure nothrow @nogc unittest 2561 { 2562 alias A = UniqueArray!int; 2563 A x; 2564 const y = [0, 1, 2, 3].s; 2565 2566 x.insertBack(y[]); 2567 assert(x[].equal(y[])); 2568 2569 x.clear(); 2570 x.insertBack(y[].map!(_ => _^^2)); // rhs has length (`hasLength`) 2571 assert(x[].equal(y[].map!(_ => _^^2))); 2572 2573 x.clear(); 2574 x.insertBack(y[].filter!(_ => _ & 1)); // rhs has no length (`!hasLength`) 2575 assert(x[].equal(y[].filter!(_ => _ & 1))); 2576 } 2577 2578 /// collection 2579 /*@safe*/ pure nothrow @nogc unittest // TODO make @safe when collect has been made safe 2580 { 2581 import std.range : iota, isOutputRange; 2582 import nxt.algorithm_ex : collect; 2583 2584 alias E = int; 2585 alias A = Array!E; 2586 2587 immutable n = 100; 2588 static assert(isOutputRange!(A, E)); 2589 2590 assert((0.iota(n).collect!A)[].equal(0.iota(n))); 2591 } 2592 2593 /// map array of uncopyable 2594 @safe pure nothrow @nogc unittest 2595 { 2596 foreach (AT; AliasSeq!(SortedUniqueArray, 2597 SortedSetUniqueArray)) 2598 { 2599 alias A = AT!int; 2600 A a; 2601 A b = a.dup; 2602 } 2603 } 2604 2605 /// init and append to empty array as AA value type 2606 @safe pure nothrow @nogc unittest 2607 { 2608 alias A = Array!int; 2609 2610 const x = A.withElements(0, 1, 3, 0, 2, 1, 3); 2611 2612 assert(x.toSortedArray == [0, 0, 1, 1, 2, 3, 3].s[]); 2613 assert(x.toSortedSetArray == [0, 1, 2, 3].s[]); 2614 2615 assert(x.toSortedArray!"a > b" == [3, 3, 2, 1, 1, 0, 0].s[]); 2616 assert(x.toSortedSetArray!"a > b" == [3, 2, 1, 0].s[]); 2617 } 2618 2619 /** Return `data` appended with arguments `args`. 2620 2621 If `data` is an r-value it's modified and returned, otherwise a copy is made 2622 and returned. 2623 */ 2624 C append(C, Args...)(auto ref C data, 2625 auto ref Args args) 2626 if (args.length >= 1) // TODO trait: when `C` is a container supporting `insertBack` 2627 { 2628 static if (__traits(isRef, data)) // `data` is an r-value 2629 { 2630 C mutableData = data.dup; 2631 } 2632 else // `data` is an l-value 2633 { 2634 alias mutableData = data; 2635 } 2636 // TODO use `mutableData.insertBack(args);` instead 2637 foreach (ref arg; args) 2638 { 2639 mutableData.insertBack(arg); 2640 } 2641 import std.algorithm.mutation : move; 2642 return move(mutableData); 2643 } 2644 2645 /// append 2646 @safe pure nothrow @nogc unittest 2647 { 2648 alias Str = UniqueString!false; 2649 2650 assert(Str(`a`).append('b', 'c')[] == `abc`); 2651 assert(Str(`a`).append(`b`, `c`)[] == `abc`); 2652 2653 const Str x = Str(`a`).append('b', 'c'); // is moved 2654 assert(x[] == `abc`); 2655 2656 Str y = `x`; 2657 Str z = y.append('y', 'z', `w`); // needs dup 2658 assert(y.ptr != z.ptr); 2659 assert(z[] == `xyzw`); 2660 } 2661 2662 version(unittest) 2663 { 2664 private static struct SS 2665 { 2666 @disable this(this); 2667 int x; 2668 } 2669 } 2670 2671 /// uncopyable elements 2672 @safe pure nothrow @nogc unittest 2673 { 2674 alias A = UniqueArray!SS; 2675 A x; 2676 x ~= SS.init; 2677 // TODO x.insertBack(A.init); 2678 } 2679 2680 // TODO implement? 2681 // T opBinary(string op, R, Args...)(R lhs, 2682 // auto ref Args args) 2683 // { 2684 // return append(lhs, rhs); 2685 // } 2686 // @safe pure nothrow @nogc unittest 2687 // { 2688 // alias S = UniqueString!false; 2689 // // TODO 2690 // // const S x = S(`a`) ~ 'b'; 2691 // // assert(x[] == `abc`); 2692 // } 2693 2694 /// See_Also: http://forum.dlang.org/post/omfm56$28nu$1@digitalmars.com 2695 version(none) 2696 @safe pure nothrow unittest 2697 { 2698 import std.range.primitives : ElementType; 2699 import std.array : Appender; 2700 2701 struct S 2702 { 2703 string src; 2704 S[] subs; 2705 } 2706 2707 struct T 2708 { 2709 string src; 2710 Appender!(T[]) subs; 2711 } 2712 2713 static assert(is(ElementType!(S[]) == S)); 2714 static assert(is(ElementType!(T[]) == void)); // TODO forward-reference bug: should be `T` 2715 2716 S s; 2717 s.subs ~= S.init; 2718 2719 T t; 2720 // t.subs ~= T.init; 2721 // t.subs.put(T.init); 2722 2723 // struct U 2724 // { 2725 // string src; 2726 // UniqueArray!U subs; 2727 // } 2728 // U u; 2729 } 2730 2731 /// class element 2732 @safe pure nothrow unittest 2733 { 2734 class Zing 2735 { 2736 void* raw; 2737 } 2738 class Edge : Zing 2739 { 2740 Zing[] actors; 2741 } 2742 2743 foreach (AT; AliasSeq!(UniqueArray, 2744 CopyingArray, 2745 SortedCopyingArray, 2746 SortedSetCopyingArray, 2747 SortedUniqueArray, 2748 SortedSetUniqueArray)) 2749 { 2750 alias A = AT!int; 2751 A a; 2752 } 2753 }