m3.List source code

1 module m3.List;
2 
3 private:
4 
5 static import m3.m3;
6 
7 static import std.traits;
8 alias isArray = std.traits.isArray;
9 
10 public:
11 
12 struct DoubleLinkedList(T) {
13     static assert(!isArray!(T), "Double Linked List cannot be used with an array");
14 
15 static struct Node {
16     T value;
17     Node* next = null;
18     Node* previous = null;
19 }
20 
21 private:
22     Node* _front;
23     Node* _end;
24 
25     size_t _length;
26 
27 public:
28     @nogc
29     ~this() {
30         Node* cur = _front;
31         while (cur) {
32             Node* tmp = cur;
33             cur = tmp.next;
34             m3.m3.destruct(tmp);
35         }
36     }
37 
38     @safe
39     @nogc
40     @property
41     size_t length() const pure nothrow {
42         return _length;
43     }
44 
45     @nogc
46     @property
47     inout(Node*) front() inout pure nothrow {
48         return _front;
49     }
50 
51     @nogc
52     @property
53     inout(Node*) end() inout pure nothrow {
54         return _end;
55     }
56 
57     @nogc
58     void pushBack(U : T)(auto ref U item) nothrow {
59         Node* newEnd = m3.m3.make!(Node);
60         newEnd.value = item;
61         newEnd.previous = _end;
62 
63         if (_end)
64             _end.next = newEnd;
65 
66         _end = newEnd;
67 
68         if (_length == 0)
69             _front = _end;
70 
71         _length++;
72     }
73 
74     @nogc
75     void pushFront(U : T)(auto ref U item) nothrow {
76         Node* newFront = m3.m3.make!(Node);
77         newFront.value = item;
78         newFront.next = _front;
79 
80         if (_front)
81             _front.previous = newFront;
82 
83         _front = newFront;
84 
85         if (_length == 0)
86             _end = _front;
87 
88         _length++;
89     }
90 
91     @nogc
92     void popBack() nothrow {
93         if (_end) {
94             Node* oldEnd = _end;
95 
96             _end = _end.previous;
97             if (_end)
98                 _end.next = null;
99 
100             m3.m3.destruct(oldEnd);
101             _length--;
102         }
103     }
104 
105     @nogc
106     void popFront() nothrow {
107         if (_front) {
108             Node* oldFront = _front;
109 
110             _front = _front.next;
111             if (_front)
112                 _front.previous = null;
113 
114             m3.m3.destruct(oldFront);
115             _length--;
116         }
117     }
118 
119     @nogc
120     void erase(Node* node) {
121         if (!node)
122             return;
123 
124         if (node is _end)
125             return this.popBack();
126         if (node is _front)
127             return this.popFront();
128 
129         Node* next = node.next;
130         Node* prev = node.previous;
131 
132         next.previous = prev;
133         prev.next = next;
134 
135         m3.m3.destruct(node);
136         _length--;
137     }
138 }
139 
140 @nogc
141 unittest {
142     DoubleLinkedList!(char) dll;
143     dll.pushBack('a');
144     dll.pushFront('H');
145     dll.pushBack('y');
146 
147     auto cur = dll.front;
148     assert(cur.value == 'H');
149     assert(cur.next.value == 'a');
150     assert(cur.next.next.value == 'y');
151 
152     dll.popBack();
153     cur = dll.front;
154 
155     assert(cur.value == 'H');
156     assert(cur.next.value == 'a');
157 
158     dll.popBack();
159     cur = dll.front;
160 
161     assert(cur.value == 'H');
162 
163     dll.pushBack('a');
164     dll.pushBack('y');
165 
166     cur = dll.front;
167     
168     assert(cur.value == 'H');
169     assert(cur.next.value == 'a');
170     assert(cur.next.next.value == 'y');
171 
172     dll.popFront();
173     cur = dll.front;
174     
175     assert(cur.value == 'a');
176     assert(cur.next.value == 'y');
177 
178     dll.popFront();
179     cur = dll.front;
180     
181     assert(cur.value == 'y');
182 
183     dll.pushBack('a');
184     dll.pushBack('y');
185 
186     cur = dll.front;
187 
188     assert(cur.value == 'y');
189     assert(cur.next.value == 'a');
190     assert(cur.next.next.value == 'y');
191 
192     dll.erase(cur.next);
193     cur = dll.front;
194 
195     assert(cur.value == 'y');
196     assert(cur.next.value == 'y');
197 }