1 module eventcore.internal.dlist; 2 3 struct StackDList(T) { 4 @safe nothrow @nogc: 5 6 private { 7 T* m_first, m_last; 8 size_t m_length; 9 } 10 11 @disable this(this); 12 13 void clear() 14 { 15 T* itm = m_first; 16 while (itm) { 17 auto next = itm.next; 18 itm.prev = null; 19 itm.next = null; 20 itm = next; 21 } 22 m_length = 0; 23 } 24 25 @property bool empty() const { return m_first is null; } 26 27 @property size_t length() const { return m_length; } 28 29 @property T* front() { return m_first; } 30 @property T* back() { return m_last; } 31 32 void insertFront(T* item) 33 { 34 assert(!item.prev && !item.next); 35 item.next = m_first; 36 if (m_first) { 37 m_first.prev = item; 38 m_first = item; 39 } else { 40 m_last = item; 41 m_first = item; 42 } 43 m_length++; 44 } 45 46 void insertBack(T* item) 47 { 48 assert(!item.prev && !item.next); 49 item.prev = m_last; 50 if (m_last) { 51 m_last.next = item; 52 m_last = item; 53 } else { 54 m_first = item; 55 m_last = item; 56 } 57 m_length++; 58 } 59 60 void insertAfter(T* item, T* after) 61 { 62 assert(!item.prev && !item.next); 63 if (!after) insertBack(item); 64 else { 65 item.prev = after; 66 item.next = after.next; 67 after.next = item; 68 if (item.next) item.next.prev = item; 69 else m_last = item; 70 } 71 m_length++; 72 } 73 74 void remove(T* item) 75 { 76 if (item.prev) item.prev.next = item.next; 77 else m_first = item.next; 78 if (item.next) item.next.prev = item.prev; 79 else m_last = item.prev; 80 item.prev = null; 81 item.next = null; 82 m_length--; 83 } 84 85 void removeFront() 86 { 87 if (m_first) remove(m_first); 88 m_length--; 89 } 90 91 void removeBack() 92 { 93 if (m_last) remove(m_last); 94 m_length--; 95 } 96 97 static struct Range { 98 private T* m_first, m_last; 99 100 this(T* first, T* last) 101 { 102 m_first = first; 103 m_last = last; 104 } 105 106 @property bool empty() const { return m_first is null; } 107 @property T* front() { return m_first; } 108 @property T* back() { return m_last; } 109 110 void popFront() { 111 assert(m_first !is null); 112 m_first = m_first.next; 113 if (!m_first) m_last = null; 114 } 115 116 void popBack() { 117 assert(m_last !is null); 118 m_last = m_last.prev; 119 if (!m_last) m_first = null; 120 } 121 } 122 123 Range opSlice() { return Range(m_first, m_last); } 124 } 125 126 unittest { 127 import std.algorithm.comparison : equal; 128 import std.algorithm.iteration : map; 129 130 struct S { size_t i; S* prev, next; } 131 132 S[10] s; 133 foreach (i, ref rs; s) rs.i = i; 134 135 StackDList!S list; 136 137 assert(list.empty); 138 assert(list[].empty); 139 list.insertBack(&s[0]); 140 assert(list[].map!(s => s.i).equal([0])); 141 list.insertBack(&s[1]); 142 assert(list[].map!(s => s.i).equal([0, 1])); 143 list.insertAfter(&s[2], &s[0]); 144 assert(list[].map!(s => s.i).equal([0, 2, 1])); 145 list.insertFront(&s[3]); 146 assert(list[].map!(s => s.i).equal([3, 0, 2, 1])); 147 list.removeBack(); 148 assert(list[].map!(s => s.i).equal([3, 0, 2])); 149 list.remove(&s[0]); 150 assert(list[].map!(s => s.i).equal([3, 2])); 151 list.remove(&s[3]); 152 assert(list[].map!(s => s.i).equal([2])); 153 list.remove(&s[2]); 154 assert(list.empty); 155 assert(list[].empty); 156 }