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.base.Preconditions.checkState;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.base.Function;
026import com.google.common.base.Joiner;
027import com.google.common.base.Joiner.MapJoiner;
028import com.google.common.base.Objects;
029import com.google.common.base.Predicate;
030import com.google.common.base.Predicates;
031import com.google.common.base.Supplier;
032import com.google.common.collect.Collections2.TransformedCollection;
033import com.google.common.collect.Maps.EntryTransformer;
034
035import java.io.IOException;
036import java.io.ObjectInputStream;
037import java.io.ObjectOutputStream;
038import java.io.Serializable;
039import java.util.AbstractCollection;
040import java.util.Collection;
041import java.util.Collections;
042import java.util.Comparator;
043import java.util.HashSet;
044import java.util.Iterator;
045import java.util.List;
046import java.util.Map;
047import java.util.Map.Entry;
048import java.util.NoSuchElementException;
049import java.util.Set;
050import java.util.SortedSet;
051
052import javax.annotation.Nullable;
053
054/**
055 * Provides static methods acting on or generating a {@code Multimap}.
056 *
057 * <p>See the Guava User Guide article on <a href=
058 * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Multimaps">
059 * {@code Multimaps}</a>.
060 *
061 * @author Jared Levy
062 * @author Robert Konigsberg
063 * @author Mike Bostock
064 * @author Louis Wasserman
065 * @since 2.0 (imported from Google Collections Library)
066 */
067@GwtCompatible(emulated = true)
068public final class Multimaps {
069  private Multimaps() {}
070
071  /**
072   * Creates a new {@code Multimap} that uses the provided map and factory. It
073   * can generate a multimap based on arbitrary {@link Map} and
074   * {@link Collection} classes.
075   *
076   * <p>The {@code factory}-generated and {@code map} classes determine the
077   * multimap iteration order. They also specify the behavior of the
078   * {@code equals}, {@code hashCode}, and {@code toString} methods for the
079   * multimap and its returned views. However, the multimap's {@code get}
080   * method returns instances of a different class than {@code factory.get()}
081   * does.
082   *
083   * <p>The multimap is serializable if {@code map}, {@code factory}, the
084   * collections generated by {@code factory}, and the multimap contents are all
085   * serializable.
086   *
087   * <p>The multimap is not threadsafe when any concurrent operations update the
088   * multimap, even if {@code map} and the instances generated by
089   * {@code factory} are. Concurrent read operations will work correctly. To
090   * allow concurrent update operations, wrap the multimap with a call to
091   * {@link #synchronizedMultimap}.
092   *
093   * <p>Call this method only when the simpler methods
094   * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()},
095   * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()},
096   * {@link TreeMultimap#create()}, and
097   * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
098   *
099   * <p>Note: the multimap assumes complete ownership over of {@code map} and
100   * the collections returned by {@code factory}. Those objects should not be
101   * manually updated and they should not use soft, weak, or phantom references.
102   *
103   * @param map place to store the mapping from each key to its corresponding
104   *     values
105   * @param factory supplier of new, empty collections that will each hold all
106   *     values for a given key
107   * @throws IllegalArgumentException if {@code map} is not empty
108   */
109  public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
110      final Supplier<? extends Collection<V>> factory) {
111    return new CustomMultimap<K, V>(map, factory);
112  }
113
114  private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> {
115    transient Supplier<? extends Collection<V>> factory;
116
117    CustomMultimap(Map<K, Collection<V>> map,
118        Supplier<? extends Collection<V>> factory) {
119      super(map);
120      this.factory = checkNotNull(factory);
121    }
122
123    @Override protected Collection<V> createCollection() {
124      return factory.get();
125    }
126
127    // can't use Serialization writeMultimap and populateMultimap methods since
128    // there's no way to generate the empty backing map.
129
130    /** @serialData the factory and the backing map */
131    @GwtIncompatible("java.io.ObjectOutputStream")
132    private void writeObject(ObjectOutputStream stream) throws IOException {
133      stream.defaultWriteObject();
134      stream.writeObject(factory);
135      stream.writeObject(backingMap());
136    }
137
138    @GwtIncompatible("java.io.ObjectInputStream")
139    @SuppressWarnings("unchecked") // reading data stored by writeObject
140    private void readObject(ObjectInputStream stream)
141        throws IOException, ClassNotFoundException {
142      stream.defaultReadObject();
143      factory = (Supplier<? extends Collection<V>>) stream.readObject();
144      Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
145      setMap(map);
146    }
147
148    @GwtIncompatible("java serialization not supported")
149    private static final long serialVersionUID = 0;
150  }
151
152  /**
153   * Creates a new {@code ListMultimap} that uses the provided map and factory.
154   * It can generate a multimap based on arbitrary {@link Map} and {@link List}
155   * classes.
156   *
157   * <p>The {@code factory}-generated and {@code map} classes determine the
158   * multimap iteration order. They also specify the behavior of the
159   * {@code equals}, {@code hashCode}, and {@code toString} methods for the
160   * multimap and its returned views. The multimap's {@code get}, {@code
161   * removeAll}, and {@code replaceValues} methods return {@code RandomAccess}
162   * lists if the factory does. However, the multimap's {@code get} method
163   * returns instances of a different class than does {@code factory.get()}.
164   *
165   * <p>The multimap is serializable if {@code map}, {@code factory}, the
166   * lists generated by {@code factory}, and the multimap contents are all
167   * serializable.
168   *
169   * <p>The multimap is not threadsafe when any concurrent operations update the
170   * multimap, even if {@code map} and the instances generated by
171   * {@code factory} are. Concurrent read operations will work correctly. To
172   * allow concurrent update operations, wrap the multimap with a call to
173   * {@link #synchronizedListMultimap}.
174   *
175   * <p>Call this method only when the simpler methods
176   * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()}
177   * won't suffice.
178   *
179   * <p>Note: the multimap assumes complete ownership over of {@code map} and
180   * the lists returned by {@code factory}. Those objects should not be manually
181   * updated, they should be empty when provided, and they should not use soft,
182   * weak, or phantom references.
183   *
184   * @param map place to store the mapping from each key to its corresponding
185   *     values
186   * @param factory supplier of new, empty lists that will each hold all values
187   *     for a given key
188   * @throws IllegalArgumentException if {@code map} is not empty
189   */
190  public static <K, V> ListMultimap<K, V> newListMultimap(
191      Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
192    return new CustomListMultimap<K, V>(map, factory);
193  }
194
195  private static class CustomListMultimap<K, V>
196      extends AbstractListMultimap<K, V> {
197    transient Supplier<? extends List<V>> factory;
198
199    CustomListMultimap(Map<K, Collection<V>> map,
200        Supplier<? extends List<V>> factory) {
201      super(map);
202      this.factory = checkNotNull(factory);
203    }
204
205    @Override protected List<V> createCollection() {
206      return factory.get();
207    }
208
209    /** @serialData the factory and the backing map */
210    @GwtIncompatible("java.io.ObjectOutputStream")
211    private void writeObject(ObjectOutputStream stream) throws IOException {
212      stream.defaultWriteObject();
213      stream.writeObject(factory);
214      stream.writeObject(backingMap());
215    }
216
217    @GwtIncompatible("java.io.ObjectInputStream")
218    @SuppressWarnings("unchecked") // reading data stored by writeObject
219    private void readObject(ObjectInputStream stream)
220        throws IOException, ClassNotFoundException {
221      stream.defaultReadObject();
222      factory = (Supplier<? extends List<V>>) stream.readObject();
223      Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
224      setMap(map);
225    }
226
227    @GwtIncompatible("java serialization not supported")
228    private static final long serialVersionUID = 0;
229  }
230
231  /**
232   * Creates a new {@code SetMultimap} that uses the provided map and factory.
233   * It can generate a multimap based on arbitrary {@link Map} and {@link Set}
234   * classes.
235   *
236   * <p>The {@code factory}-generated and {@code map} classes determine the
237   * multimap iteration order. They also specify the behavior of the
238   * {@code equals}, {@code hashCode}, and {@code toString} methods for the
239   * multimap and its returned views. However, the multimap's {@code get}
240   * method returns instances of a different class than {@code factory.get()}
241   * does.
242   *
243   * <p>The multimap is serializable if {@code map}, {@code factory}, the
244   * sets generated by {@code factory}, and the multimap contents are all
245   * serializable.
246   *
247   * <p>The multimap is not threadsafe when any concurrent operations update the
248   * multimap, even if {@code map} and the instances generated by
249   * {@code factory} are. Concurrent read operations will work correctly. To
250   * allow concurrent update operations, wrap the multimap with a call to
251   * {@link #synchronizedSetMultimap}.
252   *
253   * <p>Call this method only when the simpler methods
254   * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()},
255   * {@link TreeMultimap#create()}, and
256   * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
257   *
258   * <p>Note: the multimap assumes complete ownership over of {@code map} and
259   * the sets returned by {@code factory}. Those objects should not be manually
260   * updated and they should not use soft, weak, or phantom references.
261   *
262   * @param map place to store the mapping from each key to its corresponding
263   *     values
264   * @param factory supplier of new, empty sets that will each hold all values
265   *     for a given key
266   * @throws IllegalArgumentException if {@code map} is not empty
267   */
268  public static <K, V> SetMultimap<K, V> newSetMultimap(
269      Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
270    return new CustomSetMultimap<K, V>(map, factory);
271  }
272
273  private static class CustomSetMultimap<K, V>
274      extends AbstractSetMultimap<K, V> {
275    transient Supplier<? extends Set<V>> factory;
276
277    CustomSetMultimap(Map<K, Collection<V>> map,
278        Supplier<? extends Set<V>> factory) {
279      super(map);
280      this.factory = checkNotNull(factory);
281    }
282
283    @Override protected Set<V> createCollection() {
284      return factory.get();
285    }
286
287    /** @serialData the factory and the backing map */
288    @GwtIncompatible("java.io.ObjectOutputStream")
289    private void writeObject(ObjectOutputStream stream) throws IOException {
290      stream.defaultWriteObject();
291      stream.writeObject(factory);
292      stream.writeObject(backingMap());
293    }
294
295    @GwtIncompatible("java.io.ObjectInputStream")
296    @SuppressWarnings("unchecked") // reading data stored by writeObject
297    private void readObject(ObjectInputStream stream)
298        throws IOException, ClassNotFoundException {
299      stream.defaultReadObject();
300      factory = (Supplier<? extends Set<V>>) stream.readObject();
301      Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
302      setMap(map);
303    }
304
305    @GwtIncompatible("not needed in emulated source")
306    private static final long serialVersionUID = 0;
307  }
308
309  /**
310   * Creates a new {@code SortedSetMultimap} that uses the provided map and
311   * factory. It can generate a multimap based on arbitrary {@link Map} and
312   * {@link SortedSet} classes.
313   *
314   * <p>The {@code factory}-generated and {@code map} classes determine the
315   * multimap iteration order. They also specify the behavior of the
316   * {@code equals}, {@code hashCode}, and {@code toString} methods for the
317   * multimap and its returned views. However, the multimap's {@code get}
318   * method returns instances of a different class than {@code factory.get()}
319   * does.
320   *
321   * <p>The multimap is serializable if {@code map}, {@code factory}, the
322   * sets generated by {@code factory}, and the multimap contents are all
323   * serializable.
324   *
325   * <p>The multimap is not threadsafe when any concurrent operations update the
326   * multimap, even if {@code map} and the instances generated by
327   * {@code factory} are. Concurrent read operations will work correctly. To
328   * allow concurrent update operations, wrap the multimap with a call to
329   * {@link #synchronizedSortedSetMultimap}.
330   *
331   * <p>Call this method only when the simpler methods
332   * {@link TreeMultimap#create()} and
333   * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
334   *
335   * <p>Note: the multimap assumes complete ownership over of {@code map} and
336   * the sets returned by {@code factory}. Those objects should not be manually
337   * updated and they should not use soft, weak, or phantom references.
338   *
339   * @param map place to store the mapping from each key to its corresponding
340   *     values
341   * @param factory supplier of new, empty sorted sets that will each hold
342   *     all values for a given key
343   * @throws IllegalArgumentException if {@code map} is not empty
344   */
345  public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
346      Map<K, Collection<V>> map,
347      final Supplier<? extends SortedSet<V>> factory) {
348    return new CustomSortedSetMultimap<K, V>(map, factory);
349  }
350
351  private static class CustomSortedSetMultimap<K, V>
352      extends AbstractSortedSetMultimap<K, V> {
353    transient Supplier<? extends SortedSet<V>> factory;
354    transient Comparator<? super V> valueComparator;
355
356    CustomSortedSetMultimap(Map<K, Collection<V>> map,
357        Supplier<? extends SortedSet<V>> factory) {
358      super(map);
359      this.factory = checkNotNull(factory);
360      valueComparator = factory.get().comparator();
361    }
362
363    @Override protected SortedSet<V> createCollection() {
364      return factory.get();
365    }
366
367    @Override public Comparator<? super V> valueComparator() {
368      return valueComparator;
369    }
370
371    /** @serialData the factory and the backing map */
372    @GwtIncompatible("java.io.ObjectOutputStream")
373    private void writeObject(ObjectOutputStream stream) throws IOException {
374      stream.defaultWriteObject();
375      stream.writeObject(factory);
376      stream.writeObject(backingMap());
377    }
378
379    @GwtIncompatible("java.io.ObjectInputStream")
380    @SuppressWarnings("unchecked") // reading data stored by writeObject
381    private void readObject(ObjectInputStream stream)
382        throws IOException, ClassNotFoundException {
383      stream.defaultReadObject();
384      factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
385      valueComparator = factory.get().comparator();
386      Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
387      setMap(map);
388    }
389
390    @GwtIncompatible("not needed in emulated source")
391    private static final long serialVersionUID = 0;
392  }
393
394  /**
395   * Copies each key-value mapping in {@code source} into {@code dest}, with
396   * its key and value reversed.
397   *
398   * <p>If {@code source} is an {@link ImmutableMultimap}, consider using
399   * {@link ImmutableMultimap#inverse} instead.
400   *
401   * @param source any multimap
402   * @param dest the multimap to copy into; usually empty
403   * @return {@code dest}
404   */
405  public static <K, V, M extends Multimap<K, V>> M invertFrom(
406      Multimap<? extends V, ? extends K> source, M dest) {
407    checkNotNull(dest);
408    for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
409      dest.put(entry.getValue(), entry.getKey());
410    }
411    return dest;
412  }
413
414  /**
415   * Returns a synchronized (thread-safe) multimap backed by the specified
416   * multimap. In order to guarantee serial access, it is critical that
417   * <b>all</b> access to the backing multimap is accomplished through the
418   * returned multimap.
419   *
420   * <p>It is imperative that the user manually synchronize on the returned
421   * multimap when accessing any of its collection views: <pre>   {@code
422   *
423   *   Multimap<K, V> multimap = Multimaps.synchronizedMultimap(
424   *       HashMultimap.<K, V>create());
425   *   ...
426   *   Collection<V> values = multimap.get(key);  // Needn't be in synchronized block
427   *   ...
428   *   synchronized (multimap) {  // Synchronizing on multimap, not values!
429   *     Iterator<V> i = values.iterator(); // Must be in synchronized block
430   *     while (i.hasNext()) {
431   *       foo(i.next());
432   *     }
433   *   }}</pre>
434   *
435   * Failure to follow this advice may result in non-deterministic behavior.
436   *
437   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
438   * {@link Multimap#replaceValues} methods return collections that aren't
439   * synchronized.
440   *
441   * <p>The returned multimap will be serializable if the specified multimap is
442   * serializable.
443   *
444   * @param multimap the multimap to be wrapped in a synchronized view
445   * @return a synchronized view of the specified multimap
446   */
447  public static <K, V> Multimap<K, V> synchronizedMultimap(
448      Multimap<K, V> multimap) {
449    return Synchronized.multimap(multimap, null);
450  }
451
452  /**
453   * Returns an unmodifiable view of the specified multimap. Query operations on
454   * the returned multimap "read through" to the specified multimap, and
455   * attempts to modify the returned multimap, either directly or through the
456   * multimap's views, result in an {@code UnsupportedOperationException}.
457   *
458   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
459   * {@link Multimap#replaceValues} methods return collections that are
460   * modifiable.
461   *
462   * <p>The returned multimap will be serializable if the specified multimap is
463   * serializable.
464   *
465   * @param delegate the multimap for which an unmodifiable view is to be
466   *     returned
467   * @return an unmodifiable view of the specified multimap
468   */
469  public static <K, V> Multimap<K, V> unmodifiableMultimap(
470      Multimap<K, V> delegate) {
471    if (delegate instanceof UnmodifiableMultimap ||
472        delegate instanceof ImmutableMultimap) {
473      return delegate;
474    }
475    return new UnmodifiableMultimap<K, V>(delegate);
476  }
477
478  /**
479   * Simply returns its argument.
480   *
481   * @deprecated no need to use this
482   * @since 10.0
483   */
484  @Deprecated public static <K, V> Multimap<K, V> unmodifiableMultimap(
485      ImmutableMultimap<K, V> delegate) {
486    return checkNotNull(delegate);
487  }
488
489  private static class UnmodifiableMultimap<K, V>
490      extends ForwardingMultimap<K, V> implements Serializable {
491    final Multimap<K, V> delegate;
492    transient Collection<Entry<K, V>> entries;
493    transient Multiset<K> keys;
494    transient Set<K> keySet;
495    transient Collection<V> values;
496    transient Map<K, Collection<V>> map;
497
498    UnmodifiableMultimap(final Multimap<K, V> delegate) {
499      this.delegate = checkNotNull(delegate);
500    }
501
502    @Override protected Multimap<K, V> delegate() {
503      return delegate;
504    }
505
506    @Override public void clear() {
507      throw new UnsupportedOperationException();
508    }
509
510    @Override public Map<K, Collection<V>> asMap() {
511      Map<K, Collection<V>> result = map;
512      if (result == null) {
513        final Map<K, Collection<V>> unmodifiableMap
514            = Collections.unmodifiableMap(delegate.asMap());
515        map = result = new ForwardingMap<K, Collection<V>>() {
516          @Override protected Map<K, Collection<V>> delegate() {
517            return unmodifiableMap;
518          }
519
520          Set<Entry<K, Collection<V>>> entrySet;
521
522          @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
523            Set<Entry<K, Collection<V>>> result = entrySet;
524            return (result == null)
525                ? entrySet
526                    = unmodifiableAsMapEntries(unmodifiableMap.entrySet())
527                : result;
528          }
529
530          @Override public Collection<V> get(Object key) {
531            Collection<V> collection = unmodifiableMap.get(key);
532            return (collection == null)
533                ? null : unmodifiableValueCollection(collection);
534          }
535
536          Collection<Collection<V>> asMapValues;
537
538          @Override public Collection<Collection<V>> values() {
539            Collection<Collection<V>> result = asMapValues;
540            return (result == null)
541                ? asMapValues
542                    = new UnmodifiableAsMapValues<V>(unmodifiableMap.values())
543                : result;
544          }
545
546          @Override public boolean containsValue(Object o) {
547            return values().contains(o);
548          }
549        };
550      }
551      return result;
552    }
553
554    @Override public Collection<Entry<K, V>> entries() {
555      Collection<Entry<K, V>> result = entries;
556      if (result == null) {
557        entries = result = unmodifiableEntries(delegate.entries());
558      }
559      return result;
560    }
561
562    @Override public Collection<V> get(K key) {
563      return unmodifiableValueCollection(delegate.get(key));
564    }
565
566    @Override public Multiset<K> keys() {
567      Multiset<K> result = keys;
568      if (result == null) {
569        keys = result = Multisets.unmodifiableMultiset(delegate.keys());
570      }
571      return result;
572    }
573
574    @Override public Set<K> keySet() {
575      Set<K> result = keySet;
576      if (result == null) {
577        keySet = result = Collections.unmodifiableSet(delegate.keySet());
578      }
579      return result;
580    }
581
582    @Override public boolean put(K key, V value) {
583      throw new UnsupportedOperationException();
584    }
585
586    @Override public boolean putAll(K key, Iterable<? extends V> values) {
587      throw new UnsupportedOperationException();
588    }
589
590    @Override
591    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
592      throw new UnsupportedOperationException();
593    }
594
595    @Override public boolean remove(Object key, Object value) {
596      throw new UnsupportedOperationException();
597    }
598
599    @Override public Collection<V> removeAll(Object key) {
600      throw new UnsupportedOperationException();
601    }
602
603    @Override public Collection<V> replaceValues(
604        K key, Iterable<? extends V> values) {
605      throw new UnsupportedOperationException();
606    }
607
608    @Override public Collection<V> values() {
609      Collection<V> result = values;
610      if (result == null) {
611        values = result = Collections.unmodifiableCollection(delegate.values());
612      }
613      return result;
614    }
615
616    private static final long serialVersionUID = 0;
617  }
618
619  private static class UnmodifiableAsMapValues<V>
620      extends ForwardingCollection<Collection<V>> {
621    final Collection<Collection<V>> delegate;
622    UnmodifiableAsMapValues(Collection<Collection<V>> delegate) {
623      this.delegate = Collections.unmodifiableCollection(delegate);
624    }
625    @Override protected Collection<Collection<V>> delegate() {
626      return delegate;
627    }
628    @Override public Iterator<Collection<V>> iterator() {
629      final Iterator<Collection<V>> iterator = delegate.iterator();
630      return new UnmodifiableIterator<Collection<V>>() {
631        @Override
632        public boolean hasNext() {
633          return iterator.hasNext();
634        }
635        @Override
636        public Collection<V> next() {
637          return unmodifiableValueCollection(iterator.next());
638        }
639      };
640    }
641    @Override public Object[] toArray() {
642      return standardToArray();
643    }
644    @Override public <T> T[] toArray(T[] array) {
645      return standardToArray(array);
646    }
647    @Override public boolean contains(Object o) {
648      return standardContains(o);
649    }
650    @Override public boolean containsAll(Collection<?> c) {
651      return standardContainsAll(c);
652    }
653  }
654
655  private static class UnmodifiableListMultimap<K, V>
656      extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
657    UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
658      super(delegate);
659    }
660    @Override public ListMultimap<K, V> delegate() {
661      return (ListMultimap<K, V>) super.delegate();
662    }
663    @Override public List<V> get(K key) {
664      return Collections.unmodifiableList(delegate().get(key));
665    }
666    @Override public List<V> removeAll(Object key) {
667      throw new UnsupportedOperationException();
668    }
669    @Override public List<V> replaceValues(
670        K key, Iterable<? extends V> values) {
671      throw new UnsupportedOperationException();
672    }
673    private static final long serialVersionUID = 0;
674  }
675
676  private static class UnmodifiableSetMultimap<K, V>
677      extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
678    UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
679      super(delegate);
680    }
681    @Override public SetMultimap<K, V> delegate() {
682      return (SetMultimap<K, V>) super.delegate();
683    }
684    @Override public Set<V> get(K key) {
685      /*
686       * Note that this doesn't return a SortedSet when delegate is a
687       * SortedSetMultiset, unlike (SortedSet<V>) super.get().
688       */
689      return Collections.unmodifiableSet(delegate().get(key));
690    }
691    @Override public Set<Map.Entry<K, V>> entries() {
692      return Maps.unmodifiableEntrySet(delegate().entries());
693    }
694    @Override public Set<V> removeAll(Object key) {
695      throw new UnsupportedOperationException();
696    }
697    @Override public Set<V> replaceValues(
698        K key, Iterable<? extends V> values) {
699      throw new UnsupportedOperationException();
700    }
701    private static final long serialVersionUID = 0;
702  }
703
704  private static class UnmodifiableSortedSetMultimap<K, V>
705      extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
706    UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
707      super(delegate);
708    }
709    @Override public SortedSetMultimap<K, V> delegate() {
710      return (SortedSetMultimap<K, V>) super.delegate();
711    }
712    @Override public SortedSet<V> get(K key) {
713      return Collections.unmodifiableSortedSet(delegate().get(key));
714    }
715    @Override public SortedSet<V> removeAll(Object key) {
716      throw new UnsupportedOperationException();
717    }
718    @Override public SortedSet<V> replaceValues(
719        K key, Iterable<? extends V> values) {
720      throw new UnsupportedOperationException();
721    }
722    @Override
723    public Comparator<? super V> valueComparator() {
724      return delegate().valueComparator();
725    }
726    private static final long serialVersionUID = 0;
727  }
728
729  /**
730   * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the
731   * specified multimap.
732   *
733   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
734   *
735   * <p>The returned multimap will be serializable if the specified multimap is
736   * serializable.
737   *
738   * @param multimap the multimap to be wrapped
739   * @return a synchronized view of the specified multimap
740   */
741  public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
742      SetMultimap<K, V> multimap) {
743    return Synchronized.setMultimap(multimap, null);
744  }
745
746  /**
747   * Returns an unmodifiable view of the specified {@code SetMultimap}. Query
748   * operations on the returned multimap "read through" to the specified
749   * multimap, and attempts to modify the returned multimap, either directly or
750   * through the multimap's views, result in an
751   * {@code UnsupportedOperationException}.
752   *
753   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
754   * {@link Multimap#replaceValues} methods return collections that are
755   * modifiable.
756   *
757   * <p>The returned multimap will be serializable if the specified multimap is
758   * serializable.
759   *
760   * @param delegate the multimap for which an unmodifiable view is to be
761   *     returned
762   * @return an unmodifiable view of the specified multimap
763   */
764  public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
765      SetMultimap<K, V> delegate) {
766    if (delegate instanceof UnmodifiableSetMultimap ||
767        delegate instanceof ImmutableSetMultimap) {
768      return delegate;
769    }
770    return new UnmodifiableSetMultimap<K, V>(delegate);
771  }
772
773  /**
774   * Simply returns its argument.
775   *
776   * @deprecated no need to use this
777   * @since 10.0
778   */
779  @Deprecated public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
780      ImmutableSetMultimap<K, V> delegate) {
781    return checkNotNull(delegate);
782  }
783
784  /**
785   * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by
786   * the specified multimap.
787   *
788   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
789   *
790   * <p>The returned multimap will be serializable if the specified multimap is
791   * serializable.
792   *
793   * @param multimap the multimap to be wrapped
794   * @return a synchronized view of the specified multimap
795   */
796  public static <K, V> SortedSetMultimap<K, V>
797      synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
798    return Synchronized.sortedSetMultimap(multimap, null);
799  }
800
801  /**
802   * Returns an unmodifiable view of the specified {@code SortedSetMultimap}.
803   * Query operations on the returned multimap "read through" to the specified
804   * multimap, and attempts to modify the returned multimap, either directly or
805   * through the multimap's views, result in an
806   * {@code UnsupportedOperationException}.
807   *
808   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
809   * {@link Multimap#replaceValues} methods return collections that are
810   * modifiable.
811   *
812   * <p>The returned multimap will be serializable if the specified multimap is
813   * serializable.
814   *
815   * @param delegate the multimap for which an unmodifiable view is to be
816   *     returned
817   * @return an unmodifiable view of the specified multimap
818   */
819  public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
820      SortedSetMultimap<K, V> delegate) {
821    if (delegate instanceof UnmodifiableSortedSetMultimap) {
822      return delegate;
823    }
824    return new UnmodifiableSortedSetMultimap<K, V>(delegate);
825  }
826
827  /**
828   * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the
829   * specified multimap.
830   *
831   * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
832   *
833   * @param multimap the multimap to be wrapped
834   * @return a synchronized view of the specified multimap
835   */
836  public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
837      ListMultimap<K, V> multimap) {
838    return Synchronized.listMultimap(multimap, null);
839  }
840
841  /**
842   * Returns an unmodifiable view of the specified {@code ListMultimap}. Query
843   * operations on the returned multimap "read through" to the specified
844   * multimap, and attempts to modify the returned multimap, either directly or
845   * through the multimap's views, result in an
846   * {@code UnsupportedOperationException}.
847   *
848   * <p>Note that the generated multimap's {@link Multimap#removeAll} and
849   * {@link Multimap#replaceValues} methods return collections that are
850   * modifiable.
851   *
852   * <p>The returned multimap will be serializable if the specified multimap is
853   * serializable.
854   *
855   * @param delegate the multimap for which an unmodifiable view is to be
856   *     returned
857   * @return an unmodifiable view of the specified multimap
858   */
859  public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
860      ListMultimap<K, V> delegate) {
861    if (delegate instanceof UnmodifiableListMultimap ||
862        delegate instanceof ImmutableListMultimap) {
863      return delegate;
864    }
865    return new UnmodifiableListMultimap<K, V>(delegate);
866  }
867
868  /**
869   * Simply returns its argument.
870   *
871   * @deprecated no need to use this
872   * @since 10.0
873   */
874  @Deprecated public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
875      ImmutableListMultimap<K, V> delegate) {
876    return checkNotNull(delegate);
877  }
878
879  /**
880   * Returns an unmodifiable view of the specified collection, preserving the
881   * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and
882   * {@code Collection}, in that order of preference.
883   *
884   * @param collection the collection for which to return an unmodifiable view
885   * @return an unmodifiable view of the collection
886   */
887  private static <V> Collection<V> unmodifiableValueCollection(
888      Collection<V> collection) {
889    if (collection instanceof SortedSet) {
890      return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
891    } else if (collection instanceof Set) {
892      return Collections.unmodifiableSet((Set<V>) collection);
893    } else if (collection instanceof List) {
894      return Collections.unmodifiableList((List<V>) collection);
895    }
896    return Collections.unmodifiableCollection(collection);
897  }
898
899  /**
900   * Returns an unmodifiable view of the specified multimap {@code asMap} entry.
901   * The {@link Entry#setValue} operation throws an {@link
902   * UnsupportedOperationException}, and the collection returned by {@code
903   * getValue} is also an unmodifiable (type-preserving) view. This also has the
904   * side-effect of redefining equals to comply with the Map.Entry contract, and
905   * to avoid a possible nefarious implementation of equals.
906   *
907   * @param entry the entry for which to return an unmodifiable view
908   * @return an unmodifiable view of the entry
909   */
910  private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry(
911      final Map.Entry<K, Collection<V>> entry) {
912    checkNotNull(entry);
913    return new AbstractMapEntry<K, Collection<V>>() {
914      @Override public K getKey() {
915        return entry.getKey();
916      }
917
918      @Override public Collection<V> getValue() {
919        return unmodifiableValueCollection(entry.getValue());
920      }
921    };
922  }
923
924  /**
925   * Returns an unmodifiable view of the specified collection of entries. The
926   * {@link Entry#setValue} operation throws an {@link
927   * UnsupportedOperationException}. If the specified collection is a {@code
928   * Set}, the returned collection is also a {@code Set}.
929   *
930   * @param entries the entries for which to return an unmodifiable view
931   * @return an unmodifiable view of the entries
932   */
933  private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
934      Collection<Entry<K, V>> entries) {
935    if (entries instanceof Set) {
936      return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
937    }
938    return new Maps.UnmodifiableEntries<K, V>(
939        Collections.unmodifiableCollection(entries));
940  }
941
942  /**
943   * Returns an unmodifiable view of the specified set of {@code asMap} entries.
944   * The {@link Entry#setValue} operation throws an {@link
945   * UnsupportedOperationException}, as do any operations that attempt to modify
946   * the returned collection.
947   *
948   * @param asMapEntries the {@code asMap} entries for which to return an
949   *     unmodifiable view
950   * @return an unmodifiable view of the collection entries
951   */
952  private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries(
953      Set<Entry<K, Collection<V>>> asMapEntries) {
954    return new UnmodifiableAsMapEntries<K, V>(
955        Collections.unmodifiableSet(asMapEntries));
956  }
957
958  /** @see Multimaps#unmodifiableAsMapEntries */
959  static class UnmodifiableAsMapEntries<K, V>
960      extends ForwardingSet<Entry<K, Collection<V>>> {
961    private final Set<Entry<K, Collection<V>>> delegate;
962    UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) {
963      this.delegate = delegate;
964    }
965
966    @Override protected Set<Entry<K, Collection<V>>> delegate() {
967      return delegate;
968    }
969
970    @Override public Iterator<Entry<K, Collection<V>>> iterator() {
971      final Iterator<Entry<K, Collection<V>>> iterator = delegate.iterator();
972      return new ForwardingIterator<Entry<K, Collection<V>>>() {
973        @Override protected Iterator<Entry<K, Collection<V>>> delegate() {
974          return iterator;
975        }
976        @Override public Entry<K, Collection<V>> next() {
977          return unmodifiableAsMapEntry(iterator.next());
978        }
979      };
980    }
981
982    @Override public Object[] toArray() {
983      return standardToArray();
984    }
985
986    @Override public <T> T[] toArray(T[] array) {
987      return standardToArray(array);
988    }
989
990    @Override public boolean contains(Object o) {
991      return Maps.containsEntryImpl(delegate(), o);
992    }
993
994    @Override public boolean containsAll(Collection<?> c) {
995      return standardContainsAll(c);
996    }
997
998    @Override public boolean equals(@Nullable Object object) {
999      return standardEquals(object);
1000    }
1001  }
1002
1003  /**
1004   * Returns a multimap view of the specified map. The multimap is backed by the
1005   * map, so changes to the map are reflected in the multimap, and vice versa.
1006   * If the map is modified while an iteration over one of the multimap's
1007   * collection views is in progress (except through the iterator's own {@code
1008   * remove} operation, or through the {@code setValue} operation on a map entry
1009   * returned by the iterator), the results of the iteration are undefined.
1010   *
1011   * <p>The multimap supports mapping removal, which removes the corresponding
1012   * mapping from the map. It does not support any operations which might add
1013   * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}.
1014   *
1015   * <p>The returned multimap will be serializable if the specified map is
1016   * serializable.
1017   *
1018   * @param map the backing map for the returned multimap view
1019   */
1020  public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
1021    return new MapMultimap<K, V>(map);
1022  }
1023
1024  /** @see Multimaps#forMap */
1025  private static class MapMultimap<K, V>
1026      implements SetMultimap<K, V>, Serializable {
1027    final Map<K, V> map;
1028    transient Map<K, Collection<V>> asMap;
1029
1030    MapMultimap(Map<K, V> map) {
1031      this.map = checkNotNull(map);
1032    }
1033
1034    @Override
1035    public int size() {
1036      return map.size();
1037    }
1038
1039    @Override
1040    public boolean isEmpty() {
1041      return map.isEmpty();
1042    }
1043
1044    @Override
1045    public boolean containsKey(Object key) {
1046      return map.containsKey(key);
1047    }
1048
1049    @Override
1050    public boolean containsValue(Object value) {
1051      return map.containsValue(value);
1052    }
1053
1054    @Override
1055    public boolean containsEntry(Object key, Object value) {
1056      return map.entrySet().contains(Maps.immutableEntry(key, value));
1057    }
1058
1059    @Override
1060    public Set<V> get(final K key) {
1061      return new Sets.ImprovedAbstractSet<V>() {
1062        @Override public Iterator<V> iterator() {
1063          return new Iterator<V>() {
1064            int i;
1065
1066            @Override
1067            public boolean hasNext() {
1068              return (i == 0) && map.containsKey(key);
1069            }
1070
1071            @Override
1072            public V next() {
1073              if (!hasNext()) {
1074                throw new NoSuchElementException();
1075              }
1076              i++;
1077              return map.get(key);
1078            }
1079
1080            @Override
1081            public void remove() {
1082              checkState(i == 1);
1083              i = -1;
1084              map.remove(key);
1085            }
1086          };
1087        }
1088
1089        @Override public int size() {
1090          return map.containsKey(key) ? 1 : 0;
1091        }
1092      };
1093    }
1094
1095    @Override
1096    public boolean put(K key, V value) {
1097      throw new UnsupportedOperationException();
1098    }
1099
1100    @Override
1101    public boolean putAll(K key, Iterable<? extends V> values) {
1102      throw new UnsupportedOperationException();
1103    }
1104
1105    @Override
1106    public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1107      throw new UnsupportedOperationException();
1108    }
1109
1110    @Override
1111    public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1112      throw new UnsupportedOperationException();
1113    }
1114
1115    @Override
1116    public boolean remove(Object key, Object value) {
1117      return map.entrySet().remove(Maps.immutableEntry(key, value));
1118    }
1119
1120    @Override
1121    public Set<V> removeAll(Object key) {
1122      Set<V> values = new HashSet<V>(2);
1123      if (!map.containsKey(key)) {
1124        return values;
1125      }
1126      values.add(map.remove(key));
1127      return values;
1128    }
1129
1130    @Override
1131    public void clear() {
1132      map.clear();
1133    }
1134
1135    @Override
1136    public Set<K> keySet() {
1137      return map.keySet();
1138    }
1139
1140    @Override
1141    public Multiset<K> keys() {
1142      return Multisets.forSet(map.keySet());
1143    }
1144
1145    @Override
1146    public Collection<V> values() {
1147      return map.values();
1148    }
1149
1150    @Override
1151    public Set<Entry<K, V>> entries() {
1152      return map.entrySet();
1153    }
1154
1155    @Override
1156    public Map<K, Collection<V>> asMap() {
1157      Map<K, Collection<V>> result = asMap;
1158      if (result == null) {
1159        asMap = result = new AsMap();
1160      }
1161      return result;
1162    }
1163
1164    @Override public boolean equals(@Nullable Object object) {
1165      if (object == this) {
1166        return true;
1167      }
1168      if (object instanceof Multimap) {
1169        Multimap<?, ?> that = (Multimap<?, ?>) object;
1170        return this.size() == that.size() && asMap().equals(that.asMap());
1171      }
1172      return false;
1173    }
1174
1175    @Override public int hashCode() {
1176      return map.hashCode();
1177    }
1178
1179    private static final MapJoiner JOINER
1180        = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null");
1181
1182    @Override public String toString() {
1183      if (map.isEmpty()) {
1184        return "{}";
1185      }
1186      StringBuilder builder
1187          = Collections2.newStringBuilderForCollection(map.size()).append('{');
1188      JOINER.appendTo(builder, map);
1189      return builder.append("]}").toString();
1190    }
1191
1192    /** @see MapMultimap#asMap */
1193    class AsMapEntries extends Sets.ImprovedAbstractSet<Entry<K, Collection<V>>> {
1194      @Override public int size() {
1195        return map.size();
1196      }
1197
1198      @Override public Iterator<Entry<K, Collection<V>>> iterator() {
1199        return new TransformedIterator<K, Entry<K, Collection<V>>>(map.keySet().iterator()) {
1200          @Override
1201          Entry<K, Collection<V>> transform(final K key) {
1202            return new AbstractMapEntry<K, Collection<V>>() {
1203              @Override
1204              public K getKey() {
1205                return key;
1206              }
1207
1208              @Override
1209              public Collection<V> getValue() {
1210                return get(key);
1211              }
1212            };
1213          }
1214        };
1215      }
1216
1217      @Override public boolean contains(Object o) {
1218        if (!(o instanceof Entry)) {
1219          return false;
1220        }
1221        Entry<?, ?> entry = (Entry<?, ?>) o;
1222        if (!(entry.getValue() instanceof Set)) {
1223          return false;
1224        }
1225        Set<?> set = (Set<?>) entry.getValue();
1226        return (set.size() == 1)
1227            && containsEntry(entry.getKey(), set.iterator().next());
1228      }
1229
1230      @Override public boolean remove(Object o) {
1231        if (!(o instanceof Entry)) {
1232          return false;
1233        }
1234        Entry<?, ?> entry = (Entry<?, ?>) o;
1235        if (!(entry.getValue() instanceof Set)) {
1236          return false;
1237        }
1238        Set<?> set = (Set<?>) entry.getValue();
1239        return (set.size() == 1)
1240            && map.entrySet().remove(
1241                Maps.immutableEntry(entry.getKey(), set.iterator().next()));
1242      }
1243    }
1244
1245    /** @see MapMultimap#asMap */
1246    class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> {
1247      @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
1248        return new AsMapEntries();
1249      }
1250
1251      // The following methods are included for performance.
1252
1253      @Override public boolean containsKey(Object key) {
1254        return map.containsKey(key);
1255      }
1256
1257      @SuppressWarnings("unchecked")
1258      @Override public Collection<V> get(Object key) {
1259        Collection<V> collection = MapMultimap.this.get((K) key);
1260        return collection.isEmpty() ? null : collection;
1261      }
1262
1263      @Override public Collection<V> remove(Object key) {
1264        Collection<V> collection = removeAll(key);
1265        return collection.isEmpty() ? null : collection;
1266      }
1267    }
1268    private static final long serialVersionUID = 7845222491160860175L;
1269  }
1270
1271  /**
1272   * Returns a view of a multimap where each value is transformed by a function.
1273   * All other properties of the multimap, such as iteration order, are left
1274   * intact. For example, the code: <pre>   {@code
1275   *
1276   * Multimap<String, Integer> multimap =
1277   *     ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
1278   * Function<Integer, String> square = new Function<Integer, String>() {
1279   *     public String apply(Integer in) {
1280   *       return Integer.toString(in * in);
1281   *     }
1282   * };
1283   * Multimap<String, String> transformed =
1284   *     Multimaps.transformValues(multimap, square);
1285   *   System.out.println(transformed);}</pre>
1286   *
1287   * ... prints {@code {a=[4, 16], b=[9, 9], c=[6]}}.
1288   *
1289   * <p>Changes in the underlying multimap are reflected in this view.
1290   * Conversely, this view supports removal operations, and these are reflected
1291   * in the underlying multimap.
1292   *
1293   * <p>It's acceptable for the underlying multimap to contain null keys, and
1294   * even null values provided that the function is capable of accepting null
1295   * input.  The transformed multimap might contain null values, if the function
1296   * sometimes gives a null result.
1297   *
1298   * <p>The returned multimap is not thread-safe or serializable, even if the
1299   * underlying multimap is.  The {@code equals} and {@code hashCode} methods
1300   * of the returned multimap are meaningless, since there is not a definition
1301   * of {@code equals} or {@code hashCode} for general collections, and
1302   * {@code get()} will return a general {@code Collection} as opposed to a
1303   * {@code List} or a {@code Set}.
1304   *
1305   * <p>The function is applied lazily, invoked when needed. This is necessary
1306   * for the returned multimap to be a view, but it means that the function will
1307   * be applied many times for bulk operations like
1308   * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1309   * perform well, {@code function} should be fast. To avoid lazy evaluation
1310   * when the returned multimap doesn't need to be a view, copy the returned
1311   * multimap into a new multimap of your choosing.
1312   *
1313   * @since 7.0
1314   */
1315  public static <K, V1, V2> Multimap<K, V2> transformValues(
1316      Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1317    checkNotNull(function);
1318    EntryTransformer<K, V1, V2> transformer =
1319        new EntryTransformer<K, V1, V2>() {
1320          @Override
1321          public V2 transformEntry(K key, V1 value) {
1322            return function.apply(value);
1323          }
1324        };
1325    return transformEntries(fromMultimap, transformer);
1326  }
1327
1328  /**
1329   * Returns a view of a multimap whose values are derived from the original
1330   * multimap's entries. In contrast to {@link #transformValues}, this method's
1331   * entry-transformation logic may depend on the key as well as the value.
1332   *
1333   * <p>All other properties of the transformed multimap, such as iteration
1334   * order, are left intact. For example, the code: <pre>   {@code
1335   *
1336   *   SetMultimap<String, Integer> multimap =
1337   *       ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
1338   *   EntryTransformer<String, Integer, String> transformer =
1339   *       new EntryTransformer<String, Integer, String>() {
1340   *         public String transformEntry(String key, Integer value) {
1341   *            return (value >= 0) ? key : "no" + key;
1342   *         }
1343   *       };
1344   *   Multimap<String, String> transformed =
1345   *       Multimaps.transformEntries(multimap, transformer);
1346   *   System.out.println(transformed);}</pre>
1347   *
1348   * ... prints {@code {a=[a, a], b=[nob]}}.
1349   *
1350   * <p>Changes in the underlying multimap are reflected in this view.
1351   * Conversely, this view supports removal operations, and these are reflected
1352   * in the underlying multimap.
1353   *
1354   * <p>It's acceptable for the underlying multimap to contain null keys and
1355   * null values provided that the transformer is capable of accepting null
1356   * inputs. The transformed multimap might contain null values if the
1357   * transformer sometimes gives a null result.
1358   *
1359   * <p>The returned multimap is not thread-safe or serializable, even if the
1360   * underlying multimap is.  The {@code equals} and {@code hashCode} methods
1361   * of the returned multimap are meaningless, since there is not a definition
1362   * of {@code equals} or {@code hashCode} for general collections, and
1363   * {@code get()} will return a general {@code Collection} as opposed to a
1364   * {@code List} or a {@code Set}.
1365   *
1366   * <p>The transformer is applied lazily, invoked when needed. This is
1367   * necessary for the returned multimap to be a view, but it means that the
1368   * transformer will be applied many times for bulk operations like {@link
1369   * Multimap#containsValue} and {@link Object#toString}. For this to perform
1370   * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1371   * returned multimap doesn't need to be a view, copy the returned multimap
1372   * into a new multimap of your choosing.
1373   *
1374   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1375   * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1376   * that {@code k2} is also of type {@code K}. Using an {@code
1377   * EntryTransformer} key type for which this may not hold, such as {@code
1378   * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1379   * the transformed multimap.
1380   *
1381   * @since 7.0
1382   */
1383  public static <K, V1, V2> Multimap<K, V2> transformEntries(
1384      Multimap<K, V1> fromMap,
1385      EntryTransformer<? super K, ? super V1, V2> transformer) {
1386    return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer);
1387  }
1388
1389  private static class TransformedEntriesMultimap<K, V1, V2>
1390      implements Multimap<K, V2> {
1391    final Multimap<K, V1> fromMultimap;
1392    final EntryTransformer<? super K, ? super V1, V2> transformer;
1393
1394    TransformedEntriesMultimap(Multimap<K, V1> fromMultimap,
1395        final EntryTransformer<? super K, ? super V1, V2> transformer) {
1396      this.fromMultimap = checkNotNull(fromMultimap);
1397      this.transformer = checkNotNull(transformer);
1398    }
1399
1400    Collection<V2> transform(final K key, Collection<V1> values) {
1401      return Collections2.transform(values, new Function<V1, V2>() {
1402        @Override public V2 apply(V1 value) {
1403          return transformer.transformEntry(key, value);
1404        }
1405      });
1406    }
1407
1408    private transient Map<K, Collection<V2>> asMap;
1409
1410    @Override public Map<K, Collection<V2>> asMap() {
1411      if (asMap == null) {
1412        Map<K, Collection<V2>> aM = Maps.transformEntries(fromMultimap.asMap(),
1413            new EntryTransformer<K, Collection<V1>, Collection<V2>>() {
1414
1415              @Override public Collection<V2> transformEntry(
1416                  K key, Collection<V1> value) {
1417                return transform(key, value);
1418              }
1419            });
1420        asMap = aM;
1421        return aM;
1422      }
1423      return asMap;
1424    }
1425
1426    @Override public void clear() {
1427      fromMultimap.clear();
1428    }
1429
1430    @SuppressWarnings("unchecked")
1431    @Override public boolean containsEntry(Object key, Object value) {
1432      Collection<V2> values = get((K) key);
1433      return values.contains(value);
1434    }
1435
1436    @Override public boolean containsKey(Object key) {
1437      return fromMultimap.containsKey(key);
1438    }
1439
1440    @Override public boolean containsValue(Object value) {
1441      return values().contains(value);
1442    }
1443
1444    private transient Collection<Entry<K, V2>> entries;
1445
1446    @Override public Collection<Entry<K, V2>> entries() {
1447      if (entries == null) {
1448        Collection<Entry<K, V2>> es = new TransformedEntries(transformer);
1449        entries = es;
1450        return es;
1451      }
1452      return entries;
1453    }
1454
1455    private class TransformedEntries
1456        extends TransformedCollection<Entry<K, V1>, Entry<K, V2>> {
1457
1458      TransformedEntries(
1459          final EntryTransformer<? super K, ? super V1, V2> transformer) {
1460        super(fromMultimap.entries(),
1461            new Function<Entry<K, V1>, Entry<K, V2>>() {
1462              @Override public Entry<K, V2> apply(final Entry<K, V1> entry) {
1463                return new AbstractMapEntry<K, V2>() {
1464
1465                  @Override public K getKey() {
1466                    return entry.getKey();
1467                  }
1468
1469                  @Override public V2 getValue() {
1470                    return transformer.transformEntry(
1471                        entry.getKey(), entry.getValue());
1472                  }
1473                };
1474              }
1475            });
1476      }
1477
1478      @Override public boolean contains(Object o) {
1479        if (o instanceof Entry) {
1480          Entry<?, ?> entry = (Entry<?, ?>) o;
1481          return containsEntry(entry.getKey(), entry.getValue());
1482        }
1483        return false;
1484      }
1485
1486      @SuppressWarnings("unchecked")
1487      @Override public boolean remove(Object o) {
1488        if (o instanceof Entry) {
1489          Entry<?, ?> entry = (Entry<?, ?>) o;
1490          Collection<V2> values = get((K) entry.getKey());
1491          return values.remove(entry.getValue());
1492        }
1493        return false;
1494      }
1495
1496    }
1497
1498    @Override public Collection<V2> get(final K key) {
1499      return transform(key, fromMultimap.get(key));
1500    }
1501
1502    @Override public boolean isEmpty() {
1503      return fromMultimap.isEmpty();
1504    }
1505
1506    @Override public Set<K> keySet() {
1507      return fromMultimap.keySet();
1508    }
1509
1510    @Override public Multiset<K> keys() {
1511      return fromMultimap.keys();
1512    }
1513
1514    @Override public boolean put(K key, V2 value) {
1515      throw new UnsupportedOperationException();
1516    }
1517
1518    @Override public boolean putAll(K key, Iterable<? extends V2> values) {
1519      throw new UnsupportedOperationException();
1520    }
1521
1522    @Override public boolean putAll(
1523        Multimap<? extends K, ? extends V2> multimap) {
1524      throw new UnsupportedOperationException();
1525    }
1526
1527    @SuppressWarnings("unchecked")
1528    @Override public boolean remove(Object key, Object value) {
1529      return get((K) key).remove(value);
1530    }
1531
1532    @SuppressWarnings("unchecked")
1533    @Override public Collection<V2> removeAll(Object key) {
1534      return transform((K) key, fromMultimap.removeAll(key));
1535    }
1536
1537    @Override public Collection<V2> replaceValues(
1538        K key, Iterable<? extends V2> values) {
1539      throw new UnsupportedOperationException();
1540    }
1541
1542    @Override public int size() {
1543      return fromMultimap.size();
1544    }
1545
1546    private transient Collection<V2> values;
1547
1548    @Override public Collection<V2> values() {
1549      if (values == null) {
1550        Collection<V2> vs = Collections2.transform(
1551            fromMultimap.entries(), new Function<Entry<K, V1>, V2>() {
1552
1553              @Override public V2 apply(Entry<K, V1> entry) {
1554                return transformer.transformEntry(
1555                    entry.getKey(), entry.getValue());
1556              }
1557            });
1558        values = vs;
1559        return vs;
1560      }
1561      return values;
1562    }
1563
1564    @Override public boolean equals(Object obj) {
1565      if (obj instanceof Multimap) {
1566        Multimap<?, ?> other = (Multimap<?, ?>) obj;
1567        return asMap().equals(other.asMap());
1568      }
1569      return false;
1570    }
1571
1572    @Override public int hashCode() {
1573      return asMap().hashCode();
1574    }
1575
1576    @Override public String toString() {
1577      return asMap().toString();
1578    }
1579  }
1580
1581  /**
1582   * Returns a view of a {@code ListMultimap} where each value is transformed by
1583   * a function. All other properties of the multimap, such as iteration order,
1584   * are left intact. For example, the code: <pre>   {@code
1585   *
1586   *   ListMultimap<String, Integer> multimap
1587   *        = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
1588   *   Function<Integer, Double> sqrt =
1589   *       new Function<Integer, Double>() {
1590   *         public Double apply(Integer in) {
1591   *           return Math.sqrt((int) in);
1592   *         }
1593   *       };
1594   *   ListMultimap<String, Double> transformed = Multimaps.transformValues(map,
1595   *       sqrt);
1596   *   System.out.println(transformed);}</pre>
1597   *
1598   * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}.
1599   *
1600   * <p>Changes in the underlying multimap are reflected in this view.
1601   * Conversely, this view supports removal operations, and these are reflected
1602   * in the underlying multimap.
1603   *
1604   * <p>It's acceptable for the underlying multimap to contain null keys, and
1605   * even null values provided that the function is capable of accepting null
1606   * input.  The transformed multimap might contain null values, if the function
1607   * sometimes gives a null result.
1608   *
1609   * <p>The returned multimap is not thread-safe or serializable, even if the
1610   * underlying multimap is.
1611   *
1612   * <p>The function is applied lazily, invoked when needed. This is necessary
1613   * for the returned multimap to be a view, but it means that the function will
1614   * be applied many times for bulk operations like
1615   * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1616   * perform well, {@code function} should be fast. To avoid lazy evaluation
1617   * when the returned multimap doesn't need to be a view, copy the returned
1618   * multimap into a new multimap of your choosing.
1619   *
1620   * @since 7.0
1621   */
1622  public static <K, V1, V2> ListMultimap<K, V2> transformValues(
1623      ListMultimap<K, V1> fromMultimap,
1624      final Function<? super V1, V2> function) {
1625    checkNotNull(function);
1626    EntryTransformer<K, V1, V2> transformer =
1627        new EntryTransformer<K, V1, V2>() {
1628          @Override
1629          public V2 transformEntry(K key, V1 value) {
1630            return function.apply(value);
1631          }
1632        };
1633    return transformEntries(fromMultimap, transformer);
1634  }
1635
1636  /**
1637   * Returns a view of a {@code ListMultimap} whose values are derived from the
1638   * original multimap's entries. In contrast to
1639   * {@link #transformValues(ListMultimap, Function)}, this method's
1640   * entry-transformation logic may depend on the key as well as the value.
1641   *
1642   * <p>All other properties of the transformed multimap, such as iteration
1643   * order, are left intact. For example, the code: <pre>   {@code
1644   *
1645   *   Multimap<String, Integer> multimap =
1646   *       ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
1647   *   EntryTransformer<String, Integer, String> transformer =
1648   *       new EntryTransformer<String, Integer, String>() {
1649   *         public String transformEntry(String key, Integer value) {
1650   *           return key + value;
1651   *         }
1652   *       };
1653   *   Multimap<String, String> transformed =
1654   *       Multimaps.transformEntries(multimap, transformer);
1655   *   System.out.println(transformed);}</pre>
1656   *
1657   * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}.
1658   *
1659   * <p>Changes in the underlying multimap are reflected in this view.
1660   * Conversely, this view supports removal operations, and these are reflected
1661   * in the underlying multimap.
1662   *
1663   * <p>It's acceptable for the underlying multimap to contain null keys and
1664   * null values provided that the transformer is capable of accepting null
1665   * inputs. The transformed multimap might contain null values if the
1666   * transformer sometimes gives a null result.
1667   *
1668   * <p>The returned multimap is not thread-safe or serializable, even if the
1669   * underlying multimap is.
1670   *
1671   * <p>The transformer is applied lazily, invoked when needed. This is
1672   * necessary for the returned multimap to be a view, but it means that the
1673   * transformer will be applied many times for bulk operations like {@link
1674   * Multimap#containsValue} and {@link Object#toString}. For this to perform
1675   * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1676   * returned multimap doesn't need to be a view, copy the returned multimap
1677   * into a new multimap of your choosing.
1678   *
1679   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1680   * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1681   * that {@code k2} is also of type {@code K}. Using an {@code
1682   * EntryTransformer} key type for which this may not hold, such as {@code
1683   * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1684   * the transformed multimap.
1685   *
1686   * @since 7.0
1687   */
1688  public static <K, V1, V2> ListMultimap<K, V2> transformEntries(
1689      ListMultimap<K, V1> fromMap,
1690      EntryTransformer<? super K, ? super V1, V2> transformer) {
1691    return new TransformedEntriesListMultimap<K, V1, V2>(fromMap, transformer);
1692  }
1693
1694  private static final class TransformedEntriesListMultimap<K, V1, V2>
1695      extends TransformedEntriesMultimap<K, V1, V2>
1696      implements ListMultimap<K, V2> {
1697
1698    TransformedEntriesListMultimap(ListMultimap<K, V1> fromMultimap,
1699        EntryTransformer<? super K, ? super V1, V2> transformer) {
1700      super(fromMultimap, transformer);
1701    }
1702
1703    @Override List<V2> transform(final K key, Collection<V1> values) {
1704      return Lists.transform((List<V1>) values, new Function<V1, V2>() {
1705        @Override public V2 apply(V1 value) {
1706          return transformer.transformEntry(key, value);
1707        }
1708      });
1709    }
1710
1711    @Override public List<V2> get(K key) {
1712      return transform(key, fromMultimap.get(key));
1713    }
1714
1715    @SuppressWarnings("unchecked")
1716    @Override public List<V2> removeAll(Object key) {
1717      return transform((K) key, fromMultimap.removeAll(key));
1718    }
1719
1720    @Override public List<V2> replaceValues(
1721        K key, Iterable<? extends V2> values) {
1722      throw new UnsupportedOperationException();
1723    }
1724  }
1725
1726  /**
1727   * Creates an index {@code ImmutableListMultimap} that contains the results of
1728   * applying a specified function to each item in an {@code Iterable} of
1729   * values. Each value will be stored as a value in the resulting multimap,
1730   * yielding a multimap with the same size as the input iterable. The key used
1731   * to store that value in the multimap will be the result of calling the
1732   * function on that value. The resulting multimap is created as an immutable
1733   * snapshot. In the returned multimap, keys appear in the order they are first
1734   * encountered, and the values corresponding to each key appear in the same
1735   * order as they are encountered.
1736   *
1737   * <p>For example, <pre>   {@code
1738   *
1739   *   List<String> badGuys =
1740   *       Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1741   *   Function<String, Integer> stringLengthFunction = ...;
1742   *   Multimap<Integer, String> index =
1743   *       Multimaps.index(badGuys, stringLengthFunction);
1744   *   System.out.println(index);}</pre>
1745   *
1746   * prints <pre>   {@code
1747   *
1748   *   {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
1749   *
1750   * The returned multimap is serializable if its keys and values are all
1751   * serializable.
1752   *
1753   * @param values the values to use when constructing the {@code
1754   *     ImmutableListMultimap}
1755   * @param keyFunction the function used to produce the key for each value
1756   * @return {@code ImmutableListMultimap} mapping the result of evaluating the
1757   *     function {@code keyFunction} on each value in the input collection to
1758   *     that value
1759   * @throws NullPointerException if any of the following cases is true:
1760   *     <ul>
1761   *     <li>{@code values} is null
1762   *     <li>{@code keyFunction} is null
1763   *     <li>An element in {@code values} is null
1764   *     <li>{@code keyFunction} returns {@code null} for any element of {@code
1765   *         values}
1766   *     </ul>
1767   */
1768  public static <K, V> ImmutableListMultimap<K, V> index(
1769      Iterable<V> values, Function<? super V, K> keyFunction) {
1770    return index(values.iterator(), keyFunction);
1771  }
1772
1773  /**
1774   * Creates an index {@code ImmutableListMultimap} that contains the results of
1775   * applying a specified function to each item in an {@code Iterator} of
1776   * values. Each value will be stored as a value in the resulting multimap,
1777   * yielding a multimap with the same size as the input iterator. The key used
1778   * to store that value in the multimap will be the result of calling the
1779   * function on that value. The resulting multimap is created as an immutable
1780   * snapshot. In the returned multimap, keys appear in the order they are first
1781   * encountered, and the values corresponding to each key appear in the same
1782   * order as they are encountered.
1783   *
1784   * <p>For example, <pre>   {@code
1785   *
1786   *   List<String> badGuys =
1787   *       Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1788   *   Function<String, Integer> stringLengthFunction = ...;
1789   *   Multimap<Integer, String> index =
1790   *       Multimaps.index(badGuys.iterator(), stringLengthFunction);
1791   *   System.out.println(index);}</pre>
1792   *
1793   * prints <pre>   {@code
1794   *
1795   *   {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
1796   *
1797   * The returned multimap is serializable if its keys and values are all
1798   * serializable.
1799   *
1800   * @param values the values to use when constructing the {@code
1801   *     ImmutableListMultimap}
1802   * @param keyFunction the function used to produce the key for each value
1803   * @return {@code ImmutableListMultimap} mapping the result of evaluating the
1804   *     function {@code keyFunction} on each value in the input collection to
1805   *     that value
1806   * @throws NullPointerException if any of the following cases is true:
1807   *     <ul>
1808   *     <li>{@code values} is null
1809   *     <li>{@code keyFunction} is null
1810   *     <li>An element in {@code values} is null
1811   *     <li>{@code keyFunction} returns {@code null} for any element of {@code
1812   *         values}
1813   *     </ul>
1814   * @since 10.0
1815   */
1816  public static <K, V> ImmutableListMultimap<K, V> index(
1817      Iterator<V> values, Function<? super V, K> keyFunction) {
1818    checkNotNull(keyFunction);
1819    ImmutableListMultimap.Builder<K, V> builder
1820        = ImmutableListMultimap.builder();
1821    while (values.hasNext()) {
1822      V value = values.next();
1823      checkNotNull(value, values);
1824      builder.put(keyFunction.apply(value), value);
1825    }
1826    return builder.build();
1827  }
1828
1829  static abstract class Keys<K, V> extends AbstractMultiset<K> {
1830    abstract Multimap<K, V> multimap();
1831
1832    @Override Iterator<Multiset.Entry<K>> entryIterator() {
1833      return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>(
1834          multimap().asMap().entrySet().iterator()) {
1835        @Override
1836        Multiset.Entry<K> transform(
1837            final Map.Entry<K, Collection<V>> backingEntry) {
1838          return new Multisets.AbstractEntry<K>() {
1839            @Override
1840            public K getElement() {
1841              return backingEntry.getKey();
1842            }
1843
1844            @Override
1845            public int getCount() {
1846              return backingEntry.getValue().size();
1847            }
1848          };
1849        }
1850      };
1851    }
1852
1853    @Override int distinctElements() {
1854      return multimap().asMap().size();
1855    }
1856
1857    @Override Set<Multiset.Entry<K>> createEntrySet() {
1858      return new KeysEntrySet();
1859    }
1860
1861    class KeysEntrySet extends Multisets.EntrySet<K> {
1862      @Override Multiset<K> multiset() {
1863        return Keys.this;
1864      }
1865
1866      @Override public Iterator<Multiset.Entry<K>> iterator() {
1867        return entryIterator();
1868      }
1869
1870      @Override public int size() {
1871        return distinctElements();
1872      }
1873
1874      @Override public boolean isEmpty() {
1875        return multimap().isEmpty();
1876      }
1877
1878      @Override public boolean contains(@Nullable Object o) {
1879        if (o instanceof Multiset.Entry) {
1880          Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1881          Collection<V> collection = multimap().asMap().get(entry.getElement());
1882          return collection != null && collection.size() == entry.getCount();
1883        }
1884        return false;
1885      }
1886
1887      @Override public boolean remove(@Nullable Object o) {
1888        if (o instanceof Multiset.Entry) {
1889          Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1890          Collection<V> collection = multimap().asMap().get(entry.getElement());
1891          if (collection != null && collection.size() == entry.getCount()) {
1892            collection.clear();
1893            return true;
1894          }
1895        }
1896        return false;
1897      }
1898    }
1899
1900    @Override public boolean contains(@Nullable Object element) {
1901      return multimap().containsKey(element);
1902    }
1903
1904    @Override public Iterator<K> iterator() {
1905      return Maps.keyIterator(multimap().entries().iterator());
1906    }
1907
1908    @Override public int count(@Nullable Object element) {
1909      try {
1910        if (multimap().containsKey(element)) {
1911          Collection<V> values = multimap().asMap().get(element);
1912          return (values == null) ? 0 : values.size();
1913        }
1914        return 0;
1915      } catch (ClassCastException e) {
1916        return 0;
1917      } catch (NullPointerException e) {
1918        return 0;
1919      }
1920    }
1921
1922    @Override public int remove(@Nullable Object element, int occurrences) {
1923      checkArgument(occurrences >= 0);
1924      if (occurrences == 0) {
1925        return count(element);
1926      }
1927
1928      Collection<V> values;
1929      try {
1930        values = multimap().asMap().get(element);
1931      } catch (ClassCastException e) {
1932        return 0;
1933      } catch (NullPointerException e) {
1934        return 0;
1935      }
1936
1937      if (values == null) {
1938        return 0;
1939      }
1940
1941      int oldCount = values.size();
1942      if (occurrences >= oldCount) {
1943        values.clear();
1944      } else {
1945        Iterator<V> iterator = values.iterator();
1946        for (int i = 0; i < occurrences; i++) {
1947          iterator.next();
1948          iterator.remove();
1949        }
1950      }
1951      return oldCount;
1952    }
1953
1954    @Override public void clear() {
1955      multimap().clear();
1956    }
1957
1958    @Override public Set<K> elementSet() {
1959      return multimap().keySet();
1960    }
1961  }
1962
1963  static abstract class Values<K, V> extends AbstractCollection<V> {
1964    abstract Multimap<K, V> multimap();
1965
1966    @Override public Iterator<V> iterator() {
1967      return Maps.valueIterator(multimap().entries().iterator());
1968    }
1969
1970    @Override public int size() {
1971      return multimap().size();
1972    }
1973
1974    @Override public boolean contains(@Nullable Object o) {
1975      return multimap().containsValue(o);
1976    }
1977
1978    @Override public void clear() {
1979      multimap().clear();
1980    }
1981  }
1982
1983  /**
1984   * A skeleton implementation of {@link Multimap#entries()}.
1985   */
1986  static abstract class Entries<K, V> extends
1987      AbstractCollection<Map.Entry<K, V>> {
1988    abstract Multimap<K, V> multimap();
1989
1990    @Override public int size() {
1991      return multimap().size();
1992    }
1993
1994    @Override public boolean contains(@Nullable Object o) {
1995      if (o instanceof Map.Entry) {
1996        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1997        return multimap().containsEntry(entry.getKey(), entry.getValue());
1998      }
1999      return false;
2000    }
2001
2002    @Override public boolean remove(@Nullable Object o) {
2003      if (o instanceof Map.Entry) {
2004        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
2005        return multimap().remove(entry.getKey(), entry.getValue());
2006      }
2007      return false;
2008    }
2009
2010    @Override public void clear() {
2011      multimap().clear();
2012    }
2013  }
2014
2015  /**
2016   * A skeleton implementation of {@link SetMultimap#entries()}.
2017   */
2018  static abstract class EntrySet<K, V> extends Entries<K, V> implements
2019      Set<Map.Entry<K, V>> {
2020    @Override public int hashCode() {
2021      return Sets.hashCodeImpl(this);
2022    }
2023
2024    @Override public boolean equals(@Nullable Object obj) {
2025      return Sets.equalsImpl(this, obj);
2026    }
2027  }
2028
2029  /**
2030   * A skeleton implementation of {@link Multimap#asMap()}.
2031   */
2032  static abstract class AsMap<K, V> extends
2033      Maps.ImprovedAbstractMap<K, Collection<V>> {
2034    abstract Multimap<K, V> multimap();
2035
2036    @Override public abstract int size();
2037
2038    abstract Iterator<Entry<K, Collection<V>>> entryIterator();
2039
2040    @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
2041      return new EntrySet();
2042    }
2043
2044    void removeValuesForKey(Object key){
2045      multimap().removeAll(key);
2046    }
2047
2048    class EntrySet extends Maps.EntrySet<K, Collection<V>> {
2049      @Override Map<K, Collection<V>> map() {
2050        return AsMap.this;
2051      }
2052
2053      @Override public Iterator<Entry<K, Collection<V>>> iterator() {
2054        return entryIterator();
2055      }
2056
2057      @Override public boolean remove(Object o) {
2058        if (!contains(o)) {
2059          return false;
2060        }
2061        Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
2062        removeValuesForKey(entry.getKey());
2063        return true;
2064      }
2065    }
2066
2067    @SuppressWarnings("unchecked")
2068    @Override public Collection<V> get(Object key) {
2069      return containsKey(key) ? multimap().get((K) key) : null;
2070    }
2071
2072    @Override public Collection<V> remove(Object key) {
2073      return containsKey(key) ? multimap().removeAll(key) : null;
2074    }
2075
2076    @Override public Set<K> keySet() {
2077      return multimap().keySet();
2078    }
2079
2080    @Override public boolean isEmpty() {
2081      return multimap().isEmpty();
2082    }
2083
2084    @Override public boolean containsKey(Object key) {
2085      return multimap().containsKey(key);
2086    }
2087
2088    @Override public void clear() {
2089      multimap().clear();
2090    }
2091  }
2092
2093  /**
2094   * Returns a multimap containing the mappings in {@code unfiltered} whose keys
2095   * satisfy a predicate. The returned multimap is a live view of
2096   * {@code unfiltered}; changes to one affect the other.
2097   *
2098   * <p>The resulting multimap's views have iterators that don't support
2099   * {@code remove()}, but all other methods are supported by the multimap and
2100   * its views. When adding a key that doesn't satisfy the predicate, the
2101   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
2102   * methods throw an {@link IllegalArgumentException}.
2103   *
2104   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2105   * the filtered multimap or its views, only mappings whose keys satisfy the
2106   * filter will be removed from the underlying multimap.
2107   *
2108   * <p>The returned multimap isn't threadsafe or serializable, even if
2109   * {@code unfiltered} is.
2110   *
2111   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2112   * across every key/value mapping in the underlying multimap and determine
2113   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2114   * faster to copy the filtered multimap and use the copy.
2115   *
2116   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>,
2117   * as documented at {@link Predicate#apply}. Do not provide a predicate such
2118   * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
2119   * with equals.
2120   *
2121   * @since 11.0
2122   */
2123  @GwtIncompatible(value = "untested")
2124  public static <K, V> Multimap<K, V> filterKeys(
2125      Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2126    checkNotNull(keyPredicate);
2127    Predicate<Entry<K, V>> entryPredicate =
2128        new Predicate<Entry<K, V>>() {
2129          @Override
2130          public boolean apply(Entry<K, V> input) {
2131            return keyPredicate.apply(input.getKey());
2132          }
2133        };
2134    return filterEntries(unfiltered, entryPredicate);
2135  }
2136
2137  /**
2138   * Returns a multimap containing the mappings in {@code unfiltered} whose values
2139   * satisfy a predicate. The returned multimap is a live view of
2140   * {@code unfiltered}; changes to one affect the other.
2141   *
2142   * <p>The resulting multimap's views have iterators that don't support
2143   * {@code remove()}, but all other methods are supported by the multimap and
2144   * its views. When adding a value that doesn't satisfy the predicate, the
2145   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
2146   * methods throw an {@link IllegalArgumentException}.
2147   *
2148   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2149   * the filtered multimap or its views, only mappings whose value satisfy the
2150   * filter will be removed from the underlying multimap.
2151   *
2152   * <p>The returned multimap isn't threadsafe or serializable, even if
2153   * {@code unfiltered} is.
2154   *
2155   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2156   * across every key/value mapping in the underlying multimap and determine
2157   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2158   * faster to copy the filtered multimap and use the copy.
2159   *
2160   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
2161   * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2162   * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2163   * inconsistent with equals.
2164   *
2165   * @since 11.0
2166   */
2167  @GwtIncompatible(value = "untested")
2168  public static <K, V> Multimap<K, V> filterValues(
2169      Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2170    checkNotNull(valuePredicate);
2171    Predicate<Entry<K, V>> entryPredicate =
2172        new Predicate<Entry<K, V>>() {
2173          @Override
2174          public boolean apply(Entry<K, V> input) {
2175            return valuePredicate.apply(input.getValue());
2176          }
2177        };
2178    return filterEntries(unfiltered, entryPredicate);
2179  }
2180
2181  /**
2182   * Returns a multimap containing the mappings in {@code unfiltered} that
2183   * satisfy a predicate. The returned multimap is a live view of
2184   * {@code unfiltered}; changes to one affect the other.
2185   *
2186   * <p>The resulting multimap's views have iterators that don't support
2187   * {@code remove()}, but all other methods are supported by the multimap and
2188   * its views. When adding a key/value pair that doesn't satisfy the predicate,
2189   * multimap's {@code put()}, {@code putAll()}, and {@code replaceValues()}
2190   * methods throw an {@link IllegalArgumentException}.
2191   *
2192   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2193   * the filtered multimap or its views, only mappings whose keys satisfy the
2194   * filter will be removed from the underlying multimap.
2195   *
2196   * <p>The returned multimap isn't threadsafe or serializable, even if
2197   * {@code unfiltered} is.
2198   *
2199   * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2200   * across every key/value mapping in the underlying multimap and determine
2201   * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2202   * faster to copy the filtered multimap and use the copy.
2203   *
2204   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
2205   * equals</i>, as documented at {@link Predicate#apply}.
2206   *
2207   * @since 11.0
2208   */
2209  @GwtIncompatible(value = "untested")
2210  public static <K, V> Multimap<K, V> filterEntries(
2211      Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2212    checkNotNull(entryPredicate);
2213    return (unfiltered instanceof FilteredMultimap)
2214        ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
2215        : new FilteredMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2216  }
2217
2218  /**
2219   * Support removal operations when filtering a filtered multimap. Since a
2220   * filtered multimap has iterators that don't support remove, passing one to
2221   * the FilteredMultimap constructor would lead to a multimap whose removal
2222   * operations would fail. This method combines the predicates to avoid that
2223   * problem.
2224   */
2225  private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> map,
2226      Predicate<? super Entry<K, V>> entryPredicate) {
2227    Predicate<Entry<K, V>> predicate
2228        = Predicates.and(map.predicate, entryPredicate);
2229    return new FilteredMultimap<K, V>(map.unfiltered, predicate);
2230  }
2231
2232  private static class FilteredMultimap<K, V> implements Multimap<K, V> {
2233    final Multimap<K, V> unfiltered;
2234    final Predicate<? super Entry<K, V>> predicate;
2235
2236    FilteredMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2237      this.unfiltered = unfiltered;
2238      this.predicate = predicate;
2239    }
2240
2241    @Override public int size() {
2242      return entries().size();
2243    }
2244
2245    @Override public boolean isEmpty() {
2246      return entries().isEmpty();
2247    }
2248
2249    @Override public boolean containsKey(Object key) {
2250      return asMap().containsKey(key);
2251    }
2252
2253    @Override public boolean containsValue(Object value) {
2254      return values().contains(value);
2255    }
2256
2257    // This method should be called only when key is a K and value is a V.
2258    @SuppressWarnings("unchecked")
2259    boolean satisfiesPredicate(Object key, Object value) {
2260      return predicate.apply(Maps.immutableEntry((K) key, (V) value));
2261    }
2262
2263    @Override public boolean containsEntry(Object key, Object value) {
2264      return unfiltered.containsEntry(key, value) && satisfiesPredicate(key, value);
2265    }
2266
2267    @Override public boolean put(K key, V value) {
2268      checkArgument(satisfiesPredicate(key, value));
2269      return unfiltered.put(key, value);
2270    }
2271
2272    @Override public boolean remove(Object key, Object value) {
2273      return containsEntry(key, value) ? unfiltered.remove(key, value) : false;
2274    }
2275
2276    @Override public boolean putAll(K key, Iterable<? extends V> values) {
2277      for (V value : values) {
2278        checkArgument(satisfiesPredicate(key, value));
2279      }
2280      return unfiltered.putAll(key, values);
2281    }
2282
2283    @Override public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
2284      for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
2285        checkArgument(satisfiesPredicate(entry.getKey(), entry.getValue()));
2286      }
2287      return unfiltered.putAll(multimap);
2288    }
2289
2290    @Override public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
2291      for (V value : values) {
2292        checkArgument(satisfiesPredicate(key, value));
2293      }
2294      // Not calling unfiltered.replaceValues() since values that don't satisify
2295      // the filter should remain in the multimap.
2296      Collection<V> oldValues = removeAll(key);
2297      unfiltered.putAll(key, values);
2298      return oldValues;
2299    }
2300
2301    @Override public Collection<V> removeAll(Object key) {
2302      List<V> removed = Lists.newArrayList();
2303      Collection<V> values = unfiltered.asMap().get(key);
2304      if (values != null) {
2305        Iterator<V> iterator = values.iterator();
2306        while (iterator.hasNext()) {
2307          V value = iterator.next();
2308          if (satisfiesPredicate(key, value)) {
2309            removed.add(value);
2310            iterator.remove();
2311          }
2312        }
2313      }
2314      if (unfiltered instanceof SetMultimap) {
2315        return Collections.unmodifiableSet(Sets.newLinkedHashSet(removed));
2316      } else {
2317        return Collections.unmodifiableList(removed);
2318      }
2319    }
2320
2321    @Override public void clear() {
2322      entries().clear();
2323    }
2324
2325    @Override public boolean equals(@Nullable Object object) {
2326      if (object == this) {
2327        return true;
2328      }
2329      if (object instanceof Multimap) {
2330        Multimap<?, ?> that = (Multimap<?, ?>) object;
2331        return asMap().equals(that.asMap());
2332      }
2333      return false;
2334    }
2335
2336    @Override public int hashCode() {
2337      return asMap().hashCode();
2338    }
2339
2340    @Override public String toString() {
2341      return asMap().toString();
2342    }
2343
2344    class ValuePredicate implements Predicate<V> {
2345      final K key;
2346      ValuePredicate(K key) {
2347        this.key = key;
2348      }
2349      @Override public boolean apply(V value) {
2350        return satisfiesPredicate(key, value);
2351      }
2352    }
2353
2354    Collection<V> filterCollection(Collection<V> collection, Predicate<V> predicate) {
2355      if (collection instanceof Set) {
2356        return Sets.filter((Set<V>) collection, predicate);
2357      } else {
2358        return Collections2.filter(collection, predicate);
2359      }
2360    }
2361
2362    @Override public Collection<V> get(K key) {
2363      return filterCollection(unfiltered.get(key), new ValuePredicate(key));
2364    }
2365
2366    @Override public Set<K> keySet() {
2367      return asMap().keySet();
2368    }
2369
2370    Collection<V> values;
2371
2372    @Override public Collection<V> values() {
2373      return (values == null) ? values = new Values() : values;
2374    }
2375
2376    class Values extends Multimaps.Values<K, V> {
2377      @Override Multimap<K, V> multimap() {
2378        return FilteredMultimap.this;
2379      }
2380
2381      @Override public boolean contains(@Nullable Object o) {
2382        return Iterators.contains(iterator(), o);
2383      }
2384
2385      // Override remove methods since iterator doesn't support remove.
2386
2387      @Override public boolean remove(Object o) {
2388        Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2389        while (iterator.hasNext()) {
2390          Entry<K, V> entry = iterator.next();
2391          if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
2392            iterator.remove();
2393            return true;
2394          }
2395        }
2396        return false;
2397      }
2398
2399      @Override public boolean removeAll(Collection<?> c) {
2400        boolean changed = false;
2401        Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2402        while (iterator.hasNext()) {
2403          Entry<K, V> entry = iterator.next();
2404          if (c.contains(entry.getValue()) && predicate.apply(entry)) {
2405            iterator.remove();
2406            changed = true;
2407          }
2408        }
2409        return changed;
2410      }
2411
2412      @Override public boolean retainAll(Collection<?> c) {
2413        boolean changed = false;
2414        Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2415        while (iterator.hasNext()) {
2416          Entry<K, V> entry = iterator.next();
2417          if (!c.contains(entry.getValue()) && predicate.apply(entry)) {
2418            iterator.remove();
2419            changed = true;
2420          }
2421        }
2422        return changed;
2423      }
2424    }
2425
2426    Collection<Entry<K, V>> entries;
2427
2428    @Override public Collection<Entry<K, V>> entries() {
2429      return (entries == null)
2430          ? entries = Collections2.filter(unfiltered.entries(), predicate)
2431          : entries;
2432    }
2433
2434    /**
2435     * Remove all filtered asMap() entries that satisfy the predicate.
2436     */
2437    boolean removeEntriesIf(Predicate<Map.Entry<K, Collection<V>>> removalPredicate) {
2438      Iterator<Map.Entry<K, Collection<V>>> iterator = unfiltered.asMap().entrySet().iterator();
2439      boolean changed = false;
2440      while (iterator.hasNext()) {
2441        // Determine whether to remove the filtered values with this key.
2442        Map.Entry<K, Collection<V>> entry = iterator.next();
2443        K key = entry.getKey();
2444        Collection<V> collection = entry.getValue();
2445        Predicate<V> valuePredicate = new ValuePredicate(key);
2446        Collection<V> filteredCollection = filterCollection(collection, valuePredicate);
2447        Map.Entry<K, Collection<V>> filteredEntry = Maps.immutableEntry(key, filteredCollection);
2448        if (removalPredicate.apply(filteredEntry) && !filteredCollection.isEmpty()) {
2449          changed = true;
2450          if (Iterables.all(collection, valuePredicate)) {
2451            iterator.remove();  // Remove all values for the key.
2452          } else {
2453            filteredCollection.clear();  // Remove the filtered values only.
2454          }
2455        }
2456      }
2457      return changed;
2458    }
2459
2460    Map<K, Collection<V>> asMap;
2461
2462    @Override public Map<K, Collection<V>> asMap() {
2463      return (asMap == null) ? asMap = createAsMap() : asMap;
2464    }
2465
2466    static final Predicate<Collection<?>> NOT_EMPTY = new Predicate<Collection<?>>() {
2467      @Override public boolean apply(Collection<?> input) {
2468        return !input.isEmpty();
2469      }
2470    };
2471
2472    Map<K, Collection<V>> createAsMap() {
2473      // Select the values that satisify the predicate.
2474      EntryTransformer<K, Collection<V>, Collection<V>> transformer
2475          = new EntryTransformer<K, Collection<V>, Collection<V>>() {
2476            @Override public Collection<V> transformEntry(K key, Collection<V> collection) {
2477              return filterCollection(collection, new ValuePredicate(key));
2478            }
2479      };
2480      Map<K, Collection<V>> transformed
2481          = Maps.transformEntries(unfiltered.asMap(), transformer);
2482
2483      // Select the keys that have at least one value remaining.
2484      Map<K, Collection<V>> filtered = Maps.filterValues(transformed, NOT_EMPTY);
2485
2486      // Override the removal methods, since removing a map entry should not
2487      // affect values that don't satisfy the filter.
2488      return new AsMap(filtered);
2489    }
2490
2491    class AsMap extends ForwardingMap<K, Collection<V>> {
2492     final Map<K, Collection<V>> delegate;
2493
2494      AsMap(Map<K, Collection<V>> delegate) {
2495        this.delegate = delegate;
2496      }
2497
2498      @Override protected Map<K, Collection<V>> delegate() {
2499        return delegate;
2500      }
2501
2502      @Override public Collection<V> remove(Object o) {
2503        Collection<V> output = FilteredMultimap.this.removeAll(o);
2504        return output.isEmpty() ? null : output;
2505      }
2506
2507      @Override public void clear() {
2508        FilteredMultimap.this.clear();
2509      }
2510
2511      Set<K> keySet;
2512
2513      @Override public Set<K> keySet() {
2514        return (keySet == null) ? keySet = new KeySet() : keySet;
2515      }
2516
2517      class KeySet extends Maps.KeySet<K, Collection<V>> {
2518        @Override Map<K, Collection<V>> map() {
2519          return AsMap.this;
2520        }
2521
2522        @Override public boolean remove(Object o) {
2523           Collection<V> collection = delegate.get(o);
2524           if (collection == null) {
2525             return false;
2526           }
2527           collection.clear();
2528           return true;
2529        }
2530
2531        @Override public boolean removeAll(Collection<?> c) {
2532          return Sets.removeAllImpl(this, c.iterator());
2533        }
2534
2535        @Override public boolean retainAll(final Collection<?> c) {
2536          Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2537              = new Predicate<Map.Entry<K, Collection<V>>>() {
2538                @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2539                  return !c.contains(entry.getKey());
2540                }
2541              };
2542          return removeEntriesIf(removalPredicate);
2543        }
2544      }
2545
2546      Values asMapValues;
2547
2548      @Override public Collection<Collection<V>> values() {
2549        return (asMapValues == null) ? asMapValues = new Values() : asMapValues;
2550      }
2551
2552      class Values extends Maps.Values<K, Collection<V>> {
2553        @Override Map<K, Collection<V>> map() {
2554          return AsMap.this;
2555        }
2556
2557        @Override public boolean remove(Object o) {
2558          for (Collection<V> collection : this) {
2559            if (collection.equals(o)) {
2560              collection.clear();
2561              return true;
2562            }
2563          }
2564          return false;
2565        }
2566
2567        @Override public boolean removeAll(final Collection<?> c) {
2568          Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2569              = new Predicate<Map.Entry<K, Collection<V>>>() {
2570                @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2571                  return c.contains(entry.getValue());
2572                }
2573              };
2574          return removeEntriesIf(removalPredicate);
2575        }
2576
2577        @Override public boolean retainAll(final Collection<?> c) {
2578          Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2579              = new Predicate<Map.Entry<K, Collection<V>>>() {
2580                @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2581                  return !c.contains(entry.getValue());
2582                }
2583              };
2584          return removeEntriesIf(removalPredicate);
2585        }
2586      }
2587
2588      EntrySet entrySet;
2589
2590      @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
2591        return (entrySet == null) ? entrySet = new EntrySet(super.entrySet()) : entrySet;
2592      }
2593
2594      class EntrySet extends Maps.EntrySet<K, Collection<V>> {
2595        Set<Map.Entry<K, Collection<V>>> delegateEntries;
2596
2597        public EntrySet(Set<Map.Entry<K, Collection<V>>> delegateEntries) {
2598          this.delegateEntries = delegateEntries;
2599        }
2600
2601        @Override Map<K, Collection<V>> map() {
2602          return AsMap.this;
2603        }
2604
2605        @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
2606          return delegateEntries.iterator();
2607        }
2608
2609        @Override public boolean remove(Object o) {
2610          if (o instanceof Entry) {
2611            Entry<?, ?> entry = (Entry<?, ?>) o;
2612            Collection<V> collection = delegate.get(entry.getKey());
2613            if (collection != null && collection.equals(entry.getValue())) {
2614              collection.clear();
2615              return true;
2616            }
2617          }
2618          return false;
2619        }
2620
2621        @Override public boolean removeAll(Collection<?> c) {
2622          return Sets.removeAllImpl(this, c);
2623        }
2624
2625        @Override public boolean retainAll(final Collection<?> c) {
2626          Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2627              = new Predicate<Map.Entry<K, Collection<V>>>() {
2628                @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2629                  return !c.contains(entry);
2630                }
2631              };
2632          return removeEntriesIf(removalPredicate);
2633        }
2634      }
2635    }
2636
2637    AbstractMultiset<K> keys;
2638
2639    @Override public Multiset<K> keys() {
2640      return (keys == null) ? keys = new Keys() : keys;
2641    }
2642
2643    class Keys extends Multimaps.Keys<K, V> {
2644      @Override Multimap<K, V> multimap() {
2645        return FilteredMultimap.this;
2646      }
2647
2648      @Override public int remove(Object o, int occurrences) {
2649        checkArgument(occurrences >= 0);
2650        Collection<V> values = unfiltered.asMap().get(o);
2651        if (values == null) {
2652          return 0;
2653        }
2654        int priorCount = 0;
2655        int removed = 0;
2656        Iterator<V> iterator = values.iterator();
2657        while (iterator.hasNext()) {
2658          if (satisfiesPredicate(o, iterator.next())) {
2659            priorCount++;
2660            if (removed < occurrences) {
2661              iterator.remove();
2662              removed++;
2663            }
2664          }
2665        }
2666        return priorCount;
2667      }
2668
2669      @Override Set<Multiset.Entry<K>> createEntrySet() {
2670        return new EntrySet();
2671      }
2672
2673      class EntrySet extends Multimaps.Keys<K, V>.KeysEntrySet {
2674        @Override
2675        public boolean removeAll(final Collection<?> c) {
2676          return Sets.removeAllImpl(this, c.iterator());
2677        }
2678
2679        @Override public boolean retainAll(final Collection<?> c) {
2680          Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2681              = new Predicate<Map.Entry<K, Collection<V>>>() {
2682                @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2683                  Multiset.Entry<K> multisetEntry
2684                      = Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
2685                  return !c.contains(multisetEntry);
2686                }
2687              };
2688          return removeEntriesIf(removalPredicate);
2689        }
2690      }
2691    }
2692  }
2693
2694  // TODO(jlevy): Create methods that filter a SetMultimap or SortedSetMultimap.
2695}