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