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