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 }