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