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 }