/*
    * 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
    *
    * 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 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.collect.CollectPreconditions.checkRemove;
  
  import com.google.common.annotations.GwtCompatible;
  import com.google.common.annotations.GwtIncompatible;
  import com.google.common.collect.Maps.ImprovedAbstractMap;
  
  import java.io.Serializable;
  import java.util.AbstractCollection;
  import java.util.Collection;
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.ConcurrentModificationException;
  import java.util.Iterator;
  import java.util.List;
  import java.util.ListIterator;
  import java.util.Map;
  import java.util.Map.Entry;
  import java.util.NavigableMap;
  import java.util.NavigableSet;
  import java.util.RandomAccess;
  import java.util.Set;
  import java.util.SortedMap;
  import java.util.SortedSet;
  
  import javax.annotation.Nullable;
  
  /**
   * Basic implementation of the {@link Multimap} interface. This class represents
   * a multimap as a map that associates each key with a collection of values. All
   * methods of {@link Multimap} are supported, including those specified as
   * optional in the interface.
   *
   * <p>To implement a multimap, a subclass must define the method {@link
   * #createCollection()}, which creates an empty collection of values for a key.
   *
   * <p>The multimap constructor takes a map that has a single entry for each
   * distinct key. When you insert a key-value pair with a key that isn't already
   * in the multimap, {@code AbstractMapBasedMultimap} calls {@link #createCollection()}
   * to create the collection of values for that key. The subclass should not call
   * {@link #createCollection()} directly, and a new instance should be created
   * every time the method is called.
   *
   * <p>For example, the subclass could pass a {@link java.util.TreeMap} during
   * construction, and {@link #createCollection()} could return a {@link
   * java.util.TreeSet}, in which case the multimap's iterators would propagate
   * through the keys and values in sorted order.
   *
   * <p>Keys and values may be null, as long as the underlying collection classes
   * support null elements.
   *
   * <p>The collections created by {@link #createCollection()} may or may not
   * allow duplicates. If the collection, such as a {@link Set}, does not support
   * duplicates, an added key-value pair will replace an existing pair with the
   * same key and value, if such a pair is present. With collections like {@link
   * List} that allow duplicates, the collection will keep the existing key-value
   * pairs while adding a new pair.
   *
   * <p>This class is not threadsafe when any concurrent operations update the
   * multimap, even if the underlying map and {@link #createCollection()} method
   * return threadsafe classes. Concurrent read operations will work correctly. To
   * allow concurrent update operations, wrap your multimap with a call to {@link
   * Multimaps#synchronizedMultimap}.
   *
   * <p>For serialization to work, the subclass must specify explicit
   * {@code readObject} and {@code writeObject} methods.
   *
   * @author Jared Levy
   * @author Louis Wasserman
   */
  @GwtCompatible(emulated = true)
  abstract class AbstractMapBasedMultimap<K, V> extends AbstractMultimap<K, V>
      implements Serializable {
    /*
     * Here's an outline of the overall design.
     *
     * The map variable contains the collection of values associated with each
     * key. When a key-value pair is added to a multimap that didn't previously
     * contain any values for that key, a new collection generated by
     * createCollection is added to the map. That same collection instance
    * remains in the map as long as the multimap has any values for the key. If
    * all values for the key are removed, the key and collection are removed
    * from the map.
    *
    * The get method returns a WrappedCollection, which decorates the collection
    * in the map (if the key is present) or an empty collection (if the key is
    * not present). When the collection delegate in the WrappedCollection is
    * empty, the multimap may contain subsequently added values for that key. To
    * handle that situation, the WrappedCollection checks whether map contains
    * an entry for the provided key, and if so replaces the delegate.
    */
 
   private transient Map<K, Collection<V>> map;
   private transient int totalSize;
 
   /**
    * Creates a new multimap that uses the provided map.
    *
    * @param map place to store the mapping from each key to its corresponding
    *     values
    * @throws IllegalArgumentException if {@code map} is not empty
    */
   protected AbstractMapBasedMultimap(Map<K, Collection<V>> map) {
     checkArgument(map.isEmpty());
     this.map = map;
   }
 
   /** Used during deserialization only. */
   final void setMap(Map<K, Collection<V>> map) {
     this.map = map;
     totalSize = 0;
     for (Collection<V> values : map.values()) {
       checkArgument(!values.isEmpty());
       totalSize += values.size();
     }
   }
 
   /**
    * Creates an unmodifiable, empty collection of values.
    *
    * <p>This is used in {@link #removeAll} on an empty key.
    */
   Collection<V> createUnmodifiableEmptyCollection() {
     return unmodifiableCollectionSubclass(createCollection());
   }
 
   /**
    * Creates the collection of values for a single key.
    *
    * <p>Collections with weak, soft, or phantom references are not supported.
    * Each call to {@code createCollection} should create a new instance.
    *
    * <p>The returned collection class determines whether duplicate key-value
    * pairs are allowed.
    *
    * @return an empty collection of values
    */
   abstract Collection<V> createCollection();
 
   /**
    * Creates the collection of values for an explicitly provided key. By
    * default, it simply calls {@link #createCollection()}, which is the correct
    * behavior for most implementations. The {@link LinkedHashMultimap} class
    * overrides it.
    *
    * @param key key to associate with values in the collection
    * @return an empty collection of values
    */
   Collection<V> createCollection(@Nullable K key) {
     return createCollection();
   }
 
   Map<K, Collection<V>> backingMap() {
     return map;
   }
 
   // Query Operations
 
   @Override
   public int size() {
     return totalSize;
   }
 
   @Override
   public boolean containsKey(@Nullable Object key) {
     return map.containsKey(key);
   }
 
   // Modification Operations
 
   @Override
   public boolean put(@Nullable K key, @Nullable V value) {
     Collection<V> collection = map.get(key);
     if (collection == null) {
       collection = createCollection(key);
       if (collection.add(value)) {
         totalSize++;
         map.put(key, collection);
         return true;
       } else {
         throw new AssertionError("New Collection violated the Collection spec");
       }
     } else if (collection.add(value)) {
       totalSize++;
       return true;
     } else {
       return false;
     }
   }
 
   private Collection<V> getOrCreateCollection(@Nullable K key) {
     Collection<V> collection = map.get(key);
     if (collection == null) {
       collection = createCollection(key);
       map.put(key, collection);
     }
     return collection;
   }
 
   // Bulk Operations
 
   /**
    * {@inheritDoc}
    *
    * <p>The returned collection is immutable.
    */
   @Override
   public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
     Iterator<? extends V> iterator = values.iterator();
     if (!iterator.hasNext()) {
       return removeAll(key);
     }
 
     // TODO(user): investigate atomic failure?
     Collection<V> collection = getOrCreateCollection(key);
     Collection<V> oldValues = createCollection();
     oldValues.addAll(collection);
 
     totalSize -= collection.size();
     collection.clear();
 
     while (iterator.hasNext()) {
       if (collection.add(iterator.next())) {
         totalSize++;
       }
     }
 
     return unmodifiableCollectionSubclass(oldValues);
   }
 
   /**
    * {@inheritDoc}
    *
    * <p>The returned collection is immutable.
    */
   @Override
   public Collection<V> removeAll(@Nullable Object key) {
     Collection<V> collection = map.remove(key);
 
     if (collection == null) {
       return createUnmodifiableEmptyCollection();
     }
 
     Collection<V> output = createCollection();
     output.addAll(collection);
     totalSize -= collection.size();
     collection.clear();
 
     return unmodifiableCollectionSubclass(output);
   }
 
   Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) {
     // We don't deal with NavigableSet here yet for GWT reasons -- instead,
     // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet.
     if (collection instanceof SortedSet) {
       return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
     } else if (collection instanceof Set) {
       return Collections.unmodifiableSet((Set<V>) collection);
     } else if (collection instanceof List) {
       return Collections.unmodifiableList((List<V>) collection);
     } else {
       return Collections.unmodifiableCollection(collection);
     }
   }
 
   @Override
   public void clear() {
     // Clear each collection, to make previously returned collections empty.
     for (Collection<V> collection : map.values()) {
       collection.clear();
     }
     map.clear();
     totalSize = 0;
   }
 
   // Views
 
   /**
    * {@inheritDoc}
    *
    * <p>The returned collection is not serializable.
    */
   @Override
   public Collection<V> get(@Nullable K key) {
     Collection<V> collection = map.get(key);
     if (collection == null) {
       collection = createCollection(key);
     }
     return wrapCollection(key, collection);
   }
 
   /**
    * Generates a decorated collection that remains consistent with the values in
    * the multimap for the provided key. Changes to the multimap may alter the
    * returned collection, and vice versa.
    */
   Collection<V> wrapCollection(@Nullable K key, Collection<V> collection) {
     // We don't deal with NavigableSet here yet for GWT reasons -- instead,
     // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet.
     if (collection instanceof SortedSet) {
       return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
     } else if (collection instanceof Set) {
       return new WrappedSet(key, (Set<V>) collection);
     } else if (collection instanceof List) {
       return wrapList(key, (List<V>) collection, null);
     } else {
       return new WrappedCollection(key, collection, null);
     }
   }
 
   private List<V> wrapList(
       @Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) {
     return (list instanceof RandomAccess)
         ? new RandomAccessWrappedList(key, list, ancestor)
         : new WrappedList(key, list, ancestor);
   }
 
   /**
    * Collection decorator that stays in sync with the multimap values for a key.
    * There are two kinds of wrapped collections: full and subcollections. Both
    * have a delegate pointing to the underlying collection class.
    *
    * <p>Full collections, identified by a null ancestor field, contain all
    * multimap values for a given key. Its delegate is a value in {@link
    * AbstractMapBasedMultimap#map} whenever the delegate is non-empty. The {@code
    * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure
    * that the {@code WrappedCollection} and map remain consistent.
    *
    * <p>A subcollection, such as a sublist, contains some of the values for a
    * given key. Its ancestor field points to the full wrapped collection with
    * all values for the key. The subcollection {@code refreshIfEmpty}, {@code
    * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods
    * of the full wrapped collection.
    */
   private class WrappedCollection extends AbstractCollection<V> {
     final K key;
     Collection<V> delegate;
     final WrappedCollection ancestor;
     final Collection<V> ancestorDelegate;
 
     WrappedCollection(@Nullable K key, Collection<V> delegate,
         @Nullable WrappedCollection ancestor) {
       this.key = key;
       this.delegate = delegate;
       this.ancestor = ancestor;
       this.ancestorDelegate
           = (ancestor == null) ? null : ancestor.getDelegate();
     }
 
     /**
      * If the delegate collection is empty, but the multimap has values for the
      * key, replace the delegate with the new collection for the key.
      *
      * <p>For a subcollection, refresh its ancestor and validate that the
      * ancestor delegate hasn't changed.
      */
     void refreshIfEmpty() {
       if (ancestor != null) {
         ancestor.refreshIfEmpty();
         if (ancestor.getDelegate() != ancestorDelegate) {
           throw new ConcurrentModificationException();
         }
       } else if (delegate.isEmpty()) {
         Collection<V> newDelegate = map.get(key);
         if (newDelegate != null) {
           delegate = newDelegate;
         }
       }
     }
 
     /**
      * If collection is empty, remove it from {@code AbstractMapBasedMultimap.this.map}.
      * For subcollections, check whether the ancestor collection is empty.
      */
     void removeIfEmpty() {
       if (ancestor != null) {
         ancestor.removeIfEmpty();
       } else if (delegate.isEmpty()) {
         map.remove(key);
       }
     }
 
     K getKey() {
       return key;
     }
 
     /**
      * Add the delegate to the map. Other {@code WrappedCollection} methods
      * should call this method after adding elements to a previously empty
      * collection.
      *
      * <p>Subcollection add the ancestor's delegate instead.
      */
     void addToMap() {
       if (ancestor != null) {
         ancestor.addToMap();
       } else {
         map.put(key, delegate);
       }
     }
 
     @Override public int size() {
       refreshIfEmpty();
       return delegate.size();
     }
 
     @Override public boolean equals(@Nullable Object object) {
       if (object == this) {
         return true;
       }
       refreshIfEmpty();
       return delegate.equals(object);
     }
 
     @Override public int hashCode() {
       refreshIfEmpty();
       return delegate.hashCode();
     }
 
     @Override public String toString() {
       refreshIfEmpty();
       return delegate.toString();
     }
 
     Collection<V> getDelegate() {
       return delegate;
     }
 
     @Override public Iterator<V> iterator() {
       refreshIfEmpty();
       return new WrappedIterator();
     }
 
     /** Collection iterator for {@code WrappedCollection}. */
     class WrappedIterator implements Iterator<V> {
       final Iterator<V> delegateIterator;
       final Collection<V> originalDelegate = delegate;
 
       WrappedIterator() {
         delegateIterator = iteratorOrListIterator(delegate);
       }
 
       WrappedIterator(Iterator<V> delegateIterator) {
         this.delegateIterator = delegateIterator;
       }
 
       /**
        * If the delegate changed since the iterator was created, the iterator is
        * no longer valid.
        */
       void validateIterator() {
         refreshIfEmpty();
         if (delegate != originalDelegate) {
           throw new ConcurrentModificationException();
         }
       }
 
       @Override
       public boolean hasNext() {
         validateIterator();
         return delegateIterator.hasNext();
       }
 
       @Override
       public V next() {
         validateIterator();
         return delegateIterator.next();
       }
 
       @Override
       public void remove() {
         delegateIterator.remove();
         totalSize--;
         removeIfEmpty();
       }
 
       Iterator<V> getDelegateIterator() {
         validateIterator();
         return delegateIterator;
       }
     }
 
     @Override public boolean add(V value) {
       refreshIfEmpty();
       boolean wasEmpty = delegate.isEmpty();
       boolean changed = delegate.add(value);
       if (changed) {
         totalSize++;
         if (wasEmpty) {
           addToMap();
         }
       }
       return changed;
     }
 
     WrappedCollection getAncestor() {
       return ancestor;
     }
 
     // The following methods are provided for better performance.
 
     @Override public boolean addAll(Collection<? extends V> collection) {
       if (collection.isEmpty()) {
         return false;
       }
       int oldSize = size();  // calls refreshIfEmpty
       boolean changed = delegate.addAll(collection);
       if (changed) {
         int newSize = delegate.size();
         totalSize += (newSize - oldSize);
         if (oldSize == 0) {
           addToMap();
         }
       }
       return changed;
     }
 
     @Override public boolean contains(Object o) {
       refreshIfEmpty();
       return delegate.contains(o);
     }
 
     @Override public boolean containsAll(Collection<?> c) {
       refreshIfEmpty();
       return delegate.containsAll(c);
     }
 
     @Override public void clear() {
       int oldSize = size();  // calls refreshIfEmpty
       if (oldSize == 0) {
         return;
       }
       delegate.clear();
       totalSize -= oldSize;
       removeIfEmpty();       // maybe shouldn't be removed if this is a sublist
     }
 
     @Override public boolean remove(Object o) {
       refreshIfEmpty();
       boolean changed = delegate.remove(o);
       if (changed) {
         totalSize--;
         removeIfEmpty();
       }
       return changed;
     }
 
     @Override public boolean removeAll(Collection<?> c) {
       if (c.isEmpty()) {
         return false;
       }
       int oldSize = size();  // calls refreshIfEmpty
       boolean changed = delegate.removeAll(c);
       if (changed) {
         int newSize = delegate.size();
         totalSize += (newSize - oldSize);
         removeIfEmpty();
       }
       return changed;
     }
 
     @Override public boolean retainAll(Collection<?> c) {
       checkNotNull(c);
       int oldSize = size();  // calls refreshIfEmpty
       boolean changed = delegate.retainAll(c);
       if (changed) {
         int newSize = delegate.size();
         totalSize += (newSize - oldSize);
         removeIfEmpty();
       }
       return changed;
     }
   }
 
   private Iterator<V> iteratorOrListIterator(Collection<V> collection) {
     return (collection instanceof List)
         ? ((List<V>) collection).listIterator()
         : collection.iterator();
   }
 
   /** Set decorator that stays in sync with the multimap values for a key. */
   private class WrappedSet extends WrappedCollection implements Set<V> {
     WrappedSet(@Nullable K key, Set<V> delegate) {
       super(key, delegate, null);
     }
 
     @Override
     public boolean removeAll(Collection<?> c) {
       if (c.isEmpty()) {
         return false;
       }
       int oldSize = size();  // calls refreshIfEmpty
 
       // Guava issue 1013: AbstractSet and most JDK set implementations are
       // susceptible to quadratic removeAll performance on lists;
       // use a slightly smarter implementation here
       boolean changed = Sets.removeAllImpl((Set<V>) delegate, c);
       if (changed) {
         int newSize = delegate.size();
         totalSize += (newSize - oldSize);
         removeIfEmpty();
       }
       return changed;
     }
   }
 
   /**
    * SortedSet decorator that stays in sync with the multimap values for a key.
    */
   private class WrappedSortedSet extends WrappedCollection
       implements SortedSet<V> {
     WrappedSortedSet(@Nullable K key, SortedSet<V> delegate,
         @Nullable WrappedCollection ancestor) {
       super(key, delegate, ancestor);
     }
 
     SortedSet<V> getSortedSetDelegate() {
       return (SortedSet<V>) getDelegate();
     }
 
     @Override
     public Comparator<? super V> comparator() {
       return getSortedSetDelegate().comparator();
     }
 
     @Override
     public V first() {
       refreshIfEmpty();
       return getSortedSetDelegate().first();
     }
 
     @Override
     public V last() {
       refreshIfEmpty();
       return getSortedSetDelegate().last();
     }
 
     @Override
     public SortedSet<V> headSet(V toElement) {
       refreshIfEmpty();
       return new WrappedSortedSet(
           getKey(), getSortedSetDelegate().headSet(toElement),
           (getAncestor() == null) ? this : getAncestor());
     }
 
     @Override
     public SortedSet<V> subSet(V fromElement, V toElement) {
       refreshIfEmpty();
       return new WrappedSortedSet(
           getKey(), getSortedSetDelegate().subSet(fromElement, toElement),
           (getAncestor() == null) ? this : getAncestor());
     }
 
     @Override
     public SortedSet<V> tailSet(V fromElement) {
       refreshIfEmpty();
       return new WrappedSortedSet(
           getKey(), getSortedSetDelegate().tailSet(fromElement),
           (getAncestor() == null) ? this : getAncestor());
     }
   }
 
   @GwtIncompatible("NavigableSet")
   class WrappedNavigableSet extends WrappedSortedSet implements NavigableSet<V> {
     WrappedNavigableSet(
         @Nullable K key, NavigableSet<V> delegate, @Nullable WrappedCollection ancestor) {
       super(key, delegate, ancestor);
     }
 
     @Override
     NavigableSet<V> getSortedSetDelegate() {
       return (NavigableSet<V>) super.getSortedSetDelegate();
     }
 
     @Override
     public V lower(V v) {
       return getSortedSetDelegate().lower(v);
     }
 
     @Override
     public V floor(V v) {
       return getSortedSetDelegate().floor(v);
     }
 
     @Override
     public V ceiling(V v) {
       return getSortedSetDelegate().ceiling(v);
     }
 
     @Override
     public V higher(V v) {
       return getSortedSetDelegate().higher(v);
     }
 
     @Override
     public V pollFirst() {
       return Iterators.pollNext(iterator());
     }
 
     @Override
     public V pollLast() {
       return Iterators.pollNext(descendingIterator());
     }
 
     private NavigableSet<V> wrap(NavigableSet<V> wrapped) {
       return new WrappedNavigableSet(key, wrapped,
           (getAncestor() == null) ? this : getAncestor());
     }
 
     @Override
     public NavigableSet<V> descendingSet() {
       return wrap(getSortedSetDelegate().descendingSet());
     }
 
     @Override
     public Iterator<V> descendingIterator() {
       return new WrappedIterator(getSortedSetDelegate().descendingIterator());
     }
 
     @Override
     public NavigableSet<V> subSet(
         V fromElement, boolean fromInclusive, V toElement, boolean toInclusive) {
       return wrap(
           getSortedSetDelegate().subSet(fromElement, fromInclusive, toElement, toInclusive));
     }
 
     @Override
     public NavigableSet<V> headSet(V toElement, boolean inclusive) {
       return wrap(getSortedSetDelegate().headSet(toElement, inclusive));
     }
 
     @Override
     public NavigableSet<V> tailSet(V fromElement, boolean inclusive) {
       return wrap(getSortedSetDelegate().tailSet(fromElement, inclusive));
     }
   }
 
   /** List decorator that stays in sync with the multimap values for a key. */
   private class WrappedList extends WrappedCollection implements List<V> {
     WrappedList(@Nullable K key, List<V> delegate,
         @Nullable WrappedCollection ancestor) {
       super(key, delegate, ancestor);
     }
 
     List<V> getListDelegate() {
       return (List<V>) getDelegate();
     }
 
     @Override
     public boolean addAll(int index, Collection<? extends V> c) {
       if (c.isEmpty()) {
         return false;
       }
       int oldSize = size();  // calls refreshIfEmpty
       boolean changed = getListDelegate().addAll(index, c);
       if (changed) {
         int newSize = getDelegate().size();
         totalSize += (newSize - oldSize);
         if (oldSize == 0) {
           addToMap();
         }
       }
       return changed;
     }
 
     @Override
     public V get(int index) {
       refreshIfEmpty();
       return getListDelegate().get(index);
     }
 
     @Override
     public V set(int index, V element) {
       refreshIfEmpty();
       return getListDelegate().set(index, element);
     }
 
     @Override
     public void add(int index, V element) {
       refreshIfEmpty();
       boolean wasEmpty = getDelegate().isEmpty();
       getListDelegate().add(index, element);
       totalSize++;
       if (wasEmpty) {
         addToMap();
       }
     }
 
     @Override
     public V remove(int index) {
       refreshIfEmpty();
       V value = getListDelegate().remove(index);
       totalSize--;
       removeIfEmpty();
       return value;
     }
 
     @Override
     public int indexOf(Object o) {
       refreshIfEmpty();
       return getListDelegate().indexOf(o);
     }
 
     @Override
     public int lastIndexOf(Object o) {
       refreshIfEmpty();
       return getListDelegate().lastIndexOf(o);
     }
 
     @Override
     public ListIterator<V> listIterator() {
       refreshIfEmpty();
       return new WrappedListIterator();
     }
 
     @Override
     public ListIterator<V> listIterator(int index) {
       refreshIfEmpty();
       return new WrappedListIterator(index);
     }
 
     @Override
     public List<V> subList(int fromIndex, int toIndex) {
       refreshIfEmpty();
       return wrapList(getKey(),
           getListDelegate().subList(fromIndex, toIndex),
           (getAncestor() == null) ? this : getAncestor());
     }
 
     /** ListIterator decorator. */
     private class WrappedListIterator extends WrappedIterator
         implements ListIterator<V> {
       WrappedListIterator() {}
 
       public WrappedListIterator(int index) {
         super(getListDelegate().listIterator(index));
       }
 
       private ListIterator<V> getDelegateListIterator() {
         return (ListIterator<V>) getDelegateIterator();
       }
 
       @Override
       public boolean hasPrevious() {
         return getDelegateListIterator().hasPrevious();
       }
 
       @Override
       public V previous() {
         return getDelegateListIterator().previous();
       }
 
       @Override
       public int nextIndex() {
         return getDelegateListIterator().nextIndex();
       }
 
       @Override
       public int previousIndex() {
         return getDelegateListIterator().previousIndex();
       }
 
       @Override
       public void set(V value) {
         getDelegateListIterator().set(value);
       }
 
       @Override
       public void add(V value) {
         boolean wasEmpty = isEmpty();
         getDelegateListIterator().add(value);
         totalSize++;
         if (wasEmpty) {
           addToMap();
         }
       }
     }
   }
 
   /**
    * List decorator that stays in sync with the multimap values for a key and
    * supports rapid random access.
    */
   private class RandomAccessWrappedList extends WrappedList
       implements RandomAccess {
     RandomAccessWrappedList(@Nullable K key, List<V> delegate,
         @Nullable WrappedCollection ancestor) {
       super(key, delegate, ancestor);
     }
   }
 
   @Override
   Set<K> createKeySet() {
     // TreeMultimap uses NavigableKeySet explicitly, but we don't handle that here for GWT
     // compatibility reasons
     return (map instanceof SortedMap)
         ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map);
   }
 
   private class KeySet extends Maps.KeySet<K, Collection<V>> {
     KeySet(final Map<K, Collection<V>> subMap) {
       super(subMap);
     }
 
     @Override public Iterator<K> iterator() {
       final Iterator<Map.Entry<K, Collection<V>>> entryIterator
           = map().entrySet().iterator();
       return new Iterator<K>() {
         Map.Entry<K, Collection<V>> entry;
 
         @Override
         public boolean hasNext() {
           return entryIterator.hasNext();
         }
         @Override
         public K next() {
           entry = entryIterator.next();
           return entry.getKey();
         }
         @Override
         public void remove() {
           checkRemove(entry != null);
           Collection<V> collection = entry.getValue();
           entryIterator.remove();
           totalSize -= collection.size();
           collection.clear();
         }
       };
     }
 
     // The following methods are included for better performance.
 
     @Override public boolean remove(Object key) {
       int count = 0;
       Collection<V> collection = map().remove(key);
       if (collection != null) {
         count = collection.size();
         collection.clear();
         totalSize -= count;
       }
       return count > 0;
     }
 
     @Override
     public void clear() {
       Iterators.clear(iterator());
     }
 
     @Override public boolean containsAll(Collection<?> c) {
       return map().keySet().containsAll(c);
     }
 
     @Override public boolean equals(@Nullable Object object) {
       return this == object || this.map().keySet().equals(object);
     }
 
     @Override public int hashCode() {
       return map().keySet().hashCode();
     }
   }
 
   private class SortedKeySet extends KeySet implements SortedSet<K> {
 
     SortedKeySet(SortedMap<K, Collection<V>> subMap) {
       super(subMap);
     }
 
     SortedMap<K, Collection<V>> sortedMap() {
       return (SortedMap<K, Collection<V>>) super.map();
     }
 
     @Override
     public Comparator<? super K> comparator() {
       return sortedMap().comparator();
     }
 
     @Override
     public K first() {
       return sortedMap().firstKey();
     }
 
     @Override
     public SortedSet<K> headSet(K toElement) {
       return new SortedKeySet(sortedMap().headMap(toElement));
     }
 
     @Override
     public K last() {
       return sortedMap().lastKey();
     }
 
     @Override
     public SortedSet<K> subSet(K fromElement, K toElement) {
       return new SortedKeySet(sortedMap().subMap(fromElement, toElement));
     }
 
     @Override
     public SortedSet<K> tailSet(K fromElement) {
       return new SortedKeySet(sortedMap().tailMap(fromElement));
     }
   }
 
   @GwtIncompatible("NavigableSet")
   class NavigableKeySet extends SortedKeySet implements NavigableSet<K> {
     NavigableKeySet(NavigableMap<K, Collection<V>> subMap) {
       super(subMap);
     }
 
     @Override
     NavigableMap<K, Collection<V>> sortedMap() {
       return (NavigableMap<K, Collection<V>>) super.sortedMap();
     }
 
     @Override
     public K lower(K k) {
       return sortedMap().lowerKey(k);
     }
 
     @Override
     public K floor(K k) {
       return sortedMap().floorKey(k);
     }
 
     @Override
     public K ceiling(K k) {
       return sortedMap().ceilingKey(k);
     }
 
     @Override
     public K higher(K k) {
       return sortedMap().higherKey(k);
     }
 
     @Override
     public K pollFirst() {
       return Iterators.pollNext(iterator());
     }
 
     @Override
     public K pollLast() {
       return Iterators.pollNext(descendingIterator());
     }
 
     @Override
     public NavigableSet<K> descendingSet() {
       return new NavigableKeySet(sortedMap().descendingMap());
     }
 
     @Override
     public Iterator<K> descendingIterator() {
       return descendingSet().iterator();
     }
 
     @Override
     public NavigableSet<K> headSet(K toElement) {
       return headSet(toElement, false);
     }
 
     @Override
     public NavigableSet<K> headSet(K toElement, boolean inclusive) {
       return new NavigableKeySet(sortedMap().headMap(toElement, inclusive));
     }
 
     @Override
     public NavigableSet<K> subSet(K fromElement, K toElement) {
       return subSet(fromElement, true, toElement, false);
     }
 
     @Override
     public NavigableSet<K> subSet(
         K fromElement, boolean fromInclusive, K toElement, boolean toInclusive) {
       return new NavigableKeySet(
           sortedMap().subMap(fromElement, fromInclusive, toElement, toInclusive));
     }
 
     @Override
     public NavigableSet<K> tailSet(K fromElement) {
       return tailSet(fromElement, true);
     }
 
     @Override
     public NavigableSet<K> tailSet(K fromElement, boolean inclusive) {
       return new NavigableKeySet(sortedMap().tailMap(fromElement, inclusive));
     }
   }
 
   /**
    * Removes all values for the provided key. Unlike {@link #removeAll}, it
    * returns the number of removed mappings.
    */
   private int removeValuesForKey(Object key) {
     Collection<V> collection = Maps.safeRemove(map, key);
 
     int count = 0;
     if (collection != null) {
       count = collection.size();
       collection.clear();
       totalSize -= count;
     }
     return count;
   }
 
   private abstract class Itr<T> implements Iterator<T> {
     final Iterator<Map.Entry<K, Collection<V>>> keyIterator;
     K key;
     Collection<V> collection;
     Iterator<V> valueIterator;
 
     Itr() {
       keyIterator = map.entrySet().iterator();
       key = null;
       collection = null;
       valueIterator = Iterators.emptyModifiableIterator();
     }
 
     abstract T output(K key, V value);
 
     @Override
     public boolean hasNext() {
       return keyIterator.hasNext() || valueIterator.hasNext();
     }
 
     @Override
     public T next() {
       if (!valueIterator.hasNext()) {
         Map.Entry<K, Collection<V>> mapEntry = keyIterator.next();
         key = mapEntry.getKey();
         collection = mapEntry.getValue();
         valueIterator = collection.iterator();
       }
       return output(key, valueIterator.next());
     }
 
     @Override
     public void remove() {
       valueIterator.remove();
       if (collection.isEmpty()) {
         keyIterator.remove();
       }
       totalSize--;
     }
   }
 
   /**
    * {@inheritDoc}
    *
    * <p>The iterator generated by the returned collection traverses the values
    * for one key, followed by the values of a second key, and so on.
    */
   @Override public Collection<V> values() {
     return super.values();
   }
 
   @Override
   Iterator<V> valueIterator() {
     return new Itr<V>() {
       @Override
       V output(K key, V value) {
         return value;
       }
     };
   }
 
   /*
    * TODO(kevinb): should we copy this javadoc to each concrete class, so that
    * classes like LinkedHashMultimap that need to say something different are
    * still able to {@inheritDoc} all the way from Multimap?
    */
 
   /**
    * {@inheritDoc}
    *
    * <p>The iterator generated by the returned collection traverses the values
    * for one key, followed by the values of a second key, and so on.
    *
    * <p>Each entry is an immutable snapshot of a key-value mapping in the
    * multimap, taken at the time the entry is returned by a method call to the
    * collection or its iterator.
    */
   @Override
   public Collection<Map.Entry<K, V>> entries() {
     return super.entries();
   }
 
   /**
    * Returns an iterator across all key-value map entries, used by {@code
    * entries().iterator()} and {@code values().iterator()}. The default
    * behavior, which traverses the values for one key, the values for a second
    * key, and so on, suffices for most {@code AbstractMapBasedMultimap} implementations.
    *
    * @return an iterator across map entries
    */
   @Override
   Iterator<Map.Entry<K, V>> entryIterator() {
     return new Itr<Map.Entry<K, V>>() {
       @Override
       Entry<K, V> output(K key, V value) {
         return Maps.immutableEntry(key, value);
       }
     };
   }
 
   @Override
   Map<K, Collection<V>> createAsMap() {
     // TreeMultimap uses NavigableAsMap explicitly, but we don't handle that here for GWT
     // compatibility reasons
     return (map instanceof SortedMap)
         ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map);
   }
 
   private class AsMap extends ImprovedAbstractMap<K, Collection<V>> {
     /**
      * Usually the same as map, but smaller for the headMap(), tailMap(), or
      * subMap() of a SortedAsMap.
      */
     final transient Map<K, Collection<V>> submap;
 
     AsMap(Map<K, Collection<V>> submap) {
       this.submap = submap;
     }
 
     @Override
     protected Set<Entry<K, Collection<V>>> createEntrySet() {
       return new AsMapEntries();
     }
 
     // The following methods are included for performance.
 
     @Override public boolean containsKey(Object key) {
       return Maps.safeContainsKey(submap, key);
     }
 
     @Override public Collection<V> get(Object key) {
       Collection<V> collection = Maps.safeGet(submap, key);
       if (collection == null) {
         return null;
       }
       @SuppressWarnings("unchecked")
       K k = (K) key;
       return wrapCollection(k, collection);
     }
 
     @Override public Set<K> keySet() {
       return AbstractMapBasedMultimap.this.keySet();
     }
 
     @Override
     public int size() {
       return submap.size();
     }
 
     @Override public Collection<V> remove(Object key) {
       Collection<V> collection = submap.remove(key);
       if (collection == null) {
         return null;
       }
 
       Collection<V> output = createCollection();
       output.addAll(collection);
       totalSize -= collection.size();
       collection.clear();
       return output;
     }
 
     @Override public boolean equals(@Nullable Object object) {
       return this == object || submap.equals(object);
     }
 
     @Override public int hashCode() {
       return submap.hashCode();
     }
 
     @Override public String toString() {
       return submap.toString();
     }
 
     @Override
     public void clear() {
       if (submap == map) {
         AbstractMapBasedMultimap.this.clear();
       } else {
         Iterators.clear(new AsMapIterator());
       }
     }
 
     Entry<K, Collection<V>> wrapEntry(Entry<K, Collection<V>> entry) {
       K key = entry.getKey();
       return Maps.immutableEntry(key, wrapCollection(key, entry.getValue()));
     }
 
     class AsMapEntries extends Maps.EntrySet<K, Collection<V>> {
       @Override
       Map<K, Collection<V>> map() {
         return AsMap.this;
       }
 
       @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
         return new AsMapIterator();
       }
 
       // The following methods are included for performance.
 
       @Override public boolean contains(Object o) {
         return Collections2.safeContains(submap.entrySet(), o);
       }
 
       @Override public boolean remove(Object o) {
         if (!contains(o)) {
           return false;
         }
         Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
         removeValuesForKey(entry.getKey());
         return true;
       }
     }
 
     /** Iterator across all keys and value collections. */
     class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> {
       final Iterator<Map.Entry<K, Collection<V>>> delegateIterator
           = submap.entrySet().iterator();
       Collection<V> collection;
 
       @Override
       public boolean hasNext() {
         return delegateIterator.hasNext();
       }
 
       @Override
       public Map.Entry<K, Collection<V>> next() {
         Map.Entry<K, Collection<V>> entry = delegateIterator.next();
         collection = entry.getValue();
         return wrapEntry(entry);
       }
 
       @Override
       public void remove() {
         delegateIterator.remove();
         totalSize -= collection.size();
         collection.clear();
       }
     }
   }
 
   private class SortedAsMap extends AsMap
       implements SortedMap<K, Collection<V>> {
     SortedAsMap(SortedMap<K, Collection<V>> submap) {
       super(submap);
     }
 
     SortedMap<K, Collection<V>> sortedMap() {
       return (SortedMap<K, Collection<V>>) submap;
     }
 
     @Override
     public Comparator<? super K> comparator() {
       return sortedMap().comparator();
     }
 
     @Override
     public K firstKey() {
       return sortedMap().firstKey();
     }
 
     @Override
     public K lastKey() {
       return sortedMap().lastKey();
     }
 
     @Override
     public SortedMap<K, Collection<V>> headMap(K toKey) {
       return new SortedAsMap(sortedMap().headMap(toKey));
     }
 
     @Override
     public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) {
       return new SortedAsMap(sortedMap().subMap(fromKey, toKey));
     }
 
     @Override
     public SortedMap<K, Collection<V>> tailMap(K fromKey) {
       return new SortedAsMap(sortedMap().tailMap(fromKey));
     }
 
     SortedSet<K> sortedKeySet;
 
     // returns a SortedSet, even though returning a Set would be sufficient to
     // satisfy the SortedMap.keySet() interface
     @Override public SortedSet<K> keySet() {
       SortedSet<K> result = sortedKeySet;
       return (result == null) ? sortedKeySet = createKeySet() : result;
     }
 
     @Override
     SortedSet<K> createKeySet() {
       return new SortedKeySet(sortedMap());
     }
   }
 
   @GwtIncompatible("NavigableAsMap")
   class NavigableAsMap extends SortedAsMap implements NavigableMap<K, Collection<V>> {
 
     NavigableAsMap(NavigableMap<K, Collection<V>> submap) {
       super(submap);
     }
 
     @Override
     NavigableMap<K, Collection<V>> sortedMap() {
       return (NavigableMap<K, Collection<V>>) super.sortedMap();
     }
 
     @Override
     public Entry<K, Collection<V>> lowerEntry(K key) {
       Entry<K, Collection<V>> entry = sortedMap().lowerEntry(key);
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public K lowerKey(K key) {
       return sortedMap().lowerKey(key);
     }
 
     @Override
     public Entry<K, Collection<V>> floorEntry(K key) {
       Entry<K, Collection<V>> entry = sortedMap().floorEntry(key);
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public K floorKey(K key) {
       return sortedMap().floorKey(key);
     }
 
     @Override
     public Entry<K, Collection<V>> ceilingEntry(K key) {
       Entry<K, Collection<V>> entry = sortedMap().ceilingEntry(key);
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public K ceilingKey(K key) {
       return sortedMap().ceilingKey(key);
     }
 
     @Override
     public Entry<K, Collection<V>> higherEntry(K key) {
       Entry<K, Collection<V>> entry = sortedMap().higherEntry(key);
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public K higherKey(K key) {
       return sortedMap().higherKey(key);
     }
 
     @Override
     public Entry<K, Collection<V>> firstEntry() {
       Entry<K, Collection<V>> entry = sortedMap().firstEntry();
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public Entry<K, Collection<V>> lastEntry() {
       Entry<K, Collection<V>> entry = sortedMap().lastEntry();
       return (entry == null) ? null : wrapEntry(entry);
     }
 
     @Override
     public Entry<K, Collection<V>> pollFirstEntry() {
       return pollAsMapEntry(entrySet().iterator());
     }
 
     @Override
     public Entry<K, Collection<V>> pollLastEntry() {
       return pollAsMapEntry(descendingMap().entrySet().iterator());
     }
 
     Map.Entry<K, Collection<V>> pollAsMapEntry(Iterator<Entry<K, Collection<V>>> entryIterator) {
       if (!entryIterator.hasNext()) {
         return null;
       }
       Entry<K, Collection<V>> entry = entryIterator.next();
       Collection<V> output = createCollection();
       output.addAll(entry.getValue());
       entryIterator.remove();
       return Maps.immutableEntry(entry.getKey(), unmodifiableCollectionSubclass(output));
     }
 
     @Override
     public NavigableMap<K, Collection<V>> descendingMap() {
       return new NavigableAsMap(sortedMap().descendingMap());
     }
 
     @Override
     public NavigableSet<K> keySet() {
       return (NavigableSet<K>) super.keySet();
     }
 
     @Override
     NavigableSet<K> createKeySet() {
       return new NavigableKeySet(sortedMap());
     }
 
     @Override
     public NavigableSet<K> navigableKeySet() {
       return keySet();
     }
 
     @Override
     public NavigableSet<K> descendingKeySet() {
       return descendingMap().navigableKeySet();
     }
 
     @Override
     public NavigableMap<K, Collection<V>> subMap(K fromKey, K toKey) {
       return subMap(fromKey, true, toKey, false);
     }
 
     @Override
     public NavigableMap<K, Collection<V>> subMap(
         K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
       return new NavigableAsMap(sortedMap().subMap(fromKey, fromInclusive, toKey, toInclusive));
     }
 
     @Override
     public NavigableMap<K, Collection<V>> headMap(K toKey) {
       return headMap(toKey, false);
     }
 
     @Override
     public NavigableMap<K, Collection<V>> headMap(K toKey, boolean inclusive) {
       return new NavigableAsMap(sortedMap().headMap(toKey, inclusive));
     }
 
     @Override
     public NavigableMap<K, Collection<V>> tailMap(K fromKey) {
       return tailMap(fromKey, true);
     }
 
     @Override
     public NavigableMap<K, Collection<V>> tailMap(K fromKey, boolean inclusive) {
       return new NavigableAsMap(sortedMap().tailMap(fromKey, inclusive));
     }
   }
 
   private static final long serialVersionUID = 2447537837011683357L;
 }