anansi.container.array source code

1 module anansi.container.array;
2 
3 import std.algorithm, std.conv, std.range, std.stdio, std.traits;
4 
5 version(unittest) {
6     import std.range;
7 }
8 
9 public struct Array(T) {
10 private:
11     this(size_t size, T[] payload) {
12         _size = size;
13         _payload = payload;
14     }
15 
16 public:
17     this(U)(U[] stuff) if (isImplicitlyConvertible!(U, T)) {
18         foreach(s; stuff)
19             insertBack(s);
20     }
21 
22     this(Stuff)(Stuff stuff) if (isInputRange!Stuff && 
23                                  isImplicitlyConvertible!(ElementType!Stuff, T) &&
24                                  !is(Stuff == T[])) {
25         foreach(s; stuff) 
26             insertBack(s);
27     }
28 
29     this(this) {
30         _payload = _payload[0 .. _size].dup;
31     }
32 
33     invariant() { 
34         assert(_size >= 0); 
35         assert(_payload.length >= _size);
36     }
37 
38 public:
39     size_t insertBack(T value) {
40         ensureSpace(_size+1);
41         _payload[_size] = move(value);
42         return _size++;
43     }
44 
45     size_t insert(T value, size_t index) 
46     in {
47         assert(index <= _size);
48     }
49     body {
50         ensureSpace(_size+1);
51         moveAll(_payload[index .. $-1], _payload[index + 1 .. $]);
52         _payload[index] = move(value);
53         _size += 1;
54         return index;
55     }
56 
57     void erase(size_t index) {
58         erase(index, 1);
59     }
60 
61     /**
62      * Erases a contiguous range of items from the array.
63      */
64     void erase(size_t index, size_t count) 
65     in {
66         assert(index < _size, "Index must be smaller than Array.length.");
67         assert((index + count) <= _size, "Range must not overflow array.");
68     }
69     body {
70         auto leftovers = moveAll(_payload[index + count .. $], _payload[index .. $]);
71         foreach(ref t; leftovers) { t = T.init; }
72 
73         _size -= count;
74         if (_size < (_payload.length / 2))
75             _payload.length = _size;
76     }
77 
78     void eraseFrontOfRange(RangeT)(RangeT r) 
79         if (is(RangeT == Range!T) || is(RangeT == Range!(const T)))
80     in {
81         assert (!r.empty, "Range must not be empty.");
82         assert (r._data is _payload);
83     }
84     body {
85         erase(r._index, 1);
86     }
87 
88     void reserve(size_t n) {     
89         if (_payload.length < n)
90             _payload.length = n;
91     }
92 
93     auto opSlice() {
94         return Range!(T)(_payload, _size);
95     }
96 
97     auto opSlice() const {
98         return Range!(const T)(_payload, _size);
99     }
100 
101 public:
102     static struct Range(ElementT) {
103         this(ElementT[] data, size_t size) {
104             _index = 0;
105             _data = data;
106             _size = size;
107         }
108 
109         @property bool empty() const {
110             return _index == _size;
111         }
112 
113         @property size_t length() const {
114             return _size;
115         } 
116 
117         @property ref ElementT front() 
118         in {
119             assert (_index < _size);
120         }
121         body {
122             return _data[_index];
123         }
124 
125         void popFront() 
126         in {
127             assert (_index < _size);
128         }
129         body {
130             ++_index;
131         }
132 
133     private:
134         size_t _index;
135         size_t _size;
136         ElementT[] _data;
137     }
138 
139     alias ConstRange = Range!(const T);
140 
141     /**
142      * Provides [] sytax for the array.
143      */
144     public ref inout(T) opIndex(size_t index) inout
145     in {
146         assert(index < _size, "Index must be less than Array.length.");
147     }
148     body {
149         return _payload[index];
150     }
151 
152     /**
153      * Returns the number of elements currently stored in the array.
154      */
155     public @property size_t length() const {
156         return _size;
157     }
158 
159     /**
160      * Returns the number of items the array could store, given its 
161      * current buffer allocation.
162      */
163     public @property size_t capacity() const {
164         return _payload.length;
165     }
166 
167     public @property Array dup() {
168         return Array(_size, _payload[0 .. _size].dup);
169     }
170 
171     /**
172      * Ensures that there is storage space a minimum number of elements in
173      * the array, possibly over-allocating for efficiency's sake.
174      */
175     private void ensureSpace(size_t n) {
176         if (_payload.length < n) {
177             size_t newSize = 1 + ((_payload.length * 3) / 2);
178             auto newPayload = new T[newSize];
179             moveAll(_payload, newPayload[0 .. _size]);            
180             _payload = newPayload;
181         }
182     }
183 
184     private size_t _size;
185     private T[] _payload;
186 }
187 
188 unittest {
189   writeln("Array: empty construction yields a valid Array.");
190   Array!string s;
191   assert(s.length == 0);
192   assert(s.capacity >= 0);
193 }
194 
195 unittest {
196   writeln("Array: construction from a Range yields a valid Array.");
197   auto data = ["alpha", "beta", "delta", "gamma", "epsilon"];
198   auto s = Array!string(data);
199 
200   assert(s.length == data.length);
201   for(auto i = 0; i < data.length; ++i)
202     assert(s[i] == data[i]);
203 }
204 
205 unittest {
206   writeln("Array: insertion into empty Array yields a valid 1-element array.");
207   Array!string a;
208   auto i = a.insert("hi", 0);
209   assert (a.length == 1, "Incorrect length after insertion.");
210   assert (a[0] == "hi", "Incorrect value at insertion point.");
211   assert (i == 0, "Incorrect insertion point index returned.");
212 }
213 
214 unittest {
215   writeln("Array: insertion at the end of an Array.");
216   auto data = ["alpha", "beta", "delta", "gamma", "epsilon"];
217   auto a = Array!string(data);
218   auto i = a.insert("o hai", a.length);
219   assert (i == data.length, "Incorrect insertion point index returned.");
220 
221   assert (a.length == (data.length+1), "Incorrect length after insertion.");  
222 
223   for(auto n = 0; n < data.length; ++n) 
224     assert (a[n] == data[n]);
225 
226   assert (a[data.length] == "o hai", 
227           "Incorrect value at insertion point.");
228 }
229 
230 unittest {
231   writeln("Array: erasing a single item in the middle of the list.");
232   auto a = Array!int(iota(0, 100, 1));
233   assert(a.length == 100);
234   assert(a[7] == 7);
235 
236   a.erase(7);    
237   assert(a.length == 99);
238   foreach(i; 0 .. 7)
239     assert(a[i] == i);
240 
241   foreach(i; 7 .. 99)
242     assert(a[i] == (i+1));
243 }
244 
245 version(unittest) {
246   /**
247    * A test struct that tracks the execution of its destructor, for use in
248    * testing.
249    */
250   struct DtorTestValue {
251     static int dtorCount = 0;
252     int n;
253     ~this() {
254       if (n != 0) {
255         ++dtorCount;                
256       }
257     }
258   }
259 }
260 
261 
262 unittest {
263   writeln("Array: erasing the only item in an Array.");
264   auto a = Array!DtorTestValue();    
265   a.insertBack(DtorTestValue(1));
266   DtorTestValue.dtorCount = 0;
267   a.erase(0);   
268   assert(a.length == 0);    
269   assert (DtorTestValue.dtorCount == 1, 
270           "bad dtor count: " ~ to!string(DtorTestValue.dtorCount));
271 }
272 
273 unittest {
274   writeln("Array: erasing the first item in an Array.");
275   Array!DtorTestValue a;
276   a.reserve(100);
277   foreach(n; 0 .. 100)
278     a.insertBack(DtorTestValue(n+1));
279 
280   DtorTestValue.dtorCount = 0;
281   a.erase(0);    
282   assert(a.length == 99);
283 
284   assert (DtorTestValue.dtorCount == 1, 
285           "bad dtor count: " ~ to!string(DtorTestValue.dtorCount));
286 
287   foreach(i; 0 .. 99) {
288     assert(a[i].n == (i+2), 
289           "Invalid post-erase value: expected " ~ to!string(i+2) ~ 
290           ", got: " ~ to!string(a[i].n));
291   }
292 }
293 
294 unittest {
295   writeln("Array: erasing the last item in an array.");
296   Array!DtorTestValue a;
297   a.reserve(100);
298   foreach(n; 0 .. 100)
299     a.insertBack(DtorTestValue(n+1));
300 
301   DtorTestValue.dtorCount = 0;
302   a.erase(99);    
303   assert(a.length == 99);
304 
305   assert (DtorTestValue.dtorCount == 1, 
306           "bad dtor count: " ~ to!string(DtorTestValue.dtorCount));
307 
308   foreach(i; 0 .. 99)
309     assert(a[i].n == i+1);
310 }
311 
312 unittest {
313   writeln("Array: erasing a single, essentially random, item.");
314   Array!DtorTestValue a;
315   a.reserve(100);
316   foreach(n; 0 .. 100)
317     a.insertBack(DtorTestValue(n+1));
318 
319   DtorTestValue.dtorCount = 0;
320   a.erase(7);    
321   assert(a.length == 99);
322 
323   assert (DtorTestValue.dtorCount == 1, 
324           "bad dtor count: " ~ to!string(DtorTestValue.dtorCount));
325 
326   foreach(i; 0 .. 7)
327     assert(a[i].n == (i+1));
328 
329   foreach(i; 7 .. 99)
330     assert(a[i].n == (i+2));
331 }
332 
333 unittest {
334   writeln("Array: erasing a range of items from the array.");
335   auto a = Array!int(iota(0, 100, 1));
336   a.erase(25, 50);
337   assert (a.length == 50, 
338     "Post-erasure length is wrong: " ~ to!string(a.length)); 
339 
340   foreach(i; 0 .. 25)
341     assert(a[i] == i, "Bad pre-erased-range value");
342 
343   foreach(i; 25 .. 50)
344     assert(a[i] == (i+50), "Bad post-erased-range value. " ~
345                            "Expected " ~ to!string(i+25) ~ 
346                            ", got " ~ to!string(a[i]));
347 }
348 
349 unittest {
350   writeln("Array: erasing the entire array");
351   auto a = Array!int(iota(0, 100, 1));
352   assert(a.length == 100);
353   a.erase(0, 100);
354 
355   assert(a.length == 0, 
356     "Array should be empty after erasing it all.");
357 
358   assert(a.capacity == 0, 
359     "Internal capacity should be 0 after erasing all items.");
360 }