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