/* * Copyright (C) 2007 The Guava Authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.common.collect; import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; import static com.google.common.base.Preconditions.checkState; import com.google.common.annotations.Beta; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.GwtIncompatible; import com.google.common.base.Function; import com.google.common.base.Joiner; import com.google.common.base.Joiner.MapJoiner; import com.google.common.base.Objects; import com.google.common.base.Predicate; import com.google.common.base.Predicates; import com.google.common.base.Supplier; import com.google.common.collect.Collections2.TransformedCollection; import com.google.common.collect.Maps.EntryTransformer; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.AbstractCollection; import java.util.AbstractSet; import java.util.Collection; import java.util.Collections; import java.util.Comparator; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Map.Entry; import java.util.NoSuchElementException; import java.util.Set; import java.util.SortedSet; import javax.annotation.Nullable; /** * Provides static methods acting on or generating a {@code Multimap}. * * @author Jared Levy * @author Robert Konigsberg * @author Mike Bostock * @author Louis Wasserman * @since 2.0 (imported from Google Collections Library) */ @GwtCompatible(emulated = true) public final class Multimaps { private Multimaps() {} /** * Creates a new {@code Multimap} that uses the provided map and factory. It * can generate a multimap based on arbitrary {@link Map} and * {@link Collection} classes. * *

The {@code factory}-generated and {@code map} classes determine the * multimap iteration order. They also specify the behavior of the * {@code equals}, {@code hashCode}, and {@code toString} methods for the * multimap and its returned views. However, the multimap's {@code get} * method returns instances of a different class than {@code factory.get()} * does. * *

The multimap is serializable if {@code map}, {@code factory}, the * collections generated by {@code factory}, and the multimap contents are all * serializable. * *

The multimap is not threadsafe when any concurrent operations update the * multimap, even if {@code map} and the instances generated by * {@code factory} are. Concurrent read operations will work correctly. To * allow concurrent update operations, wrap the multimap with a call to * {@link #synchronizedMultimap}. * *

Call this method only when the simpler methods * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()}, * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()}, * {@link TreeMultimap#create()}, and * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. * *

Note: the multimap assumes complete ownership over of {@code map} and * the collections returned by {@code factory}. Those objects should not be * manually updated and they should not use soft, weak, or phantom references. * * @param map place to store the mapping from each key to its corresponding * values * @param factory supplier of new, empty collections that will each hold all * values for a given key * @throws IllegalArgumentException if {@code map} is not empty */ public static Multimap newMultimap(Map> map, final Supplier> factory) { return new CustomMultimap(map, factory); } private static class CustomMultimap extends AbstractMultimap { transient Supplier> factory; CustomMultimap(Map> map, Supplier> factory) { super(map); this.factory = checkNotNull(factory); } @Override protected Collection createCollection() { return factory.get(); } // can't use Serialization writeMultimap and populateMultimap methods since // there's no way to generate the empty backing map. /** @serialData the factory and the backing map */ @GwtIncompatible("java.io.ObjectOutputStream") private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); stream.writeObject(factory); stream.writeObject(backingMap()); } @GwtIncompatible("java.io.ObjectInputStream") @SuppressWarnings("unchecked") // reading data stored by writeObject private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); factory = (Supplier>) stream.readObject(); Map> map = (Map>) stream.readObject(); setMap(map); } @GwtIncompatible("java serialization not supported") private static final long serialVersionUID = 0; } /** * Creates a new {@code ListMultimap} that uses the provided map and factory. * It can generate a multimap based on arbitrary {@link Map} and {@link List} * classes. * *

The {@code factory}-generated and {@code map} classes determine the * multimap iteration order. They also specify the behavior of the * {@code equals}, {@code hashCode}, and {@code toString} methods for the * multimap and its returned views. The multimap's {@code get}, {@code * removeAll}, and {@code replaceValues} methods return {@code RandomAccess} * lists if the factory does. However, the multimap's {@code get} method * returns instances of a different class than does {@code factory.get()}. * *

The multimap is serializable if {@code map}, {@code factory}, the * lists generated by {@code factory}, and the multimap contents are all * serializable. * *

The multimap is not threadsafe when any concurrent operations update the * multimap, even if {@code map} and the instances generated by * {@code factory} are. Concurrent read operations will work correctly. To * allow concurrent update operations, wrap the multimap with a call to * {@link #synchronizedListMultimap}. * *

Call this method only when the simpler methods * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()} * won't suffice. * *

Note: the multimap assumes complete ownership over of {@code map} and * the lists returned by {@code factory}. Those objects should not be manually * updated, they should be empty when provided, and they should not use soft, * weak, or phantom references. * * @param map place to store the mapping from each key to its corresponding * values * @param factory supplier of new, empty lists that will each hold all values * for a given key * @throws IllegalArgumentException if {@code map} is not empty */ public static ListMultimap newListMultimap( Map> map, final Supplier> factory) { return new CustomListMultimap(map, factory); } private static class CustomListMultimap extends AbstractListMultimap { transient Supplier> factory; CustomListMultimap(Map> map, Supplier> factory) { super(map); this.factory = checkNotNull(factory); } @Override protected List createCollection() { return factory.get(); } /** @serialData the factory and the backing map */ @GwtIncompatible("java.io.ObjectOutputStream") private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); stream.writeObject(factory); stream.writeObject(backingMap()); } @GwtIncompatible("java.io.ObjectInputStream") @SuppressWarnings("unchecked") // reading data stored by writeObject private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); factory = (Supplier>) stream.readObject(); Map> map = (Map>) stream.readObject(); setMap(map); } @GwtIncompatible("java serialization not supported") private static final long serialVersionUID = 0; } /** * Creates a new {@code SetMultimap} that uses the provided map and factory. * It can generate a multimap based on arbitrary {@link Map} and {@link Set} * classes. * *

The {@code factory}-generated and {@code map} classes determine the * multimap iteration order. They also specify the behavior of the * {@code equals}, {@code hashCode}, and {@code toString} methods for the * multimap and its returned views. However, the multimap's {@code get} * method returns instances of a different class than {@code factory.get()} * does. * *

The multimap is serializable if {@code map}, {@code factory}, the * sets generated by {@code factory}, and the multimap contents are all * serializable. * *

The multimap is not threadsafe when any concurrent operations update the * multimap, even if {@code map} and the instances generated by * {@code factory} are. Concurrent read operations will work correctly. To * allow concurrent update operations, wrap the multimap with a call to * {@link #synchronizedSetMultimap}. * *

Call this method only when the simpler methods * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()}, * {@link TreeMultimap#create()}, and * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. * *

Note: the multimap assumes complete ownership over of {@code map} and * the sets returned by {@code factory}. Those objects should not be manually * updated and they should not use soft, weak, or phantom references. * * @param map place to store the mapping from each key to its corresponding * values * @param factory supplier of new, empty sets that will each hold all values * for a given key * @throws IllegalArgumentException if {@code map} is not empty */ public static SetMultimap newSetMultimap( Map> map, final Supplier> factory) { return new CustomSetMultimap(map, factory); } private static class CustomSetMultimap extends AbstractSetMultimap { transient Supplier> factory; CustomSetMultimap(Map> map, Supplier> factory) { super(map); this.factory = checkNotNull(factory); } @Override protected Set createCollection() { return factory.get(); } /** @serialData the factory and the backing map */ @GwtIncompatible("java.io.ObjectOutputStream") private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); stream.writeObject(factory); stream.writeObject(backingMap()); } @GwtIncompatible("java.io.ObjectInputStream") @SuppressWarnings("unchecked") // reading data stored by writeObject private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); factory = (Supplier>) stream.readObject(); Map> map = (Map>) stream.readObject(); setMap(map); } @GwtIncompatible("not needed in emulated source") private static final long serialVersionUID = 0; } /** * Creates a new {@code SortedSetMultimap} that uses the provided map and * factory. It can generate a multimap based on arbitrary {@link Map} and * {@link SortedSet} classes. * *

The {@code factory}-generated and {@code map} classes determine the * multimap iteration order. They also specify the behavior of the * {@code equals}, {@code hashCode}, and {@code toString} methods for the * multimap and its returned views. However, the multimap's {@code get} * method returns instances of a different class than {@code factory.get()} * does. * *

The multimap is serializable if {@code map}, {@code factory}, the * sets generated by {@code factory}, and the multimap contents are all * serializable. * *

The multimap is not threadsafe when any concurrent operations update the * multimap, even if {@code map} and the instances generated by * {@code factory} are. Concurrent read operations will work correctly. To * allow concurrent update operations, wrap the multimap with a call to * {@link #synchronizedSortedSetMultimap}. * *

Call this method only when the simpler methods * {@link TreeMultimap#create()} and * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice. * *

Note: the multimap assumes complete ownership over of {@code map} and * the sets returned by {@code factory}. Those objects should not be manually * updated and they should not use soft, weak, or phantom references. * * @param map place to store the mapping from each key to its corresponding * values * @param factory supplier of new, empty sorted sets that will each hold * all values for a given key * @throws IllegalArgumentException if {@code map} is not empty */ public static SortedSetMultimap newSortedSetMultimap( Map> map, final Supplier> factory) { return new CustomSortedSetMultimap(map, factory); } private static class CustomSortedSetMultimap extends AbstractSortedSetMultimap { transient Supplier> factory; transient Comparator valueComparator; CustomSortedSetMultimap(Map> map, Supplier> factory) { super(map); this.factory = checkNotNull(factory); valueComparator = factory.get().comparator(); } @Override protected SortedSet createCollection() { return factory.get(); } @Override public Comparator valueComparator() { return valueComparator; } /** @serialData the factory and the backing map */ @GwtIncompatible("java.io.ObjectOutputStream") private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); stream.writeObject(factory); stream.writeObject(backingMap()); } @GwtIncompatible("java.io.ObjectInputStream") @SuppressWarnings("unchecked") // reading data stored by writeObject private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); factory = (Supplier>) stream.readObject(); valueComparator = factory.get().comparator(); Map> map = (Map>) stream.readObject(); setMap(map); } @GwtIncompatible("not needed in emulated source") private static final long serialVersionUID = 0; } /** * Copies each key-value mapping in {@code source} into {@code dest}, with * its key and value reversed. * *

If {@code source} is an {@link ImmutableMultimap}, consider using * {@link ImmutableMultimap#inverse} instead. * * @param source any multimap * @param dest the multimap to copy into; usually empty * @return {@code dest} */ public static > M invertFrom( Multimap source, M dest) { checkNotNull(dest); for (Map.Entry entry : source.entries()) { dest.put(entry.getValue(), entry.getKey()); } return dest; } /** * Returns a synchronized (thread-safe) multimap backed by the specified * multimap. In order to guarantee serial access, it is critical that * all access to the backing multimap is accomplished through the * returned multimap. * *

It is imperative that the user manually synchronize on the returned * multimap when accessing any of its collection views:

   {@code
   *
   *   Multimap m = Multimaps.synchronizedMultimap(
   *       HashMultimap.create());
   *   ...
   *   Set s = m.keySet();  // Needn't be in synchronized block
   *   ...
   *   synchronized (m) {  // Synchronizing on m, not s!
   *     Iterator i = s.iterator(); // Must be in synchronized block
   *     while (i.hasNext()) {
   *       foo(i.next());
   *     }
   *   }}
* * Failure to follow this advice may result in non-deterministic behavior. * *

Note that the generated multimap's {@link Multimap#removeAll} and * {@link Multimap#replaceValues} methods return collections that aren't * synchronized. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param multimap the multimap to be wrapped in a synchronized view * @return a synchronized view of the specified multimap */ public static Multimap synchronizedMultimap( Multimap multimap) { return Synchronized.multimap(multimap, null); } /** * Returns an unmodifiable view of the specified multimap. Query operations on * the returned multimap "read through" to the specified multimap, and * attempts to modify the returned multimap, either directly or through the * multimap's views, result in an {@code UnsupportedOperationException}. * *

Note that the generated multimap's {@link Multimap#removeAll} and * {@link Multimap#replaceValues} methods return collections that are * modifiable. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param delegate the multimap for which an unmodifiable view is to be * returned * @return an unmodifiable view of the specified multimap */ public static Multimap unmodifiableMultimap( Multimap delegate) { if (delegate instanceof UnmodifiableMultimap || delegate instanceof ImmutableMultimap) { return delegate; } return new UnmodifiableMultimap(delegate); } /** * Simply returns its argument. * * @deprecated no need to use this * @since 10.0 */ @Deprecated public static Multimap unmodifiableMultimap( ImmutableMultimap delegate) { return checkNotNull(delegate); } private static class UnmodifiableMultimap extends ForwardingMultimap implements Serializable { final Multimap delegate; transient Collection> entries; transient Multiset keys; transient Set keySet; transient Collection values; transient Map> map; UnmodifiableMultimap(final Multimap delegate) { this.delegate = checkNotNull(delegate); } @Override protected Multimap delegate() { return delegate; } @Override public void clear() { throw new UnsupportedOperationException(); } @Override public Map> asMap() { Map> result = map; if (result == null) { final Map> unmodifiableMap = Collections.unmodifiableMap(delegate.asMap()); map = result = new ForwardingMap>() { @Override protected Map> delegate() { return unmodifiableMap; } Set>> entrySet; @Override public Set>> entrySet() { Set>> result = entrySet; return (result == null) ? entrySet = unmodifiableAsMapEntries(unmodifiableMap.entrySet()) : result; } @Override public Collection get(Object key) { Collection collection = unmodifiableMap.get(key); return (collection == null) ? null : unmodifiableValueCollection(collection); } Collection> asMapValues; @Override public Collection> values() { Collection> result = asMapValues; return (result == null) ? asMapValues = new UnmodifiableAsMapValues(unmodifiableMap.values()) : result; } @Override public boolean containsValue(Object o) { return values().contains(o); } }; } return result; } @Override public Collection> entries() { Collection> result = entries; if (result == null) { entries = result = unmodifiableEntries(delegate.entries()); } return result; } @Override public Collection get(K key) { return unmodifiableValueCollection(delegate.get(key)); } @Override public Multiset keys() { Multiset result = keys; if (result == null) { keys = result = Multisets.unmodifiableMultiset(delegate.keys()); } return result; } @Override public Set keySet() { Set result = keySet; if (result == null) { keySet = result = Collections.unmodifiableSet(delegate.keySet()); } return result; } @Override public boolean put(K key, V value) { throw new UnsupportedOperationException(); } @Override public boolean putAll(K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public boolean putAll(Multimap multimap) { throw new UnsupportedOperationException(); } @Override public boolean remove(Object key, Object value) { throw new UnsupportedOperationException(); } @Override public Collection removeAll(Object key) { throw new UnsupportedOperationException(); } @Override public Collection replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public Collection values() { Collection result = values; if (result == null) { values = result = Collections.unmodifiableCollection(delegate.values()); } return result; } private static final long serialVersionUID = 0; } private static class UnmodifiableAsMapValues extends ForwardingCollection> { final Collection> delegate; UnmodifiableAsMapValues(Collection> delegate) { this.delegate = Collections.unmodifiableCollection(delegate); } @Override protected Collection> delegate() { return delegate; } @Override public Iterator> iterator() { final Iterator> iterator = delegate.iterator(); return new Iterator>() { @Override public boolean hasNext() { return iterator.hasNext(); } @Override public Collection next() { return unmodifiableValueCollection(iterator.next()); } @Override public void remove() { throw new UnsupportedOperationException(); } }; } @Override public Object[] toArray() { return standardToArray(); } @Override public T[] toArray(T[] array) { return standardToArray(array); } @Override public boolean contains(Object o) { return standardContains(o); } @Override public boolean containsAll(Collection c) { return standardContainsAll(c); } } private static class UnmodifiableListMultimap extends UnmodifiableMultimap implements ListMultimap { UnmodifiableListMultimap(ListMultimap delegate) { super(delegate); } @Override public ListMultimap delegate() { return (ListMultimap) super.delegate(); } @Override public List get(K key) { return Collections.unmodifiableList(delegate().get(key)); } @Override public List removeAll(Object key) { throw new UnsupportedOperationException(); } @Override public List replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } private static final long serialVersionUID = 0; } private static class UnmodifiableSetMultimap extends UnmodifiableMultimap implements SetMultimap { UnmodifiableSetMultimap(SetMultimap delegate) { super(delegate); } @Override public SetMultimap delegate() { return (SetMultimap) super.delegate(); } @Override public Set get(K key) { /* * Note that this doesn't return a SortedSet when delegate is a * SortedSetMultiset, unlike (SortedSet) super.get(). */ return Collections.unmodifiableSet(delegate().get(key)); } @Override public Set> entries() { return Maps.unmodifiableEntrySet(delegate().entries()); } @Override public Set removeAll(Object key) { throw new UnsupportedOperationException(); } @Override public Set replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } private static final long serialVersionUID = 0; } private static class UnmodifiableSortedSetMultimap extends UnmodifiableSetMultimap implements SortedSetMultimap { UnmodifiableSortedSetMultimap(SortedSetMultimap delegate) { super(delegate); } @Override public SortedSetMultimap delegate() { return (SortedSetMultimap) super.delegate(); } @Override public SortedSet get(K key) { return Collections.unmodifiableSortedSet(delegate().get(key)); } @Override public SortedSet removeAll(Object key) { throw new UnsupportedOperationException(); } @Override public SortedSet replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public Comparator valueComparator() { return delegate().valueComparator(); } private static final long serialVersionUID = 0; } /** * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the * specified multimap. * *

You must follow the warnings described in {@link #synchronizedMultimap}. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param multimap the multimap to be wrapped * @return a synchronized view of the specified multimap */ public static SetMultimap synchronizedSetMultimap( SetMultimap multimap) { return Synchronized.setMultimap(multimap, null); } /** * Returns an unmodifiable view of the specified {@code SetMultimap}. Query * operations on the returned multimap "read through" to the specified * multimap, and attempts to modify the returned multimap, either directly or * through the multimap's views, result in an * {@code UnsupportedOperationException}. * *

Note that the generated multimap's {@link Multimap#removeAll} and * {@link Multimap#replaceValues} methods return collections that are * modifiable. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param delegate the multimap for which an unmodifiable view is to be * returned * @return an unmodifiable view of the specified multimap */ public static SetMultimap unmodifiableSetMultimap( SetMultimap delegate) { if (delegate instanceof UnmodifiableSetMultimap || delegate instanceof ImmutableSetMultimap) { return delegate; } return new UnmodifiableSetMultimap(delegate); } /** * Simply returns its argument. * * @deprecated no need to use this * @since 10.0 */ @Deprecated public static SetMultimap unmodifiableSetMultimap( ImmutableSetMultimap delegate) { return checkNotNull(delegate); } /** * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by * the specified multimap. * *

You must follow the warnings described in {@link #synchronizedMultimap}. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param multimap the multimap to be wrapped * @return a synchronized view of the specified multimap */ public static SortedSetMultimap synchronizedSortedSetMultimap(SortedSetMultimap multimap) { return Synchronized.sortedSetMultimap(multimap, null); } /** * Returns an unmodifiable view of the specified {@code SortedSetMultimap}. * Query operations on the returned multimap "read through" to the specified * multimap, and attempts to modify the returned multimap, either directly or * through the multimap's views, result in an * {@code UnsupportedOperationException}. * *

Note that the generated multimap's {@link Multimap#removeAll} and * {@link Multimap#replaceValues} methods return collections that are * modifiable. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param delegate the multimap for which an unmodifiable view is to be * returned * @return an unmodifiable view of the specified multimap */ public static SortedSetMultimap unmodifiableSortedSetMultimap( SortedSetMultimap delegate) { if (delegate instanceof UnmodifiableSortedSetMultimap) { return delegate; } return new UnmodifiableSortedSetMultimap(delegate); } /** * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the * specified multimap. * *

You must follow the warnings described in {@link #synchronizedMultimap}. * * @param multimap the multimap to be wrapped * @return a synchronized view of the specified multimap */ public static ListMultimap synchronizedListMultimap( ListMultimap multimap) { return Synchronized.listMultimap(multimap, null); } /** * Returns an unmodifiable view of the specified {@code ListMultimap}. Query * operations on the returned multimap "read through" to the specified * multimap, and attempts to modify the returned multimap, either directly or * through the multimap's views, result in an * {@code UnsupportedOperationException}. * *

Note that the generated multimap's {@link Multimap#removeAll} and * {@link Multimap#replaceValues} methods return collections that are * modifiable. * *

The returned multimap will be serializable if the specified multimap is * serializable. * * @param delegate the multimap for which an unmodifiable view is to be * returned * @return an unmodifiable view of the specified multimap */ public static ListMultimap unmodifiableListMultimap( ListMultimap delegate) { if (delegate instanceof UnmodifiableListMultimap || delegate instanceof ImmutableListMultimap) { return delegate; } return new UnmodifiableListMultimap(delegate); } /** * Simply returns its argument. * * @deprecated no need to use this * @since 10.0 */ @Deprecated public static ListMultimap unmodifiableListMultimap( ImmutableListMultimap delegate) { return checkNotNull(delegate); } /** * Returns an unmodifiable view of the specified collection, preserving the * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and * {@code Collection}, in that order of preference. * * @param collection the collection for which to return an unmodifiable view * @return an unmodifiable view of the collection */ private static Collection unmodifiableValueCollection( Collection collection) { if (collection instanceof SortedSet) { return Collections.unmodifiableSortedSet((SortedSet) collection); } else if (collection instanceof Set) { return Collections.unmodifiableSet((Set) collection); } else if (collection instanceof List) { return Collections.unmodifiableList((List) collection); } return Collections.unmodifiableCollection(collection); } /** * Returns an unmodifiable view of the specified multimap {@code asMap} entry. * The {@link Entry#setValue} operation throws an {@link * UnsupportedOperationException}, and the collection returned by {@code * getValue} is also an unmodifiable (type-preserving) view. This also has the * side-effect of redefining equals to comply with the Map.Entry contract, and * to avoid a possible nefarious implementation of equals. * * @param entry the entry for which to return an unmodifiable view * @return an unmodifiable view of the entry */ private static Map.Entry> unmodifiableAsMapEntry( final Map.Entry> entry) { checkNotNull(entry); return new AbstractMapEntry>() { @Override public K getKey() { return entry.getKey(); } @Override public Collection getValue() { return unmodifiableValueCollection(entry.getValue()); } }; } /** * Returns an unmodifiable view of the specified collection of entries. The * {@link Entry#setValue} operation throws an {@link * UnsupportedOperationException}. If the specified collection is a {@code * Set}, the returned collection is also a {@code Set}. * * @param entries the entries for which to return an unmodifiable view * @return an unmodifiable view of the entries */ private static Collection> unmodifiableEntries( Collection> entries) { if (entries instanceof Set) { return Maps.unmodifiableEntrySet((Set>) entries); } return new Maps.UnmodifiableEntries( Collections.unmodifiableCollection(entries)); } /** * Returns an unmodifiable view of the specified set of {@code asMap} entries. * The {@link Entry#setValue} operation throws an {@link * UnsupportedOperationException}, as do any operations that attempt to modify * the returned collection. * * @param asMapEntries the {@code asMap} entries for which to return an * unmodifiable view * @return an unmodifiable view of the collection entries */ private static Set>> unmodifiableAsMapEntries( Set>> asMapEntries) { return new UnmodifiableAsMapEntries( Collections.unmodifiableSet(asMapEntries)); } /** @see Multimaps#unmodifiableAsMapEntries */ static class UnmodifiableAsMapEntries extends ForwardingSet>> { private final Set>> delegate; UnmodifiableAsMapEntries(Set>> delegate) { this.delegate = delegate; } @Override protected Set>> delegate() { return delegate; } @Override public Iterator>> iterator() { final Iterator>> iterator = delegate.iterator(); return new ForwardingIterator>>() { @Override protected Iterator>> delegate() { return iterator; } @Override public Entry> next() { return unmodifiableAsMapEntry(iterator.next()); } }; } @Override public Object[] toArray() { return standardToArray(); } @Override public T[] toArray(T[] array) { return standardToArray(array); } @Override public boolean contains(Object o) { return Maps.containsEntryImpl(delegate(), o); } @Override public boolean containsAll(Collection c) { return standardContainsAll(c); } @Override public boolean equals(@Nullable Object object) { return standardEquals(object); } } /** * Returns a multimap view of the specified map. The multimap is backed by the * map, so changes to the map are reflected in the multimap, and vice versa. * If the map is modified while an iteration over one of the multimap's * collection views is in progress (except through the iterator's own {@code * remove} operation, or through the {@code setValue} operation on a map entry * returned by the iterator), the results of the iteration are undefined. * *

The multimap supports mapping removal, which removes the corresponding * mapping from the map. It does not support any operations which might add * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}. * *

The returned multimap will be serializable if the specified map is * serializable. * * @param map the backing map for the returned multimap view */ public static SetMultimap forMap(Map map) { return new MapMultimap(map); } /** @see Multimaps#forMap */ private static class MapMultimap implements SetMultimap, Serializable { final Map map; transient Map> asMap; MapMultimap(Map map) { this.map = checkNotNull(map); } @Override public int size() { return map.size(); } @Override public boolean isEmpty() { return map.isEmpty(); } @Override public boolean containsKey(Object key) { return map.containsKey(key); } @Override public boolean containsValue(Object value) { return map.containsValue(value); } @Override public boolean containsEntry(Object key, Object value) { return map.entrySet().contains(Maps.immutableEntry(key, value)); } @Override public Set get(final K key) { return new AbstractSet() { @Override public Iterator iterator() { return new Iterator() { int i; @Override public boolean hasNext() { return (i == 0) && map.containsKey(key); } @Override public V next() { if (!hasNext()) { throw new NoSuchElementException(); } i++; return map.get(key); } @Override public void remove() { checkState(i == 1); i = -1; map.remove(key); } }; } @Override public int size() { return map.containsKey(key) ? 1 : 0; } }; } @Override public boolean put(K key, V value) { throw new UnsupportedOperationException(); } @Override public boolean putAll(K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public boolean putAll(Multimap multimap) { throw new UnsupportedOperationException(); } @Override public Set replaceValues(K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public boolean remove(Object key, Object value) { return map.entrySet().remove(Maps.immutableEntry(key, value)); } @Override public Set removeAll(Object key) { Set values = new HashSet(2); if (!map.containsKey(key)) { return values; } values.add(map.remove(key)); return values; } @Override public void clear() { map.clear(); } @Override public Set keySet() { return map.keySet(); } @Override public Multiset keys() { return Multisets.forSet(map.keySet()); } @Override public Collection values() { return map.values(); } @Override public Set> entries() { return map.entrySet(); } @Override public Map> asMap() { Map> result = asMap; if (result == null) { asMap = result = new AsMap(); } return result; } @Override public boolean equals(@Nullable Object object) { if (object == this) { return true; } if (object instanceof Multimap) { Multimap that = (Multimap) object; return this.size() == that.size() && asMap().equals(that.asMap()); } return false; } @Override public int hashCode() { return map.hashCode(); } private static final MapJoiner JOINER = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null"); @Override public String toString() { if (map.isEmpty()) { return "{}"; } StringBuilder builder = Collections2.newStringBuilderForCollection(map.size()).append('{'); JOINER.appendTo(builder, map); return builder.append("]}").toString(); } /** @see MapMultimap#asMap */ class AsMapEntries extends AbstractSet>> { @Override public int size() { return map.size(); } @Override public Iterator>> iterator() { return new Iterator>>() { final Iterator keys = map.keySet().iterator(); @Override public boolean hasNext() { return keys.hasNext(); } @Override public Entry> next() { final K key = keys.next(); return new AbstractMapEntry>() { @Override public K getKey() { return key; } @Override public Collection getValue() { return get(key); } }; } @Override public void remove() { keys.remove(); } }; } @Override public boolean contains(Object o) { if (!(o instanceof Entry)) { return false; } Entry entry = (Entry) o; if (!(entry.getValue() instanceof Set)) { return false; } Set set = (Set) entry.getValue(); return (set.size() == 1) && containsEntry(entry.getKey(), set.iterator().next()); } @Override public boolean remove(Object o) { if (!(o instanceof Entry)) { return false; } Entry entry = (Entry) o; if (!(entry.getValue() instanceof Set)) { return false; } Set set = (Set) entry.getValue(); return (set.size() == 1) && map.entrySet().remove( Maps.immutableEntry(entry.getKey(), set.iterator().next())); } } /** @see MapMultimap#asMap */ class AsMap extends Maps.ImprovedAbstractMap> { @Override protected Set>> createEntrySet() { return new AsMapEntries(); } // The following methods are included for performance. @Override public boolean containsKey(Object key) { return map.containsKey(key); } @SuppressWarnings("unchecked") @Override public Collection get(Object key) { Collection collection = MapMultimap.this.get((K) key); return collection.isEmpty() ? null : collection; } @Override public Collection remove(Object key) { Collection collection = removeAll(key); return collection.isEmpty() ? null : collection; } } private static final long serialVersionUID = 7845222491160860175L; } /** * Returns a view of a multimap where each value is transformed by a function. * All other properties of the multimap, such as iteration order, are left * intact. For example, the code:

   {@code
   *
   * Multimap multimap =
   *     ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
   * Function square = new Function() {
   *     public String apply(Integer in) {
   *       return Integer.toString(in * in);
   *     }
   * };
   * Multimap transformed =
   *     Multimaps.transformValues(multimap, square);
   *   System.out.println(transformed);}
* * ... prints {@code {a=[4, 16], b=[9, 9], c=[6]}}. * *

Changes in the underlying multimap are reflected in this view. * Conversely, this view supports removal operations, and these are reflected * in the underlying multimap. * *

It's acceptable for the underlying multimap to contain null keys, and * even null values provided that the function is capable of accepting null * input. The transformed multimap might contain null values, if the function * sometimes gives a null result. * *

The returned multimap is not thread-safe or serializable, even if the * underlying multimap is. The {@code equals} and {@code hashCode} methods * of the returned multimap are meaningless, since there is not a definition * of {@code equals} or {@code hashCode} for general collections, and * {@code get()} will return a general {@code Collection} as opposed to a * {@code List} or a {@code Set}. * *

The function is applied lazily, invoked when needed. This is necessary * for the returned multimap to be a view, but it means that the function will * be applied many times for bulk operations like * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to * perform well, {@code function} should be fast. To avoid lazy evaluation * when the returned multimap doesn't need to be a view, copy the returned * multimap into a new multimap of your choosing. * * @since 7.0 */ @Beta public static Multimap transformValues( Multimap fromMultimap, final Function function) { checkNotNull(function); EntryTransformer transformer = new EntryTransformer() { @Override public V2 transformEntry(K key, V1 value) { return function.apply(value); } }; return transformEntries(fromMultimap, transformer); } /** * Returns a view of a multimap whose values are derived from the original * multimap's entries. In contrast to {@link #transformValues}, this method's * entry-transformation logic may depend on the key as well as the value. * *

All other properties of the transformed multimap, such as iteration * order, are left intact. For example, the code:

   {@code
   *
   *   SetMultimap multimap =
   *       ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
   *   EntryTransformer transformer =
   *       new EntryTransformer() {
   *         public String transformEntry(String key, Integer value) {
   *            return (value >= 0) ? key : "no" + key;
   *         }
   *       };
   *   Multimap transformed =
   *       Multimaps.transformEntries(multimap, transformer);
   *   System.out.println(transformed);}
* * ... prints {@code {a=[a, a], b=[nob]}}. * *

Changes in the underlying multimap are reflected in this view. * Conversely, this view supports removal operations, and these are reflected * in the underlying multimap. * *

It's acceptable for the underlying multimap to contain null keys and * null values provided that the transformer is capable of accepting null * inputs. The transformed multimap might contain null values if the * transformer sometimes gives a null result. * *

The returned multimap is not thread-safe or serializable, even if the * underlying multimap is. The {@code equals} and {@code hashCode} methods * of the returned multimap are meaningless, since there is not a definition * of {@code equals} or {@code hashCode} for general collections, and * {@code get()} will return a general {@code Collection} as opposed to a * {@code List} or a {@code Set}. * *

The transformer is applied lazily, invoked when needed. This is * necessary for the returned multimap to be a view, but it means that the * transformer will be applied many times for bulk operations like {@link * Multimap#containsValue} and {@link Object#toString}. For this to perform * well, {@code transformer} should be fast. To avoid lazy evaluation when the * returned multimap doesn't need to be a view, copy the returned multimap * into a new multimap of your choosing. * *

Warning: This method assumes that for any instance {@code k} of * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies * that {@code k2} is also of type {@code K}. Using an {@code * EntryTransformer} key type for which this may not hold, such as {@code * ArrayList}, may risk a {@code ClassCastException} when calling methods on * the transformed multimap. * * @since 7.0 */ @Beta public static Multimap transformEntries( Multimap fromMap, EntryTransformer transformer) { return new TransformedEntriesMultimap(fromMap, transformer); } private static class TransformedEntriesMultimap implements Multimap { final Multimap fromMultimap; final EntryTransformer transformer; TransformedEntriesMultimap(Multimap fromMultimap, final EntryTransformer transformer) { this.fromMultimap = checkNotNull(fromMultimap); this.transformer = checkNotNull(transformer); } Collection transform(final K key, Collection values) { return Collections2.transform(values, new Function() { @Override public V2 apply(V1 value) { return transformer.transformEntry(key, value); } }); } private transient Map> asMap; @Override public Map> asMap() { if (asMap == null) { Map> aM = Maps.transformEntries(fromMultimap.asMap(), new EntryTransformer, Collection>() { @Override public Collection transformEntry( K key, Collection value) { return transform(key, value); } }); asMap = aM; return aM; } return asMap; } @Override public void clear() { fromMultimap.clear(); } @SuppressWarnings("unchecked") @Override public boolean containsEntry(Object key, Object value) { Collection values = get((K) key); return values.contains(value); } @Override public boolean containsKey(Object key) { return fromMultimap.containsKey(key); } @Override public boolean containsValue(Object value) { return values().contains(value); } private transient Collection> entries; @Override public Collection> entries() { if (entries == null) { Collection> es = new TransformedEntries(transformer); entries = es; return es; } return entries; } private class TransformedEntries extends TransformedCollection, Entry> { TransformedEntries( final EntryTransformer transformer) { super(fromMultimap.entries(), new Function, Entry>() { @Override public Entry apply(final Entry entry) { return new AbstractMapEntry() { @Override public K getKey() { return entry.getKey(); } @Override public V2 getValue() { return transformer.transformEntry( entry.getKey(), entry.getValue()); } }; } }); } @Override public boolean contains(Object o) { if (o instanceof Entry) { Entry entry = (Entry) o; return containsEntry(entry.getKey(), entry.getValue()); } return false; } @SuppressWarnings("unchecked") @Override public boolean remove(Object o) { if (o instanceof Entry) { Entry entry = (Entry) o; Collection values = get((K) entry.getKey()); return values.remove(entry.getValue()); } return false; } } @Override public Collection get(final K key) { return transform(key, fromMultimap.get(key)); } @Override public boolean isEmpty() { return fromMultimap.isEmpty(); } @Override public Set keySet() { return fromMultimap.keySet(); } @Override public Multiset keys() { return fromMultimap.keys(); } @Override public boolean put(K key, V2 value) { throw new UnsupportedOperationException(); } @Override public boolean putAll(K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public boolean putAll( Multimap multimap) { throw new UnsupportedOperationException(); } @SuppressWarnings("unchecked") @Override public boolean remove(Object key, Object value) { return get((K) key).remove(value); } @SuppressWarnings("unchecked") @Override public Collection removeAll(Object key) { return transform((K) key, fromMultimap.removeAll(key)); } @Override public Collection replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } @Override public int size() { return fromMultimap.size(); } private transient Collection values; @Override public Collection values() { if (values == null) { Collection vs = Collections2.transform( fromMultimap.entries(), new Function, V2>() { @Override public V2 apply(Entry entry) { return transformer.transformEntry( entry.getKey(), entry.getValue()); } }); values = vs; return vs; } return values; } @Override public boolean equals(Object obj) { if (obj instanceof Multimap) { Multimap other = (Multimap) obj; return asMap().equals(other.asMap()); } return false; } @Override public int hashCode() { return asMap().hashCode(); } @Override public String toString() { return asMap().toString(); } } /** * Returns a view of a {@code ListMultimap} where each value is transformed by * a function. All other properties of the multimap, such as iteration order, * are left intact. For example, the code:

   {@code
   *
   *   ListMultimap multimap
   *        = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
   *   Function sqrt =
   *       new Function() {
   *         public Double apply(Integer in) {
   *           return Math.sqrt((int) in);
   *         }
   *       };
   *   ListMultimap transformed = Multimaps.transformValues(map,
   *       sqrt);
   *   System.out.println(transformed);}
* * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}. * *

Changes in the underlying multimap are reflected in this view. * Conversely, this view supports removal operations, and these are reflected * in the underlying multimap. * *

It's acceptable for the underlying multimap to contain null keys, and * even null values provided that the function is capable of accepting null * input. The transformed multimap might contain null values, if the function * sometimes gives a null result. * *

The returned multimap is not thread-safe or serializable, even if the * underlying multimap is. * *

The function is applied lazily, invoked when needed. This is necessary * for the returned multimap to be a view, but it means that the function will * be applied many times for bulk operations like * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to * perform well, {@code function} should be fast. To avoid lazy evaluation * when the returned multimap doesn't need to be a view, copy the returned * multimap into a new multimap of your choosing. * * @since 7.0 */ @Beta public static ListMultimap transformValues( ListMultimap fromMultimap, final Function function) { checkNotNull(function); EntryTransformer transformer = new EntryTransformer() { @Override public V2 transformEntry(K key, V1 value) { return function.apply(value); } }; return transformEntries(fromMultimap, transformer); } /** * Returns a view of a {@code ListMultimap} whose values are derived from the * original multimap's entries. In contrast to * {@link #transformValues(ListMultimap, Function)}, this method's * entry-transformation logic may depend on the key as well as the value. * *

All other properties of the transformed multimap, such as iteration * order, are left intact. For example, the code:

   {@code
   *
   *   Multimap multimap =
   *       ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
   *   EntryTransformer transformer =
   *       new EntryTransformer() {
   *         public String transformEntry(String key, Integer value) {
   *           return key + value;
   *         }
   *       };
   *   Multimap transformed =
   *       Multimaps.transformEntries(multimap, transformer);
   *   System.out.println(transformed);}
* * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}. * *

Changes in the underlying multimap are reflected in this view. * Conversely, this view supports removal operations, and these are reflected * in the underlying multimap. * *

It's acceptable for the underlying multimap to contain null keys and * null values provided that the transformer is capable of accepting null * inputs. The transformed multimap might contain null values if the * transformer sometimes gives a null result. * *

The returned multimap is not thread-safe or serializable, even if the * underlying multimap is. * *

The transformer is applied lazily, invoked when needed. This is * necessary for the returned multimap to be a view, but it means that the * transformer will be applied many times for bulk operations like {@link * Multimap#containsValue} and {@link Object#toString}. For this to perform * well, {@code transformer} should be fast. To avoid lazy evaluation when the * returned multimap doesn't need to be a view, copy the returned multimap * into a new multimap of your choosing. * *

Warning: This method assumes that for any instance {@code k} of * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies * that {@code k2} is also of type {@code K}. Using an {@code * EntryTransformer} key type for which this may not hold, such as {@code * ArrayList}, may risk a {@code ClassCastException} when calling methods on * the transformed multimap. * * @since 7.0 */ @Beta public static ListMultimap transformEntries( ListMultimap fromMap, EntryTransformer transformer) { return new TransformedEntriesListMultimap(fromMap, transformer); } private static final class TransformedEntriesListMultimap extends TransformedEntriesMultimap implements ListMultimap { TransformedEntriesListMultimap(ListMultimap fromMultimap, EntryTransformer transformer) { super(fromMultimap, transformer); } @Override List transform(final K key, Collection values) { return Lists.transform((List) values, new Function() { @Override public V2 apply(V1 value) { return transformer.transformEntry(key, value); } }); } @Override public List get(K key) { return transform(key, fromMultimap.get(key)); } @SuppressWarnings("unchecked") @Override public List removeAll(Object key) { return transform((K) key, fromMultimap.removeAll(key)); } @Override public List replaceValues( K key, Iterable values) { throw new UnsupportedOperationException(); } } /** * Creates an index {@code ImmutableListMultimap} that contains the results of * applying a specified function to each item in an {@code Iterable} of * values. Each value will be stored as a value in the resulting multimap, * yielding a multimap with the same size as the input iterable. The key used * to store that value in the multimap will be the result of calling the * function on that value. The resulting multimap is created as an immutable * snapshot. In the returned multimap, keys appear in the order they are first * encountered, and the values corresponding to each key appear in the same * order as they are encountered. * *

For example,

   {@code
   *
   *   List badGuys =
   *       Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
   *   Function stringLengthFunction = ...;
   *   Multimap index =
   *       Multimaps.index(badGuys, stringLengthFunction);
   *   System.out.println(index);}
* * prints
   {@code
   *
   *   {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}
* * The returned multimap is serializable if its keys and values are all * serializable. * * @param values the values to use when constructing the {@code * ImmutableListMultimap} * @param keyFunction the function used to produce the key for each value * @return {@code ImmutableListMultimap} mapping the result of evaluating the * function {@code keyFunction} on each value in the input collection to * that value * @throws NullPointerException if any of the following cases is true: * */ public static ImmutableListMultimap index( Iterable values, Function keyFunction) { return index(values.iterator(), keyFunction); } /** * Deprecated. * * @since 10.0 * @deprecated use {@link #index(Iterator, Function)} by casting {@code * values} to {@code Iterator}, or better yet, by implementing only * {@code Iterator} and not {@code Iterable}. This method is scheduled * for deletion in March 2012. */ @Beta @Deprecated public static & Iterator> ImmutableListMultimap index( I values, Function keyFunction) { Iterable valuesIterable = checkNotNull(values); return index(valuesIterable, keyFunction); } /** * Creates an index {@code ImmutableListMultimap} that contains the results of * applying a specified function to each item in an {@code Iterator} of * values. Each value will be stored as a value in the resulting multimap, * yielding a multimap with the same size as the input iterator. The key used * to store that value in the multimap will be the result of calling the * function on that value. The resulting multimap is created as an immutable * snapshot. In the returned multimap, keys appear in the order they are first * encountered, and the values corresponding to each key appear in the same * order as they are encountered. * *

For example,

   {@code
   *
   *   List badGuys =
   *       Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
   *   Function stringLengthFunction = ...;
   *   Multimap index =
   *       Multimaps.index(badGuys.iterator(), stringLengthFunction);
   *   System.out.println(index);}
* * prints
   {@code
   *
   *   {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}
* * The returned multimap is serializable if its keys and values are all * serializable. * * @param values the values to use when constructing the {@code * ImmutableListMultimap} * @param keyFunction the function used to produce the key for each value * @return {@code ImmutableListMultimap} mapping the result of evaluating the * function {@code keyFunction} on each value in the input collection to * that value * @throws NullPointerException if any of the following cases is true: *
    *
  • {@code values} is null *
  • {@code keyFunction} is null *
  • An element in {@code values} is null *
  • {@code keyFunction} returns {@code null} for any element of {@code * values} *
* @since 10.0 */ public static ImmutableListMultimap index( Iterator values, Function keyFunction) { checkNotNull(keyFunction); ImmutableListMultimap.Builder builder = ImmutableListMultimap.builder(); while (values.hasNext()) { V value = values.next(); checkNotNull(value, values); builder.put(keyFunction.apply(value), value); } return builder.build(); } static abstract class Keys extends AbstractMultiset { abstract Multimap multimap(); @Override Iterator> entryIterator() { final Iterator>> backingIterator = multimap().asMap().entrySet().iterator(); return new Iterator>() { @Override public boolean hasNext() { return backingIterator.hasNext(); } @Override public Multiset.Entry next() { final Map.Entry> backingEntry = backingIterator.next(); return new Multisets.AbstractEntry() { @Override public K getElement() { return backingEntry.getKey(); } @Override public int getCount() { return backingEntry.getValue().size(); } }; } @Override public void remove() { backingIterator.remove(); } }; } @Override int distinctElements() { return multimap().asMap().size(); } @Override Set> createEntrySet() { return new KeysEntrySet(); } class KeysEntrySet extends Multisets.EntrySet { @Override Multiset multiset() { return Keys.this; } @Override public Iterator> iterator() { return entryIterator(); } @Override public int size() { return distinctElements(); } @Override public boolean isEmpty() { return multimap().isEmpty(); } @Override public boolean contains(@Nullable Object o) { if (o instanceof Multiset.Entry) { Multiset.Entry entry = (Multiset.Entry) o; Collection collection = multimap().asMap().get(entry.getElement()); return collection != null && collection.size() == entry.getCount(); } return false; } @Override public boolean remove(@Nullable Object o) { if (o instanceof Multiset.Entry) { Multiset.Entry entry = (Multiset.Entry) o; Collection collection = multimap().asMap().get(entry.getElement()); if (collection != null && collection.size() == entry.getCount()) { collection.clear(); return true; } } return false; } } @Override public boolean contains(@Nullable Object element) { return multimap().containsKey(element); } @Override public Iterator iterator() { return Iterators.transform(multimap().entries().iterator(), new Function, K>() { @Override public K apply(Map.Entry entry) { return entry.getKey(); } }); } @Override public int count(@Nullable Object element) { try { if (multimap().containsKey(element)) { Collection values = multimap().asMap().get(element); return (values == null) ? 0 : values.size(); } return 0; } catch (ClassCastException e) { return 0; } catch (NullPointerException e) { return 0; } } @Override public int remove(@Nullable Object element, int occurrences) { checkArgument(occurrences >= 0); if (occurrences == 0) { return count(element); } Collection values; try { values = multimap().asMap().get(element); } catch (ClassCastException e) { return 0; } catch (NullPointerException e) { return 0; } if (values == null) { return 0; } int oldCount = values.size(); if (occurrences >= oldCount) { values.clear(); } else { Iterator iterator = values.iterator(); for (int i = 0; i < occurrences; i++) { iterator.next(); iterator.remove(); } } return oldCount; } @Override public void clear() { multimap().clear(); } @Override public Set elementSet() { return multimap().keySet(); } } static abstract class Values extends AbstractCollection { abstract Multimap multimap(); @Override public Iterator iterator() { final Iterator> backingIterator = multimap().entries().iterator(); return new Iterator() { @Override public boolean hasNext() { return backingIterator.hasNext(); } @Override public V next() { return backingIterator.next().getValue(); } @Override public void remove() { backingIterator.remove(); } }; } @Override public int size() { return multimap().size(); } @Override public boolean contains(@Nullable Object o) { return multimap().containsValue(o); } @Override public void clear() { multimap().clear(); } } /** * A skeleton implementation of {@link Multimap#entries()}. */ static abstract class Entries extends AbstractCollection> { abstract Multimap multimap(); @Override public int size() { return multimap().size(); } @Override public boolean contains(@Nullable Object o) { if (o instanceof Map.Entry) { Map.Entry entry = (Map.Entry) o; return multimap().containsEntry(entry.getKey(), entry.getValue()); } return false; } @Override public boolean remove(@Nullable Object o) { if (o instanceof Map.Entry) { Map.Entry entry = (Map.Entry) o; return multimap().remove(entry.getKey(), entry.getValue()); } return false; } @Override public void clear() { multimap().clear(); } } /** * A skeleton implementation of {@link SetMultimap#entries()}. */ static abstract class EntrySet extends Entries implements Set> { @Override public int hashCode() { return Sets.hashCodeImpl(this); } @Override public boolean equals(@Nullable Object obj) { return Sets.equalsImpl(this, obj); } } /** * A skeleton implementation of {@link Multimap#asMap()}. */ static abstract class AsMap extends Maps.ImprovedAbstractMap> { abstract Multimap multimap(); @Override public abstract int size(); abstract Iterator>> entryIterator(); @Override protected Set>> createEntrySet() { return new EntrySet(); } void removeValuesForKey(Object key){ multimap().removeAll(key); } class EntrySet extends Maps.EntrySet> { @Override Map> map() { return AsMap.this; } @Override public Iterator>> iterator() { return entryIterator(); } @Override public boolean remove(Object o) { if (!contains(o)) { return false; } Map.Entry entry = (Map.Entry) o; removeValuesForKey(entry.getKey()); return true; } } @SuppressWarnings("unchecked") @Override public Collection get(Object key) { return containsKey(key) ? multimap().get((K) key) : null; } @Override public Collection remove(Object key) { return containsKey(key) ? multimap().removeAll(key) : null; } @Override public Set keySet() { return multimap().keySet(); } @Override public boolean isEmpty() { return multimap().isEmpty(); } @Override public boolean containsKey(Object key) { return multimap().containsKey(key); } @Override public void clear() { multimap().clear(); } } /** * Returns a multimap containing the mappings in {@code unfiltered} whose keys * satisfy a predicate. The returned multimap is a live view of * {@code unfiltered}; changes to one affect the other. * *

The resulting multimap's views have iterators that don't support * {@code remove()}, but all other methods are supported by the multimap and * its views. When adding a key that doesn't satisfy the predicate, the * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods * throw an {@link IllegalArgumentException}. * *

When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose keys satisfy the * filter will be removed from the underlying multimap. * *

The returned multimap isn't threadsafe or serializable, even if * {@code unfiltered} is. * *

Many of the filtered multimap's methods, such as {@code size()}, iterate * across every key/value mapping in the underlying multimap and determine * which satisfy the filter. When a live view is not needed, it may be * faster to copy the filtered multimap and use the copy. * *

Warning: {@code keyPredicate} must be consistent with equals, * as documented at {@link Predicate#apply}. Do not provide a predicate such * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent * with equals. * * @since 11.0 */ @Beta @GwtIncompatible(value = "untested") public static Multimap filterKeys( Multimap unfiltered, final Predicate keyPredicate) { checkNotNull(keyPredicate); Predicate> entryPredicate = new Predicate>() { @Override public boolean apply(Entry input) { return keyPredicate.apply(input.getKey()); } }; return filterEntries(unfiltered, entryPredicate); } /** * Returns a multimap containing the mappings in {@code unfiltered} whose values * satisfy a predicate. The returned multimap is a live view of * {@code unfiltered}; changes to one affect the other. * *

The resulting multimap's views have iterators that don't support * {@code remove()}, but all other methods are supported by the multimap and * its views. When adding a value that doesn't satisfy the predicate, the * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods * throw an {@link IllegalArgumentException}. * *

When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose value satisfy the * filter will be removed from the underlying multimap. * *

The returned multimap isn't threadsafe or serializable, even if * {@code unfiltered} is. * *

Many of the filtered multimap's methods, such as {@code size()}, iterate * across every key/value mapping in the underlying multimap and determine * which satisfy the filter. When a live view is not needed, it may be * faster to copy the filtered multimap and use the copy. * *

Warning: {@code valuePredicate} must be consistent with * equals, as documented at {@link Predicate#apply}. Do not provide a * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is * inconsistent with equals. * * @since 11.0 */ @Beta @GwtIncompatible(value = "untested") public static Multimap filterValues( Multimap unfiltered, final Predicate valuePredicate) { checkNotNull(valuePredicate); Predicate> entryPredicate = new Predicate>() { @Override public boolean apply(Entry input) { return valuePredicate.apply(input.getValue()); } }; return filterEntries(unfiltered, entryPredicate); } /** * Returns a multimap containing the mappings in {@code unfiltered} that * satisfy a predicate. The returned multimap is a live view of * {@code unfiltered}; changes to one affect the other. * *

The resulting multimap's views have iterators that don't support * {@code remove()}, but all other methods are supported by the multimap and * its views. When adding a key/value pair that doesn't satisfy the predicate, * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods * throw an {@link IllegalArgumentException}. * *

When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose keys satisfy the * filter will be removed from the underlying multimap. * *

The returned multimap isn't threadsafe or serializable, even if * {@code unfiltered} is. * *

Many of the filtered multimap's methods, such as {@code size()}, iterate * across every key/value mapping in the underlying multimap and determine * which satisfy the filter. When a live view is not needed, it may be * faster to copy the filtered multimap and use the copy. * *

Warning: {@code entryPredicate} must be consistent with * equals, as documented at {@link Predicate#apply}. * * @since 11.0 */ @Beta @GwtIncompatible(value = "untested") public static Multimap filterEntries( Multimap unfiltered, Predicate> entryPredicate) { checkNotNull(entryPredicate); return (unfiltered instanceof FilteredMultimap) ? filterFiltered((FilteredMultimap) unfiltered, entryPredicate) : new FilteredMultimap(checkNotNull(unfiltered), entryPredicate); } /** * Support removal operations when filtering a filtered multimap. Since a * filtered multimap has iterators that don't support remove, passing one to * the FilteredMultimap constructor would lead to a multimap whose removal * operations would fail. This method combines the predicates to avoid that * problem. */ private static Multimap filterFiltered(FilteredMultimap map, Predicate> entryPredicate) { Predicate> predicate = Predicates.and(map.predicate, entryPredicate); return new FilteredMultimap(map.unfiltered, predicate); } private static class FilteredMultimap implements Multimap { final Multimap unfiltered; final Predicate> predicate; FilteredMultimap(Multimap unfiltered, Predicate> predicate) { this.unfiltered = unfiltered; this.predicate = predicate; } @Override public int size() { return entries().size(); } @Override public boolean isEmpty() { return entries().isEmpty(); } @Override public boolean containsKey(Object key) { return asMap().containsKey(key); } @Override public boolean containsValue(Object value) { return values().contains(value); } // This method should be called only when key is a K and value is a V. @SuppressWarnings("unchecked") boolean satisfiesPredicate(Object key, Object value) { return predicate.apply(Maps.immutableEntry((K) key, (V) value)); } @Override public boolean containsEntry(Object key, Object value) { return unfiltered.containsEntry(key, value) && satisfiesPredicate(key, value); } @Override public boolean put(K key, V value) { checkArgument(satisfiesPredicate(key, value)); return unfiltered.put(key, value); } @Override public boolean remove(Object key, Object value) { return containsEntry(key, value) ? unfiltered.remove(key, value) : false; } @Override public boolean putAll(K key, Iterable values) { for (V value : values) { checkArgument(satisfiesPredicate(key, value)); } return unfiltered.putAll(key, values); } @Override public boolean putAll(Multimap multimap) { for (Entry entry : multimap.entries()) { checkArgument(satisfiesPredicate(entry.getKey(), entry.getValue())); } return unfiltered.putAll(multimap); } @Override public Collection replaceValues(K key, Iterable values) { for (V value : values) { checkArgument(satisfiesPredicate(key, value)); } // Not calling unfiltered.replaceValues() since values that don't satisify // the filter should remain in the multimap. Collection oldValues = removeAll(key); unfiltered.putAll(key, values); return oldValues; } @Override public Collection removeAll(Object key) { List removed = Lists.newArrayList(); Collection values = unfiltered.asMap().get(key); if (values != null) { Iterator iterator = values.iterator(); while (iterator.hasNext()) { V value = iterator.next(); if (satisfiesPredicate(key, value)) { removed.add(value); iterator.remove(); } } } if (unfiltered instanceof SetMultimap) { return Collections.unmodifiableSet(Sets.newLinkedHashSet(removed)); } else { return Collections.unmodifiableList(removed); } } @Override public void clear() { entries().clear(); } @Override public boolean equals(@Nullable Object object) { if (object == this) { return true; } if (object instanceof Multimap) { Multimap that = (Multimap) object; return asMap().equals(that.asMap()); } return false; } @Override public int hashCode() { return asMap().hashCode(); } @Override public String toString() { return asMap().toString(); } class ValuePredicate implements Predicate { final K key; ValuePredicate(K key) { this.key = key; } @Override public boolean apply(V value) { return satisfiesPredicate(key, value); } } Collection filterCollection(Collection collection, Predicate predicate) { if (collection instanceof Set) { return Sets.filter((Set) collection, predicate); } else { return Collections2.filter(collection, predicate); } } @Override public Collection get(K key) { return filterCollection(unfiltered.get(key), new ValuePredicate(key)); } @Override public Set keySet() { return asMap().keySet(); } Collection values; @Override public Collection values() { return (values == null) ? values = new Values() : values; } class Values extends Multimaps.Values { @Override Multimap multimap() { return FilteredMultimap.this; } @Override public boolean contains(@Nullable Object o) { return Iterators.contains(iterator(), o); } // Override remove methods since iterator doesn't support remove. @Override public boolean remove(Object o) { Iterator> iterator = unfiltered.entries().iterator(); while (iterator.hasNext()) { Entry entry = iterator.next(); if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) { iterator.remove(); return true; } } return false; } @Override public boolean removeAll(Collection c) { boolean changed = false; Iterator> iterator = unfiltered.entries().iterator(); while (iterator.hasNext()) { Entry entry = iterator.next(); if (c.contains(entry.getValue()) && predicate.apply(entry)) { iterator.remove(); changed = true; } } return changed; } @Override public boolean retainAll(Collection c) { boolean changed = false; Iterator> iterator = unfiltered.entries().iterator(); while (iterator.hasNext()) { Entry entry = iterator.next(); if (!c.contains(entry.getValue()) && predicate.apply(entry)) { iterator.remove(); changed = true; } } return changed; } } Collection> entries; @Override public Collection> entries() { return (entries == null) ? entries = Collections2.filter(unfiltered.entries(), predicate) : entries; } /** * Remove all filtered asMap() entries that satisfy the predicate. */ boolean removeEntriesIf(Predicate>> removalPredicate) { Iterator>> iterator = unfiltered.asMap().entrySet().iterator(); boolean changed = false; while (iterator.hasNext()) { // Determine whether to remove the filtered values with this key. Map.Entry> entry = iterator.next(); K key = entry.getKey(); Collection collection = entry.getValue(); Predicate valuePredicate = new ValuePredicate(key); Collection filteredCollection = filterCollection(collection, valuePredicate); Map.Entry> filteredEntry = Maps.immutableEntry(key, filteredCollection); if (removalPredicate.apply(filteredEntry) && !filteredCollection.isEmpty()) { changed = true; if (Iterables.all(collection, valuePredicate)) { iterator.remove(); // Remove all values for the key. } else { filteredCollection.clear(); // Remove the filtered values only. } } } return changed; } Map> asMap; @Override public Map> asMap() { return (asMap == null) ? asMap = createAsMap() : asMap; } static final Predicate> NOT_EMPTY = new Predicate>() { @Override public boolean apply(Collection input) { return !input.isEmpty(); } }; Map> createAsMap() { // Select the values that satisify the predicate. EntryTransformer, Collection> transformer = new EntryTransformer, Collection>() { @Override public Collection transformEntry(K key, Collection collection) { return filterCollection(collection, new ValuePredicate(key)); } }; Map> transformed = Maps.transformEntries(unfiltered.asMap(), transformer); // Select the keys that have at least one value remaining. Map> filtered = Maps.filterValues(transformed, NOT_EMPTY); // Override the removal methods, since removing a map entry should not // affect values that don't satisfy the filter. return new AsMap(filtered); } class AsMap extends ForwardingMap> { final Map> delegate; AsMap(Map> delegate) { this.delegate = delegate; } @Override protected Map> delegate() { return delegate; } @Override public Collection remove(Object o) { Collection output = FilteredMultimap.this.removeAll(o); return output.isEmpty() ? null : output; } @Override public void clear() { FilteredMultimap.this.clear(); } Set keySet; @Override public Set keySet() { return (keySet == null) ? keySet = new KeySet() : keySet; } class KeySet extends Maps.KeySet> { @Override Map> map() { return AsMap.this; } @Override public boolean remove(Object o) { Collection collection = delegate.get(o); if (collection == null) { return false; } collection.clear(); return true; } @Override public boolean removeAll(Collection c) { return Sets.removeAllImpl(this, c); } @Override public boolean retainAll(final Collection c) { Predicate>> removalPredicate = new Predicate>>() { @Override public boolean apply(Map.Entry> entry) { return !c.contains(entry.getKey()); } }; return removeEntriesIf(removalPredicate); } } Values asMapValues; @Override public Collection> values() { return (asMapValues == null) ? asMapValues = new Values() : asMapValues; } class Values extends Maps.Values> { @Override Map> map() { return AsMap.this; } @Override public boolean remove(Object o) { for (Collection collection : this) { if (collection.equals(o)) { collection.clear(); return true; } } return false; } @Override public boolean removeAll(final Collection c) { Predicate>> removalPredicate = new Predicate>>() { @Override public boolean apply(Map.Entry> entry) { return c.contains(entry.getValue()); } }; return removeEntriesIf(removalPredicate); } @Override public boolean retainAll(final Collection c) { Predicate>> removalPredicate = new Predicate>>() { @Override public boolean apply(Map.Entry> entry) { return !c.contains(entry.getValue()); } }; return removeEntriesIf(removalPredicate); } } EntrySet entrySet; @Override public Set>> entrySet() { return (entrySet == null) ? entrySet = new EntrySet(super.entrySet()) : entrySet; } class EntrySet extends Maps.EntrySet> { Set>> delegateEntries; public EntrySet(Set>> delegateEntries) { this.delegateEntries = delegateEntries; } @Override Map> map() { return AsMap.this; } @Override public Iterator>> iterator() { return delegateEntries.iterator(); } @Override public boolean remove(Object o) { if (o instanceof Entry) { Entry entry = (Entry) o; Collection collection = delegate.get(entry.getKey()); if (collection != null && collection.equals(entry.getValue())) { collection.clear(); return true; } } return false; } @Override public boolean removeAll(Collection c) { return Sets.removeAllImpl(this, c); } @Override public boolean retainAll(final Collection c) { Predicate>> removalPredicate = new Predicate>>() { @Override public boolean apply(Map.Entry> entry) { return !c.contains(entry); } }; return removeEntriesIf(removalPredicate); } } } AbstractMultiset keys; @Override public Multiset keys() { return (keys == null) ? keys = new Keys() : keys; } class Keys extends Multimaps.Keys { @Override Multimap multimap() { return FilteredMultimap.this; } @Override public int remove(Object o, int occurrences) { checkArgument(occurrences >= 0); Collection values = unfiltered.asMap().get(o); if (values == null) { return 0; } int priorCount = 0; int removed = 0; Iterator iterator = values.iterator(); while (iterator.hasNext()) { if (satisfiesPredicate(o, iterator.next())) { priorCount++; if (removed < occurrences) { iterator.remove(); removed++; } } } return priorCount; } @Override Set> createEntrySet() { return new EntrySet(); } class EntrySet extends Multimaps.Keys.KeysEntrySet { @Override public boolean removeAll(Collection c) { return Sets.removeAllImpl(this, c); } @Override public boolean retainAll(final Collection c) { Predicate>> removalPredicate = new Predicate>>() { @Override public boolean apply(Map.Entry> entry) { Multiset.Entry multisetEntry = Multisets.immutableEntry(entry.getKey(), entry.getValue().size()); return !c.contains(multisetEntry); } }; return removeEntriesIf(removalPredicate); } } } } // TODO(jlevy): Create methods that filter a SetMultimap or SortedSetMultimap. }