ocean.util.container.map.Set source code

1 /*******************************************************************************
2 
3     Template for a class implementing a set of hashed keys. The set is built on
4     top of an efficient bucket algorithm, allowing for fast look up of keys in
5     the set.
6 
7     Usage example:
8 
9     ---
10 
11         import ocean.util.container.map.HashSet;
12 
13         // A set of hash_t's
14         auto set = new HashSet;
15 
16         hash_t hash = 232323;
17 
18         // Add a hash
19         set.put(hash);
20 
21         // Check if a hash exists in the set (null if not found)
22         auto exists = hash in set;
23 
24         // Remove a hash from the set
25         set.remove(hash);
26 
27         // Clear the set
28         set.clear();
29 
30     ---
31 
32     Copyright:
33         Copyright (c) 2009-2016 dunnhumby Germany GmbH.
34         All rights reserved.
35 
36     License:
37         Boost Software License Version 1.0. See LICENSE_BOOST.txt for details.
38         Alternatively, this file may be distributed under the terms of the Tango
39         3-Clause BSD License (see LICENSE_BSD.txt for details).
40 
41 *******************************************************************************/
42 
43 module ocean.util.container.map.Set;
44 
45 
46 
47 import ocean.meta.types.Qualifiers;
48 
49 import ocean.util.container.map.model.BucketSet;
50 
51 import ocean.util.container.map.model.Bucket;
52 
53 import ocean.util.container.map.model.MapIterator;
54 
55 import ocean.util.container.map.model.StandardHash;
56 
57 version (UnitTestVerbose) import ocean.io.Stdout;
58 
59 /*******************************************************************************
60 
61     Debug switch for verbose unittest output (uncomment if desired)
62 
63 *******************************************************************************/
64 
65 //version = UnitTestVerbose;
66 
67 version ( UnitTestVerbose )
68 {
69     import ocean.io.Stdout;
70 }
71 
72 /*******************************************************************************
73 
74     StandardKeyHashingSet class template. Manages a set of K's with fast lookup
75     using a standard way of hash calculation:
76 
77     - If K is a primitive type (integer, floating point, character), the hash
78       value is calculated from the raw key data using the FNV1a hash function.
79     - If K is a dynamic or static array of a  primitive type, the hash value is
80       calculated from the raw data of the key array content using the FNV1a hash
81       function.
82     - If K is a class, struct or union, it is expected to implement toHash(),
83       which will be used.
84     - Other key types (arrays of non-primitive types, classes/structs/unions
85       which do not implement toHash(), pointers, function references, delegates,
86       associative arrays) are not supported by this class template.
87 
88 *******************************************************************************/
89 
90 public class StandardHashingSet ( K ) : Set!(K)
91 {
92     /***************************************************************************
93 
94         Constructor.
95 
96         Params:
97             n = expected number of elements in mapping
98             load_factor = ratio of n to the number of internal buckets. The
99                 desired (approximate) number of elements per bucket. For
100                 example, 0.5 sets the number of buckets to double n; for 2 the
101                 number of buckets is the half of n. load_factor must be greater
102                 than 0. The load factor is basically a trade-off between memory
103                 usage (number of buckets) and search time (number of elements
104                 per bucket).
105 
106     ***************************************************************************/
107 
108     public this ( size_t n, float load_factor = 0.75 )
109     {
110         super(n, load_factor);
111     }
112 
113     /***************************************************************************
114 
115         Constructor.
116 
117         Params:
118             allocator = custom bucket elements allocator
119             n = expected number of elements in mapping
120             load_factor = ratio of n to the number of internal buckets. The
121                 desired (approximate) number of elements per bucket. For
122                 example, 0.5 sets the number of buckets to double n; for 2 the
123                 number of buckets is the half of n. load_factor must be greater
124                 than 0. The load factor is basically a trade-off between memory
125                 usage (number of buckets) and search time (number of elements
126                 per bucket).
127 
128     ***************************************************************************/
129 
130     public this ( IAllocator allocator, size_t n, float load_factor = 0.75 )
131     {
132         super(allocator, n, load_factor);
133     }
134 
135     /***************************************************************************
136 
137         Mixin of the toHash() method which is declared abstract in BucketSet.
138 
139     ***************************************************************************/
140 
141     override:
142         mixin StandardHash.toHash!(K);
143 }
144 
145 
146 /*******************************************************************************
147 
148     Set class. Manages a set of K's with fast lookup. The toHash() method must
149     be implemented.
150 
151 *******************************************************************************/
152 
153 public abstract class Set ( K ) : BucketSet!(0, K)
154 {
155     private alias .MapIterator!(void, K) SetIterator;
156 
157     /***************************************************************************
158 
159         Mixin of the specialized iterator classes which inherit from
160         BucketSet.Iterator.
161 
162         This makes available three iterator classes that can be newed to allow
163         certain iteration behaviors:
164 
165         * Iterator — just a normal iterator
166         * InterruptibleIterator — an iterator that can be interrupted and
167           resumed, but that has to be manually reset with reset() if the
168           iteration is meant to be repeated
169 
170         If the map is modified between interrupted iterations, it can happen
171         that new elements that were added in the mean time won't appear in the
172         iteratation, depending on whether they end up in a bucket that was
173         already iterated or not.
174 
175         Iterator usage example
176         ---
177         auto map = new HashMap!(size_t);
178 
179         auto it = map.new Iterator();
180 
181         // A normal iteration over the map
182         foreach ( k, v; it )
183         {
184             ..
185         }
186 
187         // Equal to
188         foreach ( k, v; map )
189         {
190             ..
191         }
192         ---
193 
194         InterruptibleIterator
195         ---
196         auto map = new HashMap!(size_t);
197 
198         auto interruptible_it = map.new InterruptibleIterator();
199 
200         // Iterate over the first 100k elements
201         foreach ( i, k, v; interruptible_it )
202         {
203             ..
204             // Break after 100k elements
205             if ( i % 100_000 == 0 ) break;
206         }
207 
208         // Iterate over the next 100k elments
209         foreach ( i, k, v; interruptible_it )
210         {
211             ..
212             // Break after 100k elements
213             if ( i % 100_000 == 0 ) break;
214         }
215 
216         // Assuming the map had 150k elements, the iteration is done now,
217         // so this won't do anything
218         foreach ( i, k, v; interruptible_it )
219         {
220             ..
221             // Break after 100k elements
222             if ( i % 100_000 == 0 ) break;
223         }
224 
225         assert ( interruptible_it.finished() == true );
226         ---
227 
228         See also: BucketSet.Iterator, MapIterator.IteratorClass
229 
230     ***************************************************************************/
231 
232     mixin IteratorClass!(BucketSet!(0,K).Iterator, SetIterator);
233 
234     /***************************************************************************
235 
236         Constructor.
237 
238         Params:
239             n = expected number of elements in mapping
240             load_factor = ratio of n to the number of internal buckets. The
241                 desired (approximate) number of elements per bucket. For
242                 example, 0.5 sets the number of buckets to double n; for 2 the
243                 number of buckets is the half of n. load_factor must be greater
244                 than 0. The load factor is basically a trade-off between memory
245                 usage (number of buckets) and search time (number of elements
246                 per bucket).
247 
248     ***************************************************************************/
249 
250     protected this ( size_t n, float load_factor = 0.75 )
251     {
252         super(n, load_factor);
253     }
254 
255     /***************************************************************************
256 
257         Constructor.
258 
259         Params:
260             allocator = custom bucket elements allocator
261             n = expected number of elements in mapping
262             load_factor = ratio of n to the number of internal buckets. The
263                 desired (approximate) number of elements per bucket. For
264                 example, 0.5 sets the number of buckets to double n; for 2 the
265                 number of buckets is the half of n. load_factor must be greater
266                 than 0. The load factor is basically a trade-off between memory
267                 usage (number of buckets) and search time (number of elements
268                 per bucket).
269 
270     ***************************************************************************/
271 
272     protected this ( IAllocator allocator, size_t n, float load_factor = 0.75 )
273     {
274         super(allocator, n, load_factor);
275     }
276 
277 
278     /***************************************************************************
279 
280         Looks up key in the set.
281 
282         Params:
283             key = key to look up
284 
285         Returns:
286             true if found or false if not.
287 
288     ***************************************************************************/
289 
290     public bool opIn_r ( K key )
291     {
292         return this.get_(key) !is null;
293     }
294 
295 
296     /***************************************************************************
297 
298         Support for the 'in' operator
299 
300         Aliased to opIn_r, for backwards compatibility
301 
302     ***************************************************************************/
303 
304     public alias opBinaryRight ( istring op : "in" ) = opIn_r;
305 
306 
307     /***************************************************************************
308 
309         Puts key into the set.
310 
311         Params:
312             key = key to put into set
313 
314         Returns:
315             true if the key was already on the set, false otherwise
316 
317     ***************************************************************************/
318 
319     public bool put ( K key )
320     {
321         bool added;
322 
323         this.put_(key, added);
324 
325         return !added;
326     }
327 
328 
329     /***************************************************************************
330 
331         'foreach' iteration over set.
332 
333         Note: It is possible to have interruptible iterations, see documentation
334         for mixin of IteratorClass
335 
336         See also: BucketSet.Iterator, MapIterator.IteratorClass
337 
338         Notes:
339         - During iteration it is forbidden to call clear() or redistribute() or
340           remove map elements. If elements are added, the iteration may or may
341           not include these elements.
342         - If K is a static array, the iteration variable is a dynamic array of
343           the same base type and slices the key of the element in the map.
344           (The reason is that static array 'ref' parameters are forbidden in D.)
345           In this case DO NOT modify the key in any way!
346         - It is not recommended to do a 'ref' iteration over the keys. If you do
347           it anyway, DO NOT modify the key in-place!
348 
349     ***************************************************************************/
350 
351     public int opApply ( SetIterator.Dg dg )
352     {
353         scope it = this.new Iterator;
354 
355         return it.opApply(dg);
356     }
357 
358     /***************************************************************************
359 
360         Same as above, but includes a counter
361 
362     ***************************************************************************/
363 
364     public int opApply ( SetIterator.Dgi dgi )
365     {
366         scope it = this.new Iterator;
367 
368         return it.opApply(dgi);
369     }
370 }