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