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 }