001: /*
002: * Copyright 2007 Google Inc.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005: * use this file except in compliance with the License. You may obtain a copy of
006: * the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013: * License for the specific language governing permissions and limitations under
014: * the License.
015: */
016: package java.util;
017:
018: import com.google.gwt.core.client.JavaScriptObject;
019:
020: import java.io.Serializable;
021:
022: /**
023: * Implementation of Map interface based on a hash table. <a
024: * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun
025: * docs]</a>
026: *
027: * @param <K> key type
028: * @param <V> value type
029: */
030: public class HashMap<K, V> extends AbstractMap<K, V> implements
031: Serializable {
032: /*
033: * Implementation notes:
034: *
035: * String keys are stored in a separate map from non-String keys. String keys
036: * are mapped to their values via a JS associative map, stringMap. String keys
037: * could collide with intrinsic properties (like watch, constructor) so we
038: * prepend each key with a ':' inside of stringMap.
039: *
040: * Integer keys are used to index all non-string keys. A key's hashCode is the
041: * index in hashCodeMap which should contain that key. Since several keys may
042: * have the same hash, each value in hashCodeMap is actually an array
043: * containing all entries whose keys share the same hash.
044: */
045: private final class EntrySet extends AbstractSet<Entry<K, V>> {
046:
047: @Override
048: public void clear() {
049: HashMap.this .clear();
050: }
051:
052: @Override
053: public boolean contains(Object o) {
054: if (o instanceof Map.Entry) {
055: Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
056: Object key = entry.getKey();
057: if (HashMap.this .containsKey(key)) {
058: Object value = HashMap.this .get(key);
059: return Utility.equalsWithNullCheck(
060: entry.getValue(), value);
061: }
062: }
063: return false;
064: }
065:
066: @Override
067: public Iterator<Entry<K, V>> iterator() {
068: return new EntrySetIterator();
069: }
070:
071: @Override
072: public boolean remove(Object entry) {
073: if (contains(entry)) {
074: Object key = ((Map.Entry<?, ?>) entry).getKey();
075: HashMap.this .remove(key);
076: return true;
077: }
078: return false;
079: }
080:
081: @Override
082: public int size() {
083: return HashMap.this .size();
084: }
085: }
086:
087: /**
088: * Iterator for <code>EntrySetImpl</code>.
089: */
090: private final class EntrySetIterator implements
091: Iterator<Entry<K, V>> {
092: private final Iterator<Map.Entry<K, V>> iter;
093: private Map.Entry<K, V> last = null;
094:
095: /**
096: * Constructor for <code>EntrySetIterator</code>.
097: */
098: public EntrySetIterator() {
099: List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>();
100: if (nullSlotLive) {
101: MapEntryImpl<K, V> entryImpl = new MapEntryImpl<K, V>(
102: null, nullSlot);
103: list.add(entryImpl);
104: }
105: addAllStringEntries(stringMap, list);
106: addAllHashEntries(hashCodeMap, list);
107: this .iter = list.iterator();
108: }
109:
110: public boolean hasNext() {
111: return iter.hasNext();
112: }
113:
114: public Map.Entry<K, V> next() {
115: return last = iter.next();
116: }
117:
118: public void remove() {
119: if (last == null) {
120: throw new IllegalStateException(
121: "Must call next() before remove().");
122: } else {
123: iter.remove();
124: HashMap.this .remove(last.getKey());
125: last = null;
126: }
127: }
128: }
129:
130: private static native void addAllHashEntries(
131: JavaScriptObject hashCodeMap, Collection<?> dest) /*-{
132: for (var hashCode in hashCodeMap) {
133: // sanity check that it's really an integer
134: if (hashCode == parseInt(hashCode)) {
135: var array = hashCodeMap[hashCode];
136: for (var i = 0, c = array.length; i < c; ++i) {
137: dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]);
138: }
139: }
140: }
141: }-*/;
142:
143: private static native void addAllStringEntries(
144: JavaScriptObject stringMap, Collection<?> dest) /*-{
145: for (var key in stringMap) {
146: // only keys that start with a colon ':' count
147: if (key.charCodeAt(0) == 58) {
148: var value = stringMap[key];
149: var entry = @java.util.MapEntryImpl::create(Ljava/lang/Object;Ljava/lang/Object;)(key.substring(1), value);
150: dest.@java.util.Collection::add(Ljava/lang/Object;)(entry);
151: }
152: }
153: }-*/;
154:
155: /**
156: * Returns true if hashCodeMap contains any Map.Entry whose value is Object
157: * equal to <code>value</code>.
158: */
159: private static native boolean containsHashValue(
160: JavaScriptObject hashCodeMap, Object value) /*-{
161: for (var hashCode in hashCodeMap) {
162: // sanity check that it's really one of ours
163: if (hashCode == parseInt(hashCode)) {
164: var array = hashCodeMap[hashCode];
165: for (var i = 0, c = array.length; i < c; ++i) {
166: var entry = array[i];
167: var entryValue = entry.@java.util.Map$Entry::getValue()();
168: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
169: return true;
170: }
171: }
172: }
173: }
174: return false;
175: }-*/;
176:
177: /**
178: * Returns true if stringMap contains any key whose value is Object equal to
179: * <code>value</code>.
180: */
181: private static native boolean containsStringValue(
182: JavaScriptObject stringMap, Object value) /*-{
183: for (var key in stringMap) {
184: // only keys that start with a colon ':' count
185: if (key.charCodeAt(0) == 58) {
186: var entryValue = stringMap[key];
187: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) {
188: return true;
189: }
190: }
191: }
192: return false;
193: }-*/;
194:
195: /**
196: * A map of integral hashCodes onto entries.
197: */
198: private transient JavaScriptObject hashCodeMap;
199:
200: /**
201: * This is the slot that holds the value associated with the "null" key.
202: */
203: private transient V nullSlot;
204:
205: private transient boolean nullSlotLive;
206:
207: private int size;
208:
209: /**
210: * A map of Strings onto values.
211: */
212: private transient JavaScriptObject stringMap;
213:
214: {
215: clearImpl();
216: }
217:
218: public HashMap() {
219: }
220:
221: public HashMap(int ignored) {
222: // This implementation of HashMap has no need of initial capacities.
223: this (ignored, 0);
224: }
225:
226: public HashMap(int ignored, float alsoIgnored) {
227: // This implementation of HashMap has no need of load factors or capacities.
228: if (ignored < 0 || alsoIgnored < 0) {
229: throw new IllegalArgumentException(
230: "initial capacity was negative or load factor was non-positive");
231: }
232: }
233:
234: public HashMap(Map<? extends K, ? extends V> toBeCopied) {
235: this .putAll(toBeCopied);
236: }
237:
238: @Override
239: public void clear() {
240: clearImpl();
241: }
242:
243: public Object clone() {
244: return new HashMap<K, V>(this );
245: }
246:
247: @Override
248: public boolean containsKey(Object key) {
249: return (key == null) ? nullSlotLive
250: : (!(key instanceof String) ? hasHashValue(key, key
251: .hashCode()) : hasStringValue((String) key));
252: }
253:
254: @Override
255: public boolean containsValue(Object value) {
256: if (nullSlotLive
257: && Utility.equalsWithNullCheck(nullSlot, value)) {
258: return true;
259: } else if (containsStringValue(stringMap, value)) {
260: return true;
261: } else if (containsHashValue(hashCodeMap, value)) {
262: return true;
263: }
264: return false;
265: }
266:
267: @Override
268: public Set<Map.Entry<K, V>> entrySet() {
269: return new EntrySet();
270: }
271:
272: @Override
273: public V get(Object key) {
274: return (key == null) ? nullSlot
275: : (!(key instanceof String) ? getHashValue(key, key
276: .hashCode()) : getStringValue((String) key));
277: }
278:
279: @Override
280: public V put(K key, V value) {
281: return (key == null) ? putNullSlot(value)
282: : (!(key instanceof String) ? putHashValue(key, value,
283: key.hashCode()) : putStringValue((String) key,
284: value));
285: }
286:
287: @Override
288: public V remove(Object key) {
289: return (key == null) ? removeNullSlot()
290: : (!(key instanceof String) ? removeHashValue(key, key
291: .hashCode()) : removeStringValue((String) key));
292: }
293:
294: @Override
295: public int size() {
296: return size;
297: }
298:
299: private void clearImpl() {
300: hashCodeMap = JavaScriptObject.createArray();
301: stringMap = JavaScriptObject.createObject();
302: nullSlotLive = false;
303: nullSlot = null;
304: size = 0;
305: }
306:
307: /**
308: * Returns the Map.Entry whose key is Object equal to <code>key</code>,
309: * provided that <code>key</code>'s hash code is <code>hashCode</code>;
310: * or <code>null</code> if no such Map.Entry exists at the specified
311: * hashCode.
312: */
313: private native V getHashValue(Object key, int hashCode) /*-{
314: var array = this.@java.util.HashMap::hashCodeMap[hashCode];
315: if (array) {
316: for (var i = 0, c = array.length; i < c; ++i) {
317: var entry = array[i];
318: var entryKey = entry.@java.util.Map$Entry::getKey()();
319: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
320: return entry.@java.util.Map$Entry::getValue()();
321: }
322: }
323: }
324: return null;
325: }-*/;
326:
327: /**
328: * Returns the value for the given key in the stringMap. Returns
329: * <code>null</code> if the specified key does not exist.
330: */
331: private native V getStringValue(String key) /*-{
332: return (_ = this.@java.util.HashMap::stringMap[':' + key]) == null ? null : _ ;
333: }-*/;
334:
335: /**
336: * Returns true if the a key exists in the hashCodeMap that is Object equal to
337: * <code>key</code>, provided that <code>key</code>'s hash code is
338: * <code>hashCode</code>.
339: */
340: private native boolean hasHashValue(Object key, int hashCode) /*-{
341: var array = this.@java.util.HashMap::hashCodeMap[hashCode];
342: if (array) {
343: for (var i = 0, c = array.length; i < c; ++i) {
344: var entry = array[i];
345: var entryKey = entry.@java.util.Map$Entry::getKey()();
346: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
347: return true;
348: }
349: }
350: }
351: return false;
352: }-*/;
353:
354: /**
355: * Returns true if the given key exists in the stringMap.
356: */
357: private native boolean hasStringValue(String key) /*-{
358: return (':' + key) in this.@java.util.HashMap::stringMap;
359: }-*/;
360:
361: /**
362: * Sets the specified key to the specified value in the hashCodeMap. Returns
363: * the value previously at that key. Returns <code>null</code> if the
364: * specified key did not exist.
365: */
366: private native V putHashValue(K key, V value, int hashCode) /*-{
367: var array = this.@java.util.HashMap::hashCodeMap[hashCode];
368: if (array) {
369: for (var i = 0, c = array.length; i < c; ++i) {
370: var entry = array[i];
371: var entryKey = entry.@java.util.Map$Entry::getKey()();
372: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
373: // Found an exact match, just update the existing entry
374: var previous = entry.@java.util.Map$Entry::getValue()();
375: entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value);
376: return previous;
377: }
378: }
379: } else {
380: array = this.@java.util.HashMap::hashCodeMap[hashCode] = [];
381: }
382: var entry = @java.util.MapEntryImpl::create(Ljava/lang/Object;Ljava/lang/Object;)(key, value);
383: array.push(entry);
384: ++this.@java.util.HashMap::size;
385: return null;
386: }-*/;
387:
388: private V putNullSlot(V value) {
389: V result = nullSlot;
390: nullSlot = value;
391: if (!nullSlotLive) {
392: nullSlotLive = true;
393: ++size;
394: }
395: return result;
396: }
397:
398: /**
399: * Sets the specified key to the specified value in the stringMap. Returns the
400: * value previously at that key. Returns <code>null</code> if the specified
401: * key did not exist.
402: */
403: private native V putStringValue(String key, V value) /*-{
404: key = ':' + key;
405: var result = this.@java.util.HashMap::stringMap[key];
406: this.@java.util.HashMap::stringMap[key] = value;
407: return (result === undefined) ?
408: (++this.@java.util.HashMap::size, null) : result;
409: }-*/;
410:
411: /**
412: * Removes the pair whose key is Object equal to <code>key</code> from
413: * <code>hashCodeMap</code>, provided that <code>key</code>'s hash code
414: * is <code>hashCode</code>. Returns the value that was associated with the
415: * removed key, or null if no such key existed.
416: */
417: private native V removeHashValue(Object key, int hashCode) /*-{
418: var array = this.@java.util.HashMap::hashCodeMap[hashCode];
419: if (array) {
420: for (var i = 0, c = array.length; i < c; ++i) {
421: var entry = array[i];
422: var entryKey = entry.@java.util.Map$Entry::getKey()();
423: if (@java.util.Utility::equalsWithNullCheck(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) {
424: if (array.length == 1) {
425: // remove the whole array
426: delete this.@java.util.HashMap::hashCodeMap[hashCode];
427: } else {
428: // splice out the entry we're removing
429: array.splice(i, 1);
430: }
431: --this.@java.util.HashMap::size;
432: return entry.@java.util.Map$Entry::getValue()();
433: }
434: }
435: }
436: return null;
437: }-*/;
438:
439: private V removeNullSlot() {
440: V result = nullSlot;
441: nullSlot = null;
442: if (nullSlotLive) {
443: nullSlotLive = false;
444: --size;
445: }
446: return result;
447: }
448:
449: /**
450: * Removes the specified key from the stringMap and returns the value that was
451: * previously there. Returns <code>null</code> if the specified key
452: * does not exist.
453: */
454: private native V removeStringValue(String key) /*-{
455: key = ':' + key;
456: var result = this.@java.util.HashMap::stringMap[key];
457: return (result === undefined) ? null :
458: (--this.@java.util.HashMap::size,
459: delete this.@java.util.HashMap::stringMap[key],
460: result);
461: }-*/;
462: }
|