1 files changed, 119 insertions, 19 deletions

diff --git a/guava/src/com/google/common/collect/RegularImmutableMap.java b/guava/src/com/google/common/collect/RegularImmutableMap.java
index 6d9be99..e2b7150 100644
--- a/guava/src/com/google/common/collect/RegularImmutableMap.java
+++ b/guava/src/com/google/common/collect/RegularImmutableMap.java
@@ -19,6 +19,8 @@ package com.google.common.collect;
 import static com.google.common.base.Preconditions.checkArgument;
 
 import com.google.common.annotations.GwtCompatible;
+import com.google.common.collect.ImmutableSet.ArrayImmutableSet;
+import com.google.common.collect.ImmutableSet.TransformedImmutableSet;
 
 import javax.annotation.Nullable;
 import javax.annotation.concurrent.Immutable;
@@ -39,6 +41,7 @@ final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
   private final transient LinkedEntry<K, V>[] table;
   // 'and' with an int to get a table index
   private final transient int mask;
+  private final transient int keySetHashCode;
 
   // TODO(gak): investigate avoiding the creation of ImmutableEntries since we
   // re-copy them anyway.
@@ -46,16 +49,18 @@ final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
     int size = immutableEntries.length;
     entries = createEntryArray(size);
 
-    int tableSize = Hashing.closedTableSize(size, MAX_LOAD_FACTOR);
+    int tableSize = chooseTableSize(size);
     table = createEntryArray(tableSize);
     mask = tableSize - 1;
 
+    int keySetHashCodeMutable = 0;
     for (int entryIndex = 0; entryIndex < size; entryIndex++) {
       // each of our 6 callers carefully put only Entry<K, V>s into the array!
       @SuppressWarnings("unchecked")
       Entry<K, V> entry = (Entry<K, V>) immutableEntries[entryIndex];
       K key = entry.getKey();
       int keyHashCode = key.hashCode();
+      keySetHashCodeMutable += keyHashCode;
       int tableIndex = Hashing.smear(keyHashCode) & mask;
       @Nullable LinkedEntry<K, V> existing = table[tableIndex];
       // prepend, not append, so the entries can be immutable
@@ -68,14 +73,15 @@ final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
         existing = existing.next();
       }
     }
+    keySetHashCode = keySetHashCodeMutable;
   }
 
-  /**
-   * Closed addressing tends to perform well even with high load factors.
-   * Being conservative here ensures that the table is still likely to be
-   * relatively sparse (hence it misses fast) while saving space.
-   */
-  private static final double MAX_LOAD_FACTOR = 1.2;
+  private static int chooseTableSize(int size) {
+    // least power of 2 greater than size
+    int tableSize = Integer.highestOneBit(size) << 1;
+    checkArgument(tableSize > 0, "table too large: %s", size);
+    return tableSize;
+  }
 
   /**
    * Creates a {@link LinkedEntry} array to hold parameterized entries. The
@@ -160,31 +166,125 @@ final class RegularImmutableMap<K, V> extends ImmutableMap<K, V> {
   public int size() {
     return entries.length;
   }
-  
+
+  @Override public boolean isEmpty() {
+    return false;
+  }
+
+  @Override public boolean containsValue(@Nullable Object value) {
+    if (value == null) {
+      return false;
+    }
+    for (Entry<K, V> entry : entries) {
+      if (entry.getValue().equals(value)) {
+        return true;
+      }
+    }
+    return false;
+  }
+
   @Override boolean isPartialView() {
     return false;
   }
 
-  @Override
-  ImmutableSet<Entry<K, V>> createEntrySet() {
-    return new EntrySet();
+  private transient ImmutableSet<Entry<K, V>> entrySet;
+
+  @Override public ImmutableSet<Entry<K, V>> entrySet() {
+    ImmutableSet<Entry<K, V>> es = entrySet;
+    return (es == null) ? (entrySet = new EntrySet<K, V>(this)) : es;
   }
 
   @SuppressWarnings("serial") // uses writeReplace(), not default serialization
-  private class EntrySet extends ImmutableMapEntrySet<K, V> {
-    @Override ImmutableMap<K, V> map() {
-      return RegularImmutableMap.this;
+  private static class EntrySet<K, V> extends ArrayImmutableSet<Entry<K, V>> {
+    final transient RegularImmutableMap<K, V> map;
+
+    EntrySet(RegularImmutableMap<K, V> map) {
+      super(map.entries);
+      this.map = map;
     }
 
-    @Override
-    public UnmodifiableIterator<Entry<K, V>> iterator() {
-      return asList().iterator();
+    @Override public boolean contains(Object target) {
+      if (target instanceof Entry) {
+        Entry<?, ?> entry = (Entry<?, ?>) target;
+        V mappedValue = map.get(entry.getKey());
+        return mappedValue != null && mappedValue.equals(entry.getValue());
+      }
+      return false;
+    }
+  }
+
+  private transient ImmutableSet<K> keySet;
+
+  @Override public ImmutableSet<K> keySet() {
+    ImmutableSet<K> ks = keySet;
+    return (ks == null) ? (keySet = new KeySet<K, V>(this)) : ks;
+  }
+
+  @SuppressWarnings("serial") // uses writeReplace(), not default serialization
+  private static class KeySet<K, V>
+      extends TransformedImmutableSet<Entry<K, V>, K> {
+    final RegularImmutableMap<K, V> map;
+
+    KeySet(RegularImmutableMap<K, V> map) {
+      super(map.entries, map.keySetHashCode);
+      this.map = map;
+    }
+
+    @Override K transform(Entry<K, V> element) {
+      return element.getKey();
+    }
+
+    @Override public boolean contains(Object target) {
+      return map.containsKey(target);
+    }
+
+    @Override boolean isPartialView() {
+      return true;
+    }
+  }
+
+  private transient ImmutableCollection<V> values;
+
+  @Override public ImmutableCollection<V> values() {
+    ImmutableCollection<V> v = values;
+    return (v == null) ? (values = new Values<V>(this)) : v;
+  }
+
+  @SuppressWarnings("serial") // uses writeReplace(), not default serialization
+  private static class Values<V> extends ImmutableCollection<V> {
+    final RegularImmutableMap<?, V> map;
+
+    Values(RegularImmutableMap<?, V> map) {
+      this.map = map;
     }
 
     @Override
-    ImmutableList<Entry<K, V>> createAsList() {
-      return new RegularImmutableAsList<Entry<K, V>>(this, entries);
+    public int size() {
+      return map.entries.length;
+    }
+
+    @Override public UnmodifiableIterator<V> iterator() {
+      return new AbstractIndexedListIterator<V>(map.entries.length) {
+        @Override protected V get(int index) {
+          return map.entries[index].getValue();
+        }
+      };
     }
+
+    @Override public boolean contains(Object target) {
+      return map.containsValue(target);
+    }
+
+    @Override boolean isPartialView() {
+      return true;
+    }
+  }
+
+  @Override public String toString() {
+    StringBuilder result
+        = Collections2.newStringBuilderForCollection(size()).append('{');
+    Collections2.STANDARD_JOINER.appendTo(result, entries);
+    return result.append('}').toString();
   }
 
   // This class is never actually serialized directly, but we have to make the