| /* |
| * Copyright (C) 2012 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.checkNotNull; |
| import static com.google.common.base.Predicates.in; |
| import static com.google.common.base.Predicates.not; |
| import static com.google.common.collect.CollectPreconditions.checkNonnegative; |
| |
| import com.google.common.annotations.GwtCompatible; |
| import com.google.common.base.MoreObjects; |
| import com.google.common.base.Predicate; |
| import com.google.common.collect.Maps.ViewCachingAbstractMap; |
| import com.google.j2objc.annotations.WeakOuter; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Iterator; |
| import java.util.List; |
| import java.util.Map; |
| import java.util.Map.Entry; |
| import java.util.Set; |
| import org.checkerframework.checker.nullness.compatqual.NullableDecl; |
| |
| /** |
| * Implementation of {@link Multimaps#filterEntries(Multimap, Predicate)}. |
| * |
| * @author Jared Levy |
| * @author Louis Wasserman |
| */ |
| @GwtCompatible |
| class FilteredEntryMultimap<K, V> extends AbstractMultimap<K, V> implements FilteredMultimap<K, V> { |
| final Multimap<K, V> unfiltered; |
| final Predicate<? super Entry<K, V>> predicate; |
| |
| FilteredEntryMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) { |
| this.unfiltered = checkNotNull(unfiltered); |
| this.predicate = checkNotNull(predicate); |
| } |
| |
| @Override |
| public Multimap<K, V> unfiltered() { |
| return unfiltered; |
| } |
| |
| @Override |
| public Predicate<? super Entry<K, V>> entryPredicate() { |
| return predicate; |
| } |
| |
| @Override |
| public int size() { |
| return entries().size(); |
| } |
| |
| private boolean satisfies(K key, V value) { |
| return predicate.apply(Maps.immutableEntry(key, value)); |
| } |
| |
| final class ValuePredicate implements Predicate<V> { |
| private final K key; |
| |
| ValuePredicate(K key) { |
| this.key = key; |
| } |
| |
| @Override |
| public boolean apply(@NullableDecl V value) { |
| return satisfies(key, value); |
| } |
| } |
| |
| static <E> Collection<E> filterCollection( |
| Collection<E> collection, Predicate<? super E> predicate) { |
| if (collection instanceof Set) { |
| return Sets.filter((Set<E>) collection, predicate); |
| } else { |
| return Collections2.filter(collection, predicate); |
| } |
| } |
| |
| @Override |
| public boolean containsKey(@NullableDecl Object key) { |
| return asMap().get(key) != null; |
| } |
| |
| @Override |
| public Collection<V> removeAll(@NullableDecl Object key) { |
| return MoreObjects.firstNonNull(asMap().remove(key), unmodifiableEmptyCollection()); |
| } |
| |
| Collection<V> unmodifiableEmptyCollection() { |
| // These return false, rather than throwing a UOE, on remove calls. |
| return (unfiltered instanceof SetMultimap) |
| ? Collections.<V>emptySet() |
| : Collections.<V>emptyList(); |
| } |
| |
| @Override |
| public void clear() { |
| entries().clear(); |
| } |
| |
| @Override |
| public Collection<V> get(final K key) { |
| return filterCollection(unfiltered.get(key), new ValuePredicate(key)); |
| } |
| |
| @Override |
| Collection<Entry<K, V>> createEntries() { |
| return filterCollection(unfiltered.entries(), predicate); |
| } |
| |
| @Override |
| Collection<V> createValues() { |
| return new FilteredMultimapValues<>(this); |
| } |
| |
| @Override |
| Iterator<Entry<K, V>> entryIterator() { |
| throw new AssertionError("should never be called"); |
| } |
| |
| @Override |
| Map<K, Collection<V>> createAsMap() { |
| return new AsMap(); |
| } |
| |
| @Override |
| Set<K> createKeySet() { |
| return asMap().keySet(); |
| } |
| |
| boolean removeEntriesIf(Predicate<? super Entry<K, Collection<V>>> predicate) { |
| Iterator<Entry<K, Collection<V>>> entryIterator = unfiltered.asMap().entrySet().iterator(); |
| boolean changed = false; |
| while (entryIterator.hasNext()) { |
| Entry<K, Collection<V>> entry = entryIterator.next(); |
| K key = entry.getKey(); |
| Collection<V> collection = filterCollection(entry.getValue(), new ValuePredicate(key)); |
| if (!collection.isEmpty() && predicate.apply(Maps.immutableEntry(key, collection))) { |
| if (collection.size() == entry.getValue().size()) { |
| entryIterator.remove(); |
| } else { |
| collection.clear(); |
| } |
| changed = true; |
| } |
| } |
| return changed; |
| } |
| |
| @WeakOuter |
| class AsMap extends ViewCachingAbstractMap<K, Collection<V>> { |
| @Override |
| public boolean containsKey(@NullableDecl Object key) { |
| return get(key) != null; |
| } |
| |
| @Override |
| public void clear() { |
| FilteredEntryMultimap.this.clear(); |
| } |
| |
| @Override |
| public Collection<V> get(@NullableDecl Object key) { |
| Collection<V> result = unfiltered.asMap().get(key); |
| if (result == null) { |
| return null; |
| } |
| @SuppressWarnings("unchecked") // key is equal to a K, if not a K itself |
| K k = (K) key; |
| result = filterCollection(result, new ValuePredicate(k)); |
| return result.isEmpty() ? null : result; |
| } |
| |
| @Override |
| public Collection<V> remove(@NullableDecl Object key) { |
| Collection<V> collection = unfiltered.asMap().get(key); |
| if (collection == null) { |
| return null; |
| } |
| @SuppressWarnings("unchecked") // it's definitely equal to a K |
| K k = (K) key; |
| List<V> result = Lists.newArrayList(); |
| Iterator<V> itr = collection.iterator(); |
| while (itr.hasNext()) { |
| V v = itr.next(); |
| if (satisfies(k, v)) { |
| itr.remove(); |
| result.add(v); |
| } |
| } |
| if (result.isEmpty()) { |
| return null; |
| } else if (unfiltered instanceof SetMultimap) { |
| return Collections.unmodifiableSet(Sets.newLinkedHashSet(result)); |
| } else { |
| return Collections.unmodifiableList(result); |
| } |
| } |
| |
| @Override |
| Set<K> createKeySet() { |
| @WeakOuter |
| class KeySetImpl extends Maps.KeySet<K, Collection<V>> { |
| KeySetImpl() { |
| super(AsMap.this); |
| } |
| |
| @Override |
| public boolean removeAll(Collection<?> c) { |
| return removeEntriesIf(Maps.<K>keyPredicateOnEntries(in(c))); |
| } |
| |
| @Override |
| public boolean retainAll(Collection<?> c) { |
| return removeEntriesIf(Maps.<K>keyPredicateOnEntries(not(in(c)))); |
| } |
| |
| @Override |
| public boolean remove(@NullableDecl Object o) { |
| return AsMap.this.remove(o) != null; |
| } |
| } |
| return new KeySetImpl(); |
| } |
| |
| @Override |
| Set<Entry<K, Collection<V>>> createEntrySet() { |
| @WeakOuter |
| class EntrySetImpl extends Maps.EntrySet<K, Collection<V>> { |
| @Override |
| Map<K, Collection<V>> map() { |
| return AsMap.this; |
| } |
| |
| @Override |
| public Iterator<Entry<K, Collection<V>>> iterator() { |
| return new AbstractIterator<Entry<K, Collection<V>>>() { |
| final Iterator<Entry<K, Collection<V>>> backingIterator = |
| unfiltered.asMap().entrySet().iterator(); |
| |
| @Override |
| protected Entry<K, Collection<V>> computeNext() { |
| while (backingIterator.hasNext()) { |
| Entry<K, Collection<V>> entry = backingIterator.next(); |
| K key = entry.getKey(); |
| Collection<V> collection = |
| filterCollection(entry.getValue(), new ValuePredicate(key)); |
| if (!collection.isEmpty()) { |
| return Maps.immutableEntry(key, collection); |
| } |
| } |
| return endOfData(); |
| } |
| }; |
| } |
| |
| @Override |
| public boolean removeAll(Collection<?> c) { |
| return removeEntriesIf(in(c)); |
| } |
| |
| @Override |
| public boolean retainAll(Collection<?> c) { |
| return removeEntriesIf(not(in(c))); |
| } |
| |
| @Override |
| public int size() { |
| return Iterators.size(iterator()); |
| } |
| } |
| return new EntrySetImpl(); |
| } |
| |
| @Override |
| Collection<Collection<V>> createValues() { |
| @WeakOuter |
| class ValuesImpl extends Maps.Values<K, Collection<V>> { |
| ValuesImpl() { |
| super(AsMap.this); |
| } |
| |
| @Override |
| public boolean remove(@NullableDecl Object o) { |
| if (o instanceof Collection) { |
| Collection<?> c = (Collection<?>) o; |
| Iterator<Entry<K, Collection<V>>> entryIterator = |
| unfiltered.asMap().entrySet().iterator(); |
| while (entryIterator.hasNext()) { |
| Entry<K, Collection<V>> entry = entryIterator.next(); |
| K key = entry.getKey(); |
| Collection<V> collection = |
| filterCollection(entry.getValue(), new ValuePredicate(key)); |
| if (!collection.isEmpty() && c.equals(collection)) { |
| if (collection.size() == entry.getValue().size()) { |
| entryIterator.remove(); |
| } else { |
| collection.clear(); |
| } |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| @Override |
| public boolean removeAll(Collection<?> c) { |
| return removeEntriesIf(Maps.<Collection<V>>valuePredicateOnEntries(in(c))); |
| } |
| |
| @Override |
| public boolean retainAll(Collection<?> c) { |
| return removeEntriesIf(Maps.<Collection<V>>valuePredicateOnEntries(not(in(c)))); |
| } |
| } |
| return new ValuesImpl(); |
| } |
| } |
| |
| @Override |
| Multiset<K> createKeys() { |
| return new Keys(); |
| } |
| |
| @WeakOuter |
| class Keys extends Multimaps.Keys<K, V> { |
| Keys() { |
| super(FilteredEntryMultimap.this); |
| } |
| |
| @Override |
| public int remove(@NullableDecl Object key, int occurrences) { |
| checkNonnegative(occurrences, "occurrences"); |
| if (occurrences == 0) { |
| return count(key); |
| } |
| Collection<V> collection = unfiltered.asMap().get(key); |
| if (collection == null) { |
| return 0; |
| } |
| @SuppressWarnings("unchecked") // key is equal to a K, if not a K itself |
| K k = (K) key; |
| int oldCount = 0; |
| Iterator<V> itr = collection.iterator(); |
| while (itr.hasNext()) { |
| V v = itr.next(); |
| if (satisfies(k, v)) { |
| oldCount++; |
| if (oldCount <= occurrences) { |
| itr.remove(); |
| } |
| } |
| } |
| return oldCount; |
| } |
| |
| @Override |
| public Set<Multiset.Entry<K>> entrySet() { |
| return new Multisets.EntrySet<K>() { |
| |
| @Override |
| Multiset<K> multiset() { |
| return Keys.this; |
| } |
| |
| @Override |
| public Iterator<Multiset.Entry<K>> iterator() { |
| return Keys.this.entryIterator(); |
| } |
| |
| @Override |
| public int size() { |
| return FilteredEntryMultimap.this.keySet().size(); |
| } |
| |
| private boolean removeEntriesIf(final Predicate<? super Multiset.Entry<K>> predicate) { |
| return FilteredEntryMultimap.this.removeEntriesIf( |
| new Predicate<Map.Entry<K, Collection<V>>>() { |
| @Override |
| public boolean apply(Map.Entry<K, Collection<V>> entry) { |
| return predicate.apply( |
| Multisets.immutableEntry(entry.getKey(), entry.getValue().size())); |
| } |
| }); |
| } |
| |
| @Override |
| public boolean removeAll(Collection<?> c) { |
| return removeEntriesIf(in(c)); |
| } |
| |
| @Override |
| public boolean retainAll(Collection<?> c) { |
| return removeEntriesIf(not(in(c))); |
| } |
| }; |
| } |
| } |
| } |