1 module collections.linkedmap; 2 3 import std.functional : binaryFun; 4 public import collections.commons; 5 6 /** 7 * Implements a linked map datastructure. 8 * Similar to TreeMap, but instead relies on the equals function, which can mean it can compare keys much easier, 9 * meaning much bigger data can be compared easily without hashing. Also it doesn't need to rebalance a tree, which 10 * lowers insertion complexity at the cost of higher theoretical access times (n). 11 * This linked map has the behavior of putting new elements at the back, resulting in an ordered map similar to 12 * what PHP and YAML also has. 13 * `ovrwrtBhvr` changes the overwrite behavior when keymatches are found. If true, then if a key is already existing, 14 * then it'll overwrite it at the given position. If false, then the matching key will be first deleted, then the 15 * new one will be always put in the end. 16 */ 17 18 public struct LinkedMap(K, E, bool nogcIndexing = true, alias equal = "a == b", bool ovrwrtBhvr = true) { 19 private struct Node { 20 K key; ///Identifier key 21 E elem; ///Element stored within the node 22 Node* next; ///Next node, null if none exists 23 Node* prev; ///Previous node, null if none exists 24 25 ///Keturns a string representation of the node. 26 string toString() const { 27 import std.conv : to; 28 string result = "key: " ~ to!string(key) ~ " ; elem: " ~ to!string(elem); 29 if (next) result ~= " ; next: [" ~ next.toString ~ "]"; 30 return result; 31 } 32 } 33 protected Node* root; ///Root element. 34 protected Node* last; ///Last element. 35 protected size_t _length;///N. of currently stored elements 36 /** 37 * opApply override for foreach. 38 */ 39 int opApply(scope int delegate(ref E) dg) { 40 Node* crnt = root; 41 while (crnt) { 42 if (dg(crnt.elem)) return 1; 43 crnt = crnt.next; 44 } 45 return 0; 46 } 47 /** 48 * opApply override for foreach. 49 */ 50 int opApply(scope int delegate(K, ref E) dg) { 51 Node* crnt = root; 52 while (crnt) { 53 if (dg(crnt.key, crnt.elem)) return 1; 54 crnt = crnt.next; 55 } 56 return 0; 57 } 58 /** 59 * opApplyReverse override for foreach. 60 */ 61 int opApplyReverse(scope int delegate(ref E) dg) { 62 Node* crnt = last; 63 while (crnt) { 64 if (dg(crnt.elem)) return 1; 65 crnt = crnt.prev; 66 } 67 return 0; 68 } 69 /** 70 * opApplyReverse override for foreach. 71 */ 72 int opApplyReverse(scope int delegate(K, ref E) dg) { 73 Node* crnt = last; 74 while (crnt) { 75 if (dg(crnt.key, crnt.elem)) return 1; 76 crnt = crnt.prev; 77 } 78 return 0; 79 } 80 package static string makeFunc() { 81 string makeFuncIndiv(string args) { 82 return ` 83 int opApply(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 84 Node* crnt = root; 85 while (crnt) { 86 if (dg(crnt.elem)) return 1; 87 crnt = crnt.next; 88 } 89 return 0; 90 } 91 int opApply(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 92 Node* crnt = root; 93 while (crnt) { 94 if (dg(crnt.key, crnt.elem)) return 1; 95 crnt = crnt.next; 96 } 97 return 0; 98 } 99 int opApplyReverse(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 100 Node* crnt = last; 101 while (crnt) { 102 if (dg(crnt.elem)) return 1; 103 crnt = crnt.prev; 104 } 105 return 0; 106 } 107 int opApplyReverse(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 108 Node* crnt = last; 109 while (crnt) { 110 if (dg(crnt.key, crnt.elem)) return 1; 111 crnt = crnt.prev; 112 } 113 return 0; 114 }`; 115 } 116 string result; 117 foreach (attr; attrList) { 118 result ~= makeFuncIndiv(attr); 119 } 120 return result; 121 } 122 mixin(makeFunc); 123 static if(nogcIndexing) { 124 /** 125 * Returns the element with the given key. 126 * Returns E.init if not found. 127 */ 128 E opIndex(K key) @nogc @safe pure nothrow { 129 Node* crnt = root; 130 while (crnt) { 131 if (binaryFun!equal(crnt.key, key)) return crnt.elem; 132 crnt = crnt.next; 133 } 134 return E.init; 135 } 136 /** 137 * Returns the pointer of the element with the given key. 138 * Returns null if not found. 139 */ 140 E* ptrOf(K key) @nogc @safe pure nothrow { 141 Node* crnt = root; 142 while (crnt) { 143 if (binaryFun!equal(crnt.key, key)) return &crnt.elem; 144 crnt = crnt.next; 145 } 146 return null; 147 } 148 /** 149 * Returns true if key is found. 150 */ 151 bool has(K key) @nogc @safe pure nothrow { 152 Node* crnt = root; 153 while (crnt) { 154 if (binaryFun!equal(crnt.key, key)) return true; 155 crnt = crnt.next; 156 } 157 return false; 158 } 159 auto opBinaryRight(string op)(const K key) @nogc @safe pure nothrow { 160 static if (op == "in") { 161 return has(key); 162 } else static assert(0, "Operator not supported!"); 163 } 164 } else { 165 /** 166 * Returns the element with the given key. 167 * Returns E.init if not found. 168 */ 169 ref E opIndex(K key) @safe pure { 170 Node* crnt = root; 171 while (crnt) { 172 if (binaryFun!equal(crnt.key, key)) return crnt.elem; 173 crnt = crnt.next; 174 } 175 throw new ElementNotFoundException("Key not found!"); 176 } 177 /** 178 * Returns true if key is found. 179 */ 180 bool has(K key) @safe pure { 181 Node* crnt = root; 182 while (crnt) { 183 if (binaryFun!equal(crnt.key, key)) return true; 184 crnt = crnt.next; 185 } 186 return false; 187 } 188 auto opBinaryRight(string op)(const K key) @safe pure { 189 static if (op == "in") { 190 return has(key); 191 } else static assert(0, "Operator not supported!"); 192 } 193 } 194 /** 195 * Assigns a value to the given key. 196 */ 197 auto opIndexAssign(E value, K key) @safe pure nothrow { 198 Node** crnt = &root; 199 while (*crnt) { 200 static if (ovrwrtBhvr) { 201 if (binaryFun!equal((*crnt).key, key)) { 202 return (*crnt).elem = value; 203 } 204 } else { 205 if (binaryFun!equal((*crnt).key, key)) { 206 if ((*crnt).next) (*crnt).next.prev = (*crnt).prev; 207 crnt = &(*crnt).next; 208 _length--; 209 } 210 } 211 //prev = crnt; 212 crnt = &(*crnt).next; 213 } 214 //prev.next = new Node(key, value, null); 215 *crnt = new Node(key, value, null, *crnt); 216 last = *crnt; 217 _length++; 218 return value; 219 } 220 /** 221 * Removes a value with the given key and returns it. 222 */ 223 E remove(K key) @safe pure nothrow { 224 Node** crnt = &root; 225 while (*crnt) { 226 if (binaryFun!equal((*crnt).key, key)) { 227 E result = (*crnt).elem; 228 //if ((*crnt).prev) (*crnt).prev.next = (*crnt).next; 229 if ((*crnt).next is null) last = (*crnt).prev; 230 else (*crnt).next.prev = (*crnt).prev; 231 *crnt = (*crnt).next; 232 _length--; 233 return result; 234 } 235 crnt = &(*crnt).next; 236 } 237 return E.init; 238 } 239 /** 240 * Returns the number of elements in the LinkedMap. 241 */ 242 @property size_t length() @nogc @safe pure nothrow const { 243 return _length; 244 } 245 ///Returns the string representation of this container format 246 string toString() const { 247 if (root) return root.toString; 248 else return "empty"; 249 } 250 } 251 252 unittest { 253 import std.random : uniform; 254 import std.exception : assertThrown; 255 import std.stdio : writeln; 256 { 257 alias IntMap = LinkedMap!(int, int); 258 IntMap test0, test1; 259 test0[0] = 0; 260 test0[0] = 1; 261 test0[1] = 1; 262 test0[2] = 1; 263 test0[3] = 1; 264 test0[4] = 1; 265 assert(test0.length == 5, "length mismatch!"); 266 test0.remove(3); 267 assert(test0.length == 4, "item deletion error!"); 268 assert(test0.ptrOf(0), "pointer error!"); 269 assert(!test0.ptrOf(10), "pointer error!"); 270 271 for(int i ; i < 256 ; i++) 272 test1[i] = uniform(0, 65_536); 273 assert(test1.length == 256, "length mismatch!"); 274 foreach(elem ; test1) { 275 276 } 277 foreach(key, elem ; test1) { 278 279 } 280 foreach_reverse(elem ; test1) { 281 282 } 283 foreach_reverse(key, elem ; test1) { 284 285 } 286 } 287 { 288 alias IntMap = LinkedMap!(int, int, false); 289 IntMap test2; 290 test2[0] = 1; 291 test2[1] = 1; 292 test2[2] = 1; 293 test2[3] = 1; 294 test2[4] = 1; 295 assert(4 in test2); 296 assertThrown!ElementNotFoundException(test2[8]); 297 } 298 //test FIFO behavior 299 { 300 alias IntMap = LinkedMap!(int, int, true, "a == b", true); 301 IntMap test3; 302 test3[0] = 0; 303 writeln(test3); 304 test3[1] = 1; 305 writeln(test3); 306 test3[2] = 2; 307 writeln(test3); 308 test3[3] = 3; 309 writeln(test3); 310 test3[4] = 4; 311 writeln(test3); 312 //overwriting key 3 should not distrupt the order 313 test3[3] = 5; 314 assert(4 in test3); 315 writeln(test3); 316 } 317 { 318 alias IntMap = LinkedMap!(int, int, true, "a == b", false); 319 IntMap test3; 320 test3[0] = 0; 321 writeln(test3); 322 test3[1] = 1; 323 writeln(test3); 324 test3[2] = 2; 325 writeln(test3); 326 test3[3] = 3; 327 writeln(test3); 328 test3[4] = 4; 329 writeln(test3); 330 //overwriting key 3 should put key 3 at the end 331 test3[3] = 5; 332 assert(4 in test3); 333 writeln(test3); 334 } 335 }