1 module tagion.utils.Queue;
2 
3 @safe class Queue(T) {
4     private Element _head;
5     private Element _tail;
6     static class Element {
7         Element _next;
8         Element _previous;
9         private T data;
10         this(T data) {
11             this.data = data;
12         }
13 
14         ~this() {
15             _next = _previous = null;
16         }
17     }
18 
19     void write(T data) nothrow {
20         auto element = new Element(data);
21         if (_head) {
22             element._next = _head;
23             _head._previous = element;
24             _head = element;
25         }
26         else {
27             _head = element;
28             _tail = element;
29         }
30     }
31 
32     T read() nothrow
33     in {
34         assert(_tail, "Data queue is empty");
35     }
36     do {
37         auto entry = _tail;
38         scope (exit) {
39             entry._previous = null;
40             //            entry.destroy;
41         }
42         immutable result = entry.data;
43         if (_tail is _head) {
44             _tail = _head = null;
45         }
46         else {
47             entry._previous._next = null;
48             _tail = entry._previous;
49         }
50         return result;
51     }
52 
53     ~this() {
54         @safe
55         void erase(Element e) {
56             if (e) {
57                 erase(e._next);
58                 e._next = null;
59                 e._previous = null;
60             }
61         }
62 
63         erase(_head);
64         _head = _tail = null;
65     }
66 
67     void remove(Element entry) {
68         if (entry) {
69             if (_head is entry) {
70                 _head = entry._next;
71             }
72             if (_tail is entry) {
73                 _tail = entry._previous;
74             }
75             if (entry._previous) {
76                 entry._previous._next = entry._next;
77             }
78             if (entry._next) {
79                 entry._next._previous = entry._previous;
80             }
81         }
82     }
83 
84     @nogc bool empty() const pure nothrow {
85         return _head is null;
86     }
87 
88     Range opSlice() {
89         return Range(this);
90     }
91 
92     struct Range {
93         private Element entry;
94         private Queue owner;
95         this(Queue owner) pure nothrow {
96             this.owner = owner;
97             entry = owner._tail;
98         }
99 
100         pure nothrow {
101             bool empty() const {
102                 return entry is null;
103             }
104 
105             void popFront() {
106                 entry = entry._previous;
107             }
108             // void popBack() {
109             //     entry=entry._previous;
110             // }
111             inout(T) front() inout {
112                 return entry.data;
113             }
114         }
115 
116         Range save() nothrow {
117             Range result;
118             result.owner = owner;
119             result.entry = entry;
120             return result;
121         }
122 
123         void remove() {
124             owner.remove(entry);
125         }
126     }
127 
128     unittest { // One element
129         auto q = new Queue!string;
130         assert(q.empty);
131         immutable elm1 = "1";
132 
133         q.write(elm1);
134         assert(!q.empty);
135         assert(q.read == elm1);
136         assert(q.empty);
137     }
138 
139     unittest { // two element
140         auto q = new Queue!string;
141         immutable elm1 = "A";
142         immutable elm2 = "B";
143         assert(q.empty);
144         q.write(elm1);
145         assert(!q.empty);
146         q.write(elm2);
147         assert(!q.empty);
148         assert(q.read == elm1);
149         assert(q.read == elm2);
150         assert(q.empty);
151 
152     }
153 
154     unittest { // More elements
155         immutable elm1 = "A";
156         immutable elm2 = "B";
157         immutable elm3 = "C";
158         auto q = new Queue!string;
159 
160         q.write(elm1);
161         assert(!q.empty);
162         q.write(elm2);
163         assert(!q.empty);
164         q.write(elm3);
165         assert(!q.empty);
166 
167         assert(q.read == elm1);
168         assert(!q.empty);
169         assert(q.read == elm2);
170         assert(!q.empty);
171         assert(q.read == elm3);
172         assert(q.empty);
173     }
174 
175     unittest {
176         immutable elm = [
177             "A",
178             "B",
179             "C"
180         ];
181         { // Iterator
182             auto q = new Queue!string;
183             foreach (ref e; elm) {
184                 q.write(e);
185             }
186 
187             uint i = 0;
188             foreach (d; q[]) {
189                 assert(elm[i] == d);
190                 i++;
191             }
192         }
193         { // Remove first
194             auto q = new Queue!string;
195             foreach (ref e; elm) {
196                 q.write(e);
197             }
198 
199             auto iter = q[];
200 
201             iter.remove;
202             assert(q.read == elm[1]);
203             assert(q.read == elm[2]);
204         }
205         { // Remove middel
206             auto q = new Queue!string;
207             foreach (ref e; elm) {
208                 q.write(e);
209             }
210 
211             auto iter = q[];
212             iter.popFront;
213             iter.remove;
214             assert(q.read == elm[0]);
215             assert(q.read == elm[2]);
216         }
217         { // Remove last
218             auto q = new Queue!string;
219             foreach (ref e; elm) {
220                 q.write(e);
221             }
222 
223             auto iter = q[];
224             iter.popFront;
225             iter.popFront;
226             iter.remove;
227             assert(q.read == elm[0]);
228             assert(q.read == elm[1]);
229         }
230     }
231 
232 }