am 84fb43aa: Merge "Revert "Upgraded Guava to unmodified v14.0.1""

* commit '84fb43aa6a1e752487f2624055ff26b1b6b7c043':
  Revert "Upgraded Guava to unmodified v14.0.1"

1 files changed, 280 insertions, 172 deletions

diff --git a/guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/LinkedListMultimap.java b/guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/LinkedListMultimap.java
index f51d292..2273535 100644
--- a/guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/LinkedListMultimap.java
+++ b/guava-gwt/src-super/com/google/common/collect/super/com/google/common/collect/LinkedListMultimap.java
@@ -17,7 +17,9 @@
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
+import static com.google.common.base.Preconditions.checkNotNull;
 import static com.google.common.base.Preconditions.checkState;
+import static com.google.common.collect.Multisets.setCountImpl;
 import static java.util.Collections.unmodifiableList;
 
 import com.google.common.annotations.GwtCompatible;
@@ -25,10 +27,11 @@ import com.google.common.base.Objects;
 import com.google.common.base.Preconditions;
 
 import java.io.Serializable;
+import java.util.AbstractCollection;
+import java.util.AbstractMap;
 import java.util.AbstractSequentialList;
+import java.util.AbstractSet;
 import java.util.Collection;
-import java.util.ConcurrentModificationException;
-import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
 import java.util.ListIterator;
@@ -88,10 +91,6 @@ import javax.annotation.Nullable;
  * update operations, wrap your multimap with a call to {@link
  * Multimaps#synchronizedListMultimap}.
  *
- * <p>See the Guava User Guide article on <a href=
- * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
- * {@code Multimap}</a>.
- *
  * @author Mike Bostock
  * @since 2.0 (imported from Google Collections Library)
  */
@@ -122,32 +121,12 @@ public class LinkedListMultimap<K, V>
       return key + "=" + value;
     }
   }
-  
-  private static class KeyList<K, V> {
-    Node<K, V> head;
-    Node<K, V> tail;
-    int count;
-    
-    KeyList(Node<K, V> firstNode) {
-      this.head = firstNode;
-      this.tail = firstNode;
-      firstNode.previousSibling = null;
-      firstNode.nextSibling = null;
-      this.count = 1;
-    }
-  }
 
   private transient Node<K, V> head; // the head for all keys
   private transient Node<K, V> tail; // the tail for all keys
