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