1 module betterclist;
2 
3 import std.algorithm;
4 import std.range;
5 import std.traits;
6 
7 struct List(T, long N = -1)
8 {
9 @nogc:
10     alias ElementType = T;
11 
12     /// Whether List has fixed size, which means it is backed by a static array
13     enum isSized = N >= 0;
14     static if (isSized)
15     {
16         /// Static array with capacity N that holds the List elements.
17         T[N] array;
18 
19         /// Construct List with initial elements.
20         this(Args...)(auto ref Args args)
21         {
22             pushBack(args);
23         }
24     }
25     else
26     {
27         /// Slice with dynamic capacity that holds the List elements.
28         T[] array;
29 
30         /// Construct List with backing slice and optional initial elements.
31         this(Args...)(T[] backingSlice, auto ref Args args)
32         {
33             this.array = backingSlice;
34             static if (args.length > 0)
35             {
36                 pushBack(args);
37             }
38         }
39 
40         /// Construct List with backing pointer and capacity and optional initial elements.
41         this(Args...)(T* backingArrayPointer, size_t capacity, auto ref Args args)
42         {
43             this(backingArrayPointer[0 .. capacity], args);
44         }
45 
46         /// Construct List with backing buffer slice and optional initial elements.
47         this(Args...)(void[] backingSlice, auto ref Args args)
48         {
49             this(cast(T[]) backingSlice, args);
50         }
51 
52         /// Construct List with backing buffer pointer and size and optional initial elements.
53         this(Args...)(void* backingArrayPointer, size_t bufferSize, auto ref Args args)
54         {
55             this(backingArrayPointer[0 .. bufferSize], args);
56         }
57     }
58     /// Current used length, must be less than array's length.
59     /// This is readonly accessible by the `length` property from used slice.
60     private size_t usedLength = 0;
61 
62     invariant
63     {
64         assert(usedLength <= array.length);
65     }
66 
67     /// List element capacity, which is the backing array's length.
68     @property size_t capacity() const pure @safe nothrow
69     {
70         return array.length;
71     }
72 
73     /// Available capacity for inserting elements.
74     @property size_t availableCapacity() const pure @safe nothrow
75     {
76         return capacity - usedLength;
77     }
78 
79     /// Returns whether there are no elements in List.
80     @property bool empty() const pure @safe nothrow
81     {
82         return usedLength == 0;
83     }
84 
85     /// Returns whether List is full, that is, has no more available capacity.
86     @property bool full() const pure @safe nothrow
87     {
88         return usedLength == capacity;
89     }
90 
91     /// Get a slice for the used elements.
92     auto usedSlice() inout pure
93     {
94         return array[0 .. usedLength];
95     }
96     /// Get a slice for the remaining elements.
97     private auto remainingSlice() inout pure
98     {
99         return array[usedLength .. capacity];
100     }
101 
102     /// Get a slice for the used elements.
103     auto opIndex() inout pure
104     {
105         return usedSlice;
106     }
107     /// Index the slice of used elements.
108     auto ref opIndex(const size_t index) inout pure
109     in { assert(index < usedLength); }
110     do
111     {
112         return usedSlice[index];
113     }
114     /// Alias this allows operations to target used slice by default.
115     alias usedSlice this;
116 
117     /++
118      + Push a value in the end of List.
119      + Returns: 0 if value was successfully inserted, 1 otherwise.
120      +/
121     long pushBack(U)(auto ref U value)
122     if (!isInputRange!U)
123     {
124         if (full)
125         {
126             return 1;
127         }
128         array[usedLength] = value;
129         usedLength++;
130         return 0;
131     }
132 
133     /++
134      + Push a range of values to the end of List.
135      + Returns: number of values not inserted into List:
136      +          0 if all values were inserted successfully,
137      +          positive number if the number of remaining elements is known,
138      +          -1 if the number of remaining elements is not know.
139      +/
140     long pushBack(R)(auto ref R range)
141     if (isInputRange!R)
142     {
143         static if (hasLength!R)
144         {
145             auto rangeLength = range.length;
146             if (rangeLength > availableCapacity)
147             {
148                 range.take(availableCapacity).copy(remainingSlice);
149                 usedLength = capacity;
150                 return cast(typeof(return))(range.length - availableCapacity);
151             }
152             range.copy(remainingSlice);
153             usedLength += rangeLength;
154             return 0;
155         }
156         else
157         {
158             while (!range.empty && usedLength < capacity)
159             {
160                 array[usedLength] = range.front;
161                 usedLength++;
162                 range.popFront;
163             }
164             return range.empty ? 0 : -1;
165         }
166     }
167 
168     /// Ditto
169     long pushBack(Args...)(auto ref Args args)
170     if (args.length > 1)
171     {
172         return pushBack(only(args));
173     }
174     alias push = pushBack;
175 
176     /// Push back elements on `list ~= args`
177     auto opOpAssign(string op : "~", Args...)(auto ref Args args)
178     {
179         return pushBack(args);
180     }
181 
182     /++
183      + Pop the last element from List.
184      + If element type has elaborate destructor, popped slot is reinitialized to `T.init`.
185      +/
186     void popBack()
187     {
188         if (!empty)
189         {
190             usedLength--;
191             static if (hasElaborateDestructor!T)
192             {
193                 array[usedLength] = T.init;
194             }
195         }
196     }
197     /++
198      + Pop `count` elements from the back of the List.
199      + If element type has elaborate destructor, popped slots are reinitialized to `T.init`.
200      +/
201     void popBack(const size_t count)
202     {
203         auto minCount = min(count, usedLength);
204         static if (hasElaborateDestructor!T)
205         {
206             usedSlice.retro.take(minCount).fill(T.init);
207         }
208         usedLength -= minCount;
209     }
210     alias pop = popBack;
211 
212     /++
213      + Clear all elements of List.
214      + If element type has elaborate destructor, popped slots are reinitialized to `T.init`.
215      +/
216     void clear()
217     out { assert(length == 0); assert(empty); }
218     do
219     {
220         static if (hasElaborateDestructor!T)
221         {
222             usedSlice.fill(T.init);
223         }
224         usedLength = 0;
225     }
226 }
227 
228 unittest
229 {
230     List!(int, 8) l;
231     assert(l.length == 0);
232     assert(l[] == null);
233     assert(l == null);
234 
235     assert(l.pushBack(5) == 0);
236     assert(l.length == 1);
237     assert(l[0] == 5);
238     assert(l == [5]);
239     assert(l[0 .. $] == [5]);
240 
241     l[0] = 10;
242     assert(l.length == 1);
243     assert(l[0] == 10);
244     assert(l == [10]);
245     assert(l[0 .. $] == [10]);
246 
247     assert(l.pushBack(iota(4)) == 0);
248     assert(l.length == 5);
249     assert(l == [10, 0, 1, 2, 3]);
250     assert(l[].sum == 16);
251     assert(l[$-2 .. $] == [2, 3]);
252 
253     int five() { return 5; }
254     assert(l.pushBack(generate!five) < 0);
255     assert(l.full);
256     assert(l == [10, 0, 1, 2, 3, 5, 5, 5]);
257 
258     assert(l.pushBack(500) > 0);
259     assert(l.back == 5);
260     l.popBack();
261     assert(l.length == l.capacity - 1);
262     assert((l ~= 500) == 0);
263     assert(l.full);
264     assert(l.back == 500);
265 
266     l.popBack(2);
267     assert(l.length == l.capacity - 2);
268     l.clear();
269     assert(l.empty);
270     l.popBack(42);
271 }
272 
273 unittest
274 {
275     int[10] array = 42;
276     auto l = List!(int)(array[]);
277     assert(l.capacity == 10);
278     assert(l.length == 0);
279     assert(l[] == null);
280     assert(l == null);
281 
282     auto l2 = List!(int)(array[], 0, 1);
283     assert(l2.capacity == 10);
284     assert(l2.length == 2);
285     assert(l2[] == [0, 1]);
286     assert(l2 == [0, 1]);
287 }
288 
289 unittest
290 {
291     import std.experimental.allocator.mallocator : Mallocator;
292     void[] buffer = Mallocator.instance.allocate(8 * int.sizeof);
293 
294     auto l = List!(int)(buffer);
295     assert(l.capacity == 8);
296 
297     Mallocator.instance.deallocate(buffer);
298 }
299 
300 unittest
301 {
302     import betterclist : List;
303 
304     // Lists may be backed by static arrays by passing the capacity to template
305     List!(int, 16) list;
306     assert(list.capacity == 16);
307 
308     // Lists track their own element usage
309     assert(list.length == 0);
310     assert(list.empty);
311 
312     list.pushBack(0);  // pushBack inserts an element in the end of the used slice
313     assert(list.length == 1);
314     assert(list[0] == 0);  // opIndex(size_t) indexes used elements slice, `list[1]` is out of bounds here
315     list[0] = 1;  // assigning to index works, if your List is mutable
316 
317     list.push(2, 3);  // push is an alias to pushBack. Several elements may be pushed at once
318     assert(list[] == [1, 2, 3]);  // opIndex() returns the used slice
319     assert(list.availableCapacity == 13);
320 
321     list ~= 4;  // operator ~= also calls pushBack
322     assert(list == [1, 2, 3, 4]);  // Lists are aliased to the used slice by `alias this`
323     assert(list[2 .. $] == [3, 4]);  // this means stuff like opDollar, slicing and length just works
324     // so does foreach
325     import std.stdio : writeln;
326     foreach (value; list)
327     {
328         writeln(value);
329     }
330     // so does importing common range stuff
331     import std.range;
332     assert(list.front == 1);
333     assert(list.back == 4);
334 
335     list.popBack();  // pops the last value. If element type has elaborate detructors, reinitializes element to it's `.init` value
336     assert(list == [1, 2, 3]);
337     list.popBack(2);  // pops the last N values. The same caveats apply
338     assert(list == [1]);
339     list.pop();  // pop is an alias to popBack
340     assert(list == null);
341     list.pop(42);  // popping more items than there are is safe
342     list.clear();  // pops all elements from List
343     assert(list.empty);
344 
345     list.push(iota(16));  // ranges can be pushed at once
346     assert(list.full);
347     auto result = list.push(1, 2);  // Trying to push more items than capacity permits is an error, but no exception is thrown...
348     assert(result == 2);  // ...rather pushBack returns the number of items that were not inserted
349     list.clear();
350     result = list.push(1, 1, 2, 3, 5);
351     assert(result == 0);  // if all items were inserted, pushBack returns 0
352     result = list.pushBack(repeat(42));  // if range has no known length and not all elements were inserted...
353     assert(result < 0);  // ...pushBack returns a negative value
354 
355     // Lists can also be backed by a slice
356     import core.stdc.stdlib : malloc, free;
357     alias IntList = List!int;
358 
359     enum bufferSize = 8 * int.sizeof;
360     void* buffer = malloc(bufferSize);
361 
362     // Construction using void[]
363     auto sliceList = IntList(buffer[0 .. bufferSize]);
364     assert(sliceList.capacity == 8);
365 
366     // Construction using element type slice
367     sliceList = IntList(cast(int[]) buffer[0 .. bufferSize]);
368     assert(sliceList.capacity == 8);
369 
370     // Construction using void pointer and explicit buffer size (be careful!)
371     sliceList = IntList(buffer, bufferSize);
372     assert(sliceList.capacity == 8);
373 
374     // Construction using element type pointer and explicit capacity (be careful!)
375     sliceList = IntList(cast(int*) buffer, 8);
376     assert(sliceList.capacity == 8);
377 
378     // Lists backed by slices do not manage their own memory (TODO: memory mamaged (noGC, but destructor/auto resize) List type)
379     free(buffer);
380 }