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 }