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