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