10SN/A/** 29177SN/AThis module implements a generic doubly-linked list container. 30SN/AIt can be used as a queue, dequeue or stack. 40SN/A 50SN/AThis module is a submodule of $(MREF std, container). 60SN/A 72362SN/ASource: $(PHOBOSSRC std/container/dlist.d) 80SN/A 92362SN/ACopyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders. 100SN/A 110SN/ALicense: Distributed under the Boost Software License, Version 1.0. 120SN/A(See accompanying file LICENSE_1_0.txt or copy at $(HTTP 130SN/Aboost.org/LICENSE_1_0.txt)). 140SN/A 150SN/AAuthors: $(HTTP erdani.com, Andrei Alexandrescu) 160SN/A 170SN/A$(SCRIPT inhibitQuickIndex = 1;) 180SN/A*/ 190SN/Amodule std.container.dlist; 200SN/A 212362SN/A/// 222362SN/A@safe unittest 232362SN/A{ 240SN/A import std.algorithm.comparison : equal; 250SN/A import std.container : DList; 260SN/A 270SN/A auto s = DList!int(1, 2, 3); 280SN/A assert(equal(s[], [1, 2, 3])); 290SN/A 3017178Sprr s.removeFront(); 3117178Sprr assert(equal(s[], [2, 3])); 320SN/A s.removeBack(); 330SN/A assert(equal(s[], [2])); 340SN/A 350SN/A s.insertFront([4, 5]); 360SN/A assert(equal(s[], [4, 5, 2])); 370SN/A s.insertBack([6, 7]); 380SN/A assert(equal(s[], [4, 5, 2, 6, 7])); 390SN/A 400SN/A // If you want to apply range operations, simply slice it. 410SN/A import std.algorithm.searching : countUntil; 420SN/A import std.range : popFrontN, popBackN, walkLength; 430SN/A 440SN/A auto sl = DList!int([1, 2, 3, 4, 5]); 450SN/A assert(countUntil(sl[], 2) == 1); 460SN/A 470SN/A auto r = sl[]; 480SN/A popFrontN(r, 2); 490SN/A popBackN(r, 2); 500SN/A assert(r.equal([3])); 510SN/A assert(walkLength(r) == 1); 520SN/A 530SN/A // DList.Range can be used to remove elements from the list it spans 540SN/A auto nl = DList!int([1, 2, 3, 4, 5]); 550SN/A for (auto rn = nl[]; !rn.empty;) 560SN/A if (rn.front % 2 == 0) 570SN/A nl.popFirstOf(rn); 580SN/A else 590SN/A rn.popFront(); 600SN/A assert(equal(nl[], [1, 3, 5])); 610SN/A auto rs = nl[]; 620SN/A rs.popFront(); 630SN/A nl.remove(rs); 640SN/A assert(equal(nl[], [1])); 650SN/A} 660SN/A 670SN/Aimport std.range.primitives; 680SN/Aimport std.traits; 690SN/A 700SN/Apublic import std.container.util; 710SN/A 720SN/A/+ 730SN/AA DList Node without payload. Used to handle the sentinel node (henceforth "sentinode"). 740SN/A 750SN/AAlso used for parts of the code that don't depend on the payload type. 760SN/A +/ 770SN/Aprivate struct BaseNode 780SN/A{ 790SN/A private BaseNode* _prev = null; 800SN/A private BaseNode* _next = null; 810SN/A 820SN/A /+ 830SN/A Gets the payload associated with this node. 840SN/A This is trusted because all nodes are associated with a payload, even 850SN/A the sentinel node. 860SN/A It is also not possible to mix Nodes in DLists of different types. 870SN/A This function is implemented as a member function here, as UFCS does not 880SN/A work with pointers. 890SN/A +/ 900SN/A ref inout(T) getPayload(T)() inout @trusted 910SN/A { 920SN/A return (cast(inout(DList!T.PayNode)*)&this)._payload; 930SN/A } 940SN/A 950SN/A // Helper: Given nodes p and n, connects them. 960SN/A static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure 970SN/A { 980SN/A p._next = n; 990SN/A n._prev = p; 1000SN/A } 1010SN/A} 10213629Savstepan 10313629Savstepan/+ 1040SN/AThe base DList Range. Contains Range primitives that don't depend on payload type. 1050SN/A +/ 1060SN/Aprivate struct DRange 1070SN/A{ 1080SN/A @safe unittest 1090SN/A { 1100SN/A static assert(isBidirectionalRange!DRange); 1110SN/A static assert(is(ElementType!DRange == BaseNode*)); 1120SN/A } 1130SN/A 1140SN/Anothrow @safe pure: 1150SN/A private BaseNode* _first; 1160SN/A private BaseNode* _last; 1170SN/A 1180SN/A private this(BaseNode* first, BaseNode* last) 1190SN/A { 1200SN/A assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments"); 1210SN/A _first = first; 1220SN/A _last = last; 1230SN/A } 1240SN/A private this(BaseNode* n) 1250SN/A { 1260SN/A this(n, n); 12713629Savstepan } 12813629Savstepan 1290SN/A @property 1300SN/A bool empty() const scope 1310SN/A { 1320SN/A assert((_first is null) == (_last is null), "DList.Range: Invalidated state"); 1330SN/A return !_first; 1340SN/A } 1350SN/A 1360SN/A @property BaseNode* front() return scope 1370SN/A { 1380SN/A assert(!empty, "DList.Range.front: Range is empty"); 1390SN/A return _first; 1400SN/A } 1410SN/A 1420SN/A void popFront() scope 1430SN/A { 14413629Savstepan assert(!empty, "DList.Range.popFront: Range is empty"); 14513629Savstepan if (_first is _last) 1460SN/A { 14712839Sprr _first = _last = null; 1480SN/A } 1499177SN/A else 1500SN/A { 1510SN/A assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state"); 1520SN/A _first = _first._next; 1530SN/A } 1540SN/A } 1550SN/A 1560SN/A @property BaseNode* back() return scope 1570SN/A { 1580SN/A assert(!empty, "DList.Range.front: Range is empty"); 1590SN/A return _last; 1600SN/A } 1610SN/A 16213629Savstepan void popBack() scope 16313629Savstepan { 1640SN/A assert(!empty, "DList.Range.popBack: Range is empty"); 16512839Sprr if (_first is _last) 1660SN/A { 1679177SN/A _first = _last = null; 1680SN/A } 1690SN/A else 1700SN/A { 1710SN/A assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state"); 1720SN/A _last = _last._prev; 1730SN/A } 1740SN/A } 1750SN/A 1760SN/A /// Forward range primitive. 1770SN/A @property DRange save() return scope { return this; } 1780SN/A} 17913629Savstepan 1800SN/A/** 18112839SprrImplements a doubly-linked list. 1820SN/A 1830SN/A`DList` uses reference semantics. 1840SN/A */ 1850SN/Astruct DList(T) 1860SN/A{ 1870SN/A import std.range : Take; 1880SN/A 1890SN/A /* 1900SN/A A Node with a Payload. A PayNode. 1910SN/A */ 1920SN/A struct PayNode 1930SN/A { 1940SN/A BaseNode _base; 1950SN/A alias _base this; 1960SN/A 1970SN/A T _payload = T.init; 19817178Sprr 19917178Sprr this (BaseNode _base, T _payload) 2000SN/A { 20117178Sprr this._base = _base; 2020SN/A this._payload = _payload; 2030SN/A } 2040SN/A 2050SN/A inout(BaseNode)* asBaseNode() inout @trusted 2060SN/A { 2070SN/A return &_base; 2080SN/A } 2090SN/A } 2100SN/A 2110SN/A //The sentinel node 2120SN/A private BaseNode* _root; 2130SN/A 2140SN/A private 2150SN/A { 2160SN/A //Construct as new PayNode, and returns it as a BaseNode. 2170SN/A static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null) 21817178Sprr { 21917178Sprr return (new PayNode(BaseNode(prev, next), arg)).asBaseNode(); 22017178Sprr } 22117178Sprr 22217178Sprr void initialize() nothrow @safe pure 22317178Sprr { 22417178Sprr if (_root) return; 22517178Sprr //Note: We allocate a PayNode for safety reasons. 22617178Sprr _root = (new PayNode()).asBaseNode(); 22717178Sprr _root._next = _root._prev = _root; 22817178Sprr } 2290SN/A ref inout(BaseNode*) _first() @property @safe nothrow pure inout 2300SN/A { 2310SN/A assert(_root, "Root pointer must not be null"); 2320SN/A return _root._next; 2330SN/A } 2340SN/A ref inout(BaseNode*) _last() @property @safe nothrow pure inout 2350SN/A { 2360SN/A assert(_root, "Root pointer must not be null"); 2370SN/A return _root._prev; 2380SN/A } 2390SN/A } //end private 2400SN/A 2410SN/A/** 2420SN/AConstructor taking a number of nodes 2430SN/A */ 2440SN/A this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) 24517178Sprr { 24617178Sprr insertBack(values); 2470SN/A } 24817178Sprr 2490SN/A/** 2500SN/AConstructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives) 2510SN/A */ 2520SN/A this(Stuff)(Stuff stuff) 2530SN/A if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 2540SN/A { 2550SN/A insertBack(stuff); 2560SN/A } 2570SN/A 2580SN/A/** 2590SN/AComparison for equality. 2600SN/A 2610SN/AComplexity: $(BIGOH min(n, n1)) where `n1` is the number of 2620SN/Aelements in `rhs`. 2630SN/A */ 26417178Sprr bool opEquals()(ref const DList rhs) const 26517178Sprr if (is(typeof(front == front))) 26617178Sprr { 26717178Sprr const lhs = this; 26817178Sprr const lroot = lhs._root; 26917178Sprr const rroot = rhs._root; 27017178Sprr 27117178Sprr if (lroot is rroot) return true; 27217178Sprr if (lroot is null) return rroot is rroot._next; 27317178Sprr if (rroot is null) return lroot is lroot._next; 27417178Sprr 2750SN/A const(BaseNode)* pl = lhs._first; 2760SN/A const(BaseNode)* pr = rhs._first; 2770SN/A while (true) 2780SN/A { 2790SN/A if (pl is lroot) return pr is rroot; 2800SN/A if (pr is rroot) return false; 2810SN/A 2820SN/A // !== because of NaN 2830SN/A if (!(pl.getPayload!T() == pr.getPayload!T())) return false; 2840SN/A 2850SN/A pl = pl._next; 2860SN/A pr = pr._next; 2870SN/A } 2880SN/A } 2890SN/A 2900SN/A /** 2910SN/A Defines the container's primary range, which embodies a bidirectional range. 2920SN/A */ 2930SN/A struct Range 2940SN/A { 2950SN/A static assert(isBidirectionalRange!Range); 2960SN/A 2970SN/A DRange _base; 2980SN/A alias _base this; 2990SN/A 3000SN/A private this(BaseNode* first, BaseNode* last) 3010SN/A { 3020SN/A _base = DRange(first, last); 3030SN/A } 3040SN/A private this(BaseNode* n) 3050SN/A { 3060SN/A this(n, n); 3070SN/A } 3080SN/A 3090SN/A @property ref T front() 3100SN/A { 3110SN/A return _base.front.getPayload!T(); 3120SN/A } 3130SN/A 3140SN/A @property ref T back() 3150SN/A { 3160SN/A return _base.back.getPayload!T(); 3170SN/A } 3180SN/A 3190SN/A //Note: shadows base DRange.save. 3200SN/A //Necessary for static covariance. 3210SN/A @property Range save() { return this; } 3220SN/A } 3230SN/A 3240SN/A/** 3250SN/AProperty returning `true` if and only if the container has no 3260SN/Aelements. 3270SN/A 3280SN/AComplexity: $(BIGOH 1) 32917178Sprr */ 33017178Sprr bool empty() @property const nothrow 33117178Sprr { 33217178Sprr return _root is null || _root is _first; 33317178Sprr } 33417178Sprr 33517178Sprr/** 33617178SprrRemoves all contents from the `DList`. 33717178Sprr 33817178SprrPostcondition: `empty` 33917178Sprr 34017178SprrComplexity: $(BIGOH 1) 34117178Sprr */ 3420SN/A void clear() 3430SN/A { 3440SN/A //remove actual elements. 3450SN/A remove(this[]); 3460SN/A } 3470SN/A 3480SN/A/** 3490SN/ADuplicates the container. The elements themselves are not transitively 3500SN/Aduplicated. 3510SN/A 3520SN/AComplexity: $(BIGOH n). 3530SN/A */ 3540SN/A @property DList dup() 35513629Savstepan { 3560SN/A return DList(this[]); 35713629Savstepan } 35813629Savstepan 35913629Savstepan/** 36013629SavstepanReturns a range that iterates over all elements of the container, in 3610SN/Aforward order. 36213629Savstepan 3630SN/AComplexity: $(BIGOH 1) 3640SN/A */ 3650SN/A Range opSlice() 3660SN/A { 3670SN/A if (empty) 36812628Spsadhukhan return Range(null, null); 36912628Spsadhukhan else 3700SN/A return Range(_first, _last); 3710SN/A } 3720SN/A 3730SN/A/** 3740SN/AForward to `opSlice().front`. 3750SN/A 37612628SpsadhukhanComplexity: $(BIGOH 1) 37712628Spsadhukhan */ 3780SN/A @property ref inout(T) front() inout 3790SN/A { 3800SN/A assert(!empty, "DList.front: List is empty"); 3810SN/A return _first.getPayload!T(); 3820SN/A } 3830SN/A 3840SN/A/** 3850SN/AForward to `opSlice().back`. 38617178Sprr 3870SN/AComplexity: $(BIGOH 1) 3880SN/A */ 38912628Spsadhukhan @property ref inout(T) back() inout 39012628Spsadhukhan { 3910SN/A assert(!empty, "DList.back: List is empty"); 3920SN/A return _last.getPayload!T(); 3930SN/A } 3940SN/A 3950SN/A/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 39612628Spsadhukhan/+ BEGIN CONCAT FUNCTIONS HERE +/ 3970SN/A/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 3980SN/A 3990SN/A/** 4000SN/AReturns a new `DList` that's the concatenation of `this` and its 4010SN/Aargument `rhs`. 4020SN/A */ 4030SN/A DList opBinary(string op, Stuff)(Stuff rhs) 4040SN/A if (op == "~" && is(typeof(insertBack(rhs)))) 4050SN/A { 4060SN/A auto ret = this.dup; 4070SN/A ret.insertBack(rhs); 4080SN/A return ret; 4090SN/A } 4100SN/A 4110SN/A/** 4120SN/AReturns a new `DList` that's the concatenation of the argument `lhs` 4130SN/Aand `this`. 4140SN/A */ 4150SN/A DList opBinaryRight(string op, Stuff)(Stuff lhs) 4160SN/A if (op == "~" && is(typeof(insertFront(lhs)))) 41717178Sprr { 4180SN/A auto ret = this.dup; 4190SN/A ret.insertFront(lhs); 4200SN/A return ret; 4210SN/A } 4220SN/A 4230SN/A/** 4240SN/AAppends the contents of the argument `rhs` into `this`. 4250SN/A */ 4260SN/A DList opOpAssign(string op, Stuff)(Stuff rhs) 4270SN/A if (op == "~" && is(typeof(insertBack(rhs)))) 42817178Sprr { 42917178Sprr insertBack(rhs); 43017178Sprr return this; 43117178Sprr } 43217178Sprr 43317178Sprr/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 4340SN/A/+ BEGIN INSERT FUNCTIONS HERE +/ 4350SN/A/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 4360SN/A 4370SN/A/** 4380SN/AInserts `stuff` to the front/back of the container. `stuff` can be a 4390SN/Avalue convertible to `T` or a range of objects convertible to $(D 4400SN/AT). The stable version behaves the same, but guarantees that ranges 4410SN/Aiterating over the container are never invalidated. 4420SN/A 44317178SprrReturns: The number of elements inserted 4440SN/A 4450SN/AComplexity: $(BIGOH log(n)) 44617178Sprr */ 44717178Sprr size_t insertFront(Stuff)(Stuff stuff) 44817178Sprr { 44917178Sprr initialize(); 45017178Sprr return insertAfterNode(_root, stuff); 45117178Sprr } 4520SN/A 4530SN/A /// ditto 4540SN/A size_t insertBack(Stuff)(Stuff stuff) 45512628Spsadhukhan { 4560SN/A initialize(); 45712628Spsadhukhan return insertBeforeNode(_root, stuff); 4580SN/A } 4590SN/A 4600SN/A /// ditto 4610SN/A alias insert = insertBack; 4620SN/A 4630SN/A /// ditto 4640SN/A alias stableInsert = insert; 4650SN/A 4660SN/A /// ditto 4670SN/A alias stableInsertFront = insertFront; 46813629Savstepan 4690SN/A /// ditto 47013629Savstepan alias stableInsertBack = insertBack; 47113629Savstepan 47213629Savstepan/** 47313629SavstepanInserts `stuff` after range `r`, which must be a non-empty range 4740SN/Apreviously extracted from this container. 47513629Savstepan 4760SN/A`stuff` can be a value convertible to `T` or a range of objects 4770SN/Aconvertible to `T`. The stable version behaves the same, but 4780SN/Aguarantees that ranges iterating over the container are never 47917178Sprrinvalidated. 48012628Spsadhukhan 48112628SpsadhukhanReturns: The number of values inserted. 48217178Sprr 48317178SprrComplexity: $(BIGOH k + m), where `k` is the number of elements in 4840SN/A`r` and `m` is the length of `stuff`. 4850SN/A */ 4860SN/A size_t insertBefore(Stuff)(Range r, Stuff stuff) 4870SN/A { 4880SN/A if (r._first) 4890SN/A return insertBeforeNode(r._first, stuff); 4900SN/A else 4910SN/A { 4920SN/A initialize(); 4930SN/A return insertAfterNode(_root, stuff); 4940SN/A } 4950SN/A } 4960SN/A 4970SN/A /// ditto 4980SN/A alias stableInsertBefore = insertBefore; 4990SN/A 5000SN/A /// ditto 5010SN/A size_t insertAfter(Stuff)(Range r, Stuff stuff) 5020SN/A { 5030SN/A if (r._last) 5040SN/A return insertAfterNode(r._last, stuff); 5050SN/A else 5060SN/A { 50712628Spsadhukhan initialize(); 5080SN/A return insertBeforeNode(_root, stuff); 5090SN/A } 51017178Sprr } 5110SN/A 5120SN/A /// ditto 5130SN/A alias stableInsertAfter = insertAfter; 5140SN/A 5150SN/A/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 5160SN/A/+ BEGIN REMOVE FUNCTIONS HERE +/ 5170SN/A/+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/ 5180SN/A 5190SN/A/** 5200SN/APicks one value in an unspecified position in the container, removes 5210SN/Ait from the container, and returns it. The stable version behaves the same, 5220SN/Abut guarantees that ranges iterating over the container are never invalidated. 5230SN/A 5240SN/APrecondition: `!empty` 5250SN/A 5260SN/AReturns: The element removed. 5270SN/A 5280SN/AComplexity: $(BIGOH 1). 5290SN/A */ 5300SN/A T removeAny() 5310SN/A { 5320SN/A import std.algorithm.mutation : move; 5330SN/A 5340SN/A assert(!empty, "DList.removeAny: List is empty"); 5350SN/A auto result = move(back); 5360SN/A removeBack(); 5370SN/A return result; 5380SN/A } 5390SN/A /// ditto 5400SN/A alias stableRemoveAny = removeAny; 5410SN/A 5420SN/A/** 5430SN/ARemoves the value at the front/back of the container. The stable version 5440SN/Abehaves the same, but guarantees that ranges iterating over the 5450SN/Acontainer are never invalidated. 54612628Spsadhukhan 5470SN/APrecondition: `!empty` 5480SN/A 5490SN/AComplexity: $(BIGOH 1). 5500SN/A */ 5510SN/A void removeFront() 5520SN/A { 5530SN/A assert(!empty, "DList.removeFront: List is empty"); 5540SN/A assert(_root is _first._prev, "DList: Inconsistent state"); 5550SN/A BaseNode.connect(_root, _first._next); 5560SN/A } 5570SN/A 5580SN/A /// ditto 5590SN/A alias stableRemoveFront = removeFront; 5600SN/A 5610SN/A /// ditto 5620SN/A void removeBack() 5630SN/A { 5640SN/A assert(!empty, "DList.removeBack: List is empty"); 5650SN/A assert(_last._next is _root, "DList: Inconsistent state"); 5660SN/A BaseNode.connect(_last._prev, _root); 5670SN/A } 5680SN/A 5690SN/A /// ditto 5700SN/A alias stableRemoveBack = removeBack; 5710SN/A 5720SN/A/** 5730SN/ARemoves `howMany` values at the front or back of the 5740SN/Acontainer. Unlike the unparameterized versions above, these functions 5750SN/Ado not throw if they could not remove `howMany` elements. Instead, 5760SN/Aif $(D howMany > n), all elements are removed. The returned value is 5770SN/Athe effective number of elements removed. The stable version behaves 5780SN/Athe same, but guarantees that ranges iterating over the container are 5790SN/Anever invalidated. 5800SN/A 58117178SprrReturns: The number of elements removed 58217178Sprr 58317178SprrComplexity: $(BIGOH howMany). 58417178Sprr */ 58517178Sprr size_t removeFront(size_t howMany) 58617178Sprr { 58717178Sprr if (!_root) return 0; 58817178Sprr size_t result; 5890SN/A auto p = _first; 5900SN/A while (p !is _root && result < howMany) 5910SN/A { 5920SN/A p = p._next; 5930SN/A ++result; 5940SN/A } 5950SN/A BaseNode.connect(_root, p); 5960SN/A return result; 5970SN/A } 5980SN/A 5990SN/A /// ditto 6000SN/A alias stableRemoveFront = removeFront; 6010SN/A 6020SN/A /// ditto 6030SN/A size_t removeBack(size_t howMany) 6040SN/A { 6050SN/A if (!_root) return 0; 6060SN/A size_t result; 6070SN/A auto p = _last; 6080SN/A while (p !is _root && result < howMany) 6090SN/A { 6100SN/A p = p._prev; 6110SN/A ++result; 6120SN/A } 6130SN/A BaseNode.connect(p, _root); 6140SN/A return result; 6150SN/A } 6160SN/A 6170SN/A /// ditto 6180SN/A alias stableRemoveBack = removeBack; 6190SN/A 6200SN/A/** 6210SN/ARemoves all elements belonging to `r`, which must be a range 62213629Savstepanobtained originally from this container. 62313629Savstepan 6240SN/AReturns: A range spanning the remaining elements in the container that 6250SN/Ainitially were right after `r`. 6260SN/A 6270SN/AComplexity: $(BIGOH 1) 6280SN/A */ 6290SN/A Range remove(Range r) 6300SN/A { 6310SN/A if (r.empty) 6320SN/A return r; 6330SN/A 6340SN/A assert(_root !is null, "Cannot remove from an un-initialized List"); 6350SN/A assert(r._first, "Remove: Range is empty"); 6360SN/A 6370SN/A BaseNode.connect(r._first._prev, r._last._next); 6380SN/A auto after = r._last._next; 6390SN/A if (after is _root) 6400SN/A return Range(null, null); 6410SN/A else 6420SN/A return Range(after, _last); 6430SN/A } 6440SN/A 6450SN/A /// ditto 6460SN/A Range linearRemove(Range r) 6470SN/A { 6480SN/A return remove(r); 6490SN/A } 6500SN/A 6510SN/A /// ditto 6520SN/A alias stableRemove = remove; 6530SN/A 6540SN/A/** 6550SN/ARemoves first element of `r`, wich must be a range obtained originally 6560SN/Afrom this container, from both DList instance and range `r`. 6570SN/A 6580SN/ACompexity: $(BIGOH 1) 65913629Savstepan */ 6600SN/A void popFirstOf(ref Range r) 66113629Savstepan { 66213629Savstepan assert(_root !is null, "Cannot remove from an un-initialized List"); 6630SN/A assert(r._first, "popFirstOf: Range is empty"); 6640SN/A auto prev = r._first._prev; 6650SN/A auto next = r._first._next; 6660SN/A r.popFront(); 6670SN/A BaseNode.connect(prev, next); 6680SN/A } 6690SN/A 6700SN/A/** 6710SN/ARemoves last element of `r`, wich must be a range obtained originally 6720SN/Afrom this container, from both DList instance and range `r`. 6730SN/A 67413629SavstepanCompexity: $(BIGOH 1) 6750SN/A */ 6760SN/A void popLastOf(ref Range r) 6770SN/A { 6780SN/A assert(_root !is null, "Cannot remove from an un-initialized List"); 6790SN/A assert(r._first, "popLastOf: Range is empty"); 6800SN/A auto prev = r._last._prev; 6810SN/A auto next = r._last._next; 6820SN/A r.popBack(); 6830SN/A BaseNode.connect(prev, next); 6840SN/A } 6850SN/A 6860SN/A/** 68713629Savstepan`linearRemove` functions as `remove`, but also accepts ranges that are 6880SN/Aresult the of a `take` operation. This is a convenient way to remove a 6890SN/Afixed amount of elements from the range. 6900SN/A 6910SN/AComplexity: $(BIGOH r.walkLength) 6920SN/A */ 693 Range linearRemove(Take!Range r) 694 { 695 assert(_root !is null, "Cannot remove from an un-initialized List"); 696 assert(r.source._first, "Remove: Range is empty"); 697 698 BaseNode* first = r.source._first; 699 BaseNode* last = null; 700 do 701 { 702 last = r.source._first; 703 r.popFront(); 704 } while ( !r.empty ); 705 706 return remove(Range(first, last)); 707 } 708 709 /// ditto 710 alias stableLinearRemove = linearRemove; 711 712/** 713Removes the first occurence of an element from the list in linear time. 714 715Returns: True if the element existed and was successfully removed, false otherwise. 716 717Params: 718 value = value of the node to be removed 719 720Complexity: $(BIGOH n) 721 */ 722 bool linearRemoveElement(T value) 723 { 724 auto n1 = findNodeByValue(_root, value); 725 if (n1) 726 { 727 auto n2 = n1._next._next; 728 BaseNode.connect(n1, n2); 729 return true; 730 } 731 732 return false; 733 } 734 735 736private: 737 738 BaseNode* findNodeByValue(BaseNode* n, T value) 739 { 740 if (!n) return null; 741 auto ahead = n._next; 742 while (ahead && ahead.getPayload!T() != value) 743 { 744 n = ahead; 745 ahead = n._next; 746 if (ahead == _last._next) return null; 747 } 748 return n; 749 } 750 751 // Helper: Inserts stuff before the node n. 752 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 753 if (isImplicitlyConvertible!(Stuff, T)) 754 { 755 auto p = createNode(stuff, n._prev, n); 756 n._prev._next = p; 757 n._prev = p; 758 return 1; 759 } 760 // ditto 761 size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff) 762 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 763 { 764 if (stuff.empty) return 0; 765 size_t result; 766 Range r = createRange(stuff, result); 767 BaseNode.connect(n._prev, r._first); 768 BaseNode.connect(r._last, n); 769 return result; 770 } 771 772 // Helper: Inserts stuff after the node n. 773 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 774 if (isImplicitlyConvertible!(Stuff, T)) 775 { 776 auto p = createNode(stuff, n, n._next); 777 n._next._prev = p; 778 n._next = p; 779 return 1; 780 } 781 // ditto 782 size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff) 783 if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T)) 784 { 785 if (stuff.empty) return 0; 786 size_t result; 787 Range r = createRange(stuff, result); 788 BaseNode.connect(r._last, n._next); 789 BaseNode.connect(n, r._first); 790 return result; 791 } 792 793 // Helper: Creates a chain of nodes from the range stuff. 794 Range createRange(Stuff)(ref Stuff stuff, ref size_t result) 795 { 796 BaseNode* first = createNode(stuff.front); 797 BaseNode* last = first; 798 ++result; 799 for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() ) 800 { 801 auto p = createNode(stuff.front, last); 802 last = last._next = p; 803 ++result; 804 } 805 return Range(first, last); 806 } 807} 808 809@safe unittest 810{ 811 import std.algorithm.comparison : equal; 812 813 auto e = DList!int(); 814 auto b = e.linearRemoveElement(1); 815 assert(b == false); 816 assert(e.empty()); 817 auto a = DList!int(-1, 1, 2, 1, 3, 4); 818 b = a.linearRemoveElement(1); 819 assert(equal(a[], [-1, 2, 1, 3, 4])); 820 assert(b == true); 821 b = a.linearRemoveElement(-1); 822 assert(b == true); 823 assert(equal(a[], [2, 1, 3, 4])); 824 b = a.linearRemoveElement(1); 825 assert(b == true); 826 assert(equal(a[], [2, 3, 4])); 827 b = a.linearRemoveElement(2); 828 assert(b == true); 829 b = a.linearRemoveElement(20); 830 assert(b == false); 831 assert(equal(a[], [3, 4])); 832 b = a.linearRemoveElement(4); 833 assert(b == true); 834 assert(equal(a[], [3])); 835 b = a.linearRemoveElement(3); 836 assert(b == true); 837 assert(a.empty()); 838 a.linearRemoveElement(3); 839} 840 841@safe unittest 842{ 843 import std.algorithm.comparison : equal; 844 845 //Tests construction signatures 846 alias IntList = DList!int; 847 auto a0 = IntList(); 848 auto a1 = IntList(0); 849 auto a2 = IntList(0, 1); 850 auto a3 = IntList([0]); 851 auto a4 = IntList([0, 1]); 852 853 assert(a0[].empty); 854 assert(equal(a1[], [0])); 855 assert(equal(a2[], [0, 1])); 856 assert(equal(a3[], [0])); 857 assert(equal(a4[], [0, 1])); 858} 859 860@safe unittest 861{ 862 import std.algorithm.comparison : equal; 863 864 alias IntList = DList!int; 865 IntList list = IntList([0,1,2,3]); 866 assert(equal(list[],[0,1,2,3])); 867 list.insertBack([4,5,6,7]); 868 assert(equal(list[],[0,1,2,3,4,5,6,7])); 869 870 list = IntList(); 871 list.insertFront([0,1,2,3]); 872 assert(equal(list[],[0,1,2,3])); 873 list.insertFront([4,5,6,7]); 874 assert(equal(list[],[4,5,6,7,0,1,2,3])); 875} 876 877@safe unittest 878{ 879 import std.algorithm.comparison : equal; 880 import std.range : take; 881 882 alias IntList = DList!int; 883 IntList list = IntList([0,1,2,3]); 884 auto range = list[]; 885 for ( ; !range.empty; range.popFront()) 886 { 887 int item = range.front; 888 if (item == 2) 889 { 890 list.stableLinearRemove(take(range, 1)); 891 break; 892 } 893 } 894 assert(equal(list[],[0,1,3])); 895 896 list = IntList([0,1,2,3]); 897 range = list[]; 898 for ( ; !range.empty; range.popFront()) 899 { 900 int item = range.front; 901 if (item == 2) 902 { 903 list.stableLinearRemove(take(range,2)); 904 break; 905 } 906 } 907 assert(equal(list[],[0,1])); 908 909 list = IntList([0,1,2,3]); 910 range = list[]; 911 for ( ; !range.empty; range.popFront()) 912 { 913 int item = range.front; 914 if (item == 0) 915 { 916 list.stableLinearRemove(take(range,2)); 917 break; 918 } 919 } 920 assert(equal(list[],[2,3])); 921 922 list = IntList([0,1,2,3]); 923 range = list[]; 924 for ( ; !range.empty; range.popFront()) 925 { 926 int item = range.front; 927 if (item == 1) 928 { 929 list.stableLinearRemove(take(range,2)); 930 break; 931 } 932 } 933 assert(equal(list[],[0,3])); 934} 935 936@safe unittest 937{ 938 import std.algorithm.comparison : equal; 939 940 auto dl = DList!int([1, 2, 3, 4, 5]); 941 auto r = dl[]; 942 r.popFront(); 943 dl.popFirstOf(r); 944 assert(equal(dl[], [1, 3, 4, 5])); 945 assert(equal(r, [3, 4, 5])); 946 r.popBack(); 947 dl.popLastOf(r); 948 assert(equal(dl[], [1, 3, 5])); 949 assert(equal(r, [3])); 950 dl = DList!int([0]); 951 r = dl[]; 952 dl.popFirstOf(r); 953 assert(dl.empty); 954 dl = DList!int([0]); 955 r = dl[]; 956 dl.popLastOf(r); 957 assert(dl.empty); 958} 959 960@safe unittest 961{ 962 import std.algorithm.comparison : equal; 963 964 auto dl = DList!string(["a", "b", "d"]); 965 dl.insertAfter(dl[], "e"); // insert at the end 966 assert(equal(dl[], ["a", "b", "d", "e"])); 967 auto dlr = dl[]; 968 dlr.popBack(); dlr.popBack(); 969 dl.insertAfter(dlr, "c"); // insert after "b" 970 assert(equal(dl[], ["a", "b", "c", "d", "e"])); 971} 972 973@safe unittest 974{ 975 import std.algorithm.comparison : equal; 976 977 auto dl = DList!string(["a", "b", "d"]); 978 dl.insertBefore(dl[], "e"); // insert at the front 979 assert(equal(dl[], ["e", "a", "b", "d"])); 980 auto dlr = dl[]; 981 dlr.popFront(); dlr.popFront(); 982 dl.insertBefore(dlr, "c"); // insert before "b" 983 assert(equal(dl[], ["e", "a", "c", "b", "d"])); 984} 985 986@safe unittest 987{ 988 auto d = DList!int([1, 2, 3]); 989 d.front = 5; //test frontAssign 990 assert(d.front == 5); 991 auto r = d[]; 992 r.back = 1; 993 assert(r.back == 1); 994} 995 996// https://issues.dlang.org/show_bug.cgi?id=8895 997@safe unittest 998{ 999 auto a = make!(DList!int)(1,2,3,4); 1000 auto b = make!(DList!int)(1,2,3,4); 1001 auto c = make!(DList!int)(1,2,3,5); 1002 auto d = make!(DList!int)(1,2,3,4,5); 1003 assert(a == b); // this better terminate! 1004 assert(!(a == c)); 1005 assert(!(a == d)); 1006} 1007 1008@safe unittest 1009{ 1010 auto d = DList!int([1, 2, 3]); 1011 d.front = 5; //test frontAssign 1012 assert(d.front == 5); 1013 auto r = d[]; 1014 r.back = 1; 1015 assert(r.back == 1); 1016} 1017 1018@safe unittest 1019{ 1020 auto a = DList!int(); 1021 assert(a.removeFront(10) == 0); 1022 a.insert([1, 2, 3]); 1023 assert(a.removeFront(10) == 3); 1024 assert(a[].empty); 1025} 1026 1027@safe unittest 1028{ 1029 import std.algorithm.comparison : equal; 1030 1031 //Verify all flavors of ~ 1032 auto a = DList!int(); 1033 auto b = DList!int(); 1034 auto c = DList!int([1, 2, 3]); 1035 auto d = DList!int([4, 5, 6]); 1036 1037 assert((a ~ b[])[].empty); 1038 assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6])); 1039 assert(c[].equal([1, 2, 3])); 1040 assert(d[].equal([4, 5, 6])); 1041 1042 assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6])); 1043 assert(c[].equal([1, 2, 3])); 1044 assert(d[].equal([4, 5, 6])); 1045 1046 a~=c[]; 1047 assert(a[].equal([1, 2, 3])); 1048 assert(c[].equal([1, 2, 3])); 1049 1050 a~=d[]; 1051 assert(a[].equal([1, 2, 3, 4, 5, 6])); 1052 assert(d[].equal([4, 5, 6])); 1053 1054 a~=[7, 8, 9]; 1055 assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9])); 1056 1057 //trick test: 1058 auto r = c[]; 1059 c.removeFront(); 1060 c.removeBack(); 1061} 1062 1063@safe unittest 1064{ 1065 import std.algorithm.comparison : equal; 1066 1067 // https://issues.dlang.org/show_bug.cgi?id=8905 1068 auto a = DList!int([1, 2, 3, 4]); 1069 auto r = a[]; 1070 a.stableRemoveBack(); 1071 a.stableInsertBack(7); 1072 assert(a[].equal([1, 2, 3, 7])); 1073} 1074 1075// https://issues.dlang.org/show_bug.cgi?id=12566 1076@safe unittest 1077{ 1078 auto dl2 = DList!int([2,7]); 1079 dl2.removeFront(); 1080 assert(dl2[].walkLength == 1); 1081 dl2.removeBack(); 1082 assert(dl2.empty, "not empty?!"); 1083} 1084 1085// https://issues.dlang.org/show_bug.cgi?id=13076 1086@safe unittest 1087{ 1088 DList!int list; 1089 assert(list.empty); 1090 list.clear(); 1091} 1092 1093// https://issues.dlang.org/show_bug.cgi?id=13425 1094@safe unittest 1095{ 1096 import std.range : drop, take; 1097 auto list = DList!int([1,2,3,4,5]); 1098 auto r = list[].drop(4); // r is a view of the last element of list 1099 assert(r.front == 5 && r.walkLength == 1); 1100 r = list.linearRemove(r.take(1)); 1101 assert(r.empty); // fails 1102} 1103 1104// https://issues.dlang.org/show_bug.cgi?id=14300 1105@safe unittest 1106{ 1107 interface ITest {} 1108 static class Test : ITest {} 1109 1110 DList!ITest().insertBack(new Test()); 1111} 1112 1113// https://issues.dlang.org/show_bug.cgi?id=15263 1114@safe unittest 1115{ 1116 import std.range : iota; 1117 auto a = DList!int(); 1118 a.insertFront(iota(0, 5)); // can insert range with non-ref front 1119 assert(a.front == 0 && a.back == 4); 1120} 1121