1 module prova.util.linkedlist; 2 3 import std.typecons; 4 5 /** 6 * Linked list node 7 */ 8 class Node(T) 9 { 10 private LinkedList!T list; 11 private Node!T next; 12 private Node!T last; 13 private Nullable!T _value; 14 15 /** 16 * Retrieves the stored value 17 */ 18 @property T value() 19 { 20 return _value; 21 } 22 23 /** 24 * Modifies the stored value 25 */ 26 @property void value(T value) 27 { 28 _value = value; 29 } 30 31 /** 32 * Gets the node previous in order 33 */ 34 Node!T getLast() 35 { 36 return last; 37 } 38 39 /** 40 * Gets the node next in order 41 */ 42 Node!T getNext() 43 { 44 return next; 45 } 46 47 /** 48 * Detaches the node from the list 49 */ 50 void remove() 51 { 52 if(last) 53 last.next = next; 54 55 if(next) 56 next.last = last; 57 58 if(list.last == this) 59 list.last = null; 60 61 if(list.first == this) 62 list.first = null; 63 64 list.count--; 65 } 66 } 67 68 /** 69 * LinkedList template 70 */ 71 class LinkedList(T) 72 { 73 private Node!T first; 74 private Node!T last; 75 private int count = 0; 76 77 /** 78 * Returns the node count 79 */ 80 @property int length() 81 { 82 return count; 83 } 84 85 /// 86 Node!T getFirstNode() 87 { 88 return first; 89 } 90 91 /// 92 Node!T getLastNode() 93 { 94 return last; 95 } 96 97 /** 98 * Creates a node and places it at the start of the list 99 */ 100 Node!T insertFront(T value) 101 { 102 return insertBefore(value, first); 103 } 104 105 /** 106 * Creates a node and places it at the end of the list 107 */ 108 Node!T insertBack(T value) 109 { 110 return insertAfter(value, last); 111 } 112 113 /** 114 * Creates a node in the list placed before the specified node 115 */ 116 Node!T insertBefore(T value, Node!T node) 117 { 118 if(!node && first) 119 return insertBefore(value, first); 120 121 Node!T storedNode = new Node!T; 122 storedNode.value = value; 123 storedNode.list = this; 124 125 if(node) { 126 storedNode.last = node.last; 127 node.last = storedNode; 128 storedNode.next = node; 129 } else { 130 first = last = storedNode; 131 } 132 133 if(storedNode.last) 134 storedNode.last.next = storedNode; 135 136 count++; 137 return storedNode; 138 } 139 140 /** 141 * Creates a node in the list placed after the specified node 142 */ 143 Node!T insertAfter(T value, Node!T node) 144 { 145 if(!node && last) 146 return insertAfter(value, last); 147 148 Node!T storedNode = new Node!T; 149 storedNode.value = value; 150 storedNode.list = this; 151 152 if(node) { 153 storedNode.next = node.next; 154 node.next = storedNode; 155 storedNode.last = node; 156 } else { 157 first = last = storedNode; 158 } 159 160 if(storedNode.next) 161 storedNode.next.last = storedNode; 162 163 count++; 164 return storedNode; 165 } 166 167 /** 168 * Tests if the list contains a node with the specified value 169 */ 170 bool contains(T value) 171 { 172 foreach(Node!T node; this) 173 if(node.value == value) 174 return true; 175 176 return false; 177 } 178 179 /** 180 * Removes the first node with the specified value 181 */ 182 void remove(T value) 183 { 184 foreach(Node!T node; this) { 185 if(node.value == value) { 186 node.remove(); 187 break; 188 } 189 } 190 } 191 192 /** 193 * Empties the LinkedList 194 */ 195 void clear() 196 { 197 first = null; 198 last = null; 199 count = 0; 200 } 201 202 int opApply(int delegate(Node!T result) dg) 203 { 204 int result = 0; 205 206 for(Node!T node = first; node; node = node.next) { 207 result = dg(node); 208 209 if(result) 210 break; 211 } 212 213 return result; 214 } 215 216 int opApply(int delegate(ref T result) dg) 217 { 218 int result = 0; 219 220 for(Node!T node = first; node; node = node.next) { 221 T value = node.value; 222 result = dg(value); 223 node.value = value; 224 225 if(result) 226 break; 227 } 228 229 return result; 230 } 231 }