| /* |
| * Copyright 2008 Google Inc. |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| * use this file except in compliance with the License. You may obtain a copy of |
| * the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| * License for the specific language governing permissions and limitations under |
| * the License. |
| */ |
| package java.util; |
| |
| import com.google.gwt.core.client.JavaScriptObject; |
| |
| /** |
| * Implementation of Map interface based on a hash table. <a |
| * href="http://java.sun.com/j2se/1.5.0/docs/api/java/util/HashMap.html">[Sun |
| * docs]</a> |
| * |
| * @param <K> key type |
| * @param <V> value type |
| */ |
| abstract class AbstractHashMap<K, V> extends AbstractMap<K, V> { |
| /* |
| * Implementation notes: |
| * |
| * String keys are stored in a separate map from non-String keys. String keys |
| * are mapped to their values via a JS associative map, stringMap. String keys |
| * could collide with intrinsic properties (like watch, constructor) so we |
| * prepend each key with a ':' inside of stringMap. |
| * |
| * Integer keys are used to index all non-string keys. A key's hashCode is the |
| * index in hashCodeMap which should contain that key. Since several keys may |
| * have the same hash, each value in hashCodeMap is actually an array |
| * containing all entries whose keys share the same hash. |
| */ |
| private final class EntrySet extends AbstractSet<Entry<K, V>> { |
| |
| @Override |
| public void clear() { |
| AbstractHashMap.this.clear(); |
| } |
| |
| @Override |
| public boolean contains(Object o) { |
| if (o instanceof Map.Entry) { |
| Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; |
| Object key = entry.getKey(); |
| if (AbstractHashMap.this.containsKey(key)) { |
| Object value = AbstractHashMap.this.get(key); |
| return AbstractHashMap.this.equals(entry.getValue(), value); |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public Iterator<Entry<K, V>> iterator() { |
| return new EntrySetIterator(); |
| } |
| |
| @Override |
| public boolean remove(Object entry) { |
| if (contains(entry)) { |
| Object key = ((Map.Entry<?, ?>) entry).getKey(); |
| AbstractHashMap.this.remove(key); |
| return true; |
| } |
| return false; |
| } |
| |
| @Override |
| public int size() { |
| return AbstractHashMap.this.size(); |
| } |
| } |
| |
| /** |
| * Iterator for <code>EntrySetImpl</code>. |
| */ |
| private final class EntrySetIterator implements Iterator<Entry<K, V>> { |
| private final Iterator<Map.Entry<K, V>> iter; |
| private Map.Entry<K, V> last = null; |
| |
| /** |
| * Constructor for <code>EntrySetIterator</code>. |
| */ |
| public EntrySetIterator() { |
| List<Map.Entry<K, V>> list = new ArrayList<Map.Entry<K, V>>(); |
| if (nullSlotLive) { |
| list.add(new MapEntryNull()); |
| } |
| addAllStringEntries(list); |
| addAllHashEntries(list); |
| this.iter = list.iterator(); |
| } |
| |
| public boolean hasNext() { |
| return iter.hasNext(); |
| } |
| |
| public Map.Entry<K, V> next() { |
| return last = iter.next(); |
| } |
| |
| public void remove() { |
| if (last == null) { |
| throw new IllegalStateException("Must call next() before remove()."); |
| } else { |
| iter.remove(); |
| AbstractHashMap.this.remove(last.getKey()); |
| last = null; |
| } |
| } |
| } |
| |
| private final class MapEntryNull extends AbstractMapEntry<K, V> { |
| |
| public K getKey() { |
| return null; |
| } |
| |
| public V getValue() { |
| return nullSlot; |
| } |
| |
| public V setValue(V object) { |
| return putNullSlot(object); |
| } |
| } |
| |
| // Instantiated from JSNI |
| @SuppressWarnings("unused") |
| private final class MapEntryString extends AbstractMapEntry<K, V> { |
| |
| private final String key; |
| |
| public MapEntryString(String key) { |
| this.key = key; |
| } |
| |
| @SuppressWarnings("unchecked") |
| public K getKey() { |
| return (K) key; |
| } |
| |
| public V getValue() { |
| return getStringValue(key); |
| } |
| |
| public V setValue(V object) { |
| return putStringValue(key, object); |
| } |
| } |
| |
| /** |
| * A map of integral hashCodes onto entries. |
| */ |
| // Used from JSNI. |
| @SuppressWarnings("unused") |
| private transient JavaScriptObject hashCodeMap; |
| |
| /** |
| * This is the slot that holds the value associated with the "null" key. |
| */ |
| private transient V nullSlot; |
| |
| private transient boolean nullSlotLive; |
| |
| private int size; |
| |
| /** |
| * A map of Strings onto values. |
| */ |
| // Used from JSNI. |
| @SuppressWarnings("unused") |
| private transient JavaScriptObject stringMap; |
| |
| { |
| clearImpl(); |
| } |
| |
| public AbstractHashMap() { |
| } |
| |
| public AbstractHashMap(int ignored) { |
| // This implementation of HashMap has no need of initial capacities. |
| this(ignored, 0); |
| } |
| |
| public AbstractHashMap(int ignored, float alsoIgnored) { |
| // This implementation of HashMap has no need of load factors or capacities. |
| if (ignored < 0 || alsoIgnored < 0) { |
| throw new IllegalArgumentException( |
| "initial capacity was negative or load factor was non-positive"); |
| } |
| } |
| |
| public AbstractHashMap(Map<? extends K, ? extends V> toBeCopied) { |
| this.putAll(toBeCopied); |
| } |
| |
| @Override |
| public void clear() { |
| clearImpl(); |
| } |
| |
| public abstract Object clone(); |
| |
| @Override |
| public boolean containsKey(Object key) { |
| return (key == null) ? nullSlotLive : (!(key instanceof String) |
| ? hasHashValue(key, getHashCode(key)) : hasStringValue((String) key)); |
| } |
| |
| @Override |
| public boolean containsValue(Object value) { |
| if (nullSlotLive && equals(nullSlot, value)) { |
| return true; |
| } else if (containsStringValue(value)) { |
| return true; |
| } else if (containsHashValue(value)) { |
| return true; |
| } |
| return false; |
| } |
| |
| @Override |
| public Set<Map.Entry<K, V>> entrySet() { |
| return new EntrySet(); |
| } |
| |
| @Override |
| public V get(Object key) { |
| return (key == null) ? nullSlot : (!(key instanceof String) ? getHashValue( |
| key, getHashCode(key)) : getStringValue((String) key)); |
| } |
| |
| @Override |
| public V put(K key, V value) { |
| return (key == null) ? putNullSlot(value) : (!(key instanceof String) |
| ? putHashValue(key, value, getHashCode(key)) : putStringValue( |
| (String) key, value)); |
| } |
| |
| @Override |
| public V remove(Object key) { |
| return (key == null) ? removeNullSlot() : (!(key instanceof String) |
| ? removeHashValue(key, getHashCode(key)) |
| : removeStringValue((String) key)); |
| } |
| |
| @Override |
| public int size() { |
| return size; |
| } |
| |
| /** |
| * Subclasses must override to return a whether or not two keys or values are |
| * equal. |
| */ |
| protected abstract boolean equals(Object value1, Object value2); |
| |
| /** |
| * Subclasses must override to return a hash code for a given key. The key is |
| * guaranteed to be non-null and not a String. |
| */ |
| protected abstract int getHashCode(Object key); |
| |
| private native void addAllHashEntries(Collection<?> dest) /*-{ |
| var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap; |
| for (var hashCode in hashCodeMap) { |
| // sanity check that it's really an integer |
| var hashCodeInt = parseInt(hashCode, 10); |
| if (hashCode == hashCodeInt) { |
| var array = hashCodeMap[hashCodeInt]; |
| for (var i = 0, c = array.length; i < c; ++i) { |
| dest.@java.util.Collection::add(Ljava/lang/Object;)(array[i]); |
| } |
| } |
| } |
| }-*/; |
| |
| private native void addAllStringEntries(Collection<?> dest) /*-{ |
| var stringMap = this.@java.util.AbstractHashMap::stringMap; |
| for (var key in stringMap) { |
| // only keys that start with a colon ':' count |
| if (key.charCodeAt(0) == 58) { |
| var entry = @java.util.AbstractHashMap$MapEntryString::new(Ljava/util/AbstractHashMap;Ljava/lang/String;)(this, key.substring(1)); |
| dest.@java.util.Collection::add(Ljava/lang/Object;)(entry); |
| } |
| } |
| }-*/; |
| |
| private void clearImpl() { |
| hashCodeMap = JavaScriptObject.createArray(); |
| stringMap = JavaScriptObject.createObject(); |
| nullSlotLive = false; |
| nullSlot = null; |
| size = 0; |
| } |
| |
| /** |
| * Returns true if hashCodeMap contains any Map.Entry whose value is Object |
| * equal to <code>value</code>. |
| */ |
| private native boolean containsHashValue(Object value) /*-{ |
| var hashCodeMap = this.@java.util.AbstractHashMap::hashCodeMap; |
| for (var hashCode in hashCodeMap) { |
| // sanity check that it's really one of ours |
| var hashCodeInt = parseInt(hashCode, 10); |
| if (hashCode == hashCodeInt) { |
| var array = hashCodeMap[hashCodeInt]; |
| for (var i = 0, c = array.length; i < c; ++i) { |
| var entry = array[i]; |
| var entryValue = entry.@java.util.Map$Entry::getValue()(); |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) { |
| return true; |
| } |
| } |
| } |
| } |
| return false; |
| }-*/; |
| |
| /** |
| * Returns true if stringMap contains any key whose value is Object equal to |
| * <code>value</code>. |
| */ |
| private native boolean containsStringValue(Object value) /*-{ |
| var stringMap = this.@java.util.AbstractHashMap::stringMap; |
| for (var key in stringMap) { |
| // only keys that start with a colon ':' count |
| if (key.charCodeAt(0) == 58) { |
| var entryValue = stringMap[key]; |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(value, entryValue)) { |
| return true; |
| } |
| } |
| } |
| return false; |
| }-*/; |
| |
| /** |
| * Bridge method from JSNI that keeps us from having to make polymorphic calls |
| * in JSNI. By putting the polymorphism in Java code, the compiler can do a |
| * better job of optimizing in most cases. |
| */ |
| @SuppressWarnings("unused") |
| private boolean equalsBridge(Object value1, Object value2) { |
| return equals(value1, value2); |
| } |
| |
| /** |
| * Returns the Map.Entry whose key is Object equal to <code>key</code>, |
| * provided that <code>key</code>'s hash code is <code>hashCode</code>; |
| * or <code>null</code> if no such Map.Entry exists at the specified |
| * hashCode. |
| */ |
| private native V getHashValue(Object key, int hashCode) /*-{ |
| var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode]; |
| if (array) { |
| for (var i = 0, c = array.length; i < c; ++i) { |
| var entry = array[i]; |
| var entryKey = entry.@java.util.Map$Entry::getKey()(); |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) { |
| return entry.@java.util.Map$Entry::getValue()(); |
| } |
| } |
| } |
| return null; |
| }-*/; |
| |
| /** |
| * Returns the value for the given key in the stringMap. Returns |
| * <code>null</code> if the specified key does not exist. |
| */ |
| private native V getStringValue(String key) /*-{ |
| return this.@java.util.AbstractHashMap::stringMap[':' + key]; |
| }-*/; |
| |
| /** |
| * Returns true if the a key exists in the hashCodeMap that is Object equal to |
| * <code>key</code>, provided that <code>key</code>'s hash code is |
| * <code>hashCode</code>. |
| */ |
| private native boolean hasHashValue(Object key, int hashCode) /*-{ |
| var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode]; |
| if (array) { |
| for (var i = 0, c = array.length; i < c; ++i) { |
| var entry = array[i]; |
| var entryKey = entry.@java.util.Map$Entry::getKey()(); |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) { |
| return true; |
| } |
| } |
| } |
| return false; |
| }-*/; |
| |
| /** |
| * Returns true if the given key exists in the stringMap. |
| */ |
| private native boolean hasStringValue(String key) /*-{ |
| return (':' + key) in this.@java.util.AbstractHashMap::stringMap; |
| }-*/; |
| |
| /** |
| * Sets the specified key to the specified value in the hashCodeMap. Returns |
| * the value previously at that key. Returns <code>null</code> if the |
| * specified key did not exist. |
| */ |
| private native V putHashValue(K key, V value, int hashCode) /*-{ |
| var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode]; |
| if (array) { |
| for (var i = 0, c = array.length; i < c; ++i) { |
| var entry = array[i]; |
| var entryKey = entry.@java.util.Map$Entry::getKey()(); |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) { |
| // Found an exact match, just update the existing entry |
| var previous = entry.@java.util.Map$Entry::getValue()(); |
| entry.@java.util.Map$Entry::setValue(Ljava/lang/Object;)(value); |
| return previous; |
| } |
| } |
| } else { |
| array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode] = []; |
| } |
| var entry = @java.util.MapEntryImpl::new(Ljava/lang/Object;Ljava/lang/Object;)(key, value); |
| array.push(entry); |
| ++this.@java.util.AbstractHashMap::size; |
| return null; |
| }-*/; |
| |
| private V putNullSlot(V value) { |
| V result = nullSlot; |
| nullSlot = value; |
| if (!nullSlotLive) { |
| nullSlotLive = true; |
| ++size; |
| } |
| return result; |
| } |
| |
| /** |
| * Sets the specified key to the specified value in the stringMap. Returns the |
| * value previously at that key. Returns <code>null</code> if the specified |
| * key did not exist. |
| */ |
| private native V putStringValue(String key, V value) /*-{ |
| var result, stringMap = this.@java.util.AbstractHashMap::stringMap; |
| key = ':' + key; |
| if (key in stringMap) { |
| result = stringMap[key]; |
| } else { |
| ++this.@java.util.AbstractHashMap::size; |
| } |
| stringMap[key] = value; |
| return result; |
| }-*/; |
| |
| /** |
| * Removes the pair whose key is Object equal to <code>key</code> from |
| * <code>hashCodeMap</code>, provided that <code>key</code>'s hash code |
| * is <code>hashCode</code>. Returns the value that was associated with the |
| * removed key, or null if no such key existed. |
| */ |
| private native V removeHashValue(Object key, int hashCode) /*-{ |
| var array = this.@java.util.AbstractHashMap::hashCodeMap[hashCode]; |
| if (array) { |
| for (var i = 0, c = array.length; i < c; ++i) { |
| var entry = array[i]; |
| var entryKey = entry.@java.util.Map$Entry::getKey()(); |
| if (this.@java.util.AbstractHashMap::equalsBridge(Ljava/lang/Object;Ljava/lang/Object;)(key, entryKey)) { |
| if (array.length == 1) { |
| // remove the whole array |
| delete this.@java.util.AbstractHashMap::hashCodeMap[hashCode]; |
| } else { |
| // splice out the entry we're removing |
| array.splice(i, 1); |
| } |
| --this.@java.util.AbstractHashMap::size; |
| return entry.@java.util.Map$Entry::getValue()(); |
| } |
| } |
| } |
| return null; |
| }-*/; |
| |
| private V removeNullSlot() { |
| V result = nullSlot; |
| nullSlot = null; |
| if (nullSlotLive) { |
| nullSlotLive = false; |
| --size; |
| } |
| return result; |
| } |
| |
| /** |
| * Removes the specified key from the stringMap and returns the value that was |
| * previously there. Returns <code>null</code> if the specified key does not |
| * exist. |
| */ |
| private native V removeStringValue(String key) /*-{ |
| var result, stringMap = this.@java.util.AbstractHashMap::stringMap; |
| key = ':' + key; |
| if (key in stringMap) { |
| result = stringMap[key]; |
| --this.@java.util.AbstractHashMap::size; |
| delete stringMap[key]; |
| } |
| return result; |
| }-*/; |
| } |