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