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 	} else {
149 		/**
150 		 * Returns the element with the given key.
151 		 * Returns E.init if not found.
152 		 */
153 		ref E opIndex(K key) @safe pure {
154             Node* crnt = root;
155 			while (crnt) {
156 				if (binaryFun!equal(crnt.key, key)) return crnt.elem;
157 				crnt = crnt.next;
158 			}
159 			throw new ElementNotFoundException("Key not found!");
160 		}
161 	}
162 	/**
163 	 * Assigns a value to the given key.
164 	 */
165 	auto opIndexAssign(E value, K key) @safe pure nothrow {
166 		Node** crnt = &root;
167 		while (*crnt) {
168 			static if (ovrwrtBhvr) {
169 				if (binaryFun!equal((*crnt).key, key)) { 
170 					return (*crnt).elem = value;
171 				}
172 			} else {
173 				if (binaryFun!equal((*crnt).key, key)) {
174 					if ((*crnt).next) (*crnt).next.prev = (*crnt).prev;
175 					crnt = &(*crnt).next;
176 					_length--;
177 				}
178 			}
179 			//prev = crnt;
180 			crnt = &(*crnt).next;
181 		}
182 		//prev.next = new Node(key, value, null);
183 		*crnt = new Node(key, value, null, *crnt);
184 		last = *crnt;
185 		_length++;
186 		return value;
187 	}
188 	/**
189 	 * Removes a value with the given key and returns it.
190 	 */
191 	E remove(K key) @safe pure nothrow {
192 		Node** crnt = &root;
193 		while (*crnt) {
194 			if (binaryFun!equal((*crnt).key, key)) {
195 				E result = (*crnt).elem;
196 				//if ((*crnt).prev) (*crnt).prev.next = (*crnt).next;
197 				if ((*crnt).next is null) last = (*crnt).prev;
198 				else (*crnt).next.prev = (*crnt).prev;
199 				*crnt = (*crnt).next;
200 				_length--;
201 				return result;
202 			}
203 			crnt = &(*crnt).next;
204 		}
205 		return E.init;
206 	}
207 	/**
208 	 * Returns true if key is found.
209 	 */
210 	bool has(K key) @nogc @safe pure nothrow {
211 		Node* crnt = root;
212 		while (crnt) {
213 			if (binaryFun!equal(crnt.key, key)) return true;
214 			crnt = crnt.next;
215 		}
216 		return false;
217 	}
218 	/**
219 	 * Returns the number of elements in the LinkedMap.
220 	 */
221 	@property size_t length() @nogc @safe pure nothrow const {
222 		return _length;
223 	}
224 	///Returns the string representation of this container format
225 	string toString() const {
226 		if (root) return root.toString;
227 		else return "empty";
228 	}
229 }
230 
231 unittest {
232 	import std.random : uniform;
233 	import std.exception : assertThrown;
234 	import std.stdio : writeln;
235 	{
236 		alias IntMap = LinkedMap!(int, int);
237 		IntMap test0, test1;
238 		test0[0] = 0;
239 		test0[0] = 1;
240 		test0[1] = 1;
241 		test0[2] = 1;
242 		test0[3] = 1;
243 		test0[4] = 1;
244 		assert(test0.length == 5, "length mismatch!");
245 		test0.remove(3);
246 		assert(test0.length == 4, "item deletion error!");
247 		assert(test0.ptrOf(0), "pointer error!");
248 		assert(!test0.ptrOf(10), "pointer error!");
249 
250 		for(int i ; i < 256 ; i++)
251 			test1[i] = uniform(0, 65_536);
252 		assert(test1.length == 256, "length mismatch!");
253 		foreach(elem ; test1) {
254 
255 		}
256 		foreach(key, elem ; test1) {
257 
258 		}
259 		foreach_reverse(elem ; test1) {
260 
261 		}
262 		foreach_reverse(key, elem ; test1) {
263 
264 		}
265 	}
266 	{
267 		alias IntMap = LinkedMap!(int, int, false);
268 		IntMap test2;
269 		test2[0] = 1;
270 		test2[1] = 1;
271 		test2[2] = 1;
272 		test2[3] = 1;
273 		test2[4] = 1;
274 		assertThrown!ElementNotFoundException(test2[8]);
275 	}
276 	//test FIFO behavior
277 	{
278 		alias IntMap = LinkedMap!(int, int, true, "a == b", true);
279 		IntMap test3;
280 		test3[0] = 0;
281 		writeln(test3);
282 		test3[1] = 1;
283 		writeln(test3);
284 		test3[2] = 2;
285 		writeln(test3);
286 		test3[3] = 3;
287 		writeln(test3);
288 		test3[4] = 4;
289 		writeln(test3);
290 		//overwriting key 3 should not distrupt the order
291 		test3[3] = 5;
292 		writeln(test3);
293 	}
294 	{
295 		alias IntMap = LinkedMap!(int, int, true, "a == b", false);
296 		IntMap test3;
297 		test3[0] = 0;
298 		writeln(test3);
299 		test3[1] = 1;
300 		writeln(test3);
301 		test3[2] = 2;
302 		writeln(test3);
303 		test3[3] = 3;
304 		writeln(test3);
305 		test3[4] = 4;
306 		writeln(test3);
307 		//overwriting key 3 should put key 3 at the end
308 		test3[3] = 5;
309 		writeln(test3);
310 	}
311 }