View Javadoc
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 javax.annotation.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   public Set<K> keySet() {
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
395               .removeEntriesIf(
396                   new Predicate<Map.Entry<K, Collection<V>>>() {
397                     @Override
398                     public boolean apply(Map.Entry<K, Collection<V>> entry) {
399                       return predicate.apply(
400                           Multisets.immutableEntry(entry.getKey(), entry.getValue().size()));
401                     }
402                   });
403         }
404 
405         @Override
406         public boolean removeAll(Collection<?> c) {
407           return removeEntriesIf(in(c));
408         }
409 
410         @Override
411         public boolean retainAll(Collection<?> c) {
412           return removeEntriesIf(not(in(c)));
413         }
414       };
415     }
416   }
417 }