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