libphobos/src/std/container/slist.d - rust-lang/gcc - Git at Google

 /**
 This module implements a singly-linked list container.
 It can be used as a stack.

 This module is a submodule of $(MREF std, container).

 Source: $(PHOBOSSRC std/container/slist.d)

 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

 License: Distributed under the Boost Software License, Version 1.0.
 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
 boost.org/LICENSE_1_0.txt)).

 Authors: $(HTTP erdani.com, Andrei Alexandrescu)

 $(SCRIPT inhibitQuickIndex = 1;)
 */
 module std.container.slist;

 ///
 @safe unittest
 {
     import std.algorithm.comparison : equal;
     import std.container : SList;

     auto s = SList!int(1, 2, 3);
     assert(equal(s[], [1, 2, 3]));

     s.removeFront();
     assert(equal(s[], [2, 3]));

     s.insertFront([5, 6]);
     assert(equal(s[], [5, 6, 2, 3]));

     // If you want to apply range operations, simply slice it.
     import std.algorithm.searching : countUntil;
     import std.range : popFrontN, walkLength;

     auto sl = SList!int(1, 2, 3, 4, 5);
     assert(countUntil(sl[], 2) == 1);

     auto r = sl[];
     popFrontN(r, 2);
     assert(walkLength(r) == 3);
 }

 public import std.container.util;

 /**
    Implements a simple and fast singly-linked list.
    It can be used as a stack.

    `SList` uses reference semantics.
  */
 struct SList(T)
 if (!is(T == shared))
 {
     import std.exception : enforce;
     import std.range : Take;
     import std.range.primitives : isInputRange, isForwardRange, ElementType;
     import std.traits : isImplicitlyConvertible;

     private struct Node
     {
         Node * _next;
         T _payload;
     }
     private struct NodeWithoutPayload
     {
         Node* _next;
     }
     static assert(NodeWithoutPayload._next.offsetof == Node._next.offsetof);

     private Node * _root;

     private void initialize() @trusted nothrow pure
     {
         if (_root) return;
         _root = cast (Node*) new NodeWithoutPayload();
     }

     private ref inout(Node*) _first() @property @safe nothrow pure inout
     {
         assert(_root, "root pointer must not be null");
         return _root._next;
     }

     private static Node * findLastNode(Node * n)
     {
         assert(n, "Node n pointer must not be null");
         auto ahead = n._next;
         while (ahead)
         {
             n = ahead;
             ahead = n._next;
         }
         return n;
     }

     private static Node * findLastNode(Node * n, size_t limit)
     {
         assert(n, "Node n pointer must not be null");
         assert(limit, "limit must be greater than 0");
         auto ahead = n._next;
         while (ahead)
         {
             if (!--limit) break;
             n = ahead;
             ahead = n._next;
         }
         return n;
     }

     private static Node * findNode(Node * n, Node * findMe)
     {
         assert(n, "Node n pointer must not be null");
         auto ahead = n._next;
         while (ahead != findMe)
         {
             n = ahead;
             enforce(n);
             ahead = n._next;
         }
         return n;
     }

     private static Node* findNodeByValue(Node* n, T value)
     {
         if (!n) return null;
         auto ahead = n._next;
         while (ahead && ahead._payload != value)
         {
             n = ahead;
             ahead = n._next;
         }
         return n;
     }

     private static auto createNodeChain(Stuff)(Stuff stuff)
     if (isImplicitlyConvertible!(Stuff, T))
     {
         import std.range : only;
         return createNodeChain(only(stuff));
     }

     private static auto createNodeChain(Stuff)(Stuff stuff)
     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
     {
         static struct Chain
         {
             Node* first;
             Node* last;
             size_t length;
         }

         Chain ch;

         foreach (item; stuff)
         {
             auto newNode = new Node(null, item);
             (ch.first ? ch.last._next : ch.first) = newNode;
             ch.last = newNode;
             ++ch.length;
         }

         return ch;
     }

     private static size_t insertAfterNode(Stuff)(Node* n, Stuff stuff)
     {
         auto ch = createNodeChain(stuff);

         if (!ch.length) return 0;

         ch.last._next = n._next;
         n._next = ch.first;

         return ch.length;
     }

 /**
 Constructor taking a number of nodes
      */
     this(U)(U[] values...)
     if (isImplicitlyConvertible!(U, T))
     {
         insertFront(values);
     }

 /**
 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
      */
     this(Stuff)(Stuff stuff)
     if (isInputRange!Stuff
             && isImplicitlyConvertible!(ElementType!Stuff, T)
             && !is(Stuff == T[]))
     {
         insertFront(stuff);
     }

 /**
 Comparison for equality.

 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of
 elements in `rhs`.
      */
     bool opEquals(const SList rhs) const
     {
         return opEquals(rhs);
     }

     /// ditto
     bool opEquals(ref const SList rhs) const
     {
         if (_root is rhs._root) return true;
         if (_root is null) return rhs._root is null || rhs._first is null;
         if (rhs._root is null) return _root is null || _first is null;

         const(Node) * n1 = _first, n2 = rhs._first;

         for (;; n1 = n1._next, n2 = n2._next)
         {
             if (!n1) return !n2;
             if (!n2 || n1._payload != n2._payload) return false;
         }
     }

 /**
 Defines the container's primary range, which embodies a forward range.
      */
     struct Range
     {
         private Node * _head;
         private this(Node * p) { _head = p; }

         /// Input range primitives.
         @property bool empty() const { return !_head; }

         /// ditto
         @property ref T front()
         {
             assert(!empty, "SList.Range.front: Range is empty");
             return _head._payload;
         }

         /// ditto
         void popFront()
         {
             assert(!empty, "SList.Range.popFront: Range is empty");
             _head = _head._next;
         }

         /// Forward range primitive.
         @property Range save() { return this; }

         T moveFront()
         {
             import std.algorithm.mutation : move;

             assert(!empty, "SList.Range.moveFront: Range is empty");
             return move(_head._payload);
         }

         bool sameHead(Range rhs)
         {
             return _head && _head == rhs._head;
         }
     }

     @safe unittest
     {
         static assert(isForwardRange!Range);
     }

 /**
 Property returning `true` if and only if the container has no
 elements.

 Complexity: $(BIGOH 1)
      */
     @property bool empty() const
     {
         return _root is null || _first is null;
     }

 /**
 Duplicates the container. The elements themselves are not transitively
 duplicated.

 Complexity: $(BIGOH n).
      */
     @property SList dup()
     {
         return SList(this[]);
     }

 /**
 Returns a range that iterates over all elements of the container, in
 forward order.

 Complexity: $(BIGOH 1)
      */
     Range opSlice()
     {
         if (empty)
             return Range(null);
         else
             return Range(_first);
     }

 /**
 Forward to `opSlice().front`.

 Complexity: $(BIGOH 1)
      */
     @property ref T front()
     {
         assert(!empty, "SList.front: List is empty");
         return _first._payload;
     }

     @safe unittest
     {
         auto s = SList!int(1, 2, 3);
         s.front = 42;
         assert(s == SList!int(42, 2, 3));
     }

 /**
 Returns a new `SList` that's the concatenation of `this` and its
 argument. `opBinaryRight` is only defined if `Stuff` does not
 define `opBinary`.
      */
     SList opBinary(string op, Stuff)(Stuff rhs)
     if (op == "~" && is(typeof(SList(rhs))))
     {
         import std.range : chain, only;

         static if (isInputRange!Stuff)
             alias r = rhs;
         else
             auto r = only(rhs);

         return SList(this[].chain(r));
     }

     /// ditto
     SList opBinaryRight(string op, Stuff)(Stuff lhs)
     if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))))
     {
         import std.range : chain, only;

         static if (isInputRange!Stuff)
             alias r = lhs;
         else
             auto r = only(lhs);

         return SList(r.chain(this[]));
     }

 /**
 Removes all contents from the `SList`.

 Postcondition: `empty`

 Complexity: $(BIGOH 1)
      */
     void clear()
     {
         if (_root)
             _first = null;
     }

 /**
 Reverses SList in-place. Performs no memory allocation.

 Complexity: $(BIGOH n)
      */
     void reverse()
     {
         if (!empty)
         {
             Node* prev;
             while (_first)
             {
                 auto next = _first._next;
                 _first._next = prev;
                 prev = _first;
                 _first = next;
             }
             _first = prev;
         }
     }

 /**
 Inserts `stuff` to the front of the container. `stuff` can be a
 value convertible to `T` or a range of objects convertible to $(D
 T). The stable version behaves the same, but guarantees that ranges
 iterating over the container are never invalidated.

 Returns: The number of elements inserted

 Complexity: $(BIGOH m), where `m` is the length of `stuff`
      */
     size_t insertFront(Stuff)(Stuff stuff)
     if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T))
     {
         initialize();
         return insertAfterNode(_root, stuff);
     }

     /// ditto
     alias insert = insertFront;

     /// ditto
     alias stableInsert = insert;

     /// ditto
     alias stableInsertFront = insertFront;

 /**
 Picks one value in an unspecified position in the container, removes
 it from the container, and returns it. The stable version behaves the same,
 but guarantees that ranges iterating over the container are never invalidated.

 Precondition: `!empty`

 Returns: The element removed.

 Complexity: $(BIGOH 1).
      */
     T removeAny()
     {
         import std.algorithm.mutation : move;

         assert(!empty, "SList.removeAny: List is empty");
         auto result = move(_first._payload);
         _first = _first._next;
         return result;
     }
     /// ditto
     alias stableRemoveAny = removeAny;

 /**
 Removes the value at the front of the container. The stable version
 behaves the same, but guarantees that ranges iterating over the
 container are never invalidated.

 Precondition: `!empty`

 Complexity: $(BIGOH 1).
      */
     void removeFront()
     {
         assert(!empty, "SList.removeFront: List is empty");
         _first = _first._next;
     }

     /// ditto
     alias stableRemoveFront = removeFront;

 /**
 Removes `howMany` values at the front or back of the
 container. Unlike the unparameterized versions above, these functions
 do not throw if they could not remove `howMany` elements. Instead,
 if $(D howMany > n), all elements are removed. The returned value is
 the effective number of elements removed. The stable version behaves
 the same, but guarantees that ranges iterating over the container are
 never invalidated.

 Returns: The number of elements removed

 Complexity: $(BIGOH howMany * log(n)).
      */
     size_t removeFront(size_t howMany)
     {
         size_t result;
         while (_first && result < howMany)
         {
             _first = _first._next;
             ++result;
         }
         return result;
     }

     /// ditto
     alias stableRemoveFront = removeFront;

 /**
 Inserts `stuff` after range `r`, which must be a range
 previously extracted from this container. Given that all ranges for a
 list end at the end of the list, this function essentially appends to
 the list and uses `r` as a potentially fast way to reach the last
 node in the list. Ideally `r` is positioned near or at the last
 element of the list.

 `stuff` can be a value convertible to `T` or a range of objects
 convertible to `T`. The stable version behaves the same, but
 guarantees that ranges iterating over the container are never
 invalidated.

 Returns: The number of values inserted.

 Complexity: $(BIGOH k + m), where `k` is the number of elements in
 `r` and `m` is the length of `stuff`.

 Example:
 --------------------
 auto sl = SList!string(["a", "b", "d"]);
 sl.insertAfter(sl[], "e"); // insert at the end (slowest)
 assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
 sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b"
 assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));
 --------------------
      */

     size_t insertAfter(Stuff)(Range r, Stuff stuff)
     if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T))
     {
         initialize();
         if (!_first)
         {
             enforce(!r._head);
             return insertFront(stuff);
         }
         enforce(r._head);
         auto n = findLastNode(r._head);
         return insertAfterNode(n, stuff);
     }

 /**
 Similar to `insertAfter` above, but accepts a range bounded in
 count. This is important for ensuring fast insertions in the middle of
 the list.  For fast insertions after a specified position `r`, use
 $(D insertAfter(take(r, 1), stuff)). The complexity of that operation
 only depends on the number of elements in `stuff`.

 Precondition: $(D r.original.empty || r.maxLength > 0)

 Returns: The number of values inserted.

 Complexity: $(BIGOH k + m), where `k` is the number of elements in
 `r` and `m` is the length of `stuff`.
      */
     size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
     if (isInputRange!Stuff || isImplicitlyConvertible!(Stuff, T))
     {
         auto orig = r.source;
         if (!orig._head)
         {
             // Inserting after a null range counts as insertion to the
             // front
             return insertFront(stuff);
         }
         enforce(!r.empty);
         // Find the last valid element in the range
         foreach (i; 1 .. r.maxLength)
         {
             if (!orig._head._next) break;
             orig.popFront();
         }
         // insert here
         return insertAfterNode(orig._head, stuff);
     }

 /// ditto
     alias stableInsertAfter = insertAfter;

 /**
 Removes a range from the list in linear time.

 Returns: An empty range.

 Complexity: $(BIGOH n)
      */
     Range linearRemove(Range r)
     {
         if (!_first)
         {
             enforce(!r._head);
             return this[];
         }
         auto n = findNode(_root, r._head);
         n._next = null;
         return Range(null);
     }

 /**
 Removes a `Take!Range` from the list in linear time.

 Returns: A range comprehending the elements after the removed range.

 Complexity: $(BIGOH n)
      */
     Range linearRemove(Take!Range r)
     {
         auto orig = r.source;
         // We have something to remove here
         if (orig._head == _first)
         {
             // remove straight from the head of the list
             for (; !r.empty; r.popFront())
             {
                 removeFront();
             }
             return this[];
         }
         if (!r.maxLength)
         {
             // Nothing to remove, return the range itself
             return orig;
         }
         // Remove from somewhere in the middle of the list
         enforce(_first);
         auto n1 = findNode(_root, orig._head);
         auto n2 = findLastNode(orig._head, r.maxLength);
         n1._next = n2._next;
         return Range(n1._next);
     }

 /// ditto
     alias stableLinearRemove = linearRemove;

 /**
 Removes the first occurence of an element from the list in linear time.

 Returns: True if the element existed and was successfully removed, false otherwise.

 Params:
     value = value of the node to be removed

 Complexity: $(BIGOH n)
      */
     bool linearRemoveElement(T value)
     {
         auto n1 = findNodeByValue(_root, value);

         if (n1 && n1._next)
         {
             n1._next = n1._next._next;
             return true;
         }

         return false;
     }
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;

     auto e = SList!int();
     auto b = e.linearRemoveElement(2);
     assert(b == false);
     assert(e.empty());
     auto a = SList!int(-1, 1, 2, 1, 3, 4);
     b = a.linearRemoveElement(1);
     assert(equal(a[], [-1, 2, 1, 3, 4]));
     assert(b == true);
     b = a.linearRemoveElement(-1);
     assert(b == true);
     assert(equal(a[], [2, 1, 3, 4]));
     b = a.linearRemoveElement(1);
     assert(b == true);
     assert(equal(a[], [2, 3, 4]));
     b = a.linearRemoveElement(2);
     assert(b == true);
     b = a.linearRemoveElement(20);
     assert(b == false);
     assert(equal(a[], [3, 4]));
     b = a.linearRemoveElement(4);
     assert(b == true);
     assert(equal(a[], [3]));
     b = a.linearRemoveElement(3);
     assert(b == true);
     assert(a.empty());
     a.linearRemoveElement(3);
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;

     auto a = SList!int(5);
     auto b = a;
     auto r = a[];
     a.insertFront(1);
     b.insertFront(2);
     assert(equal(a[], [2, 1, 5]));
     assert(equal(b[], [2, 1, 5]));
     r.front = 9;
     assert(equal(a[], [2, 1, 9]));
     assert(equal(b[], [2, 1, 9]));
 }

 @safe unittest
 {
     auto s = SList!int(1, 2, 3);
     auto n = s.findLastNode(s._root);
     assert(n && n._payload == 3);
 }

 @safe unittest
 {
     import std.range.primitives;
     auto s = SList!int(1, 2, 5, 10);
     assert(walkLength(s[]) == 4);
 }

 @safe unittest
 {
     import std.range : take;
     auto src = take([0, 1, 2, 3], 3);
     auto s = SList!int(src);
     assert(s == SList!int(0, 1, 2));
 }

 @safe unittest
 {
     auto a = SList!int();
     auto b = SList!int();
     auto c = a ~ b[];
     assert(c.empty);
 }

 @safe unittest
 {
     auto a = SList!int(1, 2, 3);
     auto b = SList!int(4, 5, 6);
     auto c = a ~ b[];
     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 }

 @safe unittest
 {
     auto a = SList!int(1, 2, 3);
     auto b = [4, 5, 6];
     auto c = a ~ b;
     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 }

 @safe unittest
 {
     auto a = SList!int(1, 2, 3);
     auto c = a ~ 4;
     assert(c == SList!int(1, 2, 3, 4));
 }

 @safe unittest
 {
     auto a = SList!int(2, 3, 4);
     auto b = 1 ~ a;
     assert(b == SList!int(1, 2, 3, 4));
 }

 @safe unittest
 {
     auto a = [1, 2, 3];
     auto b = SList!int(4, 5, 6);
     auto c = a ~ b;
     assert(c == SList!int(1, 2, 3, 4, 5, 6));
 }

 @safe unittest
 {
     auto s = SList!int(1, 2, 3, 4);
     s.insertFront([ 42, 43 ]);
     assert(s == SList!int(42, 43, 1, 2, 3, 4));
 }

 @safe unittest
 {
     auto s = SList!int(1, 2, 3);
     assert(s.removeAny() == 1);
     assert(s == SList!int(2, 3));
     assert(s.stableRemoveAny() == 2);
     assert(s == SList!int(3));
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;

     auto s = SList!int(1, 2, 3);
     s.removeFront();
     assert(equal(s[], [2, 3]));
     s.stableRemoveFront();
     assert(equal(s[], [3]));
 }

 @safe unittest
 {
     auto s = SList!int(1, 2, 3, 4, 5, 6, 7);
     assert(s.removeFront(3) == 3);
     assert(s == SList!int(4, 5, 6, 7));
 }

 @safe unittest
 {
     auto a = SList!int(1, 2, 3);
     auto b = SList!int(1, 2, 3);
     assert(a.insertAfter(a[], b[]) == 3);
 }

 @safe unittest
 {
     import std.range : take;
     auto s = SList!int(1, 2, 3, 4);
     auto r = take(s[], 2);
     assert(s.insertAfter(r, 5) == 1);
     assert(s == SList!int(1, 2, 5, 3, 4));
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;
     import std.range : take;

     // insertAfter documentation example
     auto sl = SList!string(["a", "b", "d"]);
     sl.insertAfter(sl[], "e"); // insert at the end (slowest)
     assert(equal(sl[], ["a", "b", "d", "e"]));
     sl.insertAfter(take(sl[], 2), "c"); // insert after "b"
     assert(equal(sl[], ["a", "b", "c", "d", "e"]));
 }

 @safe unittest
 {
     import std.range.primitives;
     auto s = SList!int(1, 2, 3, 4, 5);
     auto r = s[];
     popFrontN(r, 3);
     auto r1 = s.linearRemove(r);
     assert(s == SList!int(1, 2, 3));
     assert(r1.empty);
 }

 @safe unittest
 {
     auto s = SList!int(1, 2, 3, 4, 5);
     auto r = s[];
     auto r1 = s.linearRemove(r);
     assert(s == SList!int());
     assert(r1.empty);
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;
     import std.range;

     auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
     auto r = s[];
     popFrontN(r, 3);
     auto r1 = take(r, 4);
     assert(equal(r1, [4, 5, 6, 7]));
     auto r2 = s.linearRemove(r1);
     assert(s == SList!int(1, 2, 3, 8, 9, 10));
     assert(equal(r2, [8, 9, 10]));
 }

 @safe unittest
 {
     import std.range.primitives;
     auto lst = SList!int(1, 5, 42, 9);
     assert(!lst.empty);
     assert(lst.front == 1);
     assert(walkLength(lst[]) == 4);

     auto lst2 = lst ~ [ 1, 2, 3 ];
     assert(walkLength(lst2[]) == 7);

     auto lst3 = lst ~ [ 7 ];
     assert(walkLength(lst3[]) == 5);
 }

 @safe unittest
 {
     auto s = make!(SList!int)(1, 2, 3);
 }

 // https://issues.dlang.org/show_bug.cgi?id=5193
 @safe unittest
 {
     static struct Data
     {
         const int val;
     }
     SList!Data list;
 }

 @safe unittest
 {
     auto s = SList!int([1, 2, 3]);
     s.front = 5; //test frontAssign
     assert(s.front == 5);
     auto r = s[];
     r.front = 1; //test frontAssign
     assert(r.front == 1);
 }

 // https://issues.dlang.org/show_bug.cgi?id=14920
 @safe unittest
 {
     SList!int s;
     s.insertAfter(s[], 1);
     assert(s.front == 1);
 }

 // https://issues.dlang.org/show_bug.cgi?id=15659
 @safe unittest
 {
     SList!int s;
     s.clear();
 }

 @safe unittest
 {
     SList!int s;
     s.reverse();
 }

 @safe unittest
 {
     import std.algorithm.comparison : equal;

     auto s = SList!int([1, 2, 3]);
     assert(s[].equal([1, 2, 3]));

     s.reverse();
     assert(s[].equal([3, 2, 1]));
 }

 @safe unittest
 {
     auto s = SList!int([4, 6, 8, 12, 16]);
     auto d = s.dup;
     assert(d !is s);
     assert(d == s);
 }
	/**
	This module implements a singly-linked list container.
	It can be used as a stack.

	This module is a submodule of $(MREF std, container).

	Source: $(PHOBOSSRC std/container/slist.d)

	Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.

	License: Distributed under the Boost Software License, Version 1.0.
	(See accompanying file LICENSE_1_0.txt or copy at $(HTTP
	boost.org/LICENSE_1_0.txt)).

	Authors: $(HTTP erdani.com, Andrei Alexandrescu)

	$(SCRIPT inhibitQuickIndex = 1;)
	*/
	module std.container.slist;

	///
	@safe unittest
	{
	import std.algorithm.comparison : equal;
	import std.container : SList;

	auto s = SList!int(1, 2, 3);
	assert(equal(s[], [1, 2, 3]));

	s.removeFront();
	assert(equal(s[], [2, 3]));

	s.insertFront([5, 6]);
	assert(equal(s[], [5, 6, 2, 3]));

	// If you want to apply range operations, simply slice it.
	import std.algorithm.searching : countUntil;
	import std.range : popFrontN, walkLength;

	auto sl = SList!int(1, 2, 3, 4, 5);
	assert(countUntil(sl[], 2) == 1);

	auto r = sl[];
	popFrontN(r, 2);
	assert(walkLength(r) == 3);
	}

	public import std.container.util;

	/**
	Implements a simple and fast singly-linked list.
	It can be used as a stack.

	`SList` uses reference semantics.
	*/
	struct SList(T)
	if (!is(T == shared))
	{
	import std.exception : enforce;
	import std.range : Take;
	import std.range.primitives : isInputRange, isForwardRange, ElementType;
	import std.traits : isImplicitlyConvertible;

	private struct Node
	{
	Node * _next;
	T _payload;
	}
	private struct NodeWithoutPayload
	{
	Node* _next;
	}
	static assert(NodeWithoutPayload._next.offsetof == Node._next.offsetof);

	private Node * _root;

	private void initialize() @trusted nothrow pure
	{
	if (_root) return;
	_root = cast (Node*) new NodeWithoutPayload();
	}

	private ref inout(Node*) _first() @property @safe nothrow pure inout
	{
	assert(_root, "root pointer must not be null");
	return _root._next;
	}

	private static Node * findLastNode(Node * n)
	{
	assert(n, "Node n pointer must not be null");
	auto ahead = n._next;
	while (ahead)
	{
	n = ahead;
	ahead = n._next;
	}
	return n;
	}

	private static Node * findLastNode(Node * n, size_t limit)
	{
	assert(n, "Node n pointer must not be null");
	assert(limit, "limit must be greater than 0");
	auto ahead = n._next;
	while (ahead)
	{
	if (!--limit) break;
	n = ahead;
	ahead = n._next;
	}
	return n;
	}

	private static Node * findNode(Node * n, Node * findMe)
	{
	assert(n, "Node n pointer must not be null");
	auto ahead = n._next;
	while (ahead != findMe)
	{
	n = ahead;
	enforce(n);
	ahead = n._next;
	}
	return n;
	}

	private static Node* findNodeByValue(Node* n, T value)
	{
	if (!n) return null;
	auto ahead = n._next;
	while (ahead && ahead._payload != value)
	{
	n = ahead;
	ahead = n._next;
	}
	return n;
	}

	private static auto createNodeChain(Stuff)(Stuff stuff)
	if (isImplicitlyConvertible!(Stuff, T))
	{
	import std.range : only;
	return createNodeChain(only(stuff));
	}

	private static auto createNodeChain(Stuff)(Stuff stuff)
	if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
	{
	static struct Chain
	{
	Node* first;
	Node* last;
	size_t length;
	}

	Chain ch;

	foreach (item; stuff)
	{
	auto newNode = new Node(null, item);
	(ch.first ? ch.last._next : ch.first) = newNode;
	ch.last = newNode;
	++ch.length;
	}

	return ch;
	}

	private static size_t insertAfterNode(Stuff)(Node* n, Stuff stuff)
	{
	auto ch = createNodeChain(stuff);

	if (!ch.length) return 0;

	ch.last._next = n._next;
	n._next = ch.first;

	return ch.length;
	}

	/**
	Constructor taking a number of nodes
	*/
	this(U)(U[] values...)
	if (isImplicitlyConvertible!(U, T))
	{
	insertFront(values);
	}

	/**
	Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
	*/
	this(Stuff)(Stuff stuff)
	if (isInputRange!Stuff
	&& isImplicitlyConvertible!(ElementType!Stuff, T)
	&& !is(Stuff == T[]))
	{
	insertFront(stuff);
	}

	/**
	Comparison for equality.

	Complexity: $(BIGOH min(n, n1)) where `n1` is the number of
	elements in `rhs`.
	*/
	bool opEquals(const SList rhs) const
	{
	return opEquals(rhs);
	}

	/// ditto
	bool opEquals(ref const SList rhs) const
	{
	if (_root is rhs._root) return true;
	if (_root is null) return rhs._root is null \|\| rhs._first is null;
	if (rhs._root is null) return _root is null \|\| _first is null;

	const(Node) * n1 = _first, n2 = rhs._first;

	for (;; n1 = n1._next, n2 = n2._next)
	{
	if (!n1) return !n2;
	if (!n2 \|\| n1._payload != n2._payload) return false;
	}
	}

	/**
	Defines the container's primary range, which embodies a forward range.
	*/
	struct Range
	{
	private Node * _head;
	private this(Node * p) { _head = p; }

	/// Input range primitives.
	@property bool empty() const { return !_head; }

	/// ditto
	@property ref T front()
	{
	assert(!empty, "SList.Range.front: Range is empty");
	return _head._payload;
	}

	/// ditto
	void popFront()
	{
	assert(!empty, "SList.Range.popFront: Range is empty");
	_head = _head._next;
	}

	/// Forward range primitive.
	@property Range save() { return this; }

	T moveFront()
	{
	import std.algorithm.mutation : move;

	assert(!empty, "SList.Range.moveFront: Range is empty");
	return move(_head._payload);
	}

	bool sameHead(Range rhs)
	{
	return _head && _head == rhs._head;
	}
	}

	@safe unittest
	{
	static assert(isForwardRange!Range);
	}

	/**
	Property returning `true` if and only if the container has no
	elements.

	Complexity: $(BIGOH 1)
	*/
	@property bool empty() const
	{
	return _root is null \|\| _first is null;
	}

	/**
	Duplicates the container. The elements themselves are not transitively
	duplicated.

	Complexity: $(BIGOH n).
	*/
	@property SList dup()
	{
	return SList(this[]);
	}

	/**
	Returns a range that iterates over all elements of the container, in
	forward order.

	Complexity: $(BIGOH 1)
	*/
	Range opSlice()
	{
	if (empty)
	return Range(null);
	else
	return Range(_first);
	}

	/**
	Forward to `opSlice().front`.

	Complexity: $(BIGOH 1)
	*/
	@property ref T front()
	{
	assert(!empty, "SList.front: List is empty");
	return _first._payload;
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3);
	s.front = 42;
	assert(s == SList!int(42, 2, 3));
	}

	/**
	Returns a new `SList` that's the concatenation of `this` and its
	argument. `opBinaryRight` is only defined if `Stuff` does not
	define `opBinary`.
	*/
	SList opBinary(string op, Stuff)(Stuff rhs)
	if (op == "~" && is(typeof(SList(rhs))))
	{
	import std.range : chain, only;

	static if (isInputRange!Stuff)
	alias r = rhs;
	else
	auto r = only(rhs);

	return SList(this[].chain(r));
	}

	/// ditto
	SList opBinaryRight(string op, Stuff)(Stuff lhs)
	if (op == "~" && !is(typeof(lhs.opBinary!"~"(this))) && is(typeof(SList(lhs))))
	{
	import std.range : chain, only;

	static if (isInputRange!Stuff)
	alias r = lhs;
	else
	auto r = only(lhs);

	return SList(r.chain(this[]));
	}

	/**
	Removes all contents from the `SList`.

	Postcondition: `empty`

	Complexity: $(BIGOH 1)
	*/
	void clear()
	{
	if (_root)
	_first = null;
	}

	/**
	Reverses SList in-place. Performs no memory allocation.

	Complexity: $(BIGOH n)
	*/
	void reverse()
	{
	if (!empty)
	{
	Node* prev;
	while (_first)
	{
	auto next = _first._next;
	_first._next = prev;
	prev = _first;
	_first = next;
	}
	_first = prev;
	}
	}

	/**
	Inserts `stuff` to the front of the container. `stuff` can be a
	value convertible to `T` or a range of objects convertible to $(D
	T). The stable version behaves the same, but guarantees that ranges
	iterating over the container are never invalidated.

	Returns: The number of elements inserted

	Complexity: $(BIGOH m), where `m` is the length of `stuff`
	*/
	size_t insertFront(Stuff)(Stuff stuff)
	if (isInputRange!Stuff \|\| isImplicitlyConvertible!(Stuff, T))
	{
	initialize();
	return insertAfterNode(_root, stuff);
	}

	/// ditto
	alias insert = insertFront;

	/// ditto
	alias stableInsert = insert;

	/// ditto
	alias stableInsertFront = insertFront;

	/**
	Picks one value in an unspecified position in the container, removes
	it from the container, and returns it. The stable version behaves the same,
	but guarantees that ranges iterating over the container are never invalidated.

	Precondition: `!empty`

	Returns: The element removed.

	Complexity: $(BIGOH 1).
	*/
	T removeAny()
	{
	import std.algorithm.mutation : move;

	assert(!empty, "SList.removeAny: List is empty");
	auto result = move(_first._payload);
	_first = _first._next;
	return result;
	}
	/// ditto
	alias stableRemoveAny = removeAny;

	/**
	Removes the value at the front of the container. The stable version
	behaves the same, but guarantees that ranges iterating over the
	container are never invalidated.

	Precondition: `!empty`

	Complexity: $(BIGOH 1).
	*/
	void removeFront()
	{
	assert(!empty, "SList.removeFront: List is empty");
	_first = _first._next;
	}

	/// ditto
	alias stableRemoveFront = removeFront;

	/**
	Removes `howMany` values at the front or back of the
	container. Unlike the unparameterized versions above, these functions
	do not throw if they could not remove `howMany` elements. Instead,
	if $(D howMany > n), all elements are removed. The returned value is
	the effective number of elements removed. The stable version behaves
	the same, but guarantees that ranges iterating over the container are
	never invalidated.

	Returns: The number of elements removed

	Complexity: $(BIGOH howMany * log(n)).
	*/
	size_t removeFront(size_t howMany)
	{
	size_t result;
	while (_first && result < howMany)
	{
	_first = _first._next;
	++result;
	}
	return result;
	}

	/// ditto
	alias stableRemoveFront = removeFront;

	/**
	Inserts `stuff` after range `r`, which must be a range
	previously extracted from this container. Given that all ranges for a
	list end at the end of the list, this function essentially appends to
	the list and uses `r` as a potentially fast way to reach the last
	node in the list. Ideally `r` is positioned near or at the last
	element of the list.

	`stuff` can be a value convertible to `T` or a range of objects
	convertible to `T`. The stable version behaves the same, but
	guarantees that ranges iterating over the container are never
	invalidated.

	Returns: The number of values inserted.

	Complexity: $(BIGOH k + m), where `k` is the number of elements in
	`r` and `m` is the length of `stuff`.

	Example:
	--------------------
	auto sl = SList!string(["a", "b", "d"]);
	sl.insertAfter(sl[], "e"); // insert at the end (slowest)
	assert(std.algorithm.equal(sl[], ["a", "b", "d", "e"]));
	sl.insertAfter(std.range.take(sl[], 2), "c"); // insert after "b"
	assert(std.algorithm.equal(sl[], ["a", "b", "c", "d", "e"]));
	--------------------
	*/

	size_t insertAfter(Stuff)(Range r, Stuff stuff)
	if (isInputRange!Stuff \|\| isImplicitlyConvertible!(Stuff, T))
	{
	initialize();
	if (!_first)
	{
	enforce(!r._head);
	return insertFront(stuff);
	}
	enforce(r._head);
	auto n = findLastNode(r._head);
	return insertAfterNode(n, stuff);
	}

	/**
	Similar to `insertAfter` above, but accepts a range bounded in
	count. This is important for ensuring fast insertions in the middle of
	the list. For fast insertions after a specified position `r`, use
	$(D insertAfter(take(r, 1), stuff)). The complexity of that operation
	only depends on the number of elements in `stuff`.

	Precondition: $(D r.original.empty \|\| r.maxLength > 0)

	Returns: The number of values inserted.

	Complexity: $(BIGOH k + m), where `k` is the number of elements in
	`r` and `m` is the length of `stuff`.
	*/
	size_t insertAfter(Stuff)(Take!Range r, Stuff stuff)
	if (isInputRange!Stuff \|\| isImplicitlyConvertible!(Stuff, T))
	{
	auto orig = r.source;
	if (!orig._head)
	{
	// Inserting after a null range counts as insertion to the
	// front
	return insertFront(stuff);
	}
	enforce(!r.empty);
	// Find the last valid element in the range
	foreach (i; 1 .. r.maxLength)
	{
	if (!orig._head._next) break;
	orig.popFront();
	}
	// insert here
	return insertAfterNode(orig._head, stuff);
	}

	/// ditto
	alias stableInsertAfter = insertAfter;

	/**
	Removes a range from the list in linear time.

	Returns: An empty range.

	Complexity: $(BIGOH n)
	*/
	Range linearRemove(Range r)
	{
	if (!_first)
	{
	enforce(!r._head);
	return this[];
	}
	auto n = findNode(_root, r._head);
	n._next = null;
	return Range(null);
	}

	/**
	Removes a `Take!Range` from the list in linear time.

	Returns: A range comprehending the elements after the removed range.

	Complexity: $(BIGOH n)
	*/
	Range linearRemove(Take!Range r)
	{
	auto orig = r.source;
	// We have something to remove here
	if (orig._head == _first)
	{
	// remove straight from the head of the list
	for (; !r.empty; r.popFront())
	{
	removeFront();
	}
	return this[];
	}
	if (!r.maxLength)
	{
	// Nothing to remove, return the range itself
	return orig;
	}
	// Remove from somewhere in the middle of the list
	enforce(_first);
	auto n1 = findNode(_root, orig._head);
	auto n2 = findLastNode(orig._head, r.maxLength);
	n1._next = n2._next;
	return Range(n1._next);
	}

	/// ditto
	alias stableLinearRemove = linearRemove;

	/**
	Removes the first occurence of an element from the list in linear time.

	Returns: True if the element existed and was successfully removed, false otherwise.

	Params:
	value = value of the node to be removed

	Complexity: $(BIGOH n)
	*/
	bool linearRemoveElement(T value)
	{
	auto n1 = findNodeByValue(_root, value);

	if (n1 && n1._next)
	{
	n1._next = n1._next._next;
	return true;
	}

	return false;
	}
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;

	auto e = SList!int();
	auto b = e.linearRemoveElement(2);
	assert(b == false);
	assert(e.empty());
	auto a = SList!int(-1, 1, 2, 1, 3, 4);
	b = a.linearRemoveElement(1);
	assert(equal(a[], [-1, 2, 1, 3, 4]));
	assert(b == true);
	b = a.linearRemoveElement(-1);
	assert(b == true);
	assert(equal(a[], [2, 1, 3, 4]));
	b = a.linearRemoveElement(1);
	assert(b == true);
	assert(equal(a[], [2, 3, 4]));
	b = a.linearRemoveElement(2);
	assert(b == true);
	b = a.linearRemoveElement(20);
	assert(b == false);
	assert(equal(a[], [3, 4]));
	b = a.linearRemoveElement(4);
	assert(b == true);
	assert(equal(a[], [3]));
	b = a.linearRemoveElement(3);
	assert(b == true);
	assert(a.empty());
	a.linearRemoveElement(3);
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;

	auto a = SList!int(5);
	auto b = a;
	auto r = a[];
	a.insertFront(1);
	b.insertFront(2);
	assert(equal(a[], [2, 1, 5]));
	assert(equal(b[], [2, 1, 5]));
	r.front = 9;
	assert(equal(a[], [2, 1, 9]));
	assert(equal(b[], [2, 1, 9]));
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3);
	auto n = s.findLastNode(s._root);
	assert(n && n._payload == 3);
	}

	@safe unittest
	{
	import std.range.primitives;
	auto s = SList!int(1, 2, 5, 10);
	assert(walkLength(s[]) == 4);
	}

	@safe unittest
	{
	import std.range : take;
	auto src = take([0, 1, 2, 3], 3);
	auto s = SList!int(src);
	assert(s == SList!int(0, 1, 2));
	}

	@safe unittest
	{
	auto a = SList!int();
	auto b = SList!int();
	auto c = a ~ b[];
	assert(c.empty);
	}

	@safe unittest
	{
	auto a = SList!int(1, 2, 3);
	auto b = SList!int(4, 5, 6);
	auto c = a ~ b[];
	assert(c == SList!int(1, 2, 3, 4, 5, 6));
	}

	@safe unittest
	{
	auto a = SList!int(1, 2, 3);
	auto b = [4, 5, 6];
	auto c = a ~ b;
	assert(c == SList!int(1, 2, 3, 4, 5, 6));
	}

	@safe unittest
	{
	auto a = SList!int(1, 2, 3);
	auto c = a ~ 4;
	assert(c == SList!int(1, 2, 3, 4));
	}

	@safe unittest
	{
	auto a = SList!int(2, 3, 4);
	auto b = 1 ~ a;
	assert(b == SList!int(1, 2, 3, 4));
	}

	@safe unittest
	{
	auto a = [1, 2, 3];
	auto b = SList!int(4, 5, 6);
	auto c = a ~ b;
	assert(c == SList!int(1, 2, 3, 4, 5, 6));
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3, 4);
	s.insertFront([ 42, 43 ]);
	assert(s == SList!int(42, 43, 1, 2, 3, 4));
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3);
	assert(s.removeAny() == 1);
	assert(s == SList!int(2, 3));
	assert(s.stableRemoveAny() == 2);
	assert(s == SList!int(3));
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;

	auto s = SList!int(1, 2, 3);
	s.removeFront();
	assert(equal(s[], [2, 3]));
	s.stableRemoveFront();
	assert(equal(s[], [3]));
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3, 4, 5, 6, 7);
	assert(s.removeFront(3) == 3);
	assert(s == SList!int(4, 5, 6, 7));
	}

	@safe unittest
	{
	auto a = SList!int(1, 2, 3);
	auto b = SList!int(1, 2, 3);
	assert(a.insertAfter(a[], b[]) == 3);
	}

	@safe unittest
	{
	import std.range : take;
	auto s = SList!int(1, 2, 3, 4);
	auto r = take(s[], 2);
	assert(s.insertAfter(r, 5) == 1);
	assert(s == SList!int(1, 2, 5, 3, 4));
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;
	import std.range : take;

	// insertAfter documentation example
	auto sl = SList!string(["a", "b", "d"]);
	sl.insertAfter(sl[], "e"); // insert at the end (slowest)
	assert(equal(sl[], ["a", "b", "d", "e"]));
	sl.insertAfter(take(sl[], 2), "c"); // insert after "b"
	assert(equal(sl[], ["a", "b", "c", "d", "e"]));
	}

	@safe unittest
	{
	import std.range.primitives;
	auto s = SList!int(1, 2, 3, 4, 5);
	auto r = s[];
	popFrontN(r, 3);
	auto r1 = s.linearRemove(r);
	assert(s == SList!int(1, 2, 3));
	assert(r1.empty);
	}

	@safe unittest
	{
	auto s = SList!int(1, 2, 3, 4, 5);
	auto r = s[];
	auto r1 = s.linearRemove(r);
	assert(s == SList!int());
	assert(r1.empty);
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;
	import std.range;

	auto s = SList!int(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
	auto r = s[];
	popFrontN(r, 3);
	auto r1 = take(r, 4);
	assert(equal(r1, [4, 5, 6, 7]));
	auto r2 = s.linearRemove(r1);
	assert(s == SList!int(1, 2, 3, 8, 9, 10));
	assert(equal(r2, [8, 9, 10]));
	}

	@safe unittest
	{
	import std.range.primitives;
	auto lst = SList!int(1, 5, 42, 9);
	assert(!lst.empty);
	assert(lst.front == 1);
	assert(walkLength(lst[]) == 4);

	auto lst2 = lst ~ [ 1, 2, 3 ];
	assert(walkLength(lst2[]) == 7);

	auto lst3 = lst ~ [ 7 ];
	assert(walkLength(lst3[]) == 5);
	}

	@safe unittest
	{
	auto s = make!(SList!int)(1, 2, 3);
	}

	// https://issues.dlang.org/show_bug.cgi?id=5193
	@safe unittest
	{
	static struct Data
	{
	const int val;
	}
	SList!Data list;
	}

	@safe unittest
	{
	auto s = SList!int([1, 2, 3]);
	s.front = 5; //test frontAssign
	assert(s.front == 5);
	auto r = s[];
	r.front = 1; //test frontAssign
	assert(r.front == 1);
	}

	// https://issues.dlang.org/show_bug.cgi?id=14920
	@safe unittest
	{
	SList!int s;
	s.insertAfter(s[], 1);
	assert(s.front == 1);
	}

	// https://issues.dlang.org/show_bug.cgi?id=15659
	@safe unittest
	{
	SList!int s;
	s.clear();
	}

	@safe unittest
	{
	SList!int s;
	s.reverse();
	}

	@safe unittest
	{
	import std.algorithm.comparison : equal;

	auto s = SList!int([1, 2, 3]);
	assert(s[].equal([1, 2, 3]));

	s.reverse();
	assert(s[].equal([3, 2, 1]));
	}

	@safe unittest
	{
	auto s = SList!int([4, 6, 8, 12, 16]);
	auto d = s.dup;
	assert(d !is s);
	assert(d == s);
	}