1 /**
2 This module implements a generic doubly-linked list container.
3 It can be used as a queue, dequeue or stack.
4 
5 This module is a submodule of $(MREF std, container).
6 
7 Source: $(PHOBOSSRC std/container/dlist.d)
8 
9 Copyright: 2010- Andrei Alexandrescu. All rights reserved by the respective holders.
10 
11 License: Distributed under the Boost Software License, Version 1.0.
12 (See accompanying file LICENSE_1_0.txt or copy at $(HTTP
13 boost.org/LICENSE_1_0.txt)).
14 
15 Authors: $(HTTP erdani.com, Andrei Alexandrescu)
16 
17 $(SCRIPT inhibitQuickIndex = 1;)
18 */
19 module std.container.dlist;
20 
21 ///
22 @safe unittest
23 {
24     import std.algorithm.comparison : equal;
25     import std.container : DList;
26 
27     auto s = DList!int(1, 2, 3);
28     assert(equal(s[], [1, 2, 3]));
29 
30     s.removeFront();
31     assert(equal(s[], [2, 3]));
32     s.removeBack();
33     assert(equal(s[], [2]));
34 
35     s.insertFront([4, 5]);
36     assert(equal(s[], [4, 5, 2]));
37     s.insertBack([6, 7]);
38     assert(equal(s[], [4, 5, 2, 6, 7]));
39 
40     // If you want to apply range operations, simply slice it.
41     import std.algorithm.searching : countUntil;
42     import std.range : popFrontN, popBackN, walkLength;
43 
44     auto sl = DList!int([1, 2, 3, 4, 5]);
45     assert(countUntil(sl[], 2) == 1);
46 
47     auto r = sl[];
48     popFrontN(r, 2);
49     popBackN(r, 2);
50     assert(r.equal([3]));
51     assert(walkLength(r) == 1);
52 
53     // DList.Range can be used to remove elements from the list it spans
54     auto nl = DList!int([1, 2, 3, 4, 5]);
55     for (auto rn = nl[]; !rn.empty;)
56         if (rn.front % 2 == 0)
57             nl.popFirstOf(rn);
58         else
59             rn.popFront();
60     assert(equal(nl[], [1, 3, 5]));
61     auto rs = nl[];
62     rs.popFront();
63     nl.remove(rs);
64     assert(equal(nl[], [1]));
65 }
66 
67 import std.range.primitives;
68 import std.traits;
69 
70 public import std.container.util;
71 
72 /+
73 A DList Node without payload. Used to handle the sentinel node (henceforth "sentinode").
74 
75 Also used for parts of the code that don't depend on the payload type.
76  +/
77 private struct BaseNode
78 {
79     private BaseNode* _prev = null;
80     private BaseNode* _next = null;
81 
82     /+
83     Gets the payload associated with this node.
84     This is trusted because all nodes are associated with a payload, even
85     the sentinel node.
86     It is also not possible to mix Nodes in DLists of different types.
87     This function is implemented as a member function here, as UFCS does not
88     work with pointers.
89     +/
90     ref inout(T) getPayload(T)() inout @trusted
91     {
92         return (cast(inout(DList!T.PayNode)*)&this)._payload;
93     }
94 
95     // Helper: Given nodes p and n, connects them.
96     static void connect(BaseNode* p, BaseNode* n) @safe nothrow pure
97     {
98         p._next = n;
99         n._prev = p;
100     }
101 }
102 
103 /+
104 The base DList Range. Contains Range primitives that don't depend on payload type.
105  +/
106 private struct DRange
107 {
108     @safe unittest
109     {
110         static assert(isBidirectionalRange!DRange);
111         static assert(is(ElementType!DRange == BaseNode*));
112     }
113 
114 nothrow @safe @nogc pure:
115     private BaseNode* _first;
116     private BaseNode* _last;
117 
118     private this(BaseNode* first, BaseNode* last)
119     {
120         assert((first is null) == (last is null), "Dlist.Range.this: Invalid arguments");
121         _first = first;
122         _last = last;
123     }
124     private this(BaseNode* n)
125     {
126         this(n, n);
127     }
128 
129     @property
130     bool empty() const scope
131     {
132         assert((_first is null) == (_last is null), "DList.Range: Invalidated state");
133         return !_first;
134     }
135 
136     @property BaseNode* front() return scope
137     {
138         assert(!empty, "DList.Range.front: Range is empty");
139         return _first;
140     }
141 
142     void popFront() scope
143     {
144         assert(!empty, "DList.Range.popFront: Range is empty");
145         if (_first is _last)
146         {
147             _first = _last = null;
148         }
149         else
150         {
151             assert(_first._next && _first is _first._next._prev, "DList.Range: Invalidated state");
152             _first = _first._next;
153         }
154     }
155 
156     @property BaseNode* back() return scope
157     {
158         assert(!empty, "DList.Range.front: Range is empty");
159         return _last;
160     }
161 
162     void popBack() scope
163     {
164         assert(!empty, "DList.Range.popBack: Range is empty");
165         if (_first is _last)
166         {
167             _first = _last = null;
168         }
169         else
170         {
171             assert(_last._prev && _last is _last._prev._next, "DList.Range: Invalidated state");
172             _last = _last._prev;
173         }
174     }
175 
176     /// Forward range primitive.
177     @property DRange save() return scope { return this; }
178 }
179 
180 /**
181 Implements a doubly-linked list.
182 
183 `DList` uses reference semantics.
184  */
185 struct DList(T)
186 {
187     import std.range : Take;
188     import std.traits : isMutable;
189 
190     /*
191     A Node with a Payload. A PayNode.
192      */
193     struct PayNode
194     {
195         BaseNode _base;
196         alias _base this;
197 
198         T _payload = T.init;
199 
200         this (BaseNode _base, T _payload)
201         {
202             import std.algorithm.mutation : move;
203 
204             this._base = _base;
205             this._payload = move(_payload);
206         }
207 
208         inout(BaseNode)* asBaseNode() inout @trusted
209         {
210             return &_base;
211         }
212     }
213 
214     //The sentinel node
215     private BaseNode* _root;
216 
217   private
218   {
219     //Construct as new PayNode, and returns it as a BaseNode.
220     static BaseNode* createNode(Stuff)(auto ref Stuff arg, BaseNode* prev = null, BaseNode* next = null)
221     {
222         import std.algorithm.mutation : move;
223 
224         static if (isMutable!Stuff)
225             return (new PayNode(BaseNode(prev, next), move(arg))).asBaseNode();
226         else
227             return (new PayNode(BaseNode(prev, next), arg)).asBaseNode();
228     }
229 
230     void initialize() nothrow @safe pure
231     {
232         if (_root) return;
233         //Note: We allocate a PayNode for safety reasons.
234         _root = (new PayNode()).asBaseNode();
235         _root._next = _root._prev = _root;
236     }
237     ref inout(BaseNode*) _first() @property @safe nothrow pure inout
238     {
239         assert(_root, "Root pointer must not be null");
240         return _root._next;
241     }
242     ref inout(BaseNode*) _last() @property @safe nothrow pure inout
243     {
244         assert(_root, "Root pointer must not be null");
245         return _root._prev;
246     }
247   } //end private
248 
249 /**
250 Constructor taking a number of nodes
251      */
252     this(U)(U[] values...)
253     if (isImplicitlyConvertible!(U, T))
254     {
255         insertBack(values);
256     }
257 
258 /**
259 Constructor taking an $(REF_ALTTEXT input range, isInputRange, std,range,primitives)
260      */
261     this(Stuff)(Stuff stuff)
262     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
263     {
264         insertBack(stuff);
265     }
266 
267 /**
268 Comparison for equality.
269 
270 Complexity: $(BIGOH min(n, n1)) where `n1` is the number of
271 elements in `rhs`.
272      */
273     bool opEquals()(ref const DList rhs) const
274     if (is(typeof(front == front)))
275     {
276         const lhs = this;
277         const lroot = lhs._root;
278         const rroot = rhs._root;
279 
280         if (lroot is rroot) return true;
281         if (lroot is null) return rroot is rroot._next;
282         if (rroot is null) return lroot is lroot._next;
283 
284         const(BaseNode)* pl = lhs._first;
285         const(BaseNode)* pr = rhs._first;
286         while (true)
287         {
288             if (pl is lroot) return pr is rroot;
289             if (pr is rroot) return false;
290 
291             // !== because of NaN
292             if (!(pl.getPayload!T() == pr.getPayload!T())) return false;
293 
294             pl = pl._next;
295             pr = pr._next;
296         }
297     }
298 
299     /**
300     Defines the container's primary range, which embodies a bidirectional range.
301      */
302     struct Range
303     {
304         static assert(isBidirectionalRange!Range);
305 
306         DRange _base;
307         alias _base this;
308 
309         private this(BaseNode* first, BaseNode* last)
310         {
311             _base = DRange(first, last);
312         }
313         private this(BaseNode* n)
314         {
315             this(n, n);
316         }
317 
318         @property ref T front()
319         {
320             return _base.front.getPayload!T();
321         }
322 
323         @property ref T back()
324         {
325             return _base.back.getPayload!T();
326         }
327 
328         //Note: shadows base DRange.save.
329         //Necessary for static covariance.
330         @property Range save() { return this; }
331     }
332 
333 /**
334 Property returning `true` if and only if the container has no
335 elements.
336 
337 Complexity: $(BIGOH 1)
338      */
339     bool empty() @property const nothrow
340     {
341         return _root is null || _root is _first;
342     }
343 
344 /**
345 Removes all contents from the `DList`.
346 
347 Postcondition: `empty`
348 
349 Complexity: $(BIGOH 1)
350      */
351     void clear()
352     {
353         //remove actual elements.
354         remove(this[]);
355     }
356 
357 /**
358 Duplicates the container. The elements themselves are not transitively
359 duplicated.
360 
361 Complexity: $(BIGOH n).
362      */
363     @property DList dup()
364     {
365         return DList(this[]);
366     }
367 
368 /**
369 Returns a range that iterates over all elements of the container, in
370 forward order.
371 
372 Complexity: $(BIGOH 1)
373      */
374     Range opSlice()
375     {
376         if (empty)
377             return Range(null, null);
378         else
379             return Range(_first, _last);
380     }
381 
382 /**
383 Forward to `opSlice().front`.
384 
385 Complexity: $(BIGOH 1)
386      */
387     @property ref inout(T) front() inout
388     {
389         assert(!empty, "DList.front: List is empty");
390         return _first.getPayload!T();
391     }
392 
393 /**
394 Forward to `opSlice().back`.
395 
396 Complexity: $(BIGOH 1)
397      */
398     @property ref inout(T) back() inout
399     {
400         assert(!empty, "DList.back: List is empty");
401         return _last.getPayload!T();
402     }
403 
404 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
405 /+                        BEGIN CONCAT FUNCTIONS HERE                         +/
406 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
407 
408 /**
409 Returns a new `DList` that's the concatenation of `this` and its
410 argument `rhs`.
411      */
412     DList opBinary(string op, Stuff)(Stuff rhs)
413     if (op == "~" && is(typeof(insertBack(rhs))))
414     {
415         auto ret = this.dup;
416         ret.insertBack(rhs);
417         return ret;
418     }
419 
420 /**
421 Returns a new `DList` that's the concatenation of the argument `lhs`
422 and `this`.
423      */
424     DList opBinaryRight(string op, Stuff)(Stuff lhs)
425     if (op == "~" && is(typeof(insertFront(lhs))))
426     {
427         auto ret = this.dup;
428         ret.insertFront(lhs);
429         return ret;
430     }
431 
432 /**
433 Appends the contents of the argument `rhs` into `this`.
434      */
435     DList opOpAssign(string op, Stuff)(Stuff rhs)
436     if (op == "~" && is(typeof(insertBack(rhs))))
437     {
438         insertBack(rhs);
439         return this;
440     }
441 
442 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
443 /+                        BEGIN INSERT FUNCTIONS HERE                         +/
444 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
445 
446 /**
447 Inserts `stuff` to the front/back of the container. `stuff` can be a
448 value convertible to `T` or a range of objects convertible to $(D
449 T). The stable version behaves the same, but guarantees that ranges
450 iterating over the container are never invalidated.
451 
452 Returns: The number of elements inserted
453 
454 Complexity: $(BIGOH log(n))
455      */
456     size_t insertFront(Stuff)(Stuff stuff)
457     {
458         initialize();
459         return insertAfterNode(_root, stuff);
460     }
461 
462     /// ditto
463     size_t insertBack(Stuff)(Stuff stuff)
464     {
465         initialize();
466         return insertBeforeNode(_root, stuff);
467     }
468 
469     /// ditto
470     alias insert = insertBack;
471 
472     /// ditto
473     alias stableInsert = insert;
474 
475     /// ditto
476     alias stableInsertFront = insertFront;
477 
478     /// ditto
479     alias stableInsertBack = insertBack;
480 
481 /**
482 Inserts `stuff` after range `r`, which must be a non-empty range
483 previously extracted from this container.
484 
485 `stuff` can be a value convertible to `T` or a range of objects
486 convertible to `T`. The stable version behaves the same, but
487 guarantees that ranges iterating over the container are never
488 invalidated.
489 
490 Returns: The number of values inserted.
491 
492 Complexity: $(BIGOH k + m), where `k` is the number of elements in
493 `r` and `m` is the length of `stuff`.
494      */
495     size_t insertBefore(Stuff)(Range r, Stuff stuff)
496     {
497         if (r._first)
498             return insertBeforeNode(r._first, stuff);
499         else
500         {
501             initialize();
502             return insertAfterNode(_root, stuff);
503         }
504     }
505 
506     /// ditto
507     alias stableInsertBefore = insertBefore;
508 
509     /// ditto
510     size_t insertAfter(Stuff)(Range r, Stuff stuff)
511     {
512         if (r._last)
513             return insertAfterNode(r._last, stuff);
514         else
515         {
516             initialize();
517             return insertBeforeNode(_root, stuff);
518         }
519     }
520 
521     /// ditto
522     alias stableInsertAfter = insertAfter;
523 
524 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
525 /+                        BEGIN REMOVE FUNCTIONS HERE                         +/
526 /+ ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ +/
527 
528 /**
529 Picks one value in an unspecified position in the container, removes
530 it from the container, and returns it. The stable version behaves the same,
531 but guarantees that ranges iterating over the container are never invalidated.
532 
533 Precondition: `!empty`
534 
535 Returns: The element removed.
536 
537 Complexity: $(BIGOH 1).
538      */
539     T removeAny()
540     {
541         import std.algorithm.mutation : move;
542 
543         assert(!empty, "DList.removeAny: List is empty");
544         auto result = move(back);
545         removeBack();
546         return result;
547     }
548     /// ditto
549     alias stableRemoveAny = removeAny;
550 
551 /**
552 Removes the value at the front/back of the container. The stable version
553 behaves the same, but guarantees that ranges iterating over the
554 container are never invalidated.
555 
556 Precondition: `!empty`
557 
558 Complexity: $(BIGOH 1).
559      */
560     void removeFront()
561     {
562         assert(!empty, "DList.removeFront: List is empty");
563         assert(_root is _first._prev, "DList: Inconsistent state");
564         BaseNode.connect(_root, _first._next);
565     }
566 
567     /// ditto
568     alias stableRemoveFront = removeFront;
569 
570     /// ditto
571     void removeBack()
572     {
573         assert(!empty, "DList.removeBack: List is empty");
574         assert(_last._next is _root, "DList: Inconsistent state");
575         BaseNode.connect(_last._prev, _root);
576     }
577 
578     /// ditto
579     alias stableRemoveBack = removeBack;
580 
581 /**
582 Removes `howMany` values at the front or back of the
583 container. Unlike the unparameterized versions above, these functions
584 do not throw if they could not remove `howMany` elements. Instead,
585 if $(D howMany > n), all elements are removed. The returned value is
586 the effective number of elements removed. The stable version behaves
587 the same, but guarantees that ranges iterating over the container are
588 never invalidated.
589 
590 Returns: The number of elements removed
591 
592 Complexity: $(BIGOH howMany).
593      */
594     size_t removeFront(size_t howMany)
595     {
596         if (!_root) return 0;
597         size_t result;
598         auto p = _first;
599         while (p !is _root && result < howMany)
600         {
601             p = p._next;
602             ++result;
603         }
604         BaseNode.connect(_root, p);
605         return result;
606     }
607 
608     /// ditto
609     alias stableRemoveFront = removeFront;
610 
611     /// ditto
612     size_t removeBack(size_t howMany)
613     {
614         if (!_root) return 0;
615         size_t result;
616         auto p = _last;
617         while (p !is _root && result < howMany)
618         {
619             p = p._prev;
620             ++result;
621         }
622         BaseNode.connect(p, _root);
623         return result;
624     }
625 
626     /// ditto
627     alias stableRemoveBack = removeBack;
628 
629 /**
630 Removes all elements belonging to `r`, which must be a range
631 obtained originally from this container.
632 
633 Returns: A range spanning the remaining elements in the container that
634 initially were right after `r`.
635 
636 Complexity: $(BIGOH 1)
637      */
638     Range remove(Range r)
639     {
640         if (r.empty)
641             return r;
642 
643         assert(_root !is null, "Cannot remove from an un-initialized List");
644         assert(r._first, "Remove: Range is empty");
645 
646         BaseNode.connect(r._first._prev, r._last._next);
647         auto after = r._last._next;
648         if (after is _root)
649             return Range(null, null);
650         else
651             return Range(after, _last);
652     }
653 
654     /// ditto
655     Range linearRemove(Range r)
656     {
657         return remove(r);
658     }
659 
660     /// ditto
661     alias stableRemove = remove;
662 
663 /**
664 Removes first element of `r`, wich must be a range obtained originally
665 from this container, from both DList instance and range `r`.
666 
667 Compexity: $(BIGOH 1)
668      */
669     void popFirstOf(ref Range r)
670     {
671         assert(_root !is null, "Cannot remove from an un-initialized List");
672         assert(r._first, "popFirstOf: Range is empty");
673         auto prev = r._first._prev;
674         auto next = r._first._next;
675         r.popFront();
676         BaseNode.connect(prev, next);
677     }
678 
679 /**
680 Removes last element of `r`, wich must be a range obtained originally
681 from this container, from both DList instance and range `r`.
682 
683 Compexity: $(BIGOH 1)
684      */
685     void popLastOf(ref Range r)
686     {
687         assert(_root !is null, "Cannot remove from an un-initialized List");
688         assert(r._first, "popLastOf: Range is empty");
689         auto prev = r._last._prev;
690         auto next = r._last._next;
691         r.popBack();
692         BaseNode.connect(prev, next);
693     }
694 
695 /**
696 `linearRemove` functions as `remove`, but also accepts ranges that are
697 result the of a `take` operation. This is a convenient way to remove a
698 fixed amount of elements from the range.
699 
700 Complexity: $(BIGOH r.walkLength)
701      */
702     Range linearRemove(Take!Range r)
703     {
704         assert(_root !is null, "Cannot remove from an un-initialized List");
705         assert(r.source._first, "Remove: Range is empty");
706 
707         BaseNode* first = r.source._first;
708         BaseNode* last = null;
709         do
710         {
711             last = r.source._first;
712             r.popFront();
713         } while ( !r.empty );
714 
715         return remove(Range(first, last));
716     }
717 
718     /// ditto
719     alias stableLinearRemove = linearRemove;
720 
721 /**
722 Removes the first occurence of an element from the list in linear time.
723 
724 Returns: True if the element existed and was successfully removed, false otherwise.
725 
726 Params:
727     value = value of the node to be removed
728 
729 Complexity: $(BIGOH n)
730      */
731     bool linearRemoveElement(T value)
732     {
733         import std.algorithm.mutation : move;
734 
735         auto n1 = findNodeByValue(_root, move(value));
736         if (n1)
737         {
738             auto n2 = n1._next._next;
739             BaseNode.connect(n1, n2);
740             return true;
741         }
742 
743         return false;
744     }
745 
746 
747 private:
748 
749     BaseNode* findNodeByValue(BaseNode* n, T value)
750     {
751         if (!n) return null;
752         auto ahead = n._next;
753         while (ahead && ahead.getPayload!T() != value)
754         {
755             n = ahead;
756             ahead = n._next;
757             if (ahead == _last._next) return null;
758         }
759         return n;
760     }
761 
762     // Helper: Inserts stuff before the node n.
763     size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
764     if (isImplicitlyConvertible!(Stuff, T))
765     {
766         auto p = createNode(stuff, n._prev, n);
767         n._prev._next = p;
768         n._prev = p;
769         return 1;
770     }
771     // ditto
772     size_t insertBeforeNode(Stuff)(BaseNode* n, ref Stuff stuff)
773     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
774     {
775         if (stuff.empty) return 0;
776         size_t result;
777         Range r = createRange(stuff, result);
778         BaseNode.connect(n._prev, r._first);
779         BaseNode.connect(r._last, n);
780         return result;
781     }
782 
783     // Helper: Inserts stuff after the node n.
784     size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
785     if (isImplicitlyConvertible!(Stuff, T))
786     {
787         auto p = createNode(stuff, n, n._next);
788         n._next._prev = p;
789         n._next = p;
790         return 1;
791     }
792     // ditto
793     size_t insertAfterNode(Stuff)(BaseNode* n, ref Stuff stuff)
794     if (isInputRange!Stuff && isImplicitlyConvertible!(ElementType!Stuff, T))
795     {
796         if (stuff.empty) return 0;
797         size_t result;
798         Range r = createRange(stuff, result);
799         BaseNode.connect(r._last, n._next);
800         BaseNode.connect(n, r._first);
801         return result;
802     }
803 
804     // Helper: Creates a chain of nodes from the range stuff.
805     Range createRange(Stuff)(ref Stuff stuff, ref size_t result)
806     {
807         BaseNode* first = createNode(stuff.front);
808         BaseNode* last = first;
809         ++result;
810         for ( stuff.popFront() ; !stuff.empty ; stuff.popFront() )
811         {
812             auto p = createNode(stuff.front, last);
813             last = last._next = p;
814             ++result;
815         }
816         return Range(first, last);
817     }
818 }
819 
820 @safe unittest
821 {
822     import std.algorithm.comparison : equal;
823 
824     auto e = DList!int();
825     auto b = e.linearRemoveElement(1);
826     assert(b == false);
827     assert(e.empty());
828     auto a = DList!int(-1, 1, 2, 1, 3, 4);
829     b = a.linearRemoveElement(1);
830     assert(equal(a[], [-1, 2, 1, 3, 4]));
831     assert(b == true);
832     b = a.linearRemoveElement(-1);
833     assert(b == true);
834     assert(equal(a[], [2, 1, 3, 4]));
835     b = a.linearRemoveElement(1);
836     assert(b == true);
837     assert(equal(a[], [2, 3, 4]));
838     b = a.linearRemoveElement(2);
839     assert(b == true);
840     b = a.linearRemoveElement(20);
841     assert(b == false);
842     assert(equal(a[], [3, 4]));
843     b = a.linearRemoveElement(4);
844     assert(b == true);
845     assert(equal(a[], [3]));
846     b = a.linearRemoveElement(3);
847     assert(b == true);
848     assert(a.empty());
849     a.linearRemoveElement(3);
850 }
851 
852 @safe unittest
853 {
854     import std.algorithm.comparison : equal;
855 
856     //Tests construction signatures
857     alias IntList = DList!int;
858     auto a0 = IntList();
859     auto a1 = IntList(0);
860     auto a2 = IntList(0, 1);
861     auto a3 = IntList([0]);
862     auto a4 = IntList([0, 1]);
863 
864     assert(a0[].empty);
865     assert(equal(a1[], [0]));
866     assert(equal(a2[], [0, 1]));
867     assert(equal(a3[], [0]));
868     assert(equal(a4[], [0, 1]));
869 }
870 
871 @safe unittest
872 {
873     import std.algorithm.comparison : equal;
874 
875     alias IntList = DList!int;
876     IntList list = IntList([0,1,2,3]);
877     assert(equal(list[],[0,1,2,3]));
878     list.insertBack([4,5,6,7]);
879     assert(equal(list[],[0,1,2,3,4,5,6,7]));
880 
881     list = IntList();
882     list.insertFront([0,1,2,3]);
883     assert(equal(list[],[0,1,2,3]));
884     list.insertFront([4,5,6,7]);
885     assert(equal(list[],[4,5,6,7,0,1,2,3]));
886 }
887 
888 @safe unittest
889 {
890     import std.algorithm.comparison : equal;
891     import std.range : take;
892 
893     alias IntList = DList!int;
894     IntList list = IntList([0,1,2,3]);
895     auto range = list[];
896     for ( ; !range.empty; range.popFront())
897     {
898         int item = range.front;
899         if (item == 2)
900         {
901             list.stableLinearRemove(take(range, 1));
902             break;
903         }
904     }
905     assert(equal(list[],[0,1,3]));
906 
907     list = IntList([0,1,2,3]);
908     range = list[];
909     for ( ; !range.empty; range.popFront())
910     {
911         int item = range.front;
912         if (item == 2)
913         {
914             list.stableLinearRemove(take(range,2));
915             break;
916         }
917     }
918     assert(equal(list[],[0,1]));
919 
920     list = IntList([0,1,2,3]);
921     range = list[];
922     for ( ; !range.empty; range.popFront())
923     {
924         int item = range.front;
925         if (item == 0)
926         {
927             list.stableLinearRemove(take(range,2));
928             break;
929         }
930     }
931     assert(equal(list[],[2,3]));
932 
933     list = IntList([0,1,2,3]);
934     range = list[];
935     for ( ; !range.empty; range.popFront())
936     {
937         int item = range.front;
938         if (item == 1)
939         {
940             list.stableLinearRemove(take(range,2));
941             break;
942         }
943     }
944     assert(equal(list[],[0,3]));
945 }
946 
947 @safe unittest
948 {
949     import std.algorithm.comparison : equal;
950 
951     auto dl = DList!int([1, 2, 3, 4, 5]);
952     auto r = dl[];
953     r.popFront();
954     dl.popFirstOf(r);
955     assert(equal(dl[], [1, 3, 4, 5]));
956     assert(equal(r, [3, 4, 5]));
957     r.popBack();
958     dl.popLastOf(r);
959     assert(equal(dl[], [1, 3, 5]));
960     assert(equal(r, [3]));
961     dl = DList!int([0]);
962     r = dl[];
963     dl.popFirstOf(r);
964     assert(dl.empty);
965     dl = DList!int([0]);
966     r = dl[];
967     dl.popLastOf(r);
968     assert(dl.empty);
969 }
970 
971 @safe unittest
972 {
973     import std.algorithm.comparison : equal;
974 
975     auto dl = DList!string(["a", "b", "d"]);
976     dl.insertAfter(dl[], "e"); // insert at the end
977     assert(equal(dl[], ["a", "b", "d", "e"]));
978     auto dlr = dl[];
979     dlr.popBack(); dlr.popBack();
980     dl.insertAfter(dlr, "c"); // insert after "b"
981     assert(equal(dl[], ["a", "b", "c", "d", "e"]));
982 }
983 
984 @safe unittest
985 {
986     import std.algorithm.comparison : equal;
987 
988     auto dl = DList!string(["a", "b", "d"]);
989     dl.insertBefore(dl[], "e"); // insert at the front
990     assert(equal(dl[], ["e", "a", "b", "d"]));
991     auto dlr = dl[];
992     dlr.popFront(); dlr.popFront();
993     dl.insertBefore(dlr, "c"); // insert before "b"
994     assert(equal(dl[], ["e", "a", "c", "b", "d"]));
995 }
996 
997 @safe unittest
998 {
999     auto d = DList!int([1, 2, 3]);
1000     d.front = 5; //test frontAssign
1001     assert(d.front == 5);
1002     auto r = d[];
1003     r.back = 1;
1004     assert(r.back == 1);
1005 }
1006 
1007 // https://issues.dlang.org/show_bug.cgi?id=8895
1008 @safe unittest
1009 {
1010     auto a = make!(DList!int)(1,2,3,4);
1011     auto b = make!(DList!int)(1,2,3,4);
1012     auto c = make!(DList!int)(1,2,3,5);
1013     auto d = make!(DList!int)(1,2,3,4,5);
1014     assert(a == b); // this better terminate!
1015     assert(!(a == c));
1016     assert(!(a == d));
1017 }
1018 
1019 @safe unittest
1020 {
1021     auto d = DList!int([1, 2, 3]);
1022     d.front = 5; //test frontAssign
1023     assert(d.front == 5);
1024     auto r = d[];
1025     r.back = 1;
1026     assert(r.back == 1);
1027 }
1028 
1029 @safe unittest
1030 {
1031     auto a = DList!int();
1032     assert(a.removeFront(10) == 0);
1033     a.insert([1, 2, 3]);
1034     assert(a.removeFront(10) == 3);
1035     assert(a[].empty);
1036 }
1037 
1038 @safe unittest
1039 {
1040     import std.algorithm.comparison : equal;
1041 
1042     //Verify all flavors of ~
1043     auto a = DList!int();
1044     auto b = DList!int();
1045     auto c = DList!int([1, 2, 3]);
1046     auto d = DList!int([4, 5, 6]);
1047 
1048     assert((a ~ b[])[].empty);
1049     assert((c ~ d[])[].equal([1, 2, 3, 4, 5, 6]));
1050     assert(c[].equal([1, 2, 3]));
1051     assert(d[].equal([4, 5, 6]));
1052 
1053     assert((c[] ~ d)[].equal([1, 2, 3, 4, 5, 6]));
1054     assert(c[].equal([1, 2, 3]));
1055     assert(d[].equal([4, 5, 6]));
1056 
1057     a~=c[];
1058     assert(a[].equal([1, 2, 3]));
1059     assert(c[].equal([1, 2, 3]));
1060 
1061     a~=d[];
1062     assert(a[].equal([1, 2, 3, 4, 5, 6]));
1063     assert(d[].equal([4, 5, 6]));
1064 
1065     a~=[7, 8, 9];
1066     assert(a[].equal([1, 2, 3, 4, 5, 6, 7, 8, 9]));
1067 
1068     //trick test:
1069     auto r = c[];
1070     c.removeFront();
1071     c.removeBack();
1072 }
1073 
1074 @safe unittest
1075 {
1076     import std.algorithm.comparison : equal;
1077 
1078     // https://issues.dlang.org/show_bug.cgi?id=8905
1079     auto a = DList!int([1, 2, 3, 4]);
1080     auto r = a[];
1081     a.stableRemoveBack();
1082     a.stableInsertBack(7);
1083     assert(a[].equal([1, 2, 3, 7]));
1084 }
1085 
1086 // https://issues.dlang.org/show_bug.cgi?id=12566
1087 @safe unittest
1088 {
1089     auto dl2 = DList!int([2,7]);
1090     dl2.removeFront();
1091     assert(dl2[].walkLength == 1);
1092     dl2.removeBack();
1093     assert(dl2.empty, "not empty?!");
1094 }
1095 
1096 // https://issues.dlang.org/show_bug.cgi?id=13076
1097 @safe unittest
1098 {
1099     DList!int list;
1100     assert(list.empty);
1101     list.clear();
1102 }
1103 
1104 // https://issues.dlang.org/show_bug.cgi?id=13425
1105 @safe unittest
1106 {
1107     import std.range : drop, take;
1108     auto list = DList!int([1,2,3,4,5]);
1109     auto r = list[].drop(4); // r is a view of the last element of list
1110     assert(r.front == 5 && r.walkLength == 1);
1111     r = list.linearRemove(r.take(1));
1112     assert(r.empty); // fails
1113 }
1114 
1115 // https://issues.dlang.org/show_bug.cgi?id=14300
1116 @safe unittest
1117 {
1118     interface ITest {}
1119     static class Test : ITest {}
1120 
1121     DList!ITest().insertBack(new Test());
1122 }
1123 
1124 // https://issues.dlang.org/show_bug.cgi?id=15263
1125 @safe unittest
1126 {
1127     import std.range : iota;
1128     auto a = DList!int();
1129     a.insertFront(iota(0, 5)); // can insert range with non-ref front
1130     assert(a.front == 0 && a.back == 4);
1131 }
1132 
1133 // https://issues.dlang.org/show_bug.cgi?id=22147
1134 @safe unittest
1135 {
1136     import std.algorithm.mutation : move;
1137 
1138     static struct Item
1139     {
1140         @disable this(this);
1141 
1142         int x;
1143     }
1144 
1145     auto list = DList!Item();
1146     list.insertFront(Item(1));
1147     assert(list[].walkLength == 1);
1148     assert(list.front.x == 1);
1149     auto item = list.moveFront;
1150     item.x = 2;
1151     list.front = move(item);
1152     assert(list.front.x == 2);
1153     list.removeFront();
1154     assert(list[].walkLength == 0);
1155 }
1156 
1157 //  https://issues.dlang.org/show_bug.cgi?id=24637
1158 @safe unittest
1159 {
1160     import std.algorithm.comparison : equal;
1161 
1162     struct A
1163     {
1164         int c;
1165     }
1166 
1167     DList!A B;
1168     B.insert(A(1));
1169     assert(B[].equal([A(1)]));
1170 
1171     const a = A(3);
1172     B.insert(a);
1173     assert(B[].equal([A(1), A(3)]));
1174 }