yu.container.vector source code

1 module yu.container.vector;
2 
3 import core.memory;
4 import std.exception;
5 import std.experimental.allocator;
6 import std.experimental.allocator.mallocator;
7 import std.experimental.allocator.gc_allocator;
8 import yu.traits;
9 import core.stdc.string : memcpy, memset;
10 import yu.container.common;
11 import yu.array;
12 
13 /**
14 * copy  有三种类型：
15     1. COW： 对于值类型， 非指针， 对于结构体并且没有自定义 赋值函数
16     2. 深Copy： 对于有自定义 赋值函数的结构体
17     2. 不允许copy： 对于引用类型 和 指针
18 */
19 
20 @trusted struct Vector(T, Allocator = Mallocator, bool addInGC = true) if(is(T == Unqual!T))
21 {
22     enum addToGC = addInGC && hasIndirections!T && !is(Unqual!Allocator == GCAllocator);
23     enum needDestroy = (is(T == struct) && hasElaborateDestructor!T);
24     enum isNotCopy = isPointer!T || isRefType!T;
25     alias Data =  ArrayCOWData!(T, Allocator,addToGC);
26     static if (hasIndirections!T)
27         alias InsertT = T;
28     else
29         alias InsertT = const T;
30 
31     static if (StaticAlloc!Allocator)
32     {
33         this(size_t size)
34         {
35             reserve(size);
36         }
37 
38         this(S)(S[] data) if(is(S : InsertT))
39         {
40             assign(data);
41         }
42     }
43     else
44     {
45         @disable this();
46         this(size_t size,Allocator alloc)
47         {
48             _alloc = alloc;
49             reserve(size);
50         }
51 
52         this(S)(S[] data,Allocator alloc)  if(is(S : InsertT))
53         {
54             _alloc = alloc;
55             assign(data);
56         }
57 
58         this(Allocator alloc)
59         {
60             _alloc = alloc;
61         }
62     }
63     mixin AllocDefine!Allocator;
64     static if(isNotCopy){
65         alias DestroyFun = void function(ref Alloc alloc,ref T) nothrow;
66         private DestroyFun _fun;
67         @property void destroyFun(DestroyFun fun){_fun = fun;}
68         @property DestroyFun destroyFun(){return _fun;}
69 
70         private void doDestroy(ref T d){
71             if(_fun)
72                 _fun(_alloc, d);
73         }
74         private void doDestroy(T[] d){
75             if(_fun) {
76                 for(size_t i  = 0; i < d.length; ++i)
77                     _fun(_alloc, d[i]);
78             }
79         }
80     } else {
81         this(this)
82         {
83             Data.inf(_data);
84             static if(hasElaborateAssign!T)
85                 doCOW(0);
86         }
87     }
88 
89     ~this()
90     {
91         Data.deInf(_alloc, _data);
92     }
93 
94     void append(S)(auto ref S value) if(is(S : InsertT) || is(S : InsertT[]))
95     {
96         this.opOpAssign!("~",S)(value);
97     }
98 
99     alias insertBack = append;
100     alias put = append;
101     alias pushBack = append;
102 
103    size_t removeBack(size_t howMany = 1) {
104         if(howMany == 0 ) 
105             return 0;
106         if (howMany >= _array.length) {
107             size_t len = _array.length;
108             clear();
109             return len;
110         }
111         auto size = _array.length - howMany;
112         doInitVaule(_array[size .. $]);
113         _array = _array[0 .. size];
114         return howMany;
115     }
116 
117     void removeSite(size_t site) 
118     in {
119         assert(site < _array.length);
120     } body{
121         doCOW(0);
122         const size_t len = _array.length - 1;
123         doInitVaule(_array[site]);
124         for (size_t i = site; i < len; ++i) {
125             memcpy(&(_array[i]), &(_array[i + 1]), T.sizeof);
126         }
127         T v = T.init;
128         memcpy(&(_array[len]), &v, T.sizeof);
129         _array = _array[0..len];
130     }
131 
132     bool removeOne(S)(auto ref S value) if(is(Unqual!S == T)) {
133         doCOW(0);
134         for (size_t i = 0; i < _array.length; ++i) {
135             if (_array[i] == value) {
136                 removeSite(i);
137                 return true;
138             }
139         }
140         return false;
141     }
142 
143     size_t removeAny(S)(auto ref S value) if(is(Unqual!S == T)) {
144         doCOW(0);
145         size_t rm = 0;
146         size_t site = 0;
147         for (size_t j = site; j < _array.length; ++j) {
148             if (_array[j] != value) {
149                 if(site != j) 
150                     memcpy(&_array[site], &_array[j], T.sizeof);
151                 site++;
152             } else {
153                 doInitVaule(_array[j]);
154                 rm++;
155             }
156         }
157         if(rm > 0) {
158             auto size = _array.length - rm;
159             auto rmed = _array[size .. $];
160             _array = _array[0..size];
161             fillWithMemcpy(rmed, T.init);
162         }
163         return rm;
164     }
165 
166     alias removeIndex = removeSite;
167 
168     void clear(){
169         if(_data !is null && _data.count > 1){
170             Data.deInf(_alloc,_data);
171             _data = null;
172         } else {
173             doInitVaule(_array);
174         }
175         _array = null;
176     }
177 
178     void opIndexAssign(S)(auto ref S value,size_t index) if(is(Unqual!S == T))
179     in{
180         assert(index < _array.length);
181     }body{
182         doCOW(0);
183         _array[index] = value;
184     }
185 
186     auto opIndex(size_t index) const
187     in{
188         assert(index < _array.length);
189     } body{
190         return _array[index];
191     }
192 
193     auto opIndex(size_t index)
194     in{
195         assert(index < _array.length);
196     } body{
197         return _array[index];
198     }
199 
200     bool opEquals(S)(S other) const 
201 		if(is(S == Unqual!(typeof(this))) || is(S : InsertT[]))
202 	{
203 		if(_array.length == other.length){
204             for(size_t i = 0; i < _array.length; ++ i) {
205                 if(_array[i] != other[i]) 
206                     return false;
207             }
208             return true;
209         } else
210             return false;
211     }
212 
213     size_t opDollar(){return _array.length;}
214 
215     void opAssign(S)(auto ref S n) if((is(S == Unqual!(typeof(this))) && !(isNotCopy)) || is(S : InsertT[]))
216     {
217         static if(is(S : InsertT[])){
218             assign(n);
219         } else {
220             if(n._data !is _data){
221                 Data.deInf(_alloc,_data);
222                 _data = n._data;
223                 Data.inf(_data);
224             }
225             _array = n._array;
226             static if(hasElaborateAssign!T)
227                 doCOW(0);
228         }
229     }
230 
231     @property bool empty() const nothrow {
232             return _array.length == 0;
233     }
234 
235     @property size_t length()const nothrow {return _array.length;}
236 
237     int opApply(scope int delegate(ref T) dg)
238     {
239         int result = 0;
240 
241         for (size_t i = 0; i < _array.length; i++)
242         {
243             result = dg(_array[i]);
244             if (result)
245                 break;
246         }
247         return result;
248     }
249 
250     int opApply(scope int delegate(size_t, ref T) dg)
251     {
252         int result = 0;
253 
254         for (size_t i = 0; i < _array.length; i++)
255         {
256             result = dg(i, _array[i]);
257             if (result) break;
258         }
259         return result;
260     }
261     static if(!isNotCopy) {
262         @property typeof(this) dup() {
263             typeof(this) ret = this;
264             if(this._data !is null)
265                 ret.doCOW(0);
266             return ret;
267         }
268         T[] idup(){
269             return _array.dup;
270         }
271     }
272 
273     immutable (T)[] opCast(C)() nothrow
274         if(is(C == immutable (T)[]))
275     {
276         return data();
277     }
278 
279     immutable (T)[] data() nothrow
280     {
281         return cast(immutable (T)[])_array;
282     }
283 
284     @property const(T) * ptr() const  nothrow{
285         return _array.ptr;
286     }
287 
288     typeof(this) opBinary(string op,S)(auto ref S other) 
289 		if((is(S == Unqual!(typeof(this))) || is(S : InsertT[])) && op == "~")
290 	{
291 		typeof(this) ret = this;
292         ret ~= other;
293         return ret;
294     }
295 
296     void opOpAssign(string op,S)(auto ref S other) 
297         if((is(S == Unqual!(typeof(this))) || is(S : InsertT[]) || is(S : InsertT)) && op == "~") 
298     {
299         static if(is(Unqual!S == T)){
300             const size_t tmpLength = 1;
301         } else {
302             if(other.length == 0) return;
303             const size_t tmpLength = other.length;
304         }
305         doCOW(tmpLength);
306         T * tptr = _data.data.ptr + _array.length;
307         static if(is(Unqual!S == T)){
308             tptr[0] = other;
309         } else {
310             memcpy(tptr, other.ptr, (tmpLength * T.sizeof));
311         }
312         tptr = _data.data.ptr;
313         size_t len = _array.length + tmpLength;
314         _array = tptr[0..len];
315     }
316     
317      void reserve(size_t elements) {
318          if(elements < _array.length)
319             removeBack(_array.length - elements);
320         else if(elements > _array.length)
321             doCOW(elements - _array.length);
322      }
323 
324 private:
325     void assign(S)(S[] input) if(is(S : InsertT))
326     {
327         clear();
328         if(input.length == 0) return;
329         auto data = buildData();
330         Data.deInf(_alloc,data);
331         _data.reserve(input.length);
332         assign(_data.data.ptr,input);
333         _array = _data.data[0..input.length];
334     }
335 
336     pragma(inline)
337     void assign(S)(T * array,S[] data)if(is(S : InsertT))
338     {
339         static if(hasElaborateAssign!T){
340             for(size_t i  = 0; i < data.length; ++i)
341                 array[i] = data[i];
342         } else {
343             memcpy(array, data.ptr, (data.length * T.sizeof));
344         }
345     }
346 
347     void doCOW(size_t tmpLength = 0)
348     {
349         auto data = buildData();
350         if(data !is null) {
351             _data.reserve(extenSize(tmpLength));
352             if(_array.length > 0){
353                 assign(_data.data.ptr, _array);
354                 _array = _data.data[0.. _array.length];
355             }
356             Data.deInf(_alloc,data);
357         } else if(tmpLength > 0 && _data.reserve(extenSize(tmpLength))) {
358                 _array = _data.data[0.. _array.length];
359         }
360     }
361 
362     Data * buildData(){
363         Data* data  = null;
364         if(_data !is null && _data.count > 1){
365             data = _data;
366             _data = null;
367         }
368         if(_data is null) {
369             _data = Data.allocate(_alloc);
370             static if(!StaticAlloc!Allocator)
371                 _data._alloc = _alloc;
372         }
373         return data;
374     }
375 
376     size_t extenSize(size_t size) {
377         size += _array.length;
378         if (size > 0)
379             size = size > 128 ? size + ((size / 3) * 2) : size * 2;
380         else
381             size = 32;
382         return size;
383     }
384 
385     void doInitVaule(ref T v)
386     {
387         static if(isNotCopy){
388             doDestroy(v);
389         } else static if(needDestroy) {
390             destroy(v);
391         }
392         T tv = T.init;
393         memcpy(&v,&tv,T.sizeof);
394     }
395 
396     void doInitVaule(T[] v){
397         for(size_t i  = 0; i < v.length; ++i)
398             doInitVaule(v[i]);
399     }
400     
401 
402 private:
403     Data* _data;
404     T[] _array;
405 }
406 
407 unittest {
408     import std.stdio;
409     import std.experimental.allocator.mallocator;
410     import std.experimental.allocator;
411 
412     Vector!(int) vec; // = Vector!int(5);
413     int[] aa = [0, 1, 2, 3, 4, 5, 6, 7];
414     vec.insertBack(aa);
415     assert(vec.length == 8);
416 
417     vec.insertBack(10);
418     assert(vec.length == 9);
419 
420     Vector!(int) vec21;
421     vec21 ~= 15;
422     vec21 ~= vec;
423     assert(vec21.length == 10);
424 
425     assert(vec21.data == [15, 0, 1, 2, 3, 4, 5, 6, 7, 10]);
426 
427     vec21[1] = 500;
428     assert(vec21.data == [15, 500, 1, 2, 3, 4, 5, 6, 7, 10]);
429 
430     vec21.removeBack();
431     assert(vec21.length == 9);
432     assert(vec21.data == [15, 500, 1, 2, 3, 4, 5, 6, 7]);
433 
434     vec21.removeBack(3);
435     assert(vec21.length == 6);
436     assert(vec21.data == [15, 500, 1, 2, 3, 4]);
437 
438     vec21.insertBack(aa);
439     assert(vec21.data == [15, 500, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7]);
440 
441     vec21.removeSite(1);
442     assert(vec21.data == [15, 1, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7]);
443 
444     vec21.removeOne(1);
445     assert(vec21.data == [15, 2, 3, 4, 0, 1, 2, 3, 4, 5, 6, 7]);
446 
447     vec21.removeAny(2);
448     assert(vec21.data == [15, 3, 4, 0, 1, 3, 4, 5, 6, 7]);
449 
450     Vector!(ubyte[], Mallocator) vec2;
451     vec2.insertBack(cast(ubyte[]) "hahaha");
452     vec2.insertBack(cast(ubyte[]) "huhuhu");
453     assert(vec2.length == 2);
454     assert(cast(string) vec2[0] == "hahaha");
455     assert(cast(string) vec2[1] == "huhuhu");
456 
457     Vector!(int, IAllocator) vec22 = Vector!(int, IAllocator)(allocatorObject(Mallocator.instance));
458     int[] aa22 = [0, 1, 2, 3, 4, 5, 6, 7];
459     vec22.insertBack(aa22);
460     assert(vec22.length == 8);
461 
462     vec22.insertBack(10);
463     assert(vec22.length == 9);
464 
465     vec22.insertBack(aa22);
466     vec22.insertBack([0, 1, 2, 1, 212, 1215, 1545, 1212, 154, 51515, 1545,
467         1545, 1241, 51, 45, 1215, 12415, 12415, 1545, 12415, 1545, 152415,
468         1541515, 15415, 1545, 1545, 1545, 1545, 15454, 0, 54154]);
469 
470     vec22 ~=  [0, 1, 2, 1, 212];
471     immutable(int)[] dt = cast(immutable(int)[])vec22;
472     assert(dt.length == vec22.length);
473     //Vector!(shared int) vec2;
474 }