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