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