1 /*******************************************************************************
2 3 Utility template to implement Map.opApply()/Set.opApply(), working around
4 the problem that opApply() cannot have static array parameters because 'ref'
5 is forbidden for static arrays. The solution is to use dynamic arrays
6 instead and pass an array slice to to the 'foreach' loop body delegate.
7 8 Copyright:
9 Copyright (c) 2009-2016 dunnhumby Germany GmbH.
10 All rights reserved.
11 12 License:
13 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
14 Alternatively, this file may be distributed under the terms of the Tango
15 3-Clause BSD License (see LICENSE_BSD.txt for details).
16 17 *******************************************************************************/18 19 moduleocean.util.container.map.model.MapIterator;
20 21 importocean.util.container.map.model.Bucket;
22 23 /*******************************************************************************
24 25 Mixin that adds an iterator class and a member variable of it.
26 Note that this.iterator still has to be initialized by the constructor.
27 28 Params:
29 ParentIterator = parent class to inherit from
30 IteratorTemplate = Instance of the MapIterator template
31 32 *******************************************************************************/33 34 publictemplateIteratorClass ( aliasParentIterator, aliasIteratorTemplate )
35 {
36 /***************************************************************************
37 38 Iterator class offering specialized versions of opApply for the given
39 map/set class.
40 41 The appropriate type for the delegates is taken from the MapIterator
42 template.
43 44 ***************************************************************************/45 46 classIterator : ParentIterator47 {
48 /***********************************************************************
49 50 Ctor
51 52 ***********************************************************************/53 54 publicthis ( )
55 {
56 super(true);
57 }
58 59 /***********************************************************************
60 61 Protected Ctor, used for inheriting classes to ensure a certain
62 behavior
63 64 Params:
65 reset_after_foreach = whether to reset iteration counters
66 after a foreach (true) or not (false)
67 68 ***********************************************************************/69 70 protectedthis ( boolreset_after_foreach )
71 {
72 super(reset_after_foreach);
73 }
74 75 /***********************************************************************
76 77 Foreach support with counter
78 79 ***********************************************************************/80 81 publicintopApply ( IteratorTemplate.Dgidgi )
82 {
83 returnsuper.opApply((refsize_ti, refBucket.Elemente )
84 {
85 returnIteratorTemplate.iterate(dgi, i, e);
86 });
87 }
88 89 /***********************************************************************
90 91 Foreach support
92 93 ***********************************************************************/94 95 publicintopApply ( IteratorTemplate.Dgdg )
96 {
97 returnsuper.opApply((refBucket.Elemente )
98 {
99 returnIteratorTemplate.iterate(dg, e);
100 });
101 }
102 }
103 104 /***************************************************************************
105 106 Interruptible iterator
107 108 ***************************************************************************/109 110 classInterruptibleIterator : Iterator111 {
112 /***********************************************************************
113 114 Whether the iteration finished, set by resetIterator(), reset by
115 reset()
116 117 ***********************************************************************/118 119 protectedbool_finished;
120 121 /***********************************************************************
122 123 Constructor
124 125 ***********************************************************************/126 127 publicthis ( )
128 {
129 super(false);
130 }
131 132 /***********************************************************************
133 134 Set the finished flag.
135 136 Params:
137 interrupted = if true, the foreach iteration was interrupted
138 with a break, if false, it finished the iteration
139 140 ***********************************************************************/141 142 protectedoverridevoidresetIterator ( boolinterrupted )
143 {
144 this._finished = !interrupted;
145 }
146 147 /***********************************************************************
148 149 Prepare the iterator to restart the iteration from the beginning
150 151 ***********************************************************************/152 153 publicoverridevoidreset ( )
154 {
155 this._finished = false;
156 super.reset();
157 }
158 159 /***********************************************************************
160 161 Whether iteration finished
162 163 Returns:
164 true, if iteration finished
165 false, if not
166 167 ***********************************************************************/168 169 publicboolfinished ( )
170 {
171 return_finished;
172 }
173 }
174 }
175 176 /******************************************************************************
177 178 opApply wrapper to work around the problem that it isn't possible to have a
179 static array opApply() argument because 'ref' is not allowed with a static
180 array. Instead, the wrapper slices the argument and passes the slice to the
181 'foreach' body.
182 183 If the value type is 'void', the iteration delegate will only have a key
184 argument.
185 186 Params:
187 V = value type; 'void' indicates that there are no values at all.
188 K = key type
189 190 ******************************************************************************/191 192 templateMapIterator ( V, K = hash_t )
193 {
194 importocean.core.Verify;
195 196 /**************************************************************************
197 198 Kref type alias definition: A dynamic array of the base type of K if K
199 is a static array or K itself otherwise.
200 201 **************************************************************************/202 203 staticif (is (KKelement : Kelement[]) && !is (K == Kelement[]))
204 {
205 staticimmutablek_is_static_array = true;
206 207 aliasKelement[] Kref;
208 }
209 else210 {
211 staticimmutablek_is_static_array = false;
212 213 aliasKKref;
214 }
215 216 /**************************************************************************
217 218 Alias definitions of the Vref, the bucket element and the delegate type.
219 220 Vref is
221 - a dynamic array of the base type of V if V is a static array,
222 - not defined at all if V is 'void'
223 - V itself otherwise.
224 225 The delegate complies to the opApply() iteration delegate and iterates
226 over Kref only if V is 'void' or over Kref and Vref otherwise.
227 228 **************************************************************************/229 230 staticif (is (V == void))
231 {
232 staticimmutablev_is_static_array = false;
233 234 aliasintdelegate ( refKref ) Dg;
235 aliasintdelegate ( refsize_ti, refKref ) Dgi;
236 237 aliasBucket!(cast (size_t) 0, K).ElementElement;
238 }
239 else240 {
241 staticif (is (VVelement : Velement[]) && !is (V == Velement[]))
242 {
243 aliasVelement[] Vref;
244 245 staticimmutablev_is_static_array = true;
246 }
247 else248 {
249 aliasVVref;
250 251 staticimmutablev_is_static_array = false;
252 }
253 254 aliasintdelegate ( refKref, refVref ) Dg;
255 aliasintdelegate ( refsize_ti, refKref, refVref ) Dgi;
256 257 aliasBucket!(V.sizeof, K).ElementElement;
258 }
259 260 /**************************************************************************
261 262 Invokes dg with the key and, unless V is 'void', the value of element.
263 264 Do not modify the key in-place.
265 266 If K or V (or both) are a static array, a dynamic array slice is passed
267 to dg. Do not do a 'ref' iteration over static array keys or values.
268 To obtain a pointer to the static array key or value currently iterating
269 over, use the .ptr of the iteration variable.
270 271 Example: Consider a map that stores char[5] values with hash_t keys.
272 273 ---
274 foreach (ref key, val; map)
275 {
276 // typeof(key) is hash_t. A pointer to the key can be obtained
277 // using &key.
278 279 // typeof(val) is char[], val is a dynamic array slice
280 // referencing the value in the map. A pointer to the value can
281 // be obtained using val.ptr.
282 }
283 ---
284 285 Params:
286 dg = iteration delegate
287 element = bucket element
288 289 Returns:
290 passes through the return type of dg.
291 292 **************************************************************************/293 294 intiterate ( Dgdg, refElementelement )
295 {
296 // temporary replacement for nested function which purpose is to297 // prevent allocation of closure in D2 (because it tries to access298 // host function stack). In the long term will be replaced by better299 // d1to2fix support.300 301 staticstructDelegate302 {
303 Dgdg;
304 305 staticif (is (V == void))
306 {
307 intcall ( refsize_ti, refKrefk )
308 {
309 returndg(k);
310 }
311 }
312 else313 {
314 intcall ( refsize_ti, refKrefk, refVrefv )
315 {
316 returndg(k, v);
317 }
318 }
319 }
320 321 autotmpDg = Delegate(dg);
322 323 returniterate(&tmpDg.call, 0, element);
324 }
325 326 /***************************************************************************
327 328 Same method as above, but with counter
329 330 ***************************************************************************/331 332 intiterate ( Dgidg, size_ti, refElementelement )
333 {
334 staticif (k_is_static_array)
335 {
336 Krefkey = element.key;
337 338 Kref* key_ptr = &key;
339 }
340 else341 {
342 K* key = &element.key;
343 344 aliaskeykey_ptr;
345 }
346 347 scope (success)
348 {
349 // cast(bool) to handle Key==Object: opEquals returns int350 verify (cast(bool)(*key_ptr == element.key),
351 "attempted to change the key during iteration");
352 }
353 354 staticif (is (V == void))
355 {
356 returndg(i, *key_ptr);
357 }
358 elsestaticif (v_is_static_array)
359 {
360 Vrefval = *cast (V*) element.val.ptr;
361 362 size_tvlen = val.length;
363 364 scope (success)
365 {
366 verify (val.length == vlen,
367 "attempted to change the length of a static array "368 ~ "during iteration");
369 }
370 371 returndg(i, *key_ptr, val);
372 }
373 else374 {
375 returndg(i, *key_ptr, *cast (V*) element.val.ptr);
376 }
377 }
378 }