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