1 /** 2 This module implements a singly-linked list container. 3 It can be used as a stack. 4 5 This module is a submodule of $(MREF std, container). 6 7 Source: $(PHOBOSSRC std/container/slist.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.slist; 20 21 /// 22 @safe unittest 23 { 24 import std.algorithm.comparison : equal; 25 import std.container : SList; 26 27 auto s = SList!int(1, 2, 3); 28 assert(equal(s[], [1, 2, 3])); 29 30 s.removeFront(); 31 assert(equal(s[], [2, 3])); 32 33 s.insertFront([5, 6]); 34 assert(equal(s[], [5, 6, 2, 3])); 35 36 // If you want to apply range operations, simply slice it. 37 import std.algorithm.searching : countUntil; 38 import std.range : popFrontN, walkLength; 39 40 auto sl = SList!int(1, 2, 3, 4, 5); 41 assert(countUntil(sl[], 2) == 1); 42 43 auto r = sl[]; 44 popFrontN(r, 2); 45 assert(walkLength(r) == 3); 46 } 47 48 public import std.container.util; 49 50 /** 51 Implements a simple and fast singly-linked list. 52 It can be used as a stack. 53 54 `SList` uses reference semantics. 55 */ 56 struct SList(T) 57 if (!is(T == shared)) 58 { 59 import std.exception : enforce; 60 import std.range : Take; 61 import std.range.primitives : isInputRange, isForwardRange, ElementType; 62 import std.traits : isImplicitlyConvertible; 63 64 private struct Node 65 { 66 Node * _next; 67 T _payload; 68 } 69 private struct NodeWithoutPayload 70 { 71 Node* _next; 72 } 73 static assert(NodeWithoutPayload._next.offsetof == Node._next.offsetof); 74 75 private Node * _root; 76 77 private void initialize() @trusted nothrow pure 78 { 79 if (_root) return; 80 _root = cast (Node*) new NodeWithoutPayload(); 81 } 82 83 private ref inout(Node*) _first() @property @safe nothrow pure inout 84 { 85 assert(_root, "root pointer must not be null"); 86 return _root._next; 87 } 88 89 private static Node * findLastNode(Node * n) 90 { 91 assert(n, "Node n pointer must not be null"); 92 auto ahead = n._next; 93 while (ahead) 94 { 95 n = ahead; 96 ahead = n._next; 97 } 98 return n; 99 } 100 101 private static Node * findLastNode(Node * n, size_t limit) 102 { 103 assert(n, "Node n pointer must not be null"); 104 assert(limit, "limit must be greater than 0"); 105 auto ahead = n._next; 106 while (ahead) 107 { 108 if (!--limit) break; 109 n = ahead; 110 ahead = n._next; 111 } 112 return n; 113 } 114 115 private static Node * findNode(Node * n, Node * findMe) 116 { 117 assert(n, "Node n pointer must not be null"); 118 auto ahead = n._next; 119 while (ahead != findMe) 120 { 121 n = ahead; 122 enforce(n); 123 ahead = n._next; 124 } 125 return n; 126 } 127 128 private static Node* findNodeByValue(Node* n, T value) 129 { 130 if (!n) return null; 131 auto ahead = n._next; 132 while (ahead && ahead._payload != value) 133 { 134 n = ahead; 135 ahead = n._next; 136 } 137 return n; 138 } 139 140 private static auto createNodeChain(Stuff)(Stuff stuff) 141 if (isImplicitlyConvertible!(Stuff, T)) 142 { 143 import std.range : only; 144 return createNodeChain(only(stuff)); 145 } 146 147 private static auto createNodeChain(Stuff)(Stuff stuff) 148 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 149 { 150 static struct Chain 151 { 152 Node* first; 153 Node* last; 154 size_t length; 155 } 156 157 Chain ch; 158 159 foreach (item; stuff) 160 { 161 auto newNode = new Node(null, item); 162 (ch.first ? ch.last._next : ch.first) = newNode; 163 ch.last = newNode; 164 ++ch.length; 165 } 166 167 return ch; 168 } 169 170 private static size_t insertAfterNode(Stuff)(Node* n, Stuff stuff) 171 { 172 auto ch = createNodeChain(stuff); 173 174 if (!ch.length) return 0; 175 176 ch.last._next = n._next; 177 n._next = ch.first; 178 179 return ch.length; 180 } 181 182 /** 183 Constructor taking a number of nodes 184 */ 185 this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) 186 { 187 insertFront(values); 188 } 189 190 /** 191 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 192 */ 193 this(Stuff)(Stuff stuff) 194 if (isInputRange!Stuff 195 && isImplicitlyConvertible!(ElementType!Stuff, T) 196 && !is(Stuff == T[])) 197 { 198 insertFront(stuff); 199 } 200 201 /** 202 Comparison for equality. 203 204 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of 205 elements in `rhs`. 206 */ 207 bool opEquals(const SList rhs) const 208 { 209 return opEquals(rhs); 210 } 211 212 /// ditto 213 bool opEquals(ref const SList rhs) const 214 { 215 if (_root is rhs._root) return true; 216 if (_root is null) return rhs._root is null || rhs._first is null; 217 if (rhs._root is null) return _root is null || _first is null; 218 219 const(Node) * n1 = _first, n2 = rhs._first; 220 221 for (;; n1 = n1._next, n2 = n2._next) 222 { 223 if (!n1) return !n2; 224 if (!n2 || n1._payload != n2._payload) return false; 225 } 226 } 227 228 /** 229 Defines the container's primary range, which embodies a forward range. 230 */ 231 struct Range 232 { 233 private Node * _head; 234 private this(Node * p) { _head = p; } 235 236 /// Input range primitives. 237 @property bool empty() const { return !_head; } 238 239 /// ditto 240 @property ref T front() 241 { 242 assert(!empty, "SList.Range.front: Range is empty"); 243 return _head._payload; 244 } 245 246 /// ditto 247 void popFront() 248 { 249 assert(!empty, "SList.Range.popFront: Range is empty"); 250 _head = _head._next; 251 } 252 253 /// Forward range primitive. 254 @property Range save() { return this; } 255 256 T moveFront() 257 { 258 import std.algorithm.mutation : move; 259 260 assert(!empty, "SList.Range.moveFront: Range is empty"); 261 return move(_head._payload); 262 } 263 264 bool sameHead(Range rhs) 265 { 266 return _head && _head == rhs._head; 267 } 268 } 269 270 @safe unittest 271 { 272 static assert(isForwardRange!Range); 273 } 274 275 /** 276 Property returning `true` if and only if the container has no 277 elements. 278 279 Complexity: $(BIGOH 1) 280 */ 281 @property bool empty() const 282 { 283 return _root is null || _first is null; 284 } 285 286 /** 287 Duplicates the container. The elements themselves are not transitively 288 duplicated. 289 290 Complexity: $(BIGOH n). 291 */ 292 @property SList dup() 293 { 294 return SList(this[]); 295 } 296 297 /** 298 Returns a range that iterates over all elements of the container, in 299 forward order. 300 301 Complexity: $(BIGOH 1) 302 */ 303 Range opSlice() 304 { 305 if (empty) 306 return Range(null); 307 else 308 return Range(_first); 309 } 310 311 /** 312 Forward to `opSlice().front`. 313 314 Complexity: $(BIGOH 1) 315 */ 316 @property ref T front() 317 { 318 assert(!empty, "SList.front: List is empty"); 319 return _first._payload; 320 } 321 322 @safe unittest 323 { 324 auto s = SList!int(1, 2, 3); 325 s.front = 42; 326 assert(s == SList!int(42, 2, 3)); 327 } 328 329 /** 330 Returns a new `SList` that's the concatenation of `this` and its 331 argument. `opBinaryRight` is only defined if `Stuff` does not 332 define `opBinary`. 333 */ 334 SList opBinary(string op, Stuff)(Stuff rhs) 335 if (op == "~" && is(typeof(SList(rhs)))) 336 { 337 import std.range : chain, only; 338 339 static if (isInputRange!Stuff) 340 alias r = rhs; 341 else 342 auto r = only(rhs); 343 344 return SList(this[].chain(r)); 345 } 346 347 /// ditto 348 SList opBinaryRight(string op, Stuff)(Stuff lhs) 349 if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs)))) 350 { 351 import std.range : chain, only; 352 353 static if (isInputRange!Stuff) 354 alias r = lhs; 355 else 356 auto r = only(lhs); 357 358 return SList(r.chain(this[])); 359 } 360 361 /** 362 Removes all contents from the `SList`. 363 364 Postcondition: `empty` 365 366 Complexity: $(BIGOH 1) 367 */ 368 void clear() 369 { 370 if (_root) 371 _first = null; 372 } 373 374 /** 375 Reverses SList in-place. Performs no memory allocation. 376 377 Complexity: $(BIGOH n) 378 */ 379 void reverse() 380 { 381 if (!empty) 382 { 383 Node* prev; 384 while (_first) 385 { 386 auto next = _first._next; 387 _first._next = prev; 388 prev = _first; 389 _first = next; 390 } 391 _first = prev; 392 } 393 } 394 395 /** 396 Inserts `stuff` to the front of the container. `stuff` can be a 397 value convertible to `T` or a range of objects convertible to $(D 398 T). The stable version behaves the same, but guarantees that ranges 399 iterating over the container are never invalidated. 400 401 Returns: The number of elements inserted 402 403 Complexity: $(BIGOH m), where `m` is the length of `stuff` 404 */ 405 size_t insertFront(Stuff)(Stuff stuff) 406 if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T)) 407 { 408 initialize(); 409 return insertAfterNode(_root, stuff); 410 } 411 412 /// ditto 413 alias insert = insertFront; 414 415 /// ditto 416 alias stableInsert = insert; 417 418 /// ditto 419 alias stableInsertFront = insertFront; 420 421 /** 422 Picks one value in an unspecified position in the container, removes 423 it from the container, and returns it. The stable version behaves the same, 424 but guarantees that ranges iterating over the container are never invalidated. 425 426 Precondition: `!empty` 427 428 Returns: The element removed. 429 430 Complexity: $(BIGOH 1). 431 */ 432 T removeAny() 433 { 434 import std.algorithm.mutation : move; 435 436 assert(!empty, "SList.removeAny: List is empty"); 437 auto result = move(_first._payload); 438 _first = _first._next; 439 return result; 440 } 441 /// ditto 442 alias stableRemoveAny = removeAny; 443 444 /** 445 Removes the value at the front of the container. The stable version 446 behaves the same, but guarantees that ranges iterating over the 447 container are never invalidated. 448 449 Precondition: `!empty` 450 451 Complexity: $(BIGOH 1). 452 */ 453 void removeFront() 454 { 455 assert(!empty, "SList.removeFront: List is empty"); 456 _first = _first._next; 457 } 458 459 /// ditto 460 alias stableRemoveFront = removeFront; 461 462 /** 463 Removes `howMany` values at the front or back of the 464 container. Unlike the unparameterized versions above, these functions 465 do not throw if they could not remove `howMany` elements. Instead, 466 if $(D howMany > n), all elements are removed. The returned value is 467 the effective number of elements removed. The stable version behaves 468 the same, but guarantees that ranges iterating over the container are 469 never invalidated. 470 471 Returns: The number of elements removed 472 473 Complexity: $(BIGOH howMany * log(n)). 474 */ 475 size_t removeFront(size_t howMany) 476 { 477 size_t result; 478 while (_first && result < howMany) 479 { 480 _first = _first._next; 481 ++result; 482 } 483 return result; 484 } 485 486 /// ditto 487 alias stableRemoveFront = removeFront; 488 489 /** 490 Inserts `stuff` after range `r`, which must be a range 491 previously extracted from this container. Given that all ranges for a 492 list end at the end of the list, this function essentially appends to 493 the list and uses `r` as a potentially fast way to reach the last 494 node in the list. Ideally `r` is positioned near or at the last 495 element of the list. 496 497 `stuff` can be a value convertible to `T` or a range of objects 498 convertible to `T`. The stable version behaves the same, but 499 guarantees that ranges iterating over the container are never 500 invalidated. 501 502 Returns: The number of values inserted. 503 504 Complexity: $(BIGOH k + m), where `k` is the number of elements in 505 `r` and `m` is the length of `stuff`. 506 507 Example: 508 -------------------- 509 auto sl = SList!string(["a", "b", "d"]); 510 sl.insertAfter(sl[], "e"); // insert at the end (slowest) 511 assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"])); 512 sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b" 513 assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"])); 514 -------------------- 515 */ 516 517 size_t insertAfter(Stuff)(Range r, Stuff stuff) 518 if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T)) 519 { 520 initialize(); 521 if (!_first) 522 { 523 enforce(!r._head); 524 return insertFront(stuff); 525 } 526 enforce(r._head); 527 auto n = findLastNode(r._head); 528 return insertAfterNode(n, stuff); 529 } 530 531 /** 532 Similar to `insertAfter` above, but accepts a range bounded in 533 count. This is important for ensuring fast insertions in the middle of 534 the list. For fast insertions after a specified position `r`, use 535 $(D insertAfter(take(r, 1), stuff)). The complexity of that operation 536 only depends on the number of elements in `stuff`. 537 538 Precondition: $(D r.original.empty || r.maxLength > 0) 539 540 Returns: The number of values inserted. 541 542 Complexity: $(BIGOH k + m), where `k` is the number of elements in 543 `r` and `m` is the length of `stuff`. 544 */ 545 size_t insertAfter(Stuff)(Take!Range r, Stuff stuff) 546 if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T)) 547 { 548 auto orig = r.source; 549 if (!orig._head) 550 { 551 // Inserting after a null range counts as insertion to the 552 // front 553 return insertFront(stuff); 554 } 555 enforce(!r.empty); 556 // Find the last valid element in the range 557 foreach (i; 1 .. r.maxLength) 558 { 559 if (!orig._head._next) break; 560 orig.popFront(); 561 } 562 // insert here 563 return insertAfterNode(orig._head, stuff); 564 } 565 566 /// ditto 567 alias stableInsertAfter = insertAfter; 568 569 /** 570 Removes a range from the list in linear time. 571 572 Returns: An empty range. 573 574 Complexity: $(BIGOH n) 575 */ 576 Range linearRemove(Range r) 577 { 578 if (!_first) 579 { 580 enforce(!r._head); 581 return this[]; 582 } 583 auto n = findNode(_root, r._head); 584 n._next = null; 585 return Range(null); 586 } 587 588 /** 589 Removes a `Take!Range` from the list in linear time. 590 591 Returns: A range comprehending the elements after the removed range. 592 593 Complexity: $(BIGOH n) 594 */ 595 Range linearRemove(Take!Range r) 596 { 597 auto orig = r.source; 598 // We have something to remove here 599 if (orig._head == _first) 600 { 601 // remove straight from the head of the list 602 for (; !r.empty; r.popFront()) 603 { 604 removeFront(); 605 } 606 return this[]; 607 } 608 if (!r.maxLength) 609 { 610 // Nothing to remove, return the range itself 611 return orig; 612 } 613 // Remove from somewhere in the middle of the list 614 enforce(_first); 615 auto n1 = findNode(_root, orig._head); 616 auto n2 = findLastNode(orig._head, r.maxLength); 617 n1._next = n2._next; 618 return Range(n1._next); 619 } 620 621 /// ditto 622 alias stableLinearRemove = linearRemove; 623 624 /** 625 Removes the first occurence of an element from the list in linear time. 626 627 Returns: True if the element existed and was successfully removed, false otherwise. 628 629 Params: 630 value = value of the node to be removed 631 632 Complexity: $(BIGOH n) 633 */ 634 bool linearRemoveElement(T value) 635 { 636 auto n1 = findNodeByValue(_root, value); 637 638 if (n1 && n1._next) 639 { 640 n1._next = n1._next._next; 641 return true; 642 } 643 644 return false; 645 } 646 } 647 648 @safe unittest 649 { 650 import std.algorithm.comparison : equal; 651 652 auto e = SList!int(); 653 auto b = e.linearRemoveElement(2); 654 assert(b == false); 655 assert(e.empty()); 656 auto a = SList!int(-1, 1, 2, 1, 3, 4); 657 b = a.linearRemoveElement(1); 658 assert(equal(a[], [-1, 2, 1, 3, 4])); 659 assert(b == true); 660 b = a.linearRemoveElement(-1); 661 assert(b == true); 662 assert(equal(a[], [2, 1, 3, 4])); 663 b = a.linearRemoveElement(1); 664 assert(b == true); 665 assert(equal(a[], [2, 3, 4])); 666 b = a.linearRemoveElement(2); 667 assert(b == true); 668 b = a.linearRemoveElement(20); 669 assert(b == false); 670 assert(equal(a[], [3, 4])); 671 b = a.linearRemoveElement(4); 672 assert(b == true); 673 assert(equal(a[], [3])); 674 b = a.linearRemoveElement(3); 675 assert(b == true); 676 assert(a.empty()); 677 a.linearRemoveElement(3); 678 } 679 680 @safe unittest 681 { 682 import std.algorithm.comparison : equal; 683 684 auto a = SList!int(5); 685 auto b = a; 686 auto r = a[]; 687 a.insertFront(1); 688 b.insertFront(2); 689 assert(equal(a[], [2, 1, 5])); 690 assert(equal(b[], [2, 1, 5])); 691 r.front = 9; 692 assert(equal(a[], [2, 1, 9])); 693 assert(equal(b[], [2, 1, 9])); 694 } 695 696 @safe unittest 697 { 698 auto s = SList!int(1, 2, 3); 699 auto n = s.findLastNode(s._root); 700 assert(n && n._payload == 3); 701 } 702 703 @safe unittest 704 { 705 import std.range.primitives; 706 auto s = SList!int(1, 2, 5, 10); 707 assert(walkLength(s[]) == 4); 708 } 709 710 @safe unittest 711 { 712 import std.range : take; 713 auto src = take([0, 1, 2, 3], 3); 714 auto s = SList!int(src); 715 assert(s == SList!int(0, 1, 2)); 716 } 717 718 @safe unittest 719 { 720 auto a = SList!int(); 721 auto b = SList!int(); 722 auto c = a ~ b[]; 723 assert(c.empty); 724 } 725 726 @safe unittest 727 { 728 auto a = SList!int(1, 2, 3); 729 auto b = SList!int(4, 5, 6); 730 auto c = a ~ b[]; 731 assert(c == SList!int(1, 2, 3, 4, 5, 6)); 732 } 733 734 @safe unittest 735 { 736 auto a = SList!int(1, 2, 3); 737 auto b = [4, 5, 6]; 738 auto c = a ~ b; 739 assert(c == SList!int(1, 2, 3, 4, 5, 6)); 740 } 741 742 @safe unittest 743 { 744 auto a = SList!int(1, 2, 3); 745 auto c = a ~ 4; 746 assert(c == SList!int(1, 2, 3, 4)); 747 } 748 749 @safe unittest 750 { 751 auto a = SList!int(2, 3, 4); 752 auto b = 1 ~ a; 753 assert(b == SList!int(1, 2, 3, 4)); 754 } 755 756 @safe unittest 757 { 758 auto a = [1, 2, 3]; 759 auto b = SList!int(4, 5, 6); 760 auto c = a ~ b; 761 assert(c == SList!int(1, 2, 3, 4, 5, 6)); 762 } 763 764 @safe unittest 765 { 766 auto s = SList!int(1, 2, 3, 4); 767 s.insertFront([ 42, 43 ]); 768 assert(s == SList!int(42, 43, 1, 2, 3, 4)); 769 } 770 771 @safe unittest 772 { 773 auto s = SList!int(1, 2, 3); 774 assert(s.removeAny() == 1); 775 assert(s == SList!int(2, 3)); 776 assert(s.stableRemoveAny() == 2); 777 assert(s == SList!int(3)); 778 } 779 780 @safe unittest 781 { 782 import std.algorithm.comparison : equal; 783 784 auto s = SList!int(1, 2, 3); 785 s.removeFront(); 786 assert(equal(s[], [2, 3])); 787 s.stableRemoveFront(); 788 assert(equal(s[], [3])); 789 } 790 791 @safe unittest 792 { 793 auto s = SList!int(1, 2, 3, 4, 5, 6, 7); 794 assert(s.removeFront(3) == 3); 795 assert(s == SList!int(4, 5, 6, 7)); 796 } 797 798 @safe unittest 799 { 800 auto a = SList!int(1, 2, 3); 801 auto b = SList!int(1, 2, 3); 802 assert(a.insertAfter(a[], b[]) == 3); 803 } 804 805 @safe unittest 806 { 807 import std.range : take; 808 auto s = SList!int(1, 2, 3, 4); 809 auto r = take(s[], 2); 810 assert(s.insertAfter(r, 5) == 1); 811 assert(s == SList!int(1, 2, 5, 3, 4)); 812 } 813 814 @safe unittest 815 { 816 import std.algorithm.comparison : equal; 817 import std.range : take; 818 819 // insertAfter documentation example 820 auto sl = SList!string(["a", "b", "d"]); 821 sl.insertAfter(sl[], "e"); // insert at the end (slowest) 822 assert(equal(sl[], ["a", "b", "d", "e"])); 823 sl.insertAfter(take(sl[], 2), "c"); // insert after "b" 824 assert(equal(sl[], ["a", "b", "c", "d", "e"])); 825 } 826 827 @safe unittest 828 { 829 import std.range.primitives; 830 auto s = SList!int(1, 2, 3, 4, 5); 831 auto r = s[]; 832 popFrontN(r, 3); 833 auto r1 = s.linearRemove(r); 834 assert(s == SList!int(1, 2, 3)); 835 assert(r1.empty); 836 } 837 838 @safe unittest 839 { 840 auto s = SList!int(1, 2, 3, 4, 5); 841 auto r = s[]; 842 auto r1 = s.linearRemove(r); 843 assert(s == SList!int()); 844 assert(r1.empty); 845 } 846 847 @safe unittest 848 { 849 import std.algorithm.comparison : equal; 850 import std.range; 851 852 auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); 853 auto r = s[]; 854 popFrontN(r, 3); 855 auto r1 = take(r, 4); 856 assert(equal(r1, [4, 5, 6, 7])); 857 auto r2 = s.linearRemove(r1); 858 assert(s == SList!int(1, 2, 3, 8, 9, 10)); 859 assert(equal(r2, [8, 9, 10])); 860 } 861 862 @safe unittest 863 { 864 import std.range.primitives; 865 auto lst = SList!int(1, 5, 42, 9); 866 assert(!lst.empty); 867 assert(lst.front == 1); 868 assert(walkLength(lst[]) == 4); 869 870 auto lst2 = lst ~ [ 1, 2, 3 ]; 871 assert(walkLength(lst2[]) == 7); 872 873 auto lst3 = lst ~ [ 7 ]; 874 assert(walkLength(lst3[]) == 5); 875 } 876 877 @safe unittest 878 { 879 auto s = make!(SList!int)(1, 2, 3); 880 } 881 882 // https://issues.dlang.org/show_bug.cgi?id=5193 883 @safe unittest 884 { 885 static struct Data 886 { 887 const int val; 888 } 889 SList!Data list; 890 } 891 892 @safe unittest 893 { 894 auto s = SList!int([1, 2, 3]); 895 s.front = 5; //test frontAssign 896 assert(s.front == 5); 897 auto r = s[]; 898 r.front = 1; //test frontAssign 899 assert(r.front == 1); 900 } 901 902 // https://issues.dlang.org/show_bug.cgi?id=14920 903 @safe unittest 904 { 905 SList!int s; 906 s.insertAfter(s[], 1); 907 assert(s.front == 1); 908 } 909 910 // https://issues.dlang.org/show_bug.cgi?id=15659 911 @safe unittest 912 { 913 SList!int s; 914 s.clear(); 915 } 916 917 @safe unittest 918 { 919 SList!int s; 920 s.reverse(); 921 } 922 923 @safe unittest 924 { 925 import std.algorithm.comparison : equal; 926 927 auto s = SList!int([1, 2, 3]); 928 assert(s[].equal([1, 2, 3])); 929 930 s.reverse(); 931 assert(s[].equal([3, 2, 1])); 932 } 933 934 @safe unittest 935 { 936 auto s = SList!int([4, 6, 8, 12, 16]); 937 auto d = s.dup; 938 assert(d !is s); 939 assert(d == s); 940 }