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