Coverage Summary for Class: FilteredEntryMultimap (com.google.common.collect)

1 /*
2  * Copyright (C) 2012 The Guava Authors
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.google.common.collect;
18 
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.base.Predicates.in;
21 import static com.google.common.base.Predicates.not;
22 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
23 
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.base.MoreObjects;
26 import com.google.common.base.Predicate;
27 import com.google.common.collect.Maps.ViewCachingAbstractMap;
28 import com.google.j2objc.annotations.WeakOuter;
29 import java.util.Collection;
30 import java.util.Collections;
31 import java.util.Iterator;
32 import java.util.List;
33 import java.util.Map;
34 import java.util.Map.Entry;
35 import java.util.Set;
36 import org.checkerframework.checker.nullness.qual.Nullable;
37 
38 /**
39  * Implementation of {@link Multimaps#filterEntries(Multimap, Predicate)}.
40  *
41  * @author Jared Levy
42  * @author Louis Wasserman
43  */
44 @GwtCompatible
45 class FilteredEntryMultimap<K, V> extends AbstractMultimap<K, V> implements FilteredMultimap<K, V> {
46   final Multimap<K, V> unfiltered;
47   final Predicate<? super Entry<K, V>> predicate;
48 
49   FilteredEntryMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
50     this.unfiltered = checkNotNull(unfiltered);
51     this.predicate = checkNotNull(predicate);
52   }
53 
54   @Override
55   public Multimap<K, V> unfiltered() {
56     return unfiltered;
57   }
58 
59   @Override
60   public Predicate<? super Entry<K, V>> entryPredicate() {
61     return predicate;
62   }
63 
64   @Override
65   public int size() {
66     return entries().size();
67   }
68 
69   private boolean satisfies(K key, V value) {
70     return predicate.apply(Maps.immutableEntry(key, value));
71   }
72 
73   final class ValuePredicate implements Predicate<V> {
74     private final K key;
75 
76     ValuePredicate(K key) {
77       this.key = key;
78     }
79 
80     @Override
81     public boolean apply(@Nullable V value) {
82       return satisfies(key, value);
83     }
84   }
85 
86   static <E> Collection<E> filterCollection(
87       Collection<E> collection, Predicate<? super E> predicate) {
88     if (collection instanceof Set) {
89       return Sets.filter((Set<E>) collection, predicate);
90     } else {
91       return Collections2.filter(collection, predicate);
92     }
93   }
94 
95   @Override
96   public boolean containsKey(@Nullable Object key) {
97     return asMap().get(key) != null;
98   }
99 
100   @Override
101   public Collection<V> removeAll(@Nullable Object key) {
102     return MoreObjects.firstNonNull(asMap().remove(key), unmodifiableEmptyCollection());
103   }
104 
105   Collection<V> unmodifiableEmptyCollection() {
106     // These return false, rather than throwing a UOE, on remove calls.
107     return (unfiltered instanceof SetMultimap)
108         ? Collections.<V>emptySet()
109         : Collections.<V>emptyList();
110   }
111 
112   @Override
113   public void clear() {
114     entries().clear();
115   }
116 
117   @Override
118   public Collection<V> get(final K key) {
119     return filterCollection(unfiltered.get(key), new ValuePredicate(key));
120   }
121 
122   @Override
123   Collection<Entry<K, V>> createEntries() {
124     return filterCollection(unfiltered.entries(), predicate);
125   }
126 
127   @Override
128   Collection<V> createValues() {
129     return new FilteredMultimapValues<>(this);
130   }
131 
132   @Override
133   Iterator<Entry<K, V>> entryIterator() {
134     throw new AssertionError("should never be called");
135   }
136 
137   @Override
138   Map<K, Collection<V>> createAsMap() {
139     return new AsMap();
140   }
141 
142   @Override
143   Set<K> createKeySet() {
144     return asMap().keySet();
145   }
146 
147   boolean removeEntriesIf(Predicate<? super Entry<K, Collection<V>>> predicate) {
148     Iterator<Entry<K, Collection<V>>> entryIterator = unfiltered.asMap().entrySet().iterator();
149     boolean changed = false;
150     while (entryIterator.hasNext()) {
151       Entry<K, Collection<V>> entry = entryIterator.next();
152       K key = entry.getKey();
153       Collection<V> collection = filterCollection(entry.getValue(), new ValuePredicate(key));
154       if (!collection.isEmpty() && predicate.apply(Maps.immutableEntry(key, collection))) {
155         if (collection.size() == entry.getValue().size()) {
156           entryIterator.remove();
157         } else {
158           collection.clear();
159         }
160         changed = true;
161       }
162     }
163     return changed;
164   }
165 
166   @WeakOuter
167   class AsMap extends ViewCachingAbstractMap<K, Collection<V>> {
168     @Override
169     public boolean containsKey(@Nullable Object key) {
170       return get(key) != null;
171     }
172 
173     @Override
174     public void clear() {
175       FilteredEntryMultimap.this.clear();
176     }
177 
178     @Override
179     public Collection<V> get(@Nullable Object key) {
180       Collection<V> result = unfiltered.asMap().get(key);
181       if (result == null) {
182         return null;
183       }
184       @SuppressWarnings("unchecked") // key is equal to a K, if not a K itself
185       K k = (K) key;
186       result = filterCollection(result, new ValuePredicate(k));
187       return result.isEmpty() ? null : result;
188     }
189 
190     @Override
191     public Collection<V> remove(@Nullable Object key) {
192       Collection<V> collection = unfiltered.asMap().get(key);
193       if (collection == null) {
194         return null;
195       }
196       @SuppressWarnings("unchecked") // it's definitely equal to a K
197       K k = (K) key;
198       List<V> result = Lists.newArrayList();
199       Iterator<V> itr = collection.iterator();
200       while (itr.hasNext()) {
201         V v = itr.next();
202         if (satisfies(k, v)) {
203           itr.remove();
204           result.add(v);
205         }
206       }
207       if (result.isEmpty()) {
208         return null;
209       } else if (unfiltered instanceof SetMultimap) {
210         return Collections.unmodifiableSet(Sets.newLinkedHashSet(result));
211       } else {
212         return Collections.unmodifiableList(result);
213       }
214     }
215 
216     @Override
217     Set<K> createKeySet() {
218       @WeakOuter
219       class KeySetImpl extends Maps.KeySet<K, Collection<V>> {
220         KeySetImpl() {
221           super(AsMap.this);
222         }
223 
224         @Override
225         public boolean removeAll(Collection<?> c) {
226           return removeEntriesIf(Maps.<K>keyPredicateOnEntries(in(c)));
227         }
228 
229         @Override
230         public boolean retainAll(Collection<?> c) {
231           return removeEntriesIf(Maps.<K>keyPredicateOnEntries(not(in(c))));
232         }
233 
234         @Override
235         public boolean remove(@Nullable Object o) {
236           return AsMap.this.remove(o) != null;
237         }
238       }
239       return new KeySetImpl();
240     }
241 
242     @Override
243     Set<Entry<K, Collection<V>>> createEntrySet() {
244       @WeakOuter
245       class EntrySetImpl extends Maps.EntrySet<K, Collection<V>> {
246         @Override
247         Map<K, Collection<V>> map() {
248           return AsMap.this;
249         }
250 
251         @Override
252         public Iterator<Entry<K, Collection<V>>> iterator() {
253           return new AbstractIterator<Entry<K, Collection<V>>>() {
254             final Iterator<Entry<K, Collection<V>>> backingIterator =
255                 unfiltered.asMap().entrySet().iterator();
256 
257             @Override
258             protected Entry<K, Collection<V>> computeNext() {
259               while (backingIterator.hasNext()) {
260                 Entry<K, Collection<V>> entry = backingIterator.next();
261                 K key = entry.getKey();
262                 Collection<V> collection =
263                     filterCollection(entry.getValue(), new ValuePredicate(key));
264                 if (!collection.isEmpty()) {
265                   return Maps.immutableEntry(key, collection);
266                 }
267               }
268               return endOfData();
269             }
270           };
271         }
272 
273         @Override
274         public boolean removeAll(Collection<?> c) {
275           return removeEntriesIf(in(c));
276         }
277 
278         @Override
279         public boolean retainAll(Collection<?> c) {
280           return removeEntriesIf(not(in(c)));
281         }
282 
283         @Override
284         public int size() {
285           return Iterators.size(iterator());
286         }
287       }
288       return new EntrySetImpl();
289     }
290 
291     @Override
292     Collection<Collection<V>> createValues() {
293       @WeakOuter
294       class ValuesImpl extends Maps.Values<K, Collection<V>> {
295         ValuesImpl() {
296           super(AsMap.this);
297         }
298 
299         @Override
300         public boolean remove(@Nullable Object o) {
301           if (o instanceof Collection) {
302             Collection<?> c = (Collection<?>) o;
303             Iterator<Entry<K, Collection<V>>> entryIterator =
304                 unfiltered.asMap().entrySet().iterator();
305             while (entryIterator.hasNext()) {
306               Entry<K, Collection<V>> entry = entryIterator.next();
307               K key = entry.getKey();
308               Collection<V> collection =
309                   filterCollection(entry.getValue(), new ValuePredicate(key));
310               if (!collection.isEmpty() && c.equals(collection)) {
311                 if (collection.size() == entry.getValue().size()) {
312                   entryIterator.remove();
313                 } else {
314                   collection.clear();
315                 }
316                 return true;
317               }
318             }
319           }
320           return false;
321         }
322 
323         @Override
324         public boolean removeAll(Collection<?> c) {
325           return removeEntriesIf(Maps.<Collection<V>>valuePredicateOnEntries(in(c)));
326         }
327 
328         @Override
329         public boolean retainAll(Collection<?> c) {
330           return removeEntriesIf(Maps.<Collection<V>>valuePredicateOnEntries(not(in(c))));
331         }
332       }
333       return new ValuesImpl();
334     }
335   }
336 
337   @Override
338   Multiset<K> createKeys() {
339     return new Keys();
340   }
341 
342   @WeakOuter
343   class Keys extends Multimaps.Keys<K, V> {
344     Keys() {
345       super(FilteredEntryMultimap.this);
346     }
347 
348     @Override
349     public int remove(@Nullable Object key, int occurrences) {
350       checkNonnegative(occurrences, "occurrences");
351       if (occurrences == 0) {
352         return count(key);
353       }
354       Collection<V> collection = unfiltered.asMap().get(key);
355       if (collection == null) {
356         return 0;
357       }
358       @SuppressWarnings("unchecked") // key is equal to a K, if not a K itself
359       K k = (K) key;
360       int oldCount = 0;
361       Iterator<V> itr = collection.iterator();
362       while (itr.hasNext()) {
363         V v = itr.next();
364         if (satisfies(k, v)) {
365           oldCount++;
366           if (oldCount <= occurrences) {
367             itr.remove();
368           }
369         }
370       }
371       return oldCount;
372     }
373 
374     @Override
375     public Set<Multiset.Entry<K>> entrySet() {
376       return new Multisets.EntrySet<K>() {
377 
378         @Override
379         Multiset<K> multiset() {
380           return Keys.this;
381         }
382 
383         @Override
384         public Iterator<Multiset.Entry<K>> iterator() {
385           return Keys.this.entryIterator();
386         }
387 
388         @Override
389         public int size() {
390           return FilteredEntryMultimap.this.keySet().size();
391         }
392 
393         private boolean removeEntriesIf(final Predicate<? super Multiset.Entry<K>> predicate) {
394           return FilteredEntryMultimap.this.removeEntriesIf(
395               new Predicate<Map.Entry<K, Collection<V>>>() {
396                 @Override
397                 public boolean apply(Map.Entry<K, Collection<V>> entry) {
398                   return predicate.apply(
399                       Multisets.immutableEntry(entry.getKey(), entry.getValue().size()));
400                 }
401               });
402         }
403 
404         @Override
405         public boolean removeAll(Collection<?> c) {
406           return removeEntriesIf(in(c));
407         }
408 
409         @Override
410         public boolean retainAll(Collection<?> c) {
411           return removeEntriesIf(not(in(c)));
412         }
413       };
414     }
415   }
416 }