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