1 files changed, 39 insertions, 597 deletions
diff --git a/guava/src/com/google/common/collect/HashBiMap.java b/guava/src/com/google/common/collect/HashBiMap.java
index 0620f45..26d11e1 100644
--- a/guava/src/com/google/common/collect/HashBiMap.java
+++ b/guava/src/com/google/common/collect/HashBiMap.java
@@ -1,657 +1,97 @@
 /*
  * Copyright (C) 2007 The Guava Authors
  *
- * 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
+ * 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.
+ * 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 com.google.common.collect;
 
-import static com.google.common.base.Preconditions.checkArgument;
-import static com.google.common.base.Preconditions.checkState;
-
 import com.google.common.annotations.GwtCompatible;
 import com.google.common.annotations.GwtIncompatible;
-import com.google.common.base.Objects;
 
 import java.io.IOException;
 import java.io.ObjectInputStream;
 import java.io.ObjectOutputStream;
-import java.io.Serializable;
-import java.util.AbstractMap;
-import java.util.Arrays;
-import java.util.ConcurrentModificationException;
-import java.util.Iterator;
+import java.util.HashMap;
 import java.util.Map;
-import java.util.NoSuchElementException;
-import java.util.Set;
 
 import javax.annotation.Nullable;
 
 /**
- * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
- * {@code HashBiMap} and its inverse are both serializable.
- *
- * <p>See the Guava User Guide article on <a href=
- * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#BiMap"> {@code BiMap}
- * </a>.
+ * A {@link BiMap} backed by two {@link HashMap} instances. This implementation
+ * allows null keys and values. A {@code HashBiMap} and its inverse are both
+ * serializable.
  *
- * @author Louis Wasserman
  * @author Mike Bostock
  * @since 2.0 (imported from Google Collections Library)
  */
 @GwtCompatible(emulated = true)
