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.ShortCollection;
022: import bak.pcj.AbstractShortCollection;
023: import bak.pcj.CharIterator;
024: import bak.pcj.ShortIterator;
025: import bak.pcj.AbstractCharCollection;
026: import bak.pcj.set.AbstractCharSet;
027: import bak.pcj.set.CharSet;
028: import bak.pcj.hash.CharHashFunction;
029: import bak.pcj.hash.DefaultCharHashFunction;
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: * char values to short values.
040: *
041: * @see CharKeyShortOpenHashMap
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 CharKeyShortChainedHashMap extends AbstractCharKeyShortMap
049: implements CharKeyShortMap, 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 CharHashFunction 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 CharSet keys;
125:
126: /** A collection view of the values of this map. */
127: private transient ShortCollection 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 short lastValue;
134:
135: private CharKeyShortChainedHashMap(CharHashFunction 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 CharKeyShortChainedHashMap(int capacity, int growthPolicy,
164: double growthFactor, int growthChunk, double loadFactor) {
165: this (DefaultCharHashFunction.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 CharKeyShortChainedHashMap() {
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 CharKeyShortChainedHashMap(CharKeyShortMap 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 CharKeyShortChainedHashMap(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 CharKeyShortChainedHashMap(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 CharKeyShortChainedHashMap(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 CharKeyShortChainedHashMap(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 CharKeyShortChainedHashMap(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 CharKeyShortChainedHashMap(CharHashFunction 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 CharKeyShortChainedHashMap(CharHashFunction keyhash,
335: int capacity) {
336: this (keyhash, capacity, DEFAULT_GROWTH_POLICY,
337: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK,
338: DEFAULT_LOAD_FACTOR);
339: }
340:
341: /**
342: * Creates a new hash map with a capacity of 11, a relative
343: * growth factor of 1.0, and a specified load factor.
344: *
345: * @param keyhash
346: * the hash function to use when hashing keys.
347: *
348: * @param loadFactor
349: * the load factor of the map.
350: *
351: * @throws IllegalArgumentException
352: * if <tt>capacity</tt> is negative.
353: *
354: * @throws NullPointerException
355: * if <tt>keyhash</tt> is <tt>null</tt>.
356: */
357: public CharKeyShortChainedHashMap(CharHashFunction keyhash,
358: double loadFactor) {
359: this (keyhash, DEFAULT_CAPACITY, DEFAULT_GROWTH_POLICY,
360: DEFAULT_GROWTH_FACTOR, DEFAULT_GROWTH_CHUNK, loadFactor);
361: }
362:
363: /**
364: * Creates a new hash map with a specified capacity and
365: * load factor, and a relative growth factor of 1.0.
366: *
367: * @param keyhash
368: * the hash function to use when hashing keys.
369: *
370: * @param capacity
371: * the initial capacity of the map.
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 CharKeyShortChainedHashMap(CharHashFunction keyhash,
384: int capacity, double loadFactor) {
385: this (keyhash, 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,
391: * load factor, and relative growth factor.
392: *
393: * <p>The map capacity increases to <tt>capacity()*(1+growthFactor)</tt>.
394: * This strategy is good for avoiding many capacity increases, but
395: * the amount of wasted memory is approximately the size of the map.
396: *
397: * @param keyhash
398: * the hash function to use when hashing keys.
399: *
400: * @param capacity
401: * the initial capacity of the map.
402: *
403: * @param loadFactor
404: * the load factor of the map.
405: *
406: * @param growthFactor
407: * the relative amount with which to increase the
408: * the capacity when a capacity increase is needed.
409: *
410: * @throws IllegalArgumentException
411: * if <tt>capacity</tt> is negative;
412: * if <tt>loadFactor</tt> is not positive;
413: * if <tt>growthFactor</tt> is not positive.
414: *
415: * @throws NullPointerException
416: * if <tt>keyhash</tt> is <tt>null</tt>.
417: */
418: public CharKeyShortChainedHashMap(CharHashFunction keyhash,
419: int capacity, double loadFactor, double growthFactor) {
420: this (keyhash, capacity, GROWTH_POLICY_RELATIVE, growthFactor,
421: DEFAULT_GROWTH_CHUNK, loadFactor);
422: }
423:
424: /**
425: * Creates a new hash map with a specified capacity,
426: * load factor, and absolute growth factor.
427: *
428: * <p>The map capacity increases to <tt>capacity()+growthChunk</tt>.
429: * This strategy is good for avoiding wasting memory. However, an
430: * overhead is potentially introduced by frequent capacity increases.
431: *
432: * @param keyhash
433: * the hash function to use when hashing keys.
434: *
435: * @param capacity
436: * the initial capacity of the map.
437: *
438: * @param loadFactor
439: * the load factor of the map.
440: *
441: * @param growthChunk
442: * the absolute amount with which to increase the
443: * the capacity when a capacity increase is needed.
444: *
445: * @throws IllegalArgumentException
446: * if <tt>capacity</tt> is negative;
447: * if <tt>loadFactor</tt> is not positive;
448: * if <tt>growthChunk</tt> is not positive;
449: *
450: * @throws NullPointerException
451: * if <tt>keyhash</tt> is <tt>null</tt>.
452: */
453: public CharKeyShortChainedHashMap(CharHashFunction keyhash,
454: int capacity, double loadFactor, int growthChunk) {
455: this (keyhash, capacity, GROWTH_POLICY_ABSOLUTE,
456: DEFAULT_GROWTH_FACTOR, growthChunk, loadFactor);
457: }
458:
459: // ---------------------------------------------------------------
460: // Hash table management
461: // ---------------------------------------------------------------
462:
463: private void ensureCapacity(int elements) {
464: if (elements >= expandAt) {
465: int newcapacity;
466: if (growthPolicy == GROWTH_POLICY_RELATIVE)
467: newcapacity = (int) (data.length * (1.0 + growthFactor));
468: else
469: newcapacity = data.length + growthChunk;
470: if (newcapacity * loadFactor < elements)
471: newcapacity = (int) Math
472: .round(((double) elements / loadFactor));
473: newcapacity = bak.pcj.hash.Primes.nextPrime(newcapacity);
474: expandAt = (int) Math.round(loadFactor * newcapacity);
475:
476: Entry[] newdata = new Entry[newcapacity];
477:
478: // re-hash
479: for (int i = 0; i < data.length; i++) {
480: Entry e = data[i];
481: while (e != null) {
482: int index = Math.abs(keyhash.hash(e.key))
483: % newdata.length;
484: Entry next = e.next;
485: e.next = newdata[index];
486: newdata[index] = e;
487: e = next;
488: }
489: }
490:
491: data = newdata;
492: }
493: }
494:
495: private Entry addList(Entry list, Entry v) {
496: v.next = list;
497: return v;
498: }
499:
500: private Entry removeList(Entry list, Entry e) {
501: if (list == e) {
502: list = e.next;
503: e.next = null;
504: return list;
505: }
506: Entry listStart = list;
507: while (list.next != e)
508: list = list.next;
509: list.next = e.next;
510: e.next = null;
511: return listStart;
512: }
513:
514: private Entry searchList(Entry list, char key) {
515: while (list != null) {
516: if (list.key == key)
517: return list;
518: list = list.next;
519: }
520: return null;
521: }
522:
523: private Entry getEntry(char key) {
524: int index = Math.abs(keyhash.hash(key)) % data.length;
525: return searchList(data[index], key);
526: }
527:
528: // ---------------------------------------------------------------
529: // Operations not supported by abstract implementation
530: // ---------------------------------------------------------------
531:
532: public CharSet keySet() {
533: if (keys == null)
534: keys = new KeySet();
535: return keys;
536: }
537:
538: public short lget() {
539: if (!hasLastValue)
540: Exceptions.noLastElement();
541: return lastValue;
542: }
543:
544: public short put(char key, short value) {
545: short result;
546: int index = Math.abs(keyhash.hash(key)) % data.length;
547: Entry e = searchList(data[index], key);
548: if (e == null) {
549: result = MapDefaults.defaultShort();
550: e = new Entry(key, value);
551: e.next = data[index];
552: data[index] = e;
553: // Capacity is increased after insertion in order to
554: // avoid recalculation of index
555: ensureCapacity(size + 1);
556: size++;
557: } else {
558: result = e.value;
559: e.value = value;
560: }
561: return result;
562: }
563:
564: public ShortCollection values() {
565: if (values == null)
566: values = new ValueCollection();
567: return values;
568: }
569:
570: /**
571: * Returns a clone of this hash map.
572: *
573: * @return a clone of this hash map.
574: *
575: * @since 1.1
576: */
577: public Object clone() {
578: try {
579: CharKeyShortChainedHashMap c = (CharKeyShortChainedHashMap) super
580: .clone();
581: c.data = new Entry[data.length];
582: for (int i = 0; i < data.length; i++)
583: c.data[i] = cloneList(data[i]);
584: // The views should not refer to this map's views
585: c.values = null;
586: c.keys = null;
587: return c;
588: } catch (CloneNotSupportedException e) {
589: Exceptions.cloning();
590: return null;
591: }
592: }
593:
594: private Entry cloneList(Entry e) {
595: if (e == null)
596: return null;
597: Entry ne = new Entry(e.getKey(), e.getValue());
598: ne.next = cloneList(e.next);
599: return ne;
600: }
601:
602: private static class Entry {
603: char key;
604: short value;
605: Entry next;
606:
607: Entry(char key, short value) {
608: this .key = key;
609: this .value = value;
610: }
611:
612: public char getKey() {
613: return key;
614: }
615:
616: public short getValue() {
617: return value;
618: }
619:
620: public boolean equals(Object obj) {
621: if (!(obj instanceof Entry))
622: return false;
623: Entry e = (Entry) obj;
624: return e.getKey() == key && e.getValue() == value;
625: }
626: }
627:
628: public CharKeyShortMapIterator entries() {
629: return new CharKeyShortMapIterator() {
630: Entry currEntry = null;
631: int nextList = nextList(0);
632: Entry nextEntry = nextList == -1 ? null : data[nextList];
633:
634: int nextList(int index) {
635: while (index < data.length && data[index] == null)
636: index++;
637: return index < data.length ? index : -1;
638: }
639:
640: public boolean hasNext() {
641: return nextEntry != null;
642: }
643:
644: public void next() {
645: if (nextEntry == null)
646: Exceptions.endOfIterator();
647: currEntry = nextEntry;
648:
649: // Find next
650: nextEntry = nextEntry.next;
651: if (nextEntry == null) {
652: nextList = nextList(nextList + 1);
653: if (nextList != -1)
654: nextEntry = data[nextList];
655: }
656: }
657:
658: public char getKey() {
659: if (currEntry == null)
660: Exceptions.noElementToGet();
661: return currEntry.getKey();
662: }
663:
664: public short getValue() {
665: if (currEntry == null)
666: Exceptions.noElementToGet();
667: return currEntry.getValue();
668: }
669:
670: public void remove() {
671: if (currEntry == null)
672: Exceptions.noElementToRemove();
673: CharKeyShortChainedHashMap.this .remove(currEntry
674: .getKey());
675: currEntry = null;
676: }
677:
678: };
679: }
680:
681: private class KeySet extends AbstractCharSet {
682:
683: public void clear() {
684: CharKeyShortChainedHashMap.this .clear();
685: }
686:
687: public boolean contains(char v) {
688: return getEntry(v) != null;
689: }
690:
691: public CharIterator iterator() {
692: return new CharIterator() {
693: Entry currEntry = null;
694: int nextList = nextList(0);
695: Entry nextEntry = nextList == -1 ? null
696: : data[nextList];
697:
698: int nextList(int index) {
699: while (index < data.length && data[index] == null)
700: index++;
701: return index < data.length ? index : -1;
702: }
703:
704: public boolean hasNext() {
705: return nextEntry != null;
706: }
707:
708: public char next() {
709: if (nextEntry == null)
710: Exceptions.endOfIterator();
711: currEntry = nextEntry;
712:
713: // Find next
714: nextEntry = nextEntry.next;
715: if (nextEntry == null) {
716: nextList = nextList(nextList + 1);
717: if (nextList != -1)
718: nextEntry = data[nextList];
719: }
720: return currEntry.key;
721: }
722:
723: public void remove() {
724: if (currEntry == null)
725: Exceptions.noElementToRemove();
726: CharKeyShortChainedHashMap.this .remove(currEntry
727: .getKey());
728: currEntry = null;
729: }
730: };
731: }
732:
733: public boolean remove(char v) {
734: boolean result = containsKey(v);
735: if (result)
736: CharKeyShortChainedHashMap.this .remove(v);
737: return result;
738: }
739:
740: public int size() {
741: return size;
742: }
743:
744: }
745:
746: private class ValueCollection extends AbstractShortCollection {
747:
748: public void clear() {
749: CharKeyShortChainedHashMap.this .clear();
750: }
751:
752: public boolean contains(short v) {
753: return containsValue(v);
754: }
755:
756: public ShortIterator iterator() {
757: return new ShortIterator() {
758: Entry currEntry = null;
759: int nextList = nextList(0);
760: Entry nextEntry = nextList == -1 ? null
761: : data[nextList];
762:
763: int nextList(int index) {
764: while (index < data.length && data[index] == null)
765: index++;
766: return index < data.length ? index : -1;
767: }
768:
769: public boolean hasNext() {
770: return nextEntry != null;
771: }
772:
773: public short next() {
774: if (nextEntry == null)
775: Exceptions.endOfIterator();
776: currEntry = nextEntry;
777:
778: // Find next
779: nextEntry = nextEntry.next;
780: if (nextEntry == null) {
781: nextList = nextList(nextList + 1);
782: if (nextList != -1)
783: nextEntry = data[nextList];
784: }
785: return currEntry.value;
786: }
787:
788: public void remove() {
789: if (currEntry == null)
790: Exceptions.noElementToRemove();
791: CharKeyShortChainedHashMap.this .remove(currEntry
792: .getKey());
793: currEntry = null;
794: }
795: };
796: }
797:
798: public int size() {
799: return size;
800: }
801:
802: }
803:
804: // ---------------------------------------------------------------
805: // Operations overwritten for efficiency
806: // ---------------------------------------------------------------
807:
808: public void clear() {
809: java.util.Arrays.fill(data, null);
810: size = 0;
811: }
812:
813: public boolean containsKey(char key) {
814: Entry e = getEntry(key);
815: if (e == null)
816: hasLastValue = false;
817: else {
818: hasLastValue = true;
819: lastValue = e.value;
820: }
821: return hasLastValue;
822: }
823:
824: public boolean containsValue(short value) {
825: for (int i = 0; i < data.length; i++) {
826: Entry e = data[i];
827: while (e != null) {
828: if (e.value == value)
829: return true;
830: e = e.next;
831: }
832: }
833: return false;
834: }
835:
836: public short get(char key) {
837: int index = Math.abs(keyhash.hash(key)) % data.length;
838: Entry e = searchList(data[index], key);
839: return e != null ? e.value : MapDefaults.defaultShort();
840: }
841:
842: public boolean isEmpty() {
843: return size == 0;
844: }
845:
846: public short remove(char key) {
847: int index = Math.abs(keyhash.hash(key)) % data.length;
848: Entry e = searchList(data[index], key);
849: short value;
850: if (e != null) {
851: // This can be improved to one iteration
852: data[index] = removeList(data[index], e);
853: value = e.value;
854: size--;
855: } else
856: value = MapDefaults.defaultShort();
857: return value;
858: }
859:
860: public int size() {
861: return size;
862: }
863:
864: public short tget(char key) {
865: int index = Math.abs(keyhash.hash(key)) % data.length;
866: Entry e = searchList(data[index], key);
867: if (e == null)
868: Exceptions.noSuchMapping(String.valueOf(key));
869: return e.value;
870: }
871:
872: // ---------------------------------------------------------------
873: // Serialization
874: // ---------------------------------------------------------------
875:
876: /**
877: * @serialData Default fields; the capacity of the
878: * map (<tt>int</tt>); the maps's entries
879: * (<tt>char</tt>, <tt>short</tt>).
880: *
881: * @since 1.1
882: */
883: private void writeObject(ObjectOutputStream s) throws IOException {
884: s.defaultWriteObject();
885: s.writeInt(data.length);
886: CharKeyShortMapIterator i = entries();
887: while (i.hasNext()) {
888: i.next();
889: s.writeChar(i.getKey());
890: s.writeShort(i.getValue());
891: }
892: }
893:
894: /**
895: * @since 1.1
896: */
897: private void readObject(ObjectInputStream s) throws IOException,
898: ClassNotFoundException {
899: s.defaultReadObject();
900: data = new Entry[s.readInt()];
901: for (int i = 0; i < size; i++) {
902: char key = s.readChar();
903: short value = s.readShort();
904: int index = Math.abs(keyhash.hash(key)) % data.length;
905: Entry e = new Entry(key, value);
906: e.next = data[index];
907: data[index] = e;
908: }
909: }
910:
911: }
|