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