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