/**This module implements a generic doubly-linked list container.It can be used as a queue, dequeue or stack. This module is a submodule of $(MREF std, container). Source: $(PHOBOSSRC std/container/dlist.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.dlist; ///@safe unittest{    import std.algorithm.comparison : equal;    import std.container : DList;     auto s = DList!int(1, 2, 3);    assert(equal(s[], [1, 2, 3]));     s.removeFront();    assert(equal(s[], [2, 3]));    s.removeBack();    assert(equal(s[], [2]));     s.insertFront([4, 5]);    assert(equal(s[], [4, 5, 2]));    s.insertBack([6, 7]);    assert(equal(s[], [4, 5, 2, 6, 7]));     // If you want to apply range operations, simply slice it.    import std.algorithm.searching : countUntil;    import std.range : popFrontN, popBackN, walkLength;     auto sl = DList!int([1, 2, 3, 4, 5]);    assert(countUntil(sl[], 2) == 1);     auto r = sl[];    popFrontN(r, 2);    popBackN(r, 2);    assert(r.equal([3]));    assert(walkLength(r) == 1);     // DList.Range can be used to remove elements from the list it spans    auto nl = DList!int([1, 2, 3, 4, 5]);    for (auto rn = nl[]; !rn.empty;)        if (rn.front % 2 == 0)            nl.popFirstOf(rn);        else            rn.popFront();    assert(equal(nl[], [1, 3, 5]));    auto rs = nl[];    rs.popFront();    nl.remove(rs);    assert(equal(nl[], [1]));} import std.range.primitives;import std.traits; public import std.container.util; /+A DList Node without payload. Used to handle the sentinel node (henceforth "sentinode"). Also used for parts of the code that don't depend on the payload type. +/private struct BaseNode{    private BaseNode* _prev = null;    private BaseNode* _next = null;     /+    Gets the payload associated with this node.    This is trusted because all nodes are associated with a payload, even    the sentinel node.    It is also not possible to mix Nodes in DLists of different types.    This function is implemented as a member function here, as UFCS does not    work with pointers.    +/    ref inout(T) getPayload(T)() inout @trusted    {        return (cast(inout(DList!T.PayNode)*)&this)._payload;    }     // Helper: Given nodes p and n, connects them.    static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure    {        p._next = n;        n._prev = p;    }} /+The base DList Range. Contains Range primitives that don't depend on payload type. +/private struct DRange{    @safe unittest    {        static assert(isBidirectionalRange!DRange);        static assert(is(ElementType!DRange == BaseNode*));    } nothrow @safe @nogc pure:    private BaseNode* _first;    private BaseNode* _last;     private this(BaseNode* first, BaseNode* last)    {        assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments");        _first = first;        _last = last;    }    private this(BaseNode* n)    {        this(n, n);    }     @property    bool empty() const scope    {        assert((_first is null) == (_last is null), "DList.Range: Invalidated state");        return !_first;    }     @property BaseNode* front() return scope    {        assert(!empty, "DList.Range.front: Range is empty");        return _first;    }     void popFront() scope    {        assert(!empty, "DList.Range.popFront: Range is empty");        if (_first is _last)        {            _first = _last = null;        }        else        {            assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state");            _first = _first._next;        }    }     @property BaseNode* back() return scope    {        assert(!empty, "DList.Range.front: Range is empty");        return _last;    }     void popBack() scope    {        assert(!empty, "DList.Range.popBack: Range is empty");        if (_first is _last)        {            _first = _last = null;        }        else        {            assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state");            _last = _last._prev;        }    }     /// Forward range primitive.    @property DRange save() return scope { return this; }} /**Implements a doubly-linked list. `DList` uses reference semantics. */struct DList(T){    import std.range : Take;    import std.traits : isMutable;     /*    A Node with a Payload. A PayNode.     */    struct PayNode    {        BaseNode _base;        alias _base this;         T _payload = T.init;         this (BaseNode _base, T _payload)        {            import std.algorithm.mutation : move;             this._base = _base;            this._payload = move(_payload);        }         inout(BaseNode)* asBaseNode() inout @trusted        {            return &_base;        }    }     //The sentinel node    private BaseNode* _root;   private  {    //Construct as new PayNode, and returns it as a BaseNode.    static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null)    {        import std.algorithm.mutation : move;         static if (isMutable!Stuff)            return (new PayNode(BaseNode(prev, next), move(arg))).asBaseNode();        else            return (new PayNode(BaseNode(prev, next), arg)).asBaseNode();    }     void initialize() nothrow @safe pure    {        if (_root) return;        //Note: We allocate a PayNode for safety reasons.        _root = (new PayNode()).asBaseNode();        _root._next = _root._prev = _root;    }    ref inout(BaseNode*) _first() @property @safe nothrow pure inout    {        assert(_root, "Root pointer must not be null");        return _root._next;    }    ref inout(BaseNode*) _last() @property @safe nothrow pure inout    {        assert(_root, "Root pointer must not be null");        return _root._prev;    }  } //end private /**Constructor taking a number of nodes     */    this(U)(U[] values...)    if (isImplicitlyConvertible!(U, T))    {        insertBack(values);    } /**Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)     */    this(Stuff)(Stuff stuff)    if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))    {        insertBack(stuff);    } /**Comparison for equality. Complexity: $(BIGOH min(n, n1)) where `n1` is the number ofelements in `rhs`.     */    bool opEquals()(ref const DList rhs) const    if (is(typeof(front == front)))    {        const lhs = this;        const lroot = lhs._root;        const rroot = rhs._root;         if (lroot is rroot) return true;        if (lroot is null) return rroot is rroot._next;        if (rroot is null) return lroot is lroot._next;         const(BaseNode)* pl = lhs._first;        const(BaseNode)* pr = rhs._first;        while (true)        {            if (pl is lroot) return pr is rroot;            if (pr is rroot) return false;             // !== because of NaN            if (!(pl.getPayload!T() == pr.getPayload!T())) return false;             pl = pl._next;            pr = pr._next;        }    }     /**    Defines the container's primary range, which embodies a bidirectional range.     */    struct Range    {        static assert(isBidirectionalRange!Range);         DRange _base;        alias _base this;         private this(BaseNode* first, BaseNode* last)        {            _base = DRange(first, last);        }        private this(BaseNode* n)        {            this(n, n);        }         @property ref T front()        {            return _base.front.getPayload!T();        }         @property ref T back()        {            return _base.back.getPayload!T();        }         //Note: shadows base DRange.save.        //Necessary for static covariance.        @property Range save() { return this; }    } /**Property returning `true` if and only if the container has noelements. Complexity: $(BIGOH 1)     */    bool empty() @property const nothrow    {        return _root is null || _root is _first;    } /**Removes all contents from the `DList`. Postcondition: `empty` Complexity: $(BIGOH 1)     */    void clear()    {        //remove actual elements.        remove(this[]);    } /**Duplicates the container. The elements themselves are not transitivelyduplicated. Complexity: $(BIGOH n).     */    @property DList dup()    {        return DList(this[]);    } /**Returns a range that iterates over all elements of the container, inforward order. Complexity: $(BIGOH 1)     */    Range opSlice()    {        if (empty)            return Range(null, null);        else            return Range(_first, _last);    } /**Forward to `opSlice().front`. Complexity: $(BIGOH 1)     */    @property ref inout(T) front() inout    {        assert(!empty, "DList.front: List is empty");        return _first.getPayload!T();    } /**Forward to `opSlice().back`. Complexity: $(BIGOH 1)     */    @property ref inout(T) back() inout    {        assert(!empty, "DList.back: List is empty");        return _last.getPayload!T();    } /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +//+                        BEGIN CONCAT FUNCTIONS HERE                         +//+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ /**Returns a new `DList` that's the concatenation of `this` and itsargument `rhs`.     */    DList opBinary(string op, Stuff)(Stuff rhs)    if (op == "~" && is(typeof(insertBack(rhs))))    {        auto ret = this.dup;        ret.insertBack(rhs);        return ret;    } /**Returns a new `DList` that's the concatenation of the argument `lhs`and `this`.     */    DList opBinaryRight(string op, Stuff)(Stuff lhs)    if (op == "~" && is(typeof(insertFront(lhs))))    {        auto ret = this.dup;        ret.insertFront(lhs);        return ret;    } /**Appends the contents of the argument `rhs` into `this`.     */    DList opOpAssign(string op, Stuff)(Stuff rhs)    if (op == "~" && is(typeof(insertBack(rhs))))    {        insertBack(rhs);        return this;    } /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +//+                        BEGIN INSERT FUNCTIONS HERE                         +//+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ /**Inserts `stuff` to the front/back 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)    {        initialize();        return insertAfterNode(_root, stuff);    }     /// ditto    size_t insertBack(Stuff)(Stuff stuff)    {        initialize();        return insertBeforeNode(_root, stuff);    }     /// ditto    alias insert = insertBack;     /// ditto    alias stableInsert = insert;     /// ditto    alias stableInsertFront = insertFront;     /// ditto    alias stableInsertBack = insertBack; /**Inserts `stuff` after range `r`, which must be a non-empty rangepreviously extracted from this container. `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 neverinvalidated. 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 insertBefore(Stuff)(Range r, Stuff stuff)    {        if (r._first)            return insertBeforeNode(r._first, stuff);        else        {

Lines 1–500 of 1174. Load more