1 module collections.linkedhashmap; 2 3 import collections.commons; 4 import std.functional : binaryFun; 5 import std.traits; 6 7 import collections.linkedmap; 8 9 /** 10 * Implements a linked hashmap. 11 * If retainKeys enabled, the map will retain the original keys and hash collisions can be resorted, but can be disabled 12 * by setting keyEqual to null. 13 * It is a modified linked map, and the `ovrwrtBhvr` still works as with the linked map. 14 */ 15 public struct LinkedHashMap(K, E, alias hashFunc = defaultHash128!(K), alias equal = "a == b", bool retainKeys = false, 16 alias keyEqual = "a == b", bool ovrwrtBhvr = true) { 17 ///true if nogc Indexing is enabled. 18 static enum bool nogcIndexing = hasFunctionAttributes!(hashFunc, "@nogc"); 19 alias HashType = ReturnType!hashFunc; 20 21 private struct Node { 22 HashType hashCode; ///Identifier hash 23 static if (retainKeys) { 24 K key; ///The key for this node 25 } 26 E elem; ///Element stored within the node 27 Node* next; ///Next node, null if none exists 28 Node* prev; ///Previous node, null if none exists 29 ///Keturns a string representation of the node. 30 string toString() const { 31 import std.conv : to; 32 string result = "hashCode: " ~ to!string(hashCode) ~ " ; elem: " ~ to!string(elem); 33 static if (retainKeys) result ~= " ; key: " ~ to!string(key); 34 if (next) result ~= " ; next: [" ~ next.toString ~ "]"; 35 return result; 36 } 37 } 38 39 protected Node* root; ///Root element. 40 protected Node* last; ///Last element. 41 protected size_t _length;///N. of currently stored elements 42 static if (retainKeys) { 43 /** 44 * opApply override for foreach 45 */ 46 int opApply(scope int delegate(ref E) dg) { 47 Node* crnt = root; 48 while (crnt) { 49 if (dg(crnt.elem)) return 1; 50 crnt = crnt.next; 51 } 52 return 0; 53 } 54 /** 55 * opApply override for foreach 56 */ 57 int opApply(scope int delegate(K, ref E) dg) { 58 Node* crnt = root; 59 while (crnt) { 60 if (dg(crnt.key, crnt.elem)) return 1; 61 crnt = crnt.next; 62 } 63 return 0; 64 } 65 /** 66 * opApplyReverse override for foreach_reverse 67 */ 68 int opApplyReverse(scope int delegate(ref E) dg) { 69 Node* crnt = last; 70 while (crnt) { 71 if (dg(crnt.elem)) return 1; 72 crnt = crnt.prev; 73 } 74 return 0; 75 } 76 /** 77 * opApplyReverse override for foreach_reverse 78 */ 79 int opApplyReverse(scope int delegate(K, ref E) dg) { 80 Node* crnt = last; 81 while (crnt) { 82 if (dg(crnt.key, crnt.elem)) return 1; 83 crnt = crnt.prev; 84 } 85 return 0; 86 } 87 package static string makeFunc() { 88 string makeFuncIndiv(string args) { 89 return ` 90 int opApply(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 91 Node* crnt = root; 92 while (crnt) { 93 if (dg(crnt.elem)) return 1; 94 crnt = crnt.next; 95 } 96 return 0; 97 } 98 int opApply(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 99 Node* crnt = root; 100 while (crnt) { 101 if (dg(crnt.key, crnt.elem)) return 1; 102 crnt = crnt.next; 103 } 104 return 0; 105 } 106 int opApplyReverse(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 107 Node* crnt = last; 108 while (crnt) { 109 if (dg(crnt.elem)) return 1; 110 crnt = crnt.prev; 111 } 112 return 0; 113 } 114 int opApplyReverse(scope int delegate(K, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 115 Node* crnt = last; 116 while (crnt) { 117 if (dg(crnt.key, crnt.elem)) return 1; 118 crnt = crnt.prev; 119 } 120 return 0; 121 }`; 122 } 123 string result; 124 foreach (attr; attrList) { 125 result ~= makeFuncIndiv(attr); 126 } 127 return result; 128 } 129 mixin(makeFunc); 130 /** 131 * Assigns a value to the given key. 132 */ 133 auto opIndexAssign(E value, K key) @safe pure nothrow { 134 const HashType hashCode = hashFunc(key); 135 Node** crnt = &root; 136 while (*crnt) { 137 static if (ovrwrtBhvr) { 138 static if (keyEqual !is null) { 139 if (binaryFun!equal((*crnt).hashCode, hashCode) && binaryFun!keyEqual((*crnt).key, key)) { 140 return (*crnt).elem = value; 141 } 142 } else { 143 if (binaryFun!equal((*crnt).hashCode, hashCode)) { 144 (*crnt).key = key; 145 return (*crnt).elem = value; 146 } 147 } 148 } else { 149 if (binaryFun!equal((*crnt).hashCode, hashCode)) { 150 if ((*crnt).prev) (*crnt).prev.next = (*crnt).next; 151 *crnt = (*crnt).next; 152 _length--; 153 } 154 } 155 crnt = &(*crnt).next; 156 } 157 //prev.next = new Node(key, value, null); 158 *crnt = new Node(hashCode, key, value, null, *crnt); 159 last = *crnt; 160 _length++; 161 return value; 162 } 163 static if (nogcIndexing) { 164 165 /** 166 * Returns true if key is found. 167 */ 168 bool has(K key) @nogc @safe pure nothrow { 169 const HashType hash = hashFunc(key); 170 Node* crnt = root; 171 while (crnt) { 172 static if (keyEqual !is null) { 173 if (binaryFun!equal(crnt.hashCode, hash) && binaryFun!keyEqual(crnt.key , key)) { 174 return true; 175 } 176 } else { 177 if (binaryFun!equal(crnt.hashCode, hash)) { 178 return true; 179 } 180 } 181 crnt = crnt.next; 182 } 183 return false; 184 } 185 } else { 186 /** 187 * Returns true if key is found. 188 */ 189 bool has(K key) @safe pure nothrow { 190 const HashType hash = hashFunc(key); 191 Node* crnt = root; 192 while (crnt) { 193 static if (keyEqual !is null) { 194 if (binaryFun!equal(crnt.hashCode, hash) && binaryFun!keyEqual(crnt.key , key)) { 195 return true; 196 } 197 } else { 198 if (binaryFun!equal(crnt.hashCode, hash)) { 199 return true; 200 } 201 } 202 crnt = crnt.next; 203 } 204 return false; 205 } 206 } 207 } else { 208 /** 209 * opApply override for foreach 210 */ 211 int opApply(scope int delegate(ref E) dg) { 212 Node* crnt = root; 213 while (crnt) { 214 if (dg(crnt.elem)) return 1; 215 crnt = crnt.next; 216 } 217 return 0; 218 } 219 /** 220 * opApply override for foreach 221 */ 222 int opApply(scope int delegate(HashType, ref E) dg) { 223 Node* crnt = root; 224 while (crnt) { 225 if (dg(crnt.hashCode, crnt.elem)) return 1; 226 crnt = crnt.next; 227 } 228 return 0; 229 } 230 /** 231 * opApplyReverse override for foreach_reverse 232 */ 233 int opApplyReverse(scope int delegate(ref E) dg) { 234 Node* crnt = last; 235 while (crnt) { 236 if (dg(crnt.elem)) return 1; 237 crnt = crnt.prev; 238 } 239 return 0; 240 } 241 /** 242 * opApplyReverse override for foreach_reverse 243 */ 244 int opApplyReverse(scope int delegate(HashType, ref E) dg) { 245 Node* crnt = last; 246 while (crnt) { 247 if (dg(crnt.hashCode, crnt.elem)) return 1; 248 crnt = crnt.prev; 249 } 250 return 0; 251 } 252 package static string makeFunc() { 253 string makeFuncIndiv(string args) { 254 return ` 255 int opApply(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 256 Node* crnt = root; 257 while (crnt) { 258 if (dg(crnt.elem)) return 1; 259 crnt = crnt.next; 260 } 261 return 0; 262 } 263 int opApply(scope int delegate(HashType, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 264 Node* crnt = root; 265 while (crnt) { 266 if (dg(crnt.hashCode, crnt.elem)) return 1; 267 crnt = crnt.next; 268 } 269 return 0; 270 } 271 int opApplyReverse(scope int delegate(ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 272 Node* crnt = last; 273 while (crnt) { 274 if (dg(crnt.elem)) return 1; 275 crnt = crnt.prev; 276 } 277 return 0; 278 } 279 int opApplyReverse(scope int delegate(HashType, ref E) ` ~ args ~ ` dg) ` ~ args ~ ` { 280 Node* crnt = last; 281 while (crnt) { 282 if (dg(crnt.hashCode, crnt.elem)) return 1; 283 crnt = crnt.prev; 284 } 285 return 0; 286 }`; 287 } 288 string result; 289 foreach (attr; attrList) { 290 result ~= makeFuncIndiv(attr); 291 } 292 return result; 293 } 294 mixin(makeFunc); 295 /** 296 * Assigns a value to the given key. 297 */ 298 auto opIndexAssign(E value, K key) @safe pure nothrow { 299 const HashType hashCode = hashFunc(key); 300 Node** crnt = &root; 301 while (*crnt) { 302 static if (ovrwrtBhvr) { 303 if (binaryFun!equal((*crnt).hashCode, hashCode)) return (*crnt).elem = value; 304 } else { 305 if (binaryFun!equal((*crnt).hashCode, hashCode)) { 306 if (&(*crnt).prev) (*crnt).prev.next = (*crnt).next; 307 *crnt = &(*crnt).next; 308 length--; 309 } 310 } 311 crnt = &(*crnt).next; 312 } 313 //prev.next = new Node(key, value, null); 314 *crnt = new Node(hashCode, value, null, last); 315 last = *crnt; 316 _length++; 317 return value; 318 } 319 static if (nogcIndexing) { 320 /** 321 * Returns true if key is found. 322 */ 323 bool has(K key) @nogc @safe pure nothrow { 324 return has(hashFunc(key)); 325 } 326 } else { 327 /** 328 * Returns true if key is found. 329 */ 330 bool has(K key) @safe pure { 331 return has(hashFunc(key)); 332 } 333 } 334 } 335 static if (!retainKeys || keyEqual !is null) { 336 static if (nogcIndexing) { 337 /** 338 * Returns the element with the given key, or E.init if key is not found. 339 */ 340 E opIndex(K key) @nogc @safe pure nothrow { 341 const HashType hashCode = hashFunc(key); 342 Node* crnt = root; 343 while (crnt) { 344 if (binaryFun!equal(crnt.hashCode, hashCode)) return crnt.elem; 345 crnt = crnt.next; 346 } 347 return E.init; 348 } 349 /** 350 * Returns the element with the given key, or E.init if key is not found. 351 */ 352 E opIndex(HashType hashCode) @nogc @safe pure nothrow { 353 Node* crnt = root; 354 while (crnt) { 355 if (binaryFun!equal(crnt.hashCode, hashCode)) return crnt.elem; 356 crnt = crnt.next; 357 } 358 return E.init; 359 } 360 /** 361 * Returns the pointer to the element with the given key, of null if key is not found. 362 */ 363 E* getPtr(K key) @nogc @safe pure nothrow { 364 const HashType hashCode = hashFunc(key); 365 Node* crnt = root; 366 while (crnt) { 367 if (binaryFun!equal(crnt.hashCode, hashCode)) return &(crnt.elem); 368 crnt = crnt.next; 369 } 370 return null; 371 } 372 /** 373 * Returns the pointer to the element with the given key, of null if key is not found. 374 */ 375 E* getPtr(HashType hashCode) @nogc @safe pure nothrow { 376 Node* crnt = root; 377 while (crnt) { 378 if (binaryFun!equal(crnt.hashCode, hashCode)) return &(crnt.elem); 379 crnt = crnt.next; 380 } 381 return null; 382 } 383 } else { 384 /** 385 * Returns the element with the given key, or E.init if key is not found. 386 */ 387 ref E opIndex(K key) @safe pure { 388 const HashType hashCode = hashFunc(key); 389 Node* crnt = root; 390 while (crnt) { 391 if (binaryFun!equal(crnt.hashCode, hashCode)) return crnt.elem; 392 crnt = crnt.next; 393 } 394 throw new ElementNotFoundException("Key not found!"); 395 } 396 /** 397 * Returns the element with the given key, or E.init if key is not found. 398 */ 399 ref E opIndex(HashType hashCode) @safe pure { 400 Node* crnt = root; 401 while (crnt) { 402 if (binaryFun!equal(crnt.hashCode, hashCode)) return crnt.elem; 403 crnt = crnt.next; 404 } 405 throw new ElementNotFoundException("Key not found!"); 406 } 407 } 408 } else { 409 static if (nogcIndexing) { 410 /** 411 * Returns the element with the given key, or E.init if key is not found. 412 */ 413 E opIndex(K key) @nogc @safe pure nothrow { 414 const HashType hashCode = hashFunc(key); 415 Node* crnt = root; 416 while (crnt) { 417 if (binaryFun!equal(crnt.hashCode, hashCode) && binaryFun!keyEqual(crnt.key, key)) return crnt.elem; 418 crnt = crnt.next; 419 } 420 return E.init; 421 } 422 /** 423 * Returns the pointer to the element with the given key, of null if key is not found. 424 */ 425 E* getPtr(K key) @nogc @safe pure nothrow { 426 const HashType hashCode = hashFunc(key); 427 Node* crnt = root; 428 while (crnt) { 429 if (binaryFun!equal(crnt.hashCode, hashCode) && binaryFun!keyEqual(crnt.key, key)) return &(crnt.elem); 430 crnt = crnt.next; 431 } 432 return null; 433 } 434 } else { 435 /** 436 * Returns the element with the given key, or E.init if key is not found. 437 */ 438 ref E opIndex(K key) @safe pure { 439 const HashType hashCode = hashFunc(key); 440 Node* crnt = root; 441 while (crnt) { 442 if (binaryFun!equal(crnt.hashCode, hashCode) && binaryFun!keyEqual(crnt.key, key)) return crnt.elem; 443 crnt = crnt.next; 444 } 445 throw new ElementNotFoundException("Key not found!"); 446 } 447 } 448 } 449 /** 450 * Returns true if key is found. 451 */ 452 bool has(HashType hashCode) @nogc @safe pure nothrow { 453 Node* crnt = root; 454 while (crnt) { 455 if (binaryFun!equal(crnt.hashCode, hashCode)) return true; 456 crnt = crnt.next; 457 } 458 return false; 459 } 460 /** 461 * Returns the number of elements in the LinkedMap. 462 */ 463 @property size_t length() @nogc @safe pure nothrow const { 464 return _length; 465 } 466 ///Returns the string representation of this container format 467 string toString() const { 468 if (root) return root.toString; 469 else return "empty"; 470 } 471 } 472 473 unittest { 474 import std.random : uniform; 475 import std.exception : assertThrown; 476 import std.stdio : writeln; 477 { 478 alias StringMap = LinkedHashMap!(string, string); 479 StringMap d; 480 d["AAAAAAAAA"] = "AAAAAAAAA"; 481 d["Hello World!"] = "Hello Vilag!"; 482 assert(d["AAAAAAAAA"] == "AAAAAAAAA"); 483 assert(d["Hello World!"] == "Hello Vilag!"); 484 } 485 { 486 alias StringMap = LinkedHashMap!(string, string, defaultHash128!(string), "a == b", true, "a == b", true); 487 StringMap d; 488 d["AAAA"] = "AAAA"; 489 d["BBBB"] = "BBBB"; 490 d["CCCC"] = "CCCC"; 491 d["DDDD"] = "DDDD"; 492 assert("AAAA" == "AAAA"); 493 assert("BBBB" == "BBBB"); 494 assert("CCCC" == "CCCC"); 495 assert("DDDD" == "DDDD"); 496 writeln(d); 497 d["CCCC"] = "eeee"; 498 writeln(d); 499 foreach (key, elem; d) {} 500 foreach_reverse (key, elem; d) {} 501 foreach (key; d) {} 502 foreach_reverse (key; d) {} 503 } 504 { 505 alias StringMap = LinkedHashMap!(string, string, defaultHash128!(string), "a == b", true, "a == b", false); 506 StringMap d; 507 d["AAAA"] = "AAAA"; 508 d["BBBB"] = "BBBB"; 509 d["CCCC"] = "CCCC"; 510 d["DDDD"] = "DDDD"; 511 assert("AAAA" == "AAAA"); 512 assert("BBBB" == "BBBB"); 513 assert("CCCC" == "CCCC"); 514 assert("DDDD" == "DDDD"); 515 writeln(d); 516 d["CCCC"] = "eeee"; 517 writeln(d); 518 foreach (key, elem; d) {} 519 foreach_reverse (key, elem; d) {} 520 foreach (key; d) {} 521 foreach_reverse (key; d) {} 522 } 523 }