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