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:
026: import com.uwyn.rife.pcj.AbstractIntCollection;
027: import com.uwyn.rife.pcj.IntCollection;
028: import com.uwyn.rife.pcj.IntIterator;
029: import com.uwyn.rife.pcj.hash.DefaultIntHashFunction;
030: import com.uwyn.rife.pcj.hash.IntHashFunction;
031: import com.uwyn.rife.pcj.set.AbstractIntSet;
032: import com.uwyn.rife.pcj.set.IntSet;
033: import com.uwyn.rife.pcj.util.Exceptions;
034:
035: /**
036: * This class represents open addressing hash table based maps from
037: * int values to int values.
038: *
039: * @see IntKeyIntChainedHashMap
040: * @see java.util.Map
041: *
042: * @author Søren Bak
043: * @version 1.4 21-08-2003 18:40
044: * @since 1.0
045: */
046: public class IntKeyIntOpenHashMap extends AbstractIntKeyIntMap
047: implements IntKeyIntMap, Cloneable, Serializable {
048:
049: private static final long serialVersionUID = 4510630334925786269L;
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 = com.uwyn.rife.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 = com.uwyn.rife.pcj.hash.Primes
500: .nextPrime(newcapacity);
501: expandAt = (int) Math.round(loadFactor * newcapacity);
502:
503: int[] newkeys = new int[newcapacity];
504: int[] newvalues = new int[newcapacity];
505: byte[] newstates = new byte[newcapacity];
506:
507: used = 0;
508: // re-hash
509: for (int i = 0; i < keys.length; i++) {
510: if (states[i] == OCCUPIED) {
511: used++;
512: int k = keys[i];
513: int v = values[i];
514: // first hash
515: int h = Math.abs(keyhash.hash(k));
516: int n = h % newcapacity;
517: if (newstates[n] == OCCUPIED) {
518: // second hash
519: int c = 1 + (h % (newcapacity - 2));
520: for (;;) {
521: n -= c;
522: if (n < 0)
523: n += newcapacity;
524: if (newstates[n] == EMPTY)
525: break;
526: }
527: }
528: newstates[n] = OCCUPIED;
529: newvalues[n] = v;
530: newkeys[n] = k;
531: }
532: }
533:
534: keys = newkeys;
535: values = newvalues;
536: states = newstates;
537: }
538: }
539:
540: // ---------------------------------------------------------------
541: // Operations not supported by abstract implementation
542: // ---------------------------------------------------------------
543:
544: public IntSet keySet() {
545: if (ckeys == null)
546: ckeys = new KeySet();
547: return ckeys;
548: }
549:
550: public int lget() {
551: if (!hasLastValue)
552: Exceptions.noLastElement();
553: return lastValue;
554: }
555:
556: public int put(int key, int value) {
557: // first hash
558: int h = Math.abs(keyhash.hash(key));
559: int i = h % keys.length;
560: if (states[i] == OCCUPIED) {
561: if (keys[i] == key) {
562: int oldValue = values[i];
563: values[i] = value;
564: return oldValue;
565: }
566: // second hash
567: int c = 1 + (h % (keys.length - 2));
568: for (;;) {
569: i -= c;
570: if (i < 0)
571: i += keys.length;
572: // Empty entries are not re-used
573: if (states[i] == EMPTY || states[i] == REMOVED)
574: break;
575: if (states[i] == OCCUPIED && keys[i] == key) {
576: int oldValue = values[i];
577: values[i] = value;
578: return oldValue;
579: }
580: }
581: }
582: if (states[i] == EMPTY)
583: used++;
584: states[i] = OCCUPIED;
585: keys[i] = key;
586: values[i] = value;
587: size++;
588: ensureCapacity(used);
589: return MapDefaults.defaultInt();
590: }
591:
592: public IntCollection values() {
593: if (cvalues == null)
594: cvalues = new ValueCollection();
595: return cvalues;
596: }
597:
598: /**
599: * Returns a clone of this hash map.
600: *
601: * @return a clone of this hash map.
602: *
603: * @since 1.1
604: */
605: public Object clone() {
606: try {
607: IntKeyIntOpenHashMap c = (IntKeyIntOpenHashMap) super
608: .clone();
609: c.keys = new int[keys.length];
610: System.arraycopy(keys, 0, c.keys, 0, keys.length);
611: c.values = new int[values.length];
612: System.arraycopy(values, 0, c.values, 0, values.length);
613: c.states = new byte[states.length];
614: System.arraycopy(states, 0, c.states, 0, states.length);
615: // The views should not refer to this map's views
616: c.cvalues = null;
617: c.ckeys = null;
618: return c;
619: } catch (CloneNotSupportedException e) {
620: Exceptions.cloning();
621: return null;
622: }
623: }
624:
625: public IntKeyIntMapIterator entries() {
626: return new IntKeyIntMapIterator() {
627: int nextEntry = nextEntry(0);
628: int lastEntry = -1;
629:
630: int nextEntry(int index) {
631: while (index < keys.length && states[index] != OCCUPIED)
632: index++;
633: return index;
634: }
635:
636: public boolean hasNext() {
637: return nextEntry < keys.length;
638: }
639:
640: public void next() {
641: if (!hasNext())
642: Exceptions.endOfIterator();
643: lastEntry = nextEntry;
644: nextEntry = nextEntry(nextEntry + 1);
645: }
646:
647: public void remove() {
648: if (lastEntry == -1)
649: Exceptions.noElementToRemove();
650: states[lastEntry] = REMOVED;
651: size--;
652: lastEntry = -1;
653: }
654:
655: public int getKey() {
656: if (lastEntry == -1)
657: Exceptions.noElementToGet();
658: return keys[lastEntry];
659: }
660:
661: public int getValue() {
662: if (lastEntry == -1)
663: Exceptions.noElementToGet();
664: return values[lastEntry];
665: }
666: };
667: }
668:
669: private class KeySet extends AbstractIntSet {
670:
671: public void clear() {
672: IntKeyIntOpenHashMap.this .clear();
673: }
674:
675: public boolean contains(int v) {
676: return containsKey(v);
677: }
678:
679: public IntIterator iterator() {
680: return new IntIterator() {
681: int nextEntry = nextEntry(0);
682: int lastEntry = -1;
683:
684: int nextEntry(int index) {
685: while (index < keys.length
686: && states[index] != OCCUPIED)
687: index++;
688: return index;
689: }
690:
691: public boolean hasNext() {
692: return nextEntry < keys.length;
693: }
694:
695: public int next() {
696: if (!hasNext())
697: Exceptions.endOfIterator();
698: lastEntry = nextEntry;
699: nextEntry = nextEntry(nextEntry + 1);
700: return keys[lastEntry];
701: }
702:
703: public void remove() {
704: if (lastEntry == -1)
705: Exceptions.noElementToRemove();
706: states[lastEntry] = REMOVED;
707: size--;
708: lastEntry = -1;
709: }
710: };
711: }
712:
713: public boolean remove(int v) {
714: boolean result = containsKey(v);
715: if (result)
716: IntKeyIntOpenHashMap.this .remove(v);
717: return result;
718: }
719:
720: public int size() {
721: return size;
722: }
723:
724: }
725:
726: private class ValueCollection extends AbstractIntCollection {
727:
728: public void clear() {
729: IntKeyIntOpenHashMap.this .clear();
730: }
731:
732: public boolean contains(int v) {
733: return containsValue(v);
734: }
735:
736: public IntIterator iterator() {
737: return new IntIterator() {
738: int nextEntry = nextEntry(0);
739: int lastEntry = -1;
740:
741: int nextEntry(int index) {
742: while (index < keys.length
743: && states[index] != OCCUPIED)
744: index++;
745: return index;
746: }
747:
748: public boolean hasNext() {
749: return nextEntry < keys.length;
750: }
751:
752: public int next() {
753: if (!hasNext())
754: Exceptions.endOfIterator();
755: lastEntry = nextEntry;
756: nextEntry = nextEntry(nextEntry + 1);
757: return values[lastEntry];
758: }
759:
760: public void remove() {
761: if (lastEntry == -1)
762: Exceptions.noElementToRemove();
763: states[lastEntry] = REMOVED;
764: size--;
765: lastEntry = -1;
766: }
767: };
768: }
769:
770: public int size() {
771: return size;
772: }
773:
774: }
775:
776: // ---------------------------------------------------------------
777: // Operations overwritten for efficiency
778: // ---------------------------------------------------------------
779:
780: public void clear() {
781: java.util.Arrays.fill(states, EMPTY);
782: size = 0;
783: used = 0;
784: }
785:
786: public boolean containsKey(int key) {
787: int h = Math.abs(keyhash.hash(key));
788: int i = h % keys.length;
789: if (states[i] != EMPTY) {
790: if (states[i] == OCCUPIED && keys[i] == key) {
791: hasLastValue = true;
792: lastValue = values[i];
793: return true;
794: }
795: // second hash
796:
797: int c = 1 + (h % (keys.length - 2));
798: for (;;) {
799: i -= c;
800: if (i < 0)
801: i += keys.length;
802: if (states[i] == EMPTY) {
803: hasLastValue = false;
804: return false;
805: }
806: if (states[i] == OCCUPIED && keys[i] == key) {
807: hasLastValue = true;
808: lastValue = values[i];
809: return true;
810: }
811: }
812: }
813: hasLastValue = false;
814: return false;
815: }
816:
817: public boolean containsValue(int value) {
818: for (int i = 0; i < states.length; i++)
819: if (states[i] == OCCUPIED && values[i] == value)
820: return true;
821: return false;
822: }
823:
824: public int get(int key) {
825: int h = Math.abs(keyhash.hash(key));
826: int i = h % keys.length;
827: if (states[i] != EMPTY) {
828: if (states[i] == OCCUPIED && keys[i] == key)
829: return values[i];
830: // second hash
831:
832: int c = 1 + (h % (keys.length - 2));
833: for (;;) {
834: i -= c;
835: if (i < 0)
836: i += keys.length;
837: if (states[i] == EMPTY)
838: return MapDefaults.defaultInt();
839: if (states[i] == OCCUPIED && keys[i] == key)
840: return values[i];
841: }
842: }
843: return MapDefaults.defaultInt();
844: }
845:
846: public boolean isEmpty() {
847: return size == 0;
848: }
849:
850: public int remove(int key) {
851: int h = Math.abs(keyhash.hash(key));
852: int i = h % keys.length;
853: if (states[i] != EMPTY) {
854: if (states[i] == OCCUPIED && keys[i] == key) {
855: int oldValue = values[i];
856: states[i] = REMOVED;
857: size--;
858: return oldValue;
859: }
860: // second hash
861: int c = 1 + (h % (keys.length - 2));
862: for (;;) {
863: i -= c;
864: if (i < 0)
865: i += keys.length;
866: if (states[i] == EMPTY) {
867: return MapDefaults.defaultInt();
868: }
869: if (states[i] == OCCUPIED && keys[i] == key) {
870: int oldValue = values[i];
871: states[i] = REMOVED;
872: size--;
873: return oldValue;
874: }
875: }
876: }
877: return MapDefaults.defaultInt();
878: }
879:
880: public int size() {
881: return size;
882: }
883:
884: public int tget(int key) {
885: int h = Math.abs(keyhash.hash(key));
886: int i = h % keys.length;
887: if (states[i] != EMPTY) {
888: if (states[i] == OCCUPIED && keys[i] == key)
889: return values[i];
890: // second hash
891:
892: int c = 1 + (h % (keys.length - 2));
893: for (;;) {
894: i -= c;
895: if (i < 0)
896: i += keys.length;
897: if (states[i] == EMPTY)
898: Exceptions.noSuchMapping(String.valueOf(key));
899: if (states[i] == OCCUPIED && keys[i] == key)
900: return values[i];
901: }
902: }
903: Exceptions.noSuchMapping(String.valueOf(key));
904: throw new RuntimeException();
905: }
906:
907: // ---------------------------------------------------------------
908: // Serialization
909: // ---------------------------------------------------------------
910:
911: /**
912: * @serialData Default fields; the capacity of the
913: * map (<tt>int</tt>); the maps's entries
914: * (<tt>int</tt>, <tt>int</tt>).
915: *
916: * @since 1.1
917: */
918: private void writeObject(ObjectOutputStream s) throws IOException {
919: s.defaultWriteObject();
920: s.writeInt(keys.length);
921: IntKeyIntMapIterator i = entries();
922: while (i.hasNext()) {
923: i.next();
924: s.writeInt(i.getKey());
925: s.writeInt(i.getValue());
926: }
927: }
928:
929: /**
930: * @since 1.1
931: */
932: private void readObject(ObjectInputStream s) throws IOException,
933: ClassNotFoundException {
934: s.defaultReadObject();
935: keys = new int[s.readInt()];
936: states = new byte[keys.length];
937: values = new int[keys.length];
938: used = size;
939:
940: for (int n = 0; n < size; n++) {
941: int key = s.readInt();
942: int value = s.readInt();
943:
944: // first hash
945: int h = Math.abs(keyhash.hash(key));
946: int i = h % keys.length;
947: if (states[i] != EMPTY) {
948: // second hash
949: int c = 1 + (h % (keys.length - 2));
950: for (;;) {
951: i -= c;
952: if (i < 0)
953: i += keys.length;
954: if (states[i] == EMPTY)
955: break;
956: }
957: }
958: states[i] = OCCUPIED;
959: keys[i] = key;
960: values[i] = value;
961: }
962: }
963:
964: }
|