-public final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K, V>, Serializable {
+public final class HashBiMap<K, V> extends AbstractBiMap<K, V> {
 
   /**
-   * Returns a new, empty {@code HashBiMap} with the default initial capacity (16).
+   * Returns a new, empty {@code HashBiMap} with the default initial capacity
+   * (16).
    */
   public static <K, V> HashBiMap<K, V> create() {
-    return create(16);
+    return new HashBiMap<K, V>();
   }
 
   /**
    * Constructs a new, empty bimap with the specified expected size.
    *
    * @param expectedSize the expected number of entries
-   * @throws IllegalArgumentException if the specified expected size is negative
+   * @throws IllegalArgumentException if the specified expected size is
+   *     negative
    */
   public static <K, V> HashBiMap<K, V> create(int expectedSize) {
     return new HashBiMap<K, V>(expectedSize);
   }
 
   /**
-   * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
-   * initial capacity sufficient to hold the mappings in the specified map.
+   * Constructs a new bimap containing initial values from {@code map}. The
+   * bimap is created with an initial capacity sufficient to hold the mappings
+   * in the specified map.
    */
-  public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
+  public static <K, V> HashBiMap<K, V> create(
+      Map<? extends K, ? extends V> map) {
     HashBiMap<K, V> bimap = create(map.size());
     bimap.putAll(map);
     return bimap;
   }
 
-  private static final class BiEntry<K, V> {
-    final K key;
-    final int keyHash;
-
-    final V value;
-    final int valueHash;
-
-    @Nullable
-    BiEntry<K, V> nextInKToVBucket;
-
-    @Nullable
-    BiEntry<K, V> nextInVToKBucket;
-
-    BiEntry(K key, int keyHash, V value, int valueHash) {
-      this.key = key;
-      this.keyHash = keyHash;
-      this.value = value;
-      this.valueHash = valueHash;
-    }
+  private HashBiMap() {
+    super(new HashMap<K, V>(), new HashMap<V, K>());
   }
 
-  private static final double LOAD_FACTOR = 1.0;
-  
-  private transient BiEntry<K, V>[] hashTableKToV;
-  private transient BiEntry<K, V>[] hashTableVToK;
-  private transient int size;
-  private transient int mask;
-  private transient int modCount;
-
   private HashBiMap(int expectedSize) {
-    init(expectedSize);
-  }
-
-  private void init(int expectedSize) {
-    checkArgument(expectedSize >= 0, "expectedSize must be >= 0 but was %s", expectedSize);
-    int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR);
-    this.hashTableKToV = createTable(tableSize);
-    this.hashTableVToK = createTable(tableSize);
-    this.mask = tableSize - 1;
-    this.modCount = 0;
-    this.size = 0;
-  }
-
-  /**
-   * Finds and removes {@code entry} from the bucket linked lists in both the
-   * key-to-value direction and the value-to-key direction.
-   */
-  private void delete(BiEntry<K, V> entry) {
-    int keyBucket = entry.keyHash & mask;
-    BiEntry<K, V> prevBucketEntry = null;
-    for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket]; true;
-        bucketEntry = bucketEntry.nextInKToVBucket) {
-      if (bucketEntry == entry) {
-        if (prevBucketEntry == null) {
-          hashTableKToV[keyBucket] = entry.nextInKToVBucket;
-        } else {
-          prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
-        }
-        break;
-      }
-      prevBucketEntry = bucketEntry;
-    }
-
-    int valueBucket = entry.valueHash & mask;
-    prevBucketEntry = null;
-    for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];;
-        bucketEntry = bucketEntry.nextInVToKBucket) {
-      if (bucketEntry == entry) {
-        if (prevBucketEntry == null) {
-          hashTableVToK[valueBucket] = entry.nextInVToKBucket;
-        } else {
-          prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
-        }
-        break;
-      }
-      prevBucketEntry = bucketEntry;
-    }
-
-    size--;
-    modCount++;
-  }
-
-  private void insert(BiEntry<K, V> entry) {
-    int keyBucket = entry.keyHash & mask;
-    entry.nextInKToVBucket = hashTableKToV[keyBucket];
-    hashTableKToV[keyBucket] = entry;
-
-    int valueBucket = entry.valueHash & mask;
-    entry.nextInVToKBucket = hashTableVToK[valueBucket];
-    hashTableVToK[valueBucket] = entry;
-
-    size++;
-    modCount++;
-  }
-
-  private static int hash(@Nullable Object o) {
-    return Hashing.smear((o == null) ? 0 : o.hashCode());
+    super(
+        Maps.<K, V>newHashMapWithExpectedSize(expectedSize),
+        Maps.<V, K>newHashMapWithExpectedSize(expectedSize));
   }
 
-  private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
-    for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask]; entry != null;
-        entry = entry.nextInKToVBucket) {
-      if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
-        return entry;
-      }
-    }
-    return null;
-  }
-
-  private BiEntry<K, V> seekByValue(@Nullable Object value, int valueHash) {
-    for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask]; entry != null;
-        entry = entry.nextInVToKBucket) {
-      if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) {
-        return entry;
-      }
-    }
-    return null;
-  }
-
-  @Override
-  public boolean containsKey(@Nullable Object key) {
-    return seekByKey(key, hash(key)) != null;
-  }
-
-  @Override
-  public boolean containsValue(@Nullable Object value) {
-    return seekByValue(value, hash(value)) != null;
-  }
+  // Override these two methods to show that keys and values may be null
 
