ocean.util.container.map.model.MapIterator source code

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 module ocean.util.container.map.model.MapIterator;
20 
21 import ocean.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 public template IteratorClass ( alias ParentIterator, alias IteratorTemplate )
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     class Iterator : ParentIterator
47     {
48         /***********************************************************************
49 
50             Ctor
51 
52         ***********************************************************************/
53 
54         public this ( )
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         protected this ( bool reset_after_foreach )
71         {
72             super(reset_after_foreach);
73         }
74 
75         /***********************************************************************
76 
77             Foreach support with counter
78 
79         ***********************************************************************/
80 
81         public int opApply ( IteratorTemplate.Dgi dgi )
82         {
83             return super.opApply((ref size_t i, ref Bucket.Element e )
84                                  {
85                                     return IteratorTemplate.iterate(dgi, i, e);
86                                  });
87         }
88 
89         /***********************************************************************
90 
91             Foreach support
92 
93         ***********************************************************************/
94 
95         public int opApply ( IteratorTemplate.Dg dg )
96         {
97             return super.opApply((ref Bucket.Element e )
98                                  {
99                                     return IteratorTemplate.iterate(dg, e);
100                                  });
101         }
102     }
103 
104     /***************************************************************************
105 
106         Interruptible iterator
107 
108     ***************************************************************************/
109 
110     class InterruptibleIterator  : Iterator
111     {
112         /***********************************************************************
113 
114             Whether the iteration finished, set by resetIterator(), reset by
115             reset()
116 
117         ***********************************************************************/
118 
119         protected bool _finished;
120 
121         /***********************************************************************
122 
123             Constructor
124 
125         ***********************************************************************/
126 
127         public this ( )
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         protected override void resetIterator ( bool interrupted )
143         {
144             this._finished = !interrupted;
145         }
146 
147         /***********************************************************************
148 
149             Prepare the iterator to restart the iteration from the beginning
150 
151         ***********************************************************************/
152 
153         public override void reset ( )
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         public bool finished ( )
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 template MapIterator ( V, K = hash_t )
193 {
194     import ocean.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     static if (is (K Kelement : Kelement[]) && !is (K == Kelement[]))
204     {
205         static immutable k_is_static_array = true;
206 
207         alias Kelement[] Kref;
208     }
209     else
210     {
211         static immutable k_is_static_array = false;
212 
213         alias K Kref;
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     static if (is (V == void))
231     {
232         static immutable v_is_static_array = false;
233 
234         alias int delegate ( ref Kref ) Dg;
235         alias int delegate ( ref size_t i, ref Kref ) Dgi;
236 
237         alias Bucket!(cast (size_t) 0, K).Element Element;
238     }
239     else
240     {
241         static if (is (V Velement : Velement[]) && !is (V == Velement[]))
242         {
243             alias Velement[] Vref;
244 
245             static immutable v_is_static_array = true;
246         }
247         else
248         {
249             alias V Vref;
250 
251             static immutable v_is_static_array = false;
252         }
253 
254         alias int delegate ( ref Kref, ref Vref ) Dg;
255         alias int delegate ( ref size_t i, ref Kref, ref Vref ) Dgi;
256 
257         alias Bucket!(V.sizeof, K).Element Element;
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     int iterate ( Dg dg, ref Element element )
295     {
296         // temporary replacement for nested function which purpose is to
297         // prevent allocation of closure in D2 (because it tries to access
298         // host function stack). In the long term will be replaced by better
299         // d1to2fix support.
300 
301         static struct Delegate
302         {
303             Dg dg;
304 
305             static if (is (V == void))
306             {
307                 int call ( ref size_t i, ref Kref k )
308                 {
309                     return dg(k);
310                 }
311             }
312             else
313             {
314                 int call ( ref size_t i, ref Kref k, ref Vref v )
315                 {
316                     return dg(k, v);
317                 }
318             }
319         }
320 
321         auto tmpDg = Delegate(dg);
322 
323         return iterate(&tmpDg.call, 0, element);
324     }
325 
326     /***************************************************************************
327 
328         Same method as above, but with counter
329 
330     ***************************************************************************/
331 
332     int iterate ( Dgi dg, size_t i, ref Element element )
333     {
334         static if (k_is_static_array)
335         {
336             Kref key = element.key;
337 
338             Kref* key_ptr = &key;
339         }
340         else
341         {
342             K* key = &element.key;
343 
344             alias key key_ptr;
345         }
346 
347         scope (success)
348         {
349             // cast(bool) to handle Key==Object: opEquals returns int
350             verify (cast(bool)(*key_ptr == element.key),
351                     "attempted to change the key during iteration");
352         }
353 
354         static if (is (V == void))
355         {
356             return dg(i, *key_ptr);
357         }
358         else static if (v_is_static_array)
359         {
360             Vref val = *cast (V*) element.val.ptr;
361 
362             size_t vlen = 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             return dg(i, *key_ptr, val);
372         }
373         else
374         {
375             return dg(i, *key_ptr, *cast (V*) element.val.ptr);
376         }
377     }
378 }