/*
 * 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.collect.AbstractMultimap.Entries;
import com.google.common.collect.AbstractMultimap.EntrySet;
import com.google.common.collect.Maps.ViewCachingAbstractMap;
import com.google.j2objc.annotations.WeakOuter;
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 java.util.Spliterator;
import java.util.function.BiConsumer;
import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

Basic implementation of the Multimap interface. This class represents a multimap as a map that associates each key with a collection of values. All methods of Multimap are supported, including those specified as optional in the interface. 
To implement a multimap, a subclass must define the method createCollection(), which creates an empty collection of values for a key. 
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, 
AbstractMapBasedMultimap calls createCollection() to create the collection of values for that key. The subclass should not call createCollection() directly, and a new instance should be created every time the method is called. 
For example, the subclass could pass a TreeMap during construction, and createCollection() could return a TreeSet, in which case the multimap's iterators would propagate through the keys and values in sorted order. 
Keys and values may be null, as long as the underlying collection classes support null
elements.
The collections created by createCollection() may or may not allow duplicates. If the collection, such as a 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 List that allow duplicates, the collection will keep the existing key-value pairs while adding a new pair. 
This class is not threadsafe when any concurrent operations update the multimap, even if the underlying map and createCollection() method return threadsafe classes. Concurrent read operations will work correctly. To allow concurrent update operations, wrap your multimap with a call to Multimaps.synchronizedMultimap. 
For serialization to work, the subclass must specify explicit readObject and 
writeObject methods. 
Author:
Jared Levy, Louis Wasserman/**
 * 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
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.
Params:
map – place to store the mapping from each key to its corresponding values
Throws:
IllegalArgumentException – if map is not empty/**
   * 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. /** 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.
This is used in removeAll on an empty key. /**
   * 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.
Collections with weak, soft, or phantom references are not supported. Each call to 
createCollection should create a new instance. 
The returned collection class determines whether duplicate key-value pairs are allowed.
Returns:
an empty collection of values/**
   * 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 createCollection(), which is the correct behavior for most implementations. The LinkedHashMultimap class overrides it. 
Params:
key – key to associate with values in the collection
Returns:
an empty collection of values/**
   * 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}
The returned collection is immutable.
/**
   * {@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(lowasser): 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}
The returned collection is immutable.
/**
   * {@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);
  }

  <E> Collection<E> unmodifiableCollectionSubclass(Collection<E> collection) {
    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}
The returned collection is not serializable.
/**
   * {@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.
/**
   * 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) {
    return new WrappedCollection(key, collection, null);
  }

  final 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.
Full collections, identified by a null ancestor field, contain all multimap values for a given key. Its delegate is a value in AbstractMapBasedMultimap.map whenever the delegate is non-empty. The refreshIfEmpty, removeIfEmpty, and addToMap methods ensure that the WrappedCollection and map remain consistent. 
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 refreshIfEmpty, removeIfEmpty, and addToMap methods call the corresponding methods of the full wrapped collection. /**
   * 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.
   */
  @WeakOuter
  class WrappedCollection extends AbstractCollection<V> {
    final @Nullable K key;
    Collection<V> delegate;
    final @Nullable WrappedCollection ancestor;
    final @Nullable 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.
For a subcollection, refresh its ancestor and validate that the ancestor delegate hasn't
changed.
/**
     * 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 AbstractMapBasedMultimap.this.map. For subcollections, check whether the ancestor collection is empty. /**
     * 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 WrappedCollection methods should call this method after adding elements to a previously empty collection. 
Subcollection add the ancestor's delegate instead.
/**
     * 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();
    }

    @Override
    public Spliterator<V> spliterator() {
      refreshIfEmpty();
      return delegate.spliterator();
    }

    
Collection iterator for WrappedCollection. /** 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.
/**
       * 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 static <E> Iterator<E> iteratorOrListIterator(Collection<E> collection) {
    return (collection instanceof List)
        ? ((List<E>) collection).listIterator()
        : collection.iterator();
  }

  
Set decorator that stays in sync with the multimap values for a key. /** Set decorator that stays in sync with the multimap values for a key. */
  @WeakOuter
  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. /** SortedSet decorator that stays in sync with the multimap values for a key. */
  @WeakOuter
  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());
    }
  }

  @WeakOuter
  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. /** List decorator that stays in sync with the multimap values for a key. */
  @WeakOuter
  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. /** 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.
/**
   * 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() {
    return new KeySet(map);
  }
  
  final Set<K> createMaybeNavigableKeySet() {
    if (map instanceof NavigableMap) {
      return new NavigableKeySet((NavigableMap<K, Collection<V>>) map);
    } else if (map instanceof SortedMap) {
      return new SortedKeySet((SortedMap<K, Collection<V>>) map);
    } else {
      return new KeySet(map);
    }
  }

  @WeakOuter
  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<Entry<K, Collection<V>>> entryIterator = map().entrySet().iterator();
      return new Iterator<K>() {
        @Nullable 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();
          entry = null;
        }
      };
    }

    // The following methods are included for better performance.

    @Override
    public Spliterator<K> spliterator() {
      return map().keySet().spliterator();
    }

    @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();
    }
  }

  @WeakOuter
  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));
    }
  }

  @WeakOuter
  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. /** Removes all values for the provided key. */
  private void removeValuesForKey(Object key) {
    Collection<V> collection = Maps.safeRemove(map, key);

    if (collection != null) {
      int count = collection.size();
      collection.clear();
      totalSize -= count;
    }
  }

  private abstract class Itr<T> implements Iterator<T> {
    final Iterator<Entry<K, Collection<V>>> keyIterator;
    @Nullable K key;
    @MonotonicNonNull 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()) {
        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}
