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