001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkNonnegative;
021import static com.google.common.collect.CollectPreconditions.checkRemove;
022
023import com.google.common.annotations.Beta;
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.base.Function;
027import com.google.common.base.Predicate;
028import com.google.common.base.Predicates;
029import com.google.common.base.Supplier;
030import com.google.common.collect.Maps.EntryTransformer;
031import com.google.errorprone.annotations.CanIgnoreReturnValue;
032import com.google.j2objc.annotations.Weak;
033import com.google.j2objc.annotations.WeakOuter;
034import java.io.IOException;
035import java.io.ObjectInputStream;
036import java.io.ObjectOutputStream;
037import java.io.Serializable;
038import java.util.AbstractCollection;
039import java.util.Collection;
040import java.util.Collections;
041import java.util.Comparator;
042import java.util.HashSet;
043import java.util.Iterator;
044import java.util.List;
045import java.util.Map;
046import java.util.Map.Entry;
047import java.util.NoSuchElementException;
048import java.util.Set;
049import java.util.SortedSet;
050import java.util.Spliterator;
051import java.util.function.Consumer;
052import java.util.stream.Collector;
053import java.util.stream.Stream;
054import javax.annotation.Nullable;
055
056/**
057 * Provides static methods acting on or generating a {@code Multimap}.
058 *
059 * <p>See the Guava User Guide article on <a href=
060 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multimaps">
061 * {@code Multimaps}</a>.
062 *
063 * @author Jared Levy
064 * @author Robert Konigsberg
065 * @author Mike Bostock
066 * @author Louis Wasserman
067 * @since 2.0
068 */
069@GwtCompatible(emulated = true)
070public final class Multimaps {
071  private Multimaps() {}
072
073  /**
074   * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the
075   * specified supplier. The keys and values of the entries are the result of applying the provided
076   * mapping functions to the input elements, accumulated in the encounter order of the stream.
077   *
078   * <p>Example:
079   *
080   * <pre>{@code
081   * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP =
082   *     Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
083   *         .collect(
084   *             toMultimap(
085   *                  str -> str.charAt(0),
086   *                  str -> str.substring(1),
087   *                  MultimapBuilder.treeKeys().arrayListValues()::build));
088   *
089   * // is equivalent to
090   *
091   * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP;
092   *
093   * static {
094   *     FIRST_LETTER_MULTIMAP = MultimapBuilder.treeKeys().arrayListValues().build();
095   *     FIRST_LETTER_MULTIMAP.put('b', "anana");
096   *     FIRST_LETTER_MULTIMAP.put('a', "pple");
097   *     FIRST_LETTER_MULTIMAP.put('a', "sparagus");
098   *     FIRST_LETTER_MULTIMAP.put('c', "arrot");
099   *     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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V>(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<K, V1, V2>(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<K, V1, V2>(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<K, V>(
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<K, V>(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<K, V>(
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<K, V>(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<K, V>(
2038          prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
2039    } else {
2040      return new FilteredKeyListMultimap<K, V>(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<K, V>(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<K, V>(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}