1 module collections.sortedlist;
2 
3 import collections.commons;
4 import std.functional : binaryFun;
5 
6 /**
7  * Implements a sorted list of type T.
8  * The container ensures that all of it's elements are ordered after any insertion.
9  * Has some optimization to stop searching after a given value has passed.
10  * `cmp` can set both the direction of the array, and what parameters should be tested.
11  * If `allowDuplicates` set false, the collection will act like a sorted set over an array, and won't allow any 
12  * insertion of preexisting values.
13  */
14 public struct SortedList(E, alias cmp = "a < b", bool allowDuplicates = true, alias equal = "a == b") {
15 	private E[]			_array;		///The array where the elements are stored.
16 	private size_t		begin;		///The position of the current front iteration.
17 	private size_t		end;		///The position of the current back iteration.
18 	/**
19 	 * Constructs a sorted list out from an array.
20 	 */
21 	public this(E[] _array) @safe nothrow pure {
22 		this._array.reserve = _array.length;
23         foreach (E key; _array) {
24             put(key);
25         }
26         assert(this._array.length == _array.length);
27         assert(this._array.length == end);
28 	}
29 	/**
30 	 * Constructs a sorted list out from a range.
31 	 */
32 	public this(Range)(Range src) {
33 		foreach (E key; src) {
34             put(key);
35         }
36         //assert(this._array.length == _array.length);
37         assert(this._array.length == end);
38 	}
39     /**
40 	 * Adds a new element while keeping the order intact.
41 	 *
42 	 * TO DO: Maybe even more optimizations? Maybe look where the element would fit, then shift that position?
43 	 */
44 	E put(E a) @safe nothrow pure {
45 		static if(!allowDuplicates){
46 			if(has(a)) return E.init;
47 		}
48 		_array.length = _array.length + 1;
49 		for(sizediff_t i = _array.length - 2 ; i >= 0 ; i--) {
50 			E b = _array[i];
51 			if(binaryFun!cmp(a, b)) { //first position found
52 				_array[i + 1] = a;
53 				end++;
54 				return a;
55 			} else {
56 				_array[i + 1] = b;
57 			}
58 		}
59 		_array[0] = a;
60         end++;
61 		return a;
62 	}
63 	/**
64 	 * Removes the n-th element while keeping the order intact.
65 	 * Returns the removed element.
66 	 */
67 	E remove(size_t n) @safe nothrow pure {
68 		E result = _array[n];
69 		if(n != _array.length) {
70 			for ( ; n < _array.length - 1 ; n++) {
71 				_array[n] = _array[n + 1];
72 			}
73 		}
74 		_array.length = _array.length - 1;
75 		end--;
76 		return result;
77     }
78 	static if(!allowDuplicates) {
79 		/**
80 		 * Removes the element which is equal with the given one if the template is set to not allow duplicates.
81 		 * Returns the removed element, or E.init if not found.
82 		 */
83 		E removeByElem(E a) @safe nothrow pure {
84 			foreach_reverse(i, b; _array) {
85 				if(binaryFun!equal(a, b)) return this.remove(i);
86 				else if(binaryFun!cmp(a, b)) break;
87 			}
88 			return E.init;
89 		}
90 		/** 
91 		 * Removes the element which is equal with the given one if the template is set to not allow duplicates.
92 		 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal
93 		 * functions's overrides.
94 		 * Returns the removed element, or E.init if not found.
95 		 */
96 		E removeBy(T)(T a) @safe nothrow pure {
97 			foreach_reverse(i, b; _array) {
98 				if(binaryFun!equal(a, b)) return this.remove(i);
99 				else if(binaryFun!cmp(a, b)) break;
100 			}
101 			return E.init;
102 		}
103 		/** 
104 		 * Looks up value `a` in the list, then returns the element equal with it. Returns E.init if not found.
105 		 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal
106 		 * functions's overrides.
107 		 */
108 		E searchBy(T)(T a) @nogc @safe pure nothrow {
109 			foreach_reverse(b; _array) {
110 				if(binaryFun!equal(a, b)) return b;
111 				else if(binaryFun!cmp(a, b)) break;
112 			}
113 			return E.init;
114 		}
115 		/** 
116 		 * Looks up value `a` in the list, then returns a reference to the element equal with it. Throws an exception 
117 		 * if not found.
118 		 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal
119 		 * functions's overrides.
120 		 */
121 		E searchByRef(T)(T a) @safe pure {
122 			foreach_reverse(ref E b; _array) {
123 				if(binaryFun!equal(a, b)) return b;
124 				else if(binaryFun!cmp(a, b)) break;
125 			}
126 			throw new ElementNotFoundException("Element not found!");
127 		}
128 		/** 
129 		 * Looks up value `a` in the list, then returns the element equal with it. Returns null if not found.
130 		 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal
131 		 * functions's overrides.
132 		 */
133 		E* searchByPtr(T)(T a) @nogc pure nothrow {
134 			foreach_reverse(ref E b; _array) {
135 				if(binaryFun!equal(a, b)) return &b;
136 				else if(binaryFun!cmp(a, b)) break;
137 			}
138 			return null;
139 		}
140 		/**
141 		 * Returns whether the set has the given element.
142 		 */
143 		bool has(const E a) @nogc @safe nothrow pure const {
144 			foreach_reverse(b; _array) {
145 				if(binaryFun!equal(a, b)) return true;
146 				else if(binaryFun!cmp(a, b)) break;
147 			}
148 			return false;
149 		}
150 		/**
151 		 * Returns whether the set has the given element.
152 		 * Intended for use with structs and classes that can interface with the type of T through the cmp and equal
153 		 * functions's overrides.
154 		 */
155 		bool has(T)(const T a) @nogc @safe nothrow pure const {
156 			foreach_reverse(b; _array) {
157 				if(binaryFun!equal(a, b)) return true;
158 				else if(binaryFun!cmp(a, b)) break;
159 			}
160 			return false;
161 		}
162 		auto opBinaryRight(string op, L)(const L lhs) const {
163 			static if (op == "in") {
164 				return has(lhs);
165 			} else static assert(0, "Operator not supported!");
166 		}
167 		/**
168 		 * Returns the amount of elements found in the set.
169 		 */
170 		size_t hasRange(R)(R range) @nogc @safe pure nothrow {
171 			size_t result;
172 			foreach (key; range) {
173 				if(has(key)) result++;
174 			}
175 			return result;
176 		}
177 		/**
178 		 * Returns the index of the given element, or throws an ElementNotFoundException if not found.
179 		 */
180 		size_t which(E a) @safe pure {
181 			foreach_reverse(i, b; _array) {
182 				if(binaryFun!equal(a, b)) return i;
183 				else if(binaryFun!cmp(a, b)) break;
184 			}
185 			throw new ElementNotFoundException("Element not found!");
186 		}
187 		/**
188 	 	 * Returns a slice from the list, but the slicing is done by element.
189 		 * Search is done in a way that if either cmp or equals is true to an element, its position will be chosen
190 		 * for the slice.
191 	 	 */
192 		SortedList!(E, cmp, allowDuplicates, equal) sliceByElem(E from, E to) @safe pure {
193 			size_t f, t = _array.length;
194 			E a = from;
195 			foreach_reverse(size_t i ,E b; _array) {
196 				if(binaryFun!cmp(a, b) || binaryFun!equal(a, b)){ 
197 					f = i;
198 					break;
199 				}
200 			}
201 			a = to;
202 			foreach_reverse(size_t i ,E b; _array) {
203 				if(binaryFun!cmp(a, b) || binaryFun!equal(a, b)){ 
204 					t = i;
205 					break;
206 				}
207 			}
208 			return opSlice(f, t);
209 		}
210 		/**
211 		 * Set operators.
212 		 * Enables math operations on sets, like unions and intersections.
213 		 * Could work on ranges in general as long as they implement some basic functions, like iteration.
214 		 */
215 		SortedList!(E, cmp, allowDuplicates, equal) opBinary(string op, R)(R rhs) {
216 			static if(op == "|" || op == "~") {//Union
217 				SortedList!(E, cmp, allowDuplicates, equal) result;
218 				result.end = this.end;
219 				result._array = this._array.dup;
220 				foreach(e ; rhs){
221 					result.put(e);
222 				}
223 				return result;
224 			} else static if(op == "&" || op == "*") {//Intersection
225 				SortedList!(E, cmp, allowDuplicates, equal) result;
226 				foreach(e ; rhs){
227 					if(this.has(e)) result.put(e);
228 				}
229 				return result;
230 			} else static if(op == "-" || op == "/") {//Complement
231 				SortedList!(E, cmp, allowDuplicates, equal) result = SortedList!(E, cmp, allowDuplicates, equal)(this);
232 				foreach(e ; rhs){
233 					result.removeByElem(e);
234 				}
235 				return result;
236 			} else static if(op == "^"){//Difference
237 				SortedList!(E, cmp, allowDuplicates, equal) result = this | rhs;
238 				SortedList!(E, cmp, allowDuplicates, equal) common = this & rhs;
239 				foreach(e ; common){
240 					result.removeByElem(e);
241 				}
242 				return result;
243 			} else static assert(0, "Operator " ~ op ~ "not supported");
244 		}
245 		/**
246 		 * Set operators.
247 		 */
248 		SortedList!(E, cmp, allowDuplicates, equal) opOpAssign(string op)(E value) {
249 			static if(op == "~=") {//Append
250 				put(value);
251 			} else static if(op == "-=" || op == "/=") {
252 				removeByElem(value);
253 			} else static assert(0, "Operator " ~ op ~ "not supported");
254 			return this;
255 		}
256 		/**
257 		 * Set operators.
258 		 */
259 		SortedList!(E, cmp, allowDuplicates, equal) opOpAssign(string op, R)(R range) {
260 			static if(op == "~=" || op == "|=") {//Append
261 				foreach(val; range)
262 					put(val);
263 			} else static if(op == "-=" || op == "/=") {
264 				foreach(val; range)
265 					removeByElem(val);
266 			} else static assert(0, "Operator " ~ op ~ "not supported");
267 			return this;
268 		}
269 	}
270 	/**
271 	 * Returns a copy of this struct.
272 	 */
273 	@property auto save() @nogc @safe nothrow pure {
274 		return this;
275 	}
276 	/**
277 	 * Returns the element at the front.
278 	 */
279 	@property E front() @nogc @safe nothrow pure {
280 		return _array[begin];
281 	}
282 	/**
283 	 * Returns the element at the front.
284 	 * Note: This is recommended for elements ordered by a key, which is not modified through this function. Failure of
285 	 * doing so will ruin the sortedness of the array.
286 	 */
287 	@property ref E frontRef() @nogc @safe nothrow pure {
288 		return _array[begin];
289 	}
290 	/**
291 	 * Returns the element at the back.
292 	 */
293 	@property E back() @nogc @safe nothrow pure {
294 		return _array[end - 1];
295 	}
296 	/**
297 	 * Returns the element at the back.
298 	 * Note: This is recommended for elements ordered by a key, which is not modified through this function. Failure of
299 	 * doing so will ruin the sortedness of the array.
300 	 */
301 	@property ref E backRef() @nogc @safe nothrow pure {
302 		return _array[end - 1];
303 	}
304 	/**
305 	 * Returns the element at begin and increments the position by one.
306 	 */
307 	E moveFront() @nogc @safe nothrow pure {
308 		E result = _array[begin];
309 		popFront();
310 		return result;
311 	}
312 	/**
313 	 * Increments the front iteration position by one
314 	 */
315 	void popFront() @nogc @safe nothrow pure {
316 		if(begin < end) begin++;
317 	}
318 	/**
319 	 * Decrements the back iteration position by one
320 	 */
321 	void popBack() @nogc @safe nothrow pure {
322 		if(begin < end) end--;
323 	}
324 	/**
325 	 * Returns true when the end of the list have been reached.
326 	 */
327 	@property bool empty() @nogc @safe nothrow pure {
328 		return begin == end;
329 	}
330 	/**
331 	 * Returns the n-th element.
332 	 */
333 	E opIndex(size_t n) @nogc @safe nothrow pure {
334 		return _array[n];
335 	}
336 	/**
337 	 * Moves to the n-th position and returns the element of that position.
338 	 */
339 	E moveAt(size_t n) @nogc @safe nothrow pure {
340 		begin = n;
341 		return _array[begin];
342 	}
343 	/**
344 	 * Returns the length of the list.
345 	 */
346 	@property size_t length() @nogc @safe nothrow pure {
347 		return _array.length;
348 	}
349 	alias opDollar = length;
350 	/**
351 	 * Sets the reserve of the underlying array and returns the current reserve.
352 	 */
353 	@property size_t reserve(size_t amount) @safe pure nothrow {
354 		return _array.reserve(amount);
355 	}
356 	/**
357 	 * Returns a slice from the list.
358 	 */
359 	SortedList!(E, cmp, allowDuplicates, equal) opSlice(size_t i0, size_t i1) @safe nothrow pure {
360 		return SortedList!(E, cmp, allowDuplicates, equal)(_array[i0..i1]);
361 	}
362 	/**
363 	 * Returns a copy of the underlying array.
364 	 */
365 	@property const(E)[] arrayOf() @safe nothrow pure const {
366 		const(E)[] result;
367 		result.reserve = _array.length;
368 		foreach (const E key; _array) {
369 			result ~= key;
370 		}
371 		return result;
372 	}
373 	
374 	
375 	string toString() {
376 		import std.conv : to;
377 		return to!string(_array);
378 	}
379 }
380 
381 @safe unittest {
382 	import std.stdio : writeln;
383 	alias SortedIntList = SortedList!(int, "a < b", true);
384 	alias SortedIntSet = SortedList!(int, "a < b", false);
385 	SortedIntList sil;
386 	sil.put(5);
387 	assert(sil.arrayOf == [5], sil.toString);
388 	sil.put(3);
389 	assert(sil.arrayOf == [5, 3], sil.toString);
390 	sil.put(7);
391 	assert(sil.arrayOf == [7, 5, 3], sil.toString);
392 	sil.put(-1);
393 	assert(sil.arrayOf == [7, 5, 3, -1], sil.toString);
394 	sil.remove(2);
395 	assert(sil.arrayOf == [7, 5, -1], sil.toString);
396 	sil.put(2);
397 	assert(sil.arrayOf == [7 ,5, 2, -1], sil.toString);
398 	SortedIntSet sis;
399 	sis.put(5);
400 	assert(sis.arrayOf == [5], sis.toString);
401 	sis.put(5);
402 	assert(sis.arrayOf == [5], sis.toString);
403 	sis.put(3);
404 	assert(sis.arrayOf == [5, 3], sis.toString);
405 	sis.put(3);
406 	assert(sis.arrayOf == [5, 3], sis.toString);
407 	sis.put(7);
408 	assert(sis.arrayOf == [7, 5, 3], sis.toString);
409 	sis.put(7);
410 	assert(sis.arrayOf == [7, 5, 3], sis.toString);
411 	sis.put(-2);
412 	assert(sis.arrayOf == [7, 5, 3, -2], sis.toString);
413 	sis.put(11);
414 	assert(sis.arrayOf == [11, 7, 5, 3, -2], sis.toString);
415 	assert(!sis.has(12), sis.toString);
416 	assert(sis.has(11), sis.toString);
417 	sis.remove(0);
418 	assert(!sis.has(11), sis.toString);
419 	assert(sis.arrayOf == [7, 5, 3, -2], sis.toString);
420 	sis.put(1);
421 	assert(sis.arrayOf == [7, 5, 3, 1, -2], sis.toString);
422 	sis.put(1);
423 	assert(sis.arrayOf == [7, 5, 3, 1, -2], sis.toString);
424 	foreach(e; sil) {
425 		writeln(e);
426 	}
427 	foreach(e; sis) {
428 		writeln(e);
429 	}
430 	SortedIntList a = SortedIntList([0]);
431 	a.remove(0);
432 	assert(a.length == 0);
433 }
434 
435 @safe unittest {
436 	import std.stdio : writeln;
437 	alias SortedIntList = SortedList!(int, "a > b", true);
438 	alias SortedIntSet = SortedList!(int, "a > b", false);
439 	SortedIntList sil;
440 	sil.put(5);
441 	assert(sil.arrayOf == [5], sil.toString);
442 	sil.put(3);
443 	assert(sil.arrayOf == [3, 5], sil.toString);
444 	sil.put(7);
445 	assert(sil.arrayOf == [3, 5, 7], sil.toString);
446 	sil.put(-1);
447 	assert(sil.arrayOf == [-1, 3, 5, 7], sil.toString);
448 	sil.remove(2);
449 	assert(sil.arrayOf == [-1, 3, 7], sil.toString);
450 	sil.put(2);
451 	assert(sil.arrayOf == [-1,2, 3, 7], sil.toString);
452 	SortedIntSet sis;
453 	sis.put(5);
454 	assert(sis.arrayOf == [5], sis.toString);
455 	sis.put(5);
456 	assert(sis.arrayOf == [5], sis.toString);
457 	sis.put(3);
458 	assert(sis.arrayOf == [3, 5], sis.toString);
459 	sis.put(3);
460 	assert(sis.arrayOf == [3, 5], sis.toString);
461 	sis.put(7);
462 	assert(sis.arrayOf == [3, 5, 7], sis.toString);
463 	sis.put(7);
464 	assert(sis.arrayOf == [3, 5, 7], sis.toString);
465 	sis.put(-2);
466 	assert(sis.arrayOf == [-2, 3, 5, 7], sis.toString);
467 	sis.put(11);
468 	assert(sis.arrayOf == [-2, 3, 5, 7, 11], sis.toString);
469 	assert(!sis.has(12), sis.toString);
470 	assert(sis.has(11), sis.toString);
471 	sis.remove(0);
472 	assert(!sis.has(-2), sis.toString);
473 	assert(sis.arrayOf == [3, 5, 7, 11], sis.toString);
474 	sis.put(1);
475 	assert(sis.arrayOf == [1, 3, 5, 7, 11], sis.toString);
476 	sis.put(1);
477 	assert(sis.arrayOf == [1, 3, 5, 7, 11], sis.toString);
478 	foreach(e; sil) {
479 		writeln(e);
480 	}
481 	foreach(e; sis) {
482 		writeln(e);
483 	}
484 }
485 
486 unittest {
487 	//test set operators
488 	alias IntSet = SortedList!(int, "a > b", false, "a == b");
489 	IntSet a = IntSet([1, 3, 5, 7, 9]), b = IntSet([1, 5, 9]), c = IntSet([3, 7]);
490 	IntSet union_ab = a | b, union_ac = a | c, union_bc = b | c;
491 	IntSet intrsctn_ab = a & b, intrsctn_ac = a & c;
492 	IntSet cmplmnt_ab = a - b, cmplmnt_ac = a - c;
493 	IntSet diff_ab = a ^ b, diff_ac = a ^ c, diff_bc = b ^ c;
494 	assert(union_ab.hasRange([1, 3, 5, 7, 9]) == 5);
495 	assert(union_ac.hasRange([1, 3, 5, 7, 9]) == 5);
496 	assert(union_bc.hasRange([1, 3, 5, 7, 9]) == 5);
497 	assert(intrsctn_ab.hasRange([1, 5, 9]) == 3);
498 	assert(intrsctn_ac.hasRange([3, 7]) == 2);
499 	assert(cmplmnt_ab.hasRange([3, 7]) == 2);
500 	assert(cmplmnt_ac.hasRange([1, 5, 9]) == 3);
501 	assert(diff_ab.hasRange([3, 7]) == 2);
502 	assert(diff_ac.hasRange([1, 5, 9]) == 3);
503 	assert(diff_bc.hasRange([1, 3, 5, 7, 9]) == 5);
504 	assert(5 in diff_bc);
505 }
506 
507 //test key functions
508 unittest {
509 	import std.exception;
510 	import std.conv : to;
511 	alias TestSet = SortedList!(TestStructWithKey, "a > b", false, "a == b");
512 	TestSet a;
513 	a.put(TestStructWithKey(0, null, null));
514 	a.put(TestStructWithKey(1, null, null));
515 	a.put(TestStructWithKey(4, null, null));
516 	assert(a.has(0), a.arrayOf.to!string);
517 	assert(a.has(1), a.arrayOf.to!string);
518 	assert(!a.has(2), a.arrayOf.to!string);
519 	assert(!a.has(3), a.arrayOf.to!string);
520 	assert(a.has(4), a.arrayOf.to!string);
521 	assert(a.searchBy(4).key == 4, a.arrayOf.to!string);
522 	assert(a.searchByPtr(3) == null, a.arrayOf.to!string);
523 	assertThrown(a.searchByRef(5));
524 	assert(a.removeBy(4).key == 4, a.arrayOf.to!string);
525 	assert(!a.has(4), a.arrayOf.to!string);
526 }