001: /*
002: * Copyright (c) 1998 - 2005 Versant Corporation
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * Versant Corporation - initial API and implementation
010: */
011: package com.versant.core.util;
012:
013: import java.io.IOException;
014: import java.io.Serializable;
015:
016: /**
017: * Specialized HashMap mapping int to Object. This is a cut and paste of
018: * java.util.HashMap with the key hardcoded as int and some non-required
019: * functionality removed.
020: */
021: public final class IntObjectHashMap implements Serializable {
022:
023: /**
024: * The default initial capacity - MUST be a power of two.
025: */
026: private static final int DEFAULT_INITIAL_CAPACITY = 16;
027:
028: /**
029: * The maximum capacity, used if a higher value is implicitly specified
030: * by either of the constructors with arguments.
031: * MUST be a power of two <= 1<<30.
032: */
033: private static final int MAXIMUM_CAPACITY = 1 << 30;
034:
035: /**
036: * The load factor used when none specified in constructor.
037: */
038: private static final float DEFAULT_LOAD_FACTOR = 0.75f;
039:
040: /**
041: * The table, resized as necessary. Length MUST Always be a power of two.
042: */
043: private transient Entry[] table;
044:
045: /**
046: * The number of key-value mappings contained in this identity hash map.
047: */
048: private transient int size;
049:
050: /**
051: * The next size value at which to resize (capacity * load factor).
052: *
053: * @serial
054: */
055: private int threshold;
056:
057: /**
058: * The load factor for the hash table.
059: *
060: * @serial
061: */
062: private final float loadFactor;
063:
064: /**
065: * Constructs an empty <tt>IntObjectHashMap</tt> with the specified initial
066: * capacity and load factor.
067: *
068: * @param initialCapacity The initial capacity.
069: * @param loadFactor The load factor.
070: * @throws IllegalArgumentException if the initial capacity is negative
071: * or the load factor is nonpositive.
072: */
073: public IntObjectHashMap(int initialCapacity, float loadFactor) {
074: if (initialCapacity < 0) {
075: throw new IllegalArgumentException(
076: "Illegal initial capacity: " + initialCapacity);
077: }
078: if (initialCapacity > MAXIMUM_CAPACITY) {
079: initialCapacity = MAXIMUM_CAPACITY;
080: }
081: if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
082: throw new IllegalArgumentException("Illegal load factor: "
083: + loadFactor);
084: }
085:
086: // Find a power of 2 >= initialCapacity
087: int capacity = 1;
088: while (capacity < initialCapacity) {
089: capacity <<= 1;
090: }
091:
092: this .loadFactor = loadFactor;
093: threshold = (int) (capacity * loadFactor);
094: table = new Entry[capacity];
095: }
096:
097: /**
098: * Constructs an empty <tt>IntObjectHashMap</tt> with the specified initial
099: * capacity and the default load factor (0.75).
100: *
101: * @param initialCapacity the initial capacity.
102: * @throws IllegalArgumentException if the initial capacity is negative.
103: */
104: public IntObjectHashMap(int initialCapacity) {
105: this (initialCapacity, DEFAULT_LOAD_FACTOR);
106: }
107:
108: /**
109: * Constructs an empty <tt>IntObjectHashMap</tt> with the default initial capacity
110: * (16) and the default load factor (0.75).
111: */
112: public IntObjectHashMap() {
113: this .loadFactor = DEFAULT_LOAD_FACTOR;
114: threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
115: table = new Entry[DEFAULT_INITIAL_CAPACITY];
116: }
117:
118: /**
119: * Returns a string representation of this map. The string representation
120: * consists of a list of key-value mappings in the order returned by the
121: * map's <tt>entrySet</tt> view's iterator, enclosed in braces
122: * (<tt>"{}"</tt>). Adjacent mappings are separated by the characters
123: * <tt>", "</tt> (comma and space). Each key-value mapping is rendered as
124: * the key followed by an equals sign (<tt>"="</tt>) followed by the
125: * associated value. Keys and values are converted to strings as by
126: * <tt>String.valueOf(Object)</tt>.<p>
127: * <p/>
128: * This implementation creates an empty string buffer, appends a left
129: * brace, and iterates over the map's <tt>entrySet</tt> view, appending
130: * the string representation of each <tt>map.entry</tt> in turn. After
131: * appending each entry except the last, the string <tt>", "</tt> is
132: * appended. Finally a right brace is appended. A string is obtained
133: * from the stringbuffer, and returned.
134: *
135: * @return a String representation of this map.
136: */
137: public String toString() {
138: StringBuffer buf = new StringBuffer();
139: buf.append("{");
140: for (int i = 0; i < table.length; i++) {
141: Entry e = table[i];
142: for (; e != null; e = e.next) {
143: int key = e.key;
144: Object value = e.getValue();
145: buf.append(key + "="
146: + (value == this ? "(this Map)" : value));
147: }
148: }
149: buf.append("}");
150: return buf.toString();
151: }
152:
153: /**
154: * Returns the number of key-value mappings in this map.
155: *
156: * @return the number of key-value mappings in this map.
157: */
158: public int size() {
159: return size;
160: }
161:
162: /**
163: * Returns <tt>true</tt> if this map contains no key-value mappings.
164: *
165: * @return <tt>true</tt> if this map contains no key-value mappings.
166: */
167: public boolean isEmpty() {
168: return size == 0;
169: }
170:
171: /**
172: * Returns the value to which the specified key is mapped in this identity
173: * hash map, or <tt>null</tt> if the map contains no mapping for this key.
174: * A return value of <tt>null</tt> does not <i>necessarily</i> indicate
175: * that the map contains no mapping for the key; it is also possible that
176: * the map explicitly maps the key to <tt>null</tt>. The
177: * <tt>containsKey</tt> method may be used to distinguish these two cases.
178: *
179: * @param key the key whose associated value is to be returned.
180: * @return the value to which this map maps the specified key, or
181: * <tt>null</tt> if the map contains no mapping for this key.
182: */
183: public Object get(int key) {
184: int i = key & (table.length - 1);
185: Entry e = table[i];
186: while (true) {
187: if (e == null) {
188: return e;
189: }
190: if (key == e.key) {
191: return e.value;
192: }
193: e = e.next;
194: }
195: }
196:
197: /**
198: * Returns <tt>true</tt> if this map contains a mapping for the
199: * specified key.
200: *
201: * @param key The key whose presence in this map is to be tested
202: * @return <tt>true</tt> if this map contains a mapping for the specified
203: * key.
204: */
205: public boolean containsKey(int key) {
206: int i = key & (table.length - 1);
207: Entry e = table[i];
208: while (e != null) {
209: if (key == e.key) {
210: return true;
211: }
212: e = e.next;
213: }
214: return false;
215: }
216:
217: /**
218: * Associates the specified value with the specified key in this map.
219: * If the map previously contained a mapping for this key, the old
220: * value is replaced.
221: *
222: * @param key key with which the specified value is to be associated.
223: * @param value value to be associated with the specified key.
224: * @return previous value associated with specified key, or <tt>null</tt>
225: * if there was no mapping for key. A <tt>null</tt> return can
226: * also indicate that the IntObjectHashMap previously associated
227: * <tt>null</tt> with the specified key.
228: */
229: public Object put(int key, Object value) {
230: int i = key & (table.length - 1);
231: for (Entry e = table[i]; e != null; e = e.next) {
232: if (key == e.key) {
233: Object oldValue = e.value;
234: e.value = value;
235: return oldValue;
236: }
237: }
238: addEntry(key, value, i);
239: return null;
240: }
241:
242: /**
243: * This method is used instead of put by constructors and
244: * pseudoconstructors (clone, readObject). It does not resize the table,
245: * check for comodification, etc. It calls createEntry rather than
246: * addEntry.
247: */
248: private void putForCreate(int key, Object value) {
249: int i = key & (table.length - 1);
250:
251: /**
252: * Look for preexisting entry for key. This will never happen for
253: * clone or deserialize. It will only happen for construction if the
254: * input Map is a sorted map whose ordering is inconsistent w/ equals.
255: */
256: for (Entry e = table[i]; e != null; e = e.next) {
257: if (key == e.key) {
258: e.value = value;
259: return;
260: }
261: }
262: createEntry(key, value, i);
263: }
264:
265: /**
266: * Rehashes the contents of this map into a new array with a
267: * larger capacity. This method is called automatically when the
268: * number of keys in this map reaches its threshold.
269: * <p/>
270: * If current capacity is MAXIMUM_CAPACITY, this method does not
271: * resize the map, but but sets threshold to Integer.MAX_VALUE.
272: * This has the effect of preventing future calls.
273: *
274: * @param newCapacity the new capacity, MUST be a power of two;
275: * must be greater than current capacity unless current
276: * capacity is MAXIMUM_CAPACITY (in which case value
277: * is irrelevant).
278: */
279: private void resize(int newCapacity) {
280: Entry[] oldTable = table;
281: int oldCapacity = oldTable.length;
282: if (oldCapacity == MAXIMUM_CAPACITY) {
283: threshold = Integer.MAX_VALUE;
284: return;
285: }
286:
287: Entry[] newTable = new Entry[newCapacity];
288: transfer(newTable);
289: table = newTable;
290: threshold = (int) (newCapacity * loadFactor);
291: }
292:
293: /**
294: * Transfer all entries from current table to newTable.
295: */
296: private void transfer(Entry[] newTable) {
297: Entry[] src = table;
298: int newCapacity = newTable.length;
299: for (int j = 0; j < src.length; j++) {
300: Entry e = src[j];
301: if (e != null) {
302: src[j] = null;
303: do {
304: Entry next = e.next;
305: int i = e.key & (newCapacity - 1);
306: e.next = newTable[i];
307: newTable[i] = e;
308: e = next;
309: } while (e != null);
310: }
311: }
312: }
313:
314: /**
315: * Removes the mapping for this key from this map if present.
316: *
317: * @param key key whose mapping is to be removed from the map.
318: * @return previous value associated with specified key, or <tt>null</tt>
319: * if there was no mapping for key. A <tt>null</tt> return can
320: * also indicate that the map previously associated <tt>null</tt>
321: * with the specified key.
322: */
323: public Object remove(int key) {
324: Entry e = removeEntryForKey(key);
325: return e == null ? e : e.value;
326: }
327:
328: /**
329: * Removes and returns the entry associated with the specified key
330: * in the IntObjectHashMap. Returns null if the IntObjectHashMap contains no mapping
331: * for this key.
332: */
333: private Entry removeEntryForKey(int key) {
334: int i = key & (table.length - 1);
335: Entry prev = table[i];
336: Entry e = prev;
337:
338: while (e != null) {
339: Entry next = e.next;
340: if (key == e.key) {
341: size--;
342: if (prev == e) {
343: table[i] = next;
344: } else {
345: prev.next = next;
346: }
347: return e;
348: }
349: prev = e;
350: e = next;
351: }
352:
353: return e;
354: }
355:
356: /**
357: * Removes all mappings from this map.
358: */
359: public void clear() {
360: Entry tab[] = table;
361: for (int i = 0; i < tab.length; i++) {
362: tab[i] = null;
363: }
364: size = 0;
365: }
366:
367: /**
368: * Returns <tt>true</tt> if this map maps one or more keys to the
369: * specified value.
370: *
371: * @param value value whose presence in this map is to be tested.
372: * @return <tt>true</tt> if this map maps one or more keys to the
373: * specified value.
374: */
375: public boolean containsValue(Object value) {
376: Entry tab[] = table;
377: for (int i = 0; i < tab.length; i++) {
378: for (Entry e = tab[i]; e != null; e = e.next) {
379: if (value.equals(e.value)) {
380: return true;
381: }
382: }
383: }
384: return false;
385: }
386:
387: private static class Entry {
388:
389: final int key;
390: Object value;
391: Entry next;
392:
393: /**
394: * Create new entry.
395: */
396: public Entry(int k, Object v, Entry n) {
397: value = v;
398: next = n;
399: key = k;
400: }
401:
402: public Object getValue() {
403: return value;
404: }
405:
406: public Object setValue(Object newValue) {
407: Object oldValue = value;
408: value = newValue;
409: return oldValue;
410: }
411:
412: public boolean equals(Object o) {
413: if (!(o instanceof Entry)) {
414: return false;
415: }
416: Entry e = (Entry) o;
417: if (key == e.key) {
418: if (value == e.value
419: || (value != null && value.equals(e.value))) {
420: return true;
421: }
422: }
423: return false;
424: }
425:
426: public int hashCode() {
427: return key ^ (value == null ? 0 : value.hashCode());
428: }
429:
430: public String toString() {
431: return key + "=" + getValue();
432: }
433:
434: }
435:
436: /**
437: * Add a new entry with the specified key, value and hash code to
438: * the specified bucket. It is the responsibility of this
439: * method to resize the table if appropriate.
440: * <p/>
441: * Subclass overrides this to alter the behavior of put method.
442: */
443: private void addEntry(int key, Object value, int bucketIndex) {
444: table[bucketIndex] = new Entry(key, value, table[bucketIndex]);
445: if (size++ >= threshold) {
446: resize(2 * table.length);
447: }
448: }
449:
450: /**
451: * Like addEntry except that this version is used when creating entries
452: * as part of Map construction or "pseudo-construction" (cloning,
453: * deserialization). This version needn't worry about resizing the table.
454: * <p/>
455: * Subclass overrides this to alter the behavior of IntObjectHashMap(Map),
456: * clone, and readObject.
457: */
458: private void createEntry(int key, Object value, int bucketIndex) {
459: table[bucketIndex] = new Entry(key, value, table[bucketIndex]);
460: size++;
461: }
462:
463: /**
464: * Save the state of the <tt>IntObjectHashMap</tt> instance to a stream (i.e.,
465: * serialize it).
466: *
467: * @serialData The <i>capacity</i> of the IntObjectHashMap (the length of the
468: * bucket array) is emitted (int), followed by the
469: * <i>size</i> of the IntObjectHashMap (the number of key-value
470: * mappings), followed by the key (Object) and value (Object)
471: * for each key-value mapping represented by the IntObjectHashMap
472: * The key-value mappings are emitted in the order that they
473: * are returned by <tt>entrySet().iterator()</tt>.
474: */
475: private void writeObject(java.io.ObjectOutputStream s)
476: throws IOException {
477: // Write out the threshold, loadfactor, and any hidden stuff
478: s.defaultWriteObject();
479:
480: // Write out number of buckets
481: s.writeInt(table.length);
482:
483: // Write out size (number of Mappings)
484: s.writeInt(size);
485:
486: // Write out keys and values (alternating)
487: int c = 0;
488: for (int i = 0; c < size && i < table.length; i++) {
489: Entry e = table[i];
490: for (; e != null; e = e.next, ++c) {
491: s.writeInt(e.key);
492: s.writeObject(e.getValue());
493: }
494: }
495: }
496:
497: /**
498: * Reconstitute the <tt>IntObjectHashMap</tt> instance from a stream (i.e.,
499: * deserialize it).
500: */
501: private void readObject(java.io.ObjectInputStream s)
502: throws IOException, ClassNotFoundException {
503: // Read in the threshold, loadfactor, and any hidden stuff
504: s.defaultReadObject();
505:
506: // Read in number of buckets and allocate the bucket array;
507: int numBuckets = s.readInt();
508: table = new Entry[numBuckets];
509:
510: // Read in size (number of Mappings)
511: int size = s.readInt();
512:
513: // Read the keys and values, and put the mappings in the IntObjectHashMap
514: for (int i = 0; i < size; i++) {
515: int key = s.readInt();
516: Object value = s.readObject();
517: putForCreate(key, value);
518: }
519: }
520:
521: }
|