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