-  private transient Map<K, KeyList<K, V>> keyToKeyList;
-  private transient int size;
-  
-  /*
-   * Tracks modifications to keyToKeyList so that addition or removal of keys invalidates
-   * preexisting iterators. This does *not* track simple additions and removals of values
-   * that are not the first to be added or last to be removed for their key.
-   */
-  private transient int modCount;
+  private transient Multiset<K> keyCount; // the number of values for each key
+  private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key
+  private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key
 
   /**
    * Creates a new, empty {@code LinkedListMultimap} with the default initial
@@ -181,11 +160,15 @@ public class LinkedListMultimap<K, V>
   }
 
   LinkedListMultimap() {
-    keyToKeyList = Maps.newHashMap();
+    keyCount = LinkedHashMultiset.create();
+    keyToKeyHead = Maps.newHashMap();
+    keyToKeyTail = Maps.newHashMap();
   }
 
   private LinkedListMultimap(int expectedKeys) {
-    keyToKeyList = new HashMap<K, KeyList<K, V>>(expectedKeys);
+    keyCount = LinkedHashMultiset.create(expectedKeys);
+    keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys);
+    keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys);
   }
 
   private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
@@ -204,32 +187,27 @@ public class LinkedListMultimap<K, V>
     Node<K, V> node = new Node<K, V>(key, value);
     if (head == null) { // empty list
       head = tail = node;
-      keyToKeyList.put(key, new KeyList<K, V>(node));
-      modCount++;
+      keyToKeyHead.put(key, node);
+      keyToKeyTail.put(key, node);
     } else if (nextSibling == null) { // non-empty list, add to tail
       tail.next = node;
       node.previous = tail;
-      tail = node;
-      KeyList<K, V> keyList = keyToKeyList.get(key);
-      if (keyList == null) {
-        keyToKeyList.put(key, keyList = new KeyList<K, V>(node));
-        modCount++;
+      Node<K, V> keyTail = keyToKeyTail.get(key);
+      if (keyTail == null) { // first for this key
+        keyToKeyHead.put(key, node);
       } else {
-        keyList.count++;
-        Node<K, V> keyTail = keyList.tail;
         keyTail.nextSibling = node;
         node.previousSibling = keyTail;
-        keyList.tail = node;
       }
+      keyToKeyTail.put(key, node);
+      tail = node;
     } else { // non-empty list, insert before nextSibling
-      KeyList<K, V> keyList = keyToKeyList.get(key);
-      keyList.count++;
       node.previous = nextSibling.previous;
       node.previousSibling = nextSibling.previousSibling;
       node.next = nextSibling;
       node.nextSibling = nextSibling;
       if (nextSibling.previousSibling == null) { // nextSibling was key head
-        keyToKeyList.get(key).head = node;
+        keyToKeyHead.put(key, node);
       } else {
         nextSibling.previousSibling.nextSibling = node;
       }
@@ -241,7 +219,7 @@ public class LinkedListMultimap<K, V>
       nextSibling.previous = node;
       nextSibling.previousSibling = node;
     }
-    size++;
+    keyCount.add(key);
     return node;
   }
 
@@ -261,27 +239,21 @@ public class LinkedListMultimap<K, V>
     } else { // node was tail
       tail = node.previous;
     }
-    if (node.previousSibling == null && node.nextSibling == null) {
-      KeyList<K, V> keyList = keyToKeyList.remove(node.key);
-      keyList.count = 0;
-      modCount++;
+    if (node.previousSibling != null) {
+      node.previousSibling.nextSibling = node.nextSibling;
+    } else if (node.nextSibling != null) { // node was key head
+      keyToKeyHead.put(node.key, node.nextSibling);
     } else {
-      KeyList<K, V> keyList = keyToKeyList.get(node.key);
-      keyList.count--;
-
-      if (node.previousSibling == null) {
-        keyList.head = node.nextSibling;
-      } else {
-        node.previousSibling.nextSibling = node.nextSibling;
-      }
-      
-      if (node.nextSibling == null) {
-        keyList.tail = node.previousSibling;
-      } else {
-        node.nextSibling.previousSibling = node.previousSibling;
-      }
+      keyToKeyHead.remove(node.key); // don't leak a key-null entry
     }
-    size--;
+    if (node.nextSibling != null) {
+      node.nextSibling.previousSibling = node.previousSibling;
+    } else if (node.previousSibling != null) { // node was key tail
+      keyToKeyTail.put(node.key, node.previousSibling);
+    } else {
+      keyToKeyTail.remove(node.key); // don't leak a key-null entry
+    }
+    keyCount.remove(node.key);
   }
 
   /** Removes all nodes for the specified key. */
@@ -305,7 +277,6 @@ public class LinkedListMultimap<K, V>
     Node<K, V> next;
     Node<K, V> current;
     Node<K, V> previous;
-    int expectedModCount = modCount;
 
     NodeIterator() {
       next = head;
@@ -327,19 +298,12 @@ public class LinkedListMultimap<K, V>
       }
       current = null;
     }
-    private void checkForConcurrentModification() {
-      if (modCount != expectedModCount) {
-        throw new ConcurrentModificationException();
-      }
-    }
     @Override
     public boolean hasNext() {
-      checkForConcurrentModification();
       return next != null;
     }
     @Override
     public Node<K, V> next() {
-      checkForConcurrentModification();
       checkElement(next);
       previous = current = next;
       next = next.next;
@@ -348,7 +312,6 @@ public class LinkedListMultimap<K, V>
     }
     @Override
     public void remove() {
-      checkForConcurrentModification();
       checkState(current != null);
       if (current != next) { // after call to next()
         previous = current.previous;
@@ -358,16 +321,13 @@ public class LinkedListMultimap<K, V>
       }
       removeNode(current);
       current = null;
-      expectedModCount = modCount;
     }
     @Override
     public boolean hasPrevious() {
-      checkForConcurrentModification();
       return previous != null;
     }
     @Override
     public Node<K, V> previous() {
-      checkForConcurrentModification();
       checkElement(previous);
       next = current = previous;
       previous = previous.previous;
@@ -401,21 +361,13 @@ public class LinkedListMultimap<K, V>
     final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size());
     Node<K, V> next = head;
     Node<K, V> current;
-    int expectedModCount = modCount;
-    
-    private void checkForConcurrentModification() {
-      if (modCount != expectedModCount) {
-        throw new ConcurrentModificationException();
-      }
-    }
+
     @Override
     public boolean hasNext() {
-      checkForConcurrentModification();
       return next != null;
     }
     @Override
     public K next() {
-      checkForConcurrentModification();
       checkElement(next);
       current = next;
       seenKeys.add(current.key);
@@ -426,11 +378,9 @@ public class LinkedListMultimap<K, V>
     }
     @Override
     public void remove() {
-      checkForConcurrentModification();
       checkState(current != null);
       removeAllNodes(current.key);
       current = null;
-      expectedModCount = modCount;
     }
   }
 
