001 /*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkNotNull;
021 import static com.google.common.base.Preconditions.checkState;
022
023 import com.google.common.annotations.Beta;
024 import com.google.common.annotations.GwtCompatible;
025 import com.google.common.annotations.GwtIncompatible;
026 import com.google.common.base.Function;
027 import com.google.common.base.Joiner;
028 import com.google.common.base.Joiner.MapJoiner;
029 import com.google.common.base.Objects;
030 import com.google.common.base.Predicate;
031 import com.google.common.base.Predicates;
032 import com.google.common.base.Supplier;
033 import com.google.common.collect.Collections2.TransformedCollection;
034 import com.google.common.collect.Maps.EntryTransformer;
035
036 import java.io.IOException;
037 import java.io.ObjectInputStream;
038 import java.io.ObjectOutputStream;
039 import java.io.Serializable;
040 import java.util.AbstractCollection;
041 import java.util.AbstractSet;
042 import java.util.Collection;
043 import java.util.Collections;
044 import java.util.Comparator;
045 import java.util.HashSet;
046 import java.util.Iterator;
047 import java.util.List;
048 import java.util.Map;
049 import java.util.Map.Entry;
050 import java.util.NoSuchElementException;
051 import java.util.Set;
052 import java.util.SortedSet;
053
054 import javax.annotation.Nullable;
055
056 /**
057 * Provides static methods acting on or generating a {@code Multimap}.
058 *
059 * @author Jared Levy
060 * @author Robert Konigsberg
061 * @author Mike Bostock
062 * @author Louis Wasserman
063 * @since 2.0 (imported from Google Collections Library)
064 */
065 @GwtCompatible(emulated = true)
066 public final class Multimaps {
067 private Multimaps() {}
068
069 /**
070 * Creates a new {@code Multimap} that uses the provided map and factory. It
071 * can generate a multimap based on arbitrary {@link Map} and
072 * {@link Collection} classes.
073 *
074 * <p>The {@code factory}-generated and {@code map} classes determine the
075 * multimap iteration order. They also specify the behavior of the
076 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
077 * multimap and its returned views. However, the multimap's {@code get}
078 * method returns instances of a different class than {@code factory.get()}
079 * does.
080 *
081 * <p>The multimap is serializable if {@code map}, {@code factory}, the
082 * collections generated by {@code factory}, and the multimap contents are all
083 * serializable.
084 *
085 * <p>The multimap is not threadsafe when any concurrent operations update the
086 * multimap, even if {@code map} and the instances generated by
087 * {@code factory} are. Concurrent read operations will work correctly. To
088 * allow concurrent update operations, wrap the multimap with a call to
089 * {@link #synchronizedMultimap}.
090 *
091 * <p>Call this method only when the simpler methods
092 * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()},
093 * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()},
094 * {@link TreeMultimap#create()}, and
095 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
096 *
097 * <p>Note: the multimap assumes complete ownership over of {@code map} and
098 * the collections returned by {@code factory}. Those objects should not be
099 * manually updated and they should not use soft, weak, or phantom references.
100 *
101 * @param map place to store the mapping from each key to its corresponding
102 * values
103 * @param factory supplier of new, empty collections that will each hold all
104 * values for a given key
105 * @throws IllegalArgumentException if {@code map} is not empty
106 */
107 public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
108 final Supplier<? extends Collection<V>> factory) {
109 return new CustomMultimap<K, V>(map, factory);
110 }
111
112 private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> {
113 transient Supplier<? extends Collection<V>> factory;
114
115 CustomMultimap(Map<K, Collection<V>> map,
116 Supplier<? extends Collection<V>> factory) {
117 super(map);
118 this.factory = checkNotNull(factory);
119 }
120
121 @Override protected Collection<V> createCollection() {
122 return factory.get();
123 }
124
125 // can't use Serialization writeMultimap and populateMultimap methods since
126 // there's no way to generate the empty backing map.
127
128 /** @serialData the factory and the backing map */
129 @GwtIncompatible("java.io.ObjectOutputStream")
130 private void writeObject(ObjectOutputStream stream) throws IOException {
131 stream.defaultWriteObject();
132 stream.writeObject(factory);
133 stream.writeObject(backingMap());
134 }
135
136 @GwtIncompatible("java.io.ObjectInputStream")
137 @SuppressWarnings("unchecked") // reading data stored by writeObject
138 private void readObject(ObjectInputStream stream)
139 throws IOException, ClassNotFoundException {
140 stream.defaultReadObject();
141 factory = (Supplier<? extends Collection<V>>) stream.readObject();
142 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
143 setMap(map);
144 }
145
146 @GwtIncompatible("java serialization not supported")
147 private static final long serialVersionUID = 0;
148 }
149
150 /**
151 * Creates a new {@code ListMultimap} that uses the provided map and factory.
152 * It can generate a multimap based on arbitrary {@link Map} and {@link List}
153 * classes.
154 *
155 * <p>The {@code factory}-generated and {@code map} classes determine the
156 * multimap iteration order. They also specify the behavior of the
157 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
158 * multimap and its returned views. The multimap's {@code get}, {@code
159 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess}
160 * lists if the factory does. However, the multimap's {@code get} method
161 * returns instances of a different class than does {@code factory.get()}.
162 *
163 * <p>The multimap is serializable if {@code map}, {@code factory}, the
164 * lists generated by {@code factory}, and the multimap contents are all
165 * serializable.
166 *
167 * <p>The multimap is not threadsafe when any concurrent operations update the
168 * multimap, even if {@code map} and the instances generated by
169 * {@code factory} are. Concurrent read operations will work correctly. To
170 * allow concurrent update operations, wrap the multimap with a call to
171 * {@link #synchronizedListMultimap}.
172 *
173 * <p>Call this method only when the simpler methods
174 * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()}
175 * won't suffice.
176 *
177 * <p>Note: the multimap assumes complete ownership over of {@code map} and
178 * the lists returned by {@code factory}. Those objects should not be manually
179 * updated, they should be empty when provided, and they should not use soft,
180 * weak, or phantom references.
181 *
182 * @param map place to store the mapping from each key to its corresponding
183 * values
184 * @param factory supplier of new, empty lists that will each hold all values
185 * for a given key
186 * @throws IllegalArgumentException if {@code map} is not empty
187 */
188 public static <K, V> ListMultimap<K, V> newListMultimap(
189 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
190 return new CustomListMultimap<K, V>(map, factory);
191 }
192
193 private static class CustomListMultimap<K, V>
194 extends AbstractListMultimap<K, V> {
195 transient Supplier<? extends List<V>> factory;
196
197 CustomListMultimap(Map<K, Collection<V>> map,
198 Supplier<? extends List<V>> factory) {
199 super(map);
200 this.factory = checkNotNull(factory);
201 }
202
203 @Override protected List<V> createCollection() {
204 return factory.get();
205 }
206
207 /** @serialData the factory and the backing map */
208 @GwtIncompatible("java.io.ObjectOutputStream")
209 private void writeObject(ObjectOutputStream stream) throws IOException {
210 stream.defaultWriteObject();
211 stream.writeObject(factory);
212 stream.writeObject(backingMap());
213 }
214
215 @GwtIncompatible("java.io.ObjectInputStream")
216 @SuppressWarnings("unchecked") // reading data stored by writeObject
217 private void readObject(ObjectInputStream stream)
218 throws IOException, ClassNotFoundException {
219 stream.defaultReadObject();
220 factory = (Supplier<? extends List<V>>) stream.readObject();
221 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
222 setMap(map);
223 }
224
225 @GwtIncompatible("java serialization not supported")
226 private static final long serialVersionUID = 0;
227 }
228
229 /**
230 * Creates a new {@code SetMultimap} that uses the provided map and factory.
231 * It can generate a multimap based on arbitrary {@link Map} and {@link Set}
232 * classes.
233 *
234 * <p>The {@code factory}-generated and {@code map} classes determine the
235 * multimap iteration order. They also specify the behavior of the
236 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
237 * multimap and its returned views. However, the multimap's {@code get}
238 * method returns instances of a different class than {@code factory.get()}
239 * does.
240 *
241 * <p>The multimap is serializable if {@code map}, {@code factory}, the
242 * sets generated by {@code factory}, and the multimap contents are all
243 * serializable.
244 *
245 * <p>The multimap is not threadsafe when any concurrent operations update the
246 * multimap, even if {@code map} and the instances generated by
247 * {@code factory} are. Concurrent read operations will work correctly. To
248 * allow concurrent update operations, wrap the multimap with a call to
249 * {@link #synchronizedSetMultimap}.
250 *
251 * <p>Call this method only when the simpler methods
252 * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()},
253 * {@link TreeMultimap#create()}, and
254 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
255 *
256 * <p>Note: the multimap assumes complete ownership over of {@code map} and
257 * the sets returned by {@code factory}. Those objects should not be manually
258 * updated and they should not use soft, weak, or phantom references.
259 *
260 * @param map place to store the mapping from each key to its corresponding
261 * values
262 * @param factory supplier of new, empty sets that will each hold all values
263 * for a given key
264 * @throws IllegalArgumentException if {@code map} is not empty
265 */
266 public static <K, V> SetMultimap<K, V> newSetMultimap(
267 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
268 return new CustomSetMultimap<K, V>(map, factory);
269 }
270
271 private static class CustomSetMultimap<K, V>
272 extends AbstractSetMultimap<K, V> {
273 transient Supplier<? extends Set<V>> factory;
274
275 CustomSetMultimap(Map<K, Collection<V>> map,
276 Supplier<? extends Set<V>> factory) {
277 super(map);
278 this.factory = checkNotNull(factory);
279 }
280
281 @Override protected Set<V> createCollection() {
282 return factory.get();
283 }
284
285 /** @serialData the factory and the backing map */
286 @GwtIncompatible("java.io.ObjectOutputStream")
287 private void writeObject(ObjectOutputStream stream) throws IOException {
288 stream.defaultWriteObject();
289 stream.writeObject(factory);
290 stream.writeObject(backingMap());
291 }
292
293 @GwtIncompatible("java.io.ObjectInputStream")
294 @SuppressWarnings("unchecked") // reading data stored by writeObject
295 private void readObject(ObjectInputStream stream)
296 throws IOException, ClassNotFoundException {
297 stream.defaultReadObject();
298 factory = (Supplier<? extends Set<V>>) stream.readObject();
299 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
300 setMap(map);
301 }
302
303 @GwtIncompatible("not needed in emulated source")
304 private static final long serialVersionUID = 0;
305 }
306
307 /**
308 * Creates a new {@code SortedSetMultimap} that uses the provided map and
309 * factory. It can generate a multimap based on arbitrary {@link Map} and
310 * {@link SortedSet} classes.
311 *
312 * <p>The {@code factory}-generated and {@code map} classes determine the
313 * multimap iteration order. They also specify the behavior of the
314 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
315 * multimap and its returned views. However, the multimap's {@code get}
316 * method returns instances of a different class than {@code factory.get()}
317 * does.
318 *
319 * <p>The multimap is serializable if {@code map}, {@code factory}, the
320 * sets generated by {@code factory}, and the multimap contents are all
321 * serializable.
322 *
323 * <p>The multimap is not threadsafe when any concurrent operations update the
324 * multimap, even if {@code map} and the instances generated by
325 * {@code factory} are. Concurrent read operations will work correctly. To
326 * allow concurrent update operations, wrap the multimap with a call to
327 * {@link #synchronizedSortedSetMultimap}.
328 *
329 * <p>Call this method only when the simpler methods
330 * {@link TreeMultimap#create()} and
331 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
332 *
333 * <p>Note: the multimap assumes complete ownership over of {@code map} and
334 * the sets returned by {@code factory}. Those objects should not be manually
335 * updated and they should not use soft, weak, or phantom references.
336 *
337 * @param map place to store the mapping from each key to its corresponding
338 * values
339 * @param factory supplier of new, empty sorted sets that will each hold
340 * all values for a given key
341 * @throws IllegalArgumentException if {@code map} is not empty
342 */
343 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
344 Map<K, Collection<V>> map,
345 final Supplier<? extends SortedSet<V>> factory) {
346 return new CustomSortedSetMultimap<K, V>(map, factory);
347 }
348
349 private static class CustomSortedSetMultimap<K, V>
350 extends AbstractSortedSetMultimap<K, V> {
351 transient Supplier<? extends SortedSet<V>> factory;
352 transient Comparator<? super V> valueComparator;
353
354 CustomSortedSetMultimap(Map<K, Collection<V>> map,
355 Supplier<? extends SortedSet<V>> factory) {
356 super(map);
357 this.factory = checkNotNull(factory);
358 valueComparator = factory.get().comparator();
359 }
360
361 @Override protected SortedSet<V> createCollection() {
362 return factory.get();
363 }
364
365 @Override public Comparator<? super V> valueComparator() {
366 return valueComparator;
367 }
368
369 /** @serialData the factory and the backing map */
370 @GwtIncompatible("java.io.ObjectOutputStream")
371 private void writeObject(ObjectOutputStream stream) throws IOException {
372 stream.defaultWriteObject();
373 stream.writeObject(factory);
374 stream.writeObject(backingMap());
375 }
376
377 @GwtIncompatible("java.io.ObjectInputStream")
378 @SuppressWarnings("unchecked") // reading data stored by writeObject
379 private void readObject(ObjectInputStream stream)
380 throws IOException, ClassNotFoundException {
381 stream.defaultReadObject();
382 factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
383 valueComparator = factory.get().comparator();
384 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
385 setMap(map);
386 }
387
388 @GwtIncompatible("not needed in emulated source")
389 private static final long serialVersionUID = 0;
390 }
391
392 /**
393 * Copies each key-value mapping in {@code source} into {@code dest}, with
394 * its key and value reversed.
395 *
396 * <p>If {@code source} is an {@link ImmutableMultimap}, consider using
397 * {@link ImmutableMultimap#inverse} instead.
398 *
399 * @param source any multimap
400 * @param dest the multimap to copy into; usually empty
401 * @return {@code dest}
402 */
403 public static <K, V, M extends Multimap<K, V>> M invertFrom(
404 Multimap<? extends V, ? extends K> source, M dest) {
405 checkNotNull(dest);
406 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
407 dest.put(entry.getValue(), entry.getKey());
408 }
409 return dest;
410 }
411
412 /**
413 * Returns a synchronized (thread-safe) multimap backed by the specified
414 * multimap. In order to guarantee serial access, it is critical that
415 * <b>all</b> access to the backing multimap is accomplished through the
416 * returned multimap.
417 *
418 * <p>It is imperative that the user manually synchronize on the returned
419 * multimap when accessing any of its collection views: <pre> {@code
420 *
421 * Multimap<K, V> m = Multimaps.synchronizedMultimap(
422 * HashMultimap.<K, V>create());
423 * ...
424 * Set<K> s = m.keySet(); // Needn't be in synchronized block
425 * ...
426 * synchronized (m) { // Synchronizing on m, not s!
427 * Iterator<K> i = s.iterator(); // Must be in synchronized block
428 * while (i.hasNext()) {
429 * foo(i.next());
430 * }
431 * }}</pre>
432 *
433 * Failure to follow this advice may result in non-deterministic behavior.
434 *
435 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
436 * {@link Multimap#replaceValues} methods return collections that aren't
437 * synchronized.
438 *
439 * <p>The returned multimap will be serializable if the specified multimap is
440 * serializable.
441 *
442 * @param multimap the multimap to be wrapped in a synchronized view
443 * @return a synchronized view of the specified multimap
444 */
445 public static <K, V> Multimap<K, V> synchronizedMultimap(
446 Multimap<K, V> multimap) {
447 return Synchronized.multimap(multimap, null);
448 }
449
450 /**
451 * Returns an unmodifiable view of the specified multimap. Query operations on
452 * the returned multimap "read through" to the specified multimap, and
453 * attempts to modify the returned multimap, either directly or through the
454 * multimap's views, result in an {@code UnsupportedOperationException}.
455 *
456 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
457 * {@link Multimap#replaceValues} methods return collections that are
458 * modifiable.
459 *
460 * <p>The returned multimap will be serializable if the specified multimap is
461 * serializable.
462 *
463 * @param delegate the multimap for which an unmodifiable view is to be
464 * returned
465 * @return an unmodifiable view of the specified multimap
466 */
467 public static <K, V> Multimap<K, V> unmodifiableMultimap(
468 Multimap<K, V> delegate) {
469 if (delegate instanceof UnmodifiableMultimap ||
470 delegate instanceof ImmutableMultimap) {
471 return delegate;
472 }
473 return new UnmodifiableMultimap<K, V>(delegate);
474 }
475
476 /**
477 * Simply returns its argument.
478 *
479 * @deprecated no need to use this
480 * @since 10.0
481 */
482 @Deprecated public static <K, V> Multimap<K, V> unmodifiableMultimap(
483 ImmutableMultimap<K, V> delegate) {
484 return checkNotNull(delegate);
485 }
486
487 private static class UnmodifiableMultimap<K, V>
488 extends ForwardingMultimap<K, V> implements Serializable {
489 final Multimap<K, V> delegate;
490 transient Collection<Entry<K, V>> entries;
491 transient Multiset<K> keys;
492 transient Set<K> keySet;
493 transient Collection<V> values;
494 transient Map<K, Collection<V>> map;
495
496 UnmodifiableMultimap(final Multimap<K, V> delegate) {
497 this.delegate = checkNotNull(delegate);
498 }
499
500 @Override protected Multimap<K, V> delegate() {
501 return delegate;
502 }
503
504 @Override public void clear() {
505 throw new UnsupportedOperationException();
506 }
507
508 @Override public Map<K, Collection<V>> asMap() {
509 Map<K, Collection<V>> result = map;
510 if (result == null) {
511 final Map<K, Collection<V>> unmodifiableMap
512 = Collections.unmodifiableMap(delegate.asMap());
513 map = result = new ForwardingMap<K, Collection<V>>() {
514 @Override protected Map<K, Collection<V>> delegate() {
515 return unmodifiableMap;
516 }
517
518 Set<Entry<K, Collection<V>>> entrySet;
519
520 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
521 Set<Entry<K, Collection<V>>> result = entrySet;
522 return (result == null)
523 ? entrySet
524 = unmodifiableAsMapEntries(unmodifiableMap.entrySet())
525 : result;
526 }
527
528 @Override public Collection<V> get(Object key) {
529 Collection<V> collection = unmodifiableMap.get(key);
530 return (collection == null)
531 ? null : unmodifiableValueCollection(collection);
532 }
533
534 Collection<Collection<V>> asMapValues;
535
536 @Override public Collection<Collection<V>> values() {
537 Collection<Collection<V>> result = asMapValues;
538 return (result == null)
539 ? asMapValues
540 = new UnmodifiableAsMapValues<V>(unmodifiableMap.values())
541 : result;
542 }
543
544 @Override public boolean containsValue(Object o) {
545 return values().contains(o);
546 }
547 };
548 }
549 return result;
550 }
551
552 @Override public Collection<Entry<K, V>> entries() {
553 Collection<Entry<K, V>> result = entries;
554 if (result == null) {
555 entries = result = unmodifiableEntries(delegate.entries());
556 }
557 return result;
558 }
559
560 @Override public Collection<V> get(K key) {
561 return unmodifiableValueCollection(delegate.get(key));
562 }
563
564 @Override public Multiset<K> keys() {
565 Multiset<K> result = keys;
566 if (result == null) {
567 keys = result = Multisets.unmodifiableMultiset(delegate.keys());
568 }
569 return result;
570 }
571
572 @Override public Set<K> keySet() {
573 Set<K> result = keySet;
574 if (result == null) {
575 keySet = result = Collections.unmodifiableSet(delegate.keySet());
576 }
577 return result;
578 }
579
580 @Override public boolean put(K key, V value) {
581 throw new UnsupportedOperationException();
582 }
583
584 @Override public boolean putAll(K key, Iterable<? extends V> values) {
585 throw new UnsupportedOperationException();
586 }
587
588 @Override
589 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
590 throw new UnsupportedOperationException();
591 }
592
593 @Override public boolean remove(Object key, Object value) {
594 throw new UnsupportedOperationException();
595 }
596
597 @Override public Collection<V> removeAll(Object key) {
598 throw new UnsupportedOperationException();
599 }
600
601 @Override public Collection<V> replaceValues(
602 K key, Iterable<? extends V> values) {
603 throw new UnsupportedOperationException();
604 }
605
606 @Override public Collection<V> values() {
607 Collection<V> result = values;
608 if (result == null) {
609 values = result = Collections.unmodifiableCollection(delegate.values());
610 }
611 return result;
612 }
613
614 private static final long serialVersionUID = 0;
615 }
616
617 private static class UnmodifiableAsMapValues<V>
618 extends ForwardingCollection<Collection<V>> {
619 final Collection<Collection<V>> delegate;
620 UnmodifiableAsMapValues(Collection<Collection<V>> delegate) {
621 this.delegate = Collections.unmodifiableCollection(delegate);
622 }
623 @Override protected Collection<Collection<V>> delegate() {
624 return delegate;
625 }
626 @Override public Iterator<Collection<V>> iterator() {
627 final Iterator<Collection<V>> iterator = delegate.iterator();
628 return new Iterator<Collection<V>>() {
629 @Override
630 public boolean hasNext() {
631 return iterator.hasNext();
632 }
633 @Override
634 public Collection<V> next() {
635 return unmodifiableValueCollection(iterator.next());
636 }
637 @Override
638 public void remove() {
639 throw new UnsupportedOperationException();
640 }
641 };
642 }
643 @Override public Object[] toArray() {
644 return standardToArray();
645 }
646 @Override public <T> T[] toArray(T[] array) {
647 return standardToArray(array);
648 }
649 @Override public boolean contains(Object o) {
650 return standardContains(o);
651 }
652 @Override public boolean containsAll(Collection<?> c) {
653 return standardContainsAll(c);
654 }
655 }
656
657 private static class UnmodifiableListMultimap<K, V>
658 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
659 UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
660 super(delegate);
661 }
662 @Override public ListMultimap<K, V> delegate() {
663 return (ListMultimap<K, V>) super.delegate();
664 }
665 @Override public List<V> get(K key) {
666 return Collections.unmodifiableList(delegate().get(key));
667 }
668 @Override public List<V> removeAll(Object key) {
669 throw new UnsupportedOperationException();
670 }
671 @Override public List<V> replaceValues(
672 K key, Iterable<? extends V> values) {
673 throw new UnsupportedOperationException();
674 }
675 private static final long serialVersionUID = 0;
676 }
677
678 private static class UnmodifiableSetMultimap<K, V>
679 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
680 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
681 super(delegate);
682 }
683 @Override public SetMultimap<K, V> delegate() {
684 return (SetMultimap<K, V>) super.delegate();
685 }
686 @Override public Set<V> get(K key) {
687 /*
688 * Note that this doesn't return a SortedSet when delegate is a
689 * SortedSetMultiset, unlike (SortedSet<V>) super.get().
690 */
691 return Collections.unmodifiableSet(delegate().get(key));
692 }
693 @Override public Set<Map.Entry<K, V>> entries() {
694 return Maps.unmodifiableEntrySet(delegate().entries());
695 }
696 @Override public Set<V> removeAll(Object key) {
697 throw new UnsupportedOperationException();
698 }
699 @Override public Set<V> replaceValues(
700 K key, Iterable<? extends V> values) {
701 throw new UnsupportedOperationException();
702 }
703 private static final long serialVersionUID = 0;
704 }
705
706 private static class UnmodifiableSortedSetMultimap<K, V>
707 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
708 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
709 super(delegate);
710 }
711 @Override public SortedSetMultimap<K, V> delegate() {
712 return (SortedSetMultimap<K, V>) super.delegate();
713 }
714 @Override public SortedSet<V> get(K key) {
715 return Collections.unmodifiableSortedSet(delegate().get(key));
716 }
717 @Override public SortedSet<V> removeAll(Object key) {
718 throw new UnsupportedOperationException();
719 }
720 @Override public SortedSet<V> replaceValues(
721 K key, Iterable<? extends V> values) {
722 throw new UnsupportedOperationException();
723 }
724 @Override
725 public Comparator<? super V> valueComparator() {
726 return delegate().valueComparator();
727 }
728 private static final long serialVersionUID = 0;
729 }
730
731 /**
732 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the
733 * specified multimap.
734 *
735 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
736 *
737 * <p>The returned multimap will be serializable if the specified multimap is
738 * serializable.
739 *
740 * @param multimap the multimap to be wrapped
741 * @return a synchronized view of the specified multimap
742 */
743 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
744 SetMultimap<K, V> multimap) {
745 return Synchronized.setMultimap(multimap, null);
746 }
747
748 /**
749 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query
750 * operations on the returned multimap "read through" to the specified
751 * multimap, and attempts to modify the returned multimap, either directly or
752 * through the multimap's views, result in an
753 * {@code UnsupportedOperationException}.
754 *
755 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
756 * {@link Multimap#replaceValues} methods return collections that are
757 * modifiable.
758 *
759 * <p>The returned multimap will be serializable if the specified multimap is
760 * serializable.
761 *
762 * @param delegate the multimap for which an unmodifiable view is to be
763 * returned
764 * @return an unmodifiable view of the specified multimap
765 */
766 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
767 SetMultimap<K, V> delegate) {
768 if (delegate instanceof UnmodifiableSetMultimap ||
769 delegate instanceof ImmutableSetMultimap) {
770 return delegate;
771 }
772 return new UnmodifiableSetMultimap<K, V>(delegate);
773 }
774
775 /**
776 * Simply returns its argument.
777 *
778 * @deprecated no need to use this
779 * @since 10.0
780 */
781 @Deprecated public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
782 ImmutableSetMultimap<K, V> delegate) {
783 return checkNotNull(delegate);
784 }
785
786 /**
787 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by
788 * the specified multimap.
789 *
790 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
791 *
792 * <p>The returned multimap will be serializable if the specified multimap is
793 * serializable.
794 *
795 * @param multimap the multimap to be wrapped
796 * @return a synchronized view of the specified multimap
797 */
798 public static <K, V> SortedSetMultimap<K, V>
799 synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
800 return Synchronized.sortedSetMultimap(multimap, null);
801 }
802
803 /**
804 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}.
805 * Query operations on the returned multimap "read through" to the specified
806 * multimap, and attempts to modify the returned multimap, either directly or
807 * through the multimap's views, result in an
808 * {@code UnsupportedOperationException}.
809 *
810 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
811 * {@link Multimap#replaceValues} methods return collections that are
812 * modifiable.
813 *
814 * <p>The returned multimap will be serializable if the specified multimap is
815 * serializable.
816 *
817 * @param delegate the multimap for which an unmodifiable view is to be
818 * returned
819 * @return an unmodifiable view of the specified multimap
820 */
821 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
822 SortedSetMultimap<K, V> delegate) {
823 if (delegate instanceof UnmodifiableSortedSetMultimap) {
824 return delegate;
825 }
826 return new UnmodifiableSortedSetMultimap<K, V>(delegate);
827 }
828
829 /**
830 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the
831 * specified multimap.
832 *
833 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
834 *
835 * @param multimap the multimap to be wrapped
836 * @return a synchronized view of the specified multimap
837 */
838 public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
839 ListMultimap<K, V> multimap) {
840 return Synchronized.listMultimap(multimap, null);
841 }
842
843 /**
844 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query
845 * operations on the returned multimap "read through" to the specified
846 * multimap, and attempts to modify the returned multimap, either directly or
847 * through the multimap's views, result in an
848 * {@code UnsupportedOperationException}.
849 *
850 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
851 * {@link Multimap#replaceValues} methods return collections that are
852 * modifiable.
853 *
854 * <p>The returned multimap will be serializable if the specified multimap is
855 * serializable.
856 *
857 * @param delegate the multimap for which an unmodifiable view is to be
858 * returned
859 * @return an unmodifiable view of the specified multimap
860 */
861 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
862 ListMultimap<K, V> delegate) {
863 if (delegate instanceof UnmodifiableListMultimap ||
864 delegate instanceof ImmutableListMultimap) {
865 return delegate;
866 }
867 return new UnmodifiableListMultimap<K, V>(delegate);
868 }
869
870 /**
871 * Simply returns its argument.
872 *
873 * @deprecated no need to use this
874 * @since 10.0
875 */
876 @Deprecated public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
877 ImmutableListMultimap<K, V> delegate) {
878 return checkNotNull(delegate);
879 }
880
881 /**
882 * Returns an unmodifiable view of the specified collection, preserving the
883 * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and
884 * {@code Collection}, in that order of preference.
885 *
886 * @param collection the collection for which to return an unmodifiable view
887 * @return an unmodifiable view of the collection
888 */
889 private static <V> Collection<V> unmodifiableValueCollection(
890 Collection<V> collection) {
891 if (collection instanceof SortedSet) {
892 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
893 } else if (collection instanceof Set) {
894 return Collections.unmodifiableSet((Set<V>) collection);
895 } else if (collection instanceof List) {
896 return Collections.unmodifiableList((List<V>) collection);
897 }
898 return Collections.unmodifiableCollection(collection);
899 }
900
901 /**
902 * Returns an unmodifiable view of the specified multimap {@code asMap} entry.
903 * The {@link Entry#setValue} operation throws an {@link
904 * UnsupportedOperationException}, and the collection returned by {@code
905 * getValue} is also an unmodifiable (type-preserving) view. This also has the
906 * side-effect of redefining equals to comply with the Map.Entry contract, and
907 * to avoid a possible nefarious implementation of equals.
908 *
909 * @param entry the entry for which to return an unmodifiable view
910 * @return an unmodifiable view of the entry
911 */
912 private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry(
913 final Map.Entry<K, Collection<V>> entry) {
914 checkNotNull(entry);
915 return new AbstractMapEntry<K, Collection<V>>() {
916 @Override public K getKey() {
917 return entry.getKey();
918 }
919
920 @Override public Collection<V> getValue() {
921 return unmodifiableValueCollection(entry.getValue());
922 }
923 };
924 }
925
926 /**
927 * Returns an unmodifiable view of the specified collection of entries. The
928 * {@link Entry#setValue} operation throws an {@link
929 * UnsupportedOperationException}. If the specified collection is a {@code
930 * Set}, the returned collection is also a {@code Set}.
931 *
932 * @param entries the entries for which to return an unmodifiable view
933 * @return an unmodifiable view of the entries
934 */
935 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
936 Collection<Entry<K, V>> entries) {
937 if (entries instanceof Set) {
938 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
939 }
940 return new Maps.UnmodifiableEntries<K, V>(
941 Collections.unmodifiableCollection(entries));
942 }
943
944 /**
945 * Returns an unmodifiable view of the specified set of {@code asMap} entries.
946 * The {@link Entry#setValue} operation throws an {@link
947 * UnsupportedOperationException}, as do any operations that attempt to modify
948 * the returned collection.
949 *
950 * @param asMapEntries the {@code asMap} entries for which to return an
951 * unmodifiable view
952 * @return an unmodifiable view of the collection entries
953 */
954 private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries(
955 Set<Entry<K, Collection<V>>> asMapEntries) {
956 return new UnmodifiableAsMapEntries<K, V>(
957 Collections.unmodifiableSet(asMapEntries));
958 }
959
960 /** @see Multimaps#unmodifiableAsMapEntries */
961 static class UnmodifiableAsMapEntries<K, V>
962 extends ForwardingSet<Entry<K, Collection<V>>> {
963 private final Set<Entry<K, Collection<V>>> delegate;
964 UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) {
965 this.delegate = delegate;
966 }
967
968 @Override protected Set<Entry<K, Collection<V>>> delegate() {
969 return delegate;
970 }
971
972 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
973 final Iterator<Entry<K, Collection<V>>> iterator = delegate.iterator();
974 return new ForwardingIterator<Entry<K, Collection<V>>>() {
975 @Override protected Iterator<Entry<K, Collection<V>>> delegate() {
976 return iterator;
977 }
978 @Override public Entry<K, Collection<V>> next() {
979 return unmodifiableAsMapEntry(iterator.next());
980 }
981 };
982 }
983
984 @Override public Object[] toArray() {
985 return standardToArray();
986 }
987
988 @Override public <T> T[] toArray(T[] array) {
989 return standardToArray(array);
990 }
991
992 @Override public boolean contains(Object o) {
993 return Maps.containsEntryImpl(delegate(), o);
994 }
995
996 @Override public boolean containsAll(Collection<?> c) {
997 return standardContainsAll(c);
998 }
999
1000 @Override public boolean equals(@Nullable Object object) {
1001 return standardEquals(object);
1002 }
1003 }
1004
1005 /**
1006 * Returns a multimap view of the specified map. The multimap is backed by the
1007 * map, so changes to the map are reflected in the multimap, and vice versa.
1008 * If the map is modified while an iteration over one of the multimap's
1009 * collection views is in progress (except through the iterator's own {@code
1010 * remove} operation, or through the {@code setValue} operation on a map entry
1011 * returned by the iterator), the results of the iteration are undefined.
1012 *
1013 * <p>The multimap supports mapping removal, which removes the corresponding
1014 * mapping from the map. It does not support any operations which might add
1015 * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}.
1016 *
1017 * <p>The returned multimap will be serializable if the specified map is
1018 * serializable.
1019 *
1020 * @param map the backing map for the returned multimap view
1021 */
1022 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
1023 return new MapMultimap<K, V>(map);
1024 }
1025
1026 /** @see Multimaps#forMap */
1027 private static class MapMultimap<K, V>
1028 implements SetMultimap<K, V>, Serializable {
1029 final Map<K, V> map;
1030 transient Map<K, Collection<V>> asMap;
1031
1032 MapMultimap(Map<K, V> map) {
1033 this.map = checkNotNull(map);
1034 }
1035
1036 @Override
1037 public int size() {
1038 return map.size();
1039 }
1040
1041 @Override
1042 public boolean isEmpty() {
1043 return map.isEmpty();
1044 }
1045
1046 @Override
1047 public boolean containsKey(Object key) {
1048 return map.containsKey(key);
1049 }
1050
1051 @Override
1052 public boolean containsValue(Object value) {
1053 return map.containsValue(value);
1054 }
1055
1056 @Override
1057 public boolean containsEntry(Object key, Object value) {
1058 return map.entrySet().contains(Maps.immutableEntry(key, value));
1059 }
1060
1061 @Override
1062 public Set<V> get(final K key) {
1063 return new AbstractSet<V>() {
1064 @Override public Iterator<V> iterator() {
1065 return new Iterator<V>() {
1066 int i;
1067
1068 @Override
1069 public boolean hasNext() {
1070 return (i == 0) && map.containsKey(key);
1071 }
1072
1073 @Override
1074 public V next() {
1075 if (!hasNext()) {
1076 throw new NoSuchElementException();
1077 }
1078 i++;
1079 return map.get(key);
1080 }
1081
1082 @Override
1083 public void remove() {
1084 checkState(i == 1);
1085 i = -1;
1086 map.remove(key);
1087 }
1088 };
1089 }
1090
1091 @Override public int size() {
1092 return map.containsKey(key) ? 1 : 0;
1093 }
1094 };
1095 }
1096
1097 @Override
1098 public boolean put(K key, V value) {
1099 throw new UnsupportedOperationException();
1100 }
1101
1102 @Override
1103 public boolean putAll(K key, Iterable<? extends V> values) {
1104 throw new UnsupportedOperationException();
1105 }
1106
1107 @Override
1108 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1109 throw new UnsupportedOperationException();
1110 }
1111
1112 @Override
1113 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1114 throw new UnsupportedOperationException();
1115 }
1116
1117 @Override
1118 public boolean remove(Object key, Object value) {
1119 return map.entrySet().remove(Maps.immutableEntry(key, value));
1120 }
1121
1122 @Override
1123 public Set<V> removeAll(Object key) {
1124 Set<V> values = new HashSet<V>(2);
1125 if (!map.containsKey(key)) {
1126 return values;
1127 }
1128 values.add(map.remove(key));
1129 return values;
1130 }
1131
1132 @Override
1133 public void clear() {
1134 map.clear();
1135 }
1136
1137 @Override
1138 public Set<K> keySet() {
1139 return map.keySet();
1140 }
1141
1142 @Override
1143 public Multiset<K> keys() {
1144 return Multisets.forSet(map.keySet());
1145 }
1146
1147 @Override
1148 public Collection<V> values() {
1149 return map.values();
1150 }
1151
1152 @Override
1153 public Set<Entry<K, V>> entries() {
1154 return map.entrySet();
1155 }
1156
1157 @Override
1158 public Map<K, Collection<V>> asMap() {
1159 Map<K, Collection<V>> result = asMap;
1160 if (result == null) {
1161 asMap = result = new AsMap();
1162 }
1163 return result;
1164 }
1165
1166 @Override public boolean equals(@Nullable Object object) {
1167 if (object == this) {
1168 return true;
1169 }
1170 if (object instanceof Multimap) {
1171 Multimap<?, ?> that = (Multimap<?, ?>) object;
1172 return this.size() == that.size() && asMap().equals(that.asMap());
1173 }
1174 return false;
1175 }
1176
1177 @Override public int hashCode() {
1178 return map.hashCode();
1179 }
1180
1181 private static final MapJoiner JOINER
1182 = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null");
1183
1184 @Override public String toString() {
1185 if (map.isEmpty()) {
1186 return "{}";
1187 }
1188 StringBuilder builder
1189 = Collections2.newStringBuilderForCollection(map.size()).append('{');
1190 JOINER.appendTo(builder, map);
1191 return builder.append("]}").toString();
1192 }
1193
1194 /** @see MapMultimap#asMap */
1195 class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
1196 @Override public int size() {
1197 return map.size();
1198 }
1199
1200 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
1201 return new Iterator<Entry<K, Collection<V>>>() {
1202 final Iterator<K> keys = map.keySet().iterator();
1203
1204 @Override
1205 public boolean hasNext() {
1206 return keys.hasNext();
1207 }
1208 @Override
1209 public Entry<K, Collection<V>> next() {
1210 final K key = keys.next();
1211 return new AbstractMapEntry<K, Collection<V>>() {
1212 @Override public K getKey() {
1213 return key;
1214 }
1215 @Override public Collection<V> getValue() {
1216 return get(key);
1217 }
1218 };
1219 }
1220 @Override
1221 public void remove() {
1222 keys.remove();
1223 }
1224 };
1225 }
1226
1227 @Override public boolean contains(Object o) {
1228 if (!(o instanceof Entry)) {
1229 return false;
1230 }
1231 Entry<?, ?> entry = (Entry<?, ?>) o;
1232 if (!(entry.getValue() instanceof Set)) {
1233 return false;
1234 }
1235 Set<?> set = (Set<?>) entry.getValue();
1236 return (set.size() == 1)
1237 && containsEntry(entry.getKey(), set.iterator().next());
1238 }
1239
1240 @Override public boolean remove(Object o) {
1241 if (!(o instanceof Entry)) {
1242 return false;
1243 }
1244 Entry<?, ?> entry = (Entry<?, ?>) o;
1245 if (!(entry.getValue() instanceof Set)) {
1246 return false;
1247 }
1248 Set<?> set = (Set<?>) entry.getValue();
1249 return (set.size() == 1)
1250 && map.entrySet().remove(
1251 Maps.immutableEntry(entry.getKey(), set.iterator().next()));
1252 }
1253 }
1254
1255 /** @see MapMultimap#asMap */
1256 class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> {
1257 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
1258 return new AsMapEntries();
1259 }
1260
1261 // The following methods are included for performance.
1262
1263 @Override public boolean containsKey(Object key) {
1264 return map.containsKey(key);
1265 }
1266
1267 @SuppressWarnings("unchecked")
1268 @Override public Collection<V> get(Object key) {
1269 Collection<V> collection = MapMultimap.this.get((K) key);
1270 return collection.isEmpty() ? null : collection;
1271 }
1272
1273 @Override public Collection<V> remove(Object key) {
1274 Collection<V> collection = removeAll(key);
1275 return collection.isEmpty() ? null : collection;
1276 }
1277 }
1278 private static final long serialVersionUID = 7845222491160860175L;
1279 }
1280
1281 /**
1282 * Returns a view of a multimap where each value is transformed by a function.
1283 * All other properties of the multimap, such as iteration order, are left
1284 * intact. For example, the code: <pre> {@code
1285 *
1286 * Multimap<String, Integer> multimap =
1287 * ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
1288 * Function<Integer, String> square = new Function<Integer, String>() {
1289 * public String apply(Integer in) {
1290 * return Integer.toString(in * in);
1291 * }
1292 * };
1293 * Multimap<String, String> transformed =
1294 * Multimaps.transformValues(multimap, square);
1295 * System.out.println(transformed);}</pre>
1296 *
1297 * ... prints {@code {a=[4, 16], b=[9, 9], c=[6]}}.
1298 *
1299 * <p>Changes in the underlying multimap are reflected in this view.
1300 * Conversely, this view supports removal operations, and these are reflected
1301 * in the underlying multimap.
1302 *
1303 * <p>It's acceptable for the underlying multimap to contain null keys, and
1304 * even null values provided that the function is capable of accepting null
1305 * input. The transformed multimap might contain null values, if the function
1306 * sometimes gives a null result.
1307 *
1308 * <p>The returned multimap is not thread-safe or serializable, even if the
1309 * underlying multimap is. The {@code equals} and {@code hashCode} methods
1310 * of the returned multimap are meaningless, since there is not a definition
1311 * of {@code equals} or {@code hashCode} for general collections, and
1312 * {@code get()} will return a general {@code Collection} as opposed to a
1313 * {@code List} or a {@code Set}.
1314 *
1315 * <p>The function is applied lazily, invoked when needed. This is necessary
1316 * for the returned multimap to be a view, but it means that the function will
1317 * be applied many times for bulk operations like
1318 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1319 * perform well, {@code function} should be fast. To avoid lazy evaluation
1320 * when the returned multimap doesn't need to be a view, copy the returned
1321 * multimap into a new multimap of your choosing.
1322 *
1323 * @since 7.0
1324 */
1325 @Beta
1326 public static <K, V1, V2> Multimap<K, V2> transformValues(
1327 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1328 checkNotNull(function);
1329 EntryTransformer<K, V1, V2> transformer =
1330 new EntryTransformer<K, V1, V2>() {
1331 @Override
1332 public V2 transformEntry(K key, V1 value) {
1333 return function.apply(value);
1334 }
1335 };
1336 return transformEntries(fromMultimap, transformer);
1337 }
1338
1339 /**
1340 * Returns a view of a multimap whose values are derived from the original
1341 * multimap's entries. In contrast to {@link #transformValues}, this method's
1342 * entry-transformation logic may depend on the key as well as the value.
1343 *
1344 * <p>All other properties of the transformed multimap, such as iteration
1345 * order, are left intact. For example, the code: <pre> {@code
1346 *
1347 * SetMultimap<String, Integer> multimap =
1348 * ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
1349 * EntryTransformer<String, Integer, String> transformer =
1350 * new EntryTransformer<String, Integer, String>() {
1351 * public String transformEntry(String key, Integer value) {
1352 * return (value >= 0) ? key : "no" + key;
1353 * }
1354 * };
1355 * Multimap<String, String> transformed =
1356 * Multimaps.transformEntries(multimap, transformer);
1357 * System.out.println(transformed);}</pre>
1358 *
1359 * ... prints {@code {a=[a, a], b=[nob]}}.
1360 *
1361 * <p>Changes in the underlying multimap are reflected in this view.
1362 * Conversely, this view supports removal operations, and these are reflected
1363 * in the underlying multimap.
1364 *
1365 * <p>It's acceptable for the underlying multimap to contain null keys and
1366 * null values provided that the transformer is capable of accepting null
1367 * inputs. The transformed multimap might contain null values if the
1368 * transformer sometimes gives a null result.
1369 *
1370 * <p>The returned multimap is not thread-safe or serializable, even if the
1371 * underlying multimap is. The {@code equals} and {@code hashCode} methods
1372 * of the returned multimap are meaningless, since there is not a definition
1373 * of {@code equals} or {@code hashCode} for general collections, and
1374 * {@code get()} will return a general {@code Collection} as opposed to a
1375 * {@code List} or a {@code Set}.
1376 *
1377 * <p>The transformer is applied lazily, invoked when needed. This is
1378 * necessary for the returned multimap to be a view, but it means that the
1379 * transformer will be applied many times for bulk operations like {@link
1380 * Multimap#containsValue} and {@link Object#toString}. For this to perform
1381 * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1382 * returned multimap doesn't need to be a view, copy the returned multimap
1383 * into a new multimap of your choosing.
1384 *
1385 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1386 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1387 * that {@code k2} is also of type {@code K}. Using an {@code
1388 * EntryTransformer} key type for which this may not hold, such as {@code
1389 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1390 * the transformed multimap.
1391 *
1392 * @since 7.0
1393 */
1394 @Beta
1395 public static <K, V1, V2> Multimap<K, V2> transformEntries(
1396 Multimap<K, V1> fromMap,
1397 EntryTransformer<? super K, ? super V1, V2> transformer) {
1398 return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer);
1399 }
1400
1401 private static class TransformedEntriesMultimap<K, V1, V2>
1402 implements Multimap<K, V2> {
1403 final Multimap<K, V1> fromMultimap;
1404 final EntryTransformer<? super K, ? super V1, V2> transformer;
1405
1406 TransformedEntriesMultimap(Multimap<K, V1> fromMultimap,
1407 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1408 this.fromMultimap = checkNotNull(fromMultimap);
1409 this.transformer = checkNotNull(transformer);
1410 }
1411
1412 Collection<V2> transform(final K key, Collection<V1> values) {
1413 return Collections2.transform(values, new Function<V1, V2>() {
1414 @Override public V2 apply(V1 value) {
1415 return transformer.transformEntry(key, value);
1416 }
1417 });
1418 }
1419
1420 private transient Map<K, Collection<V2>> asMap;
1421
1422 @Override public Map<K, Collection<V2>> asMap() {
1423 if (asMap == null) {
1424 Map<K, Collection<V2>> aM = Maps.transformEntries(fromMultimap.asMap(),
1425 new EntryTransformer<K, Collection<V1>, Collection<V2>>() {
1426
1427 @Override public Collection<V2> transformEntry(
1428 K key, Collection<V1> value) {
1429 return transform(key, value);
1430 }
1431 });
1432 asMap = aM;
1433 return aM;
1434 }
1435 return asMap;
1436 }
1437
1438 @Override public void clear() {
1439 fromMultimap.clear();
1440 }
1441
1442 @SuppressWarnings("unchecked")
1443 @Override public boolean containsEntry(Object key, Object value) {
1444 Collection<V2> values = get((K) key);
1445 return values.contains(value);
1446 }
1447
1448 @Override public boolean containsKey(Object key) {
1449 return fromMultimap.containsKey(key);
1450 }
1451
1452 @Override public boolean containsValue(Object value) {
1453 return values().contains(value);
1454 }
1455
1456 private transient Collection<Entry<K, V2>> entries;
1457
1458 @Override public Collection<Entry<K, V2>> entries() {
1459 if (entries == null) {
1460 Collection<Entry<K, V2>> es = new TransformedEntries(transformer);
1461 entries = es;
1462 return es;
1463 }
1464 return entries;
1465 }
1466
1467 private class TransformedEntries
1468 extends TransformedCollection<Entry<K, V1>, Entry<K, V2>> {
1469
1470 TransformedEntries(
1471 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1472 super(fromMultimap.entries(),
1473 new Function<Entry<K, V1>, Entry<K, V2>>() {
1474 @Override public Entry<K, V2> apply(final Entry<K, V1> entry) {
1475 return new AbstractMapEntry<K, V2>() {
1476
1477 @Override public K getKey() {
1478 return entry.getKey();
1479 }
1480
1481 @Override public V2 getValue() {
1482 return transformer.transformEntry(
1483 entry.getKey(), entry.getValue());
1484 }
1485 };
1486 }
1487 });
1488 }
1489
1490 @Override public boolean contains(Object o) {
1491 if (o instanceof Entry) {
1492 Entry<?, ?> entry = (Entry<?, ?>) o;
1493 return containsEntry(entry.getKey(), entry.getValue());
1494 }
1495 return false;
1496 }
1497
1498 @SuppressWarnings("unchecked")
1499 @Override public boolean remove(Object o) {
1500 if (o instanceof Entry) {
1501 Entry<?, ?> entry = (Entry<?, ?>) o;
1502 Collection<V2> values = get((K) entry.getKey());
1503 return values.remove(entry.getValue());
1504 }
1505 return false;
1506 }
1507
1508 }
1509
1510 @Override public Collection<V2> get(final K key) {
1511 return transform(key, fromMultimap.get(key));
1512 }
1513
1514 @Override public boolean isEmpty() {
1515 return fromMultimap.isEmpty();
1516 }
1517
1518 @Override public Set<K> keySet() {
1519 return fromMultimap.keySet();
1520 }
1521
1522 @Override public Multiset<K> keys() {
1523 return fromMultimap.keys();
1524 }
1525
1526 @Override public boolean put(K key, V2 value) {
1527 throw new UnsupportedOperationException();
1528 }
1529
1530 @Override public boolean putAll(K key, Iterable<? extends V2> values) {
1531 throw new UnsupportedOperationException();
1532 }
1533
1534 @Override public boolean putAll(
1535 Multimap<? extends K, ? extends V2> multimap) {
1536 throw new UnsupportedOperationException();
1537 }
1538
1539 @SuppressWarnings("unchecked")
1540 @Override public boolean remove(Object key, Object value) {
1541 return get((K) key).remove(value);
1542 }
1543
1544 @SuppressWarnings("unchecked")
1545 @Override public Collection<V2> removeAll(Object key) {
1546 return transform((K) key, fromMultimap.removeAll(key));
1547 }
1548
1549 @Override public Collection<V2> replaceValues(
1550 K key, Iterable<? extends V2> values) {
1551 throw new UnsupportedOperationException();
1552 }
1553
1554 @Override public int size() {
1555 return fromMultimap.size();
1556 }
1557
1558 private transient Collection<V2> values;
1559
1560 @Override public Collection<V2> values() {
1561 if (values == null) {
1562 Collection<V2> vs = Collections2.transform(
1563 fromMultimap.entries(), new Function<Entry<K, V1>, V2>() {
1564
1565 @Override public V2 apply(Entry<K, V1> entry) {
1566 return transformer.transformEntry(
1567 entry.getKey(), entry.getValue());
1568 }
1569 });
1570 values = vs;
1571 return vs;
1572 }
1573 return values;
1574 }
1575
1576 @Override public boolean equals(Object obj) {
1577 if (obj instanceof Multimap) {
1578 Multimap<?, ?> other = (Multimap<?, ?>) obj;
1579 return asMap().equals(other.asMap());
1580 }
1581 return false;
1582 }
1583
1584 @Override public int hashCode() {
1585 return asMap().hashCode();
1586 }
1587
1588 @Override public String toString() {
1589 return asMap().toString();
1590 }
1591 }
1592
1593 /**
1594 * Returns a view of a {@code ListMultimap} where each value is transformed by
1595 * a function. All other properties of the multimap, such as iteration order,
1596 * are left intact. For example, the code: <pre> {@code
1597 *
1598 * ListMultimap<String, Integer> multimap
1599 * = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
1600 * Function<Integer, Double> sqrt =
1601 * new Function<Integer, Double>() {
1602 * public Double apply(Integer in) {
1603 * return Math.sqrt((int) in);
1604 * }
1605 * };
1606 * ListMultimap<String, Double> transformed = Multimaps.transformValues(map,
1607 * sqrt);
1608 * System.out.println(transformed);}</pre>
1609 *
1610 * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}.
1611 *
1612 * <p>Changes in the underlying multimap are reflected in this view.
1613 * Conversely, this view supports removal operations, and these are reflected
1614 * in the underlying multimap.
1615 *
1616 * <p>It's acceptable for the underlying multimap to contain null keys, and
1617 * even null values provided that the function is capable of accepting null
1618 * input. The transformed multimap might contain null values, if the function
1619 * sometimes gives a null result.
1620 *
1621 * <p>The returned multimap is not thread-safe or serializable, even if the
1622 * underlying multimap is.
1623 *
1624 * <p>The function is applied lazily, invoked when needed. This is necessary
1625 * for the returned multimap to be a view, but it means that the function will
1626 * be applied many times for bulk operations like
1627 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1628 * perform well, {@code function} should be fast. To avoid lazy evaluation
1629 * when the returned multimap doesn't need to be a view, copy the returned
1630 * multimap into a new multimap of your choosing.
1631 *
1632 * @since 7.0
1633 */
1634 @Beta
1635 public static <K, V1, V2> ListMultimap<K, V2> transformValues(
1636 ListMultimap<K, V1> fromMultimap,
1637 final Function<? super V1, V2> function) {
1638 checkNotNull(function);
1639 EntryTransformer<K, V1, V2> transformer =
1640 new EntryTransformer<K, V1, V2>() {
1641 @Override
1642 public V2 transformEntry(K key, V1 value) {
1643 return function.apply(value);
1644 }
1645 };
1646 return transformEntries(fromMultimap, transformer);
1647 }
1648
1649 /**
1650 * Returns a view of a {@code ListMultimap} whose values are derived from the
1651 * original multimap's entries. In contrast to
1652 * {@link #transformValues(ListMultimap, Function)}, this method's
1653 * entry-transformation logic may depend on the key as well as the value.
1654 *
1655 * <p>All other properties of the transformed multimap, such as iteration
1656 * order, are left intact. For example, the code: <pre> {@code
1657 *
1658 * Multimap<String, Integer> multimap =
1659 * ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
1660 * EntryTransformer<String, Integer, String> transformer =
1661 * new EntryTransformer<String, Integer, String>() {
1662 * public String transformEntry(String key, Integer value) {
1663 * return key + value;
1664 * }
1665 * };
1666 * Multimap<String, String> transformed =
1667 * Multimaps.transformEntries(multimap, transformer);
1668 * System.out.println(transformed);}</pre>
1669 *
1670 * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}.
1671 *
1672 * <p>Changes in the underlying multimap are reflected in this view.
1673 * Conversely, this view supports removal operations, and these are reflected
1674 * in the underlying multimap.
1675 *
1676 * <p>It's acceptable for the underlying multimap to contain null keys and
1677 * null values provided that the transformer is capable of accepting null
1678 * inputs. The transformed multimap might contain null values if the
1679 * transformer sometimes gives a null result.
1680 *
1681 * <p>The returned multimap is not thread-safe or serializable, even if the
1682 * underlying multimap is.
1683 *
1684 * <p>The transformer is applied lazily, invoked when needed. This is
1685 * necessary for the returned multimap to be a view, but it means that the
1686 * transformer will be applied many times for bulk operations like {@link
1687 * Multimap#containsValue} and {@link Object#toString}. For this to perform
1688 * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1689 * returned multimap doesn't need to be a view, copy the returned multimap
1690 * into a new multimap of your choosing.
1691 *
1692 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1693 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1694 * that {@code k2} is also of type {@code K}. Using an {@code
1695 * EntryTransformer} key type for which this may not hold, such as {@code
1696 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1697 * the transformed multimap.
1698 *
1699 * @since 7.0
1700 */
1701 @Beta
1702 public static <K, V1, V2> ListMultimap<K, V2> transformEntries(
1703 ListMultimap<K, V1> fromMap,
1704 EntryTransformer<? super K, ? super V1, V2> transformer) {
1705 return new TransformedEntriesListMultimap<K, V1, V2>(fromMap, transformer);
1706 }
1707
1708 private static final class TransformedEntriesListMultimap<K, V1, V2>
1709 extends TransformedEntriesMultimap<K, V1, V2>
1710 implements ListMultimap<K, V2> {
1711
1712 TransformedEntriesListMultimap(ListMultimap<K, V1> fromMultimap,
1713 EntryTransformer<? super K, ? super V1, V2> transformer) {
1714 super(fromMultimap, transformer);
1715 }
1716
1717 @Override List<V2> transform(final K key, Collection<V1> values) {
1718 return Lists.transform((List<V1>) values, new Function<V1, V2>() {
1719 @Override public V2 apply(V1 value) {
1720 return transformer.transformEntry(key, value);
1721 }
1722 });
1723 }
1724
1725 @Override public List<V2> get(K key) {
1726 return transform(key, fromMultimap.get(key));
1727 }
1728
1729 @SuppressWarnings("unchecked")
1730 @Override public List<V2> removeAll(Object key) {
1731 return transform((K) key, fromMultimap.removeAll(key));
1732 }
1733
1734 @Override public List<V2> replaceValues(
1735 K key, Iterable<? extends V2> values) {
1736 throw new UnsupportedOperationException();
1737 }
1738 }
1739
1740 /**
1741 * Creates an index {@code ImmutableListMultimap} that contains the results of
1742 * applying a specified function to each item in an {@code Iterable} of
1743 * values. Each value will be stored as a value in the resulting multimap,
1744 * yielding a multimap with the same size as the input iterable. The key used
1745 * to store that value in the multimap will be the result of calling the
1746 * function on that value. The resulting multimap is created as an immutable
1747 * snapshot. In the returned multimap, keys appear in the order they are first
1748 * encountered, and the values corresponding to each key appear in the same
1749 * order as they are encountered.
1750 *
1751 * <p>For example, <pre> {@code
1752 *
1753 * List<String> badGuys =
1754 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1755 * Function<String, Integer> stringLengthFunction = ...;
1756 * Multimap<Integer, String> index =
1757 * Multimaps.index(badGuys, stringLengthFunction);
1758 * System.out.println(index);}</pre>
1759 *
1760 * prints <pre> {@code
1761 *
1762 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
1763 *
1764 * The returned multimap is serializable if its keys and values are all
1765 * serializable.
1766 *
1767 * @param values the values to use when constructing the {@code
1768 * ImmutableListMultimap}
1769 * @param keyFunction the function used to produce the key for each value
1770 * @return {@code ImmutableListMultimap} mapping the result of evaluating the
1771 * function {@code keyFunction} on each value in the input collection to
1772 * that value
1773 * @throws NullPointerException if any of the following cases is true:
1774 * <ul>
1775 * <li>{@code values} is null
1776 * <li>{@code keyFunction} is null
1777 * <li>An element in {@code values} is null
1778 * <li>{@code keyFunction} returns {@code null} for any element of {@code
1779 * values}
1780 * </ul>
1781 */
1782 public static <K, V> ImmutableListMultimap<K, V> index(
1783 Iterable<V> values, Function<? super V, K> keyFunction) {
1784 return index(values.iterator(), keyFunction);
1785 }
1786
1787 /**
1788 * <b>Deprecated.</b>
1789 *
1790 * @since 10.0
1791 * @deprecated use {@link #index(Iterator, Function)} by casting {@code
1792 * values} to {@code Iterator<V>}, or better yet, by implementing only
1793 * {@code Iterator} and not {@code Iterable}. <b>This method is scheduled
1794 * for deletion in March 2012.</b>
1795 */
1796 @Beta
1797 @Deprecated
1798 public static <K, V, I extends Object & Iterable<V> & Iterator<V>>
1799 ImmutableListMultimap<K, V> index(
1800 I values, Function<? super V, K> keyFunction) {
1801 Iterable<V> valuesIterable = checkNotNull(values);
1802 return index(valuesIterable, keyFunction);
1803 }
1804
1805 /**
1806 * Creates an index {@code ImmutableListMultimap} that contains the results of
1807 * applying a specified function to each item in an {@code Iterator} of
1808 * values. Each value will be stored as a value in the resulting multimap,
1809 * yielding a multimap with the same size as the input iterator. The key used
1810 * to store that value in the multimap will be the result of calling the
1811 * function on that value. The resulting multimap is created as an immutable
1812 * snapshot. In the returned multimap, keys appear in the order they are first
1813 * encountered, and the values corresponding to each key appear in the same
1814 * order as they are encountered.
1815 *
1816 * <p>For example, <pre> {@code
1817 *
1818 * List<String> badGuys =
1819 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1820 * Function<String, Integer> stringLengthFunction = ...;
1821 * Multimap<Integer, String> index =
1822 * Multimaps.index(badGuys.iterator(), stringLengthFunction);
1823 * System.out.println(index);}</pre>
1824 *
1825 * prints <pre> {@code
1826 *
1827 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
1828 *
1829 * The returned multimap is serializable if its keys and values are all
1830 * serializable.
1831 *
1832 * @param values the values to use when constructing the {@code
1833 * ImmutableListMultimap}
1834 * @param keyFunction the function used to produce the key for each value
1835 * @return {@code ImmutableListMultimap} mapping the result of evaluating the
1836 * function {@code keyFunction} on each value in the input collection to
1837 * that value
1838 * @throws NullPointerException if any of the following cases is true:
1839 * <ul>
1840 * <li>{@code values} is null
1841 * <li>{@code keyFunction} is null
1842 * <li>An element in {@code values} is null
1843 * <li>{@code keyFunction} returns {@code null} for any element of {@code
1844 * values}
1845 * </ul>
1846 * @since 10.0
1847 */
1848 public static <K, V> ImmutableListMultimap<K, V> index(
1849 Iterator<V> values, Function<? super V, K> keyFunction) {
1850 checkNotNull(keyFunction);
1851 ImmutableListMultimap.Builder<K, V> builder
1852 = ImmutableListMultimap.builder();
1853 while (values.hasNext()) {
1854 V value = values.next();
1855 checkNotNull(value, values);
1856 builder.put(keyFunction.apply(value), value);
1857 }
1858 return builder.build();
1859 }
1860
1861 static abstract class Keys<K, V> extends AbstractMultiset<K> {
1862 abstract Multimap<K, V> multimap();
1863
1864 @Override Iterator<Multiset.Entry<K>> entryIterator() {
1865 final Iterator<Map.Entry<K, Collection<V>>> backingIterator =
1866 multimap().asMap().entrySet().iterator();
1867 return new Iterator<Multiset.Entry<K>>() {
1868 @Override public boolean hasNext() {
1869 return backingIterator.hasNext();
1870 }
1871
1872 @Override public Multiset.Entry<K> next() {
1873 final Map.Entry<K, Collection<V>> backingEntry =
1874 backingIterator.next();
1875 return new Multisets.AbstractEntry<K>() {
1876 @Override public K getElement() {
1877 return backingEntry.getKey();
1878 }
1879
1880 @Override public int getCount() {
1881 return backingEntry.getValue().size();
1882 }
1883 };
1884 }
1885
1886 @Override public void remove() {
1887 backingIterator.remove();
1888 }
1889 };
1890 }
1891
1892 @Override int distinctElements() {
1893 return multimap().asMap().size();
1894 }
1895
1896 @Override Set<Multiset.Entry<K>> createEntrySet() {
1897 return new KeysEntrySet();
1898 }
1899
1900 class KeysEntrySet extends Multisets.EntrySet<K> {
1901 @Override Multiset<K> multiset() {
1902 return Keys.this;
1903 }
1904
1905 @Override public Iterator<Multiset.Entry<K>> iterator() {
1906 return entryIterator();
1907 }
1908
1909 @Override public int size() {
1910 return distinctElements();
1911 }
1912
1913 @Override public boolean isEmpty() {
1914 return multimap().isEmpty();
1915 }
1916
1917 @Override public boolean contains(@Nullable Object o) {
1918 if (o instanceof Multiset.Entry<?>) {
1919 Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1920 Collection<V> collection = multimap().asMap().get(entry.getElement());
1921 return collection != null && collection.size() == entry.getCount();
1922 }
1923 return false;
1924 }
1925
1926 @Override public boolean remove(@Nullable Object o) {
1927 if (o instanceof Multiset.Entry<?>) {
1928 Multiset.Entry<?> entry = (Multiset.Entry<?>) o;
1929 Collection<V> collection = multimap().asMap().get(entry.getElement());
1930 if (collection != null && collection.size() == entry.getCount()) {
1931 collection.clear();
1932 return true;
1933 }
1934 }
1935 return false;
1936 }
1937 }
1938
1939 @Override public boolean contains(@Nullable Object element) {
1940 return multimap().containsKey(element);
1941 }
1942
1943 @Override public Iterator<K> iterator() {
1944 return Iterators.transform(multimap().entries().iterator(),
1945 new Function<Map.Entry<K, V>, K>() {
1946 @Override public K apply(Map.Entry<K, V> entry) {
1947 return entry.getKey();
1948 }
1949 });
1950 }
1951
1952 @Override public int count(@Nullable Object element) {
1953 try {
1954 if (multimap().containsKey(element)) {
1955 Collection<V> values = multimap().asMap().get(element);
1956 return (values == null) ? 0 : values.size();
1957 }
1958 return 0;
1959 } catch (ClassCastException e) {
1960 return 0;
1961 } catch (NullPointerException e) {
1962 return 0;
1963 }
1964 }
1965
1966 @Override public int remove(@Nullable Object element, int occurrences) {
1967 checkArgument(occurrences >= 0);
1968 if (occurrences == 0) {
1969 return count(element);
1970 }
1971
1972 Collection<V> values;
1973 try {
1974 values = multimap().asMap().get(element);
1975 } catch (ClassCastException e) {
1976 return 0;
1977 } catch (NullPointerException e) {
1978 return 0;
1979 }
1980
1981 if (values == null) {
1982 return 0;
1983 }
1984
1985 int oldCount = values.size();
1986 if (occurrences >= oldCount) {
1987 values.clear();
1988 } else {
1989 Iterator<V> iterator = values.iterator();
1990 for (int i = 0; i < occurrences; i++) {
1991 iterator.next();
1992 iterator.remove();
1993 }
1994 }
1995 return oldCount;
1996 }
1997
1998 @Override public void clear() {
1999 multimap().clear();
2000 }
2001
2002 @Override public Set<K> elementSet() {
2003 return multimap().keySet();
2004 }
2005 }
2006
2007 static abstract class Values<K, V> extends AbstractCollection<V> {
2008 abstract Multimap<K, V> multimap();
2009
2010 @Override public Iterator<V> iterator() {
2011 final Iterator<Map.Entry<K, V>> backingIterator =
2012 multimap().entries().iterator();
2013 return new Iterator<V>() {
2014 @Override public boolean hasNext() {
2015 return backingIterator.hasNext();
2016 }
2017
2018 @Override public V next() {
2019 return backingIterator.next().getValue();
2020 }
2021
2022 @Override public void remove() {
2023 backingIterator.remove();
2024 }
2025 };
2026 }
2027
2028 @Override public int size() {
2029 return multimap().size();
2030 }
2031
2032 @Override public boolean contains(@Nullable Object o) {
2033 return multimap().containsValue(o);
2034 }
2035
2036 @Override public void clear() {
2037 multimap().clear();
2038 }
2039 }
2040
2041 /**
2042 * A skeleton implementation of {@link Multimap#entries()}.
2043 */
2044 static abstract class Entries<K, V> extends
2045 AbstractCollection<Map.Entry<K, V>> {
2046 abstract Multimap<K, V> multimap();
2047
2048 @Override public int size() {
2049 return multimap().size();
2050 }
2051
2052 @Override public boolean contains(@Nullable Object o) {
2053 if (o instanceof Map.Entry<?, ?>) {
2054 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
2055 return multimap().containsEntry(entry.getKey(), entry.getValue());
2056 }
2057 return false;
2058 }
2059
2060 @Override public boolean remove(@Nullable Object o) {
2061 if (o instanceof Map.Entry<?, ?>) {
2062 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
2063 return multimap().remove(entry.getKey(), entry.getValue());
2064 }
2065 return false;
2066 }
2067
2068 @Override public void clear() {
2069 multimap().clear();
2070 }
2071 }
2072
2073 /**
2074 * A skeleton implementation of {@link SetMultimap#entries()}.
2075 */
2076 static abstract class EntrySet<K, V> extends Entries<K, V> implements
2077 Set<Map.Entry<K, V>> {
2078 @Override public int hashCode() {
2079 return Sets.hashCodeImpl(this);
2080 }
2081
2082 @Override public boolean equals(@Nullable Object obj) {
2083 return Sets.equalsImpl(this, obj);
2084 }
2085 }
2086
2087 /**
2088 * A skeleton implementation of {@link Multimap#asMap()}.
2089 */
2090 static abstract class AsMap<K, V> extends
2091 Maps.ImprovedAbstractMap<K, Collection<V>> {
2092 abstract Multimap<K, V> multimap();
2093
2094 @Override public abstract int size();
2095
2096 abstract Iterator<Entry<K, Collection<V>>> entryIterator();
2097
2098 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
2099 return new EntrySet();
2100 }
2101
2102 void removeValuesForKey(Object key){
2103 multimap().removeAll(key);
2104 }
2105
2106 class EntrySet extends Maps.EntrySet<K, Collection<V>> {
2107 @Override Map<K, Collection<V>> map() {
2108 return AsMap.this;
2109 }
2110
2111 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
2112 return entryIterator();
2113 }
2114
2115 @Override public boolean remove(Object o) {
2116 if (!contains(o)) {
2117 return false;
2118 }
2119 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
2120 removeValuesForKey(entry.getKey());
2121 return true;
2122 }
2123 }
2124
2125 @SuppressWarnings("unchecked")
2126 @Override public Collection<V> get(Object key) {
2127 return containsKey(key) ? multimap().get((K) key) : null;
2128 }
2129
2130 @Override public Collection<V> remove(Object key) {
2131 return containsKey(key) ? multimap().removeAll(key) : null;
2132 }
2133
2134 @Override public Set<K> keySet() {
2135 return multimap().keySet();
2136 }
2137
2138 @Override public boolean isEmpty() {
2139 return multimap().isEmpty();
2140 }
2141
2142 @Override public boolean containsKey(Object key) {
2143 return multimap().containsKey(key);
2144 }
2145
2146 @Override public void clear() {
2147 multimap().clear();
2148 }
2149 }
2150
2151 /**
2152 * Returns a multimap containing the mappings in {@code unfiltered} whose keys
2153 * satisfy a predicate. The returned multimap is a live view of
2154 * {@code unfiltered}; changes to one affect the other.
2155 *
2156 * <p>The resulting multimap's views have iterators that don't support
2157 * {@code remove()}, but all other methods are supported by the multimap and
2158 * its views. When adding a key that doesn't satisfy the predicate, the
2159 * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods
2160 * throw an {@link IllegalArgumentException}.
2161 *
2162 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2163 * the filtered multimap or its views, only mappings whose keys satisfy the
2164 * filter will be removed from the underlying multimap.
2165 *
2166 * <p>The returned multimap isn't threadsafe or serializable, even if
2167 * {@code unfiltered} is.
2168 *
2169 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2170 * across every key/value mapping in the underlying multimap and determine
2171 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2172 * faster to copy the filtered multimap and use the copy.
2173 *
2174 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>,
2175 * as documented at {@link Predicate#apply}. Do not provide a predicate such
2176 * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent
2177 * with equals.
2178 *
2179 * @since 11.0
2180 */
2181 @Beta
2182 @GwtIncompatible(value = "untested")
2183 public static <K, V> Multimap<K, V> filterKeys(
2184 Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2185 checkNotNull(keyPredicate);
2186 Predicate<Entry<K, V>> entryPredicate =
2187 new Predicate<Entry<K, V>>() {
2188 @Override
2189 public boolean apply(Entry<K, V> input) {
2190 return keyPredicate.apply(input.getKey());
2191 }
2192 };
2193 return filterEntries(unfiltered, entryPredicate);
2194 }
2195
2196 /**
2197 * Returns a multimap containing the mappings in {@code unfiltered} whose values
2198 * satisfy a predicate. The returned multimap is a live view of
2199 * {@code unfiltered}; changes to one affect the other.
2200 *
2201 * <p>The resulting multimap's views have iterators that don't support
2202 * {@code remove()}, but all other methods are supported by the multimap and
2203 * its views. When adding a value that doesn't satisfy the predicate, the
2204 * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods
2205 * throw an {@link IllegalArgumentException}.
2206 *
2207 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2208 * the filtered multimap or its views, only mappings whose value satisfy the
2209 * filter will be removed from the underlying multimap.
2210 *
2211 * <p>The returned multimap isn't threadsafe or serializable, even if
2212 * {@code unfiltered} is.
2213 *
2214 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2215 * across every key/value mapping in the underlying multimap and determine
2216 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2217 * faster to copy the filtered multimap and use the copy.
2218 *
2219 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
2220 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
2221 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
2222 * inconsistent with equals.
2223 *
2224 * @since 11.0
2225 */
2226 @Beta
2227 @GwtIncompatible(value = "untested")
2228 public static <K, V> Multimap<K, V> filterValues(
2229 Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2230 checkNotNull(valuePredicate);
2231 Predicate<Entry<K, V>> entryPredicate =
2232 new Predicate<Entry<K, V>>() {
2233 @Override
2234 public boolean apply(Entry<K, V> input) {
2235 return valuePredicate.apply(input.getValue());
2236 }
2237 };
2238 return filterEntries(unfiltered, entryPredicate);
2239 }
2240
2241 /**
2242 * Returns a multimap containing the mappings in {@code unfiltered} that
2243 * satisfy a predicate. The returned multimap is a live view of
2244 * {@code unfiltered}; changes to one affect the other.
2245 *
2246 * <p>The resulting multimap's views have iterators that don't support
2247 * {@code remove()}, but all other methods are supported by the multimap and
2248 * its views. When adding a key/value pair that doesn't satisfy the predicate,
2249 * multimap's {@code put()}, {@code putAll()}, and {@replaceValues()} methods
2250 * throw an {@link IllegalArgumentException}.
2251 *
2252 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on
2253 * the filtered multimap or its views, only mappings whose keys satisfy the
2254 * filter will be removed from the underlying multimap.
2255 *
2256 * <p>The returned multimap isn't threadsafe or serializable, even if
2257 * {@code unfiltered} is.
2258 *
2259 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate
2260 * across every key/value mapping in the underlying multimap and determine
2261 * which satisfy the filter. When a live view is <i>not</i> needed, it may be
2262 * faster to copy the filtered multimap and use the copy.
2263 *
2264 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
2265 * equals</i>, as documented at {@link Predicate#apply}.
2266 *
2267 * @since 11.0
2268 */
2269 @Beta
2270 @GwtIncompatible(value = "untested")
2271 public static <K, V> Multimap<K, V> filterEntries(
2272 Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2273 checkNotNull(entryPredicate);
2274 return (unfiltered instanceof FilteredMultimap)
2275 ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
2276 : new FilteredMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2277 }
2278
2279 /**
2280 * Support removal operations when filtering a filtered multimap. Since a
2281 * filtered multimap has iterators that don't support remove, passing one to
2282 * the FilteredMultimap constructor would lead to a multimap whose removal
2283 * operations would fail. This method combines the predicates to avoid that
2284 * problem.
2285 */
2286 private static <K, V> Multimap<K, V> filterFiltered(FilteredMultimap<K, V> map,
2287 Predicate<? super Entry<K, V>> entryPredicate) {
2288 Predicate<Entry<K, V>> predicate
2289 = Predicates.and(map.predicate, entryPredicate);
2290 return new FilteredMultimap<K, V>(map.unfiltered, predicate);
2291 }
2292
2293 private static class FilteredMultimap<K, V> implements Multimap<K, V> {
2294 final Multimap<K, V> unfiltered;
2295 final Predicate<? super Entry<K, V>> predicate;
2296
2297 FilteredMultimap(Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2298 this.unfiltered = unfiltered;
2299 this.predicate = predicate;
2300 }
2301
2302 @Override public int size() {
2303 return entries().size();
2304 }
2305
2306 @Override public boolean isEmpty() {
2307 return entries().isEmpty();
2308 }
2309
2310 @Override public boolean containsKey(Object key) {
2311 return asMap().containsKey(key);
2312 }
2313
2314 @Override public boolean containsValue(Object value) {
2315 return values().contains(value);
2316 }
2317
2318 // This method should be called only when key is a K and value is a V.
2319 @SuppressWarnings("unchecked")
2320 boolean satisfiesPredicate(Object key, Object value) {
2321 return predicate.apply(Maps.immutableEntry((K) key, (V) value));
2322 }
2323
2324 @Override public boolean containsEntry(Object key, Object value) {
2325 return unfiltered.containsEntry(key, value) && satisfiesPredicate(key, value);
2326 }
2327
2328 @Override public boolean put(K key, V value) {
2329 checkArgument(satisfiesPredicate(key, value));
2330 return unfiltered.put(key, value);
2331 }
2332
2333 @Override public boolean remove(Object key, Object value) {
2334 return containsEntry(key, value) ? unfiltered.remove(key, value) : false;
2335 }
2336
2337 @Override public boolean putAll(K key, Iterable<? extends V> values) {
2338 for (V value : values) {
2339 checkArgument(satisfiesPredicate(key, value));
2340 }
2341 return unfiltered.putAll(key, values);
2342 }
2343
2344 @Override public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
2345 for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
2346 checkArgument(satisfiesPredicate(entry.getKey(), entry.getValue()));
2347 }
2348 return unfiltered.putAll(multimap);
2349 }
2350
2351 @Override public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
2352 for (V value : values) {
2353 checkArgument(satisfiesPredicate(key, value));
2354 }
2355 // Not calling unfiltered.replaceValues() since values that don't satisify
2356 // the filter should remain in the multimap.
2357 Collection<V> oldValues = removeAll(key);
2358 unfiltered.putAll(key, values);
2359 return oldValues;
2360 }
2361
2362 @Override public Collection<V> removeAll(Object key) {
2363 List<V> removed = Lists.newArrayList();
2364 Collection<V> values = unfiltered.asMap().get(key);
2365 if (values != null) {
2366 Iterator<V> iterator = values.iterator();
2367 while (iterator.hasNext()) {
2368 V value = iterator.next();
2369 if (satisfiesPredicate(key, value)) {
2370 removed.add(value);
2371 iterator.remove();
2372 }
2373 }
2374 }
2375 if (unfiltered instanceof SetMultimap) {
2376 return Collections.unmodifiableSet(Sets.newLinkedHashSet(removed));
2377 } else {
2378 return Collections.unmodifiableList(removed);
2379 }
2380 }
2381
2382 @Override public void clear() {
2383 entries().clear();
2384 }
2385
2386 @Override public boolean equals(@Nullable Object object) {
2387 if (object == this) {
2388 return true;
2389 }
2390 if (object instanceof Multimap) {
2391 Multimap<?, ?> that = (Multimap<?, ?>) object;
2392 return asMap().equals(that.asMap());
2393 }
2394 return false;
2395 }
2396
2397 @Override public int hashCode() {
2398 return asMap().hashCode();
2399 }
2400
2401 @Override public String toString() {
2402 return asMap().toString();
2403 }
2404
2405 class ValuePredicate implements Predicate<V> {
2406 final K key;
2407 ValuePredicate(K key) {
2408 this.key = key;
2409 }
2410 @Override public boolean apply(V value) {
2411 return satisfiesPredicate(key, value);
2412 }
2413 }
2414
2415 Collection<V> filterCollection(Collection<V> collection, Predicate<V> predicate) {
2416 if (collection instanceof Set) {
2417 return Sets.filter((Set<V>) collection, predicate);
2418 } else {
2419 return Collections2.filter(collection, predicate);
2420 }
2421 }
2422
2423 @Override public Collection<V> get(K key) {
2424 return filterCollection(unfiltered.get(key), new ValuePredicate(key));
2425 }
2426
2427 @Override public Set<K> keySet() {
2428 return asMap().keySet();
2429 }
2430
2431 Collection<V> values;
2432
2433 @Override public Collection<V> values() {
2434 return (values == null) ? values = new Values() : values;
2435 }
2436
2437 class Values extends Multimaps.Values<K, V> {
2438 @Override Multimap<K, V> multimap() {
2439 return FilteredMultimap.this;
2440 }
2441
2442 @Override public boolean contains(@Nullable Object o) {
2443 return Iterators.contains(iterator(), o);
2444 }
2445
2446 // Override remove methods since iterator doesn't support remove.
2447
2448 @Override public boolean remove(Object o) {
2449 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2450 while (iterator.hasNext()) {
2451 Entry<K, V> entry = iterator.next();
2452 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
2453 iterator.remove();
2454 return true;
2455 }
2456 }
2457 return false;
2458 }
2459
2460 @Override public boolean removeAll(Collection<?> c) {
2461 boolean changed = false;
2462 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2463 while (iterator.hasNext()) {
2464 Entry<K, V> entry = iterator.next();
2465 if (c.contains(entry.getValue()) && predicate.apply(entry)) {
2466 iterator.remove();
2467 changed = true;
2468 }
2469 }
2470 return changed;
2471 }
2472
2473 @Override public boolean retainAll(Collection<?> c) {
2474 boolean changed = false;
2475 Iterator<Entry<K, V>> iterator = unfiltered.entries().iterator();
2476 while (iterator.hasNext()) {
2477 Entry<K, V> entry = iterator.next();
2478 if (!c.contains(entry.getValue()) && predicate.apply(entry)) {
2479 iterator.remove();
2480 changed = true;
2481 }
2482 }
2483 return changed;
2484 }
2485 }
2486
2487 Collection<Entry<K, V>> entries;
2488
2489 @Override public Collection<Entry<K, V>> entries() {
2490 return (entries == null)
2491 ? entries = Collections2.filter(unfiltered.entries(), predicate)
2492 : entries;
2493 }
2494
2495 /**
2496 * Remove all filtered asMap() entries that satisfy the predicate.
2497 */
2498 boolean removeEntriesIf(Predicate<Map.Entry<K, Collection<V>>> removalPredicate) {
2499 Iterator<Map.Entry<K, Collection<V>>> iterator = unfiltered.asMap().entrySet().iterator();
2500 boolean changed = false;
2501 while (iterator.hasNext()) {
2502 // Determine whether to remove the filtered values with this key.
2503 Map.Entry<K, Collection<V>> entry = iterator.next();
2504 K key = entry.getKey();
2505 Collection<V> collection = entry.getValue();
2506 Predicate<V> valuePredicate = new ValuePredicate(key);
2507 Collection<V> filteredCollection = filterCollection(collection, valuePredicate);
2508 Map.Entry<K, Collection<V>> filteredEntry = Maps.immutableEntry(key, filteredCollection);
2509 if (removalPredicate.apply(filteredEntry) && !filteredCollection.isEmpty()) {
2510 changed = true;
2511 if (Iterables.all(collection, valuePredicate)) {
2512 iterator.remove(); // Remove all values for the key.
2513 } else {
2514 filteredCollection.clear(); // Remove the filtered values only.
2515 }
2516 }
2517 }
2518 return changed;
2519 }
2520
2521 Map<K, Collection<V>> asMap;
2522
2523 @Override public Map<K, Collection<V>> asMap() {
2524 return (asMap == null) ? asMap = createAsMap() : asMap;
2525 }
2526
2527 static final Predicate<Collection<?>> NOT_EMPTY = new Predicate<Collection<?>>() {
2528 @Override public boolean apply(Collection<?> input) {
2529 return !input.isEmpty();
2530 }
2531 };
2532
2533 Map<K, Collection<V>> createAsMap() {
2534 // Select the values that satisify the predicate.
2535 EntryTransformer<K, Collection<V>, Collection<V>> transformer
2536 = new EntryTransformer<K, Collection<V>, Collection<V>>() {
2537 @Override public Collection<V> transformEntry(K key, Collection<V> collection) {
2538 return filterCollection(collection, new ValuePredicate(key));
2539 }
2540 };
2541 Map<K, Collection<V>> transformed
2542 = Maps.transformEntries(unfiltered.asMap(), transformer);
2543
2544 // Select the keys that have at least one value remaining.
2545 Map<K, Collection<V>> filtered = Maps.filterValues(transformed, NOT_EMPTY);
2546
2547 // Override the removal methods, since removing a map entry should not
2548 // affect values that don't satisfy the filter.
2549 return new AsMap(filtered);
2550 }
2551
2552 class AsMap extends ForwardingMap<K, Collection<V>> {
2553 final Map<K, Collection<V>> delegate;
2554
2555 AsMap(Map<K, Collection<V>> delegate) {
2556 this.delegate = delegate;
2557 }
2558
2559 @Override protected Map<K, Collection<V>> delegate() {
2560 return delegate;
2561 }
2562
2563 @Override public Collection<V> remove(Object o) {
2564 Collection<V> output = FilteredMultimap.this.removeAll(o);
2565 return output.isEmpty() ? null : output;
2566 }
2567
2568 @Override public void clear() {
2569 FilteredMultimap.this.clear();
2570 }
2571
2572 Set<K> keySet;
2573
2574 @Override public Set<K> keySet() {
2575 return (keySet == null) ? keySet = new KeySet() : keySet;
2576 }
2577
2578 class KeySet extends Maps.KeySet<K, Collection<V>> {
2579 @Override Map<K, Collection<V>> map() {
2580 return AsMap.this;
2581 }
2582
2583 @Override public boolean remove(Object o) {
2584 Collection<V> collection = delegate.get(o);
2585 if (collection == null) {
2586 return false;
2587 }
2588 collection.clear();
2589 return true;
2590 }
2591
2592 @Override public boolean removeAll(Collection<?> c) {
2593 return Sets.removeAllImpl(this, c);
2594 }
2595
2596 @Override public boolean retainAll(final Collection<?> c) {
2597 Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2598 = new Predicate<Map.Entry<K, Collection<V>>>() {
2599 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2600 return !c.contains(entry.getKey());
2601 }
2602 };
2603 return removeEntriesIf(removalPredicate);
2604 }
2605 }
2606
2607 Values asMapValues;
2608
2609 @Override public Collection<Collection<V>> values() {
2610 return (asMapValues == null) ? asMapValues = new Values() : asMapValues;
2611 }
2612
2613 class Values extends Maps.Values<K, Collection<V>> {
2614 @Override Map<K, Collection<V>> map() {
2615 return AsMap.this;
2616 }
2617
2618 @Override public boolean remove(Object o) {
2619 for (Collection<V> collection : this) {
2620 if (collection.equals(o)) {
2621 collection.clear();
2622 return true;
2623 }
2624 }
2625 return false;
2626 }
2627
2628 @Override public boolean removeAll(final Collection<?> c) {
2629 Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2630 = new Predicate<Map.Entry<K, Collection<V>>>() {
2631 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2632 return c.contains(entry.getValue());
2633 }
2634 };
2635 return removeEntriesIf(removalPredicate);
2636 }
2637
2638 @Override public boolean retainAll(final Collection<?> c) {
2639 Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2640 = new Predicate<Map.Entry<K, Collection<V>>>() {
2641 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2642 return !c.contains(entry.getValue());
2643 }
2644 };
2645 return removeEntriesIf(removalPredicate);
2646 }
2647 }
2648
2649 EntrySet entrySet;
2650
2651 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
2652 return (entrySet == null) ? entrySet = new EntrySet(super.entrySet()) : entrySet;
2653 }
2654
2655 class EntrySet extends Maps.EntrySet<K, Collection<V>> {
2656 Set<Map.Entry<K, Collection<V>>> delegateEntries;
2657
2658 public EntrySet(Set<Map.Entry<K, Collection<V>>> delegateEntries) {
2659 this.delegateEntries = delegateEntries;
2660 }
2661
2662 @Override Map<K, Collection<V>> map() {
2663 return AsMap.this;
2664 }
2665
2666 @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() {
2667 return delegateEntries.iterator();
2668 }
2669
2670 @Override public boolean remove(Object o) {
2671 if (o instanceof Entry<?, ?>) {
2672 Entry<?, ?> entry = (Entry<?, ?>) o;
2673 Collection<V> collection = delegate.get(entry.getKey());
2674 if (collection != null && collection.equals(entry.getValue())) {
2675 collection.clear();
2676 return true;
2677 }
2678 }
2679 return false;
2680 }
2681
2682 @Override public boolean removeAll(Collection<?> c) {
2683 return Sets.removeAllImpl(this, c);
2684 }
2685
2686 @Override public boolean retainAll(final Collection<?> c) {
2687 Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2688 = new Predicate<Map.Entry<K, Collection<V>>>() {
2689 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2690 return !c.contains(entry);
2691 }
2692 };
2693 return removeEntriesIf(removalPredicate);
2694 }
2695 }
2696 }
2697
2698 AbstractMultiset<K> keys;
2699
2700 @Override public Multiset<K> keys() {
2701 return (keys == null) ? keys = new Keys() : keys;
2702 }
2703
2704 class Keys extends Multimaps.Keys<K, V> {
2705 @Override Multimap<K, V> multimap() {
2706 return FilteredMultimap.this;
2707 }
2708
2709 @Override public int remove(Object o, int occurrences) {
2710 checkArgument(occurrences >= 0);
2711 Collection<V> values = unfiltered.asMap().get(o);
2712 if (values == null) {
2713 return 0;
2714 }
2715 int priorCount = 0;
2716 int removed = 0;
2717 Iterator<V> iterator = values.iterator();
2718 while (iterator.hasNext()) {
2719 if (satisfiesPredicate(o, iterator.next())) {
2720 priorCount++;
2721 if (removed < occurrences) {
2722 iterator.remove();
2723 removed++;
2724 }
2725 }
2726 }
2727 return priorCount;
2728 }
2729
2730 @Override Set<Multiset.Entry<K>> createEntrySet() {
2731 return new EntrySet();
2732 }
2733
2734 class EntrySet extends Multimaps.Keys<K, V>.KeysEntrySet {
2735 @Override public boolean removeAll(Collection<?> c) {
2736 return Sets.removeAllImpl(this, c);
2737 }
2738
2739 @Override public boolean retainAll(final Collection<?> c) {
2740 Predicate<Map.Entry<K, Collection<V>>> removalPredicate
2741 = new Predicate<Map.Entry<K, Collection<V>>>() {
2742 @Override public boolean apply(Map.Entry<K, Collection<V>> entry) {
2743 Multiset.Entry<K> multisetEntry
2744 = Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
2745 return !c.contains(multisetEntry);
2746 }
2747 };
2748 return removeEntriesIf(removalPredicate);
2749 }
2750 }
2751 }
2752 }
2753
2754 // TODO(jlevy): Create methods that filter a SetMultimap or SortedSetMultimap.
2755 }