|
132
|
1 /*
|
|
|
2 File: HashSet.d
|
|
|
3
|
|
|
4 Originally written by Doug Lea and released into the public domain.
|
|
|
5 Thanks for the assistance and support of Sun Microsystems Labs, Agorics
|
|
|
6 Inc, Loral, and everyone contributing, testing, and using this code.
|
|
|
7
|
|
|
8 History:
|
|
|
9 Date Who What
|
|
|
10 24Sep95 dl@cs.oswego.edu Create from tango.util.collection.d working file
|
|
|
11 13Oct95 dl Changed protection statuses
|
|
|
12
|
|
|
13 */
|
|
|
14
|
|
|
15
|
|
|
16 module tango.util.collection.HashSet;
|
|
|
17
|
|
|
18 private import tango.core.Exception;
|
|
|
19
|
|
|
20 private import tango.util.collection.model.Iterator,
|
|
|
21 tango.util.collection.model.HashParams,
|
|
|
22 tango.util.collection.model.GuardIterator;
|
|
|
23
|
|
|
24 private import tango.util.collection.impl.LLCell,
|
|
|
25 tango.util.collection.impl.SetCollection,
|
|
|
26 tango.util.collection.impl.AbstractIterator;
|
|
|
27
|
|
|
28
|
|
|
29 /**
|
|
|
30 *
|
|
|
31 * Hash table implementation of set
|
|
|
32 *
|
|
|
33 author: Doug Lea
|
|
|
34 * @version 0.93
|
|
|
35 *
|
|
|
36 * <P> For an introduction to this package see <A HREF="index.html"> Overview </A>.
|
|
|
37 **/
|
|
|
38
|
|
|
39 public class HashSet(T) : SetCollection!(T), HashParams
|
|
|
40 {
|
|
|
41 private alias LLCell!(T) LLCellT;
|
|
|
42
|
|
|
43 alias SetCollection!(T).remove remove;
|
|
|
44 alias SetCollection!(T).removeAll removeAll;
|
|
|
45
|
|
|
46
|
|
|
47 // instance variables
|
|
|
48
|
|
|
49 /**
|
|
|
50 * The table. Each entry is a list. Null if no table allocated
|
|
|
51 **/
|
|
|
52 private LLCellT table[];
|
|
|
53 /**
|
|
|
54 * The threshold load factor
|
|
|
55 **/
|
|
|
56 private float loadFactor;
|
|
|
57
|
|
|
58
|
|
|
59 // constructors
|
|
|
60
|
|
|
61 /**
|
|
|
62 * Make an empty HashedSet.
|
|
|
63 **/
|
|
|
64
|
|
|
65 public this ()
|
|
|
66 {
|
|
|
67 this(null, defaultLoadFactor);
|
|
|
68 }
|
|
|
69
|
|
|
70 /**
|
|
|
71 * Make an empty HashedSet using given element screener
|
|
|
72 **/
|
|
|
73
|
|
|
74 public this (Predicate screener)
|
|
|
75 {
|
|
|
76 this(screener, defaultLoadFactor);
|
|
|
77 }
|
|
|
78
|
|
|
79 /**
|
|
|
80 * Special version of constructor needed by clone()
|
|
|
81 **/
|
|
|
82
|
|
|
83 protected this (Predicate s, float f)
|
|
|
84 {
|
|
|
85 super(s);
|
|
|
86 table = null;
|
|
|
87 loadFactor = f;
|
|
|
88 }
|
|
|
89
|
|
|
90 /**
|
|
|
91 * Make an independent copy of the table. Does not clone elements.
|
|
|
92 **/
|
|
|
93
|
|
|
94 public final HashSet duplicate()
|
|
|
95 {
|
|
|
96 auto c = new HashSet (screener, loadFactor);
|
|
|
97
|
|
|
98 if (count !is 0)
|
|
|
99 {
|
|
|
100 int cap = 2 * cast(int)(count / loadFactor) + 1;
|
|
|
101 if (cap < defaultInitialBuckets)
|
|
|
102 cap = defaultInitialBuckets;
|
|
|
103
|
|
|
104 c.buckets(cap);
|
|
|
105 for (int i = 0; i < table.length; ++i)
|
|
|
106 for (LLCellT p = table[i]; p !is null; p = p.next())
|
|
|
107 c.add(p.element());
|
|
|
108 }
|
|
|
109 return c;
|
|
|
110 }
|
|
|
111
|
|
|
112
|
|
|
113 // HashTableParams methods
|
|
|
114
|
|
|
115 /**
|
|
|
116 * Implements tango.util.collection.HashTableParams.buckets.
|
|
|
117 * Time complexity: O(1).
|
|
|
118 * See_Also: tango.util.collection.HashTableParams.buckets.
|
|
|
119 **/
|
|
|
120
|
|
|
121 public final int buckets()
|
|
|
122 {
|
|
|
123 return (table is null) ? 0 : table.length;
|
|
|
124 }
|
|
|
125
|
|
|
126 /**
|
|
|
127 * Implements tango.util.collection.HashTableParams.buckets.
|
|
|
128 * Time complexity: O(n).
|
|
|
129 * See_Also: tango.util.collection.HashTableParams.buckets.
|
|
|
130 **/
|
|
|
131
|
|
|
132 public final void buckets(int newCap)
|
|
|
133 {
|
|
|
134 if (newCap is buckets())
|
|
|
135 return ;
|
|
|
136 else
|
|
|
137 if (newCap >= 1)
|
|
|
138 resize(newCap);
|
|
|
139 else
|
|
|
140 {
|
|
|
141 char[16] tmp;
|
|
|
142 throw new IllegalArgumentException("Impossible Hash table size:" ~ itoa(tmp, newCap));
|
|
|
143 }
|
|
|
144 }
|
|
|
145
|
|
|
146 /**
|
|
|
147 * Implements tango.util.collection.HashTableParams.thresholdLoadfactor
|
|
|
148 * Time complexity: O(1).
|
|
|
149 * See_Also: tango.util.collection.HashTableParams.thresholdLoadfactor
|
|
|
150 **/
|
|
|
151
|
|
|
152 public final float thresholdLoadFactor()
|
|
|
153 {
|
|
|
154 return loadFactor;
|
|
|
155 }
|
|
|
156
|
|
|
157 /**
|
|
|
158 * Implements tango.util.collection.HashTableParams.thresholdLoadfactor
|
|
|
159 * Time complexity: O(n).
|
|
|
160 * See_Also: tango.util.collection.HashTableParams.thresholdLoadfactor
|
|
|
161 **/
|
|
|
162
|
|
|
163 public final void thresholdLoadFactor(float desired)
|
|
|
164 {
|
|
|
165 if (desired > 0.0)
|
|
|
166 {
|
|
|
167 loadFactor = desired;
|
|
|
168 checkLoadFactor();
|
|
|
169 }
|
|
|
170 else
|
|
|
171 throw new IllegalArgumentException("Invalid Hash table load factor");
|
|
|
172 }
|
|
|
173
|
|
|
174
|
|
|
175
|
|
|
176
|
|
|
177
|
|
|
178 // Collection methods
|
|
|
179
|
|
|
180 /**
|
|
|
181 * Implements tango.util.collection.impl.Collection.Collection.contains
|
|
|
182 * Time complexity: O(1) average; O(n) worst.
|
|
|
183 * See_Also: tango.util.collection.impl.Collection.Collection.contains
|
|
|
184 **/
|
|
|
185 public final bool contains(T element)
|
|
|
186 {
|
|
|
187 if (!isValidArg(element) || count is 0)
|
|
|
188 return false;
|
|
|
189
|
|
|
190 LLCellT p = table[hashOf(element)];
|
|
|
191 if (p !is null)
|
|
|
192 return p.find(element) !is null;
|
|
|
193 else
|
|
|
194 return false;
|
|
|
195 }
|
|
|
196
|
|
|
197 /**
|
|
|
198 * Implements tango.util.collection.impl.Collection.Collection.instances
|
|
|
199 * Time complexity: O(n).
|
|
|
200 * See_Also: tango.util.collection.impl.Collection.Collection.instances
|
|
|
201 **/
|
|
|
202 public final uint instances(T element)
|
|
|
203 {
|
|
|
204 if (contains(element))
|
|
|
205 return 1;
|
|
|
206 else
|
|
|
207 return 0;
|
|
|
208 }
|
|
|
209
|
|
|
210 /**
|
|
|
211 * Implements tango.util.collection.impl.Collection.Collection.elements
|
|
|
212 * Time complexity: O(1).
|
|
|
213 * See_Also: tango.util.collection.impl.Collection.Collection.elements
|
|
|
214 **/
|
|
|
215 public final GuardIterator!(T) elements()
|
|
|
216 {
|
|
|
217 return new CellIterator!(T)(this);
|
|
|
218 }
|
|
|
219
|
|
|
220 /**
|
|
|
221 * Implements tango.util.collection.model.View.View.opApply
|
|
|
222 * Time complexity: O(n).
|
|
|
223 * See_Also: tango.util.collection.model.View.View.opApply
|
|
|
224 **/
|
|
|
225 int opApply (int delegate (inout T value) dg)
|
|
|
226 {
|
|
|
227 auto scope iterator = new CellIterator!(T)(this);
|
|
|
228 return iterator.opApply (dg);
|
|
|
229 }
|
|
|
230
|
|
|
231 // MutableCollection methods
|
|
|
232
|
|
|
233 /**
|
|
|
234 * Implements tango.util.collection.impl.Collection.Collection.clear.
|
|
|
235 * Time complexity: O(1).
|
|
|
236 * See_Also: tango.util.collection.impl.Collection.Collection.clear
|
|
|
237 **/
|
|
|
238 public final void clear()
|
|
|
239 {
|
|
|
240 setCount(0);
|
|
|
241 table = null;
|
|
|
242 }
|
|
|
243
|
|
|
244 /**
|
|
|
245 * Implements tango.util.collection.impl.Collection.Collection.exclude.
|
|
|
246 * Time complexity: O(1) average; O(n) worst.
|
|
|
247 * See_Also: tango.util.collection.impl.Collection.Collection.exclude
|
|
|
248 **/
|
|
|
249 public final void removeAll(T element)
|
|
|
250 {
|
|
|
251 remove(element);
|
|
|
252 }
|
|
|
253
|
|
|
254 public final void remove(T element)
|
|
|
255 {
|
|
|
256 if (!isValidArg(element) || count is 0)
|
|
|
257 return ;
|
|
|
258
|
|
|
259 int h = hashOf(element);
|
|
|
260 LLCellT hd = table[h];
|
|
|
261 LLCellT p = hd;
|
|
|
262 LLCellT trail = p;
|
|
|
263
|
|
|
264 while (p !is null)
|
|
|
265 {
|
|
|
266 LLCellT n = p.next();
|
|
|
267 if (p.element() == (element))
|
|
|
268 {
|
|
|
269 decCount();
|
|
|
270 if (p is table[h])
|
|
|
271 {
|
|
|
272 table[h] = n;
|
|
|
273 trail = n;
|
|
|
274 }
|
|
|
275 else
|
|
|
276 trail.next(n);
|
|
|
277 return ;
|
|
|
278 }
|
|
|
279 else
|
|
|
280 {
|
|
|
281 trail = p;
|
|
|
282 p = n;
|
|
|
283 }
|
|
|
284 }
|
|
|
285 }
|
|
|
286
|
|
|
287 public final void replace(T oldElement, T newElement)
|
|
|
288 {
|
|
|
289
|
|
|
290 if (count is 0 || !isValidArg(oldElement) || oldElement == (newElement))
|
|
|
291 return ;
|
|
|
292
|
|
|
293 if (contains(oldElement))
|
|
|
294 {
|
|
|
295 checkElement(newElement);
|
|
|
296 remove(oldElement);
|
|
|
297 add(newElement);
|
|
|
298 }
|
|
|
299 }
|
|
|
300
|
|
|
301 public final void replaceAll(T oldElement, T newElement)
|
|
|
302 {
|
|
|
303 replace(oldElement, newElement);
|
|
|
304 }
|
|
|
305
|
|
|
306 /**
|
|
|
307 * Implements tango.util.collection.impl.Collection.Collection.take.
|
|
|
308 * Time complexity: O(number of buckets).
|
|
|
309 * See_Also: tango.util.collection.impl.Collection.Collection.take
|
|
|
310 **/
|
|
|
311 public final T take()
|
|
|
312 {
|
|
|
313 if (count !is 0)
|
|
|
314 {
|
|
|
315 for (int i = 0; i < table.length; ++i)
|
|
|
316 {
|
|
|
317 if (table[i] !is null)
|
|
|
318 {
|
|
|
319 decCount();
|
|
|
320 auto v = table[i].element();
|
|
|
321 table[i] = table[i].next();
|
|
|
322 return v;
|
|
|
323 }
|
|
|
324 }
|
|
|
325 }
|
|
|
326
|
|
|
327 checkIndex(0);
|
|
|
328 return T.init; // not reached
|
|
|
329 }
|
|
|
330
|
|
|
331
|
|
|
332 // MutableSet methods
|
|
|
333
|
|
|
334 /**
|
|
|
335 * Implements tango.util.collection.impl.SetCollection.SetCollection.add.
|
|
|
336 * Time complexity: O(1) average; O(n) worst.
|
|
|
337 * See_Also: tango.util.collection.impl.SetCollection.SetCollection.add
|
|
|
338 **/
|
|
|
339 public final void add(T element)
|
|
|
340 {
|
|
|
341 checkElement(element);
|
|
|
342
|
|
|
343 if (table is null)
|
|
|
344 resize(defaultInitialBuckets);
|
|
|
345
|
|
|
346 int h = hashOf(element);
|
|
|
347 LLCellT hd = table[h];
|
|
|
348 if (hd !is null && hd.find(element) !is null)
|
|
|
349 return ;
|
|
|
350
|
|
|
351 LLCellT n = new LLCellT(element, hd);
|
|
|
352 table[h] = n;
|
|
|
353 incCount();
|
|
|
354
|
|
|
355 if (hd !is null)
|
|
|
356 checkLoadFactor(); // only check if bin was nonempty
|
|
|
357 }
|
|
|
358
|
|
|
359
|
|
|
360
|
|
|
361 // Helper methods
|
|
|
362
|
|
|
363 /**
|
|
|
364 * Check to see if we are past load factor threshold. If so, resize
|
|
|
365 * so that we are at half of the desired threshold.
|
|
|
366 * Also while at it, check to see if we are empty so can just
|
|
|
367 * unlink table.
|
|
|
368 **/
|
|
|
369 protected final void checkLoadFactor()
|
|
|
370 {
|
|
|
371 if (table is null)
|
|
|
372 {
|
|
|
373 if (count !is 0)
|
|
|
374 resize(defaultInitialBuckets);
|
|
|
375 }
|
|
|
376 else
|
|
|
377 {
|
|
|
378 float fc = cast(float) (count);
|
|
|
379 float ft = table.length;
|
|
|
380 if (fc / ft > loadFactor)
|
|
|
381 {
|
|
|
382 int newCap = 2 * cast(int)(fc / loadFactor) + 1;
|
|
|
383 resize(newCap);
|
|
|
384 }
|
|
|
385 }
|
|
|
386 }
|
|
|
387
|
|
|
388 /**
|
|
|
389 * Mask off and remainder the hashCode for element
|
|
|
390 * so it can be used as table index
|
|
|
391 **/
|
|
|
392
|
|
|
393 protected final int hashOf(T element)
|
|
|
394 {
|
|
|
395 return (typeid(T).getHash(&element) & 0x7FFFFFFF) % table.length;
|
|
|
396 }
|
|
|
397
|
|
|
398
|
|
|
399 /**
|
|
|
400 * resize table to new capacity, rehashing all elements
|
|
|
401 **/
|
|
|
402 protected final void resize(int newCap)
|
|
|
403 {
|
|
|
404 LLCellT newtab[] = new LLCellT[newCap];
|
|
|
405
|
|
|
406 if (table !is null)
|
|
|
407 {
|
|
|
408 for (int i = 0; i < table.length; ++i)
|
|
|
409 {
|
|
|
410 LLCellT p = table[i];
|
|
|
411 while (p !is null)
|
|
|
412 {
|
|
|
413 LLCellT n = p.next();
|
|
|
414 int h = (p.elementHash() & 0x7FFFFFFF) % newCap;
|
|
|
415 p.next(newtab[h]);
|
|
|
416 newtab[h] = p;
|
|
|
417 p = n;
|
|
|
418 }
|
|
|
419 }
|
|
|
420 }
|
|
|
421
|
|
|
422 table = newtab;
|
|
|
423 incVersion();
|
|
|
424 }
|
|
|
425
|
|
|
426 /+
|
|
|
427 private final void readObject(java.io.ObjectInputStream stream)
|
|
|
428
|
|
|
429 {
|
|
|
430 int len = stream.readInt();
|
|
|
431
|
|
|
432 if (len > 0)
|
|
|
433 table = new LLCellT[len];
|
|
|
434 else
|
|
|
435 table = null;
|
|
|
436
|
|
|
437 loadFactor = stream.readFloat();
|
|
|
438 int count = stream.readInt();
|
|
|
439
|
|
|
440 while (count-- > 0)
|
|
|
441 {
|
|
|
442 T element = stream.readObject();
|
|
|
443 int h = hashOf(element);
|
|
|
444 LLCellT hd = table[h];
|
|
|
445 LLCellT n = new LLCellT(element, hd);
|
|
|
446 table[h] = n;
|
|
|
447 }
|
|
|
448 }
|
|
|
449
|
|
|
450 private final void writeObject(java.io.ObjectOutputStream stream)
|
|
|
451 {
|
|
|
452 int len;
|
|
|
453
|
|
|
454 if (table !is null)
|
|
|
455 len = table.length;
|
|
|
456 else
|
|
|
457 len = 0;
|
|
|
458
|
|
|
459 stream.writeInt(len);
|
|
|
460 stream.writeFloat(loadFactor);
|
|
|
461 stream.writeInt(count);
|
|
|
462
|
|
|
463 if (len > 0)
|
|
|
464 {
|
|
|
465 Iterator e = elements();
|
|
|
466 while (e.more())
|
|
|
467 stream.writeObject(e.value());
|
|
|
468 }
|
|
|
469 }
|
|
|
470
|
|
|
471 +/
|
|
|
472
|
|
|
473 // ImplementationCheckable methods
|
|
|
474
|
|
|
475 /**
|
|
|
476 * Implements tango.util.collection.model.View.View.checkImplementation.
|
|
|
477 * See_Also: tango.util.collection.model.View.View.checkImplementation
|
|
|
478 **/
|
|
|
479 public override void checkImplementation()
|
|
|
480 {
|
|
|
481 super.checkImplementation();
|
|
|
482
|
|
|
483 assert(!(table is null && count !is 0));
|
|
|
484 assert((table is null || table.length > 0));
|
|
|
485 assert(loadFactor > 0.0f);
|
|
|
486
|
|
|
487 if (table !is null)
|
|
|
488 {
|
|
|
489 int c = 0;
|
|
|
490 for (int i = 0; i < table.length; ++i)
|
|
|
491 {
|
|
|
492 for (LLCellT p = table[i]; p !is null; p = p.next())
|
|
|
493 {
|
|
|
494 ++c;
|
|
|
495 assert(allows(p.element()));
|
|
|
496 assert(contains(p.element()));
|
|
|
497 assert(instances(p.element()) is 1);
|
|
|
498 assert(hashOf(p.element()) is i);
|
|
|
499 }
|
|
|
500 }
|
|
|
501 assert(c is count);
|
|
|
502 }
|
|
|
503 }
|
|
|
504
|
|
|
505
|
|
|
506
|
|
|
507 /***********************************************************************
|
|
|
508
|
|
|
509 opApply() has migrated here to mitigate the virtual call
|
|
|
510 on method get()
|
|
|
511
|
|
|
512 ************************************************************************/
|
|
|
513
|
|
|
514 private static class CellIterator(T) : AbstractIterator!(T)
|
|
|
515 {
|
|
|
516 private int row;
|
|
|
517 private LLCellT cell;
|
|
|
518 private LLCellT[] table;
|
|
|
519
|
|
|
520 public this (HashSet set)
|
|
|
521 {
|
|
|
522 super (set);
|
|
|
523 table = set.table;
|
|
|
524 }
|
|
|
525
|
|
|
526 public final T get()
|
|
|
527 {
|
|
|
528 decRemaining();
|
|
|
529
|
|
|
530 while (cell is null)
|
|
|
531 cell = table [row++];
|
|
|
532
|
|
|
533 auto v = cell.element();
|
|
|
534 cell = cell.next();
|
|
|
535 return v;
|
|
|
536 }
|
|
|
537
|
|
|
538 int opApply (int delegate (inout T value) dg)
|
|
|
539 {
|
|
|
540 int result;
|
|
|
541
|
|
|
542 for (auto i=remaining(); i--;)
|
|
|
543 {
|
|
|
544 auto value = get();
|
|
|
545 if ((result = dg(value)) != 0)
|
|
|
546 break;
|
|
|
547 }
|
|
|
548 return result;
|
|
|
549 }
|
|
|
550 }
|
|
|
551 }
|
|
|
552
|
|
|
553
|
|
|
554
|
|
|
555 debug (Test)
|
|
|
556 {
|
|
|
557 import tango.io.Console;
|
|
|
558
|
|
|
559 void main()
|
|
|
560 {
|
|
|
561 auto set = new HashSet!(char[]);
|
|
|
562 set.add ("foo");
|
|
|
563 set.add ("bar");
|
|
|
564 set.add ("wumpus");
|
|
|
565
|
|
|
566 foreach (value; set.elements) {}
|
|
|
567
|
|
|
568 auto elements = set.elements();
|
|
|
569 while (elements.more)
|
|
|
570 auto v = elements.get();
|
|
|
571
|
|
|
572 set.checkImplementation();
|
|
|
573
|
|
|
574 foreach (value; set)
|
|
|
575 Cout (value).newline;
|
|
|
576 }
|
|
|
577 }
|
