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