diff options
Diffstat (limited to 'guava/src/com/google/common/collect/Multimaps.java')
| -rw-r--r-- | guava/src/com/google/common/collect/Multimaps.java | 888 |
1 files changed, 733 insertions, 155 deletions
diff --git a/guava/src/com/google/common/collect/Multimaps.java b/guava/src/com/google/common/collect/Multimaps.java index 92e5d06..e2f593e 100644 --- a/guava/src/com/google/common/collect/Multimaps.java +++ b/guava/src/com/google/common/collect/Multimaps.java @@ -20,14 +20,17 @@ 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; @@ -35,6 +38,7 @@ 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; @@ -52,10 +56,6 @@ import javax.annotation.Nullable; /** * Provides static methods acting on or generating a {@code Multimap}. * - * <p>See the Guava User Guide article on <a href= - * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Multimaps"> - * {@code Multimaps}</a>. - * * @author Jared Levy * @author Robert Konigsberg * @author Mike Bostock @@ -67,14 +67,9 @@ public final class Multimaps { private Multimaps() {} /** - * Creates a new {@code Multimap} backed by {@code map}, whose internal value - * collections are generated by {@code factory}. - * - * <b>Warning: do not use</b> this method when the collections returned by - * {@code factory} implement either {@link List} or {@code Set}! Use the more - * specific method {@link #newListMultimap}, {@link #newSetMultimap} or {@link - * #newSortedSetMultimap} instead, to avoid very surprising behavior from - * {@link Multimap#equals}. + * 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. * * <p>The {@code factory}-generated and {@code map} classes determine the * multimap iteration order. They also specify the behavior of the @@ -114,7 +109,7 @@ public final class Multimaps { return new CustomMultimap<K, V>(map, factory); } - private static class CustomMultimap<K, V> extends AbstractMapBasedMultimap<K, V> { + private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> { transient Supplier<? extends Collection<V>> factory; CustomMultimap(Map<K, Collection<V>> map, @@ -423,13 +418,13 @@ public final class Multimaps { * <p>It is imperative that the user manually synchronize on the returned * multimap when accessing any of its collection views: <pre> {@code * - * Multimap<K, V> multimap = Multimaps.synchronizedMultimap( + * Multimap<K, V> m = Multimaps.synchronizedMultimap( * HashMultimap.<K, V>create()); * ... - * Collection<V> values = multimap.get(key); // Needn't be in synchronized block + * Set<K> s = m.keySet(); // Needn't be in synchronized block * ... - * synchronized (multimap) { // Synchronizing on multimap, not values! - * Iterator<V> i = values.iterator(); // Must be in synchronized block + * synchronized (m) { // Synchronizing on m, not s! + * Iterator<K> i = s.iterator(); // Must be in synchronized block * while (i.hasNext()) { * foo(i.next()); * } @@ -630,7 +625,7 @@ public final class Multimaps { } @Override public Iterator<Collection<V>> iterator() { final Iterator<Collection<V>> iterator = delegate.iterator(); - return new UnmodifiableIterator<Collection<V>>() { + return new Iterator<Collection<V>>() { @Override public boolean hasNext() { return iterator.hasNext(); @@ -639,6 +634,10 @@ public final class Multimaps { public Collection<V> next() { return unmodifiableValueCollection(iterator.next()); } + @Override + public void remove() { + throw new UnsupportedOperationException(); + } }; } @Override public Object[] toArray() { @@ -1061,7 +1060,7 @@ public final class Multimaps { @Override public Set<V> get(final K key) { - return new Sets.ImprovedAbstractSet<V>() { + return new AbstractSet<V>() { @Override public Iterator<V> iterator() { return new Iterator<V>() { int i; @@ -1142,7 +1141,7 @@ public final class Multimaps { @Override public Multiset<K> keys() { - return new Multimaps.Keys<K, V>(this); + return Multisets.forSet(map.keySet()); } @Override @@ -1193,27 +1192,35 @@ public final class Multimaps { } /** @see MapMultimap#asMap */ - class AsMapEntries extends Sets.ImprovedAbstractSet<Entry<K, Collection<V>>> { + class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> { @Override public int size() { return map.size(); } @Override public Iterator<Entry<K, Collection<V>>> iterator() { - return new TransformedIterator<K, Entry<K, Collection<V>>>(map.keySet().iterator()) { + return new Iterator<Entry<K, Collection<V>>>() { + final Iterator<K> keys = map.keySet().iterator(); + @Override - Entry<K, Collection<V>> transform(final K key) { + public boolean hasNext() { + return keys.hasNext(); + } + @Override + public Entry<K, Collection<V>> next() { + final K key = keys.next(); return new AbstractMapEntry<K, Collection<V>>() { - @Override - public K getKey() { + @Override public K getKey() { return key; } - - @Override - public Collection<V> getValue() { + @Override public Collection<V> getValue() { return get(key); } }; } + @Override + public void remove() { + keys.remove(); + } }; } @@ -1315,6 +1322,7 @@ public final class Multimaps { * * @since 7.0 */ + @Beta public static <K, V1, V2> Multimap<K, V2> transformValues( Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) { checkNotNull(function); @@ -1383,29 +1391,15 @@ public final class Multimaps { * * @since 7.0 */ + @Beta public static <K, V1, V2> Multimap<K, V2> transformEntries( Multimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) { return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer); } - - static final class ValueFunction<K, V1, V2> implements Function<V1, V2> { - private final K key; - private final EntryTransformer<? super K, ? super V1, V2> transformer; - - ValueFunction(K key, EntryTransformer<? super K, ? super V1, V2> transformer) { - this.key = key; - this.transformer = transformer; - } - - @Override - public V2 apply(@Nullable V1 value) { - return transformer.transformEntry(key, value); - } - } private static class TransformedEntriesMultimap<K, V1, V2> - extends AbstractMultimap<K, V2> { + implements Multimap<K, V2> { final Multimap<K, V1> fromMultimap; final EntryTransformer<? super K, ? super V1, V2> transformer; @@ -1415,25 +1409,30 @@ public final class Multimaps { this.transformer = checkNotNull(transformer); } - Collection<V2> transform(K key, Collection<V1> values) { - Function<V1, V2> function = new ValueFunction<K, V1, V2>(key, transformer); - if (values instanceof List) { - return Lists.transform((List<V1>) values, function); - } else { - return Collections2.transform(values, function); - } + Collection<V2> transform(final K key, Collection<V1> values) { + return Collections2.transform(values, new Function<V1, V2>() { + @Override public V2 apply(V1 value) { + return transformer.transformEntry(key, value); + } + }); } - @Override - Map<K, Collection<V2>> createAsMap() { - return Maps.transformEntries(fromMultimap.asMap(), - new EntryTransformer<K, Collection<V1>, Collection<V2>>() { + private transient Map<K, Collection<V2>> asMap; - @Override public Collection<V2> transformEntry( - K key, Collection<V1> value) { - return transform(key, value); - } - }); + @Override public Map<K, Collection<V2>> asMap() { + if (asMap == null) { + Map<K, Collection<V2>> aM = Maps.transformEntries(fromMultimap.asMap(), + new EntryTransformer<K, Collection<V1>, Collection<V2>>() { + + @Override public Collection<V2> transformEntry( + K key, Collection<V1> value) { + return transform(key, value); + } + }); + asMap = aM; + return aM; + } + return asMap; } @Override public void clear() { @@ -1454,25 +1453,58 @@ public final class Multimaps { return values().contains(value); } - @Override - Iterator<Entry<K, V2>> entryIterator() { - return Iterators.transform( - fromMultimap.entries().iterator(), new Function<Entry<K, V1>, Entry<K, V2>>() { - @Override - public Entry<K, V2> apply(final Entry<K, V1> entry) { - return new AbstractMapEntry<K, V2>() { - @Override - public K getKey() { - return entry.getKey(); - } + private transient Collection<Entry<K, V2>> entries; + + @Override public Collection<Entry<K, V2>> entries() { + if (entries == null) { + Collection<Entry<K, V2>> es = new TransformedEntries(transformer); + entries = es; + return es; + } + return entries; + } + + private class TransformedEntries + extends TransformedCollection<Entry<K, V1>, Entry<K, V2>> { + + TransformedEntries( + final EntryTransformer<? super K, ? super V1, V2> transformer) { + super(fromMultimap.entries(), + new Function<Entry<K, V1>, Entry<K, V2>>() { + @Override public Entry<K, V2> apply(final Entry<K, V1> entry) { + return new AbstractMapEntry<K, V2>() { + + @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<V2> values = get((K) entry.getKey()); + return values.remove(entry.getValue()); + } + return false; + } - @Override - public V2 getValue() { - return transformer.transformEntry(entry.getKey(), entry.getValue()); - } - }; - } - }); } @Override public Collection<V2> get(final K key) { @@ -1522,16 +1554,39 @@ public final class Multimaps { @Override public int size() { return fromMultimap.size(); } - - @Override - Collection<V2> createValues() { - return Collections2.transform( - fromMultimap.entries(), new Function<Entry<K, V1>, V2>() { - @Override public V2 apply(Entry<K, V1> entry) { - return transformer.transformEntry( - entry.getKey(), entry.getValue()); - } - }); + + private transient Collection<V2> values; + + @Override public Collection<V2> values() { + if (values == null) { + Collection<V2> vs = Collections2.transform( + fromMultimap.entries(), new Function<Entry<K, V1>, V2>() { + + @Override public V2 apply(Entry<K, V1> 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(); } } @@ -1576,6 +1631,7 @@ public final class Multimaps { * * @since 7.0 */ + @Beta public static <K, V1, V2> ListMultimap<K, V2> transformValues( ListMultimap<K, V1> fromMultimap, final Function<? super V1, V2> function) { @@ -1642,6 +1698,7 @@ public final class Multimaps { * * @since 7.0 */ + @Beta public static <K, V1, V2> ListMultimap<K, V2> transformEntries( ListMultimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) { @@ -1728,6 +1785,24 @@ public final class Multimaps { } /** + * <b>Deprecated.</b> + * + * @since 10.0 + * @deprecated use {@link #index(Iterator, Function)} by casting {@code + * values} to {@code Iterator<V>}, or better yet, by implementing only + * {@code Iterator} and not {@code Iterable}. <b>This method is scheduled + * for deletion in March 2012.</b> + */ + @Beta + @Deprecated + public static <K, V, I extends Object & Iterable<V> & Iterator<V>> + ImmutableListMultimap<K, V> index( + I values, Function<? super V, K> keyFunction) { + Iterable<V> 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, @@ -1783,36 +1858,39 @@ public final class Multimaps { return builder.build(); } - static class Keys<K, V> extends AbstractMultiset<K> { - final Multimap<K, V> multimap; - - Keys(Multimap<K, V> multimap) { - this.multimap = multimap; - } + static abstract class Keys<K, V> extends AbstractMultiset<K> { + abstract Multimap<K, V> multimap(); @Override Iterator<Multiset.Entry<K>> entryIterator() { - return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>( - multimap.asMap().entrySet().iterator()) { - @Override - Multiset.Entry<K> transform( - final Map.Entry<K, Collection<V>> backingEntry) { + final Iterator<Map.Entry<K, Collection<V>>> backingIterator = + multimap().asMap().entrySet().iterator(); + return new Iterator<Multiset.Entry<K>>() { + @Override public boolean hasNext() { + return backingIterator.hasNext(); + } + + @Override public Multiset.Entry<K> next() { + final Map.Entry<K, Collection<V>> backingEntry = + backingIterator.next(); return new Multisets.AbstractEntry<K>() { - @Override - public K getElement() { + @Override public K getElement() { return backingEntry.getKey(); } - @Override - public int getCount() { + @Override public int getCount() { return backingEntry.getValue().size(); } }; } + + @Override public void remove() { + backingIterator.remove(); + } }; } @Override int distinctElements() { - return multimap.asMap().size(); + return multimap().asMap().size(); } @Override Set<Multiset.Entry<K>> createEntrySet() { @@ -1833,22 +1911,22 @@ public final class Multimaps { } @Override public boolean isEmpty() { - return multimap.isEmpty(); + return multimap().isEmpty(); } @Override public boolean contains(@Nullable Object o) { - if (o instanceof Multiset.Entry) { + if (o instanceof Multiset.Entry<?>) { Multiset.Entry<?> entry = (Multiset.Entry<?>) o; - Collection<V> collection = multimap.asMap().get(entry.getElement()); + Collection<V> 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) { + if (o instanceof Multiset.Entry<?>) { Multiset.Entry<?> entry = (Multiset.Entry<?>) o; - Collection<V> collection = multimap.asMap().get(entry.getElement()); + Collection<V> collection = multimap().asMap().get(entry.getElement()); if (collection != null && collection.size() == entry.getCount()) { collection.clear(); return true; @@ -1859,16 +1937,30 @@ public final class Multimaps { } @Override public boolean contains(@Nullable Object element) { - return multimap.containsKey(element); + return multimap().containsKey(element); } @Override public Iterator<K> iterator() { - return Maps.keyIterator(multimap.entries().iterator()); + return Iterators.transform(multimap().entries().iterator(), + new Function<Map.Entry<K, V>, K>() { + @Override public K apply(Map.Entry<K, V> entry) { + return entry.getKey(); + } + }); } @Override public int count(@Nullable Object element) { - Collection<V> values = Maps.safeGet(multimap.asMap(), element); - return (values == null) ? 0 : values.size(); + try { + if (multimap().containsKey(element)) { + Collection<V> 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) { @@ -1877,7 +1969,14 @@ public final class Multimaps { return count(element); } - Collection<V> values = Maps.safeGet(multimap.asMap(), element); + Collection<V> values; + try { + values = multimap().asMap().get(element); + } catch (ClassCastException e) { + return 0; + } catch (NullPointerException e) { + return 0; + } if (values == null) { return 0; @@ -1897,35 +1996,45 @@ public final class Multimaps { } @Override public void clear() { - multimap.clear(); + multimap().clear(); } @Override public Set<K> elementSet() { - return multimap.keySet(); + return multimap().keySet(); } } - static class Values<K, V> extends AbstractCollection<V> { - final Multimap<K, V> multimap; - - Values(Multimap<K, V> multimap) { - this.multimap = multimap; - } + static abstract class Values<K, V> extends AbstractCollection<V> { + abstract Multimap<K, V> multimap(); @Override public Iterator<V> iterator() { - return Maps.valueIterator(multimap.entries().iterator()); + final Iterator<Map.Entry<K, V>> backingIterator = + multimap().entries().iterator(); + return new Iterator<V>() { + @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(); + return multimap().size(); } @Override public boolean contains(@Nullable Object o) { - return multimap.containsValue(o); + return multimap().containsValue(o); } @Override public void clear() { - multimap.clear(); + multimap().clear(); } } @@ -1941,7 +2050,7 @@ public final class Multimaps { } @Override public boolean contains(@Nullable Object o) { - if (o instanceof Map.Entry) { + if (o instanceof Map.Entry<?, ?>) { Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; return multimap().containsEntry(entry.getKey(), entry.getValue()); } @@ -1949,7 +2058,7 @@ public final class Multimaps { } @Override public boolean remove(@Nullable Object o) { - if (o instanceof Map.Entry) { + if (o instanceof Map.Entry<?, ?>) { Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; return multimap().remove(entry.getKey(), entry.getValue()); } @@ -2047,8 +2156,8 @@ public final class Multimaps { * <p>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 {@code replaceValues()} - * methods throw an {@link IllegalArgumentException}. + * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods + * throw an {@link IllegalArgumentException}. * * <p>When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose keys satisfy the @@ -2069,21 +2178,19 @@ public final class Multimaps { * * @since 11.0 */ + @Beta @GwtIncompatible(value = "untested") public static <K, V> Multimap<K, V> filterKeys( - Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { - if (unfiltered instanceof FilteredKeyMultimap) { - FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap<K, V>) unfiltered; - return new FilteredKeyMultimap<K, V>(prev.unfiltered, - Predicates.and(prev.keyPredicate, keyPredicate)); - } else if (unfiltered instanceof FilteredMultimap) { - FilteredMultimap<K, V> prev = (FilteredMultimap<K, V>) unfiltered; - return new FilteredEntryMultimap<K, V>(prev.unfiltered, - Predicates.<Entry<K, V>>and(prev.entryPredicate(), - Predicates.compose(keyPredicate, Maps.<K>keyFunction()))); - } else { - return new FilteredKeyMultimap<K, V>(unfiltered, keyPredicate); - } + Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { + checkNotNull(keyPredicate); + Predicate<Entry<K, V>> entryPredicate = + new Predicate<Entry<K, V>>() { + @Override + public boolean apply(Entry<K, V> input) { + return keyPredicate.apply(input.getKey()); + } + }; + return filterEntries(unfiltered, entryPredicate); } /** @@ -2094,8 +2201,8 @@ public final class Multimaps { * <p>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 {@code replaceValues()} - * methods throw an {@link IllegalArgumentException}. + * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods + * throw an {@link IllegalArgumentException}. * * <p>When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose value satisfy the @@ -2116,10 +2223,19 @@ public final class Multimaps { * * @since 11.0 */ + @Beta @GwtIncompatible(value = "untested") public static <K, V> Multimap<K, V> filterValues( - Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { - return filterEntries(unfiltered, Predicates.compose(valuePredicate, Maps.<V>valueFunction())); + Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { + checkNotNull(valuePredicate); + Predicate<Entry<K, V>> entryPredicate = + new Predicate<Entry<K, V>>() { + @Override + public boolean apply(Entry<K, V> input) { + return valuePredicate.apply(input.getValue()); + } + }; + return filterEntries(unfiltered, entryPredicate); } /** @@ -2130,8 +2246,8 @@ public final class Multimaps { * <p>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 {@code replaceValues()} - * methods throw an {@link IllegalArgumentException}. + * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods + * throw an {@link IllegalArgumentException}. * * <p>When methods such as {@code removeAll()} and {@code clear()} are called on * the filtered multimap or its views, only mappings whose keys satisfy the @@ -2150,27 +2266,489 @@ public final class Multimaps { * * @since 11.0 */ + @Beta @GwtIncompatible(value = "untested") public static <K, V> Multimap<K, V> filterEntries( - Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { + Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { checkNotNull(entryPredicate); return (unfiltered instanceof FilteredMultimap) ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate) - : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate); + : new FilteredMultimap<K, V>(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 FilteredEntryMultimap constructor would lead to a multimap whose removal + * the FilteredMultimap constructor would lead to a multimap whose removal * operations would fail. This method combines the predicates to avoid that * problem. */ - private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> multimap, + private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) { Predicate<Entry<K, V>> predicate - = Predicates.and(multimap.entryPredicate(), entryPredicate); - return new FilteredEntryMultimap<K, V>(multimap.unfiltered, predicate); + = Predicates.and(map.predicate, entryPredicate); + return new FilteredMultimap<K, V>(map.unfiltered, predicate); + } + + private static class FilteredMultimap<K, V> implements Multimap<K, V> { + final Multimap<K, V> unfiltered; + final Predicate<? super Entry<K, V>> predicate; + + FilteredMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> 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<? extends V> values) { + for (V value : values) { + checkArgument(satisfiesPredicate(key, value)); + } + return unfiltered.putAll(key, values); + } + + @Override public boolean putAll(Multimap<? extends K, ? extends V> multimap) { + for (Entry<? extends K, ? extends V> entry : multimap.entries()) { + checkArgument(satisfiesPredicate(entry.getKey(), entry.getValue())); + } + return unfiltered.putAll(multimap); + } + + @Override public Collection<V> replaceValues(K key, Iterable<? extends V> 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<V> oldValues = removeAll(key); + unfiltered.putAll(key, values); + return oldValues; + } + + @Override public Collection<V> removeAll(Object key) { + List<V> removed = Lists.newArrayList(); + Collection<V> values = unfiltered.asMap().get(key); + if (values != null) { + Iterator<V> 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<V> { + final K key; + ValuePredicate(K key) { + this.key = key; + } + @Override public boolean apply(V value) { + return satisfiesPredicate(key, value); + } + } + + Collection<V> filterCollection(Collection<V> collection, Predicate<V> predicate) { + if (collection instanceof Set) { + return Sets.filter((Set<V>) collection, predicate); + } else { + return Collections2.filter(collection, predicate); + } + } + + @Override public Collection<V> get(K key) { + return filterCollection(unfiltered.get(key), new ValuePredicate(key)); + } + + @Override public Set<K> keySet() { + return asMap().keySet(); + } + + Collection<V> values; + + @Override public Collection<V> values() { + return (values == null) ? values = new Values() : values; + } + + class Values extends Multimaps.Values<K, V> { + @Override Multimap<K, V> 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<Entry<K, V>> iterator = unfiltered.entries().iterator(); + while (iterator.hasNext()) { + Entry<K, V> 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<Entry<K, V>> iterator = unfiltered.entries().iterator(); + while (iterator.hasNext()) { + Entry<K, V> 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<Entry<K, V>> iterator = unfiltered.entries().iterator(); + while (iterator.hasNext()) { + Entry<K, V> entry = iterator.next(); + if (!c.contains(entry.getValue()) && predicate.apply(entry)) { + iterator.remove(); + changed = true; + } + } + return changed; + } + } + + Collection<Entry<K, V>> entries; + + @Override public Collection<Entry<K, V>> entries() { + return (entries == null) + ? entries = Collections2.filter(unfiltered.entries(), predicate) + : entries; + } + + /** + * Remove all filtered asMap() entries that satisfy the predicate. + */ + boolean removeEntriesIf(Predicate<Map.Entry<K, Collection<V>>> removalPredicate) { + Iterator<Map.Entry<K, Collection<V>>> iterator = unfiltered.asMap().entrySet().iterator(); + boolean changed = false; + while (iterator.hasNext()) { + // Determine whether to remove the filtered values with this key. + Map.Entry<K, Collection<V>> entry = iterator.next(); + K key = entry.getKey(); + Collection<V> collection = entry.getValue(); + Predicate<V> valuePredicate = new ValuePredicate(key); + Collection<V> filteredCollection = filterCollection(collection, valuePredicate); + Map.Entry<K, Collection<V>> 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<K, Collection<V>> asMap; + + @Override public Map<K, Collection<V>> asMap() { + return (asMap == null) ? asMap = createAsMap() : asMap; + } + + static final Predicate<Collection<?>> NOT_EMPTY = new Predicate<Collection<?>>() { + @Override public boolean apply(Collection<?> input) { + return !input.isEmpty(); + } + }; + + Map<K, Collection<V>> createAsMap() { + // Select the values that satisify the predicate. + EntryTransformer<K, Collection<V>, Collection<V>> transformer + = new EntryTransformer<K, Collection<V>, Collection<V>>() { + @Override public Collection<V> transformEntry(K key, Collection<V> collection) { + return filterCollection(collection, new ValuePredicate(key)); + } + }; + Map<K, Collection<V>> transformed + = Maps.transformEntries(unfiltered.asMap(), transformer); + + // Select the keys that have at least one value remaining. + Map<K, Collection<V>> 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<K, Collection<V>> { + final Map<K, Collection<V>> delegate; + + AsMap(Map<K, Collection<V>> delegate) { + this.delegate = delegate; + } + + @Override protected Map<K, Collection<V>> delegate() { + return delegate; + } + + @Override public Collection<V> remove(Object o) { + Collection<V> output = FilteredMultimap.this.removeAll(o); + return output.isEmpty() ? null : output; + } + + @Override public void clear() { + FilteredMultimap.this.clear(); + } + + Set<K> keySet; + + @Override public Set<K> keySet() { + return (keySet == null) ? keySet = new KeySet() : keySet; + } + + class KeySet extends Maps.KeySet<K, Collection<V>> { + @Override Map<K, Collection<V>> map() { + return AsMap.this; + } + + @Override public boolean remove(Object o) { + Collection<V> 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<Map.Entry<K, Collection<V>>> removalPredicate + = new Predicate<Map.Entry<K, Collection<V>>>() { + @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { + return !c.contains(entry.getKey()); + } + }; + return removeEntriesIf(removalPredicate); + } + } + + Values asMapValues; + + @Override public Collection<Collection<V>> values() { + return (asMapValues == null) ? asMapValues = new Values() : asMapValues; + } + + class Values extends Maps.Values<K, Collection<V>> { + @Override Map<K, Collection<V>> map() { + return AsMap.this; + } + + @Override public boolean remove(Object o) { + for (Collection<V> collection : this) { + if (collection.equals(o)) { + collection.clear(); + return true; + } + } + return false; + } + + @Override public boolean removeAll(final Collection<?> c) { + Predicate<Map.Entry<K, Collection<V>>> removalPredicate + = new Predicate<Map.Entry<K, Collection<V>>>() { + @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { + return c.contains(entry.getValue()); + } + }; + return removeEntriesIf(removalPredicate); + } + + @Override public boolean retainAll(final Collection<?> c) { + Predicate<Map.Entry<K, Collection<V>>> removalPredicate + = new Predicate<Map.Entry<K, Collection<V>>>() { + @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { + return !c.contains(entry.getValue()); + } + }; + return removeEntriesIf(removalPredicate); + } + } + + EntrySet entrySet; + + @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { + return (entrySet == null) ? entrySet = new EntrySet(super.entrySet()) : entrySet; + } + + class EntrySet extends Maps.EntrySet<K, Collection<V>> { + Set<Map.Entry<K, Collection<V>>> delegateEntries; + + public EntrySet(Set<Map.Entry<K, Collection<V>>> delegateEntries) { + this.delegateEntries = delegateEntries; + } + + @Override Map<K, Collection<V>> map() { + return AsMap.this; + } + + @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { + return delegateEntries.iterator(); + } + + @Override public boolean remove(Object o) { + if (o instanceof Entry<?, ?>) { + Entry<?, ?> entry = (Entry<?, ?>) o; + Collection<V> 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<Map.Entry<K, Collection<V>>> removalPredicate + = new Predicate<Map.Entry<K, Collection<V>>>() { + @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { + return !c.contains(entry); + } + }; + return removeEntriesIf(removalPredicate); + } + } + } + + AbstractMultiset<K> keys; + + @Override public Multiset<K> keys() { + return (keys == null) ? keys = new Keys() : keys; + } + + class Keys extends Multimaps.Keys<K, V> { + @Override Multimap<K, V> multimap() { + return FilteredMultimap.this; + } + + @Override public int remove(Object o, int occurrences) { + checkArgument(occurrences >= 0); + Collection<V> values = unfiltered.asMap().get(o); + if (values == null) { + return 0; + } + int priorCount = 0; + int removed = 0; + Iterator<V> iterator = values.iterator(); + while (iterator.hasNext()) { + if (satisfiesPredicate(o, iterator.next())) { + priorCount++; + if (removed < occurrences) { + iterator.remove(); + removed++; + } + } + } + return priorCount; + } + + @Override Set<Multiset.Entry<K>> createEntrySet() { + return new EntrySet(); + } + + class EntrySet extends Multimaps.Keys<K, V>.KeysEntrySet { + @Override public boolean removeAll(Collection<?> c) { + return Sets.removeAllImpl(this, c); + } + + @Override public boolean retainAll(final Collection<?> c) { + Predicate<Map.Entry<K, Collection<V>>> removalPredicate + = new Predicate<Map.Entry<K, Collection<V>>>() { + @Override public boolean apply(Map.Entry<K, Collection<V>> entry) { + Multiset.Entry<K> 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. |