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