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 }