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