1 /** 2 IndexedArray 3 4 Copyright: (c) Enalye 2017 5 License: Zlib 6 Authors: Enalye 7 */ 8 9 module atelier.core.indexedarray; 10 11 import std.parallelism; 12 import std.range; 13 import std.typecons; 14 15 /** 16 Special Array that remove fragmentation while keeping indexes valid. 17 */ 18 class IndexedArray(T, uint _capacity, bool _useParallelism = false) { 19 private uint _dataTop = 0u; 20 private uint _availableIndexesTop = 0u; 21 private uint _removeTop = 0u; 22 23 private T[_capacity] _dataTable; 24 private uint[_capacity] _availableIndexes; 25 private uint[_capacity] _translationTable; 26 private uint[_capacity] _reverseTranslationTable; 27 private uint[_capacity] _removeTable; 28 29 @property { 30 uint length() const { 31 return _dataTop; 32 } 33 34 uint capacity() const { 35 return _capacity; 36 } 37 38 ref T[_capacity] data() { 39 return _dataTable; 40 } 41 } 42 43 uint push(T value) { 44 uint index; 45 46 if ((_dataTop + 1u) == _capacity) { 47 throw new Exception("IndexedArray overload"); 48 } 49 50 if (_availableIndexesTop) { 51 //Take out the last available index on the list. 52 _availableIndexesTop--; 53 index = _availableIndexes[_availableIndexesTop]; 54 } 55 else { 56 //Or use a new id. 57 index = _dataTop; 58 } 59 60 //Add the value to the data stack. 61 _dataTable[_dataTop] = value; 62 _translationTable[index] = _dataTop; 63 _reverseTranslationTable[_dataTop] = index; 64 65 ++_dataTop; 66 67 return index; 68 } 69 70 void pop(uint index) { 71 uint valueIndex = _translationTable[index]; 72 73 //Push the index on the available indexes stack. 74 _availableIndexes[_availableIndexesTop] = index; 75 _availableIndexesTop++; 76 77 //Invalidate the index. 78 _translationTable[index] = -1; 79 80 //Take the top value on the stack and fill the gap. 81 _dataTop--; 82 if (valueIndex < _dataTop) { 83 uint userIndex = _reverseTranslationTable[_dataTop]; 84 _dataTable[valueIndex] = _dataTable[_dataTop]; 85 _translationTable[userIndex] = valueIndex; 86 _reverseTranslationTable[valueIndex] = userIndex; 87 } 88 } 89 90 void reset() { 91 _dataTop = 0u; 92 _availableIndexesTop = 0u; 93 _removeTop = 0u; 94 } 95 96 void markInternalForRemoval(uint index) { 97 synchronized { 98 _removeTable[_removeTop] = _reverseTranslationTable[index]; 99 _removeTop++; 100 } 101 } 102 103 void markForRemoval(uint index) { 104 _removeTable[_removeTop] = index; 105 _removeTop++; 106 } 107 108 void sweepMarkedData() { 109 for (uint i = 0u; i < _removeTop; i++) { 110 pop(_removeTable[i]); 111 } 112 _removeTop = 0u; 113 } 114 115 static if (_useParallelism) { 116 int opApply(int delegate(ref T) dlg) { 117 int result; 118 119 foreach (i; parallel(iota(_dataTop))) { 120 result = dlg(_dataTable[i]); 121 122 if (result) 123 break; 124 } 125 126 return result; 127 } 128 } 129 else { 130 int opApply(int delegate(ref T) dlg) { 131 int result; 132 133 foreach (i; 0u .. _dataTop) { 134 result = dlg(_dataTable[i]); 135 136 if (result) 137 break; 138 } 139 140 return result; 141 } 142 } 143 144 int opApply(int delegate(const ref T) dlg) const { 145 int result; 146 147 foreach (i; 0u .. _dataTop) { 148 result = dlg(_dataTable[i]); 149 150 if (result) 151 break; 152 } 153 154 return result; 155 } 156 157 static if (_useParallelism) { 158 int opApply(int delegate(ref T, uint) dlg) { 159 int result; 160 161 foreach (i; parallel(iota(_dataTop))) { 162 result = dlg(_dataTable[i], i); 163 164 if (result) 165 break; 166 } 167 168 return result; 169 } 170 } 171 else { 172 int opApply(int delegate(ref T, uint) dlg) { 173 int result; 174 175 foreach (i; 0u .. _dataTop) { 176 result = dlg(_dataTable[i], i); 177 178 if (result) 179 break; 180 } 181 182 return result; 183 } 184 } 185 186 int opApply(int delegate(const ref T, uint) dlg) const { 187 int result; 188 189 foreach (i; 0u .. _dataTop) { 190 result = dlg(_dataTable[i], i); 191 192 if (result) 193 break; 194 } 195 196 return result; 197 } 198 199 int opApply(int delegate(const Tuple!(const uint, const T)) dlg) const { 200 int result; 201 202 foreach (i; 0u .. _dataTop) { 203 result = dlg(tuple!(const uint, const T)(_reverseTranslationTable[i], _dataTable[i])); 204 205 if (result) 206 break; 207 } 208 209 return result; 210 } 211 212 T opIndex(uint index) { 213 return _dataTable[_translationTable[index]]; 214 } 215 216 bool has(uint index) { 217 if (index > _dataTop) 218 return false; 219 if (_translationTable[index] == -1) 220 return false; 221 return true; 222 } 223 224 /// Returns the first element in the list 225 T first() { 226 assert(_dataTop > 0); 227 return _dataTable[0]; 228 } 229 230 /// Returns the last element in the list 231 T last() { 232 assert(_dataTop > 0); 233 return _dataTable[_dataTop - 1]; 234 } 235 }