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 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 /** 181 Implements a doubly-linked list. 182 183 `DList` uses reference semantics. 184 */ 185 struct 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, "Root pointer must not be null"); 226 return _root._next; 227 } 228 ref inout(BaseNode*) _last() @property @safe nothrow pure inout 229 { 230 assert(_root, "Root pointer must not be null"); 231 return _root._prev; 232 } 233 } //end private 234 235 /** 236 Constructor taking a number of nodes 237 */ 238 this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) 239 { 240 insertBack(values); 241 } 242 243 /** 244 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 245 */ 246 this(Stuff)(Stuff stuff) 247 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 248 { 249 insertBack(stuff); 250 } 251 252 /** 253 Comparison for equality. 254 255 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of 256 elements in `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 /** 319 Property returning `true` if and only if the container has no 320 elements. 321 322 Complexity: $(BIGOH 1) 323 */ 324 bool empty() @property const nothrow 325 { 326 return _root is null || _root is _first; 327 } 328 329 /** 330 Removes all contents from the `DList`. 331 332 Postcondition: `empty` 333 334 Complexity: $(BIGOH 1) 335 */ 336 void clear() 337 { 338 //remove actual elements. 339 remove(this[]); 340 } 341 342 /** 343 Duplicates the container. The elements themselves are not transitively 344 duplicated. 345 346 Complexity: $(BIGOH n). 347 */ 348 @property DList dup() 349 { 350 return DList(this[]); 351 } 352 353 /** 354 Returns a range that iterates over all elements of the container, in 355 forward order. 356 357 Complexity: $(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 /** 368 Forward to `opSlice().front`. 369 370 Complexity: $(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 /** 379 Forward to `opSlice().back`. 380 381 Complexity: $(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 /** 394 Returns a new `DList` that's the concatenation of `this` and its 395 argument `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 /** 406 Returns a new `DList` that's the concatenation of the argument `lhs` 407 and `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 /** 418 Appends the contents of the argument `rhs` into `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 /** 432 Inserts `stuff` to the front/back of the container. `stuff` can be a 433 value convertible to `T` or a range of objects convertible to $(D 434 T). The stable version behaves the same, but guarantees that ranges 435 iterating over the container are never invalidated. 436 437 Returns: The number of elements inserted 438 439 Complexity: $(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 /** 467 Inserts `stuff` after range `r`, which must be a non-empty range 468 previously extracted from this container. 469 470 `stuff` can be a value convertible to `T` or a range of objects 471 convertible to `T`. The stable version behaves the same, but 472 guarantees that ranges iterating over the container are never 473 invalidated. 474 475 Returns: The number of values inserted. 476 477 Complexity: $(BIGOH k + m), where `k` is the number of elements in 478 `r` and `m` is the length of `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 /** 514 Picks one value in an unspecified position in the container, removes 515 it from the container, and returns it. The stable version behaves the same, 516 but guarantees that ranges iterating over the container are never invalidated. 517 518 Precondition: `!empty` 519 520 Returns: The element removed. 521 522 Complexity: $(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 /** 537 Removes the value at the front/back of the container. The stable version 538 behaves the same, but guarantees that ranges iterating over the 539 container are never invalidated. 540 541 Precondition: `!empty` 542 543 Complexity: $(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 /** 567 Removes `howMany` values at the front or back of the 568 container. Unlike the unparameterized versions above, these functions 569 do not throw if they could not remove `howMany` elements. Instead, 570 if $(D howMany > n), all elements are removed. The returned value is 571 the effective number of elements removed. The stable version behaves 572 the same, but guarantees that ranges iterating over the container are 573 never invalidated. 574 575 Returns: The number of elements removed 576 577 Complexity: $(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 /** 615 Removes all elements belonging to `r`, which must be a range 616 obtained originally from this container. 617 618 Returns: A range spanning the remaining elements in the container that 619 initially were right after `r`. 620 621 Complexity: $(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 /// ditto 646 alias stableRemove = remove; 647 648 /** 649 Removes first element of `r`, wich must be a range obtained originally 650 from this container, from both DList instance and range `r`. 651 652 Compexity: $(BIGOH 1) 653 */ 654 void popFirstOf(ref Range r) 655 { 656 assert(_root !is null, "Cannot remove from an un-initialized List"); 657 assert(r._first, "popFirstOf: Range is empty"); 658 auto prev = r._first._prev; 659 auto next = r._first._next; 660 r.popFront(); 661 BaseNode.connect(prev, next); 662 } 663 664 /** 665 Removes last element of `r`, wich must be a range obtained originally 666 from this container, from both DList instance and range `r`. 667 668 Compexity: $(BIGOH 1) 669 */ 670 void popLastOf(ref Range r) 671 { 672 assert(_root !is null, "Cannot remove from an un-initialized List"); 673 assert(r._first, "popLastOf: Range is empty"); 674 auto prev = r._last._prev; 675 auto next = r._last._next; 676 r.popBack(); 677 BaseNode.connect(prev, next); 678 } 679 680 /** 681 `linearRemove` functions as `remove`, but also accepts ranges that are 682 result the of a `take` operation. This is a convenient way to remove a 683 fixed amount of elements from the range. 684 685 Complexity: $(BIGOH r.walkLength) 686 */ 687 Range linearRemove(Take!Range r) 688 { 689 assert(_root !is null, "Cannot remove from an un-initialized List"); 690 assert(r.source._first, "Remove: Range is empty"); 691 692 BaseNode* first = r.source._first; 693 BaseNode* last = null; 694 do 695 { 696 last = r.source._first; 697 r.popFront(); 698 } while ( !r.empty ); 699 700 return remove(Range(first, last)); 701 } 702 703 /// ditto 704 alias stableLinearRemove = linearRemove; 705 706 /** 707 Removes the first occurence of an element from the list in linear time. 708 709 Returns: True if the element existed and was successfully removed, false otherwise. 710 711 Params: 712 value = value of the node to be removed 713 714 Complexity: $(BIGOH n) 715 */ 716 bool linearRemoveElement(T value) 717 { 718 auto n1 = findNodeByValue(_root, value); 719 if (n1) 720 { 721 auto n2 = n1._next._next; 722 BaseNode.connect(n1, n2); 723 return true; 724 } 725 726 return false; 727 } 728 729 730 private: 731 732 BaseNode* findNodeByValue(BaseNode* n, T value) 733 { 734 if (!n) return null; 735 auto ahead = n._next; 736 while (ahead && ahead.getPayload!T() != value) 737 { 738 n = ahead; 739 ahead = n._next; 740 if (ahead == _last._next) return null; 741 } 742 return n; 743 } 744 745 // Helper: Inserts stuff before the node n. 746 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 747 if (isImplicitlyConvertible!(Stuff, T)) 748 { 749 auto p = createNode(stuff, n._prev, n); 750 n._prev._next = p; 751 n._prev = p; 752 return 1; 753 } 754 // ditto 755 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 756 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 757 { 758 if (stuff.empty) return 0; 759 size_t result; 760 Range r = createRange(stuff, result); 761 BaseNode.connect(n._prev, r._first); 762 BaseNode.connect(r._last, n); 763 return result; 764 } 765 766 // Helper: Inserts stuff after the node n. 767 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 768 if (isImplicitlyConvertible!(Stuff, T)) 769 { 770 auto p = createNode(stuff, n, n._next); 771 n._next._prev = p; 772 n._next = p; 773 return 1; 774 } 775 // ditto 776 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 777 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 778 { 779 if (stuff.empty) return 0; 780 size_t result; 781 Range r = createRange(stuff, result); 782 BaseNode.connect(r._last, n._next); 783 BaseNode.connect(n, r._first); 784 return result; 785 } 786 787 // Helper: Creates a chain of nodes from the range stuff. 788 Range createRange(Stuff)(ref Stuff stuff, ref size_t result) 789 { 790 BaseNode* first = createNode(stuff.front); 791 BaseNode* last = first; 792 ++result; 793 for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() ) 794 { 795 auto p = createNode(stuff.front, last); 796 last = last._next = p; 797 ++result; 798 } 799 return Range(first, last); 800 } 801 } 802 803 @safe unittest 804 { 805 import std.algorithm.comparison : equal; 806 807 auto e = DList!int(); 808 auto b = e.linearRemoveElement(1); 809 assert(b == false); 810 assert(e.empty()); 811 auto a = DList!int(-1, 1, 2, 1, 3, 4); 812 b = a.linearRemoveElement(1); 813 assert(equal(a[], [-1, 2, 1, 3, 4])); 814 assert(b == true); 815 b = a.linearRemoveElement(-1); 816 assert(b == true); 817 assert(equal(a[], [2, 1, 3, 4])); 818 b = a.linearRemoveElement(1); 819 assert(b == true); 820 assert(equal(a[], [2, 3, 4])); 821 b = a.linearRemoveElement(2); 822 assert(b == true); 823 b = a.linearRemoveElement(20); 824 assert(b == false); 825 assert(equal(a[], [3, 4])); 826 b = a.linearRemoveElement(4); 827 assert(b == true); 828 assert(equal(a[], [3])); 829 b = a.linearRemoveElement(3); 830 assert(b == true); 831 assert(a.empty()); 832 a.linearRemoveElement(3); 833 } 834 835 @safe unittest 836 { 837 import std.algorithm.comparison : equal; 838 839 //Tests construction signatures 840 alias IntList = DList!int; 841 auto a0 = IntList(); 842 auto a1 = IntList(0); 843 auto a2 = IntList(0, 1); 844 auto a3 = IntList([0]); 845 auto a4 = IntList([0, 1]); 846 847 assert(a0[].empty); 848 assert(equal(a1[], [0])); 849 assert(equal(a2[], [0, 1])); 850 assert(equal(a3[], [0])); 851 assert(equal(a4[], [0, 1])); 852 } 853 854 @safe unittest 855 { 856 import std.algorithm.comparison : equal; 857 858 alias IntList = DList!int; 859 IntList list = IntList([0,1,2,3]); 860 assert(equal(list[],[0,1,2,3])); 861 list.insertBack([4,5,6,7]); 862 assert(equal(list[],[0,1,2,3,4,5,6,7])); 863 864 list = IntList(); 865 list.insertFront([0,1,2,3]); 866 assert(equal(list[],[0,1,2,3])); 867 list.insertFront([4,5,6,7]); 868 assert(equal(list[],[4,5,6,7,0,1,2,3])); 869 } 870 871 @safe unittest 872 { 873 import std.algorithm.comparison : equal; 874 import std.range : take; 875 876 alias IntList = DList!int; 877 IntList list = IntList([0,1,2,3]); 878 auto range = list[]; 879 for ( ; !range.empty; range.popFront()) 880 { 881 int item = range.front; 882 if (item == 2) 883 { 884 list.stableLinearRemove(take(range, 1)); 885 break; 886 } 887 } 888 assert(equal(list[],[0,1,3])); 889 890 list = IntList([0,1,2,3]); 891 range = list[]; 892 for ( ; !range.empty; range.popFront()) 893 { 894 int item = range.front; 895 if (item == 2) 896 { 897 list.stableLinearRemove(take(range,2)); 898 break; 899 } 900 } 901 assert(equal(list[],[0,1])); 902 903 list = IntList([0,1,2,3]); 904 range = list[]; 905 for ( ; !range.empty; range.popFront()) 906 { 907 int item = range.front; 908 if (item == 0) 909 { 910 list.stableLinearRemove(take(range,2)); 911 break; 912 } 913 } 914 assert(equal(list[],[2,3])); 915 916 list = IntList([0,1,2,3]); 917 range = list[]; 918 for ( ; !range.empty; range.popFront()) 919 { 920 int item = range.front; 921 if (item == 1) 922 { 923 list.stableLinearRemove(take(range,2)); 924 break; 925 } 926 } 927 assert(equal(list[],[0,3])); 928 } 929 930 @safe unittest 931 { 932 import std.algorithm.comparison : equal; 933 934 auto dl = DList!int([1, 2, 3, 4, 5]); 935 auto r = dl[]; 936 r.popFront(); 937 dl.popFirstOf(r); 938 assert(equal(dl[], [1, 3, 4, 5])); 939 assert(equal(r, [3, 4, 5])); 940 r.popBack(); 941 dl.popLastOf(r); 942 assert(equal(dl[], [1, 3, 5])); 943 assert(equal(r, [3])); 944 dl = DList!int([0]); 945 r = dl[]; 946 dl.popFirstOf(r); 947 assert(dl.empty); 948 dl = DList!int([0]); 949 r = dl[]; 950 dl.popLastOf(r); 951 assert(dl.empty); 952 } 953 954 @safe unittest 955 { 956 import std.algorithm.comparison : equal; 957 958 auto dl = DList!string(["a", "b", "d"]); 959 dl.insertAfter(dl[], "e"); // insert at the end 960 assert(equal(dl[], ["a", "b", "d", "e"])); 961 auto dlr = dl[]; 962 dlr.popBack(); dlr.popBack(); 963 dl.insertAfter(dlr, "c"); // insert after "b" 964 assert(equal(dl[], ["a", "b", "c", "d", "e"])); 965 } 966 967 @safe unittest 968 { 969 import std.algorithm.comparison : equal; 970 971 auto dl = DList!string(["a", "b", "d"]); 972 dl.insertBefore(dl[], "e"); // insert at the front 973 assert(equal(dl[], ["e", "a", "b", "d"])); 974 auto dlr = dl[]; 975 dlr.popFront(); dlr.popFront(); 976 dl.insertBefore(dlr, "c"); // insert before "b" 977 assert(equal(dl[], ["e", "a", "c", "b", "d"])); 978 } 979 980 @safe unittest 981 { 982 auto d = DList!int([1, 2, 3]); 983 d.front = 5; //test frontAssign 984 assert(d.front == 5); 985 auto r = d[]; 986 r.back = 1; 987 assert(r.back == 1); 988 } 989 990 // https://issues.dlang.org/show_bug.cgi?id=8895 991 @safe unittest 992 { 993 auto a = make!(DList!int)(1,2,3,4); 994 auto b = make!(DList!int)(1,2,3,4); 995 auto c = make!(DList!int)(1,2,3,5); 996 auto d = make!(DList!int)(1,2,3,4,5); 997 assert(a == b); // this better terminate! 998 assert(!(a == c)); 999 assert(!(a == d)); 1000 } 1001 1002 @safe unittest 1003 { 1004 auto d = DList!int([1, 2, 3]); 1005 d.front = 5; //test frontAssign 1006 assert(d.front == 5); 1007 auto r = d[]; 1008 r.back = 1; 1009 assert(r.back == 1); 1010 } 1011 1012 @safe unittest 1013 { 1014 auto a = DList!int(); 1015 assert(a.removeFront(10) == 0); 1016 a.insert([1, 2, 3]); 1017 assert(a.removeFront(10) == 3); 1018 assert(a[].empty); 1019 } 1020 1021 @safe unittest 1022 { 1023 import std.algorithm.comparison : equal; 1024 1025 //Verify all flavors of ~ 1026 auto a = DList!int(); 1027 auto b = DList!int(); 1028 auto c = DList!int([1, 2, 3]); 1029 auto d = DList!int([4, 5, 6]); 1030 1031 assert((a ~ b[])[].empty); 1032 assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6])); 1033 assert(c[].equal([1, 2, 3])); 1034 assert(d[].equal([4, 5, 6])); 1035 1036 assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6])); 1037 assert(c[].equal([1, 2, 3])); 1038 assert(d[].equal([4, 5, 6])); 1039 1040 a~=c[]; 1041 assert(a[].equal([1, 2, 3])); 1042 assert(c[].equal([1, 2, 3])); 1043 1044 a~=d[]; 1045 assert(a[].equal([1, 2, 3, 4, 5, 6])); 1046 assert(d[].equal([4, 5, 6])); 1047 1048 a~=[7, 8, 9]; 1049 assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9])); 1050 1051 //trick test: 1052 auto r = c[]; 1053 c.removeFront(); 1054 c.removeBack(); 1055 } 1056 1057 @safe unittest 1058 { 1059 import std.algorithm.comparison : equal; 1060 1061 // https://issues.dlang.org/show_bug.cgi?id=8905 1062 auto a = DList!int([1, 2, 3, 4]); 1063 auto r = a[]; 1064 a.stableRemoveBack(); 1065 a.stableInsertBack(7); 1066 assert(a[].equal([1, 2, 3, 7])); 1067 } 1068 1069 // https://issues.dlang.org/show_bug.cgi?id=12566 1070 @safe unittest 1071 { 1072 auto dl2 = DList!int([2,7]); 1073 dl2.removeFront(); 1074 assert(dl2[].walkLength == 1); 1075 dl2.removeBack(); 1076 assert(dl2.empty, "not empty?!"); 1077 } 1078 1079 // https://issues.dlang.org/show_bug.cgi?id=13076 1080 @safe unittest 1081 { 1082 DList!int list; 1083 assert(list.empty); 1084 list.clear(); 1085 } 1086 1087 // https://issues.dlang.org/show_bug.cgi?id=13425 1088 @safe unittest 1089 { 1090 import std.range : drop, take; 1091 auto list = DList!int([1,2,3,4,5]); 1092 auto r = list[].drop(4); // r is a view of the last element of list 1093 assert(r.front == 5 && r.walkLength == 1); 1094 r = list.linearRemove(r.take(1)); 1095 assert(r.empty); // fails 1096 } 1097 1098 // https://issues.dlang.org/show_bug.cgi?id=14300 1099 @safe unittest 1100 { 1101 interface ITest {} 1102 static class Test : ITest {} 1103 1104 DList!ITest().insertBack(new Test()); 1105 } 1106 1107 // https://issues.dlang.org/show_bug.cgi?id=15263 1108 @safe unittest 1109 { 1110 import std.range : iota; 1111 auto a = DList!int(); 1112 a.insertFront(iota(0, 5)); // can insert range with non-ref front 1113 assert(a.front == 0 && a.back == 4); 1114 }