Java > Open Source Codes > bak > pcj > set > FloatOpenHashSet


1 /*
2  * Primitive Collections for Java.
3  * Copyright (C) 2002 Søren Bak
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18  */
19 package bak.pcj.set;
20
21 import bak.pcj.FloatCollection;
22 import bak.pcj.FloatIterator;
23 import bak.pcj.hash.FloatHashFunction;
24 import bak.pcj.hash.DefaultFloatHashFunction;
25 import bak.pcj.util.Exceptions;
26
27 import java.io.Serializable ;
28 import java.io.IOException ;
29 import java.io.ObjectInputStream ;
30 import java.io.ObjectOutputStream ;
31
32 /**
33  * This class represents open addressing hash table based sets of float values.
34  * Unlike the Java Collections <tt>HashSet</tt> instances of this class
35  * are not backed up by a map. It is implemented using a simple open addressing
36  * hash table where the keys are stored directly as entries.
37  *
38  * @see FloatOpenHashSet
39  * @see java.util.HashSet
40  *
41  * @author S&oslash;ren Bak
42  * @version 1.3 22-08-2003 20:19
43  * @since 1.0
44  */
45 public class FloatOpenHashSet extends AbstractFloatSet implements FloatSet, Cloneable , Serializable {
46
47     /** Constant indicating relative growth policy. */
48     private static final int GROWTH_POLICY_RELATIVE = 0;
49
50     /** Constant indicating absolute growth policy. */
51     private static final int GROWTH_POLICY_ABSOLUTE = 1;
52
53     /**
54      * The default growth policy of this set.
55      * @see #GROWTH_POLICY_RELATIVE
56      * @see #GROWTH_POLICY_ABSOLUTE
57      */
58     private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
59
60     /** The default factor with which to increase the capacity of this set. */
61     public static final double DEFAULT_GROWTH_FACTOR = 1.0;
62
63     /** The default chunk size with which to increase the capacity of this set. */
64     public static final int DEFAULT_GROWTH_CHUNK = 10;
65
66     /** The default capacity of this set. */
67     public static final int DEFAULT_CAPACITY = 11;
68
69     /** The default load factor of this set. */
70     public static final double DEFAULT_LOAD_FACTOR = 0.75;
71
72     /**
73      * The hash function used to hash keys in this set.
74      * @serial
75      */
76     private FloatHashFunction keyhash;
77
78     /**
79      * The size of this set.
80      * @serial
81      */
82     private int size;
83
84     /**
85      * The hash table backing up this set. Contains set values directly.
86      * Due to the use of a secondary hash function, the length of this
87      * array must be a prime.
88      */
89     private transient float[] data;
90
91     /** The states of each cell in the keys[]. */
92     private transient byte[] states;
93
94     private static final byte EMPTY = 0;
95     private static final byte OCCUPIED = 1;
96     private static final byte REMOVED = 2;
97
98     /** The number of entries in use (removed or occupied). */
99     private transient int used;
100
101     /**
102      * The growth policy of this set (0 is relative growth, 1 is absolute growth).
103      * @serial
104      */
105     private int growthPolicy;
106
107     /**
108      * The growth factor of this set, if the growth policy is
109      * relative.
110      * @serial
111      */
112     private double growthFactor;
113
114     /**
115      * The growth chunk size of this set, if the growth policy is
116      * absolute.
117      * @serial
118      */
119     private int growthChunk;
120
121     /**
122      * The load factor of this set.
123      * @serial
124      */
125     private double loadFactor;
126
127     /**
128      * The next size at which to expand the keys[].
129      * @serial
130      */
131     private int expandAt;
132
133     private FloatOpenHashSet(FloatHashFunction keyhash, int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
134         if (keyhash == null)
135             Exceptions.nullArgument("hash function");
136         if (capacity < 0)
137             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
138         if (growthFactor <= 0.0)
139             Exceptions.negativeOrZeroArgument("growthFactor", String.valueOf(growthFactor));
140         if (growthChunk <= 0)
141             Exceptions.negativeOrZeroArgument("growthChunk", String.valueOf(growthChunk));
142         if (loadFactor <= 0.0)
143             Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor));
144         this.keyhash = keyhash;
145         capacity = bak.pcj.hash.Primes.nextPrime(capacity);
146         data = new float[capacity];
147         this.states = new byte[capacity];
148         size = 0;
149         expandAt = (int)Math.round(loadFactor*capacity);
150         used = 0;
151         this.growthPolicy = growthPolicy;
152         this.growthFactor = growthFactor;
153         this.growthChunk = growthChunk;
154         this.loadFactor = loadFactor;
155     }
156
157     private FloatOpenHashSet(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
158         this(DefaultFloatHashFunction.INSTANCE, capacity, growthPolicy, growthFactor, growthChunk, loadFactor);
159     }
160
161     /**
162      * Creates a new hash set with capacity 11, a relative
163      * growth factor of 1.0, and a load factor of 75%.
164      */
165     public FloatOpenHashSet() {
166         this(DEFAULT_CAPACITY);
167     }
168
169     /**
170      * Creates a new hash set with the same elements as a specified
171      * collection.
172      *
173      * @param c
174      * the collection whose elements to add to the new
175      * set.
176      *
177      * @throws NullPointerException
178      * if <tt>c</tt> is <tt>null</tt>.
179      */
180     public FloatOpenHashSet(FloatCollection c) {
181         this();
182         addAll(c);
183     }
184
185     /**
186      * Creates a new hash set with the same elements as the specified
187      * array.
188      *
189      * @param a
190      * the array whose elements to add to the new
191      * set.
192      *
193      * @throws NullPointerException
194      * if <tt>a</tt> is <tt>null</tt>.
195      *
196      * @since 1.1
197      */
198     public FloatOpenHashSet(float[] a) {
199         this();
200         for (int i = 0; i < a.length; i++)
201             add(a[i]);
202     }
203
204     /**
205      * Creates a new hash set with a specified capacity, a relative
206      * growth factor of 1.0, and a load factor of 75%.
207      *
208      * @param capacity
209      * the initial capacity of the set.
210      *
211      * @throws IllegalArgumentException
212      * if <tt>capacity</tt> is negative.
213      */
214     public FloatOpenHashSet(int capacity) {
215         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
216     }
217
218     /**
219      * Creates a new hash set with a capacity of 11, a relative
220      * growth factor of 1.0, and a specified load factor.
221      *
222      * @param loadFactor
223      * the load factor of the set.
224      *
225      * @throws IllegalArgumentException
226      * if <tt>loadFactor</tt> is negative or zero.
227      */
228     public FloatOpenHashSet(double loadFactor) {
229         this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
230     }
231
232     /**
233      * Creates a new hash set with a specified capacity and
234      * load factor, and a relative growth factor of 1.0.
235      *
236      * @param capacity
237      * the initial capacity of the set.
238      *
239      * @param loadFactor
240      * the load factor of the set.
241      *
242      * @throws IllegalArgumentException
243      * if <tt>capacity</tt> is negative;
244      * if <tt>loadFactor</tt> is not positive.
245      */
246     public FloatOpenHashSet(int capacity, double loadFactor) {
247         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
248     }
249
250     /**
251      * Creates a new hash set with a specified capacity,
252      * load factor, and relative growth factor.
253      *
254      * <p>The set capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
255      * This strategy is good for avoiding many capacity increases, but
256      * the amount of wasted memory is approximately the size of the set.
257      *
258      * @param capacity
259      * the initial capacity of the set.
260      *
261      * @param loadFactor
262      * the load factor of the set.
263      *
264      * @param growthFactor
265      * the relative amount with which to increase the
266      * the capacity when a capacity increase is needed.
267      *
268      * @throws IllegalArgumentException
269      * if <tt>capacity</tt> is negative;
270      * if <tt>loadFactor</tt> is not positive;
271      * if <tt>growthFactor</tt> is not positive.
272      */
273     public FloatOpenHashSet(int capacity, double loadFactor, double growthFactor) {
274         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
275     }
276
277     /**
278      * Creates a new hash set with a specified capacity,
279      * load factor, and absolute growth factor.
280      *
281      * <p>The set capacity increases to <tt>capacity()+growthChunk</tt>.
282      * This strategy is good for avoiding wasting memory. However, an
283      * overhead is potentially introduced by frequent capacity increases.
284      *
285      * @param capacity
286      * the initial capacity of the set.
287      *
288      * @param loadFactor
289      * the load factor of the set.
290      *
291      * @param growthChunk
292      * the absolute amount with which to increase the
293      * the capacity when a capacity increase is needed.
294      *
295      * @throws IllegalArgumentException
296      * if <tt>capacity</tt> is negative;
297      * if <tt>loadFactor</tt> is not positive;
298      * if <tt>growthChunk</tt> is not positive.
299      */
300     public FloatOpenHashSet(int capacity, double loadFactor, int growthChunk) {
301         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
302     }
303
304     // ---------------------------------------------------------------
305 // Constructors with hash function argument
306 // ---------------------------------------------------------------
307
308     /**
309      * Creates a new hash set with capacity 11, a relative
310      * growth factor of 1.0, and a load factor of 75%.
311      *
312      * @param keyhash
313      * the hash function to use when hashing keys.
314      *
315      * @throws NullPointerException
316      * if <tt>keyhash</tt> is <tt>null</tt>.
317      */
318     public FloatOpenHashSet(FloatHashFunction keyhash) {
319         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
320     }
321
322     /**
323      * Creates a new hash set with a specified capacity, a relative
324      * growth factor of 1.0, and a load factor of 75%.
325      *
326      * @param keyhash
327      * the hash function to use when hashing keys.
328      *
329      * @param capacity
330      * the initial capacity of the set.
331      *
332      * @throws IllegalArgumentException
333      * if <tt>capacity</tt> is negative.
334      *
335      * @throws NullPointerException
336      * if <tt>keyhash</tt> is <tt>null</tt>.
337      */
338     public FloatOpenHashSet(FloatHashFunction keyhash, int capacity) {
339         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
340     }
341
342     /**
343      * Creates a new hash set with a capacity of 11, a relative
344      * growth factor of 1.0, and a specified load factor.
345      *
346      * @param keyhash
347      * the hash function to use when hashing keys.
348      *
349      * @param loadFactor
350      * the load factor of the set.
351      *
352      * @throws IllegalArgumentException
353      * if <tt>loadFactor</tt> is negative or zero.
354      *
355      * @throws NullPointerException
356      * if <tt>keyhash</tt> is <tt>null</tt>.
357      */
358     public FloatOpenHashSet(FloatHashFunction keyhash, double loadFactor) {
359         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
360     }
361
362     /**
363      * Creates a new hash set with a specified capacity and
364      * load factor, and a relative growth factor of 1.0.
365      *
366      * @param keyhash
367      * the hash function to use when hashing keys.
368      *
369      * @param capacity
370      * the initial capacity of the set.
371      *
372      * @param loadFactor
373      * the load factor of the set.
374      *
375      * @throws IllegalArgumentException
376      * if <tt>capacity</tt> is negative;
377      * if <tt>loadFactor</tt> is not positive.
378      *
379      * @throws NullPointerException
380      * if <tt>keyhash</tt> is <tt>null</tt>.
381      */
382     public FloatOpenHashSet(FloatHashFunction keyhash, int capacity, double loadFactor) {
383         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
384     }
385
386     /**
387      * Creates a new hash set with a specified capacity,
388      * load factor, and relative growth factor.
389      *
390      * <p>The set capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
391      * This strategy is good for avoiding many capacity increases, but
392      * the amount of wasted memory is approximately the size of the set.
393      *
394      * @param keyhash
395      * the hash function to use when hashing keys.
396      *
397      * @param capacity
398      * the initial capacity of the set.
399      *
400      * @param loadFactor
401      * the load factor of the set.
402      *
403      * @param growthFactor
404      * the relative amount with which to increase the
405      * the capacity when a capacity increase is needed.
406      *
407      * @throws IllegalArgumentException
408      * if <tt>capacity</tt> is negative;
409      * if <tt>loadFactor</tt> is not positive;
410      * if <tt>growthFactor</tt> is not positive.
411      *
412      * @throws NullPointerException
413      * if <tt>keyhash</tt> is <tt>null</tt>.
414      */
415     public FloatOpenHashSet(FloatHashFunction keyhash, int capacity, double loadFactor, double growthFactor) {
416         this(keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
417     }
418
419     /**
420      * Creates a new hash set with a specified capacity,
421      * load factor, and absolute growth factor.
422      *
423      * @param keyhash
424      * the hash function to use when hashing keys.
425      *
426      * <p>The set capacity increases to <tt>capacity()+growthChunk</tt>.
427      * This strategy is good for avoiding wasting memory. However, an
428      * overhead is potentially introduced by frequent capacity increases.
429      *
430      * @param capacity
431      * the initial capacity of the set.
432      *
433      * @param loadFactor
434      * the load factor of the set.
435      *
436      * @param growthChunk
437      * the absolute amount with which to increase the
438      * the capacity when a capacity increase is needed.
439      *
440      * @throws IllegalArgumentException
441      * if <tt>capacity</tt> is negative;
442      * if <tt>loadFactor</tt> is not positive;
443      * if <tt>growthChunk</tt> is not positive.
444      *
445      * @throws NullPointerException
446      * if <tt>keyhash</tt> is <tt>null</tt>.
447      */
448     public FloatOpenHashSet(FloatHashFunction keyhash, int capacity, double loadFactor, int growthChunk) {
449         this(keyhash, capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
450     }
451
452     // ---------------------------------------------------------------
453 // Hash table management
454 // ---------------------------------------------------------------
455
456     private void ensureCapacity(int elements) {
457         if (elements >= expandAt) {
458             int newcapacity;
459             if (growthPolicy == GROWTH_POLICY_RELATIVE)
460                 newcapacity = (int)(data.length * (1.0 + growthFactor));
461             else
462                 newcapacity = data.length + growthChunk;
463             if (newcapacity*loadFactor < elements)
464                 newcapacity = (int)Math.round(((double)elements/loadFactor));
465             newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
466             expandAt = (int)Math.round(loadFactor*newcapacity);
467
468             float[] newdata = new float[newcapacity];
469             byte[] newstates = new byte[newcapacity];
470
471             used = 0;
472             // re-hash
473 for (int i = 0; i < data.length; i++) {
474                 if (states[i] == OCCUPIED) {
475                     used++;
476                     float v = data[i];
477                     // first hash
478 int h = Math.abs(keyhash.hash(v));
479                     int n = h % newcapacity;
480                     if (newstates[n] == OCCUPIED) {
481                         // second hash
482 int c = 1 + (h % (newcapacity - 2));
483                         for (;;) {
484                             n -= c;
485                             if (n < 0)
486                                 n += newcapacity;
487                             if (newstates[n] == EMPTY)
488                                 break;
489                         }
490                     }
491                     newstates[n] = OCCUPIED;
492                     newdata[n] = v;
493                 }
494             }
495
496             data = newdata;
497             states = newstates;
498         }
499     }
500
501     // ---------------------------------------------------------------
502 // Operations not supported by abstract implementation
503 // ---------------------------------------------------------------
504
505     public boolean add(float v) {
506         ensureCapacity(used+1);
507
508         // first hash
509 int h = Math.abs(keyhash.hash(v));
510         int i = h % data.length;
511         if (states[i] == OCCUPIED) {
512             if (data[i] == v)
513                 return false;
514             // second hash
515 int c = 1 + (h % (data.length - 2));
516             for (;;) {
517                 i -= c;
518                 if (i < 0)
519                     i += data.length;
520                 // Removed entries are re-used
521 if (states[i] == EMPTY || states[i] == REMOVED)
522                     break;
523                 if (states[i] == OCCUPIED && data[i] == v)
524                     return false;
525             }
526         }
527         if (states[i] == EMPTY)
528             used++;
529         states[i] = OCCUPIED;
530         data[i] = v;
531         size++;
532         return true;
533     }
534
535     public FloatIterator iterator() {
536         return new FloatIterator() {
537             int nextEntry = nextEntry(0);
538             int lastEntry = -1;
539
540             int nextEntry(int index) {
541                 while (index < data.length && states[index] != OCCUPIED)
542                     index++;
543                 return index;
544             }
545
546             public boolean hasNext() {
547                 return nextEntry < data.length;
548             }
549
550             public float next() {
551                 if (!hasNext())
552                     Exceptions.endOfIterator();
553                 lastEntry = nextEntry;
554                 nextEntry = nextEntry(nextEntry+1);
555                 return data[lastEntry];
556             }
557
558             public void remove() {
559                 if (lastEntry == -1)
560                     Exceptions.noElementToRemove();
561                 states[lastEntry] = REMOVED;
562                 size--;
563                 lastEntry = -1;
564             }
565         };
566     }
567
568     public void trimToSize()
569     { }
570
571     /**
572      * Returns a clone of this hash set.
573      *
574      * @return a clone of this hash set.
575      *
576      * @since 1.1
577      */
578     public Object clone() {
579         try {
580             FloatOpenHashSet c = (FloatOpenHashSet)super.clone();
581             c.data = new float[data.length];
582             System.arraycopy(data, 0, c.data, 0, data.length);
583             c.states = new byte[data.length];
584             System.arraycopy(states, 0, c.states, 0, states.length);
585             return c;
586         } catch (CloneNotSupportedException e) {
587             Exceptions.cloning(); throw new RuntimeException ();
588         }
589     }
590
591     // ---------------------------------------------------------------
592 // Operations overwritten for efficiency
593 // ---------------------------------------------------------------
594
595     public int size()
596     { return size; }
597
598     public void clear() {
599         size = 0;
600         used = 0;
601         java.util.Arrays.fill(states, EMPTY);
602     }
603
604     public boolean contains(float v) {
605         int h = Math.abs(keyhash.hash(v));
606         int i = h % data.length;
607         if (states[i] != EMPTY) {
608             if (states[i] == OCCUPIED && data[i] == v)
609                 return true;
610
611             // second hash
612 int c = 1 + (h % (data.length - 2));
613             for (;;) {
614                 i -= c;
615                 if (i < 0)
616                     i += data.length;
617                 if (states[i] == EMPTY)
618                     return false;
619                 if (states[i] == OCCUPIED && data[i] == v)
620                     return true;
621             }
622         }
623         return false;
624     }
625
626     public int hashCode() {
627         int h = 0;
628         for (int i = 0; i < data.length; i++)
629             if (states[i] == OCCUPIED)
630                 h += data[i];
631         return h;
632     }
633
634     public boolean remove(float v) {
635         int h = Math.abs(keyhash.hash(v));
636         int i = h % data.length;
637         if (states[i] != EMPTY) {
638             if (states[i] == OCCUPIED && data[i] == v) {
639                 states[i] = REMOVED;
640                 size--;
641                 return true;
642             }
643             // second hash
644 int c = 1 + (h % (data.length - 2));
645             for (;;) {
646                 i -= c;
647                 if (i < 0)
648                     i += data.length;
649                 if (states[i] == EMPTY)
650                     return false;
651                 if (states[i] == OCCUPIED && data[i] == v) {
652                     states[i] = REMOVED;
653                     size--;
654                     return true;
655                 }
656             }
657         }
658         return false;
659     }
660
661     public float[] toArray(float[] a) {
662         if (a == null || a.length < size)
663             a = new float[size];
664
665         int p = 0;
666         for (int i = 0; i < data.length; i++)
667             if (states[i] == OCCUPIED)
668                 a[p++] = data[i];
669         return a;
670     }
671
672     // ---------------------------------------------------------------
673 // Serialization
674 // ---------------------------------------------------------------
675
676     /**
677      * @serialData Default fields; the capacity of the
678      * set (<tt>int</tt>); the set's elements
679      * (<tt>float</tt>).
680      *
681      * @since 1.1
682      */
683     private void writeObject(ObjectOutputStream s) throws IOException {
684         s.defaultWriteObject();
685         s.writeInt(data.length);
686         FloatIterator i = iterator();
687         while (i.hasNext()) {
688             float x = i.next();
689             s.writeFloat(x);
690         }
691     }
692
693     /**
694      * @since 1.1
695      */
696     private void readObject(ObjectInputStream s) throws IOException , ClassNotFoundException {
697         s.defaultReadObject();
698         data = new float[s.readInt()];
699         states = new byte[data.length];
700         used = size;
701         for (int n = 0; n < size; n++) {
702             float v = s.readFloat();
703
704             // first hash
705 int h = Math.abs(keyhash.hash(v));
706             int i = h % data.length;
707             if (states[i] == OCCUPIED) {
708                 // second hash
709 int c = 1 + (h % (data.length - 2));
710                 for (;;) {
711                     i -= c;
712                     if (i < 0)
713                         i += data.length;
714                     if (states[i] == EMPTY)
715                         break;
716                 }
717             }
718             states[i] = OCCUPIED;
719             data[i] = v;
720         }
721     }
722
723 }
724

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags