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