Unofficial Dub Package Documentation 
1 module mecca.containers.lists;
2 
3 // Licensed under the Boost license. Full copyright information in the AUTHORS file
4 
5 import std.traits;
6 
7 import mecca.lib.memory: prefetch;
8 import mecca.lib.exception;
9 import mecca.log;
10 
11 
12 ///////////////////////////////////////////////////////////////////////////////////////////////////
13 //
14 // LinkedList: doubly-linked list of elements; next/prev stored in-element (intrusive)
15 //
16 ///////////////////////////////////////////////////////////////////////////////////////////////////
17 
18 struct _LinkedList(T, string nextAttr, string prevAttr, string ownerAttr, bool withLength) {
19     T head;
20     static if (withLength) {
21         size_t length;
22     }
23     enum withOwner = ownerAttr.length > 0;
24 
25     private enum MAY_PREFETCH = __traits(compiles, {T t; prefetch(t);});
26 
27     static if(isPointer!T) pure nothrow @nogc {
28         private static bool isValid(const T t) pure nothrow @safe @nogc {
29             return t !is null;
30         }
31 
32         enum invalid = null;
33     } else {
34         private static bool isValid(const T t) pure nothrow @safe @nogc {
35             return t.isValid;
36         }
37 
38         enum invalid = T.invalid;
39     }
40 
41     static assert (!isValid(invalid), "invalid is valid for type " ~ T.stringof);
42 
43     static T getNextOf(T node) nothrow @safe @nogc {
44         pragma(inline, true);
45         T tmp = mixin("node." ~ nextAttr);
46         static if(MAY_PREFETCH) prefetch(tmp);
47         return tmp;
48     }
49     static void setNextOf(T node, T val) nothrow @safe @nogc {
50         pragma(inline, true);
51         mixin("node." ~ nextAttr ~ " = val;");
52     }
53 
54     static T getPrevOf(T node) nothrow @safe @nogc {
55         pragma(inline, true);
56         T tmp = mixin("node." ~ prevAttr);
57         static if (MAY_PREFETCH) prefetch(tmp);
58         return tmp;
59     }
60     static void setPrevOf(T node, T val) nothrow @safe @nogc {
61         pragma(inline, true);
62         mixin("node." ~ prevAttr ~ " = val;");
63     }
64 
65     static if (withOwner) {
66         @notrace private static _LinkedList* getOwnerOf(T node) nothrow @trusted @nogc {
67             pragma(inline, true);
68             mixin("return cast(_LinkedList*)(node." ~ ownerAttr ~ ");");
69         }
70         @notrace private static void clearOwnerOf(T node) nothrow @safe @nogc {
71             pragma(inline, true);
72             mixin("node." ~ ownerAttr ~ " = null;");
73         }
74     }
75 
76     @property bool empty() const pure nothrow {
77         static if (withLength) assert (isValid(head) || length == 0, "head is null but length != 0");
78         return !isValid(head);
79     }
80     @property T tail() nothrow {
81         static if (withLength) assert (isValid(head) || length == 0, "head is null but length != 0");
82         return isValid(head) ? getPrevOf(head) : invalid;
83     }
84 
85     bool _insert(bool after)(T anchor, T node) nothrow @safe @nogc {
86         assert (isValid(node), "appending null");
87 
88         static if (withOwner) {
89             assert (!isValid(anchor) || getOwnerOf(anchor) is &this, "anchor does not belong to this list");
90             auto owner = getOwnerOf(node);
91             if (owner is &this) {
92                 return false;
93             }
94             assert (owner is null, "owner already set");
95             mixin("node." ~ ownerAttr ~ " = &this;");
96         }
97         ASSERT!"next is linked"(!isValid(getNextOf(node)));
98         ASSERT!"prev is linked"(!isValid(getPrevOf(node)));
99 
100         if (!isValid(head)) {
101             assert (!isValid(anchor));
102             static if (withLength) assert (length == 0);
103             head = node;
104             setNextOf(node, node);
105             setPrevOf(node, node);
106         }
107         else {
108             static if (withLength) assert (length > 0, "List with head has length 0");
109             static if (after) {
110                 auto next = getNextOf(anchor);
111                 setNextOf(anchor, node);
112                 setPrevOf(node, anchor);
113                 setNextOf(node, next);
114                 setPrevOf(next, node);
115             }
116             else {
117                 auto prev = getPrevOf(anchor);
118                 setNextOf(node, anchor);
119                 setPrevOf(node, prev);
120                 setPrevOf(anchor, node);
121                 setNextOf(prev, node);
122 
123                 if (anchor is head) {
124                     head = node;
125                 }
126             }
127         }
128 
129         static if (withLength) length++;
130         return true;
131     }
132 
133     bool insertAfter(T anchor, T node) nothrow @safe @nogc {pragma(inline, true);
134         return _insert!true(anchor, node);
135     }
136     bool insertBefore(T anchor, T node) nothrow @safe @nogc {pragma(inline, true);
137         return _insert!false(anchor, node);
138     }
139 
140     bool append(T node) nothrow @safe @nogc {pragma(inline, true);
141         return insertAfter(tail, node);
142     }
143     bool prepend(T node) nothrow @safe @nogc {pragma(inline, true);
144         return insertBefore(head, node);
145     }
146 
147     bool remove(T node) nothrow @safe @nogc {
148         assert (isValid(node));
149         assert (!empty);
150 
151         static if (withOwner) {
152             auto owner = getOwnerOf(node);
153             if (owner is null) {
154                 assert (!isValid(getNextOf(node)), "no owner but next is linked");
155                 assert (!isValid(getPrevOf(node)), "no owner but prev is linked");
156                 return false;
157             }
158             ASSERT!"Trying to remove node that doesn't belong to list. Owner %s, this %s" (owner is &this, owner, &this);
159             clearOwnerOf(node);
160         }
161 
162         if (getNextOf(head) is head) {
163             // single element
164             assert (node is head);
165             setNextOf(node, invalid);
166             setPrevOf(node, invalid);
167             head = invalid;
168         }
169         else {
170             auto p = getPrevOf(node);
171             auto n = getNextOf(node);
172             setNextOf(p, n);
173             setPrevOf(n, p);
174             if (node is head) {
175                 head = n;
176             }
177         }
178         setNextOf(node, invalid);
179         setPrevOf(node, invalid);
180 
181         static if (withLength) {
182             assert (length > 0);
183             length--;
184         }
185         return true;
186     }
187 
188     static if (withOwner) {
189         bool opBinaryRight(string op: "in")(T node) const nothrow @safe @nogc {
190             return getOwnerOf(node) is &this;
191         }
192 
193         static bool discard(T node) nothrow @safe @nogc {
194             if (auto owner = getOwnerOf(node)) {
195                 return owner.remove(node);
196             }
197             else {
198                 assert (!isValid(getNextOf(node)), "no owner but next is linked");
199                 assert (!isValid(getPrevOf(node)), "no owner but prev is linked");
200                 return false;
201             }
202         }
203     }
204 
205     T popHead() nothrow @safe @nogc {
206         auto node = head;
207         if (isValid(node)) {
208             remove(node);
209         }
210         return node;
211     }
212     T popTail() nothrow @safe @nogc {
213         auto node = tail;
214         if (isValid(node)) {
215             remove(node);
216         }
217         return node;
218     }
219 
220     static if (!withOwner) {
221         void splice(_LinkedList* second) nothrow {
222             assert (second !is &this);
223             if (second.empty) {
224                 return;
225             }
226             if (empty) {
227                 head = second.head;
228             }
229             else {
230                 setNextOf(tail, second.head);
231                 setPrevOf(second.head, tail);
232                 setNextOf(second.tail, head);
233                 setPrevOf(head, second.tail);
234             }
235 
236             // For safety reasons, `second` is emptied (otherwise pop() from it would break this)
237             second.head = invalid;
238             static if (withLength) {
239                 length += second.length;
240                 second.length = 0;
241             }
242         }
243     }
244 
245     void removeAll() nothrow {
246         while (isValid(head)) {
247             auto next = getNextOf(head);
248             setPrevOf(head, invalid);
249             setNextOf(head, invalid);
250             static if (withOwner) clearOwnerOf(head);
251             head = (next is head) ? invalid : next;
252         }
253         static if (withLength) length = 0;
254     }
255 
256     static struct Range {
257         _LinkedList* list;
258         T front;
259 
260         @property bool empty() const pure nothrow @nogc {
261             return !isValid(front);
262         }
263         void popFront() nothrow {
264             assert (list !is null);
265             assert (isValid(front));
266             front = getNextOf(front);
267             if (front is list.head) {
268                 front = invalid;
269             }
270         }
271     }
272     @property auto range() nothrow {
273         return Range(&this, head);
274     }
275 
276     static struct ReverseRange {
277         _LinkedList* list;
278         T front;
279 
280         @property bool empty() const pure nothrow @nogc {
281             return !isValid(front);
282         }
283         void popFront() nothrow {
284             assert (list);
285             assert (isValid(front));
286             front = getPrevOf(front);
287             if (front is list.tail) {
288                 front = invalid;
289             }
290         }
291     }
292     @property auto reverseRange() nothrow {
293         return ReverseRange(&this, tail);
294     }
295 }
296 
297 alias LinkedList(T, string nextAttr="_next", string prevAttr="_prev") = _LinkedList!(T, nextAttr, prevAttr, "", false);
298 alias LinkedListWithLength(T, string nextAttr="_next", string prevAttr="_prev") = _LinkedList!(T, nextAttr, prevAttr, "", true);
299 
300 alias LinkedListWithOwner(T, string nextAttr="_next", string prevAttr="_prev", string ownerAttr="_owner") = _LinkedList!(T, nextAttr, prevAttr, ownerAttr, false);
301 alias LinkedListWithLengthAndOwner(T, string nextAttr="_next", string prevAttr="_prev", string ownerAttr="_owner") = _LinkedList!(T, nextAttr, prevAttr, ownerAttr, true);
302 
303 
304 unittest {
305     import std.stdio;
306     import std..string;
307 
308     struct Node {
309         int value;
310         Node* _next;
311         Node* _prev;
312 
313         @disable this(this);
314     }
315 
316     Node[10] nodes;
317     foreach(int i, ref n; nodes) {
318         n.value = i;
319     }
320 
321     LinkedList!(Node*) list;
322     assert (list.head is null);
323 
324     list.append(&nodes[0]);
325     assert (list.head.value == 0);
326 
327     list.append(&nodes[1]);
328     list.append(&nodes[2]);
329     list.append(&nodes[3]);
330     list.append(&nodes[4]);
331     list.append(&nodes[5]);
332     list.append(&nodes[6]);
333     list.append(&nodes[7]);
334     list.append(&nodes[8]);
335     list.append(&nodes[9]);
336     assert (list.head.value == 0);
337 
338     void matchElements(R)(R range, int[] expected) {
339         int[] arr;
340         foreach(n; range) {
341             arr ~= n.value;
342         }
343         //writeln(arr);
344         assert (arr == expected, "%s != %s".format(arr, expected));
345     }
346 
347     matchElements(list.range, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
348     matchElements(list.range, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
349 
350     list.remove(&nodes[3]);
351     matchElements(list.range, [0, 1, 2, 4, 5, 6, 7, 8, 9]);
352 
353     list.remove(&nodes[0]);
354     matchElements(list.range, [1, 2, 4, 5, 6, 7, 8, 9]);
355 
356     list.remove(&nodes[9]);
357     matchElements(list.range, [1, 2, 4, 5, 6, 7, 8]);
358 
359     list.insertAfter(&nodes[2], &nodes[3]);
360     matchElements(list.range, [1, 2, 3, 4, 5, 6, 7, 8]);
361 
362     list.insertBefore(&nodes[7], &nodes[9]);
363     matchElements(list.range, [1, 2, 3, 4, 5, 6, 9, 7, 8]);
364 
365     matchElements(list.reverseRange, [8, 7, 9, 6, 5, 4, 3, 2, 1]);
366 
367     list.removeAll();
368     assert (list.empty);
369 }
370 
371 unittest {
372     import std.stdio;
373     import std..string;
374 
375     struct Node {
376         int value;
377         Node* _next;
378         Node* _prev;
379 
380         @disable this(this);
381     }
382 
383     Node[10] nodes;
384     foreach(int i, ref n; nodes) {
385         n.value = i;
386     }
387 
388     LinkedListWithLength!(Node*) list;
389     assert (list.head is null);
390 
391     list.append(&nodes[0]);
392     assert (list.head.value == 0);
393 
394     list.append(&nodes[1]);
395     list.append(&nodes[2]);
396     list.append(&nodes[3]);
397     list.append(&nodes[4]);
398     list.append(&nodes[5]);
399     list.append(&nodes[6]);
400     list.append(&nodes[7]);
401     list.append(&nodes[8]);
402     list.append(&nodes[9]);
403     assert (list.head.value == 0);
404 
405     void matchElements(R)(R range, int[] expected) {
406         int[] arr;
407         foreach(n; range) {
408             arr ~= n.value;
409         }
410         //writeln(arr);
411         assert (arr == expected, "%s != %s".format(arr, expected));
412     }
413 
414     matchElements(list.range, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
415     matchElements(list.range, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
416 
417     list.remove(&nodes[3]);
418     matchElements(list.range, [0, 1, 2, 4, 5, 6, 7, 8, 9]);
419 
420     list.remove(&nodes[0]);
421     matchElements(list.range, [1, 2, 4, 5, 6, 7, 8, 9]);
422 
423     list.remove(&nodes[9]);
424     matchElements(list.range, [1, 2, 4, 5, 6, 7, 8]);
425 
426     list.insertAfter(&nodes[2], &nodes[3]);
427     matchElements(list.range, [1, 2, 3, 4, 5, 6, 7, 8]);
428 
429     list.insertBefore(&nodes[7], &nodes[9]);
430     matchElements(list.range, [1, 2, 3, 4, 5, 6, 9, 7, 8]);
431 
432     matchElements(list.reverseRange, [8, 7, 9, 6, 5, 4, 3, 2, 1]);
433 
434     list.removeAll();
435     assert (list.empty);
436 }
437 
438 unittest {
439     import std.stdio;
440     import std..string;
441 
442     // Linked list using abstracted _next and _prev
443     struct Node {
444         @disable this(this);
445 
446         static Node[10] theNodes;
447 
448         int value;
449         ubyte nextIdx = ubyte.max;
450         ubyte prevIdx = ubyte.max;
451 
452         @property Node* _next() nothrow @safe @nogc {
453             return nextIdx == ubyte.max ? null : &theNodes[nextIdx];
454         }
455         @property void _next(Node* n) nothrow @safe @nogc {
456             nextIdx = n is null ? ubyte.max : cast(ubyte)(n - &theNodes[0]);
457         }
458 
459         @property Node* _prev() nothrow @safe @nogc {
460             return prevIdx == ubyte.max ? null : &theNodes[prevIdx];
461         }
462         @property void _prev(Node* n) nothrow @safe @nogc {
463             prevIdx = n is null ? ubyte.max : cast(ubyte)(n - &theNodes[0]);
464         }
465     }
466 
467     foreach(int i, ref n; Node.theNodes) {
468         n.value = 100 + i;
469     }
470 
471     LinkedList!(Node*) list;
472     assert (list.head is null);
473 
474     list.append(&Node.theNodes[0]);
475     assert (list.head.value == 100);
476 
477     list.append(&Node.theNodes[1]);
478     list.append(&Node.theNodes[2]);
479     list.append(&Node.theNodes[3]);
480     list.append(&Node.theNodes[4]);
481     list.append(&Node.theNodes[5]);
482     list.append(&Node.theNodes[6]);
483     list.append(&Node.theNodes[7]);
484     list.append(&Node.theNodes[8]);
485     list.append(&Node.theNodes[9]);
486     assert (list.head.value == 100);
487 
488     list.remove(&Node.theNodes[5]);
489     list.remove(&Node.theNodes[6]);
490 
491     int[] arr;
492     foreach(n; list.range) {
493         arr ~= n.value;
494     }
495     assert(arr == [100, 101, 102, 103, 104, 107, 108, 109]);
496 }
497 
498 unittest {
499     import std.stdio;
500     import std..string;
501 
502     // Linked list using abstracted pointer
503     struct Node {
504         static Node[10] theNodes;
505 
506         static struct Ptr {
507             ubyte index = ubyte.max;
508 
509             @property Node* node() nothrow @safe @nogc {
510                 if (index==ubyte.max)
511                     return null;
512 
513                 return &theNodes[index];
514             }
515 
516             @property ref Ptr _prev() nothrow @safe @nogc {
517                 return node._prev;
518             }
519 
520             @property ref Ptr _next() nothrow @safe @nogc {
521                 return node._next;
522             }
523 
524             bool isValid() const pure nothrow @safe @nogc {
525                 return index != ubyte.max;
526             }
527 
528             enum invalid = Ptr.init;
529         }
530 
531         int value;
532         Ptr _next;
533         Ptr _prev;
534     }
535 
536     foreach(int i, ref n; Node.theNodes) {
537         n.value = 100 + i;
538     }
539 
540     LinkedList!(Node.Ptr) list;
541     assert (!list.head.isValid);
542 
543     list.append(Node.Ptr(0));
544     assert (list.head.node.value == 100);
545 
546     list.append(Node.Ptr(1));
547     list.append(Node.Ptr(2));
548     list.append(Node.Ptr(3));
549     list.append(Node.Ptr(4));
550     list.append(Node.Ptr(5));
551     list.append(Node.Ptr(6));
552     list.append(Node.Ptr(7));
553     list.append(Node.Ptr(8));
554     list.append(Node.Ptr(9));
555     assert (list.head.node.value == 100);
556 
557     list.remove(Node.Ptr(5));
558     list.remove(Node.Ptr(6));
559 
560     int[] arr;
561     foreach(n; list.range) {
562         arr ~= n.node.value;
563     }
564     assert(arr == [100, 101, 102, 103, 104, 107, 108, 109], "Incorrect result: %s".format(arr));
565 }
566 
567 unittest {
568     import std.stdio;
569     import std..string;
570 
571     struct Node {
572         int value;
573         Node* _next;
574         Node* _prev;
575         void* _owner;
576 
577         @disable this(this);
578     }
579 
580     Node[10] nodes;
581     foreach(int i, ref n; nodes) {
582         n.value = i;
583     }
584 
585     LinkedListWithOwner!(Node*) set;
586     assert (set.empty);
587 
588     assert(set.append(&nodes[1]));
589     assert(set.append(&nodes[2]));
590     assert(set.append(&nodes[3]));
591     assert(!set.append(&nodes[2]));
592 
593     assert (&nodes[1] in set);
594     assert (&nodes[2] in set);
595     assert (&nodes[3] in set);
596     assert (&nodes[4] !in set);
597 
598     assert (set.remove(&nodes[2]));
599     assert (&nodes[2] !in set);
600 
601     assert (!set.remove(&nodes[2]));
602     assert (!set.discard(&nodes[2]));
603     assert (set.discard(&nodes[1]));
604     assert (&nodes[1] !in set);
605 }
606 
607 ///////////////////////////////////////////////////////////////////////////////////////////////////
608 //
609 // LinkedQueue: singly-linked list of elements; next pointer is stored in-element (intrusive).
610 //              insert in the head or tail, from only from head
611 //
612 ///////////////////////////////////////////////////////////////////////////////////////////////////
613 
614 struct _LinkedQueue(T, string nextAttr, bool withLength) {
615     T head;
616     T tail;
617     static if (withLength) {
618         size_t length;
619     }
620 
621     static T getNextOf(T node) nothrow @safe @nogc {
622         pragma(inline, true);
623         T tmp = mixin("node." ~ nextAttr);
624         prefetch(tmp);
625         return tmp;
626     }
627     static void setNextOf(T node, T val) nothrow @safe @nogc {
628         pragma(inline, true);
629         mixin("node." ~ nextAttr ~ " = val;");
630     }
631 
632     @property empty() const pure nothrow @safe @nogc {
633         static if (withLength) {
634             assert ((head is null && tail is null && length == 0) || (head !is null && tail !is null && length > 0));
635         }
636         else {
637             assert ((head is null && tail is null) || (head !is null && tail !is null));
638         }
639         return head is null;
640     }
641 
642     void append(T node) nothrow @safe @nogc {
643         assert (getNextOf(node) is null, "Appending non-free node to list");
644         assert (node !is head && node !is tail, "Appending an invalid node to list");
645 
646         if (empty) {
647             head = tail = node;
648         }
649         else {
650             setNextOf(tail, node);
651             tail = node;
652         }
653         static if (withLength) length++;
654     }
655     void prepend(T node) nothrow @safe @nogc {
656         assert (getNextOf(node) is null && node !is head && node !is tail);
657 
658         if (empty) {
659             head = tail = node;
660         }
661         else {
662             setNextOf(node, head);
663             head = node;
664         }
665         static if (withLength) length++;
666     }
667 
668     T popHead() nothrow @safe @nogc {
669         assert (!empty);
670 
671         auto node = head;
672         head = getNextOf(head);
673         setNextOf(node, null);
674         static if (withLength) length--;
675 
676         if (head is null) {
677             tail = null;
678             static if (withLength) assert (length == 0);
679         }
680 
681         return node;
682     }
683 
684     void removeAll() nothrow {
685         while (!empty) {
686             popHead();
687         }
688     }
689 
690     void splice(_LinkedQueue* second) nothrow {
691         assert (second !is &this);
692         if (second.empty) {
693             return;
694         }
695         if (empty) {
696             head = second.head;
697         }
698         else {
699             setNextOf(tail, second.head);
700         }
701 
702         tail = second.tail;
703         static if (withLength) length += second.length;
704 
705         // For safety reasons, `second` is emptied (otherwise pop() from it would break this)
706         second.head = null;
707         second.tail = null;
708         static if (withLength) second.length = 0;
709     }
710 
711     static struct Range {
712         T front;
713 
714         @property empty() const pure @safe @nogc nothrow {
715             return front is null;
716         }
717         void popFront() nothrow {
718             assert (front);
719             front = getNextOf(front);
720         }
721     }
722     @property auto range() nothrow {
723         return Range(head);
724     }
725 }
726 
727 alias LinkedQueue(T, string nextAttr="_next") = _LinkedQueue!(T, nextAttr, false);
728 alias LinkedQueueWithLength(T, string nextAttr="_next") = _LinkedQueue!(T, nextAttr, true);
729 
730 unittest {
731     import std.stdio;
732     import std..string;
733 
734     static struct Node {
735         int value;
736         Node* _next;
737     }
738     Node[10] nodes;
739     foreach(int i, ref n; nodes) {
740         n.value = i;
741     }
742 
743     LinkedQueue!(Node*) queue;
744     assert (queue.empty);
745 
746     queue.append(&nodes[0]);
747     assert (!queue.empty);
748 
749     queue.append(&nodes[1]);
750     queue.append(&nodes[2]);
751     queue.append(&nodes[3]);
752     queue.append(&nodes[4]);
753     queue.append(&nodes[5]);
754     queue.append(&nodes[6]);
755 
756     queue.prepend(&nodes[7]);
757     queue.prepend(&nodes[8]);
758     queue.prepend(&nodes[9]);
759 
760     void matchElements(R)(R range, int[] expected) {
761         int[] arr;
762         foreach(n; range) {
763             arr ~= n.value;
764         }
765         //writeln(arr);
766         assert (arr == expected, "%s != %s".format(arr, expected));
767     }
768 
769     matchElements(queue.range, [9, 8, 7, 0, 1, 2, 3, 4, 5, 6]);
770     assert (!queue.empty);
771 
772     queue.removeAll();
773     assert (queue.empty);
774 
775     LinkedQueue!(Node*) queue2;
776 
777     queue.append(&nodes[0]);
778     queue.append(&nodes[1]);
779     queue.append(&nodes[2]);
780 
781     queue2.append(&nodes[3]);
782     queue2.append(&nodes[4]);
783     queue2.append(&nodes[5]);
784 
785     matchElements(queue.range, [0, 1, 2]);
786     matchElements(queue2.range, [3, 4, 5]);
787     queue.splice(&queue2);
788     assert(queue2.empty);
789     matchElements(queue.range, [0, 1, 2, 3, 4, 5]);
790 }
791 
792 unittest {
793     struct Node {
794         static Node[10] theNodes;
795 
796         int value;
797         ubyte nextIdx = ubyte.max;
798 
799         @property Node* _next() const nothrow @safe @nogc {
800             return nextIdx == ubyte.max ? null : &theNodes[nextIdx];
801         }
802         @property void _next(Node* n) nothrow @safe @nogc {
803             nextIdx = n is null ? ubyte.max : cast(ubyte)(n - &theNodes[0]);
804         }
805     }
806 
807     foreach(int i, ref n; Node.theNodes) {
808         n.value = 100 + i;
809     }
810 
811     LinkedQueue!(Node*) queue;
812     assert (queue.empty);
813 
814     queue.append(&Node.theNodes[0]);
815     assert (!queue.empty);
816     queue.append(&Node.theNodes[1]);
817     queue.append(&Node.theNodes[2]);
818     queue.append(&Node.theNodes[3]);
819     queue.append(&Node.theNodes[4]);
820 
821     int[] arr;
822     foreach(n; queue.range) {
823         arr ~= n.value;
824     }
825     assert(arr == [100, 101, 102, 103, 104]);
826 
827     queue.removeAll();
828     assert (queue.empty);
829 }
830 
831 unittest {
832     // Dummy node type for list. This is means primarily to make sure no one in the list implementation is comparing to null instead of using
833     // isValid. Nothing runs in this UT. If it compiles, it's fine
834     struct S {
835         alias OurList = _LinkedList!(S, "_next", "_prev", "owner", false);
836         @property S _next() pure nothrow @nogc @safe {
837             return invalid;
838         }
839         @property void _next(S rhs) pure nothrow @nogc @safe {
840         }
841         @property S _prev() pure nothrow @nogc @safe {
842             return invalid;
843         }
844         @property void _prev(S rhs) pure nothrow @nogc @safe {
845         }
846         OurList* owner;
847         bool isValid() const pure nothrow @safe @nogc {
848             return false;
849         }
850         enum invalid = S.init;
851     }
852 
853     S.OurList list;
854 }

Page generated by adrdox