/**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 $(HTTPboost.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 ofelements 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 noelements. Complexity: $(BIGOH 1)     */    @property bool empty() const    {        return _root is null || _first is null;    } /**Duplicates the container. The elements themselves are not transitivelyduplicated. Complexity: $(BIGOH n).     */    @property SList dup()    {        return SList(this[]);    } /**Returns a range that iterates over all elements of the container, inforward 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 itsargument. `opBinaryRight` is only defined if `Stuff` does notdefine `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 avalue convertible to `T` or a range of objects convertible to $(DT). The stable version behaves the same, but guarantees that rangesiterating 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, removesit 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 versionbehaves the same, but guarantees that ranges iterating over thecontainer 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 thecontainer. Unlike the unparameterized versions above, these functionsdo not throw if they could not remove `howMany` elements. Instead,if $(D howMany > n), all elements are removed. The returned value isthe effective number of elements removed. The stable version behavesthe same, but guarantees that ranges iterating over the container arenever 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 rangepreviously extracted from this container. Given that all ranges for alist end at the end of the list, this function essentially appends tothe list and uses `r` as a potentially fast way to reach the lastnode in the list. Ideally `r` is positioned near or at the lastelement of the list. `stuff` can be a value convertible to `T` or a range of objectsconvertible to `T`. The stable version behaves the same, butguarantees that ranges iterating over the container are never

Lines 1–500 of 946. Load more