1 /**
2 
3 This module implements object collections.
4 
5 Copyright: Vadim Lopatin, 2014
6 License:   Boost License 1.0
7 Authors:   Vadim Lopatin, coolreader.org@gmail.com
8 */
9 module collections;
10 
11 import std.algorithm;
12 
13 /** 
14     Array based collection of items.
15 
16     Retains item order when during add/remove operations.
17 
18     Optionally destroys removed objects when instanciated with ownItems = true.
19 */
20 struct Collection(T, bool ownItems = false) {
21     private T[] _items;
22     private size_t _len;
23     /// returns true if there are no items in collection
24     @property bool empty() { return _len == 0; }
25     /// returns number of items in collection
26     @property size_t length() { return _len; }
27     /// returns currently allocated capacity (may be more than length)
28     @property size_t size() { return _items.length; }
29     /// change capacity (e.g. to reserve big space to avoid multiple reallocations)
30     @property void size(size_t newSize) {
31         if (_len > newSize)
32             length = newSize; // shrink
33         _items.length = newSize; 
34     }
35     /// returns number of items in collection
36     @property void length(size_t newSize) { 
37         if (newSize < _len) {
38             // shrink
39             static if (is(T == class) || is(T == struct)) {
40                 // clear items
41                 for (size_t i = newSize; i < _len; i++) {
42 					static if (ownItems)
43 						destroy(_items[i]);
44                     _items[i] = T.init;
45 				}
46             }
47         } else if (newSize > _len) {
48             // expand
49             if (_items.length < newSize)
50                 _items.length = newSize;
51         }
52         _len = newSize;
53     }
54     /// access item by index
55     ref T opIndex(size_t index) {
56         assert(index < _len);
57         return _items[index];
58     }
59     /// insert new item in specified position
60     void add(T item, size_t index = size_t.max) {
61         if (index > _len)
62             index = _len;
63         if (_items.length <= _len) {
64             if (_items.length < 4)
65                 _items.length = 4;
66             else
67                 _items.length = _items.length * 2;
68         }
69         if (index < _len) {
70             for (size_t i = _len; i > index; i--)
71                 _items[i] = _items[i - 1];
72         }
73         _items[index] = item;
74         _len++;
75     }
76 	/// add all items from other collection
77 	void addAll(ref Collection!(T, ownItems) v) {
78 		for (int i = 0; i < v.length; i++)
79 			add(v[i]);
80 	}
81     /// support for appending (~=, +=) and removing by value (-=)
82     ref Collection opOpAssign(string op)(T item) {
83         static if (op.equal("~") || op.equal("+")) {
84             // append item to end of collection
85             add(item);
86             return this;
87         } else if (op.equal("-")) {
88             // remove item from collection, if present
89             removeValue(item);
90             return this;
91         } else {
92             assert(false, "not supported opOpAssign " ~ op);
93         }
94     }
95     /// returns index of first occurence of item, size_t.max if not found
96     size_t indexOf(T item) {
97         for (size_t i = 0; i < _len; i++)
98             if (_items[i] == item)
99                 return i;
100         return size_t.max;
101     }
102     /// remove single item, returning removed item
103     T remove(size_t index) {
104         assert(index < _len);
105         T result = _items[index];
106         for (size_t i = index; i + 1 < _len; i++)
107             _items[i] = _items[i + 1];
108         _items[_len] = T.init;
109         _len--;
110         return result;
111     }
112     /// remove single item by value - if present in collection, returning true if item was found and removed
113     bool removeValue(T value) {
114         size_t index = indexOf(value);
115         if (index == size_t.max)
116             return false;
117         T res = remove(index);
118 		static if (ownItems)
119 			destroy(res);
120         return true;
121     }
122     /// support of foreach with reference
123     int opApply(int delegate(ref T param) op) {
124         int result = 0;
125         for (size_t i = 0; i < _len; i++) {
126             result = op(_items[i]);
127             if (result)
128                 break;
129         }
130         return result;
131     }
132     /// remove all items
133     void clear() {
134         static if (is(T == class) || is(T == struct)) {
135             /// clear references
136             for(size_t i = 0; i < _len; i++) {
137 				static if (ownItems)
138 					destroy(_items[i]);
139                 _items[i] = T.init;
140 			}
141         }
142         _len = 0;
143         _items = null;
144     }
145 
146     //===================================
147     // stack/queue-like ops
148 
149     /// remove first item
150     @property T popFront() {
151         if (empty)
152             return T.init; // no items
153         return remove(0);
154     }
155 
156     /// insert item at beginning of collection
157     void pushFront(T item) {
158         add(item, 0);
159     }
160 
161     /// remove last item
162     @property T popBack() {
163         if (empty)
164             return T.init; // no items
165         return remove(length - 1);
166     }
167 
168     /// insert item at end of collection
169     void pushBack(T item) {
170         add(item);
171     }
172 
173     /// peek first item
174     @property T front() {
175         if (empty)
176             return T.init; // no items
177         return _items[0];
178     }
179 
180     /// peek last item
181     @property T back() {
182         if (empty)
183             return T.init; // no items
184         return _items[_len - 1];
185     }
186     /// removes all items on destroy
187     ~this() {
188         clear();
189     }
190 }
191 
192 
193 /** object list holder, owning its objects - on destroy of holder, all own objects will be destroyed */
194 struct ObjectList(T) {
195     protected T[] _list;
196     protected int _count;
197     /** returns count of items */
198     @property int count() const { return _count; }
199     /** get item by index */
200     T get(int index) {
201         assert(index >= 0 && index < _count, "child index out of range");
202         return _list[index];
203     }
204     /// get item by index
205     T opIndex(int index) {
206         return get(index);
207     }
208     /** add item to list */
209     T add(T item) {
210         if (_list.length <= _count) // resize
211             _list.length = _list.length < 4 ? 4 : _list.length * 2;
212         _list[_count++] = item;
213         return item;
214     }
215     /** add item to list */
216     T insert(T item, int index = -1) {
217         if (index > _count || index < 0)
218             index = _count;
219         if (_list.length <= _count) // resize
220             _list.length = _list.length < 4 ? 4 : _list.length * 2;
221         for (int i = _count; i > index; i--)
222             _list[i] = _list[i - 1];
223         _list[index] = item;
224         _count++;
225         return item;
226     }
227     /** find child index for item, return -1 if not found */
228     int indexOf(T item) {
229         if (item is null)
230             return -1;
231         for (int i = 0; i < _count; i++)
232             if (_list[i] == item)
233                 return i;
234         return -1;
235     }
236     /** find child index for item by id, return -1 if not found */
237     static if (__traits(hasMember, T, "compareId")) {
238         int indexOf(string id) {
239             for (int i = 0; i < _count; i++)
240                 if (_list[i].compareId(id))
241                     return i;
242             return -1;
243         }
244     }
245     /** remove item from list, return removed item */
246     T remove(int index) {
247         assert(index >= 0 && index < _count, "child index out of range");
248         T item = _list[index];
249         for (int i = index; i < _count - 1; i++)
250             _list[i] = _list[i + 1];
251         _count--;
252         return item;
253     }
254     /** Replace item with another value, destroy old value. */
255     void replace(T item, int index) {
256         T old = _list[index];
257         _list[index] = item;
258         destroy(old);
259     }
260     /** Replace item with another value, destroy old value. */
261     void replace(T newItem, T oldItem) {
262         int idx = indexOf(oldItem);
263         if (newItem is null) {
264             if (idx >= 0) {
265                 T item = remove(idx);
266                 destroy(item);
267             }
268         } else {
269             if (idx >= 0)
270                 replace(newItem, idx);
271             else
272                 add(newItem);
273         }
274     }
275     /** remove and destroy all items */
276     void clear() {
277         for (int i = 0; i < _count; i++) {
278             destroy(_list[i]);
279             _list[i] = null;
280         }
281         _count = 0;
282     }
283     ~this() {
284         clear();
285     }
286 }
287