Mercurial > projects > ldc

comparison tango/tango/util/collection/HashSet.d @ 132:1700239cab2e trunk

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[svn r136] MAJOR UNSTABLE UPDATE!!! Initial commit after moving to Tango instead of Phobos. Lots of bugfixes... This build is not suitable for most things.
author lindquist
date Fri, 11 Jan 2008 17:57:40 +0100
parents
children
comparison
equal deleted inserted replaced
131:5825d48b27d1 132:1700239cab2e
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 }