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