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