001: /*
002: * Primitive Collections for Java.
003: * Copyright (C) 2002, 2003 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 com.uwyn.rife.pcj.map;
020:
021: import java.io.IOException;
022: import java.io.ObjectInputStream;
023: import java.io.ObjectOutputStream;
024: import java.io.Serializable;
025: import java.util.AbstractCollection;
026: import java.util.Collection;
027: import java.util.Iterator;
028:
029: import com.uwyn.rife.pcj.IntIterator;
030: import com.uwyn.rife.pcj.hash.DefaultIntHashFunction;
031: import com.uwyn.rife.pcj.hash.IntHashFunction;
032: import com.uwyn.rife.pcj.set.AbstractIntSet;
033: import com.uwyn.rife.pcj.set.IntSet;
034: import com.uwyn.rife.pcj.util.Exceptions;
035:
036: /**
037: * This class represents open addressing hash table based maps from
038: * int values to objects.
039: *
040: * @see java.util.Map
041: *
042: * @author Søren Bak
043: * @version 1.3 21-08-2003 19:45
044: * @since 1.0
045: */
046: public class IntKeyOpenHashMap<E> extends AbstractIntKeyMap<E>
047: implements IntKeyMap<E>, Cloneable, Serializable {
048:
049: private static final long serialVersionUID = -2735632961345735697L;
050:
051: /** Constant indicating relative growth policy. */
052: private static final int GROWTH_POLICY_RELATIVE = 0;
053:
054: /** Constant indicating absolute growth policy. */
055: private static final int GROWTH_POLICY_ABSOLUTE = 1;
056:
057: /**
058: * The default growth policy of this map.
059: * @see #GROWTH_POLICY_RELATIVE
060: * @see #GROWTH_POLICY_ABSOLUTE
061: */
062: private static final int DEFAULT_GROWTH_POLICY = GROWTH_POLICY_RELATIVE;
063:
064: /** The default factor with which to increase the capacity of this map. */
065: public static final double DEFAULT_GROWTH_FACTOR = 1.0;
066:
067: /** The default chunk size with which to increase the capacity of this map. */
068: public static final int DEFAULT_GROWTH_CHUNK = 10;
069:
070: /** The default capacity of this map. */
071: public static final int DEFAULT_CAPACITY = 11;
072:
073: /** The default load factor of this map. */
074: public static final double DEFAULT_LOAD_FACTOR = 0.75;
075:
076: /**
077: * The hash function used to hash keys in this map.
078: * @serial
079: */
080: private IntHashFunction keyhash;
081:
082: /**
083: * The size of this map.
084: * @serial
085: */
086: private int size;
087:
088: /**
089: * The keys of this map. Contains key values directly.
090: * Due to the use of a secondary hash function, the length of this
091: * array must be a prime.
092: */
093: private transient int[] keys;
094:
095: /**
096: * The values of this map. Contains values directly.
097: * Due to the use of a secondary hash function, the length of this
098: * array must be a prime.
099: */
100: private transient E[] values;
101:
102: /** The states of each cell in the keys[] and values[]. */
103: private transient byte[] states;
104:
105: private static final byte EMPTY = 0;
106: private static final byte OCCUPIED = 1;
107: private static final byte REMOVED = 2;
108:
109: /** The number of entries in use (removed or occupied). */
110: private transient int used;
111:
112: /**
113: * The growth policy of this map (0 is relative growth, 1 is absolute growth).
114: * @serial
115: */
116: private int growthPolicy;
117:
118: /**
119: * The growth factor of this map, if the growth policy is
120: * relative.
121: * @serial
122: */
123: private double growthFactor;
124:
125: /**
126: * The growth chunk size of this map, if the growth policy is
127: * absolute.
128: * @serial
129: */
130: private int growthChunk;
131:
132: /**
133: * The load factor of this map.
134: * @serial
135: */
136: private double loadFactor;
137:
138: /**
139: * The next size at which to expand the data[].
140: * @serial
141: */
142: private int expandAt;
143:
144: /** A set view of the keys of this map. */
145: private transient IntSet ckeys;
146:
147: /** A collection view of the values of this map. */
148: private transient Collection cvalues;
149:
150: private IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
151: int growthPolicy, double growthFactor, int growthChunk,
152: double loadFactor) {
153: if (keyhash == null)
154: Exceptions.nullArgument("hash function");
155: if (capacity < 0)
156: Exceptions.negativeArgument("capacity", String
157: .valueOf(capacity));
158: if (growthFactor <= 0.0)
159: Exceptions.negativeOrZeroArgument("growthFactor", String
160: .valueOf(growthFactor));
161: if (growthChunk <= 0)
162: Exceptions.negativeOrZeroArgument("growthChunk", String
163: .valueOf(growthChunk));
164: if (loadFactor <= 0.0)
165: Exceptions.negativeOrZeroArgument("loadFactor", String
166: .valueOf(loadFactor));
167: this .keyhash = keyhash;
168: capacity = com.uwyn.rife.pcj.hash.Primes.nextPrime(capacity);
169: keys = new int[capacity];
170: values = (E[]) new Object[capacity];
171: this .states = new byte[capacity];
172: size = 0;
173: expandAt = (int) Math.round(loadFactor * capacity);
174: this .used = 0;
175: this .growthPolicy = growthPolicy;
176: this .growthFactor = growthFactor;
177: this .growthChunk = growthChunk;
178: this .loadFactor = loadFactor;
179: }
180:
181: private IntKeyOpenHashMap(int capacity, int growthPolicy,
182: double growthFactor, int growthChunk, double loadFactor) {
183: this (DefaultIntHashFunction.INSTANCE, capacity, growthPolicy,
184: growthFactor, growthChunk, loadFactor);
185: }
186:
187: /**
188: * Creates a new hash map with capacity 11, a relative
189: * growth factor of 1.0, and a load factor of 75%.
190: */
191: public IntKeyOpenHashMap() {
192: this (DEFAULT_CAPACITY);
193: }
194:
195: /**
196: * Creates a new hash map with the same mappings as a specified map.
197: *
198: * @param map
199: * the map whose mappings to put into the new map.
200: *
201: * @throws NullPointerException
202: * if <tt>map</tt> is <tt>null</tt>.
203: */
204: public IntKeyOpenHashMap(IntKeyMap map) {
205: this ();
206: putAll(map);
207: }
208:
209: /**
210: * Creates a new hash map with a specified capacity, a relative
211: * growth factor of 1.0, and a load factor of 75%.
212: *
213: * @param capacity
214: * the initial capacity of the map.
215: *
216: * @throws IllegalArgumentException
217: * if <tt>capacity</tt> is negative.
218: */
219: public IntKeyOpenHashMap(int capacity) {
220: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
221: DEFAULT_GROWTH_CHUNK, DEFAULT_LOAD_FACTOR);
222: }
223:
224: /**
225: * Creates a new hash map with a capacity of 11, a relative
226: * growth factor of 1.0, and a specified load factor.
227: *
228: * @param loadFactor
229: * the load factor of the map.
230: *
231: * @throws IllegalArgumentException
232: * if <tt>capacity</tt> is negative;
233: * if <tt>loadFactor</tt> is not positive.
234: */
235: public IntKeyOpenHashMap(double loadFactor) {
236: this (DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
237: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
238: }
239:
240: /**
241: * Creates a new hash map with a specified capacity and
242: * load factor, and a relative growth factor of 1.0.
243: *
244: * @param capacity
245: * the initial capacity of the map.
246: *
247: * @param loadFactor
248: * the load factor of the map.
249: *
250: * @throws IllegalArgumentException
251: * if <tt>capacity</tt> is negative;
252: * if <tt>loadFactor</tt> is not positive.
253: */
254: public IntKeyOpenHashMap(int capacity, double loadFactor) {
255: this (capacity, DEFAULT_GROWTH_POLICY, DEFAULT_GROWTH_FACTOR,
256: DEFAULT_GROWTH_CHUNK, loadFactor);
257: }
258:
259: /**
260: * Creates a new hash map with a specified capacity,
261: * load factor, and relative growth factor.
262: *
263: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
264: * This strategy is good for avoiding many capacity increases, but
265: * the amount of wasted memory is approximately the size of the map.
266: *
267: * @param capacity
268: * the initial capacity of the map.
269: *
270: * @param loadFactor
271: * the load factor of the map.
272: *
273: * @param growthFactor
274: * the relative amount with which to increase the
275: * the capacity when a capacity increase is needed.
276: *
277: * @throws IllegalArgumentException
278: * if <tt>capacity</tt> is negative;
279: * if <tt>loadFactor</tt> is not positive;
280: * if <tt>growthFactor</tt> is not positive.
281: */
282: public IntKeyOpenHashMap(int capacity, double loadFactor,
283: double growthFactor) {
284: this (capacity, GROWTH_POLICY_RELATIVE, growthFactor,
285: DEFAULT_GROWTH_CHUNK, loadFactor);
286: }
287:
288: /**
289: * Creates a new hash map with a specified capacity,
290: * load factor, and absolute growth factor.
291: *
292: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
293: * This strategy is good for avoiding wasting memory. However, an
294: * overhead is potentially introduced by frequent capacity increases.
295: *
296: * @param capacity
297: * the initial capacity of the map.
298: *
299: * @param loadFactor
300: * the load factor of the map.
301: *
302: * @param growthChunk
303: * the absolute amount with which to increase the
304: * the capacity when a capacity increase is needed.
305: *
306: * @throws IllegalArgumentException
307: * if <tt>capacity</tt> is negative;
308: * if <tt>loadFactor</tt> is not positive;
309: * if <tt>growthChunk</tt> is not positive.
310: */
311: public IntKeyOpenHashMap(int capacity, double loadFactor,
312: int growthChunk) {
313: this (capacity, GROWTH_POLICY_ABSOLUTE, DEFAULT_GROWTH_FACTOR,
314: growthChunk, loadFactor);
315: }
316:
317: // ---------------------------------------------------------------
318: // Constructors with hash function argument
319: // ---------------------------------------------------------------
320:
321: /**
322: * Creates a new hash map with capacity 11, a relative
323: * growth factor of 1.0, and a load factor of 75%.
324: *
325: * @param keyhash
326: * the hash function to use when hashing keys.
327: *
328: * @throws NullPointerException
329: * if <tt>keyhash</tt> is <tt>null</tt>.
330: */
331: public IntKeyOpenHashMap(IntHashFunction keyhash) {
332: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
333: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
334: DEFAULT_LOAD_FACTOR);
335: }
336:
337: /**
338: * Creates a new hash map with a specified capacity, a relative
339: * growth factor of 1.0, and a load factor of 75%.
340: *
341: * @param keyhash
342: * the hash function to use when hashing keys.
343: *
344: * @param capacity
345: * the initial capacity of the map.
346: *
347: * @throws IllegalArgumentException
348: * if <tt>capacity</tt> is negative.
349: *
350: * @throws NullPointerException
351: * if <tt>keyhash</tt> is <tt>null</tt>.
352: */
353: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity) {
354: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
355: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
356: DEFAULT_LOAD_FACTOR);
357: }
358:
359: /**
360: * Creates a new hash map with a capacity of 11, a relative
361: * growth factor of 1.0, and a specified load factor.
362: *
363: * @param keyhash
364: * the hash function to use when hashing keys.
365: *
366: * @param loadFactor
367: * the load factor of the map.
368: *
369: * @throws IllegalArgumentException
370: * if <tt>capacity</tt> is negative;
371: * if <tt>loadFactor</tt> is not positive.
372: *
373: * @throws NullPointerException
374: * if <tt>keyhash</tt> is <tt>null</tt>.
375: */
376: public IntKeyOpenHashMap(IntHashFunction keyhash, double loadFactor) {
377: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
378: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
379: }
380:
381: /**
382: * Creates a new hash map with a specified capacity and
383: * load factor, and a relative growth factor of 1.0.
384: *
385: * @param keyhash
386: * the hash function to use when hashing keys.
387: *
388: * @param capacity
389: * the initial capacity of the map.
390: *
391: * @param loadFactor
392: * the load factor of the map.
393: *
394: * @throws IllegalArgumentException
395: * if <tt>capacity</tt> is negative;
396: * if <tt>loadFactor</tt> is not positive.
397: *
398: * @throws NullPointerException
399: * if <tt>keyhash</tt> is <tt>null</tt>.
400: */
401: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
402: double loadFactor) {
403: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
404: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
405: }
406:
407: /**
408: * Creates a new hash map with a specified capacity,
409: * load factor, and relative growth factor.
410: *
411: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
412: * This strategy is good for avoiding many capacity increases, but
413: * the amount of wasted memory is approximately the size of the map.
414: *
415: * @param keyhash
416: * the hash function to use when hashing keys.
417: *
418: * @param capacity
419: * the initial capacity of the map.
420: *
421: * @param loadFactor
422: * the load factor of the map.
423: *
424: * @param growthFactor
425: * the relative amount with which to increase the
426: * the capacity when a capacity increase is needed.
427: *
428: * @throws IllegalArgumentException
429: * if <tt>capacity</tt> is negative;
430: * if <tt>loadFactor</tt> is not positive;
431: * if <tt>growthFactor</tt> is not positive.
432: *
433: * @throws NullPointerException
434: * if <tt>keyhash</tt> is <tt>null</tt>.
435: */
436: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
437: double loadFactor, double growthFactor) {
438: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
439: DEFAULT_GROWTH_CHUNK, loadFactor);
440: }
441:
442: /**
443: * Creates a new hash map with a specified capacity,
444: * load factor, and absolute growth factor.
445: *
446: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
447: * This strategy is good for avoiding wasting memory. However, an
448: * overhead is potentially introduced by frequent capacity increases.
449: *
450: * @param keyhash
451: * the hash function to use when hashing keys.
452: *
453: * @param capacity
454: * the initial capacity of the map.
455: *
456: * @param loadFactor
457: * the load factor of the map.
458: *
459: * @param growthChunk
460: * the absolute amount with which to increase the
461: * the capacity when a capacity increase is needed.
462: *
463: * @throws IllegalArgumentException
464: * if <tt>capacity</tt> is negative;
465: * if <tt>loadFactor</tt> is not positive;
466: * if <tt>growthChunk</tt> is not positive.
467: *
468: * @throws NullPointerException
469: * if <tt>keyhash</tt> is <tt>null</tt>.
470: */
471: public IntKeyOpenHashMap(IntHashFunction keyhash, int capacity,
472: double loadFactor, int growthChunk) {
473: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
474: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
475: }
476:
477: // ---------------------------------------------------------------
478: // Hash table management
479: // ---------------------------------------------------------------
480:
481: private void ensureCapacity(int elements) {
482: if (elements >= expandAt) {
483: int newcapacity;
484: if (growthPolicy == GROWTH_POLICY_RELATIVE)
485: newcapacity = (int) (keys.length * (1.0 + growthFactor));
486: else
487: newcapacity = keys.length + growthChunk;
488: if (newcapacity * loadFactor < elements)
489: newcapacity = (int) Math
490: .round(((double) elements / loadFactor));
491: newcapacity = com.uwyn.rife.pcj.hash.Primes
492: .nextPrime(newcapacity);
493: expandAt = (int) Math.round(loadFactor * newcapacity);
494:
495: int[] newkeys = new int[newcapacity];
496: E[] newvalues = (E[]) new Object[newcapacity];
497: byte[] newstates = new byte[newcapacity];
498:
499: used = 0;
500: // re-hash
501: for (int i = 0; i < keys.length; i++) {
502: if (states[i] == OCCUPIED) {
503: used++;
504: int k = keys[i];
505: E v = values[i];
506: // first hash
507: int h = Math.abs(keyhash.hash(k));
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: newvalues[n] = v;
522: newkeys[n] = k;
523: }
524: }
525:
526: keys = newkeys;
527: values = newvalues;
528: states = newstates;
529: }
530: }
531:
532: // ---------------------------------------------------------------
533: // Operations not supported by abstract implementation
534: // ---------------------------------------------------------------
535:
536: public IntSet keySet() {
537: if (ckeys == null)
538: ckeys = new KeySet();
539: return ckeys;
540: }
541:
542: public E put(int key, E value) {
543: // first hash
544: int h = Math.abs(keyhash.hash(key));
545: int i = h % keys.length;
546: if (states[i] == OCCUPIED) {
547: if (keys[i] == key) {
548: E oldValue = values[i];
549: values[i] = value;
550: return oldValue;
551: }
552: // second hash
553: int c = 1 + (h % (keys.length - 2));
554: for (;;) {
555: i -= c;
556: if (i < 0)
557: i += keys.length;
558: // Empty entries are re-used
559: if (states[i] == EMPTY || states[i] == REMOVED)
560: break;
561: if (states[i] == OCCUPIED && keys[i] == key) {
562: E oldValue = values[i];
563: values[i] = value;
564: return oldValue;
565: }
566: }
567: }
568:
569: if (states[i] == EMPTY)
570: used++;
571: states[i] = OCCUPIED;
572: keys[i] = key;
573: values[i] = value;
574: size++;
575: ensureCapacity(used);
576: return null;
577: }
578:
579: public Collection<E> values() {
580: if (cvalues == null)
581: cvalues = new ValueCollection();
582: return cvalues;
583: }
584:
585: /**
586: * Returns a clone of this hash map.
587: *
588: * @return a clone of this hash map.
589: *
590: * @since 1.1
591: */
592: public IntKeyOpenHashMap clone() {
593: try {
594: IntKeyOpenHashMap c = (IntKeyOpenHashMap) super .clone();
595: c.keys = new int[keys.length];
596: System.arraycopy(keys, 0, c.keys, 0, keys.length);
597: c.values = new Object[values.length];
598: System.arraycopy(values, 0, c.values, 0, values.length);
599: c.states = new byte[states.length];
600: System.arraycopy(states, 0, c.states, 0, states.length);
601: // The views should not refer to this map's views
602: c.cvalues = null;
603: c.ckeys = null;
604: return c;
605: } catch (CloneNotSupportedException e) {
606: Exceptions.cloning();
607: return null;
608: }
609: }
610:
611: public IntKeyMapIterator<E> entries() {
612: return new IntKeyMapIterator<E>() {
613: int nextEntry = nextEntry(0);
614: int lastEntry = -1;
615:
616: int nextEntry(int index) {
617: while (index < keys.length && states[index] != OCCUPIED)
618: index++;
619: return index;
620: }
621:
622: public boolean hasNext() {
623: return nextEntry < keys.length;
624: }
625:
626: public void next() {
627: if (!hasNext())
628: Exceptions.endOfIterator();
629: lastEntry = nextEntry;
630: nextEntry = nextEntry(nextEntry + 1);
631: }
632:
633: public void remove() {
634: if (lastEntry == -1)
635: Exceptions.noElementToRemove();
636: states[lastEntry] = REMOVED;
637: values[lastEntry] = null; // GC
638: size--;
639: lastEntry = -1;
640: }
641:
642: public int getKey() {
643: if (lastEntry == -1)
644: Exceptions.noElementToGet();
645: return keys[lastEntry];
646: }
647:
648: public E getValue() {
649: if (lastEntry == -1)
650: Exceptions.noElementToGet();
651: return values[lastEntry];
652: }
653: };
654: }
655:
656: private class KeySet extends AbstractIntSet {
657:
658: public void clear() {
659: IntKeyOpenHashMap.this .clear();
660: }
661:
662: public boolean contains(int v) {
663: return containsKey(v);
664: }
665:
666: public IntIterator iterator() {
667: return new IntIterator() {
668: int nextEntry = nextEntry(0);
669: int lastEntry = -1;
670:
671: int nextEntry(int index) {
672: while (index < keys.length
673: && states[index] != OCCUPIED)
674: index++;
675: return index;
676: }
677:
678: public boolean hasNext() {
679: return nextEntry < keys.length;
680: }
681:
682: public int next() {
683: if (!hasNext())
684: Exceptions.endOfIterator();
685: lastEntry = nextEntry;
686: nextEntry = nextEntry(nextEntry + 1);
687: return keys[lastEntry];
688: }
689:
690: public void remove() {
691: if (lastEntry == -1)
692: Exceptions.noElementToRemove();
693: states[lastEntry] = REMOVED;
694: values[lastEntry] = null; // GC
695: size--;
696: lastEntry = -1;
697: }
698: };
699: }
700:
701: public boolean remove(int v) {
702: boolean result = containsKey(v);
703: if (result)
704: IntKeyOpenHashMap.this .remove(v);
705: return result;
706: }
707:
708: public int size() {
709: return size;
710: }
711:
712: }
713:
714: private class ValueCollection extends AbstractCollection<E> {
715:
716: public void clear() {
717: IntKeyOpenHashMap.this .clear();
718: }
719:
720: public boolean contains(Object v) {
721: return containsValue(v);
722: }
723:
724: public Iterator<E> iterator() {
725: return new Iterator<E>() {
726: int nextEntry = nextEntry(0);
727: int lastEntry = -1;
728:
729: int nextEntry(int index) {
730: while (index < keys.length
731: && states[index] != OCCUPIED)
732: index++;
733: return index;
734: }
735:
736: public boolean hasNext() {
737: return nextEntry < keys.length;
738: }
739:
740: public E next() {
741: if (!hasNext())
742: Exceptions.endOfIterator();
743: lastEntry = nextEntry;
744: nextEntry = nextEntry(nextEntry + 1);
745: return values[lastEntry];
746: }
747:
748: public void remove() {
749: if (lastEntry == -1)
750: Exceptions.noElementToRemove();
751: states[lastEntry] = REMOVED;
752: values[lastEntry] = null; // GC
753: size--;
754: lastEntry = -1;
755: }
756: };
757: }
758:
759: public int size() {
760: return size;
761: }
762:
763: }
764:
765: // ---------------------------------------------------------------
766: // Operations overwritten for efficiency
767: // ---------------------------------------------------------------
768:
769: public void clear() {
770: java.util.Arrays.fill(states, EMPTY);
771: java.util.Arrays.fill(values, null); // GC
772: size = 0;
773: used = 0;
774: }
775:
776: public boolean containsKey(int key) {
777: int h = Math.abs(keyhash.hash(key));
778: int i = h % keys.length;
779: if (states[i] != EMPTY) {
780: if (states[i] == OCCUPIED && keys[i] == key)
781: return true;
782:
783: // second hash
784: int c = 1 + (h % (keys.length - 2));
785: for (;;) {
786: i -= c;
787: if (i < 0)
788: i += keys.length;
789: if (states[i] == EMPTY)
790: return false;
791: if (states[i] == OCCUPIED && keys[i] == key)
792: return true;
793: }
794: }
795: return false;
796: }
797:
798: public boolean containsValue(Object value) {
799: if (value == null) {
800: for (int i = 0; i < states.length; i++)
801: if (states[i] == OCCUPIED && values[i] == null)
802: return true;
803: } else {
804: for (int i = 0; i < states.length; i++)
805: if (states[i] == OCCUPIED && value.equals(values[i]))
806: return true;
807: }
808: return false;
809: }
810:
811: public E get(int key) {
812: int h = Math.abs(keyhash.hash(key));
813: int i = h % keys.length;
814: if (states[i] != EMPTY) {
815: if (states[i] == OCCUPIED && keys[i] == key)
816: return values[i];
817: // second hash
818:
819: int c = 1 + (h % (keys.length - 2));
820: for (;;) {
821: i -= c;
822: if (i < 0)
823: i += keys.length;
824: if (states[i] == EMPTY)
825: return null;
826: if (states[i] == OCCUPIED && keys[i] == key)
827: return values[i];
828: }
829: }
830: return null;
831: }
832:
833: public boolean isEmpty() {
834: return size == 0;
835: }
836:
837: public E remove(int key) {
838: int h = Math.abs(keyhash.hash(key));
839: int i = h % keys.length;
840: if (states[i] != EMPTY) {
841: if (states[i] == OCCUPIED && keys[i] == key) {
842: E oldValue = values[i];
843: values[i] = null; // GC
844: states[i] = REMOVED;
845: size--;
846: return oldValue;
847: }
848: // second hash
849: int c = 1 + (h % (keys.length - 2));
850: for (;;) {
851: i -= c;
852: if (i < 0)
853: i += keys.length;
854: if (states[i] == EMPTY) {
855: return null;
856: }
857: if (states[i] == OCCUPIED && keys[i] == key) {
858: E oldValue = values[i];
859: values[i] = null; // GC
860: states[i] = REMOVED;
861: size--;
862: return oldValue;
863: }
864: }
865: }
866: return null;
867: }
868:
869: public int size() {
870: return size;
871: }
872:
873: // ---------------------------------------------------------------
874: // Serialization
875: // ---------------------------------------------------------------
876:
877: /**
878: * @serialData Default fields; the capacity of the
879: * map (<tt>int</tt>); the maps's entries
880: * (<tt>int</tt>, <tt>Object</tt>).
881: *
882: * @since 1.1
883: */
884: private void writeObject(ObjectOutputStream s) throws IOException {
885: s.defaultWriteObject();
886: s.writeInt(keys.length);
887: IntKeyMapIterator i = entries();
888: while (i.hasNext()) {
889: i.next();
890: s.writeInt(i.getKey());
891: s.writeObject(i.getValue());
892: }
893: }
894:
895: /**
896: * @since 1.1
897: */
898: private void readObject(ObjectInputStream s) throws IOException,
899: ClassNotFoundException {
900: s.defaultReadObject();
901: keys = new int[s.readInt()];
902: states = new byte[keys.length];
903: values = (E[]) new Object[keys.length];
904: used = size;
905:
906: for (int n = 0; n < size; n++) {
907: int key = s.readInt();
908: E value = (E) s.readObject();
909:
910: // first hash
911: int h = Math.abs(keyhash.hash(key));
912: int i = h % keys.length;
913: if (states[i] != EMPTY) {
914: // second hash
915: int c = 1 + (h % (keys.length - 2));
916: for (;;) {
917: i -= c;
918: if (i < 0)
919: i += keys.length;
920: if (states[i] == EMPTY)
921: break;
922: }
923: }
924: states[i] = OCCUPIED;
925: keys[i] = key;
926: values[i] = value;
927: }
928: }
929:
930: }
|