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