1 // Written in the D programming language.
2 
3 /**
4 
5 This module implements object collection.
6 
7 Wrapper around array of objects, providing a set of useful operations, and handling of object ownership.
8 
9 Optionally can be owner of its items if instanciated with ownItems=true - will destroy removed items.
10 
11 
12 Synopsis:
13 
14 ----
15 import dlangui.core.collections;
16 
17 // add
18 Collection!Widget widgets;
19 widgets ~= new Widget("id1");
20 widgets ~= new Widget("id2");
21 Widget w3 = new Widget("id3");
22 widgets ~= w3;
23 
24 // remove by index
25 widgets.remove(1);
26 
27 // foreach
28 foreach(w; widgets)
29     writeln("widget: ", w.id);
30 
31 // remove by value
32 widgets -= w3;
33 writeln(widgets[0].id);
34 ----
35 
36 
37 Copyright: Vadim Lopatin, 2014
38 License:   Boost License 1.0
39 Authors:   Vadim Lopatin, coolreader.org@gmail.com
40 */
41 module dlangui.core.collections;
42 
43 import std.algorithm;
44 
45 /** 
46     Array based collection of items.
47 
48     Retains item order when during add/remove operations.
49 
50     Optionally destroys removed objects when instanciated with ownItems = true.
51 */
52 struct Collection(T, bool ownItems = false) {
53     private T[] _items;
54     private size_t _len;
55     /// returns true if there are no items in collection
56     @property bool empty() { return _len == 0; }
57     /// returns number of items in collection
58     @property size_t length() { return _len; }
59     /// returns currently allocated capacity (may be more than length)
60     @property size_t size() { return _items.length; }
61     /// change capacity (e.g. to reserve big space to avoid multiple reallocations)
62     @property void size(size_t newSize) {
63         if (_len > newSize)
64             length = newSize; // shrink
65         _items.length = newSize; 
66     }
67     /// returns number of items in collection
68     @property void length(size_t newSize) { 
69         if (newSize < _len) {
70             // shrink
71             static if (is(T == class) || is(T == struct)) {
72                 // clear items
73                 for (size_t i = newSize; i < _len; i++) {
74                     static if (ownItems)
75                         destroy(_items[i]);
76                     _items[i] = T.init;
77                 }
78             }
79         } else if (newSize > _len) {
80             // expand
81             if (_items.length < newSize)
82                 _items.length = newSize;
83         }
84         _len = newSize;
85     }
86     /// access item by index
87     ref T opIndex(size_t index) {
88         assert(index < _len);
89         return _items[index];
90     }
91     /// insert new item in specified position
92     void add(T item, size_t index = size_t.max) {
93         if (index > _len)
94             index = _len;
95         if (_items.length <= _len) {
96             if (_items.length < 4)
97                 _items.length = 4;
98             else
99                 _items.length = _items.length * 2;
100         }
101         if (index < _len) {
102             for (size_t i = _len; i > index; i--)
103                 _items[i] = _items[i - 1];
104         }
105         _items[index] = item;
106         _len++;
107     }
108     /// add all items from other collection
109     void addAll(ref Collection!(T, ownItems) v) {
110         for (int i = 0; i < v.length; i++)
111             add(v[i]);
112     }
113     /// support for appending (~=, +=) and removing by value (-=)
114     ref Collection opOpAssign(string op)(T item) {
115         static if (op.equal("~") || op.equal("+")) {
116             // append item to end of collection
117             add(item);
118             return this;
119         } else if (op.equal("-")) {
120             // remove item from collection, if present
121             removeValue(item);
122             return this;
123         } else {
124             assert(false, "not supported opOpAssign " ~ op);
125         }
126     }
127     /// returns index of first occurence of item, size_t.max if not found
128     size_t indexOf(T item) {
129         for (size_t i = 0; i < _len; i++)
130             if (_items[i] == item)
131                 return i;
132         return size_t.max;
133     }
134     /// remove single item, returning removed item
135     T remove(size_t index) {
136         assert(index < _len);
137         T result = _items[index];
138         for (size_t i = index; i + 1 < _len; i++)
139             _items[i] = _items[i + 1];
140         _len--;
141         _items[_len] = T.init;
142         return result;
143     }
144     /// remove single item by value - if present in collection, returning true if item was found and removed
145     bool removeValue(T value) {
146         size_t index = indexOf(value);
147         if (index == size_t.max)
148             return false;
149         T res = remove(index);
150         static if (ownItems)
151             destroy(res);
152         return true;
153     }
154     /// support of foreach with reference
155     int opApply(int delegate(ref T param) op) {
156         int result = 0;
157         for (size_t i = 0; i < _len; i++) {
158             result = op(_items[i]);
159             if (result)
160                 break;
161         }
162         return result;
163     }
164     /// remove all items
165     void clear() {
166         static if (is(T == class) || is(T == struct)) {
167             /// clear references
168             for(size_t i = 0; i < _len; i++) {
169                 static if (ownItems)
170                     destroy(_items[i]);
171                 _items[i] = T.init;
172             }
173         }
174         _len = 0;
175         _items = null;
176     }
177 
178     //===================================
179     // stack/queue-like ops
180 
181     /// remove first item
182     @property T popFront() {
183         if (empty)
184             return T.init; // no items
185         return remove(0);
186     }
187 
188     /// peek first item
189     @property T peekFront() {
190         if (empty)
191             return T.init; // no items
192         return _items[0];
193     }
194 
195     /// insert item at beginning of collection
196     void pushFront(T item) {
197         add(item, 0);
198     }
199 
200     /// remove last item
201     @property T popBack() {
202         if (empty)
203             return T.init; // no items
204         return remove(length - 1);
205     }
206 
207     /// peek last item
208     @property T peekBack() {
209         if (empty)
210             return T.init; // no items
211         return _items[length - 1];
212     }
213 
214     /// insert item at end of collection
215     void pushBack(T item) {
216         add(item);
217     }
218 
219     /// peek first item
220     @property T front() {
221         if (empty)
222             return T.init; // no items
223         return _items[0];
224     }
225 
226     /// peek last item
227     @property T back() {
228         if (empty)
229             return T.init; // no items
230         return _items[_len - 1];
231     }
232     /// removes all items on destroy
233     ~this() {
234         clear();
235     }
236 }
237 
238 
239 /** object list holder, owning its objects - on destroy of holder, all own objects will be destroyed */
240 struct ObjectList(T) {
241     protected T[] _list;
242     protected int _count;
243     /** returns count of items */
244     @property int count() @safe @nogc const { return _count; }
245     alias length = count;
246     /** get item by index */
247     inout(T) get(int index) @safe inout {
248         assert(index >= 0 && index < _count, "child index out of range");
249         return _list[index];
250     }
251     /// get item by index
252     T opIndex(int index) @safe {
253         return get(index);
254     }
255     /** add item to list */
256     T add(T item) @safe {
257         if (_list.length <= _count) // resize
258             _list.length = _list.length < 4 ? 4 : _list.length * 2;
259         _list[_count++] = item;
260         return item;
261     }
262     /** add item to list */
263     T insert(T item, int index = -1) @safe {
264         if (index > _count || index < 0)
265             index = _count;
266         if (_list.length <= _count) // resize
267             _list.length = _list.length < 4 ? 4 : _list.length * 2;
268         for (int i = _count; i > index; i--)
269             _list[i] = _list[i - 1];
270         _list[index] = item;
271         _count++;
272         return item;
273     }
274     /** find child index for item, return -1 if not found */
275     int indexOf(T item) @safe @nogc const{
276         if (item is null)
277             return -1;
278         for (int i = 0; i < _count; i++)
279             if (_list[i] is item)
280                 return i;
281         return -1;
282     }
283     /** find child index for item by id, return -1 if not found */
284     static if (__traits(hasMember, T, "compareId")) {
285         int indexOf(string id) {
286             for (int i = 0; i < _count; i++)
287                 if (_list[i].compareId(id))
288                     return i;
289             return -1;
290         }
291     }
292     /** remove item from list, return removed item */
293     T remove(int index) @safe {
294         assert(index >= 0 && index < _count, "child index out of range");
295         T item = _list[index];
296         for (int i = index; i < _count - 1; i++)
297             _list[i] = _list[i + 1];
298         _count--;
299         return item;
300     }
301     /** Replace item with another value, destroy old value. */
302     void replace(T item, int index) {
303         T old = _list[index];
304         _list[index] = item;
305         destroy(old);
306     }
307     /** Replace item with another value, destroy old value. */
308     void replace(T newItem, T oldItem) {
309         int idx = indexOf(oldItem);
310         if (newItem is null) {
311             if (idx >= 0) {
312                 T item = remove(idx);
313                 destroy(item);
314             }
315         } else {
316             if (idx >= 0)
317                 replace(newItem, idx);
318             else
319                 add(newItem);
320         }
321     }
322     /** remove and destroy all items */
323     void clear(bool destroyObj = true) {
324         for (int i = 0; i < _count; i++) {
325             if(destroyObj) {
326                 destroy(_list[i]);
327             }
328             _list[i] = null;
329         }
330         _count = 0;
331     }
332     /// Support foreach
333     int opApply(int delegate(ref T) callback) {
334         int res = 0;
335         for(int i = 0; i < _count; i++) {
336             res = callback(_list[i]);
337             if (res)
338                 break;
339         }
340         return res;
341     }
342     /// Get items array slice. Don't try to resize it!
343     T[] asArray() {
344         if (!_count)
345             return null;
346         return _list[0.._count];
347     }
348     /// destructor destroys all items
349     ~this() {
350         clear();
351     }
352 }
353 
354 unittest
355 {
356     class Dummy
357     {
358         this() { }
359         this(int v) { a = v; }
360         int a = 11;
361     }
362     Dummy test = new Dummy(123);
363     ObjectList!Dummy d;
364     d.add(new Dummy());
365     assert(d.count == 1);
366     d.add(new Dummy(13));
367     assert(d.count == 2);
368     int count = 0;
369     foreach(a; d)
370         count++;
371     assert(count == 2);
372     d.remove(0);
373     assert(d[0].a == 13);
374     d.insert(new Dummy(44), 0);
375     d.insert(new Dummy(0), 1);
376     assert(d[0].a == 44 && d[1].a == 0);
377     d.insert(test);
378     assert(d.indexOf(test) == d.count() - 1);
379     d.replace(new Dummy(456), 0);
380     assert(d[0].a == 456);
381 }