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.ByteCollection;
022: import bak.pcj.ByteIterator;
023: import bak.pcj.hash.ByteHashFunction;
024: import bak.pcj.hash.DefaultByteHashFunction;
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 byte 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 ByteOpenHashSet
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 ByteOpenHashSet extends AbstractByteSet implements
046: ByteSet, 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 ByteHashFunction 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 byte[] 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 ByteOpenHashSet(ByteHashFunction 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 byte[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 ByteOpenHashSet(int capacity, int growthPolicy,
165: double growthFactor, int growthChunk, double loadFactor) {
166: this (DefaultByteHashFunction.INSTANCE, capacity, growthPolicy,
167: 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 ByteOpenHashSet() {
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 ByteOpenHashSet(ByteCollection 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 ByteOpenHashSet(byte[] 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 ByteOpenHashSet(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 ByteOpenHashSet(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 ByteOpenHashSet(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 ByteOpenHashSet(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 ByteOpenHashSet(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 ByteOpenHashSet(ByteHashFunction 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 ByteOpenHashSet(ByteHashFunction 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 ByteOpenHashSet(ByteHashFunction keyhash, double loadFactor) {
379: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
380: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
381: }
382:
383: /**
384: * Creates a new hash set with a specified capacity and
385: * load factor, and a relative growth factor of 1.0.
386: *
387: * @param keyhash
388: * the hash function to use when hashing keys.
389: *
390: * @param capacity
391: * the initial capacity of the set.
392: *
393: * @param loadFactor
394: * the load factor of the set.
395: *
396: * @throws IllegalArgumentException
397: * if <tt>capacity</tt> is negative;
398: * if <tt>loadFactor</tt> is not positive.
399: *
400: * @throws NullPointerException
401: * if <tt>keyhash</tt> is <tt>null</tt>.
402: */
403: public ByteOpenHashSet(ByteHashFunction keyhash, int capacity,
404: double loadFactor) {
405: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
406: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
407: }
408:
409: /**
410: * Creates a new hash set with a specified capacity,
411: * load factor, and relative growth factor.
412: *
413: * <p>The set capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
414: * This strategy is good for avoiding many capacity increases, but
415: * the amount of wasted memory is approximately the size of the set.
416: *
417: * @param keyhash
418: * the hash function to use when hashing keys.
419: *
420: * @param capacity
421: * the initial capacity of the set.
422: *
423: * @param loadFactor
424: * the load factor of the set.
425: *
426: * @param growthFactor
427: * the relative amount with which to increase the
428: * the capacity when a capacity increase is needed.
429: *
430: * @throws IllegalArgumentException
431: * if <tt>capacity</tt> is negative;
432: * if <tt>loadFactor</tt> is not positive;
433: * if <tt>growthFactor</tt> is not positive.
434: *
435: * @throws NullPointerException
436: * if <tt>keyhash</tt> is <tt>null</tt>.
437: */
438: public ByteOpenHashSet(ByteHashFunction keyhash, int capacity,
439: double loadFactor, double growthFactor) {
440: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
441: DEFAULT_GROWTH_CHUNK, loadFactor);
442: }
443:
444: /**
445: * Creates a new hash set with a specified capacity,
446: * load factor, and absolute growth factor.
447: *
448: * @param keyhash
449: * the hash function to use when hashing keys.
450: *
451: * <p>The set capacity increases to <tt>capacity()+growthChunk</tt>.
452: * This strategy is good for avoiding wasting memory. However, an
453: * overhead is potentially introduced by frequent capacity increases.
454: *
455: * @param capacity
456: * the initial capacity of the set.
457: *
458: * @param loadFactor
459: * the load factor of the set.
460: *
461: * @param growthChunk
462: * the absolute amount with which to increase the
463: * the capacity when a capacity increase is needed.
464: *
465: * @throws IllegalArgumentException
466: * if <tt>capacity</tt> is negative;
467: * if <tt>loadFactor</tt> is not positive;
468: * if <tt>growthChunk</tt> is not positive.
469: *
470: * @throws NullPointerException
471: * if <tt>keyhash</tt> is <tt>null</tt>.
472: */
473: public ByteOpenHashSet(ByteHashFunction keyhash, int capacity,
474: double loadFactor, int growthChunk) {
475: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
476: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
477: }
478:
479: // ---------------------------------------------------------------
480: // Hash table management
481: // ---------------------------------------------------------------
482:
483: private void ensureCapacity(int elements) {
484: if (elements >= expandAt) {
485: int newcapacity;
486: if (growthPolicy == GROWTH_POLICY_RELATIVE)
487: newcapacity = (int) (data.length * (1.0 + growthFactor));
488: else
489: newcapacity = data.length + growthChunk;
490: if (newcapacity * loadFactor < elements)
491: newcapacity = (int) Math
492: .round(((double) elements / loadFactor));
493: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
494: expandAt = (int) Math.round(loadFactor * newcapacity);
495:
496: byte[] newdata = new byte[newcapacity];
497: byte[] newstates = new byte[newcapacity];
498:
499: used = 0;
500: // re-hash
501: for (int i = 0; i < data.length; i++) {
502: if (states[i] == OCCUPIED) {
503: used++;
504: byte v = data[i];
505: // first hash
506: int h = Math.abs(keyhash.hash(v));
507: int n = h % newcapacity;
508: if (newstates[n] == OCCUPIED) {
509: // second hash
510: int c = 1 + (h % (newcapacity - 2));
511: for (;;) {
512: n -= c;
513: if (n < 0)
514: n += newcapacity;
515: if (newstates[n] == EMPTY)
516: break;
517: }
518: }
519: newstates[n] = OCCUPIED;
520: newdata[n] = v;
521: }
522: }
523:
524: data = newdata;
525: states = newstates;
526: }
527: }
528:
529: // ---------------------------------------------------------------
530: // Operations not supported by abstract implementation
531: // ---------------------------------------------------------------
532:
533: public boolean add(byte v) {
534: ensureCapacity(used + 1);
535:
536: // first hash
537: int h = Math.abs(keyhash.hash(v));
538: int i = h % data.length;
539: if (states[i] == OCCUPIED) {
540: if (data[i] == v)
541: return false;
542: // second hash
543: int c = 1 + (h % (data.length - 2));
544: for (;;) {
545: i -= c;
546: if (i < 0)
547: i += data.length;
548: // Removed entries are re-used
549: if (states[i] == EMPTY || states[i] == REMOVED)
550: break;
551: if (states[i] == OCCUPIED && data[i] == v)
552: return false;
553: }
554: }
555: if (states[i] == EMPTY)
556: used++;
557: states[i] = OCCUPIED;
558: data[i] = v;
559: size++;
560: return true;
561: }
562:
563: public ByteIterator iterator() {
564: return new ByteIterator() {
565: int nextEntry = nextEntry(0);
566: int lastEntry = -1;
567:
568: int nextEntry(int index) {
569: while (index < data.length && states[index] != OCCUPIED)
570: index++;
571: return index;
572: }
573:
574: public boolean hasNext() {
575: return nextEntry < data.length;
576: }
577:
578: public byte next() {
579: if (!hasNext())
580: Exceptions.endOfIterator();
581: lastEntry = nextEntry;
582: nextEntry = nextEntry(nextEntry + 1);
583: return data[lastEntry];
584: }
585:
586: public void remove() {
587: if (lastEntry == -1)
588: Exceptions.noElementToRemove();
589: states[lastEntry] = REMOVED;
590: size--;
591: lastEntry = -1;
592: }
593: };
594: }
595:
596: public void trimToSize() {
597: }
598:
599: /**
600: * Returns a clone of this hash set.
601: *
602: * @return a clone of this hash set.
603: *
604: * @since 1.1
605: */
606: public Object clone() {
607: try {
608: ByteOpenHashSet c = (ByteOpenHashSet) super .clone();
609: c.data = new byte[data.length];
610: System.arraycopy(data, 0, c.data, 0, data.length);
611: c.states = new byte[data.length];
612: System.arraycopy(states, 0, c.states, 0, states.length);
613: return c;
614: } catch (CloneNotSupportedException e) {
615: Exceptions.cloning();
616: throw new RuntimeException();
617: }
618: }
619:
620: // ---------------------------------------------------------------
621: // Operations overwritten for efficiency
622: // ---------------------------------------------------------------
623:
624: public int size() {
625: return size;
626: }
627:
628: public void clear() {
629: size = 0;
630: used = 0;
631: java.util.Arrays.fill(states, EMPTY);
632: }
633:
634: public boolean contains(byte 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: return true;
640:
641: // second hash
642: int c = 1 + (h % (data.length - 2));
643: for (;;) {
644: i -= c;
645: if (i < 0)
646: i += data.length;
647: if (states[i] == EMPTY)
648: return false;
649: if (states[i] == OCCUPIED && data[i] == v)
650: return true;
651: }
652: }
653: return false;
654: }
655:
656: public int hashCode() {
657: int h = 0;
658: for (int i = 0; i < data.length; i++)
659: if (states[i] == OCCUPIED)
660: h += data[i];
661: return h;
662: }
663:
664: public boolean remove(byte v) {
665: int h = Math.abs(keyhash.hash(v));
666: int i = h % data.length;
667: if (states[i] != EMPTY) {
668: if (states[i] == OCCUPIED && data[i] == v) {
669: states[i] = REMOVED;
670: size--;
671: return true;
672: }
673: // second hash
674: int c = 1 + (h % (data.length - 2));
675: for (;;) {
676: i -= c;
677: if (i < 0)
678: i += data.length;
679: if (states[i] == EMPTY)
680: return false;
681: if (states[i] == OCCUPIED && data[i] == v) {
682: states[i] = REMOVED;
683: size--;
684: return true;
685: }
686: }
687: }
688: return false;
689: }
690:
691: public byte[] toArray(byte[] a) {
692: if (a == null || a.length < size)
693: a = new byte[size];
694:
695: int p = 0;
696: for (int i = 0; i < data.length; i++)
697: if (states[i] == OCCUPIED)
698: a[p++] = data[i];
699: return a;
700: }
701:
702: // ---------------------------------------------------------------
703: // Serialization
704: // ---------------------------------------------------------------
705:
706: /**
707: * @serialData Default fields; the capacity of the
708: * set (<tt>int</tt>); the set's elements
709: * (<tt>byte</tt>).
710: *
711: * @since 1.1
712: */
713: private void writeObject(ObjectOutputStream s) throws IOException {
714: s.defaultWriteObject();
715: s.writeInt(data.length);
716: ByteIterator i = iterator();
717: while (i.hasNext()) {
718: byte x = i.next();
719: s.writeByte(x);
720: }
721: }
722:
723: /**
724: * @since 1.1
725: */
726: private void readObject(ObjectInputStream s) throws IOException,
727: ClassNotFoundException {
728: s.defaultReadObject();
729: data = new byte[s.readInt()];
730: states = new byte[data.length];
731: used = size;
732: for (int n = 0; n < size; n++) {
733: byte v = s.readByte();
734:
735: // first hash
736: int h = Math.abs(keyhash.hash(v));
737: int i = h % data.length;
738: if (states[i] == OCCUPIED) {
739: // second hash
740: int c = 1 + (h % (data.length - 2));
741: for (;;) {
742: i -= c;
743: if (i < 0)
744: i += data.length;
745: if (states[i] == EMPTY)
746: break;
747: }
748: }
749: states[i] = OCCUPIED;
750: data[i] = v;
751: }
752: }
753:
754: }
|