1 module tagion.utils.DList;
2 
3 import tagion.utils.Result;
4 
5 @safe struct DList(E) {
6     @nogc struct Element {
7         E entry;
8         protected Element* next;
9         protected Element* prev;
10         this(E e) pure nothrow {
11             entry = e;
12         }
13     }
14 
15     private Element* _head;
16     private Element* _tail;
17     // Number of element in the DList
18     private uint count;
19     Element* unshift(E e) nothrow {
20         auto element = new Element(e);
21         if (_head is null) {
22             element.prev = null;
23             element.next = null;
24             _head = _tail = element;
25         }
26         else {
27             element.next = _head;
28             _head.prev = element;
29             _head = element;
30             _head.prev = null;
31         }
32         count++;
33         return element;
34     }
35 
36     Result!E shift() nothrow {
37         if (_head is null) {
38             return Result!E(E.init, this.stringof ~ " is empty");
39         }
40         scope (success) {
41             _head = _head.next;
42             _head.prev = null;
43             count--;
44         }
45         return Result!E(_head.entry);
46     }
47 
48     const(Element*) push(E e) nothrow {
49         auto element = new Element(e);
50         if (_head is null) {
51             _head = _tail = element;
52         }
53         else {
54             _tail.next = element;
55             element.prev = _tail;
56             _tail = element;
57         }
58         count++;
59         return element;
60     }
61 
62     Result!E pop() nothrow {
63         Element* result;
64         if (_tail !is null) {
65             result = _tail;
66             _tail = _tail.prev;
67             if (_tail is null) {
68                 _head = null;
69             }
70             else {
71                 _tail.next = null;
72             }
73             count--;
74             return Result!E(result.entry);
75 
76         }
77         return Result!E(E.init, "Pop from an empty list");
78     }
79 
80     /**
81        Returns; true if the element was not found
82      */
83     @nogc
84     bool remove(Element* e) nothrow
85     in {
86         assert(e !is null);
87         if (_head is null) {
88             assert(count == 0);
89         }
90         if (e.next is null) {
91             assert(e is _tail);
92         }
93         if (e.prev is null) {
94             assert(e is _head);
95         }
96     }
97     do {
98         if (_head is null) {
99             return true;
100             //            throw new UtilException("Remove from an empty list");
101         }
102         if (_head is e) {
103             if (_head.next is null) {
104                 _head = _tail = null;
105             }
106             else {
107                 _head = _head.next;
108                 _head.prev = null;
109                 if (_head is _tail) {
110                     _tail.prev = null;
111                 }
112             }
113         }
114         else if (_tail is e) {
115             _tail = _tail.prev;
116             if (_tail is null) {
117                 _head = null;
118             }
119             else {
120                 _tail.next = null;
121             }
122         }
123         else {
124             e.next.prev = e.prev;
125             e.prev.next = e.next;
126         }
127         count--;
128         return false;
129     }
130 
131     @nogc
132     void moveToFront(Element* e) nothrow
133     in {
134         assert(e !is null);
135     }
136     do {
137         if (e !is _head) {
138             if (e == _tail) {
139                 _tail = _tail.prev;
140                 _tail.next = null;
141             }
142             else {
143                 e.next.prev = e.prev;
144                 e.prev.next = e.next;
145             }
146             e.next = _head;
147             _head.prev = e;
148             _head = e;
149             _head.prev = null;
150         }
151     }
152 
153     @nogc
154     uint length() pure const nothrow {
155         return count;
156     }
157 
158     @nogc inout(Element*) first() inout pure nothrow {
159         return _head;
160     }
161 
162     @nogc inout(Element*) last() inout pure nothrow {
163         return _tail;
164     }
165 
166     @nogc Range!false opSlice() pure nothrow {
167         return Range!false(this);
168     }
169 
170     @nogc Range!true revert() pure nothrow {
171         return Range!true(this);
172     }
173 
174     @nogc struct Range(bool revert) {
175         private Element* cursor;
176         this(DList l) pure nothrow {
177             static if (revert) {
178                 cursor = l._tail;
179             }
180             else {
181                 cursor = l._head;
182             }
183         }
184 
185         bool empty() const pure nothrow {
186             return cursor is null;
187         }
188 
189         void popFront() nothrow {
190             if (cursor !is null) {
191                 static if (revert) {
192                     cursor = cursor.prev;
193                 }
194                 else {
195                     cursor = cursor.next;
196                 }
197             }
198         }
199 
200         // void popBack() nothrow {
201         //     if ( cursor !is null) {
202         //         static if (revert) {
203         //             cursor = cursor.next;
204         //         }
205         //         else {
206         //             cursor = cursor.prev;
207         //         }
208         //     }
209         // }
210 
211         E front() pure nothrow {
212             return cursor.entry;
213         }
214 
215         // alias back=front;
216 
217         inout(Element*) current() inout pure nothrow {
218             return cursor;
219         }
220     }
221 
222     invariant {
223         if (_head is null) {
224             assert(_tail is null);
225         }
226         else {
227             assert(_head.prev is null);
228             assert(_tail.next is null);
229             if (_head is _tail) {
230                 assert(_head.next is null);
231                 assert(_tail.prev is null);
232             }
233         }
234 
235     }
236 }
237 
238 unittest {
239     { // Empty element test
240         DList!int l;
241         //        auto e = l.shift;
242         //        assert(e is null);
243         // bool flag;
244         assert(l.length == 0);
245         {
246             const r = l.pop;
247             assert(r.error);
248         }
249         assert(l.length == 0);
250         {
251             const r = l.shift;
252             assert(r.error);
253         }
254         assert(l.length == 0);
255     }
256 
257     { // One element test
258         DList!int l;
259         l.unshift(7);
260         assert(l.length == 1);
261         auto first = l.first;
262         auto last = l.last;
263         assert(first !is null);
264         assert(last !is null);
265         assert(first is last);
266         l.remove(first);
267         assert(l.length == 0);
268     }
269     { // two element test
270         DList!int l;
271         assert(l.length == 0);
272         l.unshift(7);
273         assert(l.length == 1);
274         l.unshift(4);
275         assert(l.length == 2);
276         auto first = l.first;
277         auto last = l.last;
278         assert(first.entry == 4);
279         assert(last.entry == 7);
280         // moveToFront test
281         l.moveToFront(last);
282         assert(l.length == 2);
283         first = l.first;
284         last = l.last;
285         assert(first.entry == 7);
286         assert(last.entry == 4);
287     }
288     { // pop
289         import std.algorithm.comparison : equal;
290         import std.array;
291 
292         DList!int l;
293         enum amount = 4;
294         int[] test;
295         foreach (i; 0 .. amount) {
296             l.push(i);
297             test ~= i;
298         }
299         auto I = l[];
300         // This statement does not work anymore
301         // assert(equal(I, test));
302         assert(array(I) == test);
303 
304         foreach_reverse (i; 0 .. amount) {
305             assert(l.pop.value == i);
306             assert(l.length == i);
307         }
308     }
309     { // More elements test
310         import std.algorithm.comparison : equal;
311 
312         DList!int l;
313         enum amount = 4;
314         foreach (i; 0 .. amount) {
315             l.push(i);
316         }
317         assert(l.length == amount);
318 
319         { // Forward iteration test
320             auto I = l[];
321             uint i;
322             for (i = 0; !I.empty; I.popFront, i++) {
323                 assert(I.front == i);
324             }
325             assert(i == amount);
326             i = 0;
327             I = l[];
328             foreach (entry; I) {
329                 assert(entry == i);
330                 i++;
331             }
332             assert(i == amount);
333         }
334 
335         assert(l.length == amount);
336 
337         import std.algorithm : map;
338         import std.stdio;
339 
340         { // Backward iteration test
341             auto I = l.revert;
342             uint i;
343             for (i = amount; !I.empty; I.popFront) {
344                 i--;
345                 assert(I.front == i);
346             }
347             assert(i == 0);
348             i = amount;
349 
350             foreach (entry; l.revert) {
351                 i--;
352                 assert(entry == i);
353             }
354             assert(i == 0);
355         }
356 
357         // moveToFront for the second element ( element number 1 )
358 
359         {
360             import std.array;
361 
362             auto I = l[];
363             I.popFront;
364             auto current = I.current;
365             l.moveToFront(current);
366             assert(l.length == amount);
367             // The element shoud now be ordred as
368             // [1, 0, 2, 3]
369             I = l[];
370             // This statem does not work anymore
371             // assert(equal(I, [1, 0, 2, 3]));
372             assert(array(I) == [1, 0, 2, 3]);
373         }
374 
375         {
376             import std.array;
377 
378             auto I = l[];
379             I.popFront;
380             I.popFront;
381             auto current = I.current;
382             l.moveToFront(current);
383             assert(l.length == amount);
384             // The element shoud now be ordred as
385             // [1, 0, 2, 3]
386             I = l[];
387             // This statem does not work anymore
388             // assert(equal(I, [2, 1, 0, 3]));
389             assert(array(I) == [2, 1, 0, 3]);
390         }
391 
392     }
393 }