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 }