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