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 {
15 	alias cmpFunction=binaryFun!less;
16 	Vector!T vec;
17 
18 	bool empty(){
19 		return (vec.used==0);
20 	}
21 	
22 	size_t length(){
23 		return vec.used;
24 	}	
25 	
26 	void reset(){
27 		vec.used=0;
28 	}
29 
30 	size_t add(T t){
31 		foreach(i, el;vec[]){
32 			if(cmpFunction(t,el)){
33 				vec.add(t, i);
34 				return i;
35 			}
36 		}
37 		size_t addPos=vec.length;
38 		vec.add(t, addPos);
39 		return addPos;
40 	}
41 
42 	void add( T[]  t ) {
43 		T[8] tmpMemory;
44 		Vector!T tmp;
45 		T[] slice;
46 
47 		if(t.length<=8){
48 			tmpMemory[0..t.length]=t;
49 			slice=tmpMemory[0..t.length];
50 		}else{
51 			tmp.add(t);
52 			slice=tmp[];
53 		}
54 		sort!(cmpFunction)(slice);
55 		vec.reserve(vec.length+t.length);
56 		size_t lastInsertIndex=vec.length;
57 		foreach_reverse(elNum, elToAdd;slice){
58 			size_t posToInsert=lastInsertIndex;
59 			foreach_reverse(i, el;vec.array[0..lastInsertIndex]){
60 				if(cmpFunction(elToAdd, el)){
61 					posToInsert=i;
62 				}
63 			}
64 			foreach_reverse(i; posToInsert..lastInsertIndex){
65 				vec.array[elNum+i+1]=vec.array[i];
66 			}
67 			vec.array[posToInsert+elNum]=elToAdd;
68 			lastInsertIndex=posToInsert;
69 		}
70 
71 		vec.used+=t.length;
72 		tmp.removeAll();
73 	}
74 
75 	void remove(size_t elemNum){
76 		vec.remove(elemNum);
77 	}
78 
79 	void opOpAssign(string op)(T obj){
80 		static assert(op=="~");
81 		add(obj);
82 	}
83 	
84 	void opOpAssign(string op)(T[] obj){
85 		static assert(op=="~");
86 		add(obj);
87 	}
88 
89 	ref T opIndex(size_t elemNum){
90 		return vec.array[elemNum];
91 	}
92 	
93 	auto opSlice(){
94 		return vec.array[0..vec.used];
95 	}
96 	
97 	T[] opSlice(size_t x, size_t y){
98 		return vec.array[x..y];
99 	}
100 	
101 	size_t opDollar(){
102 		return vec.used;
103 	}
104 }
105 
106 unittest{
107 	SortedVector!int vector;
108 	assert(vector.add(5)==0);
109 	assert(vector.add(3)==0);
110 	assert(vector.add(6)==2);
111 	assert(vector[]==[3,5,6]);
112 
113 	vector.add([2,4,7]);
114 	assert(vector[]==[2,3,4,5,6,7]);
115 	vector.add(vector[]);
116 	vector.add(vector[]);
117 	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]);
118 }