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