KickJava   Java API By Example, From Geeks To Geeks.

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


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.ShortCollection;
22 import bak.pcj.ShortIterator;
23 import bak.pcj.hash.ShortHashFunction;
24 import bak.pcj.hash.DefaultShortHashFunction;
25 import bak.pcj.util.Exceptions;
26
27 import java.io.Serializable JavaDoc;
28 import java.io.IOException JavaDoc;
29 import java.io.ObjectInputStream JavaDoc;
30 import java.io.ObjectOutputStream JavaDoc;
31
32 /**
33  * This class represents chained hash table based sets of short 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 chained
36  * hash table where the keys are stored directly as entries.
37  *
38  * @see ShortOpenHashSet
39  * @see java.util.HashSet
40  *
41  * @author S&oslash;ren Bak
42  * @version 1.4 21-08-2003 20:05
43  * @since 1.0
44  */

45 public class ShortChainedHashSet extends AbstractShortSet implements ShortSet, Cloneable JavaDoc, Serializable JavaDoc {
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 ShortHashFunction keyhash;
77
78     /**
79      * The size of this set.
80      * @serial
81      */

82     private int size;
83
84     /** The hash table backing up this set. Contains set values directly. */
85     private transient short[][] data;
86
87     /**
88      * The growth policy of this set (0 is relative growth, 1 is absolute growth).
89      * @serial
90      */

91     private int growthPolicy;
92
93     /**
94      * The growth factor of this set, if the growth policy is
95      * relative.
96      * @serial
97      */

98     private double growthFactor;
99
100     /**
101      * The growth chunk size of this set, if the growth policy is
102      * absolute.
103      * @serial
104      */

105     private int growthChunk;
106
107     /**
108      * The load factor of this set.
109      * @serial
110      */

111     private double loadFactor;
112
113     /**
114      * The next size at which to expand the data[].
115      * @serial
116      */

117     private int expandAt;
118
119     private ShortChainedHashSet(ShortHashFunction keyhash, int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
120         if (keyhash == null)
121             Exceptions.nullArgument("hash function");
122         if (capacity < 0)
123             Exceptions.negativeArgument("capacity", String.valueOf(capacity));
124         if (growthFactor < 0.0)
125             Exceptions.negativeArgument("growthFactor", String.valueOf(growthFactor));
126         if (growthChunk < 0)
127             Exceptions.negativeArgument("growthChunk", String.valueOf(growthChunk));
128         if (loadFactor <= 0.0)
129             Exceptions.negativeOrZeroArgument("loadFactor", String.valueOf(loadFactor));
130         data = new short[capacity][];
131         size = 0;
132         expandAt = (int)Math.round(loadFactor*capacity);
133         this.growthPolicy = growthPolicy;
134         this.growthFactor = growthFactor;
135         this.growthChunk = growthChunk;
136         this.loadFactor = loadFactor;
137         this.keyhash = keyhash;
138     }
139
140     private ShortChainedHashSet(int capacity, int growthPolicy, double growthFactor, int growthChunk, double loadFactor) {
141         this(DefaultShortHashFunction.INSTANCE, capacity, growthPolicy, growthFactor, growthChunk, loadFactor);
142     }
143
144     /**
145      * Creates a new hash set with capacity 11, a relative
146      * growth factor of 1.0, and a load factor of 75%.
147      */

148     public ShortChainedHashSet() {
149         this(DEFAULT_CAPACITY);
150     }
151
152     /**
153      * Creates a new hash set with the same elements as a specified
154      * collection.
155      *
156      * @param c
157      * the collection whose elements to add to the new
158      * set.
159      *
160      * @throws NullPointerException
161      * if <tt>c</tt> is <tt>null</tt>.
162      */

163     public ShortChainedHashSet(ShortCollection c) {
164         this();
165         addAll(c);
166     }
167
168     /**
169      * Creates a new hash set with the same elements as the specified
170      * array.
171      *
172      * @param a
173      * the array whose elements to add to the new
174      * set.
175      *
176      * @throws NullPointerException
177      * if <tt>a</tt> is <tt>null</tt>.
178      *
179      * @since 1.1
180      */

181     public ShortChainedHashSet(short[] a) {
182         this();
183         for (int i = 0; i < a.length; i++)
184             add(a[i]);
185     }
186
187     /**
188      * Creates a new hash set with a specified capacity, a relative
189      * growth factor of 1.0, and a load factor of 75%.
190      *
191      * @param capacity
192      * the initial capacity of the set.
193      *
194      * @throws IllegalArgumentException
195      * if <tt>capacity</tt> is negative.
196      */

197     public ShortChainedHashSet(int capacity) {
198         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
199     }
200
201     /**
202      * Creates a new hash set with a capacity of 11, a relative
203      * growth factor of 1.0, and a specified load factor.
204      *
205      * @param loadFactor
206      * the load factor of the set.
207      *
208      * @throws IllegalArgumentException
209      * if <tt>loadFactor</tt> is negative.
210      */

211     public ShortChainedHashSet(double loadFactor) {
212         this(DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
213     }
214
215     /**
216      * Creates a new hash set with a specified capacity and
217      * load factor, and a relative growth factor of 1.0.
218      *
219      * @param capacity
220      * the initial capacity of the set.
221      *
222      * @param loadFactor
223      * the load factor of the set.
224      *
225      * @throws IllegalArgumentException
226      * if <tt>capacity</tt> is negative;
227      * if <tt>loadFactor</tt> is not positive.
228      */

229     public ShortChainedHashSet(int capacity, double loadFactor) {
230         this(capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
231     }
232
233     /**
234      * Creates a new hash set with a specified capacity,
235      * load factor, and relative growth factor.
236      *
237      * <p>The set capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
238      * This strategy is good for avoiding many capacity increases, but
239      * the amount of wasted memory is approximately the size of the set.
240      *
241      * @param capacity
242      * the initial capacity of the set.
243      *
244      * @param loadFactor
245      * the load factor of the set.
246      *
247      * @param growthFactor
248      * the relative amount with which to increase the
249      * the capacity when a capacity increase is needed.
250      *
251      * @throws IllegalArgumentException
252      * if <tt>capacity</tt> is negative;
253      * if <tt>loadFactor</tt> is not positive;
254      * if <tt>growthFactor</tt> is not positive.
255      */

256     public ShortChainedHashSet(int capacity, double loadFactor, double growthFactor) {
257         this(capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
258     }
259
260     /**
261      * Creates a new hash set with a specified capacity,
262      * load factor, and absolute growth factor.
263      *
264      * <p>The set capacity increases to <tt>capacity()+growthChunk</tt>.
265      * This strategy is good for avoiding wasting memory. However, an
266      * overhead is potentially introduced by frequent capacity increases.
267      *
268      * @param capacity
269      * the initial capacity of the set.
270      *
271      * @param loadFactor
272      * the load factor of the set.
273      *
274      * @param growthChunk
275      * the absolute amount with which to increase the
276      * the capacity when a capacity increase is needed.
277      *
278      * @throws IllegalArgumentException
279      * if <tt>capacity</tt> is negative;
280      * if <tt>loadFactor</tt> is not positive;
281      * if <tt>growthChunk</tt> is not positive.
282      */

283     public ShortChainedHashSet(int capacity, double loadFactor, int growthChunk) {
284         this(capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
285     }
286
287     // ---------------------------------------------------------------
288
// Constructors with hash function argument
289
// ---------------------------------------------------------------
290

291     /**
292      * Creates a new hash set with capacity 11, a relative
293      * growth factor of 1.0, and a load factor of 75%.
294      *
295      * @param keyhash
296      * the hash function to use when hashing keys.
297      *
298      * @throws NullPointerException
299      * if <tt>keyhash</tt> is <tt>null</tt>.
300      */

301     public ShortChainedHashSet(ShortHashFunction keyhash) {
302         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
303     }
304
305     /**
306      * Creates a new hash set with a specified capacity, a relative
307      * growth factor of 1.0, and a load factor of 75%.
308      *
309      * @param keyhash
310      * the hash function to use when hashing keys.
311      *
312      * @param capacity
313      * the initial capacity of the set.
314      *
315      * @throws IllegalArgumentException
316      * if <tt>capacity</tt> is negative.
317      *
318      * @throws NullPointerException
319      * if <tt>keyhash</tt> is <tt>null</tt>.
320      */

321     public ShortChainedHashSet(ShortHashFunction keyhash, int capacity) {
322         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
323     }
324
325     /**
326      * Creates a new hash set with a capacity of 11, a relative
327      * growth factor of 1.0, and a specified load factor.
328      *
329      * @param keyhash
330      * the hash function to use when hashing keys.
331      *
332      * @param loadFactor
333      * the load factor of the set.
334      *
335      * @throws IllegalArgumentException
336      * if <tt>loadFactor</tt> is negative.
337      *
338      * @throws NullPointerException
339      * if <tt>keyhash</tt> is <tt>null</tt>.
340      */

341     public ShortChainedHashSet(ShortHashFunction keyhash, double loadFactor) {
342         this(keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
343     }
344
345     /**
346      * Creates a new hash set with a specified capacity and
347      * load factor, and a relative growth factor of 1.0.
348      *
349      * @param keyhash
350      * the hash function to use when hashing keys.
351      *
352      * @param capacity
353      * the initial capacity of the set.
354      *
355      * @param loadFactor
356      * the load factor of the set.
357      *
358      * @throws IllegalArgumentException
359      * if <tt>capacity</tt> is negative;
360      * if <tt>loadFactor</tt> is not positive.
361      *
362      * @throws NullPointerException
363      * if <tt>keyhash</tt> is <tt>null</tt>.
364      */

365     public ShortChainedHashSet(ShortHashFunction keyhash, int capacity, double loadFactor) {
366         this(keyhash, capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
367     }
368
369     /**
370      * Creates a new hash set with a specified capacity,
371      * load factor, and relative growth factor.
372      *
373      * <p>The set capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
374      * This strategy is good for avoiding many capacity increases, but
375      * the amount of wasted memory is approximately the size of the set.
376      *
377      * @param keyhash
378      * the hash function to use when hashing keys.
379      *
380      * @param capacity
381      * the initial capacity of the set.
382      *
383      * @param loadFactor
384      * the load factor of the set.
385      *
386      * @param growthFactor
387      * the relative amount with which to increase the
388      * the capacity when a capacity increase is needed.
389      *
390      * @throws IllegalArgumentException
391      * if <tt>capacity</tt> is negative;
392      * if <tt>loadFactor</tt> is not positive;
393      * if <tt>growthFactor</tt> is not positive.
394      *
395      * @throws NullPointerException
396      * if <tt>keyhash</tt> is <tt>null</tt>.
397      */

398     public ShortChainedHashSet(ShortHashFunction keyhash, int capacity, double loadFactor, double growthFactor) {
399         this(keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor, DEFAULT_GROWTH_CHUNK, loadFactor);
400     }
401
402     /**
403      * Creates a new hash set with a specified capacity,
404      * load factor, and absolute growth factor.
405      *
406      * <p>The set capacity increases to <tt>capacity()+growthChunk</tt>.
407      * This strategy is good for avoiding wasting memory. However, an
408      * overhead is potentially introduced by frequent capacity increases.
409      *
410      * @param keyhash
411      * the hash function to use when hashing keys.
412      *
413      * @param capacity
414      * the initial capacity of the set.
415      *
416      * @param loadFactor
417      * the load factor of the set.
418      *
419      * @param growthChunk
420      * the absolute amount with which to increase the
421      * the capacity when a capacity increase is needed.
422      *
423      * @throws IllegalArgumentException
424      * if <tt>capacity</tt> is negative;
425      * if <tt>loadFactor</tt> is not positive;
426      * if <tt>growthChunk</tt> is not positive.
427      *
428      * @throws NullPointerException
429      * if <tt>keyhash</tt> is <tt>null</tt>.
430      */

431     public ShortChainedHashSet(ShortHashFunction keyhash, int capacity, double loadFactor, int growthChunk) {
432         this(keyhash, capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
433     }
434
435     // ---------------------------------------------------------------
436
// Hash table management
437
// ---------------------------------------------------------------
438

439     private void ensureCapacity(int elements) {
440         if (elements >= expandAt) {
441             int newcapacity;
442             if (growthPolicy == GROWTH_POLICY_RELATIVE)
443                 newcapacity = (int)(data.length * (1.0 + growthFactor));
444             else
445                 newcapacity = data.length + growthChunk;
446             if (newcapacity*loadFactor < elements)
447                 newcapacity = (int)Math.round(((double)elements/loadFactor));
448             newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
449             expandAt = (int)Math.round(loadFactor*newcapacity);
450
451             short[][] newdata = new short[newcapacity][];
452
453             // re-hash
454
for (int i = 0; i < data.length; i++) {
455                 short[] list = data[i];
456                 if (list != null) {
457                     for (int n = 0; n < list.length; n++) {
458                         short v = list[n];
459                         int index = Math.abs(keyhash.hash(v)) % newdata.length;
460                         newdata[index] = addList(newdata[index], v);
461                     }
462                 }
463             }
464
465             data = newdata;
466         }
467     }
468
469     private short[] addList(short[] list, short v) {
470         if (list == null)
471             return new short[]{v};
472         short[] newlist = new short[list.length+1];
473         for (int i = 0; i < list.length; i++)
474             newlist[i] = list[i];
475         newlist[list.length] = v;
476         return newlist;
477     }
478
479     private short[] removeList(short[] list, int index) {
480         if (list.length == 1)
481             return null;
482         short[] newlist = new short[list.length-1];
483         int n = 0;
484         for (int i = 0; i < index; i++)
485             newlist[n++] = list[i];
486         for (int i = index+1; i < list.length; i++)
487             newlist[n++] = list[i];
488         return newlist;
489     }
490
491     private int searchList(short[] list, short v) {
492         for (int i = 0; i < list.length; i++)
493             if (list[i] == v)
494                 return i;
495         return -1;
496     }
497
498     // ---------------------------------------------------------------
499
// Operations not supported by abstract implementation
500
// ---------------------------------------------------------------
501

502     public boolean add(short v) {
503         ensureCapacity(size+1);
504
505         int index = Math.abs(keyhash.hash(v)) % data.length;
506         short[] list = data[index];
507         if (list == null) {
508             data[index] = new short[]{v};
509             size++;
510             return true;
511         }
512         for (int i = 0; i < list.length; i++)
513             if (list[i] == v)
514                 return false;
515         data[index] = addList(data[index], v);
516         size++;
517         return true;
518     }
519
520     public ShortIterator iterator() {
521         return new ShortIterator() {
522             int currList = nextList(0);
523             int currShort = 0;
524             int lastList = -1;
525             int lastShort;
526             short lastValue;
527
528             int nextList(int index) {
529                 while (index < data.length && data[index] == null)
530                     index++;
531                 return index < data.length ? index : -1;
532             }
533
534             public boolean hasNext() {
535                 return currList != -1;
536             }
537
538             public short next() {
539                 if (currList == -1)
540                     Exceptions.endOfIterator();
541                 lastList = currList;
542                 lastShort = currShort;
543                 lastValue = data[currList][currShort];
544                 if (currShort == data[currList].length-1) {
545                     currList = nextList(currList+1);
546                     currShort = 0;
547                 } else {
548                     currShort++;
549                 }
550                 return lastValue;
551             }
552
553             public void remove() {
554                 if (lastList == -1)
555                     Exceptions.noElementToRemove();
556                 if (currList == lastList)
557                     currShort--;
558                 data[lastList] = removeList(data[lastList], lastShort);
559                 size--;
560                 lastList = -1;
561             }
562         };
563     }
564
565     public void trimToSize()
566     { }
567
568     /**
569      * Returns a clone of this hash set.
570      *
571      * @return a clone of this hash set.
572      *
573      * @since 1.1
574      */

575     public Object JavaDoc clone() {
576         try {
577             ShortChainedHashSet c = (ShortChainedHashSet)super.clone();
578             c.data = new short[data.length][];
579             // Cloning each array is not necessary since they are immutable
580
System.arraycopy(data, 0, c.data, 0, data.length);
581             return c;
582         } catch (CloneNotSupportedException JavaDoc e) {
583             Exceptions.cloning(); throw new RuntimeException JavaDoc();
584         }
585     }
586
587     // ---------------------------------------------------------------
588
// Operations overwritten for efficiency
589
// ---------------------------------------------------------------
590

591     public int size()
592     { return size; }
593
594     public void clear()
595     { size = 0; }
596
597     public boolean contains(short v) {
598         short[] list = data[Math.abs(keyhash.hash(v)) % data.length];
599         if (list == null)
600             return false;
601         return searchList(list, v) != -1;
602     }
603
604     public int hashCode() {
605         int h = 0;
606         for (int i = 0; i < data.length; i++) {
607             short[] list = data[i];
608             if (list != null) {
609                 for (int n = 0; n < list.length; n++)
610                     h += list[n];
611             }
612         }
613         return h;
614     }
615
616     public boolean remove(short v) {
617         int index = Math.abs(keyhash.hash(v)) % data.length;
618         short[] list = data[index];
619         if (list != null) {
620             int lindex = searchList(list, v);
621             if (lindex == -1)
622                 return false;
623             data[index] = removeList(list, lindex);
624             size--;
625             return true;
626         }
627         return false;
628     }
629
630     public short[] toArray(short[] a) {
631         if (a == null || a.length < size)
632             a = new short[size];
633
634         int p = 0;
635         for (int i = 0; i < data.length; i++) {
636             short[] list = data[i];
637             if (list != null) {
638                 for (int n = 0; n < list.length; n++)
639                     a[p++] = list[n];
640             }
641         }
642         return a;
643     }
644
645     // ---------------------------------------------------------------
646
// Serialization
647
// ---------------------------------------------------------------
648

649     /**
650      * @serialData Default fields; the capacity of the
651      * set (<tt>int</tt>); the set's elements
652      * (<tt>short</tt>).
653      *
654      * @since 1.1
655      */

656     private void writeObject(ObjectOutputStream JavaDoc s) throws IOException JavaDoc {
657         s.defaultWriteObject();
658         s.writeInt(data.length);
659         ShortIterator i = iterator();
660         while (i.hasNext()) {
661             short x = i.next();
662             s.writeShort(x);
663         }
664     }
665
666     /**
667      * @since 1.1
668      */

669     private void readObject(ObjectInputStream JavaDoc s) throws IOException JavaDoc, ClassNotFoundException JavaDoc {
670         s.defaultReadObject();
671         data = new short[s.readInt()][];
672         for (int i = 0; i < size; i++) {
673             short v = s.readShort();
674             int index = Math.abs(keyhash.hash(v)) % data.length;
675             short[] list = data[index];
676             if (list == null)
677                 data[index] = new short[]{v};
678             else
679                 data[index] = addList(data[index], v);
680         }
681     }
682
683 }
684
Popular Tags