1 /** 2 This module implements a generic doubly-linked list container. 3 It can be used as a queue, dequeue or stack. 4 5 This module is a submodule of $(MREF std, container). 6 7 Source: $(PHOBOSSRC std/container/dlist.d) 8 9 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 10 11 License: Distributed under the Boost Software License, Version 1.0. 12 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP 13 boost.org/LICENSE_1_0.txt)). 14 15 Authors: $(HTTP erdani.com, Andrei Alexandrescu) 16 17 $(SCRIPT inhibitQuickIndex = 1;) 18 */ 19 module std.container.dlist; 20 21 /// 22 @safe unittest 23 { 24 import std.algorithm.comparison : equal; 25 import std.container : DList; 26 27 auto s = DList!int(1, 2, 3); 28 assert(equal(s[], [1, 2, 3])); 29 30 s.removeFront(); 31 assert(equal(s[], [2, 3])); 32 s.removeBack(); 33 assert(equal(s[], [2])); 34 35 s.insertFront([4, 5]); 36 assert(equal(s[], [4, 5, 2])); 37 s.insertBack([6, 7]); 38 assert(equal(s[], [4, 5, 2, 6, 7])); 39 40 // If you want to apply range operations, simply slice it. 41 import std.algorithm.searching : countUntil; 42 import std.range : popFrontN, popBackN, walkLength; 43 44 auto sl = DList!int([1, 2, 3, 4, 5]); 45 assert(countUntil(sl[], 2) == 1); 46 47 auto r = sl[]; 48 popFrontN(r, 2); 49 popBackN(r, 2); 50 assert(r.equal([3])); 51 assert(walkLength(r) == 1); 52 53 // DList.Range can be used to remove elements from the list it spans 54 auto nl = DList!int([1, 2, 3, 4, 5]); 55 for (auto rn = nl[]; !rn.empty;) 56 if (rn.front % 2 == 0) 57 nl.popFirstOf(rn); 58 else 59 rn.popFront(); 60 assert(equal(nl[], [1, 3, 5])); 61 auto rs = nl[]; 62 rs.popFront(); 63 nl.remove(rs); 64 assert(equal(nl[], [1])); 65 } 66 67 import std.range.primitives; 68 import std.traits; 69 70 public import std.container.util; 71 72 /+ 73 A DList Node without payload. Used to handle the sentinel node (henceforth "sentinode"). 74 75 Also used for parts of the code that don't depend on the payload type. 76 +/ 77 private struct BaseNode 78 { 79 private BaseNode* _prev = null; 80 private BaseNode* _next = null; 81 82 /+ 83 Gets the payload associated with this node. 84 This is trusted because all nodes are associated with a payload, even 85 the sentinel node. 86 It is also not possible to mix Nodes in DLists of different types. 87 This function is implemented as a member function here, as UFCS does not 88 work with pointers. 89 +/ 90 ref inout(T) getPayload(T)() inout @trusted 91 { 92 return (cast(inout(DList!T.PayNode)*)&this)._payload; 93 } 94 95 // Helper: Given nodes p and n, connects them. 96 static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure 97 { 98 p._next = n; 99 n._prev = p; 100 } 101 } 102 103 /+ 104 The base DList Range. Contains Range primitives that don't depend on payload type. 105 +/ 106 private struct DRange 107 { 108 @safe unittest 109 { 110 static assert(isBidirectionalRange!DRange); 111 static assert(is(ElementType!DRange == BaseNode*)); 112 } 113 114 nothrow @safe @nogc pure: 115 private BaseNode* _first; 116 private BaseNode* _last; 117 118 private this(BaseNode* first, BaseNode* last) 119 { 120 assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments"); 121 _first = first; 122 _last = last; 123 } 124 private this(BaseNode* n) 125 { 126 this(n, n); 127 } 128 129 @property 130 bool empty() const scope 131 { 132 assert((_first is null) == (_last is null), "DList.Range: Invalidated state"); 133 return !_first; 134 } 135 136 @property BaseNode* front() return scope 137 { 138 assert(!empty, "DList.Range.front: Range is empty"); 139 return _first; 140 } 141 142 void popFront() scope 143 { 144 assert(!empty, "DList.Range.popFront: Range is empty"); 145 if (_first is _last) 146 { 147 _first = _last = null; 148 } 149 else 150 { 151 assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state"); 152 _first = _first._next; 153 } 154 } 155 156 @property BaseNode* back() return scope 157 { 158 assert(!empty, "DList.Range.front: Range is empty"); 159 return _last; 160 } 161 162 void popBack() scope 163 { 164 assert(!empty, "DList.Range.popBack: Range is empty"); 165 if (_first is _last) 166 { 167 _first = _last = null; 168 } 169 else 170 { 171 assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state"); 172 _last = _last._prev; 173 } 174 } 175 176 /// Forward range primitive. 177 @property DRange save() return scope { return this; } 178 } 179 180 /** 181 Implements a doubly-linked list. 182 183 `DList` uses reference semantics. 184 */ 185 struct DList(T) 186 { 187 import std.range : Take; 188 import std.traits : isMutable; 189 190 /* 191 A Node with a Payload. A PayNode. 192 */ 193 struct PayNode 194 { 195 BaseNode _base; 196 alias _base this; 197 198 T _payload = T.init; 199 200 this (BaseNode _base, T _payload) 201 { 202 import std.algorithm.mutation : move; 203 204 this._base = _base; 205 this._payload = move(_payload); 206 } 207 208 inout(BaseNode)* asBaseNode() inout @trusted 209 { 210 return &_base; 211 } 212 } 213 214 //The sentinel node 215 private BaseNode* _root; 216 217 private 218 { 219 //Construct as new PayNode, and returns it as a BaseNode. 220 static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null) 221 { 222 import std.algorithm.mutation : move; 223 224 static if (isMutable!Stuff) 225 return (new PayNode(BaseNode(prev, next), move(arg))).asBaseNode(); 226 else 227 return (new PayNode(BaseNode(prev, next), arg)).asBaseNode(); 228 } 229 230 void initialize() nothrow @safe pure 231 { 232 if (_root) return; 233 //Note: We allocate a PayNode for safety reasons. 234 _root = (new PayNode()).asBaseNode(); 235 _root._next = _root._prev = _root; 236 } 237 ref inout(BaseNode*) _first() @property @safe nothrow pure inout 238 { 239 assert(_root, "Root pointer must not be null"); 240 return _root._next; 241 } 242 ref inout(BaseNode*) _last() @property @safe nothrow pure inout 243 { 244 assert(_root, "Root pointer must not be null"); 245 return _root._prev; 246 } 247 } //end private 248 249 /** 250 Constructor taking a number of nodes 251 */ 252 this(U)(U[] values...) 253 if (isImplicitlyConvertible!(U, T)) 254 { 255 insertBack(values); 256 } 257 258 /** 259 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 260 */ 261 this(Stuff)(Stuff stuff) 262 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 263 { 264 insertBack(stuff); 265 } 266 267 /** 268 Comparison for equality. 269 270 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of 271 elements in `rhs`. 272 */ 273 bool opEquals()(ref const DList rhs) const 274 if (is(typeof(front == front))) 275 { 276 const lhs = this; 277 const lroot = lhs._root; 278 const rroot = rhs._root; 279 280 if (lroot is rroot) return true; 281 if (lroot is null) return rroot is rroot._next; 282 if (rroot is null) return lroot is lroot._next; 283 284 const(BaseNode)* pl = lhs._first; 285 const(BaseNode)* pr = rhs._first; 286 while (true) 287 { 288 if (pl is lroot) return pr is rroot; 289 if (pr is rroot) return false; 290 291 // !== because of NaN 292 if (!(pl.getPayload!T() == pr.getPayload!T())) return false; 293 294 pl = pl._next; 295 pr = pr._next; 296 } 297 } 298 299 /** 300 Defines the container's primary range, which embodies a bidirectional range. 301 */ 302 struct Range 303 { 304 static assert(isBidirectionalRange!Range); 305 306 DRange _base; 307 alias _base this; 308 309 private this(BaseNode* first, BaseNode* last) 310 { 311 _base = DRange(first, last); 312 } 313 private this(BaseNode* n) 314 { 315 this(n, n); 316 } 317 318 @property ref T front() 319 { 320 return _base.front.getPayload!T(); 321 } 322 323 @property ref T back() 324 { 325 return _base.back.getPayload!T(); 326 } 327 328 //Note: shadows base DRange.save. 329 //Necessary for static covariance. 330 @property Range save() { return this; } 331 } 332 333 /** 334 Property returning `true` if and only if the container has no 335 elements. 336 337 Complexity: $(BIGOH 1) 338 */ 339 bool empty() @property const nothrow 340 { 341 return _root is null || _root is _first; 342 } 343 344 /** 345 Removes all contents from the `DList`. 346 347 Postcondition: `empty` 348 349 Complexity: $(BIGOH 1) 350 */ 351 void clear() 352 { 353 //remove actual elements. 354 remove(this[]); 355 } 356 357 /** 358 Duplicates the container. The elements themselves are not transitively 359 duplicated. 360 361 Complexity: $(BIGOH n). 362 */ 363 @property DList dup() 364 { 365 return DList(this[]); 366 } 367 368 /** 369 Returns a range that iterates over all elements of the container, in 370 forward order. 371 372 Complexity: $(BIGOH 1) 373 */ 374 Range opSlice() 375 { 376 if (empty) 377 return Range(null, null); 378 else 379 return Range(_first, _last); 380 } 381 382 /** 383 Forward to `opSlice().front`. 384 385 Complexity: $(BIGOH 1) 386 */ 387 @property ref inout(T) front() inout 388 { 389 assert(!empty, "DList.front: List is empty"); 390 return _first.getPayload!T(); 391 } 392 393 /** 394 Forward to `opSlice().back`. 395 396 Complexity: $(BIGOH 1) 397 */ 398 @property ref inout(T) back() inout 399 { 400 assert(!empty, "DList.back: List is empty"); 401 return _last.getPayload!T(); 402 } 403 404 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 405 /+ BEGIN CONCAT FUNCTIONS HERE +/ 406 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 407 408 /** 409 Returns a new `DList` that's the concatenation of `this` and its 410 argument `rhs`. 411 */ 412 DList opBinary(string op, Stuff)(Stuff rhs) 413 if (op == "~" && is(typeof(insertBack(rhs)))) 414 { 415 auto ret = this.dup; 416 ret.insertBack(rhs); 417 return ret; 418 } 419 420 /** 421 Returns a new `DList` that's the concatenation of the argument `lhs` 422 and `this`. 423 */ 424 DList opBinaryRight(string op, Stuff)(Stuff lhs) 425 if (op == "~" && is(typeof(insertFront(lhs)))) 426 { 427 auto ret = this.dup; 428 ret.insertFront(lhs); 429 return ret; 430 } 431 432 /** 433 Appends the contents of the argument `rhs` into `this`. 434 */ 435 DList opOpAssign(string op, Stuff)(Stuff rhs) 436 if (op == "~" && is(typeof(insertBack(rhs)))) 437 { 438 insertBack(rhs); 439 return this; 440 } 441 442 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 443 /+ BEGIN INSERT FUNCTIONS HERE +/ 444 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 445 446 /** 447 Inserts `stuff` to the front/back of the container. `stuff` can be a 448 value convertible to `T` or a range of objects convertible to $(D 449 T). The stable version behaves the same, but guarantees that ranges 450 iterating over the container are never invalidated. 451 452 Returns: The number of elements inserted 453 454 Complexity: $(BIGOH log(n)) 455 */ 456 size_t insertFront(Stuff)(Stuff stuff) 457 { 458 initialize(); 459 return insertAfterNode(_root, stuff); 460 } 461 462 /// ditto 463 size_t insertBack(Stuff)(Stuff stuff) 464 { 465 initialize(); 466 return insertBeforeNode(_root, stuff); 467 } 468 469 /// ditto 470 alias insert = insertBack; 471 472 /// ditto 473 alias stableInsert = insert; 474 475 /// ditto 476 alias stableInsertFront = insertFront; 477 478 /// ditto 479 alias stableInsertBack = insertBack; 480 481 /** 482 Inserts `stuff` after range `r`, which must be a non-empty range 483 previously extracted from this container. 484 485 `stuff` can be a value convertible to `T` or a range of objects 486 convertible to `T`. The stable version behaves the same, but 487 guarantees that ranges iterating over the container are never 488 invalidated. 489 490 Returns: The number of values inserted. 491 492 Complexity: $(BIGOH k + m), where `k` is the number of elements in 493 `r` and `m` is the length of `stuff`. 494 */ 495 size_t insertBefore(Stuff)(Range r, Stuff stuff) 496 { 497 if (r._first) 498 return insertBeforeNode(r._first, stuff); 499 else 500 { 501 initialize(); 502 return insertAfterNode(_root, stuff); 503 } 504 } 505 506 /// ditto 507 alias stableInsertBefore = insertBefore; 508 509 /// ditto 510 size_t insertAfter(Stuff)(Range r, Stuff stuff) 511 { 512 if (r._last) 513 return insertAfterNode(r._last, stuff); 514 else 515 { 516 initialize(); 517 return insertBeforeNode(_root, stuff); 518 } 519 } 520 521 /// ditto 522 alias stableInsertAfter = insertAfter; 523 524 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 525 /+ BEGIN REMOVE FUNCTIONS HERE +/ 526 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 527 528 /** 529 Picks one value in an unspecified position in the container, removes 530 it from the container, and returns it. The stable version behaves the same, 531 but guarantees that ranges iterating over the container are never invalidated. 532 533 Precondition: `!empty` 534 535 Returns: The element removed. 536 537 Complexity: $(BIGOH 1). 538 */ 539 T removeAny() 540 { 541 import std.algorithm.mutation : move; 542 543 assert(!empty, "DList.removeAny: List is empty"); 544 auto result = move(back); 545 removeBack(); 546 return result; 547 } 548 /// ditto 549 alias stableRemoveAny = removeAny; 550 551 /** 552 Removes the value at the front/back of the container. The stable version 553 behaves the same, but guarantees that ranges iterating over the 554 container are never invalidated. 555 556 Precondition: `!empty` 557 558 Complexity: $(BIGOH 1). 559 */ 560 void removeFront() 561 { 562 assert(!empty, "DList.removeFront: List is empty"); 563 assert(_root is _first._prev, "DList: Inconsistent state"); 564 BaseNode.connect(_root, _first._next); 565 } 566 567 /// ditto 568 alias stableRemoveFront = removeFront; 569 570 /// ditto 571 void removeBack() 572 { 573 assert(!empty, "DList.removeBack: List is empty"); 574 assert(_last._next is _root, "DList: Inconsistent state"); 575 BaseNode.connect(_last._prev, _root); 576 } 577 578 /// ditto 579 alias stableRemoveBack = removeBack; 580 581 /** 582 Removes `howMany` values at the front or back of the 583 container. Unlike the unparameterized versions above, these functions 584 do not throw if they could not remove `howMany` elements. Instead, 585 if $(D howMany > n), all elements are removed. The returned value is 586 the effective number of elements removed. The stable version behaves 587 the same, but guarantees that ranges iterating over the container are 588 never invalidated. 589 590 Returns: The number of elements removed 591 592 Complexity: $(BIGOH howMany). 593 */ 594 size_t removeFront(size_t howMany) 595 { 596 if (!_root) return 0; 597 size_t result; 598 auto p = _first; 599 while (p !is _root && result < howMany) 600 { 601 p = p._next; 602 ++result; 603 } 604 BaseNode.connect(_root, p); 605 return result; 606 } 607 608 /// ditto 609 alias stableRemoveFront = removeFront; 610 611 /// ditto 612 size_t removeBack(size_t howMany) 613 { 614 if (!_root) return 0; 615 size_t result; 616 auto p = _last; 617 while (p !is _root && result < howMany) 618 { 619 p = p._prev; 620 ++result; 621 } 622 BaseNode.connect(p, _root); 623 return result; 624 } 625 626 /// ditto 627 alias stableRemoveBack = removeBack; 628 629 /** 630 Removes all elements belonging to `r`, which must be a range 631 obtained originally from this container. 632 633 Returns: A range spanning the remaining elements in the container that 634 initially were right after `r`. 635 636 Complexity: $(BIGOH 1) 637 */ 638 Range remove(Range r) 639 { 640 if (r.empty) 641 return r; 642 643 assert(_root !is null, "Cannot remove from an un-initialized List"); 644 assert(r._first, "Remove: Range is empty"); 645 646 BaseNode.connect(r._first._prev, r._last._next); 647 auto after = r._last._next; 648 if (after is _root) 649 return Range(null, null); 650 else 651 return Range(after, _last); 652 } 653 654 /// ditto 655 Range linearRemove(Range r) 656 { 657 return remove(r); 658 } 659 660 /// ditto 661 alias stableRemove = remove; 662 663 /** 664 Removes first element of `r`, wich must be a range obtained originally 665 from this container, from both DList instance and range `r`. 666 667 Compexity: $(BIGOH 1) 668 */ 669 void popFirstOf(ref Range r) 670 { 671 assert(_root !is null, "Cannot remove from an un-initialized List"); 672 assert(r._first, "popFirstOf: Range is empty"); 673 auto prev = r._first._prev; 674 auto next = r._first._next; 675 r.popFront(); 676 BaseNode.connect(prev, next); 677 } 678 679 /** 680 Removes last element of `r`, wich must be a range obtained originally 681 from this container, from both DList instance and range `r`. 682 683 Compexity: $(BIGOH 1) 684 */ 685 void popLastOf(ref Range r) 686 { 687 assert(_root !is null, "Cannot remove from an un-initialized List"); 688 assert(r._first, "popLastOf: Range is empty"); 689 auto prev = r._last._prev; 690 auto next = r._last._next; 691 r.popBack(); 692 BaseNode.connect(prev, next); 693 } 694 695 /** 696 `linearRemove` functions as `remove`, but also accepts ranges that are 697 result the of a `take` operation. This is a convenient way to remove a 698 fixed amount of elements from the range. 699 700 Complexity: $(BIGOH r.walkLength) 701 */ 702 Range linearRemove(Take!Range r) 703 { 704 assert(_root !is null, "Cannot remove from an un-initialized List"); 705 assert(r.source._first, "Remove: Range is empty"); 706 707 BaseNode* first = r.source._first; 708 BaseNode* last = null; 709 do 710 { 711 last = r.source._first; 712 r.popFront(); 713 } while ( !r.empty ); 714 715 return remove(Range(first, last)); 716 } 717 718 /// ditto 719 alias stableLinearRemove = linearRemove; 720 721 /** 722 Removes the first occurence of an element from the list in linear time. 723 724 Returns: True if the element existed and was successfully removed, false otherwise. 725 726 Params: 727 value = value of the node to be removed 728 729 Complexity: $(BIGOH n) 730 */ 731 bool linearRemoveElement(T value) 732 { 733 import std.algorithm.mutation : move; 734 735 auto n1 = findNodeByValue(_root, move(value)); 736 if (n1) 737 { 738 auto n2 = n1._next._next; 739 BaseNode.connect(n1, n2); 740 return true; 741 } 742 743 return false; 744 } 745 746 747 private: 748 749 BaseNode* findNodeByValue(BaseNode* n, T value) 750 { 751 if (!n) return null; 752 auto ahead = n._next; 753 while (ahead && ahead.getPayload!T() != value) 754 { 755 n = ahead; 756 ahead = n._next; 757 if (ahead == _last._next) return null; 758 } 759 return n; 760 } 761 762 // Helper: Inserts stuff before the node n. 763 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 764 if (isImplicitlyConvertible!(Stuff, T)) 765 { 766 auto p = createNode(stuff, n._prev, n); 767 n._prev._next = p; 768 n._prev = p; 769 return 1; 770 } 771 // ditto 772 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 773 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 774 { 775 if (stuff.empty) return 0; 776 size_t result; 777 Range r = createRange(stuff, result); 778 BaseNode.connect(n._prev, r._first); 779 BaseNode.connect(r._last, n); 780 return result; 781 } 782 783 // Helper: Inserts stuff after the node n. 784 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 785 if (isImplicitlyConvertible!(Stuff, T)) 786 { 787 auto p = createNode(stuff, n, n._next); 788 n._next._prev = p; 789 n._next = p; 790 return 1; 791 } 792 // ditto 793 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 794 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 795 { 796 if (stuff.empty) return 0; 797 size_t result; 798 Range r = createRange(stuff, result); 799 BaseNode.connect(r._last, n._next); 800 BaseNode.connect(n, r._first); 801 return result; 802 } 803 804 // Helper: Creates a chain of nodes from the range stuff. 805 Range createRange(Stuff)(ref Stuff stuff, ref size_t result) 806 { 807 BaseNode* first = createNode(stuff.front); 808 BaseNode* last = first; 809 ++result; 810 for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() ) 811 { 812 auto p = createNode(stuff.front, last); 813 last = last._next = p; 814 ++result; 815 } 816 return Range(first, last); 817 } 818 } 819 820 @safe unittest 821 { 822 import std.algorithm.comparison : equal; 823 824 auto e = DList!int(); 825 auto b = e.linearRemoveElement(1); 826 assert(b == false); 827 assert(e.empty()); 828 auto a = DList!int(-1, 1, 2, 1, 3, 4); 829 b = a.linearRemoveElement(1); 830 assert(equal(a[], [-1, 2, 1, 3, 4])); 831 assert(b == true); 832 b = a.linearRemoveElement(-1); 833 assert(b == true); 834 assert(equal(a[], [2, 1, 3, 4])); 835 b = a.linearRemoveElement(1); 836 assert(b == true); 837 assert(equal(a[], [2, 3, 4])); 838 b = a.linearRemoveElement(2); 839 assert(b == true); 840 b = a.linearRemoveElement(20); 841 assert(b == false); 842 assert(equal(a[], [3, 4])); 843 b = a.linearRemoveElement(4); 844 assert(b == true); 845 assert(equal(a[], [3])); 846 b = a.linearRemoveElement(3); 847 assert(b == true); 848 assert(a.empty()); 849 a.linearRemoveElement(3); 850 } 851 852 @safe unittest 853 { 854 import std.algorithm.comparison : equal; 855 856 //Tests construction signatures 857 alias IntList = DList!int; 858 auto a0 = IntList(); 859 auto a1 = IntList(0); 860 auto a2 = IntList(0, 1); 861 auto a3 = IntList([0]); 862 auto a4 = IntList([0, 1]); 863 864 assert(a0[].empty); 865 assert(equal(a1[], [0])); 866 assert(equal(a2[], [0, 1])); 867 assert(equal(a3[], [0])); 868 assert(equal(a4[], [0, 1])); 869 } 870 871 @safe unittest 872 { 873 import std.algorithm.comparison : equal; 874 875 alias IntList = DList!int; 876 IntList list = IntList([0,1,2,3]); 877 assert(equal(list[],[0,1,2,3])); 878 list.insertBack([4,5,6,7]); 879 assert(equal(list[],[0,1,2,3,4,5,6,7])); 880 881 list = IntList(); 882 list.insertFront([0,1,2,3]); 883 assert(equal(list[],[0,1,2,3])); 884 list.insertFront([4,5,6,7]); 885 assert(equal(list[],[4,5,6,7,0,1,2,3])); 886 } 887 888 @safe unittest 889 { 890 import std.algorithm.comparison : equal; 891 import std.range : take; 892 893 alias IntList = DList!int; 894 IntList list = IntList([0,1,2,3]); 895 auto range = list[]; 896 for ( ; !range.empty; range.popFront()) 897 { 898 int item = range.front; 899 if (item == 2) 900 { 901 list.stableLinearRemove(take(range, 1)); 902 break; 903 } 904 } 905 assert(equal(list[],[0,1,3])); 906 907 list = IntList([0,1,2,3]); 908 range = list[]; 909 for ( ; !range.empty; range.popFront()) 910 { 911 int item = range.front; 912 if (item == 2) 913 { 914 list.stableLinearRemove(take(range,2)); 915 break; 916 } 917 } 918 assert(equal(list[],[0,1])); 919 920 list = IntList([0,1,2,3]); 921 range = list[]; 922 for ( ; !range.empty; range.popFront()) 923 { 924 int item = range.front; 925 if (item == 0) 926 { 927 list.stableLinearRemove(take(range,2)); 928 break; 929 } 930 } 931 assert(equal(list[],[2,3])); 932 933 list = IntList([0,1,2,3]); 934 range = list[]; 935 for ( ; !range.empty; range.popFront()) 936 { 937 int item = range.front; 938 if (item == 1) 939 { 940 list.stableLinearRemove(take(range,2)); 941 break; 942 } 943 } 944 assert(equal(list[],[0,3])); 945 } 946 947 @safe unittest 948 { 949 import std.algorithm.comparison : equal; 950 951 auto dl = DList!int([1, 2, 3, 4, 5]); 952 auto r = dl[]; 953 r.popFront(); 954 dl.popFirstOf(r); 955 assert(equal(dl[], [1, 3, 4, 5])); 956 assert(equal(r, [3, 4, 5])); 957 r.popBack(); 958 dl.popLastOf(r); 959 assert(equal(dl[], [1, 3, 5])); 960 assert(equal(r, [3])); 961 dl = DList!int([0]); 962 r = dl[]; 963 dl.popFirstOf(r); 964 assert(dl.empty); 965 dl = DList!int([0]); 966 r = dl[]; 967 dl.popLastOf(r); 968 assert(dl.empty); 969 } 970 971 @safe unittest 972 { 973 import std.algorithm.comparison : equal; 974 975 auto dl = DList!string(["a", "b", "d"]); 976 dl.insertAfter(dl[], "e"); // insert at the end 977 assert(equal(dl[], ["a", "b", "d", "e"])); 978 auto dlr = dl[]; 979 dlr.popBack(); dlr.popBack(); 980 dl.insertAfter(dlr, "c"); // insert after "b" 981 assert(equal(dl[], ["a", "b", "c", "d", "e"])); 982 } 983 984 @safe unittest 985 { 986 import std.algorithm.comparison : equal; 987 988 auto dl = DList!string(["a", "b", "d"]); 989 dl.insertBefore(dl[], "e"); // insert at the front 990 assert(equal(dl[], ["e", "a", "b", "d"])); 991 auto dlr = dl[]; 992 dlr.popFront(); dlr.popFront(); 993 dl.insertBefore(dlr, "c"); // insert before "b" 994 assert(equal(dl[], ["e", "a", "c", "b", "d"])); 995 } 996 997 @safe unittest 998 { 999 auto d = DList!int([1, 2, 3]); 1000 d.front = 5; //test frontAssign 1001 assert(d.front == 5); 1002 auto r = d[]; 1003 r.back = 1; 1004 assert(r.back == 1); 1005 } 1006 1007 // https://issues.dlang.org/show_bug.cgi?id=8895 1008 @safe unittest 1009 { 1010 auto a = make!(DList!int)(1,2,3,4); 1011 auto b = make!(DList!int)(1,2,3,4); 1012 auto c = make!(DList!int)(1,2,3,5); 1013 auto d = make!(DList!int)(1,2,3,4,5); 1014 assert(a == b); // this better terminate! 1015 assert(!(a == c)); 1016 assert(!(a == d)); 1017 } 1018 1019 @safe unittest 1020 { 1021 auto d = DList!int([1, 2, 3]); 1022 d.front = 5; //test frontAssign 1023 assert(d.front == 5); 1024 auto r = d[]; 1025 r.back = 1; 1026 assert(r.back == 1); 1027 } 1028 1029 @safe unittest 1030 { 1031 auto a = DList!int(); 1032 assert(a.removeFront(10) == 0); 1033 a.insert([1, 2, 3]); 1034 assert(a.removeFront(10) == 3); 1035 assert(a[].empty); 1036 } 1037 1038 @safe unittest 1039 { 1040 import std.algorithm.comparison : equal; 1041 1042 //Verify all flavors of ~ 1043 auto a = DList!int(); 1044 auto b = DList!int(); 1045 auto c = DList!int([1, 2, 3]); 1046 auto d = DList!int([4, 5, 6]); 1047 1048 assert((a ~ b[])[].empty); 1049 assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6])); 1050 assert(c[].equal([1, 2, 3])); 1051 assert(d[].equal([4, 5, 6])); 1052 1053 assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6])); 1054 assert(c[].equal([1, 2, 3])); 1055 assert(d[].equal([4, 5, 6])); 1056 1057 a~=c[]; 1058 assert(a[].equal([1, 2, 3])); 1059 assert(c[].equal([1, 2, 3])); 1060 1061 a~=d[]; 1062 assert(a[].equal([1, 2, 3, 4, 5, 6])); 1063 assert(d[].equal([4, 5, 6])); 1064 1065 a~=[7, 8, 9]; 1066 assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9])); 1067 1068 //trick test: 1069 auto r = c[]; 1070 c.removeFront(); 1071 c.removeBack(); 1072 } 1073 1074 @safe unittest 1075 { 1076 import std.algorithm.comparison : equal; 1077 1078 // https://issues.dlang.org/show_bug.cgi?id=8905 1079 auto a = DList!int([1, 2, 3, 4]); 1080 auto r = a[]; 1081 a.stableRemoveBack(); 1082 a.stableInsertBack(7); 1083 assert(a[].equal([1, 2, 3, 7])); 1084 } 1085 1086 // https://issues.dlang.org/show_bug.cgi?id=12566 1087 @safe unittest 1088 { 1089 auto dl2 = DList!int([2,7]); 1090 dl2.removeFront(); 1091 assert(dl2[].walkLength == 1); 1092 dl2.removeBack(); 1093 assert(dl2.empty, "not empty?!"); 1094 } 1095 1096 // https://issues.dlang.org/show_bug.cgi?id=13076 1097 @safe unittest 1098 { 1099 DList!int list; 1100 assert(list.empty); 1101 list.clear(); 1102 } 1103 1104 // https://issues.dlang.org/show_bug.cgi?id=13425 1105 @safe unittest 1106 { 1107 import std.range : drop, take; 1108 auto list = DList!int([1,2,3,4,5]); 1109 auto r = list[].drop(4); // r is a view of the last element of list 1110 assert(r.front == 5 && r.walkLength == 1); 1111 r = list.linearRemove(r.take(1)); 1112 assert(r.empty); // fails 1113 } 1114 1115 // https://issues.dlang.org/show_bug.cgi?id=14300 1116 @safe unittest 1117 { 1118 interface ITest {} 1119 static class Test : ITest {} 1120 1121 DList!ITest().insertBack(new Test()); 1122 } 1123 1124 // https://issues.dlang.org/show_bug.cgi?id=15263 1125 @safe unittest 1126 { 1127 import std.range : iota; 1128 auto a = DList!int(); 1129 a.insertFront(iota(0, 5)); // can insert range with non-ref front 1130 assert(a.front == 0 && a.back == 4); 1131 } 1132 1133 // https://issues.dlang.org/show_bug.cgi?id=22147 1134 @safe unittest 1135 { 1136 import std.algorithm.mutation : move; 1137 1138 static struct Item 1139 { 1140 @disable this(this); 1141 1142 int x; 1143 } 1144 1145 auto list = DList!Item(); 1146 list.insertFront(Item(1)); 1147 assert(list[].walkLength == 1); 1148 assert(list.front.x == 1); 1149 auto item = list.moveFront; 1150 item.x = 2; 1151 list.front = move(item); 1152 assert(list.front.x == 2); 1153 list.removeFront(); 1154 assert(list[].walkLength == 0); 1155 } 1156 1157 // https://issues.dlang.org/show_bug.cgi?id=24637 1158 @safe unittest 1159 { 1160 import std.algorithm.comparison : equal; 1161 1162 struct A 1163 { 1164 int c; 1165 } 1166 1167 DList!A B; 1168 B.insert(A(1)); 1169 assert(B[].equal([A(1)])); 1170 1171 const a = A(3); 1172 B.insert(a); 1173 assert(B[].equal([A(1), A(3)])); 1174 }