mutils.container.sorted_vector source code

1 module mutils.container.sorted_vector;
2 
3 import std.algorithm : sort;
4 import std.experimental.allocator;
5 import std.experimental.allocator.mallocator;
6 import std.functional : binaryFun;
7 
8 import mutils.container.vector;
9 
10 /***
11  * Vector which keeps data sorted
12  */
13 struct SortedVector(T, alias less = "a < b") {
14 	alias cmpFunction = binaryFun!less;
15 	Vector!T vec;
16 
17 	bool empty() {
18 		return (vec.used == 0);
19 	}
20 
21 	size_t length() {
22 		return vec.used;
23 	}
24 
25 	void reset() {
26 		vec.used = 0;
27 	}
28 
29 	void clear() {
30 		vec.clear();
31 	}
32 
33 	size_t add(T t) {
34 		foreach (i, el; vec[]) {
35 			if (cmpFunction(t, el)) {
36 				vec.add(t, i);
37 				return i;
38 			}
39 		}
40 		size_t addPos = vec.length;
41 		vec.add(t, addPos);
42 		return addPos;
43 	}
44 
45 	void add(T[] t) {
46 		T[8] tmpMemory;
47 		Vector!T tmp;
48 		T[] slice;
49 
50 		if (t.length <= 8) {
51 			tmpMemory[0 .. t.length] = t;
52 			slice = tmpMemory[0 .. t.length];
53 		} else {
54 			tmp.add(t);
55 			slice = tmp[];
56 		}
57 		sort!(cmpFunction)(slice);
58 		vec.reserve(vec.length + t.length);
59 		size_t lastInsertIndex = vec.length;
60 		foreach_reverse (elNum, elToAdd; slice) {
61 			size_t posToInsert = lastInsertIndex;
62 			foreach_reverse (i, el; vec.array[0 .. lastInsertIndex]) {
63 				if (cmpFunction(elToAdd, el)) {
64 					posToInsert = i;
65 				}
66 			}
67 			foreach_reverse (i; posToInsert .. lastInsertIndex) {
68 				vec.array[elNum + i + 1] = vec.array[i];
69 			}
70 			vec.array[posToInsert + elNum] = elToAdd;
71 			lastInsertIndex = posToInsert;
72 		}
73 
74 		vec.used += t.length;
75 		tmp.removeAll();
76 	}
77 
78 	void remove(size_t elemNum) {
79 		vec.removeStable(elemNum);
80 	}
81 
82 	void opOpAssign(string op)(T obj) {
83 		static assert(op == "~");
84 		add(obj);
85 	}
86 
87 	void opOpAssign(string op)(T[] obj) {
88 		static assert(op == "~");
89 		add(obj);
90 	}
91 
92 	ref T opIndex(size_t elemNum) {
93 		return vec.array[elemNum];
94 	}
95 
96 	auto opSlice() {
97 		return vec.array[0 .. vec.used];
98 	}
99 
100 	T[] opSlice(size_t x, size_t y) {
101 		return vec.array[x .. y];
102 	}
103 
104 	size_t opDollar() {
105 		return vec.used;
106 	}
107 }
108 
109 // Helper to avoid GC
110 private T[n] s(T, size_t n)(auto ref T[n] array) pure nothrow @nogc @safe {
111 	return array;
112 }
113 
114 unittest {
115 	SortedVector!int vector;
116 	assert(vector.add(5) == 0);
117 	assert(vector.add(3) == 0);
118 	assert(vector.add(6) == 2);
119 	assert(vector[] == [3, 5, 6].s);
120 
121 	vector.add([2, 4, 7].s);
122 	assert(vector[] == [2, 3, 4, 5, 6, 7].s);
123 	vector.add(vector[]);
124 	vector.add(vector[]);
125 	assert(vector[] == [2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7].s);
126 }