@@ -445,8 +395,7 @@ public class LinkedListMultimap<K, V>
     /** Constructs a new iterator over all values for the specified key. */
     ValueForKeyIterator(@Nullable Object key) {
       this.key = key;
-      KeyList<K, V> keyList = keyToKeyList.get(key);
-      next = (keyList == null) ? null : keyList.head;
+      next = keyToKeyHead.get(key);
     }
 
     /**
@@ -459,17 +408,16 @@ public class LinkedListMultimap<K, V>
      * @throws IndexOutOfBoundsException if index is invalid
      */
     public ValueForKeyIterator(@Nullable Object key, int index) {
-      KeyList<K, V> keyList = keyToKeyList.get(key);
-      int size = (keyList == null) ? 0 : keyList.count;
+      int size = keyCount.count(key);
       Preconditions.checkPositionIndex(index, size);
       if (index >= (size / 2)) {
-        previous = (keyList == null) ? null : keyList.tail;
+        previous = keyToKeyTail.get(key);
         nextIndex = size;
         while (index++ < size) {
           previous();
         }
       } else {
-        next = (keyList == null) ? null : keyList.head;
+        next = keyToKeyHead.get(key);
         while (index-- > 0) {
           next();
         }
@@ -548,7 +496,7 @@ public class LinkedListMultimap<K, V>
 
   @Override
   public int size() {
-    return size;
+    return keyCount.size();
   }
 
   @Override
@@ -558,7 +506,7 @@ public class LinkedListMultimap<K, V>
 
   @Override
   public boolean containsKey(@Nullable Object key) {
-    return keyToKeyList.containsKey(key);
+    return keyToKeyHead.containsKey(key);
   }
 
   @Override
@@ -685,9 +633,9 @@ public class LinkedListMultimap<K, V>
   public void clear() {
     head = null;
     tail = null;
-    keyToKeyList.clear();
-    size = 0;
-    modCount++;
+    keyCount.clear();
+    keyToKeyHead.clear();
+    keyToKeyTail.clear();
   }
 
   // Views
@@ -705,8 +653,7 @@ public class LinkedListMultimap<K, V>
   public List<V> get(final @Nullable K key) {
     return new AbstractSequentialList<V>() {
       @Override public int size() {
-        KeyList<K, V> keyList = keyToKeyList.get(key);
-        return (keyList == null) ? 0 : keyList.count;
+        return keyCount.count(key);
       }
       @Override public ListIterator<V> listIterator(int index) {
         return new ValueForKeyIterator(key, index);
@@ -726,19 +673,19 @@ public class LinkedListMultimap<K, V>
   public Set<K> keySet() {
     Set<K> result = keySet;
     if (result == null) {
-      keySet = result = new Sets.ImprovedAbstractSet<K>() {
+      keySet = result = new AbstractSet<K>() {
         @Override public int size() {
-          return keyToKeyList.size();
+          return keyCount.elementSet().size();
         }
         @Override public Iterator<K> iterator() {
           return new DistinctKeyIterator();
         }
         @Override public boolean contains(Object key) { // for performance
-          return containsKey(key);
+          return keyCount.contains(key);
         }
-        @Override
-        public boolean remove(Object o) { // for performance
-          return !LinkedListMultimap.this.removeAll(o).isEmpty();
+        @Override public boolean removeAll(Collection<?> c) {
+          checkNotNull(c); // eager for GWT
+          return super.removeAll(c);
         }
       };
     }
@@ -756,50 +703,39 @@ public class LinkedListMultimap<K, V>
     return result;
   }
 
-  private class MultisetView extends AbstractMultiset<K> {
-    @Override
-    public int size() {
-      return size;
-    }
+  private class MultisetView extends AbstractCollection<K>
+      implements Multiset<K> {
 
-    @Override
-    public int count(Object element) {
-      KeyList<K, V> keyList = keyToKeyList.get(element);
-      return (keyList == null) ? 0 : keyList.count;
+    @Override public int size() {
+      return keyCount.size();
     }
 
-    @Override
-    Iterator<Entry<K>> entryIterator() {
-      return new TransformedIterator<K, Entry<K>>(new DistinctKeyIterator()) {
+    @Override public Iterator<K> iterator() {
+      final Iterator<Node<K, V>> nodes = new NodeIterator();
+      return new Iterator<K>() {
         @Override
-        Entry<K> transform(final K key) {
-          return new Multisets.AbstractEntry<K>() {
-            @Override
-            public K getElement() {
-              return key;
-            }
-
-            @Override
-            public int getCount() {
-              return keyToKeyList.get(key).count;
-            }
-          };
+        public boolean hasNext() {
+          return nodes.hasNext();
+        }
+        @Override
+        public K next() {
+          return nodes.next().key;
+        }
+        @Override
+        public void remove() {
+          nodes.remove();
         }
       };
     }
 
     @Override
-    int distinctElements() {
-      return elementSet().size();
+    public int count(@Nullable Object key) {
+      return keyCount.count(key);
     }
 
-    @Override public Iterator<K> iterator() {
-      return new TransformedIterator<Node<K, V>, K>(new NodeIterator()) {
-        @Override
-        K transform(Node<K, V> node) {
-          return node.key;
-        }
-      };
+    @Override
+    public int add(@Nullable K key, int occurrences) {
+      throw new UnsupportedOperationException();
     }
 
     @Override
@@ -815,9 +751,77 @@ public class LinkedListMultimap<K, V>
     }
 
     @Override
+    public int setCount(K element, int count) {
+      return setCountImpl(this, element, count);
+    }
+
+    @Override
+    public boolean setCount(K element, int oldCount, int newCount) {
+      return setCountImpl(this, element, oldCount, newCount);
+    }
+
+    @Override public boolean removeAll(Collection<?> c) {
+      return Iterators.removeAll(iterator(), c);
+    }
+
+    @Override public boolean retainAll(Collection<?> c) {
+      return Iterators.retainAll(iterator(), c);
+    }
+
+    @Override
     public Set<K> elementSet() {
       return keySet();
     }
+
+    @Override
+    public Set<Entry<K>> entrySet() {
+      // TODO(jlevy): lazy init?
+      return new AbstractSet<Entry<K>>() {
+        @Override public int size() {
+          return keyCount.elementSet().size();
+        }
+
+        @Override public Iterator<Entry<K>> iterator() {
+          final Iterator<K> keyIterator = new DistinctKeyIterator();
+          return new Iterator<Entry<K>>() {
+            @Override
+            public boolean hasNext() {
+              return keyIterator.hasNext();
+            }
+            @Override
+            public Entry<K> next() {
+              final K key = keyIterator.next();
+              return new Multisets.AbstractEntry<K>() {
+                @Override
+                public K getElement() {
+                  return key;
+                }
+                @Override
+                public int getCount() {
+                  return keyCount.count(key);
+                }
+              };
+            }
+            @Override
+            public void remove() {
+              keyIterator.remove();
+            }
+          };
+        }
+      };
+    }
+
+    @Override public boolean equals(@Nullable Object object) {
+      return keyCount.equals(object);
+    }
+
+    @Override public int hashCode() {
+      return keyCount.hashCode();
+    }
+
+    @Override public String toString() {
+      return keyCount.toString(); // XXX observe order?
+    }
   }
 
   private transient List<V> valuesList;
@@ -837,20 +841,47 @@ public class LinkedListMultimap<K, V>
     if (result == null) {
       valuesList = result = new AbstractSequentialList<V>() {
         @Override public int size() {
-          return size;
+          return keyCount.size();
         }
         @Override
         public ListIterator<V> listIterator(int index) {
           final NodeIterator nodes = new NodeIterator(index);
-          return new TransformedListIterator<Node<K, V>, V>(nodes) {
+          return new ListIterator<V>() {
             @Override
-            V transform(Node<K, V> node) {
-              return node.value;
+            public boolean hasNext() {
+              return nodes.hasNext();
+            }
+            @Override
+            public V next() {
+              return nodes.next().value;
+            }
+            @Override
+            public boolean hasPrevious() {
+              return nodes.hasPrevious();
+            }
+            @Override
+            public V previous() {
+              return nodes.previous().value;
             }
-
             @Override
-            public void set(V value) {
-              nodes.setValue(value);
+            public int nextIndex() {
+              return nodes.nextIndex();
+            }
+            @Override
+            public int previousIndex() {
+              return nodes.previousIndex();
+            }
+            @Override
+            public void remove() {
+              nodes.remove();
+            }
+            @Override
+            public void set(V e) {
+              nodes.setValue(e);
+            }
+            @Override
+            public void add(V e) {
+              throw new UnsupportedOperationException();
             }
           };
         }
@@ -901,14 +932,55 @@ public class LinkedListMultimap<K, V>
     if (result == null) {
       entries = result = new AbstractSequentialList<Entry<K, V>>() {
         @Override public int size() {
-          return size;
+          return keyCount.size();
         }
 
         @Override public ListIterator<Entry<K, V>> listIterator(int index) {
-          return new TransformedListIterator<Node<K, V>, Entry<K, V>>(new NodeIterator(index)) {
+          final ListIterator<Node<K, V>> nodes = new NodeIterator(index);
+          return new ListIterator<Entry<K, V>>() {
+            @Override
+            public boolean hasNext() {
+              return nodes.hasNext();
+            }
+
+            @Override
+            public Entry<K, V> next() {
+              return createEntry(nodes.next());
+            }
+
+            @Override
+            public void remove() {
+              nodes.remove();
+            }
+
+            @Override
+            public boolean hasPrevious() {
+              return nodes.hasPrevious();
+            }
+
+            @Override
+            public Map.Entry<K, V> previous() {
+              return createEntry(nodes.previous());
+            }
+
+            @Override
+            public int nextIndex() {
+              return nodes.nextIndex();
+            }
+
+            @Override
+            public int previousIndex() {
+              return nodes.previousIndex();
+            }
+
+            @Override
+            public void set(Map.Entry<K, V> e) {
+              throw new UnsupportedOperationException();
+            }
+
             @Override
-            Entry<K, V> transform(Node<K, V> node) {
-              return createEntry(node);
+            public void add(Map.Entry<K, V> e) {
+              throw new UnsupportedOperationException();
             }
           };
         }
@@ -917,39 +989,75 @@ public class LinkedListMultimap<K, V>
     return result;
   }
 
+  private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
+    @Override public int size() {
+      return keyCount.elementSet().size();
+    }
+
+    @Override public Iterator<Entry<K, Collection<V>>> iterator() {
+      final Iterator<K> keyIterator = new DistinctKeyIterator();
+      return new Iterator<Entry<K, Collection<V>>>() {
+        @Override
+        public boolean hasNext() {
+          return keyIterator.hasNext();
+        }
+
+        @Override
+        public Entry<K, Collection<V>> next() {
+          final K key = keyIterator.next();
+          return new AbstractMapEntry<K, Collection<V>>() {
+            @Override public K getKey() {
+              return key;
+            }
+
+            @Override public Collection<V> getValue() {
+              return LinkedListMultimap.this.get(key);
+            }
+          };
+        }
+
+        @Override
+        public void remove() {
+          keyIterator.remove();
+        }
+      };
+    }
+
+    // TODO(jlevy): Override contains() and remove() for better performance.
+  }
+
   private transient Map<K, Collection<V>> map;
 
   @Override
   public Map<K, Collection<V>> asMap() {
     Map<K, Collection<V>> result = map;
     if (result == null) {
-      map = result = new Multimaps.AsMap<K, V>() {
-        @Override
-        public int size() {
-          return keyToKeyList.size();
+      map = result = new AbstractMap<K, Collection<V>>() {
+        Set<Entry<K, Collection<V>>> entrySet;
+
+        @Override public Set<Entry<K, Collection<V>>> entrySet() {
+          Set<Entry<K, Collection<V>>> result = entrySet;
+          if (result == null) {
+            entrySet = result = new AsMapEntries();
+          }
+          return result;
         }
 
-        @Override
-        Multimap<K, V> multimap() {
-          return LinkedListMultimap.this;
+        // The following methods are included for performance.
+
+        @Override public boolean containsKey(@Nullable Object key) {
+          return LinkedListMultimap.this.containsKey(key);
         }
 
-        @Override
-        Iterator<Entry<K, Collection<V>>> entryIterator() {
-          return new TransformedIterator<K, Entry<K, Collection<V>>>(new DistinctKeyIterator()) {
-            @Override
-            Entry<K, Collection<V>> transform(final K key) {
-              return new AbstractMapEntry<K, Collection<V>>() {
-                @Override public K getKey() {
-                  return key;
-                }
+        @SuppressWarnings("unchecked")
+        @Override public Collection<V> get(@Nullable Object key) {
+          Collection<V> collection = LinkedListMultimap.this.get((K) key);
+          return collection.isEmpty() ? null : collection;
+        }
 
-                @Override public Collection<V> getValue() {
-                  return LinkedListMultimap.this.get(key);
-                }
-              };
-            }
-          };
+        @Override public Collection<V> remove(@Nullable Object key) {
+          Collection<V> collection = removeAll(key);
+          return collection.isEmpty() ? null : collection;
         }
       };
     }