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