-  @Nullable
-  @Override
-  public V get(@Nullable Object key) {
-    BiEntry<K, V> entry = seekByKey(key, hash(key));
-    return (entry == null) ? null : entry.value;
+  @Override public V put(@Nullable K key, @Nullable V value) {
+    return super.put(key, value);
   }
 
-  @Override
-  public V put(@Nullable K key, @Nullable V value) {
-    return put(key, value, false);
-  }
-
-  @Override
-  public V forcePut(@Nullable K key, @Nullable V value) {
-    return put(key, value, true);
-  }
-
-  private V put(@Nullable K key, @Nullable V value, boolean force) {
-    int keyHash = hash(key);
-    int valueHash = hash(value);
-
-    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
-    if (oldEntryForKey != null && valueHash == oldEntryForKey.valueHash
-        && Objects.equal(value, oldEntryForKey.value)) {
-      return value;
-    }
-
-    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
-    if (oldEntryForValue != null) {
-      if (force) {
-        delete(oldEntryForValue);
-      } else {
-        throw new IllegalArgumentException("value already present: " + value);
-      }
-    }
-
-    if (oldEntryForKey != null) {
-      delete(oldEntryForKey);
-    }
-    BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
-    insert(newEntry);
-    rehashIfNecessary();
-    return (oldEntryForKey == null) ? null : oldEntryForKey.value;
-  }
-
-  @Nullable
-  private K putInverse(@Nullable V value, @Nullable K key, boolean force) {
-    int valueHash = hash(value);
-    int keyHash = hash(key);
-
-    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
-    if (oldEntryForValue != null && keyHash == oldEntryForValue.keyHash
-        && Objects.equal(key, oldEntryForValue.key)) {
-      return key;
-    }
-
-    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
-    if (oldEntryForKey != null) {
-      if (force) {
-        delete(oldEntryForKey);
-      } else {
-        throw new IllegalArgumentException("value already present: " + key);
-      }
-    }
-
-    if (oldEntryForValue != null) {
-      delete(oldEntryForValue);
-    }
-    BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
-    insert(newEntry);
-    rehashIfNecessary();
-    return (oldEntryForValue == null) ? null : oldEntryForValue.key;
-  }
-
-  private void rehashIfNecessary() {
-    BiEntry<K, V>[] oldKToV = hashTableKToV;
-    if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
-      int newTableSize = oldKToV.length * 2;
-
-      this.hashTableKToV = createTable(newTableSize);
-      this.hashTableVToK = createTable(newTableSize);
-      this.mask = newTableSize - 1;
-      this.size = 0;
-
-      for (int bucket = 0; bucket < oldKToV.length; bucket++) {
-        BiEntry<K, V> entry = oldKToV[bucket];
-        while (entry != null) {
-          BiEntry<K, V> nextEntry = entry.nextInKToVBucket;
-          insert(entry);
-          entry = nextEntry;
-        }
-      }
-      this.modCount++;
-    }
-  }
-
-  @SuppressWarnings("unchecked")
-  private BiEntry<K, V>[] createTable(int length) {
-    return new BiEntry[length];
-  }
-
-  @Override
-  public V remove(@Nullable Object key) {
-    BiEntry<K, V> entry = seekByKey(key, hash(key));
-    if (entry == null) {
-      return null;
-    } else {
-      delete(entry);
-      return entry.value;
-    }
-  }
-
-  @Override
-  public void clear() {
-    size = 0;
-    Arrays.fill(hashTableKToV, null);
-    Arrays.fill(hashTableVToK, null);
-    modCount++;
-  }
-
-  @Override
-  public int size() {
-    return size;
-  }
-
-  abstract class Itr<T> implements Iterator<T> {
-    int nextBucket = 0;
-    BiEntry<K, V> next = null;
-    BiEntry<K, V> toRemove = null;
-    int expectedModCount = modCount;
-
-    private void checkForConcurrentModification() {
-      if (modCount != expectedModCount) {
-        throw new ConcurrentModificationException();
-      }
-    }
-
-    @Override
-    public boolean hasNext() {
-      checkForConcurrentModification();
-      if (next != null) {
-        return true;
-      }
-      while (nextBucket < hashTableKToV.length) {
-        if (hashTableKToV[nextBucket] != null) {
-          next = hashTableKToV[nextBucket++];
-          return true;
-        }
-        nextBucket++;
-      }
-      return false;
-    }
-
-    @Override
-    public T next() {
-      checkForConcurrentModification();
-      if (!hasNext()) {
-        throw new NoSuchElementException();
-      }
-
-      BiEntry<K, V> entry = next;
-      next = entry.nextInKToVBucket;
-      toRemove = entry;
-      return output(entry);
-    }
-
-    @Override
-    public void remove() {
-      checkForConcurrentModification();
-      checkState(toRemove != null, "Only one remove() call allowed per call to next");
-      delete(toRemove);
-      expectedModCount = modCount;
-      toRemove = null;
-    }
-
-    abstract T output(BiEntry<K, V> entry);
-  }
-
-  @Override
-  public Set<K> keySet() {
-    return new KeySet();
-  }
-
-  private final class KeySet extends Maps.KeySet<K, V> {
-    @Override
-    Map<K, V> map() {
-      return HashBiMap.this;
-    }
-
-    @Override
-    public Iterator<K> iterator() {
-      return new Itr<K>() {
-        @Override
-        K output(BiEntry<K, V> entry) {
-          return entry.key;
-        }
-      };
-    }
-
-    @Override
-    public boolean remove(@Nullable Object o) {
-      BiEntry<K, V> entry = seekByKey(o, hash(o));
-      if (entry == null) {
-        return false;
-      } else {
-        delete(entry);
-        return true;
-      }
-    }
-  }
-
-  @Override
-  public Set<V> values() {
-    return inverse().keySet();
-  }
-
-  @Override
-  public Set<Entry<K, V>> entrySet() {
-    return new EntrySet();
-  }
-
-  private final class EntrySet extends Maps.EntrySet<K, V> {
-    @Override
-    Map<K, V> map() {
-      return HashBiMap.this;
-    }
-
-    @Override
-    public Iterator<Entry<K, V>> iterator() {
-      return new Itr<Entry<K, V>>() {
-        @Override
-        Entry<K, V> output(BiEntry<K, V> entry) {
-          return new MapEntry(entry);
-        }
-
-        class MapEntry extends AbstractMapEntry<K, V> {
-          BiEntry<K, V> delegate;
-
-          MapEntry(BiEntry<K, V> entry) {
-            this.delegate = entry;
-          }
-
-          @Override public K getKey() {
-            return delegate.key;
-          }
-
-          @Override public V getValue() {
-            return delegate.value;
-          }
-
-          @Override public V setValue(V value) {
-            V oldValue = delegate.value;
-            int valueHash = hash(value);
-            if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) {
-              return value;
-            }
-            checkArgument(
-                seekByValue(value, valueHash) == null, "value already present: %s", value);
-            delete(delegate);
-            BiEntry<K, V> newEntry =
-                new BiEntry<K, V>(delegate.key, delegate.keyHash, value, valueHash);
-            insert(newEntry);
-            expectedModCount = modCount;
-            if (toRemove == delegate) {
-              toRemove = newEntry;
-            }
-            delegate = newEntry;
-            return oldValue;
-          }
-        }
-      };
-    }
-  }
-
-  private transient BiMap<V, K> inverse;
-
-  @Override
-  public BiMap<V, K> inverse() {
-    return (inverse == null) ? inverse = new Inverse() : inverse;
-  }
-
-  private final class Inverse extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
-    BiMap<K, V> forward() {
-      return HashBiMap.this;
-    }
-
-    @Override
-    public int size() {
-      return size;
-    }
-
-    @Override
-    public void clear() {
-      forward().clear();
-    }
-
-    @Override
-    public boolean containsKey(@Nullable Object value) {
-      return forward().containsValue(value);
-    }
-
-    @Override
-    public K get(@Nullable Object value) {
-      BiEntry<K, V> entry = seekByValue(value, hash(value));
-      return (entry == null) ? null : entry.key;
-    }
-
-    @Override
-    public K put(@Nullable V value, @Nullable K key) {
-      return putInverse(value, key, false);
-    }
-
-    @Override
-    public K forcePut(@Nullable V value, @Nullable K key) {
-      return putInverse(value, key, true);
-    }
-
-    @Override
-    public K remove(@Nullable Object value) {
-      BiEntry<K, V> entry = seekByValue(value, hash(value));
-      if (entry == null) {
-        return null;
-      } else {
-        delete(entry);
-        return entry.key;
-      }
-    }
-
-    @Override
-    public BiMap<K, V> inverse() {
-      return forward();
-    }
-
-    @Override
-    public Set<V> keySet() {
-      return new InverseKeySet();
-    }
-
-    private final class InverseKeySet extends Maps.KeySet<V, K> {
-      @Override
-      Map<V, K> map() {
-        return Inverse.this;
-      }
-
-      @Override
-      public boolean remove(@Nullable Object o) {
-        BiEntry<K, V> entry = seekByValue(o, hash(o));
-        if (entry == null) {
-          return false;
-        } else {
-          delete(entry);
-          return true;
-        }
-      }
-
-      @Override
-      public Iterator<V> iterator() {
-        return new Itr<V>() {
-          @Override V output(BiEntry<K, V> entry) {
-            return entry.value;
-          }
-        };
-      }
-    }
-
-    @Override
-    public Set<K> values() {
-      return forward().keySet();
-    }
-
-    @Override
-    public Set<Entry<V, K>> entrySet() {
-      return new Maps.EntrySet<V, K>() {
-
-        @Override
-        Map<V, K> map() {
-          return Inverse.this;
-        }
-
-        @Override
-        public Iterator<Entry<V, K>> iterator() {
-          return new Itr<Entry<V, K>>() {
-            @Override
-            Entry<V, K> output(BiEntry<K, V> entry) {
-              return new InverseEntry(entry);
-            }
-
-            class InverseEntry extends AbstractMapEntry<V, K> {
-              BiEntry<K, V> delegate;
-
-              InverseEntry(BiEntry<K, V> entry) {
-                this.delegate = entry;
-              }
-
-              @Override
-              public V getKey() {
-                return delegate.value;
-              }
-
-              @Override
-              public K getValue() {
-                return delegate.key;
-              }
-
-              @Override
-              public K setValue(K key) {
-                K oldKey = delegate.key;
-                int keyHash = hash(key);
-                if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) {
-                  return key;
-                }
-                checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key);
-                delete(delegate);
-                BiEntry<K, V> newEntry =
-                    new BiEntry<K, V>(key, keyHash, delegate.value, delegate.valueHash);
-                insert(newEntry);
-                expectedModCount = modCount;
-                // This is safe because entries can only get bumped up to earlier in the iteration,
-                // so they can't get revisited.
-                return oldKey;
-              }
-            }
-          };
-        }
-      };
-    }
-
-    Object writeReplace() {
-      return new InverseSerializedForm<K, V>(HashBiMap.this);
-    }
-  }
-
-  private static final class InverseSerializedForm<K, V> implements Serializable {
-    private final HashBiMap<K, V> bimap;
-
-    InverseSerializedForm(HashBiMap<K, V> bimap) {
-      this.bimap = bimap;
-    }
-
-    Object readResolve() {
-      return bimap.inverse();
-    }
+  @Override public V forcePut(@Nullable K key, @Nullable V value) {
+    return super.forcePut(key, value);
   }
 
   /**
-   * @serialData the number of entries, first key, first value, second key, second value, and so on.
+   * @serialData the number of entries, first key, first value, second key,
+   *     second value, and so on.
    */
   @GwtIncompatible("java.io.ObjectOutputStream")
   private void writeObject(ObjectOutputStream stream) throws IOException {
@@ -660,10 +100,12 @@ public final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K,
   }
 
   @GwtIncompatible("java.io.ObjectInputStream")
-  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
+  private void readObject(ObjectInputStream stream)
+      throws IOException, ClassNotFoundException {
     stream.defaultReadObject();
     int size = Serialization.readCount(stream);
-    init(size);
+    setDelegates(Maps.<K, V>newHashMapWithExpectedSize(size),
+        Maps.<V, K>newHashMapWithExpectedSize(size));
     Serialization.populateMap(this, stream, size);
   }