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