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