001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021import static com.google.common.collect.CollectPreconditions.checkRemove;
022import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
023import static java.util.Objects.requireNonNull;
024
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.common.annotations.J2ktIncompatible;
028import com.google.common.base.Function;
029import com.google.common.base.Predicate;
030import com.google.common.base.Predicates;
031import com.google.common.base.Supplier;
032import com.google.common.collect.Maps.EntryTransformer;
033import com.google.errorprone.annotations.CanIgnoreReturnValue;
034import com.google.errorprone.annotations.InlineMe;
035import com.google.errorprone.annotations.concurrent.LazyInit;
036import com.google.j2objc.annotations.Weak;
037import com.google.j2objc.annotations.WeakOuter;
038import java.io.IOException;
039import java.io.ObjectInputStream;
040import java.io.ObjectOutputStream;
041import java.io.Serializable;
042import java.util.AbstractCollection;
043import java.util.Collection;
044import java.util.Collections;
045import java.util.Comparator;
046import java.util.HashSet;
047import java.util.Iterator;
048import java.util.List;
049import java.util.Map;
050import java.util.Map.Entry;
051import java.util.NavigableSet;
052import java.util.NoSuchElementException;
053import java.util.Set;
054import java.util.SortedSet;
055import java.util.stream.Collector;
056import java.util.stream.Stream;
057import org.jspecify.annotations.Nullable;
058
059/**
060 * Provides static methods acting on or generating a {@code Multimap}.
061 *
062 * <p>See the Guava User Guide article on <a href=
063 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multimaps">{@code
064 * Multimaps}</a>.
065 *
066 * @author Jared Levy
067 * @author Robert Konigsberg
068 * @author Mike Bostock
069 * @author Louis Wasserman
070 * @since 2.0
071 */
072@GwtCompatible(emulated = true)
073public final class Multimaps {
074  private Multimaps() {}
075
076  /**
077   * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the
078   * specified supplier. The keys and values of the entries are the result of applying the provided
079   * mapping functions to the input elements, accumulated in the encounter order of the stream.
080   *
081   * <p>Example:
082   *
083   * <pre>{@code
084   * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP =
085   *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
086   *         .collect(
087   *             toMultimap(
088   *                  str -> str.charAt(0),
089   *                  str -> str.substring(1),
090   *                  MultimapBuilder.treeKeys().arrayListValues()::build));
091   *
092   * // is equivalent to
093   *
094   * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP;
095   *
096   * static {
097   *     FIRST_LETTER_MULTIMAP = MultimapBuilder.treeKeys().arrayListValues().build();
098   *     FIRST_LETTER_MULTIMAP.put('b', "anana");
099   *     FIRST_LETTER_MULTIMAP.put('a', "pple");
100   *     FIRST_LETTER_MULTIMAP.put('a', "sparagus");
101   *     FIRST_LETTER_MULTIMAP.put('c', "arrot");
102   *     FIRST_LETTER_MULTIMAP.put('c', "herry");
103   * }
104   * }</pre>
105   *
106   * <p>To collect to an {@link ImmutableMultimap}, use either {@link
107   * ImmutableSetMultimap#toImmutableSetMultimap} or {@link
108   * ImmutableListMultimap#toImmutableListMultimap}.
109   *
110   * @since 33.2.0 (available since 21.0 in guava-jre)
111   */
112  @SuppressWarnings("Java7ApiChecker")
113  @IgnoreJRERequirement // Users will use this only if they're already using streams.
114  public static <
115          T extends @Nullable Object,
116          K extends @Nullable Object,
117          V extends @Nullable Object,
118          M extends Multimap<K, V>>
119      Collector<T, ?, M> toMultimap(
120          java.util.function.Function<? super T, ? extends K> keyFunction,
121          java.util.function.Function<? super T, ? extends V> valueFunction,
122          java.util.function.Supplier<M> multimapSupplier) {
123    return CollectCollectors.<T, K, V, M>toMultimap(keyFunction, valueFunction, multimapSupplier);
124  }
125
126  /**
127   * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the
128   * specified supplier. Each input element is mapped to a key and a stream of values, each of which
129   * are put into the resulting {@code Multimap}, in the encounter order of the stream and the
130   * encounter order of the streams of values.
131   *
132   * <p>Example:
133   *
134   * <pre>{@code
135   * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
136   *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
137   *         .collect(
138   *             flatteningToMultimap(
139   *                  str -> str.charAt(0),
140   *                  str -> str.substring(1).chars().mapToObj(c -> (char) c),
141   *                  MultimapBuilder.linkedHashKeys().arrayListValues()::build));
142   *
143   * // is equivalent to
144   *
145   * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP;
146   *
147   * static {
148   *     FIRST_LETTER_MULTIMAP = MultimapBuilder.linkedHashKeys().arrayListValues().build();
149   *     FIRST_LETTER_MULTIMAP.putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a'));
150   *     FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('p', 'p', 'l', 'e'));
151   *     FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't'));
152   *     FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's'));
153   *     FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y'));
154   * }
155   * }</pre>
156   *
157   * @since 33.2.0 (available since 21.0 in guava-jre)
158   */
159  @SuppressWarnings("Java7ApiChecker")
160  @IgnoreJRERequirement // Users will use this only if they're already using streams.
161  public static <
162          T extends @Nullable Object,
163          K extends @Nullable Object,
164          V extends @Nullable Object,
165          M extends Multimap<K, V>>
166      Collector<T, ?, M> flatteningToMultimap(
167          java.util.function.Function<? super T, ? extends K> keyFunction,
168          java.util.function.Function<? super T, ? extends Stream<? extends V>> valueFunction,
169          java.util.function.Supplier<M> multimapSupplier) {
170    return CollectCollectors.<T, K, V, M>flatteningToMultimap(
171        keyFunction, valueFunction, multimapSupplier);
172  }
173
174  /**
175   * Creates a new {@code Multimap} backed by {@code map}, whose internal value collections are
176   * generated by {@code factory}.
177   *
178   * <p><b>Warning: do not use</b> this method when the collections returned by {@code factory}
179   * implement either {@link List} or {@code Set}! Use the more specific method {@link
180   * #newListMultimap}, {@link #newSetMultimap} or {@link #newSortedSetMultimap} instead, to avoid
181   * very surprising behavior from {@link Multimap#equals}.
182   *
183   * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
184   * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
185   * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
186   * method returns instances of a different class than {@code factory.get()} does.
187   *
188   * <p>The multimap is serializable if {@code map}, {@code factory}, the collections generated by
189   * {@code factory}, and the multimap contents are all serializable.
190   *
191   * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
192   * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
193   * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
194   * #synchronizedMultimap}.
195   *
196   * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()}, {@link
197   * HashMultimap#create()}, {@link LinkedHashMultimap#create()}, {@link
198   * LinkedListMultimap#create()}, {@link TreeMultimap#create()}, and {@link
199   * TreeMultimap#create(Comparator, Comparator)} won't suffice.
200   *
201   * <p>Note: the multimap assumes complete ownership over of {@code map} and the collections
202   * returned by {@code factory}. Those objects should not be manually updated and they should not
203   * use soft, weak, or phantom references.
204   *
205   * @param map place to store the mapping from each key to its corresponding values
206   * @param factory supplier of new, empty collections that will each hold all values for a given
207   *     key
208   * @throws IllegalArgumentException if {@code map} is not empty
209   */
210  public static <K extends @Nullable Object, V extends @Nullable Object> Multimap<K, V> newMultimap(
211      Map<K, Collection<V>> map, final Supplier<? extends Collection<V>> factory) {
212    return new CustomMultimap<>(map, factory);
213  }
214
215  private static class CustomMultimap<K extends @Nullable Object, V extends @Nullable Object>
216      extends AbstractMapBasedMultimap<K, V> {
217    transient Supplier<? extends Collection<V>> factory;
218
219    CustomMultimap(Map<K, Collection<V>> map, Supplier<? extends Collection<V>> factory) {
220      super(map);
221      this.factory = checkNotNull(factory);
222    }
223
224    @Override
225    Set<K> createKeySet() {
226      return createMaybeNavigableKeySet();
227    }
228
229    @Override
230    Map<K, Collection<V>> createAsMap() {
231      return createMaybeNavigableAsMap();
232    }
233
234    @Override
235    protected Collection<V> createCollection() {
236      return factory.get();
237    }
238
239    @Override
240    <E extends @Nullable Object> Collection<E> unmodifiableCollectionSubclass(
241        Collection<E> collection) {
242      if (collection instanceof NavigableSet) {
243        return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection);
244      } else if (collection instanceof SortedSet) {
245        return Collections.unmodifiableSortedSet((SortedSet<E>) collection);
246      } else if (collection instanceof Set) {
247        return Collections.unmodifiableSet((Set<E>) collection);
248      } else if (collection instanceof List) {
249        return Collections.unmodifiableList((List<E>) collection);
250      } else {
251        return Collections.unmodifiableCollection(collection);
252      }
253    }
254
255    @Override
256    Collection<V> wrapCollection(@ParametricNullness K key, Collection<V> collection) {
257      if (collection instanceof List) {
258        return wrapList(key, (List<V>) collection, null);
259      } else if (collection instanceof NavigableSet) {
260        return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
261      } else if (collection instanceof SortedSet) {
262        return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
263      } else if (collection instanceof Set) {
264        return new WrappedSet(key, (Set<V>) collection);
265      } else {
266        return new WrappedCollection(key, collection, null);
267      }
268    }
269
270    // can't use Serialization writeMultimap and populateMultimap methods since
271    // there's no way to generate the empty backing map.
272
273    /**
274     * @serialData the factory and the backing map
275     */
276    @GwtIncompatible // java.io.ObjectOutputStream
277    @J2ktIncompatible
278    private void writeObject(ObjectOutputStream stream) throws IOException {
279      stream.defaultWriteObject();
280      stream.writeObject(factory);
281      stream.writeObject(backingMap());
282    }
283
284    @GwtIncompatible // java.io.ObjectInputStream
285    @J2ktIncompatible
286    @SuppressWarnings("unchecked") // reading data stored by writeObject
287    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
288      stream.defaultReadObject();
289      factory = (Supplier<? extends Collection<V>>) requireNonNull(stream.readObject());
290      Map<K, Collection<V>> map = (Map<K, Collection<V>>) requireNonNull(stream.readObject());
291      setMap(map);
292    }
293
294    @GwtIncompatible // java serialization not supported
295    @J2ktIncompatible
296    private static final long serialVersionUID = 0;
297  }
298
299  /**
300   * Creates a new {@code ListMultimap} that uses the provided map and factory. It can generate a
301   * multimap based on arbitrary {@link Map} and {@link List} classes.
302   *
303   * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
304   * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
305   * toString} methods for the multimap and its returned views. The multimap's {@code get}, {@code
306   * removeAll}, and {@code replaceValues} methods return {@code RandomAccess} lists if the factory
307   * does. However, the multimap's {@code get} method returns instances of a different class than
308   * does {@code factory.get()}.
309   *
310   * <p>The multimap is serializable if {@code map}, {@code factory}, the lists generated by {@code
311   * factory}, and the multimap contents are all serializable.
312   *
313   * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
314   * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
315   * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
316   * #synchronizedListMultimap}.
317   *
318   * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()} and {@link
319   * LinkedListMultimap#create()} won't suffice.
320   *
321   * <p>Note: the multimap assumes complete ownership over of {@code map} and the lists returned by
322   * {@code factory}. Those objects should not be manually updated, they should be empty when
323   * provided, and they should not use soft, weak, or phantom references.
324   *
325   * @param map place to store the mapping from each key to its corresponding values
326   * @param factory supplier of new, empty lists that will each hold all values for a given key
327   * @throws IllegalArgumentException if {@code map} is not empty
328   */
329  public static <K extends @Nullable Object, V extends @Nullable Object>
330      ListMultimap<K, V> newListMultimap(
331          Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
332    return new CustomListMultimap<>(map, factory);
333  }
334
335  private static class CustomListMultimap<K extends @Nullable Object, V extends @Nullable Object>
336      extends AbstractListMultimap<K, V> {
337    transient Supplier<? extends List<V>> factory;
338
339    CustomListMultimap(Map<K, Collection<V>> map, Supplier<? extends List<V>> factory) {
340      super(map);
341      this.factory = checkNotNull(factory);
342    }
343
344    @Override
345    Set<K> createKeySet() {
346      return createMaybeNavigableKeySet();
347    }
348
349    @Override
350    Map<K, Collection<V>> createAsMap() {
351      return createMaybeNavigableAsMap();
352    }
353
354    @Override
355    protected List<V> createCollection() {
356      return factory.get();
357    }
358
359    /**
360     * @serialData the factory and the backing map
361     */
362    @GwtIncompatible // java.io.ObjectOutputStream
363    @J2ktIncompatible
364    private void writeObject(ObjectOutputStream stream) throws IOException {
365      stream.defaultWriteObject();
366      stream.writeObject(factory);
367      stream.writeObject(backingMap());
368    }
369
370    @GwtIncompatible // java.io.ObjectInputStream
371    @J2ktIncompatible
372    @SuppressWarnings("unchecked") // reading data stored by writeObject
373    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
374      stream.defaultReadObject();
375      factory = (Supplier<? extends List<V>>) requireNonNull(stream.readObject());
376      Map<K, Collection<V>> map = (Map<K, Collection<V>>) requireNonNull(stream.readObject());
377      setMap(map);
378    }
379
380    @GwtIncompatible // java serialization not supported
381    @J2ktIncompatible
382    private static final long serialVersionUID = 0;
383  }
384
385  /**
386   * Creates a new {@code SetMultimap} that uses the provided map and factory. It can generate a
387   * multimap based on arbitrary {@link Map} and {@link Set} classes.
388   *
389   * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
390   * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
391   * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
392   * method returns instances of a different class than {@code factory.get()} does.
393   *
394   * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code
395   * factory}, and the multimap contents are all serializable.
396   *
397   * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
398   * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
399   * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
400   * #synchronizedSetMultimap}.
401   *
402   * <p>Call this method only when the simpler methods {@link HashMultimap#create()}, {@link
403   * LinkedHashMultimap#create()}, {@link TreeMultimap#create()}, and {@link
404   * TreeMultimap#create(Comparator, Comparator)} won't suffice.
405   *
406   * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by
407   * {@code factory}. Those objects should not be manually updated and they should not use soft,
408   * weak, or phantom references.
409   *
410   * @param map place to store the mapping from each key to its corresponding values
411   * @param factory supplier of new, empty sets that will each hold all values for a given key
412   * @throws IllegalArgumentException if {@code map} is not empty
413   */
414  public static <K extends @Nullable Object, V extends @Nullable Object>
415      SetMultimap<K, V> newSetMultimap(
416          Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
417    return new CustomSetMultimap<>(map, factory);
418  }
419
420  private static class CustomSetMultimap<K extends @Nullable Object, V extends @Nullable Object>
421      extends AbstractSetMultimap<K, V> {
422    transient Supplier<? extends Set<V>> factory;
423
424    CustomSetMultimap(Map<K, Collection<V>> map, Supplier<? extends Set<V>> factory) {
425      super(map);
426      this.factory = checkNotNull(factory);
427    }
428
429    @Override
430    Set<K> createKeySet() {
431      return createMaybeNavigableKeySet();
432    }
433
434    @Override
435    Map<K, Collection<V>> createAsMap() {
436      return createMaybeNavigableAsMap();
437    }
438
439    @Override
440    protected Set<V> createCollection() {
441      return factory.get();
442    }
443
444    @Override
445    <E extends @Nullable Object> Collection<E> unmodifiableCollectionSubclass(
446        Collection<E> collection) {
447      if (collection instanceof NavigableSet) {
448        return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection);
449      } else if (collection instanceof SortedSet) {
450        return Collections.unmodifiableSortedSet((SortedSet<E>) collection);
451      } else {
452        return Collections.unmodifiableSet((Set<E>) collection);
453      }
454    }
455
456    @Override
457    Collection<V> wrapCollection(@ParametricNullness K key, Collection<V> collection) {
458      if (collection instanceof NavigableSet) {
459        return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
460      } else if (collection instanceof SortedSet) {
461        return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
462      } else {
463        return new WrappedSet(key, (Set<V>) collection);
464      }
465    }
466
467    /**
468     * @serialData the factory and the backing map
469     */
470    @GwtIncompatible // java.io.ObjectOutputStream
471    @J2ktIncompatible
472    private void writeObject(ObjectOutputStream stream) throws IOException {
473      stream.defaultWriteObject();
474      stream.writeObject(factory);
475      stream.writeObject(backingMap());
476    }
477
478    @GwtIncompatible // java.io.ObjectInputStream
479    @J2ktIncompatible
480    @SuppressWarnings("unchecked") // reading data stored by writeObject
481    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
482      stream.defaultReadObject();
483      factory = (Supplier<? extends Set<V>>) requireNonNull(stream.readObject());
484      Map<K, Collection<V>> map = (Map<K, Collection<V>>) requireNonNull(stream.readObject());
485      setMap(map);
486    }
487
488    @GwtIncompatible // not needed in emulated source
489    @J2ktIncompatible
490    private static final long serialVersionUID = 0;
491  }
492
493  /**
494   * Creates a new {@code SortedSetMultimap} that uses the provided map and factory. It can generate
495   * a multimap based on arbitrary {@link Map} and {@link SortedSet} classes.
496   *
497   * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
498   * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
499   * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
500   * method returns instances of a different class than {@code factory.get()} does.
501   *
502   * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code
503   * factory}, and the multimap contents are all serializable.
504   *
505   * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
506   * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
507   * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
508   * #synchronizedSortedSetMultimap}.
509   *
510   * <p>Call this method only when the simpler methods {@link TreeMultimap#create()} and {@link
511   * TreeMultimap#create(Comparator, Comparator)} won't suffice.
512   *
513   * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by
514   * {@code factory}. Those objects should not be manually updated and they should not use soft,
515   * weak, or phantom references.
516   *
517   * @param map place to store the mapping from each key to its corresponding values
518   * @param factory supplier of new, empty sorted sets that will each hold all values for a given
519   *     key
520   * @throws IllegalArgumentException if {@code map} is not empty
521   */
522  public static <K extends @Nullable Object, V extends @Nullable Object>
523      SortedSetMultimap<K, V> newSortedSetMultimap(
524          Map<K, Collection<V>> map, final Supplier<? extends SortedSet<V>> factory) {
525    return new CustomSortedSetMultimap<>(map, factory);
526  }
527
528  private static class CustomSortedSetMultimap<
529          K extends @Nullable Object, V extends @Nullable Object>
530      extends AbstractSortedSetMultimap<K, V> {
531    transient Supplier<? extends SortedSet<V>> factory;
532    transient @Nullable Comparator<? super V> valueComparator;
533
534    CustomSortedSetMultimap(Map<K, Collection<V>> map, Supplier<? extends SortedSet<V>> factory) {
535      super(map);
536      this.factory = checkNotNull(factory);
537      valueComparator = factory.get().comparator();
538    }
539
540    @Override
541    Set<K> createKeySet() {
542      return createMaybeNavigableKeySet();
543    }
544
545    @Override
546    Map<K, Collection<V>> createAsMap() {
547      return createMaybeNavigableAsMap();
548    }
549
550    @Override
551    protected SortedSet<V> createCollection() {
552      return factory.get();
553    }
554
555    @Override
556    public @Nullable Comparator<? super V> valueComparator() {
557      return valueComparator;
558    }
559
560    /**
561     * @serialData the factory and the backing map
562     */
563    @GwtIncompatible // java.io.ObjectOutputStream
564    @J2ktIncompatible
565    private void writeObject(ObjectOutputStream stream) throws IOException {
566      stream.defaultWriteObject();
567      stream.writeObject(factory);
568      stream.writeObject(backingMap());
569    }
570
571    @GwtIncompatible // java.io.ObjectInputStream
572    @J2ktIncompatible
573    @SuppressWarnings("unchecked") // reading data stored by writeObject
574    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
575      stream.defaultReadObject();
576      factory = (Supplier<? extends SortedSet<V>>) requireNonNull(stream.readObject());
577      valueComparator = factory.get().comparator();
578      Map<K, Collection<V>> map = (Map<K, Collection<V>>) requireNonNull(stream.readObject());
579      setMap(map);
580    }
581
582    @GwtIncompatible // not needed in emulated source
583    @J2ktIncompatible
584    private static final long serialVersionUID = 0;
585  }
586
587  /**
588   * Copies each key-value mapping in {@code source} into {@code dest}, with its key and value
589   * reversed.
590   *
591   * <p>If {@code source} is an {@link ImmutableMultimap}, consider using {@link
592   * ImmutableMultimap#inverse} instead.
593   *
594   * @param source any multimap
595   * @param dest the multimap to copy into; usually empty
596   * @return {@code dest}
597   */
598  @CanIgnoreReturnValue
599  public static <K extends @Nullable Object, V extends @Nullable Object, M extends Multimap<K, V>>
600      M invertFrom(Multimap<? extends V, ? extends K> source, M dest) {
601    checkNotNull(dest);
602    for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
603      dest.put(entry.getValue(), entry.getKey());
604    }
605    return dest;
606  }
607
608  /**
609   * Returns a synchronized (thread-safe) multimap backed by the specified multimap. In order to
610   * guarantee serial access, it is critical that <b>all</b> access to the backing multimap is
611   * accomplished through the returned multimap.
612   *
613   * <p>It is imperative that the user manually synchronize on the returned multimap when accessing
614   * any of its collection views:
615   *
616   * <pre>{@code
617   * Multimap<K, V> multimap = Multimaps.synchronizedMultimap(
618   *     HashMultimap.<K, V>create());
619   * ...
620   * Collection<V> values = multimap.get(key);  // Needn't be in synchronized block
621   * ...
622   * synchronized (multimap) {  // Synchronizing on multimap, not values!
623   *   Iterator<V> i = values.iterator(); // Must be in synchronized block
624   *   while (i.hasNext()) {
625   *     foo(i.next());
626   *   }
627   * }
628   * }</pre>
629   *
630   * <p>Failure to follow this advice may result in non-deterministic behavior.
631   *
632   * <p>Note that the generated multimap's {@link Multimap#removeAll} and {@link
633   * Multimap#replaceValues} methods return collections that aren't synchronized.
634   *
635   * <p>The returned multimap will be serializable if the specified multimap is serializable.
636   *
637   * @param multimap the multimap to be wrapped in a synchronized view
638   * @return a synchronized view of the specified multimap
639   */
640  @J2ktIncompatible // Synchronized
641  public static <K extends @Nullable Object, V extends @Nullable Object>
642      Multimap<K, V> synchronizedMultimap(Multimap<K, V> multimap) {
643    return Synchronized.multimap(multimap, null);
644  }
645
646  /**
647   * Returns an unmodifiable view of the specified multimap. Query operations on the returned
648   * multimap "read through" to the specified multimap, and attempts to modify the returned
649   * multimap, either directly or through the multimap's views, result in an {@code
650   * UnsupportedOperationException}.
651   *
652   * <p>The returned multimap will be serializable if the specified multimap is serializable.
653   *
654   * @param delegate the multimap for which an unmodifiable view is to be returned
655   * @return an unmodifiable view of the specified multimap
656   */
657  public static <K extends @Nullable Object, V extends @Nullable Object>
658      Multimap<K, V> unmodifiableMultimap(Multimap<K, V> delegate) {
659    if (delegate instanceof UnmodifiableMultimap || delegate instanceof ImmutableMultimap) {
660      return delegate;
661    }
662    return new UnmodifiableMultimap<>(delegate);
663  }
664
665  /**
666   * Simply returns its argument.
667   *
668   * @deprecated no need to use this
669   * @since 10.0
670   */
671  @InlineMe(
672      replacement = "checkNotNull(delegate)",
673      staticImports = "com.google.common.base.Preconditions.checkNotNull")
674  @Deprecated
675  public static <K, V> Multimap<K, V> unmodifiableMultimap(ImmutableMultimap<K, V> delegate) {
676    return checkNotNull(delegate);
677  }
678
679  private static class UnmodifiableMultimap<K extends @Nullable Object, V extends @Nullable Object>
680      extends ForwardingMultimap<K, V> implements Serializable {
681    final Multimap<K, V> delegate;
682    @LazyInit transient @Nullable Collection<Entry<K, V>> entries;
683    @LazyInit transient @Nullable Multiset<K> keys;
684    @LazyInit transient @Nullable Set<K> keySet;
685    @LazyInit transient @Nullable Collection<V> values;
686    @LazyInit transient @Nullable Map<K, Collection<V>> map;
687
688    UnmodifiableMultimap(final Multimap<K, V> delegate) {
689      this.delegate = checkNotNull(delegate);
690    }
691
692    @Override
693    protected Multimap<K, V> delegate() {
694      return delegate;
695    }
696
697    @Override
698    public void clear() {
699      throw new UnsupportedOperationException();
700    }
701
702    @Override
703    public Map<K, Collection<V>> asMap() {
704      Map<K, Collection<V>> result = map;
705      if (result == null) {
706        result =
707            map =
708                Collections.unmodifiableMap(
709                    Maps.transformValues(
710                        delegate.asMap(), collection -> unmodifiableValueCollection(collection)));
711      }
712      return result;
713    }
714
715    @Override
716    public Collection<Entry<K, V>> entries() {
717      Collection<Entry<K, V>> result = entries;
718      if (result == null) {
719        entries = result = unmodifiableEntries(delegate.entries());
720      }
721      return result;
722    }
723
724    @Override
725    public Collection<V> get(@ParametricNullness K key) {
726      return unmodifiableValueCollection(delegate.get(key));
727    }
728
729    @Override
730    public Multiset<K> keys() {
731      Multiset<K> result = keys;
732      if (result == null) {
733        keys = result = Multisets.unmodifiableMultiset(delegate.keys());
734      }
735      return result;
736    }
737
738    @Override
739    public Set<K> keySet() {
740      Set<K> result = keySet;
741      if (result == null) {
742        keySet = result = Collections.unmodifiableSet(delegate.keySet());
743      }
744      return result;
745    }
746
747    @Override
748    public boolean put(@ParametricNullness K key, @ParametricNullness V value) {
749      throw new UnsupportedOperationException();
750    }
751
752    @Override
753    public boolean putAll(@ParametricNullness K key, Iterable<? extends V> values) {
754      throw new UnsupportedOperationException();
755    }
756
757    @Override
758    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
759      throw new UnsupportedOperationException();
760    }
761
762    @Override
763    public boolean remove(@Nullable Object key, @Nullable Object value) {
764      throw new UnsupportedOperationException();
765    }
766
767    @Override
768    public Collection<V> removeAll(@Nullable Object key) {
769      throw new UnsupportedOperationException();
770    }
771
772    @Override
773    public Collection<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
774      throw new UnsupportedOperationException();
775    }
776
777    @Override
778    public Collection<V> values() {
779      Collection<V> result = values;
780      if (result == null) {
781        values = result = Collections.unmodifiableCollection(delegate.values());
782      }
783      return result;
784    }
785
786    private static final long serialVersionUID = 0;
787  }
788
789  private static class UnmodifiableListMultimap<
790          K extends @Nullable Object, V extends @Nullable Object>
791      extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
792    UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
793      super(delegate);
794    }
795
796    @Override
797    public ListMultimap<K, V> delegate() {
798      return (ListMultimap<K, V>) super.delegate();
799    }
800
801    @Override
802    public List<V> get(@ParametricNullness K key) {
803      return Collections.unmodifiableList(delegate().get(key));
804    }
805
806    @Override
807    public List<V> removeAll(@Nullable Object key) {
808      throw new UnsupportedOperationException();
809    }
810
811    @Override
812    public List<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
813      throw new UnsupportedOperationException();
814    }
815
816    private static final long serialVersionUID = 0;
817  }
818
819  private static class UnmodifiableSetMultimap<
820          K extends @Nullable Object, V extends @Nullable Object>
821      extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
822    UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
823      super(delegate);
824    }
825
826    @Override
827    public SetMultimap<K, V> delegate() {
828      return (SetMultimap<K, V>) super.delegate();
829    }
830
831    @Override
832    public Set<V> get(@ParametricNullness K key) {
833      /*
834       * Note that this doesn't return a SortedSet when delegate is a
835       * SortedSetMultiset, unlike (SortedSet<V>) super.get().
836       */
837      return Collections.unmodifiableSet(delegate().get(key));
838    }
839
840    @Override
841    public Set<Map.Entry<K, V>> entries() {
842      return Maps.unmodifiableEntrySet(delegate().entries());
843    }
844
845    @Override
846    public Set<V> removeAll(@Nullable Object key) {
847      throw new UnsupportedOperationException();
848    }
849
850    @Override
851    public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
852      throw new UnsupportedOperationException();
853    }
854
855    private static final long serialVersionUID = 0;
856  }
857
858  private static class UnmodifiableSortedSetMultimap<
859          K extends @Nullable Object, V extends @Nullable Object>
860      extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
861    UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
862      super(delegate);
863    }
864
865    @Override
866    public SortedSetMultimap<K, V> delegate() {
867      return (SortedSetMultimap<K, V>) super.delegate();
868    }
869
870    @Override
871    public SortedSet<V> get(@ParametricNullness K key) {
872      return Collections.unmodifiableSortedSet(delegate().get(key));
873    }
874
875    @Override
876    public SortedSet<V> removeAll(@Nullable Object key) {
877      throw new UnsupportedOperationException();
878    }
879
880    @Override
881    public SortedSet<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
882      throw new UnsupportedOperationException();
883    }
884
885    @Override
886    public @Nullable Comparator<? super V> valueComparator() {
887      return delegate().valueComparator();
888    }
889
890    private static final long serialVersionUID = 0;
891  }
892
893  /**
894   * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the specified multimap.
895   *
896   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
897   *
898   * <p>The returned multimap will be serializable if the specified multimap is serializable.
899   *
900   * @param multimap the multimap to be wrapped
901   * @return a synchronized view of the specified multimap
902   */
903  @J2ktIncompatible // Synchronized
904  public static <K extends @Nullable Object, V extends @Nullable Object>
905      SetMultimap<K, V> synchronizedSetMultimap(SetMultimap<K, V> multimap) {
906    return Synchronized.setMultimap(multimap, null);
907  }
908
909  /**
910   * Returns an unmodifiable view of the specified {@code SetMultimap}. Query operations on the
911   * returned multimap "read through" to the specified multimap, and attempts to modify the returned
912   * multimap, either directly or through the multimap's views, result in an {@code
913   * UnsupportedOperationException}.
914   *
915   * <p>The returned multimap will be serializable if the specified multimap is serializable.
916   *
917   * @param delegate the multimap for which an unmodifiable view is to be returned
918   * @return an unmodifiable view of the specified multimap
919   */
920  public static <K extends @Nullable Object, V extends @Nullable Object>
921      SetMultimap<K, V> unmodifiableSetMultimap(SetMultimap<K, V> delegate) {
922    if (delegate instanceof UnmodifiableSetMultimap || delegate instanceof ImmutableSetMultimap) {
923      return delegate;
924    }
925    return new UnmodifiableSetMultimap<>(delegate);
926  }
927
928  /**
929   * Simply returns its argument.
930   *
931   * @deprecated no need to use this
932   * @since 10.0
933   */
934  @InlineMe(
935      replacement = "checkNotNull(delegate)",
936      staticImports = "com.google.common.base.Preconditions.checkNotNull")
937  @Deprecated
938  public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
939      ImmutableSetMultimap<K, V> delegate) {
940    return checkNotNull(delegate);
941  }
942
943  /**
944   * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by the specified
945   * multimap.
946   *
947   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
948   *
949   * <p>The returned multimap will be serializable if the specified multimap is serializable.
950   *
951   * @param multimap the multimap to be wrapped
952   * @return a synchronized view of the specified multimap
953   */
954  @J2ktIncompatible // Synchronized
955  public static <K extends @Nullable Object, V extends @Nullable Object>
956      SortedSetMultimap<K, V> synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
957    return Synchronized.sortedSetMultimap(multimap, null);
958  }
959
960  /**
961   * Returns an unmodifiable view of the specified {@code SortedSetMultimap}. Query operations on
962   * the returned multimap "read through" to the specified multimap, and attempts to modify the
963   * returned multimap, either directly or through the multimap's views, result in an {@code
964   * UnsupportedOperationException}.
965   *
966   * <p>The returned multimap will be serializable if the specified multimap is serializable.
967   *
968   * @param delegate the multimap for which an unmodifiable view is to be returned
969   * @return an unmodifiable view of the specified multimap
970   */
971  public static <K extends @Nullable Object, V extends @Nullable Object>
972      SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
973    if (delegate instanceof UnmodifiableSortedSetMultimap) {
974      return delegate;
975    }
976    return new UnmodifiableSortedSetMultimap<>(delegate);
977  }
978
979  /**
980   * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the specified multimap.
981   *
982   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
983   *
984   * @param multimap the multimap to be wrapped
985   * @return a synchronized view of the specified multimap
986   */
987  @J2ktIncompatible // Synchronized
988  public static <K extends @Nullable Object, V extends @Nullable Object>
989      ListMultimap<K, V> synchronizedListMultimap(ListMultimap<K, V> multimap) {
990    return Synchronized.listMultimap(multimap, null);
991  }
992
993  /**
994   * Returns an unmodifiable view of the specified {@code ListMultimap}. Query operations on the
995   * returned multimap "read through" to the specified multimap, and attempts to modify the returned
996   * multimap, either directly or through the multimap's views, result in an {@code
997   * UnsupportedOperationException}.
998   *
999   * <p>The returned multimap will be serializable if the specified multimap is serializable.
1000   *
1001   * @param delegate the multimap for which an unmodifiable view is to be returned
1002   * @return an unmodifiable view of the specified multimap
1003   */
1004  public static <K extends @Nullable Object, V extends @Nullable Object>
1005      ListMultimap<K, V> unmodifiableListMultimap(ListMultimap<K, V> delegate) {
1006    if (delegate instanceof UnmodifiableListMultimap || delegate instanceof ImmutableListMultimap) {
1007      return delegate;
1008    }
1009    return new UnmodifiableListMultimap<>(delegate);
1010  }
1011
1012  /**
1013   * Simply returns its argument.
1014   *
1015   * @deprecated no need to use this
1016   * @since 10.0
1017   */
1018  @InlineMe(
1019      replacement = "checkNotNull(delegate)",
1020      staticImports = "com.google.common.base.Preconditions.checkNotNull")
1021  @Deprecated
1022  public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
1023      ImmutableListMultimap<K, V> delegate) {
1024    return checkNotNull(delegate);
1025  }
1026
1027  /**
1028   * Returns an unmodifiable view of the specified collection, preserving the interface for
1029   * instances of {@code SortedSet}, {@code Set}, {@code List} and {@code Collection}, in that order
1030   * of preference.
1031   *
1032   * @param collection the collection for which to return an unmodifiable view
1033   * @return an unmodifiable view of the collection
1034   */
1035  private static <V extends @Nullable Object> Collection<V> unmodifiableValueCollection(
1036      Collection<V> collection) {
1037    if (collection instanceof SortedSet) {
1038      return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
1039    } else if (collection instanceof Set) {
1040      return Collections.unmodifiableSet((Set<V>) collection);
1041    } else if (collection instanceof List) {
1042      return Collections.unmodifiableList((List<V>) collection);
1043    }
1044    return Collections.unmodifiableCollection(collection);
1045  }
1046
1047  /**
1048   * Returns an unmodifiable view of the specified collection of entries. The {@link Entry#setValue}
1049   * operation throws an {@link UnsupportedOperationException}. If the specified collection is a
1050   * {@code Set}, the returned collection is also a {@code Set}.
1051   *
1052   * @param entries the entries for which to return an unmodifiable view
1053   * @return an unmodifiable view of the entries
1054   */
1055  private static <K extends @Nullable Object, V extends @Nullable Object>
1056      Collection<Entry<K, V>> unmodifiableEntries(Collection<Entry<K, V>> entries) {
1057    if (entries instanceof Set) {
1058      return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
1059    }
1060    return new Maps.UnmodifiableEntries<>(Collections.unmodifiableCollection(entries));
1061  }
1062
1063  /**
1064   * Returns {@link ListMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K,
1065   * Collection<V>>} to {@code Map<K, List<V>>}.
1066   *
1067   * @since 15.0
1068   */
1069  @SuppressWarnings("unchecked")
1070  // safe by specification of ListMultimap.asMap()
1071  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, List<V>> asMap(
1072      ListMultimap<K, V> multimap) {
1073    return (Map<K, List<V>>) (Map<K, ?>) multimap.asMap();
1074  }
1075
1076  /**
1077   * Returns {@link SetMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K,
1078   * Collection<V>>} to {@code Map<K, Set<V>>}.
1079   *
1080   * @since 15.0
1081   */
1082  @SuppressWarnings("unchecked")
1083  // safe by specification of SetMultimap.asMap()
1084  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, Set<V>> asMap(
1085      SetMultimap<K, V> multimap) {
1086    return (Map<K, Set<V>>) (Map<K, ?>) multimap.asMap();
1087  }
1088
1089  /**
1090   * Returns {@link SortedSetMultimap#asMap multimap.asMap()}, with its type corrected from {@code
1091   * Map<K, Collection<V>>} to {@code Map<K, SortedSet<V>>}.
1092   *
1093   * @since 15.0
1094   */
1095  @SuppressWarnings("unchecked")
1096  // safe by specification of SortedSetMultimap.asMap()
1097  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, SortedSet<V>> asMap(
1098      SortedSetMultimap<K, V> multimap) {
1099    return (Map<K, SortedSet<V>>) (Map<K, ?>) multimap.asMap();
1100  }
1101
1102  /**
1103   * Returns {@link Multimap#asMap multimap.asMap()}. This is provided for parity with the other
1104   * more strongly-typed {@code asMap()} implementations.
1105   *
1106   * @since 15.0
1107   */
1108  public static <K extends @Nullable Object, V extends @Nullable Object>
1109      Map<K, Collection<V>> asMap(Multimap<K, V> multimap) {
1110    return multimap.asMap();
1111  }
1112
1113  /**
1114   * Returns a multimap view of the specified map. The multimap is backed by the map, so changes to
1115   * the map are reflected in the multimap, and vice versa. If the map is modified while an
1116   * iteration over one of the multimap's collection views is in progress (except through the
1117   * iterator's own {@code remove} operation, or through the {@code setValue} operation on a map
1118   * entry returned by the iterator), the results of the iteration are undefined.
1119   *
1120   * <p>The multimap supports mapping removal, which removes the corresponding mapping from the map.
1121   * It does not support any operations which might add mappings, such as {@code put}, {@code
1122   * putAll} or {@code replaceValues}.
1123   *
1124   * <p>The returned multimap will be serializable if the specified map is serializable.
1125   *
1126   * @param map the backing map for the returned multimap view
1127   */
1128  public static <K extends @Nullable Object, V extends @Nullable Object> SetMultimap<K, V> forMap(
1129      Map<K, V> map) {
1130    return new MapMultimap<>(map);
1131  }
1132
1133  /** @see Multimaps#forMap */
1134  private static class MapMultimap<K extends @Nullable Object, V extends @Nullable Object>
1135      extends AbstractMultimap<K, V> implements SetMultimap<K, V>, Serializable {
1136    final Map<K, V> map;
1137
1138    MapMultimap(Map<K, V> map) {
1139      this.map = checkNotNull(map);
1140    }
1141
1142    @Override
1143    public int size() {
1144      return map.size();
1145    }
1146
1147    @Override
1148    public boolean containsKey(@Nullable Object key) {
1149      return map.containsKey(key);
1150    }
1151
1152    @Override
1153    public boolean containsValue(@Nullable Object value) {
1154      return map.containsValue(value);
1155    }
1156
1157    @Override
1158    public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
1159      return map.entrySet().contains(Maps.immutableEntry(key, value));
1160    }
1161
1162    @Override
1163    public Set<V> get(@ParametricNullness final K key) {
1164      return new Sets.ImprovedAbstractSet<V>() {
1165        @Override
1166        public Iterator<V> iterator() {
1167          return new Iterator<V>() {
1168            int i;
1169
1170            @Override
1171            public boolean hasNext() {
1172              return (i == 0) && map.containsKey(key);
1173            }
1174
1175            @Override
1176            @ParametricNullness
1177            public V next() {
1178              if (!hasNext()) {
1179                throw new NoSuchElementException();
1180              }
1181              i++;
1182              /*
1183               * The cast is safe because of the containsKey check in hasNext(). (That means it's
1184               * unsafe under concurrent modification, but all bets are off then, anyway.)
1185               */
1186              return uncheckedCastNullableTToT(map.get(key));
1187            }
1188
1189            @Override
1190            public void remove() {
1191              checkRemove(i == 1);
1192              i = -1;
1193              map.remove(key);
1194            }
1195          };
1196        }
1197
1198        @Override
1199        public int size() {
1200          return map.containsKey(key) ? 1 : 0;
1201        }
1202      };
1203    }
1204
1205    @Override
1206    public boolean put(@ParametricNullness K key, @ParametricNullness V value) {
1207      throw new UnsupportedOperationException();
1208    }
1209
1210    @Override
1211    public boolean putAll(@ParametricNullness K key, Iterable<? extends V> values) {
1212      throw new UnsupportedOperationException();
1213    }
1214
1215    @Override
1216    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1217      throw new UnsupportedOperationException();
1218    }
1219
1220    @Override
1221    public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
1222      throw new UnsupportedOperationException();
1223    }
1224
1225    @Override
1226    public boolean remove(@Nullable Object key, @Nullable Object value) {
1227      return map.entrySet().remove(Maps.immutableEntry(key, value));
1228    }
1229
1230    @Override
1231    public Set<V> removeAll(@Nullable Object key) {
1232      Set<V> values = new HashSet<>(2);
1233      if (!map.containsKey(key)) {
1234        return values;
1235      }
1236      values.add(map.remove(key));
1237      return values;
1238    }
1239
1240    @Override
1241    public void clear() {
1242      map.clear();
1243    }
1244
1245    @Override
1246    Set<K> createKeySet() {
1247      return map.keySet();
1248    }
1249
1250    @Override
1251    Collection<V> createValues() {
1252      return map.values();
1253    }
1254
1255    @Override
1256    public Set<Entry<K, V>> entries() {
1257      return map.entrySet();
1258    }
1259
1260    @Override
1261    Collection<Entry<K, V>> createEntries() {
1262      throw new AssertionError("unreachable");
1263    }
1264
1265    @Override
1266    Multiset<K> createKeys() {
1267      return new Multimaps.Keys<K, V>(this);
1268    }
1269
1270    @Override
1271    Iterator<Entry<K, V>> entryIterator() {
1272      return map.entrySet().iterator();
1273    }
1274
1275    @Override
1276    Map<K, Collection<V>> createAsMap() {
1277      return new AsMap<>(this);
1278    }
1279
1280    @Override
1281    public int hashCode() {
1282      return map.hashCode();
1283    }
1284
1285    private static final long serialVersionUID = 7845222491160860175L;
1286  }
1287
1288  /**
1289   * Returns a view of a multimap where each value is transformed by a function. All other
1290   * properties of the multimap, such as iteration order, are left intact. For example, the code:
1291   *
1292   * <pre>{@code
1293   * Multimap<String, Integer> multimap =
1294   *     ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
1295   * Function<Integer, String> square = new Function<Integer, String>() {
1296   *     public String apply(Integer in) {
1297   *       return Integer.toString(in * in);
1298   *     }
1299   * };
1300   * Multimap<String, String> transformed =
1301   *     Multimaps.transformValues(multimap, square);
1302   *   System.out.println(transformed);
1303   * }</pre>
1304   *
1305   * ... prints {@code {a=[4, 16], b=[9, 9], c=[36]}}.
1306   *
1307   * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1308   * supports removal operations, and these are reflected in the underlying multimap.
1309   *
1310   * <p>It's acceptable for the underlying multimap to contain null keys, and even null values
1311   * provided that the function is capable of accepting null input. The transformed multimap might
1312   * contain null values, if the function sometimes gives a null result.
1313   *
1314   * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1315   * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless,
1316   * since there is not a definition of {@code equals} or {@code hashCode} for general collections,
1317   * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a
1318   * {@code Set}.
1319   *
1320   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned
1321   * multimap to be a view, but it means that the function will be applied many times for bulk
1322   * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1323   * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned
1324   * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your
1325   * choosing.
1326   *
1327   * @since 7.0
1328   */
1329  public static <
1330          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1331      Multimap<K, V2> transformValues(
1332          Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1333    checkNotNull(function);
1334    EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1335    return transformEntries(fromMultimap, transformer);
1336  }
1337
1338  /**
1339   * Returns a view of a {@code ListMultimap} where each value is transformed by a function. All
1340   * other properties of the multimap, such as iteration order, are left intact. For example, the
1341   * code:
1342   *
1343   * <pre>{@code
1344   * ListMultimap<String, Integer> multimap
1345   *      = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
1346   * Function<Integer, Double> sqrt =
1347   *     new Function<Integer, Double>() {
1348   *       public Double apply(Integer in) {
1349   *         return Math.sqrt((int) in);
1350   *       }
1351   *     };
1352   * ListMultimap<String, Double> transformed = Multimaps.transformValues(map,
1353   *     sqrt);
1354   * System.out.println(transformed);
1355   * }</pre>
1356   *
1357   * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}.
1358   *
1359   * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1360   * supports removal operations, and these are reflected in the underlying multimap.
1361   *
1362   * <p>It's acceptable for the underlying multimap to contain null keys, and even null values
1363   * provided that the function is capable of accepting null input. The transformed multimap might
1364   * contain null values, if the function sometimes gives a null result.
1365   *
1366   * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1367   * is.
1368   *
1369   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned
1370   * multimap to be a view, but it means that the function will be applied many times for bulk
1371   * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1372   * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned
1373   * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your
1374   * choosing.
1375   *
1376   * @since 7.0
1377   */
1378  public static <
1379          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1380      ListMultimap<K, V2> transformValues(
1381          ListMultimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1382    checkNotNull(function);
1383    EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1384    return transformEntries(fromMultimap, transformer);
1385  }
1386
1387  /**
1388   * Returns a view of a multimap whose values are derived from the original multimap's entries. In
1389   * contrast to {@link #transformValues}, this method's entry-transformation logic may depend on
1390   * the key as well as the value.
1391   *
1392   * <p>All other properties of the transformed multimap, such as iteration order, are left intact.
1393   * For example, the code:
1394   *
1395   * <pre>{@code
1396   * SetMultimap<String, Integer> multimap =
1397   *     ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
1398   * EntryTransformer<String, Integer, String> transformer =
1399   *     new EntryTransformer<String, Integer, String>() {
1400   *       public String transformEntry(String key, Integer value) {
1401   *          return (value >= 0) ? key : "no" + key;
1402   *       }
1403   *     };
1404   * Multimap<String, String> transformed =
1405   *     Multimaps.transformEntries(multimap, transformer);
1406   * System.out.println(transformed);
1407   * }</pre>
1408   *
1409   * ... prints {@code {a=[a, a], b=[nob]}}.
1410   *
1411   * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1412   * supports removal operations, and these are reflected in the underlying multimap.
1413   *
1414   * <p>It's acceptable for the underlying multimap to contain null keys and null values provided
1415   * that the transformer is capable of accepting null inputs. The transformed multimap might
1416   * contain null values if the transformer sometimes gives a null result.
1417   *
1418   * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1419   * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless,
1420   * since there is not a definition of {@code equals} or {@code hashCode} for general collections,
1421   * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a
1422   * {@code Set}.
1423   *
1424   * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1425   * multimap to be a view, but it means that the transformer will be applied many times for bulk
1426   * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform
1427   * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap
1428   * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing.
1429   *
1430   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1431   * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1432   * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1433   * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1434   * transformed multimap.
1435   *
1436   * @since 7.0
1437   */
1438  public static <
1439          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1440      Multimap<K, V2> transformEntries(
1441          Multimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1442    return new TransformedEntriesMultimap<>(fromMap, transformer);
1443  }
1444
1445  /**
1446   * Returns a view of a {@code ListMultimap} whose values are derived from the original multimap's
1447   * entries. In contrast to {@link #transformValues(ListMultimap, Function)}, this method's
1448   * entry-transformation logic may depend on the key as well as the value.
1449   *
1450   * <p>All other properties of the transformed multimap, such as iteration order, are left intact.
1451   * For example, the code:
1452   *
1453   * <pre>{@code
1454   * Multimap<String, Integer> multimap =
1455   *     ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
1456   * EntryTransformer<String, Integer, String> transformer =
1457   *     new EntryTransformer<String, Integer, String>() {
1458   *       public String transformEntry(String key, Integer value) {
1459   *         return key + value;
1460   *       }
1461   *     };
1462   * Multimap<String, String> transformed =
1463   *     Multimaps.transformEntries(multimap, transformer);
1464   * System.out.println(transformed);
1465   * }</pre>
1466   *
1467   * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}.
1468   *
1469   * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1470   * supports removal operations, and these are reflected in the underlying multimap.
1471   *
1472   * <p>It's acceptable for the underlying multimap to contain null keys and null values provided
1473   * that the transformer is capable of accepting null inputs. The transformed multimap might
1474   * contain null values if the transformer sometimes gives a null result.
1475   *
1476   * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1477   * is.
1478   *
1479   * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1480   * multimap to be a view, but it means that the transformer will be applied many times for bulk
1481   * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform
1482   * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap
1483   * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing.
1484   *
1485   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1486   * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1487   * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1488   * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1489   * transformed multimap.
1490   *
1491   * @since 7.0
1492   */
1493  public static <
1494          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1495      ListMultimap<K, V2> transformEntries(
1496          ListMultimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1497    return new TransformedEntriesListMultimap<>(fromMap, transformer);
1498  }
1499
1500  private static class TransformedEntriesMultimap<
1501          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1502      extends AbstractMultimap<K, V2> {
1503    final Multimap<K, V1> fromMultimap;
1504    final EntryTransformer<? super K, ? super V1, V2> transformer;
1505
1506    TransformedEntriesMultimap(
1507        Multimap<K, V1> fromMultimap,
1508        final EntryTransformer<? super K, ? super V1, V2> transformer) {
1509      this.fromMultimap = checkNotNull(fromMultimap);
1510      this.transformer = checkNotNull(transformer);
1511    }
1512
1513    Collection<V2> transform(@ParametricNullness K key, Collection<V1> values) {
1514      Function<? super V1, V2> function = Maps.asValueToValueFunction(transformer, key);
1515      if (values instanceof List) {
1516        return Lists.transform((List<V1>) values, function);
1517      } else {
1518        return Collections2.transform(values, function);
1519      }
1520    }
1521
1522    @Override
1523    Map<K, Collection<V2>> createAsMap() {
1524      return Maps.transformEntries(fromMultimap.asMap(), (key, value) -> transform(key, value));
1525    }
1526
1527    @Override
1528    public void clear() {
1529      fromMultimap.clear();
1530    }
1531
1532    @Override
1533    public boolean containsKey(@Nullable Object key) {
1534      return fromMultimap.containsKey(key);
1535    }
1536
1537    @Override
1538    Collection<Entry<K, V2>> createEntries() {
1539      return new Entries();
1540    }
1541
1542    @Override
1543    Iterator<Entry<K, V2>> entryIterator() {
1544      return Iterators.transform(
1545          fromMultimap.entries().iterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
1546    }
1547
1548    @Override
1549    public Collection<V2> get(@ParametricNullness final K key) {
1550      return transform(key, fromMultimap.get(key));
1551    }
1552
1553    @Override
1554    public boolean isEmpty() {
1555      return fromMultimap.isEmpty();
1556    }
1557
1558    @Override
1559    Set<K> createKeySet() {
1560      return fromMultimap.keySet();
1561    }
1562
1563    @Override
1564    Multiset<K> createKeys() {
1565      return fromMultimap.keys();
1566    }
1567
1568    @Override
1569    public boolean put(@ParametricNullness K key, @ParametricNullness V2 value) {
1570      throw new UnsupportedOperationException();
1571    }
1572
1573    @Override
1574    public boolean putAll(@ParametricNullness K key, Iterable<? extends V2> values) {
1575      throw new UnsupportedOperationException();
1576    }
1577
1578    @Override
1579    public boolean putAll(Multimap<? extends K, ? extends V2> multimap) {
1580      throw new UnsupportedOperationException();
1581    }
1582
1583    @SuppressWarnings("unchecked")
1584    @Override
1585    public boolean remove(@Nullable Object key, @Nullable Object value) {
1586      return get((K) key).remove(value);
1587    }
1588
1589    @SuppressWarnings("unchecked")
1590    @Override
1591    public Collection<V2> removeAll(@Nullable Object key) {
1592      return transform((K) key, fromMultimap.removeAll(key));
1593    }
1594
1595    @Override
1596    public Collection<V2> replaceValues(@ParametricNullness K key, Iterable<? extends V2> values) {
1597      throw new UnsupportedOperationException();
1598    }
1599
1600    @Override
1601    public int size() {
1602      return fromMultimap.size();
1603    }
1604
1605    @Override
1606    Collection<V2> createValues() {
1607      return Collections2.transform(
1608          fromMultimap.entries(), Maps.<K, V1, V2>asEntryToValueFunction(transformer));
1609    }
1610  }
1611
1612  private static final class TransformedEntriesListMultimap<
1613          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1614      extends TransformedEntriesMultimap<K, V1, V2> implements ListMultimap<K, V2> {
1615
1616    TransformedEntriesListMultimap(
1617        ListMultimap<K, V1> fromMultimap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1618      super(fromMultimap, transformer);
1619    }
1620
1621    @Override
1622    List<V2> transform(@ParametricNullness K key, Collection<V1> values) {
1623      return Lists.transform((List<V1>) values, Maps.asValueToValueFunction(transformer, key));
1624    }
1625
1626    @Override
1627    public List<V2> get(@ParametricNullness K key) {
1628      return transform(key, fromMultimap.get(key));
1629    }
1630
1631    @SuppressWarnings("unchecked")
1632    @Override
1633    public List<V2> removeAll(@Nullable Object key) {
1634      return transform((K) key, fromMultimap.removeAll(key));
1635    }
1636
1637    @Override
1638    public List<V2> replaceValues(@ParametricNullness K key, Iterable<? extends V2> values) {
1639      throw new UnsupportedOperationException();
1640    }
1641  }
1642
1643  /**
1644   * Creates an index {@code ImmutableListMultimap} that contains the results of applying a
1645   * specified function to each item in an {@code Iterable} of values. Each value will be stored as
1646   * a value in the resulting multimap, yielding a multimap with the same size as the input
1647   * iterable. The key used to store that value in the multimap will be the result of calling the
1648   * function on that value. The resulting multimap is created as an immutable snapshot. In the
1649   * returned multimap, keys appear in the order they are first encountered, and the values
1650   * corresponding to each key appear in the same order as they are encountered.
1651   *
1652   * <p>For example,
1653   *
1654   * <pre>{@code
1655   * List<String> badGuys =
1656   *     Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1657   * Function<String, Integer> stringLengthFunction = ...;
1658   * Multimap<Integer, String> index =
1659   *     Multimaps.index(badGuys, stringLengthFunction);
1660   * System.out.println(index);
1661   * }</pre>
1662   *
1663   * <p>prints
1664   *
1665   * <pre>{@code
1666   * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}
1667   * }</pre>
1668   *
1669   * <p>The returned multimap is serializable if its keys and values are all serializable.
1670   *
1671   * @param values the values to use when constructing the {@code ImmutableListMultimap}
1672   * @param keyFunction the function used to produce the key for each value
1673   * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code
1674   *     keyFunction} on each value in the input collection to that value
1675   * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1676   *     keyFunction} produces {@code null} for any key
1677   */
1678  public static <K, V> ImmutableListMultimap<K, V> index(
1679      Iterable<V> values, Function<? super V, K> keyFunction) {
1680    return index(values.iterator(), keyFunction);
1681  }
1682
1683  /**
1684   * Creates an index {@code ImmutableListMultimap} that contains the results of applying a
1685   * specified function to each item in an {@code Iterator} of values. Each value will be stored as
1686   * a value in the resulting multimap, yielding a multimap with the same size as the input
1687   * iterator. The key used to store that value in the multimap will be the result of calling the
1688   * function on that value. The resulting multimap is created as an immutable snapshot. In the
1689   * returned multimap, keys appear in the order they are first encountered, and the values
1690   * corresponding to each key appear in the same order as they are encountered.
1691   *
1692   * <p>For example,
1693   *
1694   * <pre>{@code
1695   * List<String> badGuys =
1696   *     Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1697   * Function<String, Integer> stringLengthFunction = ...;
1698   * Multimap<Integer, String> index =
1699   *     Multimaps.index(badGuys.iterator(), stringLengthFunction);
1700   * System.out.println(index);
1701   * }</pre>
1702   *
1703   * <p>prints
1704   *
1705   * <pre>{@code
1706   * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}
1707   * }</pre>
1708   *
1709   * <p>The returned multimap is serializable if its keys and values are all serializable.
1710   *
1711   * @param values the values to use when constructing the {@code ImmutableListMultimap}
1712   * @param keyFunction the function used to produce the key for each value
1713   * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code
1714   *     keyFunction} on each value in the input collection to that value
1715   * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1716   *     keyFunction} produces {@code null} for any key
1717   * @since 10.0
1718   */
1719  public static <K, V> ImmutableListMultimap<K, V> index(
1720      Iterator<V> values, Function<? super V, K> keyFunction) {
1721    checkNotNull(keyFunction);
1722    ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
1723    while (values.hasNext()) {
1724      V value = values.next();
1725      checkNotNull(value, values);
1726      builder.put(keyFunction.apply(value), value);
1727    }
1728    return builder.build();
1729  }
1730
1731  static class Keys<K extends @Nullable Object, V extends @Nullable Object>
1732      extends AbstractMultiset<K> {
1733    @Weak final Multimap<K, V> multimap;
1734
1735    Keys(Multimap<K, V> multimap) {
1736      this.multimap = multimap;
1737    }
1738
1739    @Override
1740    Iterator<Multiset.Entry<K>> entryIterator() {
1741      return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>(
1742          multimap.asMap().entrySet().iterator()) {
1743        @Override
1744        Multiset.Entry<K> transform(final Map.Entry<K, Collection<V>> backingEntry) {
1745          return new Multisets.AbstractEntry<K>() {
1746            @Override
1747            @ParametricNullness
1748            public K getElement() {
1749              return backingEntry.getKey();
1750            }
1751
1752            @Override
1753            public int getCount() {
1754              return backingEntry.getValue().size();
1755            }
1756          };
1757        }
1758      };
1759    }
1760
1761    @Override
1762    int distinctElements() {
1763      return multimap.asMap().size();
1764    }
1765
1766    @Override
1767    public int size() {
1768      return multimap.size();
1769    }
1770
1771    @Override
1772    public boolean contains(@Nullable Object element) {
1773      return multimap.containsKey(element);
1774    }
1775
1776    @Override
1777    public Iterator<K> iterator() {
1778      return Maps.keyIterator(multimap.entries().iterator());
1779    }
1780
1781    @Override
1782    public int count(@Nullable Object element) {
1783      Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1784      return (values == null) ? 0 : values.size();
1785    }
1786
1787    @Override
1788    public int remove(@Nullable Object element, int occurrences) {
1789      checkNonnegative(occurrences, "occurrences");
1790      if (occurrences == 0) {
1791        return count(element);
1792      }
1793
1794      Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1795
1796      if (values == null) {
1797        return 0;
1798      }
1799
1800      int oldCount = values.size();
1801      if (occurrences >= oldCount) {
1802        values.clear();
1803      } else {
1804        Iterator<V> iterator = values.iterator();
1805        for (int i = 0; i < occurrences; i++) {
1806          iterator.next();
1807          iterator.remove();
1808        }
1809      }
1810      return oldCount;
1811    }
1812
1813    @Override
1814    public void clear() {
1815      multimap.clear();
1816    }
1817
1818    @Override
1819    public Set<K> elementSet() {
1820      return multimap.keySet();
1821    }
1822
1823    @Override
1824    Iterator<K> elementIterator() {
1825      throw new AssertionError("should never be called");
1826    }
1827  }
1828
1829  /** A skeleton implementation of {@link Multimap#entries()}. */
1830  abstract static class Entries<K extends @Nullable Object, V extends @Nullable Object>
1831      extends AbstractCollection<Map.Entry<K, V>> {
1832    abstract Multimap<K, V> multimap();
1833
1834    @Override
1835    public int size() {
1836      return multimap().size();
1837    }
1838
1839    @Override
1840    public boolean contains(@Nullable Object o) {
1841      if (o instanceof Map.Entry) {
1842        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1843        return multimap().containsEntry(entry.getKey(), entry.getValue());
1844      }
1845      return false;
1846    }
1847
1848    @Override
1849    public boolean remove(@Nullable Object o) {
1850      if (o instanceof Map.Entry) {
1851        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1852        return multimap().remove(entry.getKey(), entry.getValue());
1853      }
1854      return false;
1855    }
1856
1857    @Override
1858    public void clear() {
1859      multimap().clear();
1860    }
1861  }
1862
1863  /** A skeleton implementation of {@link Multimap#asMap()}. */
1864  static final class AsMap<K extends @Nullable Object, V extends @Nullable Object>
1865      extends Maps.ViewCachingAbstractMap<K, Collection<V>> {
1866    @Weak private final Multimap<K, V> multimap;
1867
1868    AsMap(Multimap<K, V> multimap) {
1869      this.multimap = checkNotNull(multimap);
1870    }
1871
1872    @Override
1873    public int size() {
1874      return multimap.keySet().size();
1875    }
1876
1877    @Override
1878    protected Set<Entry<K, Collection<V>>> createEntrySet() {
1879      return new EntrySet();
1880    }
1881
1882    void removeValuesForKey(@Nullable Object key) {
1883      multimap.keySet().remove(key);
1884    }
1885
1886    @WeakOuter
1887    class EntrySet extends Maps.EntrySet<K, Collection<V>> {
1888      @Override
1889      Map<K, Collection<V>> map() {
1890        return AsMap.this;
1891      }
1892
1893      @Override
1894      public Iterator<Entry<K, Collection<V>>> iterator() {
1895        return Maps.asMapEntryIterator(multimap.keySet(), key -> multimap.get(key));
1896      }
1897
1898      @Override
1899      public boolean remove(@Nullable Object o) {
1900        if (!contains(o)) {
1901          return false;
1902        }
1903        // requireNonNull is safe because of the contains check.
1904        Map.Entry<?, ?> entry = requireNonNull((Map.Entry<?, ?>) o);
1905        removeValuesForKey(entry.getKey());
1906        return true;
1907      }
1908    }
1909
1910    @SuppressWarnings("unchecked")
1911    @Override
1912    public @Nullable Collection<V> get(@Nullable Object key) {
1913      return containsKey(key) ? multimap.get((K) key) : null;
1914    }
1915
1916    @Override
1917    public @Nullable Collection<V> remove(@Nullable Object key) {
1918      return containsKey(key) ? multimap.removeAll(key) : null;
1919    }
1920
1921    @Override
1922    public Set<K> keySet() {
1923      return multimap.keySet();
1924    }
1925
1926    @Override
1927    public boolean isEmpty() {
1928      return multimap.isEmpty();
1929    }
1930
1931    @Override
1932    public boolean containsKey(@Nullable Object key) {
1933      return multimap.containsKey(key);
1934    }
1935
1936    @Override
1937    public void clear() {
1938      multimap.clear();
1939    }
1940  }
1941
1942  /**
1943   * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
1944   * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
1945   * the other.
1946   *
1947   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
1948   * other methods are supported by the multimap and its views. When adding a key that doesn't
1949   * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
1950   * replaceValues()} methods throw an {@link IllegalArgumentException}.
1951   *
1952   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
1953   * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
1954   * underlying multimap.
1955   *
1956   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
1957   *
1958   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
1959   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
1960   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
1961   * copy.
1962   *
1963   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
1964   * {@link Predicate#apply}. Do not provide a predicate such as {@code
1965   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
1966   *
1967   * @since 11.0
1968   */
1969  public static <K extends @Nullable Object, V extends @Nullable Object> Multimap<K, V> filterKeys(
1970      Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1971    if (unfiltered instanceof SetMultimap) {
1972      return filterKeys((SetMultimap<K, V>) unfiltered, keyPredicate);
1973    } else if (unfiltered instanceof ListMultimap) {
1974      return filterKeys((ListMultimap<K, V>) unfiltered, keyPredicate);
1975    } else if (unfiltered instanceof FilteredKeyMultimap) {
1976      FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap<K, V>) unfiltered;
1977      return new FilteredKeyMultimap<>(
1978          prev.unfiltered, Predicates.<K>and(prev.keyPredicate, keyPredicate));
1979    } else if (unfiltered instanceof FilteredMultimap) {
1980      FilteredMultimap<K, V> prev = (FilteredMultimap<K, V>) unfiltered;
1981      return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
1982    } else {
1983      return new FilteredKeyMultimap<>(unfiltered, keyPredicate);
1984    }
1985  }
1986
1987  /**
1988   * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
1989   * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
1990   * the other.
1991   *
1992   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
1993   * other methods are supported by the multimap and its views. When adding a key that doesn't
1994   * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
1995   * replaceValues()} methods throw an {@link IllegalArgumentException}.
1996   *
1997   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
1998   * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
1999   * underlying multimap.
2000   *
2001   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2002   *
2003   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2004   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2005   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2006   * copy.
2007   *
2008   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
2009   * {@link Predicate#apply}. Do not provide a predicate such as {@code
2010   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2011   *
2012   * @since 14.0
2013   */
2014  public static <K extends @Nullable Object, V extends @Nullable Object>
2015      SetMultimap<K, V> filterKeys(
2016          SetMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2017    if (unfiltered instanceof FilteredKeySetMultimap) {
2018      FilteredKeySetMultimap<K, V> prev = (FilteredKeySetMultimap<K, V>) unfiltered;
2019      return new FilteredKeySetMultimap<>(
2020          prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
2021    } else if (unfiltered instanceof FilteredSetMultimap) {
2022      FilteredSetMultimap<K, V> prev = (FilteredSetMultimap<K, V>) unfiltered;
2023      return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
2024    } else {
2025      return new FilteredKeySetMultimap<>(unfiltered, keyPredicate);
2026    }
2027  }
2028
2029  /**
2030   * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
2031   * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
2032   * the other.
2033   *
2034   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2035   * other methods are supported by the multimap and its views. When adding a key that doesn't
2036   * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
2037   * replaceValues()} methods throw an {@link IllegalArgumentException}.
2038   *
2039   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2040   * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
2041   * underlying multimap.
2042   *
2043   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2044   *
2045   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2046   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2047   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2048   * copy.
2049   *
2050   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
2051   * {@link Predicate#apply}. Do not provide a predicate such as {@code
2052   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2053   *
2054   * @since 14.0
2055   */
2056  public static <K extends @Nullable Object, V extends @Nullable Object>
2057      ListMultimap<K, V> filterKeys(
2058          ListMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2059    if (unfiltered instanceof FilteredKeyListMultimap) {
2060      FilteredKeyListMultimap<K, V> prev = (FilteredKeyListMultimap<K, V>) unfiltered;
2061      return new FilteredKeyListMultimap<>(
2062          prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
2063    } else {
2064      return new FilteredKeyListMultimap<>(unfiltered, keyPredicate);
2065    }
2066  }
2067
2068  /**
2069   * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a
2070   * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
2071   * the other.
2072   *
2073   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2074   * other methods are supported by the multimap and its views. When adding a value that doesn't
2075   * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
2076   * replaceValues()} methods throw an {@link IllegalArgumentException}.
2077   *
2078   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2079   * multimap or its views, only mappings whose value satisfy the filter will be removed from the
2080   * underlying multimap.
2081   *
2082   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2083   *
2084   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2085   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2086   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2087   * copy.
2088   *
2089   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2090   * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2091   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2092   *
2093   * @since 11.0
2094   */
2095  public static <K extends @Nullable Object, V extends @Nullable Object>
2096      Multimap<K, V> filterValues(
2097          Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2098    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2099  }
2100
2101  /**
2102   * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a
2103   * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
2104   * the other.
2105   *
2106   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2107   * other methods are supported by the multimap and its views. When adding a value that doesn't
2108   * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
2109   * replaceValues()} methods throw an {@link IllegalArgumentException}.
2110   *
2111   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2112   * multimap or its views, only mappings whose value satisfy the filter will be removed from the
2113   * underlying multimap.
2114   *
2115   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2116   *
2117   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2118   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2119   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2120   * copy.
2121   *
2122   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2123   * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2124   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2125   *
2126   * @since 14.0
2127   */
2128  public static <K extends @Nullable Object, V extends @Nullable Object>
2129      SetMultimap<K, V> filterValues(
2130          SetMultimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2131    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2132  }
2133
2134  /**
2135   * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2136   * returned multimap is a live view of {@code unfiltered}; changes to one affect the other.
2137   *
2138   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2139   * other methods are supported by the multimap and its views. When adding a key/value pair that
2140   * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code
2141   * replaceValues()} methods throw an {@link IllegalArgumentException}.
2142   *
2143   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2144   * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
2145   * underlying multimap.
2146   *
2147   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2148   *
2149   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2150   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2151   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2152   * copy.
2153   *
2154   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2155   * at {@link Predicate#apply}.
2156   *
2157   * @since 11.0
2158   */
2159  public static <K extends @Nullable Object, V extends @Nullable Object>
2160      Multimap<K, V> filterEntries(
2161          Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2162    checkNotNull(entryPredicate);
2163    if (unfiltered instanceof SetMultimap) {
2164      return filterEntries((SetMultimap<K, V>) unfiltered, entryPredicate);
2165    }
2166    return (unfiltered instanceof FilteredMultimap)
2167        ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
2168        : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2169  }
2170
2171  /**
2172   * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2173   * returned multimap is a live view of {@code unfiltered}; changes to one affect the other.
2174   *
2175   * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2176   * other methods are supported by the multimap and its views. When adding a key/value pair that
2177   * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code
2178   * replaceValues()} methods throw an {@link IllegalArgumentException}.
2179   *
2180   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2181   * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
2182   * underlying multimap.
2183   *
2184   * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2185   *
2186   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2187   * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2188   * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2189   * copy.
2190   *
2191   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2192   * at {@link Predicate#apply}.
2193   *
2194   * @since 14.0
2195   */
2196  public static <K extends @Nullable Object, V extends @Nullable Object>
2197      SetMultimap<K, V> filterEntries(
2198          SetMultimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2199    checkNotNull(entryPredicate);
2200    return (unfiltered instanceof FilteredSetMultimap)
2201        ? filterFiltered((FilteredSetMultimap<K, V>) unfiltered, entryPredicate)
2202        : new FilteredEntrySetMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2203  }
2204
2205  /**
2206   * Support removal operations when filtering a filtered multimap. Since a filtered multimap has
2207   * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would
2208   * lead to a multimap whose removal operations would fail. This method combines the predicates to
2209   * avoid that problem.
2210   */
2211  private static <K extends @Nullable Object, V extends @Nullable Object>
2212      Multimap<K, V> filterFiltered(
2213          FilteredMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) {
2214    Predicate<Entry<K, V>> predicate =
2215        Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate);
2216    return new FilteredEntryMultimap<>(multimap.unfiltered(), predicate);
2217  }
2218
2219  /**
2220   * Support removal operations when filtering a filtered multimap. Since a filtered multimap has
2221   * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would
2222   * lead to a multimap whose removal operations would fail. This method combines the predicates to
2223   * avoid that problem.
2224   */
2225  private static <K extends @Nullable Object, V extends @Nullable Object>
2226      SetMultimap<K, V> filterFiltered(
2227          FilteredSetMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) {
2228    Predicate<Entry<K, V>> predicate =
2229        Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate);
2230    return new FilteredEntrySetMultimap<>(multimap.unfiltered(), predicate);
2231  }
2232
2233  static boolean equalsImpl(Multimap<?, ?> multimap, @Nullable Object object) {
2234    if (object == multimap) {
2235      return true;
2236    }
2237    if (object instanceof Multimap) {
2238      Multimap<?, ?> that = (Multimap<?, ?>) object;
2239      return multimap.asMap().equals(that.asMap());
2240    }
2241    return false;
2242  }
2243
2244  // TODO(jlevy): Create methods that filter a SortedSetMultimap.
2245}