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