The iterator generated by the returned collection traverses the values for one key, followed
by the values of a second key, and so on.
/**
   * {@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
  Collection<V> createValues() {
    return new Values();
  }

  @Override
  Iterator<V> valueIterator() {
    return new Itr<V>() {
      @Override
      V output(K key, V value) {
        return value;
      }
    };
  }

  @Override
  Spliterator<V> valueSpliterator() {
    return CollectSpliterators.flatMap(
        map.values().spliterator(), Collection::spliterator, Spliterator.SIZED, size());
  }

  /*
   * 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?
   */

  @Override
  Multiset<K> createKeys() {
    return new Multimaps.Keys<K, V>(this);
  }

  
{@inheritDoc}
The iterator generated by the returned collection traverses the values for one key, followed
by the values of a second key, and so on.
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.
/**
   * {@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<Entry<K, V>> entries() {
    return super.entries();
  }
  
  @Override
  Collection<Entry<K, V>> createEntries() {
    if (this instanceof SetMultimap) {
      return new EntrySet();
    } else {
      return new Entries();
    }
  }

  
Returns an iterator across all key-value map entries, used by entries().iterator() and values().iterator(). The default behavior, which traverses the values for one key, the values for a second key, and so on, suffices for most AbstractMapBasedMultimap implementations. 
Returns:
an iterator across map 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<Entry<K, V>> entryIterator() {
    return new Itr<Entry<K, V>>() {
      @Override
      Entry<K, V> output(K key, V value) {
        return Maps.immutableEntry(key, value);
      }
    };
  }

  @Override
  Spliterator<Entry<K, V>> entrySpliterator() {
    return CollectSpliterators.flatMap(
        map.entrySet().spliterator(),
        keyToValueCollectionEntry -> {
          K key = keyToValueCollectionEntry.getKey();
          Collection<V> valueCollection = keyToValueCollectionEntry.getValue();
          return CollectSpliterators.map(
              valueCollection.spliterator(), (V value) -> Maps.immutableEntry(key, value));
        },
        Spliterator.SIZED,
        size());
  }

  @Override
  public void forEach(BiConsumer<? super K, ? super V> action) {
    checkNotNull(action);
    map.forEach(
        (key, valueCollection) -> valueCollection.forEach(value -> action.accept(key, value)));
  }

  @Override
  Map<K, Collection<V>> createAsMap() {
    return new AsMap(map);
  }
  
  final Map<K, Collection<V>> createMaybeNavigableAsMap() {
    if (map instanceof NavigableMap) {
      return new NavigableAsMap((NavigableMap<K, Collection<V>>) map);
    } else if (map instanceof SortedMap) {
      return new SortedAsMap((SortedMap<K, Collection<V>>) map);
    } else {
      return new AsMap(map);
    }
  }

  @WeakOuter
  private class AsMap extends ViewCachingAbstractMap<K, Collection<V>> {
    
Usually the same as map, but smaller for the headMap(), tailMap(), or subMap() of a
SortedAsMap.
/**
     * 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()));
    }

    @WeakOuter
    class AsMapEntries extends Maps.EntrySet<K, Collection<V>> {
      @Override
      Map<K, Collection<V>> map() {
        return AsMap.this;
      }

      @Override
      public Iterator<Entry<K, Collection<V>>> iterator() {
        return new AsMapIterator();
      }

      @Override
      public Spliterator<Entry<K, Collection<V>>> spliterator() {
        return CollectSpliterators.map(submap.entrySet().spliterator(), AsMap.this::wrapEntry);
      }

      // 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;
        }
        Entry<?, ?> entry = (Entry<?, ?>) o;
        removeValuesForKey(entry.getKey());
        return true;
      }
    }

    
Iterator across all keys and value collections. /** Iterator across all keys and value collections. */
    class AsMapIterator implements Iterator<Entry<K, Collection<V>>> {
      final Iterator<Entry<K, Collection<V>>> delegateIterator = submap.entrySet().iterator();
      @Nullable Collection<V> collection;

      @Override
      public boolean hasNext() {
        return delegateIterator.hasNext();
      }

      @Override
      public Entry<K, Collection<V>> next() {
        Entry<K, Collection<V>> entry = delegateIterator.next();
        collection = entry.getValue();
        return wrapEntry(entry);
      }

      @Override
      public void remove() {
        checkRemove(collection != null);
        delegateIterator.remove();
        totalSize -= collection.size();
        collection.clear();
        collection = null;
      }
    }
  }

  @WeakOuter
  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));
    }

    @MonotonicNonNull 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());
    }
  }

  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());
    }

    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;
}