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