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