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 /// 1741 @safe pure nothrow unittest 1742 { 1743 immutable capacity = 10; 1744 auto x = capacity.withCapacityMake!(int[]); 1745 assert(x.capacity >= capacity); 1746 } 1747 1748 /** Return an instance of `R` of length `length`. */ 1749 R withLengthMake(R)(size_t length) 1750 if (hasMember!(R, "withLength")) 1751 { 1752 return R.withLength(length); 1753 } 1754 /// ditto 1755 R withLengthMake(R)(size_t length) 1756 if (isDynamicArray!R) 1757 { 1758 R r; 1759 r.length = length; 1760 return r; 1761 } 1762 1763 /** Return an instance of `R` containing a single element `e`. */ 1764 R withElementMake(R)(typeof(R.init[0]) e) 1765 if (hasMember!(R, "withElement")) 1766 { 1767 return R.withElement(e); 1768 } 1769 /// ditto 1770 R withElementMake(R)(typeof(R.init[0]) e) 1771 if (isDynamicArray!R) 1772 { 1773 return [e]; 1774 } 1775 1776 alias UniqueArray(E, bool useGCAllocation = false) = Array!(E, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1777 alias CopyingArray(E, bool useGCAllocation = false) = Array!(E, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1778 1779 alias SortedCopyingArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.copy, Ordering.sortedValues, useGCAllocation, size_t, less); 1780 alias SortedSetCopyingArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.copy, Ordering.sortedUniqueSet, useGCAllocation, size_t, less); 1781 1782 alias SortedUniqueArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.disabled, Ordering.sortedValues, useGCAllocation, size_t, less); 1783 alias SortedSetUniqueArray(E, bool useGCAllocation = false, alias less = "a < b") = Array!(E, Assignment.disabled, Ordering.sortedUniqueSet, useGCAllocation, size_t, less); 1784 1785 // string aliases 1786 alias UniqueString(bool useGCAllocation = false) = Array!(char, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1787 alias CopyingString(bool useGCAllocation = false) = Array!(char, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1788 alias UniqueWString(bool useGCAllocation = false) = Array!(wchar, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1789 alias CopyingWString(bool useGCAllocation = false) = Array!(wchar, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1790 alias UniqueDString(bool useGCAllocation = false) = Array!(dchar, Assignment.disabled, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1791 alias CopyingDString(bool useGCAllocation = false) = Array!(dchar, Assignment.copy, Ordering.unsorted, useGCAllocation, size_t, "a < b"); 1792 1793 /// 1794 @safe pure unittest 1795 { 1796 auto c = UniqueString!false(); 1797 auto w = UniqueWString!false(); 1798 auto d = UniqueDString!false(); 1799 } 1800 1801 /// 1802 @safe pure unittest 1803 { 1804 auto c = CopyingString!false(); 1805 auto w = CopyingWString!false(); 1806 auto d = CopyingDString!false(); 1807 } 1808 1809 /// 1810 @safe pure unittest 1811 { 1812 import std.conv : to; 1813 foreach (assignment; AliasSeq!(Assignment.disabled, Assignment.copy)) 1814 { 1815 foreach (Ch; AliasSeq!(char, wchar, dchar)) 1816 { 1817 alias Str = Array!(Ch, assignment); 1818 Str str_as = Str.withElement('a'); 1819 Str str_as2 = 'a'.withElementMake!Str; 1820 Str str_as3 = 'a'.withElementMake!(Ch[]); 1821 assert(str_as == str_as2); 1822 assert(str_as2 == str_as3); 1823 str_as ~= Ch('_'); 1824 assert(str_as[].equal("a_")); 1825 } 1826 } 1827 } 1828 1829 static void tester(Ordering ordering, bool supportGC, alias less)() 1830 { 1831 import std.functional : binaryFun; 1832 import std.range : iota, chain, repeat, only, ElementType; 1833 import std.algorithm : filter, map; 1834 import std.algorithm.sorting : isSorted, sort; 1835 import std.exception : assertThrown, assertNotThrown; 1836 import std.traits : isInstanceOf; 1837 import core.internal.traits : Unqual; 1838 1839 enum assignment = Assignment.copy; 1840 alias comp = binaryFun!less; //< comparison 1841 1842 alias E = int; 1843 1844 { 1845 alias A = SortedUniqueArray!E; 1846 auto x = A.withElements(0, 3, 2, 1); 1847 assert(x[].equal([0, 1, 2, 3].s[])); 1848 } 1849 1850 foreach (Ch; AliasSeq!(char, wchar, dchar)) 1851 { 1852 static if (!isOrdered!ordering || // either not ordered 1853 is(Ch == dchar)) // or not a not a narrow string 1854 { 1855 alias Str = Array!(Ch, assignment, ordering, supportGC, size_t, less); 1856 auto y = Str.withElements('a', 'b', 'c'); 1857 static assert(is(Unqual!(ElementType!Str) == Ch)); 1858 y = Str.init; 1859 1860 const(Ch)[] xs; 1861 { 1862 // immutable 1863 immutable x = Str.withElements('a', 'b', 'c'); 1864 static if (!isOrdered!ordering) 1865 { 1866 xs = x[]; // TODO should fail with DIP-1000 scope 1867 } 1868 } 1869 } 1870 } 1871 1872 foreach (Ch; AliasSeq!(char)) 1873 { 1874 static if (!isOrdered!ordering) 1875 { 1876 alias Str = Array!(Ch, assignment, ordering, supportGC, size_t, less); 1877 auto str = Str.withElements('a', 'b', 'c'); 1878 1879 static if (isOrdered!ordering) 1880 { 1881 static assert(is(Unqual!(ElementType!Str) == Ch)); 1882 } 1883 else 1884 { 1885 static assert(is(ElementType!Str == Ch)); 1886 assert(str[] == `abc`); // TODO this fails for wchar and dchar 1887 } 1888 } 1889 } 1890 1891 { 1892 alias A = Array!(int, assignment, ordering, supportGC, size_t, less); 1893 foreach (immutable n; [0, 1, 2, 3, 4, 5]) 1894 { 1895 assert(A.withLength(n).isSmall); 1896 } 1897 assert(!(A.withLength(6).isSmall)); 1898 assert((A.withLength(6).isLarge)); 1899 } 1900 1901 // test move construction 1902 { 1903 immutable maxLength = 1024; 1904 foreach (immutable n; 0 .. maxLength) 1905 { 1906 auto x = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(n); 1907 1908 // test resize 1909 static if (!isOrdered!ordering) 1910 { 1911 assert(x.length == n); 1912 x.length = n + 1; 1913 assert(x.length == n + 1); 1914 x.length = n; 1915 } 1916 1917 const ptr = x.ptr; 1918 immutable capacity = x.capacity; 1919 assert(x.length == n); 1920 1921 import std.algorithm.mutation : move; 1922 auto y = Array!(E, assignment, ordering, supportGC, size_t, less)(); 1923 move(x, y); 1924 1925 assert(x.length == 0); 1926 assert(x.capacity == x.smallCapacity); 1927 1928 assert(y.length == n); 1929 assert(y.capacity == capacity); 1930 } 1931 } 1932 1933 foreach (immutable n; chain(0.only, iota(0, 10).map!(x => 2^^x))) 1934 { 1935 import std.array : array; 1936 import std.range : radial; 1937 1938 immutable zi = cast(int)0; // zero index 1939 immutable ni = cast(int)n; // number index 1940 1941 auto fw = iota(zi, ni); // 0, 1, 2, ..., n-1 1942 1943 auto bw = fw.array.radial; 1944 1945 Array!(E, assignment, ordering, supportGC, size_t, less) ss0 = bw; // reversed 1946 static assert(is(Unqual!(ElementType!(typeof(ss0))) == E)); 1947 static assert(isInstanceOf!(Array, typeof(ss0))); 1948 assert(ss0.length == n); 1949 1950 static if (isOrdered!ordering) 1951 { 1952 if (!ss0.empty) { assert(ss0[0] == ss0[0]); } // trigger use of opindex 1953 assert(ss0[].equal(fw.array 1954 .sort!comp)); 1955 assert(ss0[].isSorted!comp); 1956 } 1957 1958 Array!(E, assignment, ordering, supportGC, size_t, less) ss1 = fw; // ordinary 1959 assert(ss1.length == n); 1960 1961 static if (isOrdered!ordering) 1962 { 1963 assert(ss1[].equal(fw.array 1964 .sort!comp)); 1965 assert(ss1[].isSorted!comp); 1966 } 1967 1968 Array!(E, assignment, ordering, supportGC, size_t, less) ss2 = fw.filter!(x => x & 1); 1969 assert(ss2.length == n/2); 1970 1971 static if (isOrdered!ordering) 1972 { 1973 assert(ss2[].equal(fw.filter!(x => x & 1) 1974 .array 1975 .sort!comp)); 1976 assert(ss2[].isSorted!comp); 1977 } 1978 1979 auto ssA = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 1980 static if (isOrdered!ordering) 1981 { 1982 static if (less == "a < b") 1983 { 1984 alias A = Array!(E, assignment, ordering, supportGC, size_t, less); 1985 const A x = [1, 2, 3, 4, 5, 6]; 1986 assert(x.front == 1); 1987 assert(x.back == 6); 1988 assert(x.lowerBound(3).equal([1, 2].s[])); 1989 assert(x.upperBound(3).equal([4, 5, 6].s[])); 1990 assert(x[].equal(x[])); // already sorted 1991 } 1992 1993 foreach (i; bw) 1994 { 1995 static if (ordering == Ordering.sortedUniqueSet) 1996 { 1997 assert(ssA.insertMany(i)[].equal([true].s[])); 1998 assert(ssA.insertMany(i)[].equal([false].s[])); 1999 } 2000 else 2001 { 2002 ssA.insertMany(i); 2003 } 2004 } 2005 assert(ssA[].equal(sort!comp(fw.array))); 2006 2007 auto ssB = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2008 static if (ordering == Ordering.sortedUniqueSet) 2009 { 2010 assert(ssB.insertMany(1, 7, 4, 9)[].equal(true.repeat(4))); 2011 assert(ssB.insertMany(3, 6, 8, 5, 1, 9)[].equal([true, true, true, true, false, false].s[])); 2012 assert(ssB.insertMany(3, 0, 2, 10, 11, 5)[].equal([false, true, true, true, true, false].s[])); 2013 assert(ssB.insertMany(0, 2, 10, 11)[].equal(false.repeat(4))); // false becuse already inserted 2014 assert(ssB.capacity == 16); 2015 } 2016 else 2017 { 2018 ssB.insertMany(1, 7, 4, 9); 2019 ssB.insertMany(3, 6, 8, 5); 2020 ssB.insertMany(0, 2, 10, 11); 2021 assert(ssB.capacity == 16); 2022 } 2023 2024 auto ssI = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11].sort!comp; // values 2025 immutable ssO = [12, 13]; // values not range 2026 2027 assert(ssB[].equal(ssI)); 2028 2029 foreach (s; ssI) { assert(ssB.contains(s)); } 2030 foreach (s; ssO) { assert(!ssB.contains(s)); } 2031 2032 ssB.compress(); 2033 assert(ssB.capacity == 12); 2034 } 2035 else 2036 { 2037 { 2038 alias A = Array!(E, assignment, ordering, supportGC); 2039 A x = [1, 2, 3]; 2040 x ~= x; 2041 assert(x[].equal([1, 2, 3, 2042 1, 2, 3].s[])); 2043 x ~= x[]; 2044 assert(x[].equal([1, 2, 3, 1, 2, 3, 2045 1, 2, 3, 1, 2, 3].s[])); 2046 } 2047 2048 ssA ~= 3; 2049 ssA ~= 2; 2050 ssA ~= 1; 2051 assert(ssA[].equal([3, 2, 1].s[])); 2052 2053 ssA.compress(); 2054 2055 // popBack 2056 ssA[0] = 1; 2057 ssA[1] = 2; 2058 assert(ssA[].equal([1, 2, 1].s[])); 2059 assert(!ssA.empty); 2060 assert(ssA.front == 1); 2061 assert(ssA.back == 1); 2062 2063 assertNotThrown(ssA.popBack()); 2064 assert(ssA[].equal([1, 2].s[])); 2065 assert(!ssA.empty); 2066 assert(ssA.front == 1); 2067 assert(ssA.back == 2); 2068 2069 assertNotThrown(ssA.popBack()); 2070 assert(ssA[].equal([1].s[])); 2071 assert(!ssA.empty); 2072 assert(ssA.front == 1); 2073 assert(ssA.back == 1); 2074 2075 assertNotThrown(ssA.popBack()); 2076 assert(ssA.length == 0); 2077 assert(ssA.empty); 2078 assert(ssA.capacity != 0); 2079 2080 ssA.compress(); 2081 assert(ssA.length == 0); 2082 assert(ssA.empty); 2083 2084 // insertAt 2085 ssA ~= 1; 2086 ssA ~= 2; 2087 ssA ~= 3; 2088 ssA ~= 4; 2089 ssA ~= 5; 2090 ssA ~= 6; 2091 ssA ~= 7; 2092 ssA ~= 8; 2093 assert(ssA[].equal([1, 2, 3, 4, 5, 6, 7, 8].s[])); 2094 ssA.insertAtIndex(3, 100, 101); 2095 assert(ssA[].equal([1, 2, 3, 100, 101, 4, 5, 6, 7, 8].s[])); 2096 assertNotThrown(ssA.popFront()); 2097 assert(ssA[].equal([2, 3, 100, 101, 4, 5, 6, 7, 8].s[])); 2098 assertNotThrown(ssA.popFront()); 2099 assert(ssA[].equal([3, 100, 101, 4, 5, 6, 7, 8].s[])); 2100 assertNotThrown(ssA.popFront()); 2101 assert(ssA[].equal([100, 101, 4, 5, 6, 7, 8].s[])); 2102 assertNotThrown(ssA.popFront()); 2103 assertNotThrown(ssA.popFront()); 2104 assertNotThrown(ssA.popFront()); 2105 assertNotThrown(ssA.popFront()); 2106 assertNotThrown(ssA.popFront()); 2107 assertNotThrown(ssA.popFront()); 2108 assertNotThrown(ssA.popFront()); 2109 assert(ssA.empty); 2110 ssA.compress(); 2111 2112 // removeAt 2113 ssA ~= 1; 2114 ssA ~= 2; 2115 ssA ~= 3; 2116 ssA ~= 4; 2117 ssA ~= 5; 2118 assertNotThrown(ssA.removeAt(2)); 2119 assert(ssA[].equal([1, 2, 4, 5].s[])); 2120 2121 // insertBack and assignment from slice 2122 auto ssB = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2123 ssB.insertBack([1, 2, 3, 4, 5].s[]); 2124 ssB.insertBack([6, 7]); 2125 assert(ssB[].equal([1, 2, 3, 4, 5, 6, 7].s[])); 2126 assert(ssB.backPop() == 7); 2127 assert(ssB.backPop() == 6); 2128 assert(ssB.backPop() == 5); 2129 assert(ssB.backPop() == 4); 2130 assert(ssB.backPop() == 3); 2131 assert(ssB.backPop() == 2); 2132 assert(ssB.backPop() == 1); 2133 assert(ssB.empty); 2134 2135 // insertBack(Array) 2136 { 2137 immutable s = [1, 2, 3]; 2138 Array!(E, assignment, ordering, supportGC, size_t, less) s1 = s; 2139 Array!(E, assignment, ordering, supportGC, size_t, less) s2 = s1[]; 2140 assert(s1[].equal(s)); 2141 s1 ~= s1; 2142 assert(s1[].equal(chain(s, s))); 2143 s1 ~= s2; 2144 assert(s1[].equal(chain(s, s, s))); 2145 } 2146 2147 // immutable ss_ = Array!(E, assignment, ordering, supportGC, size_t, less)(null); 2148 // assert(ss_.empty); 2149 2150 auto ssC = Array!(E, assignment, ordering, supportGC, size_t, less).withLength(0); 2151 immutable int[5] i5_ = [1, 2, 3, 4, 5]; 2152 immutable(int)[] i5 = i5_[]; 2153 ssC.insertBack(i5); 2154 assert(i5 == [1, 2, 3, 4, 5].s[]); 2155 assert(ssC[].equal(i5)); 2156 2157 auto ssCc = ssC; // copy it 2158 assert(ssCc[].equal(i5)); 2159 2160 ssC.shrinkTo(4); 2161 assert(ssC[].equal([1, 2, 3, 4].s[])); 2162 2163 ssC.shrinkTo(3); 2164 assert(ssC[].equal([1, 2, 3].s[])); 2165 2166 ssC.shrinkTo(2); 2167 assert(ssC[].equal([1, 2].s[])); 2168 2169 ssC.shrinkTo(1); 2170 assert(ssC[].equal([1].s[])); 2171 2172 ssC.shrinkTo(0); 2173 assert(ssC[].length == 0); 2174 assert(ssC.empty); 2175 2176 ssC.insertBack(i5); 2177 ssC.popBackN(3); 2178 assert(ssC[].equal([1, 2].s[])); 2179 2180 auto ssD = ssC; 2181 ssC.clear(); 2182 assert(ssC.empty); 2183 2184 assert(!ssD.empty); 2185 ssD = null; 2186 assert(ssD.empty); 2187 assert(ssD == typeof(ssD).init); 2188 2189 assert(ssCc[].equal(i5)); 2190 2191 ssCc = ssCc; // self assignment 2192 } 2193 } 2194 } 2195 2196 /// disabled copying 2197 @safe pure nothrow @nogc unittest 2198 { 2199 alias E = ubyte; 2200 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2201 A a; 2202 immutable n = ubyte.max; 2203 size_t i = 0; 2204 foreach (ubyte e; 0 .. n) 2205 { 2206 a ~= e; 2207 // assert(a.back == e.to!E); 2208 assert(a.length == i + 1); 2209 ++i; 2210 } 2211 const b = a.dup; 2212 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2213 assert(b.length == a.length); 2214 assert(a !is b); 2215 assert(a == b); 2216 } 2217 2218 /// disabled copying 2219 @safe pure nothrow unittest 2220 { 2221 alias E = string; 2222 2223 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2224 A a; 2225 immutable n = 100_000; 2226 size_t i = 0; 2227 foreach (const ref e; 0 .. n) 2228 { 2229 a ~= e.to!E; 2230 // assert(a.back == e.to!E); 2231 assert(a.length == i + 1); 2232 ++i; 2233 } 2234 const b = a.dup; 2235 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2236 assert(b.length == a.length); 2237 assert(a !is b); 2238 assert(a == b); 2239 } 2240 2241 /// disabled copying 2242 @safe pure nothrow unittest 2243 { 2244 alias E = string; 2245 alias A = Array!(E, Assignment.disabled, Ordering.unsorted, false, size_t, "a < b"); 2246 A a; 2247 immutable n = 100_000; 2248 size_t i = 0; 2249 foreach (const ref e; 0 .. n) 2250 { 2251 a ~= e.to!E; 2252 assert(a.length == i + 1); 2253 ++i; 2254 } 2255 const b = a.dup; 2256 static assert(is(typeof(a) == Unqual!(typeof(b)))); 2257 assert(a[] == b[]); 2258 } 2259 2260 /// disabled copying 2261 @safe pure nothrow @nogc unittest 2262 { 2263 import std.traits : isAssignable; 2264 2265 alias E = string; 2266 2267 alias A = Array!E; 2268 static assert(!__traits(isCopyable, A)); 2269 2270 alias CA = CopyingArray!E; 2271 static assert(__traits(isCopyable, CA)); 2272 2273 // import std.traits : isRvalueAssignable, isLvalueAssignable; 2274 // static assert(isRvalueAssignable!(A)); 2275 // static assert(isLvalueAssignable!(A)); 2276 2277 static assert(isAssignable!(A)); 2278 2279 // import std.range.primitives : hasSlicing; 2280 // TODO make this evaluate to `true` 2281 // static assert(hasSlicing!A); 2282 2283 alias AA = Array!A; 2284 2285 AA aa; 2286 A a; 2287 a ~= "string"; 2288 aa ~= A.init; 2289 2290 assert(aa == aa); 2291 assert(AA.withLength(3) == AA.withLength(3)); 2292 assert(AA.withCapacity(3) == AA.withCapacity(3)); 2293 assert(AA.withLength(3).length == 3); 2294 assert(aa != AA.init); 2295 } 2296 2297 /// 2298 @safe pure nothrow @nogc unittest 2299 { 2300 alias E = int; 2301 alias A = Array!E; 2302 A a; 2303 import std.range : iota; 2304 import std.container.util : make; 2305 foreach (n; 0 .. 100) 2306 { 2307 const e = iota(0, n).make!Array; 2308 assert(e[].equal(iota(0, n))); 2309 } 2310 } 2311 2312 version(unittest) 2313 { 2314 import std.traits : EnumMembers; 2315 } 2316 2317 /// use GC 2318 pure nothrow unittest 2319 { 2320 foreach (ordering; EnumMembers!Ordering) 2321 { 2322 tester!(ordering, true, "a < b"); // use GC 2323 tester!(ordering, true, "a > b"); // use GC 2324 } 2325 } 2326 2327 /// don't use GC 2328 pure nothrow /+TODO @nogc+/ unittest 2329 { 2330 foreach (ordering; EnumMembers!Ordering) 2331 { 2332 tester!(ordering, false, "a < b"); // don't use GC 2333 tester!(ordering, false, "a > b"); // don't use GC 2334 } 2335 } 2336 2337 /// 2338 @safe pure nothrow unittest 2339 { 2340 alias E = int; 2341 alias A = Array!E; 2342 A[string] map; 2343 map["a"] = A.init; 2344 map["B"] = A.withLength(42); 2345 2346 auto aPtr = "a" in map; 2347 assert(aPtr); 2348 assert(A.init == *aPtr); 2349 assert(*aPtr == A.init); 2350 2351 assert("z" !in map); 2352 auto zPtr = "z" in map; 2353 assert(!zPtr); 2354 } 2355 2356 /// test withElement and withElements 2357 @safe pure nothrow @nogc unittest 2358 { 2359 import std.algorithm.mutation : move; 2360 import std.range.primitives : ElementType; 2361 2362 alias A = Array!int; 2363 alias AA = Array!A; 2364 alias AAA = Array!AA; 2365 2366 foreach (A_; AliasSeq!(A, AA, AAA)) 2367 { 2368 alias E = ElementType!A_; 2369 A_ x = A_.withElement(E.init); 2370 A_ y = A_.withElements(E.init, E.init); 2371 assert(x.length == 1); 2372 assert(y.length == 2); 2373 immutable n = 100; 2374 foreach (_; 0 .. n) 2375 { 2376 auto e = E.init; 2377 x ~= move(e); 2378 y ~= E.init; 2379 } 2380 foreach (_; 0 .. n) 2381 { 2382 assert(x.backPop() == E.init); 2383 assert(y.backPop() == E.init); 2384 } 2385 assert(x.length == 1); 2386 assert(y.length == 2); 2387 2388 import std.algorithm : swap; 2389 swap(x, y); 2390 assert(x.length == 2); 2391 assert(y.length == 1); 2392 2393 swap(x[0], y[0]); 2394 } 2395 2396 } 2397 2398 /// assert same behaviour of `dup` as for builtin arrays 2399 @safe pure nothrow unittest 2400 { 2401 struct Vec { int x, y; } 2402 class Db { int* _ptr; } 2403 struct Node { int x; class Db; } 2404 // struct Node1 { const(int) x; class Db; } 2405 foreach (E; AliasSeq!(int, const(int), Vec, Node// , Node1 2406 )) 2407 { 2408 alias DA = E[]; // builtin D array/slice 2409 immutable DA da = [E.init]; // construct from array 2410 auto daCopy = da.dup; // duplicate 2411 daCopy[] = E.init; // opSliceAssign 2412 2413 alias CA = Array!E; // container array 2414 immutable ca = CA.withElement(E.init); 2415 2416 auto caCopy = ca.dup; 2417 2418 import std.traits : hasIndirections; 2419 static if (!hasIndirections!E) 2420 { 2421 const(E)[2] x = [E.init, E.init]; 2422 // TODO caCopy ~= E.init; 2423 caCopy ~= x[]; 2424 assert(caCopy.length == 3); 2425 assert(caCopy[1 .. $] == x[]); 2426 } 2427 2428 // should have same element type 2429 static assert(is(typeof(caCopy[0]) == 2430 typeof(daCopy[0]))); 2431 2432 } 2433 } 2434 2435 /// array as AA key type 2436 @safe pure nothrow unittest 2437 { 2438 struct E { int x, y; } 2439 foreach (A; AliasSeq!(Array!E, 2440 CopyingArray!E)) 2441 { 2442 int[A] x; 2443 immutable n = 100; 2444 foreach (immutable i; 0 .. n) 2445 { 2446 assert(x.length == i); 2447 assert(A.withElement(E(i, 2*i)) !in x); 2448 x[A.withElement(E(i, 2*i))] = 42; 2449 assert(x.length == i + 1); 2450 auto a = A.withElement(E(i, 2*i)); 2451 import std.traits : isCopyable; 2452 static if (__traits(isCopyable, A)) 2453 { 2454 // TODO why do these fail when `A` is uncopyable? 2455 assert(a in x); 2456 assert(A.withElement(E(i, 2*i)) in x); 2457 assert(x[A.withElement(E(i, 2*i))] == 42); 2458 } 2459 } 2460 } 2461 } 2462 2463 /// init and append to empty array as AA value type 2464 @safe pure nothrow unittest 2465 { 2466 alias Key = string; 2467 alias A = Array!int; 2468 2469 A[Key] x; 2470 2471 assert("a" !in x); 2472 2473 x["a"] = A.init; // if this init is removed.. 2474 x["a"] ~= 42; // ..then this fails 2475 2476 assert(x["a"] == A.withElement(42)); 2477 } 2478 2479 /// compress 2480 @safe pure nothrow @nogc unittest 2481 { 2482 alias A = Array!string; 2483 A a; 2484 2485 a.compress(); 2486 2487 a ~= "a"; 2488 a ~= "b"; 2489 a ~= "c"; 2490 2491 assert(a.length == 3); 2492 assert(a.capacity == 4); 2493 2494 a.compress(); 2495 2496 assert(a.capacity == a.length); 2497 } 2498 2499 /// 2500 @safe pure nothrow @nogc unittest 2501 { 2502 alias Key = UniqueArray!char; 2503 alias Value = UniqueArray!int; 2504 struct E 2505 { 2506 Key key; 2507 Value value; 2508 E dup() @safe pure nothrow @nogc 2509 { 2510 return E(key.dup, value.dup); 2511 } 2512 } 2513 E e; 2514 e.key = Key.withElement('a'); 2515 e.value = Value.withElement(42); 2516 2517 auto f = e.dup; 2518 assert(e == f); 2519 2520 e.key = Key.withElement('b'); 2521 assert(e != f); 2522 2523 e.key = Key.withElement('a'); 2524 assert(e == f); 2525 2526 e.value = Value.withElement(43); 2527 assert(e != f); 2528 2529 e.value = Value.withElement(42); 2530 assert(e == f); 2531 2532 } 2533 2534 /// append to empty to array as AA value type 2535 @safe pure nothrow @nogc unittest 2536 { 2537 import std.exception: assertThrown; 2538 import core.exception : RangeError; 2539 2540 alias Key = string; 2541 alias A = Array!int; 2542 2543 A[Key] x; 2544 // assertThrown!RangeError({ x["a"] ~= 42; }); // TODO make this work 2545 } 2546 2547 /// map array of uncopyable 2548 @safe pure nothrow unittest 2549 { 2550 import std.range.primitives : isInputRange; 2551 import std.array : array; 2552 2553 alias A = UniqueArray!int; 2554 auto y = A.init[].map!(_ => _^^2).array; 2555 2556 A z = y.dup; // check that dup returns same type 2557 z = A.init; 2558 const w = [0, 1].s; 2559 z.insertBack(w[]); 2560 assert(z[].equal(w[])); 2561 } 2562 2563 /// 2564 version(none) 2565 @safe pure nothrow @nogc unittest 2566 { 2567 alias A = UniqueArray!int; 2568 A x; 2569 const y = [0, 1, 2, 3].s; 2570 2571 x.insertBack(y[]); 2572 assert(x[].equal(y[])); 2573 2574 x.clear(); 2575 x.insertBack(y[].map!(_ => _^^2)); // rhs has length (`hasLength`) 2576 assert(x[].equal(y[].map!(_ => _^^2))); 2577 2578 x.clear(); 2579 x.insertBack(y[].filter!(_ => _ & 1)); // rhs has no length (`!hasLength`) 2580 assert(x[].equal(y[].filter!(_ => _ & 1))); 2581 } 2582 2583 /// collection 2584 /*@safe*/ pure nothrow @nogc unittest // TODO make @safe when collect has been made safe 2585 { 2586 import std.range : iota, isOutputRange; 2587 import nxt.algorithm_ex : collect; 2588 2589 alias E = int; 2590 alias A = Array!E; 2591 2592 immutable n = 100; 2593 static assert(isOutputRange!(A, E)); 2594 2595 assert((0.iota(n).collect!A)[].equal(0.iota(n))); 2596 } 2597 2598 /// map array of uncopyable 2599 @safe pure nothrow @nogc unittest 2600 { 2601 foreach (AT; AliasSeq!(SortedUniqueArray, 2602 SortedSetUniqueArray)) 2603 { 2604 alias A = AT!int; 2605 A a; 2606 A b = a.dup; 2607 } 2608 } 2609 2610 /// init and append to empty array as AA value type 2611 @safe pure nothrow @nogc unittest 2612 { 2613 alias A = Array!int; 2614 2615 const x = A.withElements(0, 1, 3, 0, 2, 1, 3); 2616 2617 assert(x.toSortedArray == [0, 0, 1, 1, 2, 3, 3].s[]); 2618 assert(x.toSortedSetArray == [0, 1, 2, 3].s[]); 2619 2620 assert(x.toSortedArray!"a > b" == [3, 3, 2, 1, 1, 0, 0].s[]); 2621 assert(x.toSortedSetArray!"a > b" == [3, 2, 1, 0].s[]); 2622 } 2623 2624 /** Return `data` appended with arguments `args`. 2625 2626 If `data` is an r-value it's modified and returned, otherwise a copy is made 2627 and returned. 2628 */ 2629 C append(C, Args...)(auto ref C data, 2630 auto ref Args args) 2631 if (args.length >= 1) // TODO trait: when `C` is a container supporting `insertBack` 2632 { 2633 static if (__traits(isRef, data)) // `data` is an r-value 2634 { 2635 C mutableData = data.dup; 2636 } 2637 else // `data` is an l-value 2638 { 2639 alias mutableData = data; 2640 } 2641 // TODO use `mutableData.insertBack(args);` instead 2642 foreach (ref arg; args) 2643 { 2644 mutableData.insertBack(arg); 2645 } 2646 import std.algorithm.mutation : move; 2647 return move(mutableData); 2648 } 2649 2650 /// append 2651 @safe pure nothrow @nogc unittest 2652 { 2653 alias Str = UniqueString!false; 2654 2655 assert(Str(`a`).append('b', 'c')[] == `abc`); 2656 assert(Str(`a`).append(`b`, `c`)[] == `abc`); 2657 2658 const Str x = Str(`a`).append('b', 'c'); // is moved 2659 assert(x[] == `abc`); 2660 2661 Str y = `x`; 2662 Str z = y.append('y', 'z', `w`); // needs dup 2663 assert(y.ptr != z.ptr); 2664 assert(z[] == `xyzw`); 2665 } 2666 2667 version(unittest) 2668 { 2669 private static struct SS 2670 { 2671 @disable this(this); 2672 int x; 2673 } 2674 } 2675 2676 /// uncopyable elements 2677 @safe pure nothrow @nogc unittest 2678 { 2679 alias A = UniqueArray!SS; 2680 A x; 2681 x ~= SS.init; 2682 // TODO x.insertBack(A.init); 2683 } 2684 2685 // TODO implement? 2686 // T opBinary(string op, R, Args...)(R lhs, 2687 // auto ref Args args) 2688 // { 2689 // return append(lhs, rhs); 2690 // } 2691 // @safe pure nothrow @nogc unittest 2692 // { 2693 // alias S = UniqueString!false; 2694 // // TODO 2695 // // const S x = S(`a`) ~ 'b'; 2696 // // assert(x[] == `abc`); 2697 // } 2698 2699 /// See_Also: http://forum.dlang.org/post/omfm56$28nu$1@digitalmars.com 2700 version(none) 2701 @safe pure nothrow unittest 2702 { 2703 import std.range.primitives : ElementType; 2704 import std.array : Appender; 2705 2706 struct S 2707 { 2708 string src; 2709 S[] subs; 2710 } 2711 2712 struct T 2713 { 2714 string src; 2715 Appender!(T[]) subs; 2716 } 2717 2718 static assert(is(ElementType!(S[]) == S)); 2719 static assert(is(ElementType!(T[]) == void)); // TODO forward-reference bug: should be `T` 2720 2721 S s; 2722 s.subs ~= S.init; 2723 2724 T t; 2725 // t.subs ~= T.init; 2726 // t.subs.put(T.init); 2727 2728 // struct U 2729 // { 2730 // string src; 2731 // UniqueArray!U subs; 2732 // } 2733 // U u; 2734 } 2735 2736 /// class element 2737 @safe pure nothrow unittest 2738 { 2739 class Zing 2740 { 2741 void* raw; 2742 } 2743 class Edge : Zing 2744 { 2745 Zing[] actors; 2746 } 2747 2748 foreach (AT; AliasSeq!(UniqueArray, 2749 CopyingArray, 2750 SortedCopyingArray, 2751 SortedSetCopyingArray, 2752 SortedUniqueArray, 2753 SortedSetUniqueArray)) 2754 { 2755 alias A = AT!int; 2756 A a; 2757 } 2758 }