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

Page generated by adrdox