1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
21 import static com.google.common.collect.CollectPreconditions.checkRemove;
22
23 import com.google.common.annotations.Beta;
24 import com.google.common.annotations.GwtCompatible;
25 import com.google.common.annotations.GwtIncompatible;
26 import com.google.common.base.Function;
27 import com.google.common.base.Predicate;
28 import com.google.common.base.Predicates;
29 import com.google.common.base.Supplier;
30 import com.google.common.collect.Maps.EntryTransformer;
31 import com.google.errorprone.annotations.CanIgnoreReturnValue;
32 import com.google.errorprone.annotations.concurrent.LazyInit;
33 import com.google.j2objc.annotations.Weak;
34 import com.google.j2objc.annotations.WeakOuter;
35 import java.io.IOException;
36 import java.io.ObjectInputStream;
37 import java.io.ObjectOutputStream;
38 import java.io.Serializable;
39 import java.util.AbstractCollection;
40 import java.util.Collection;
41 import java.util.Collections;
42 import java.util.Comparator;
43 import java.util.HashSet;
44 import java.util.Iterator;
45 import java.util.List;
46 import java.util.Map;
47 import java.util.Map.Entry;
48 import java.util.NavigableSet;
49 import java.util.NoSuchElementException;
50 import java.util.Set;
51 import java.util.SortedSet;
52 import java.util.Spliterator;
53 import java.util.function.BiConsumer;
54 import java.util.function.Consumer;
55 import java.util.stream.Collector;
56 import java.util.stream.Stream;
57 import org.checkerframework.checker.nullness.qual.Nullable;
58
59 /**
60 * Provides static methods acting on or generating a {@code Multimap}.
61 *
62 * <p>See the Guava User Guide article on <a href=
63 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multimaps"> {@code
64 * Multimaps}</a>.
65 *
66 * @author Jared Levy
67 * @author Robert Konigsberg
68 * @author Mike Bostock
69 * @author Louis Wasserman
70 * @since 2.0
71 */
72 @GwtCompatible(emulated = true)
73 public final class Multimaps {
74 private Multimaps() {}
75
76 /**
77 * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the
78 * specified supplier. The keys and values of the entries are the result of applying the provided
79 * mapping functions to the input elements, accumulated in the encounter order of the stream.
80 *
81 * <p>Example:
82 *
83 * <pre>{@code
84 * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP =
85 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
86 * .collect(
87 * toMultimap(
88 * str -> str.charAt(0),
89 * str -> str.substring(1),
90 * MultimapBuilder.treeKeys().arrayListValues()::build));
91 *
92 * // is equivalent to
93 *
94 * static final ListMultimap<Character, String> FIRST_LETTER_MULTIMAP;
95 *
96 * static {
97 * FIRST_LETTER_MULTIMAP = MultimapBuilder.treeKeys().arrayListValues().build();
98 * FIRST_LETTER_MULTIMAP.put('b', "anana");
99 * FIRST_LETTER_MULTIMAP.put('a', "pple");
100 * FIRST_LETTER_MULTIMAP.put('a', "sparagus");
101 * FIRST_LETTER_MULTIMAP.put('c', "arrot");
102 * FIRST_LETTER_MULTIMAP.put('c', "herry");
103 * }
104 * }</pre>
105 *
106 * <p>To collect to an {@link ImmutableMultimap}, use either {@link
107 * ImmutableSetMultimap#toImmutableSetMultimap} or {@link
108 * ImmutableListMultimap#toImmutableListMultimap}.
109 *
110 * @since 21.0
111 */
112 public static <T, K, V, M extends Multimap<K, V>> Collector<T, ?, M> toMultimap(
113 java.util.function.Function<? super T, ? extends K> keyFunction,
114 java.util.function.Function<? super T, ? extends V> valueFunction,
115 java.util.function.Supplier<M> multimapSupplier) {
116 return CollectCollectors.toMultimap(keyFunction, valueFunction, multimapSupplier);
117 }
118
119 /**
120 * Returns a {@code Collector} accumulating entries into a {@code Multimap} generated from the
121 * specified supplier. Each input element is mapped to a key and a stream of values, each of which
122 * are put into the resulting {@code Multimap}, in the encounter order of the stream and the
123 * encounter order of the streams of values.
124 *
125 * <p>Example:
126 *
127 * <pre>{@code
128 * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP =
129 * Stream.of("banana", "apple", "carrot", "asparagus", "cherry")
130 * .collect(
131 * flatteningToMultimap(
132 * str -> str.charAt(0),
133 * str -> str.substring(1).chars().mapToObj(c -> (char) c),
134 * MultimapBuilder.linkedHashKeys().arrayListValues()::build));
135 *
136 * // is equivalent to
137 *
138 * static final ListMultimap<Character, Character> FIRST_LETTER_MULTIMAP;
139 *
140 * static {
141 * FIRST_LETTER_MULTIMAP = MultimapBuilder.linkedHashKeys().arrayListValues().build();
142 * FIRST_LETTER_MULTIMAP.putAll('b', Arrays.asList('a', 'n', 'a', 'n', 'a'));
143 * FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('p', 'p', 'l', 'e'));
144 * FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('a', 'r', 'r', 'o', 't'));
145 * FIRST_LETTER_MULTIMAP.putAll('a', Arrays.asList('s', 'p', 'a', 'r', 'a', 'g', 'u', 's'));
146 * FIRST_LETTER_MULTIMAP.putAll('c', Arrays.asList('h', 'e', 'r', 'r', 'y'));
147 * }
148 * }</pre>
149 *
150 * @since 21.0
151 */
152 @Beta
153 public static <T, K, V, M extends Multimap<K, V>> Collector<T, ?, M> flatteningToMultimap(
154 java.util.function.Function<? super T, ? extends K> keyFunction,
155 java.util.function.Function<? super T, ? extends Stream<? extends V>> valueFunction,
156 java.util.function.Supplier<M> multimapSupplier) {
157 return CollectCollectors.flatteningToMultimap(keyFunction, valueFunction, multimapSupplier);
158 }
159
160 /**
161 * Creates a new {@code Multimap} backed by {@code map}, whose internal value collections are
162 * generated by {@code factory}.
163 *
164 * <p><b>Warning: do not use</b> this method when the collections returned by {@code factory}
165 * implement either {@link List} or {@code Set}! Use the more specific method {@link
166 * #newListMultimap}, {@link #newSetMultimap} or {@link #newSortedSetMultimap} instead, to avoid
167 * very surprising behavior from {@link Multimap#equals}.
168 *
169 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
170 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
171 * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
172 * method returns instances of a different class than {@code factory.get()} does.
173 *
174 * <p>The multimap is serializable if {@code map}, {@code factory}, the collections generated by
175 * {@code factory}, and the multimap contents are all serializable.
176 *
177 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
178 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
179 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
180 * #synchronizedMultimap}.
181 *
182 * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()}, {@link
183 * HashMultimap#create()}, {@link LinkedHashMultimap#create()}, {@link
184 * LinkedListMultimap#create()}, {@link TreeMultimap#create()}, and {@link
185 * TreeMultimap#create(Comparator, Comparator)} won't suffice.
186 *
187 * <p>Note: the multimap assumes complete ownership over of {@code map} and the collections
188 * returned by {@code factory}. Those objects should not be manually updated and they should not
189 * use soft, weak, or phantom references.
190 *
191 * @param map place to store the mapping from each key to its corresponding values
192 * @param factory supplier of new, empty collections that will each hold all values for a given
193 * key
194 * @throws IllegalArgumentException if {@code map} is not empty
195 */
196 public static <K, V> Multimap<K, V> newMultimap(
197 Map<K, Collection<V>> map, final Supplier<? extends Collection<V>> factory) {
198 return new CustomMultimap<>(map, factory);
199 }
200
201 private static class CustomMultimap<K, V> extends AbstractMapBasedMultimap<K, V> {
202 transient Supplier<? extends Collection<V>> factory;
203
204 CustomMultimap(Map<K, Collection<V>> map, Supplier<? extends Collection<V>> factory) {
205 super(map);
206 this.factory = checkNotNull(factory);
207 }
208
209 @Override
210 Set<K> createKeySet() {
211 return createMaybeNavigableKeySet();
212 }
213
214 @Override
215 Map<K, Collection<V>> createAsMap() {
216 return createMaybeNavigableAsMap();
217 }
218
219 @Override
220 protected Collection<V> createCollection() {
221 return factory.get();
222 }
223
224 @Override
225 <E> Collection<E> unmodifiableCollectionSubclass(Collection<E> collection) {
226 if (collection instanceof NavigableSet) {
227 return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection);
228 } else if (collection instanceof SortedSet) {
229 return Collections.unmodifiableSortedSet((SortedSet<E>) collection);
230 } else if (collection instanceof Set) {
231 return Collections.unmodifiableSet((Set<E>) collection);
232 } else if (collection instanceof List) {
233 return Collections.unmodifiableList((List<E>) collection);
234 } else {
235 return Collections.unmodifiableCollection(collection);
236 }
237 }
238
239 @Override
240 Collection<V> wrapCollection(K key, Collection<V> collection) {
241 if (collection instanceof List) {
242 return wrapList(key, (List<V>) collection, null);
243 } else if (collection instanceof NavigableSet) {
244 return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
245 } else if (collection instanceof SortedSet) {
246 return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
247 } else if (collection instanceof Set) {
248 return new WrappedSet(key, (Set<V>) collection);
249 } else {
250 return new WrappedCollection(key, collection, null);
251 }
252 }
253
254 // can't use Serialization writeMultimap and populateMultimap methods since
255 // there's no way to generate the empty backing map.
256
257 /** @serialData the factory and the backing map */
258 @GwtIncompatible // java.io.ObjectOutputStream
259 private void writeObject(ObjectOutputStream stream) throws IOException {
260 stream.defaultWriteObject();
261 stream.writeObject(factory);
262 stream.writeObject(backingMap());
263 }
264
265 @GwtIncompatible // java.io.ObjectInputStream
266 @SuppressWarnings("unchecked") // reading data stored by writeObject
267 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
268 stream.defaultReadObject();
269 factory = (Supplier<? extends Collection<V>>) stream.readObject();
270 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
271 setMap(map);
272 }
273
274 @GwtIncompatible // java serialization not supported
275 private static final long serialVersionUID = 0;
276 }
277
278 /**
279 * Creates a new {@code ListMultimap} that uses the provided map and factory. It can generate a
280 * multimap based on arbitrary {@link Map} and {@link List} classes.
281 *
282 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
283 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
284 * toString} methods for the multimap and its returned views. The multimap's {@code get}, {@code
285 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess} lists if the factory
286 * does. However, the multimap's {@code get} method returns instances of a different class than
287 * does {@code factory.get()}.
288 *
289 * <p>The multimap is serializable if {@code map}, {@code factory}, the lists generated by {@code
290 * factory}, and the multimap contents are all serializable.
291 *
292 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
293 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
294 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
295 * #synchronizedListMultimap}.
296 *
297 * <p>Call this method only when the simpler methods {@link ArrayListMultimap#create()} and {@link
298 * LinkedListMultimap#create()} won't suffice.
299 *
300 * <p>Note: the multimap assumes complete ownership over of {@code map} and the lists returned by
301 * {@code factory}. Those objects should not be manually updated, they should be empty when
302 * provided, and they should not use soft, weak, or phantom references.
303 *
304 * @param map place to store the mapping from each key to its corresponding values
305 * @param factory supplier of new, empty lists that will each hold all values for a given key
306 * @throws IllegalArgumentException if {@code map} is not empty
307 */
308 public static <K, V> ListMultimap<K, V> newListMultimap(
309 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
310 return new CustomListMultimap<>(map, factory);
311 }
312
313 private static class CustomListMultimap<K, V> extends AbstractListMultimap<K, V> {
314 transient Supplier<? extends List<V>> factory;
315
316 CustomListMultimap(Map<K, Collection<V>> map, Supplier<? extends List<V>> factory) {
317 super(map);
318 this.factory = checkNotNull(factory);
319 }
320
321 @Override
322 Set<K> createKeySet() {
323 return createMaybeNavigableKeySet();
324 }
325
326 @Override
327 Map<K, Collection<V>> createAsMap() {
328 return createMaybeNavigableAsMap();
329 }
330
331 @Override
332 protected List<V> createCollection() {
333 return factory.get();
334 }
335
336 /** @serialData the factory and the backing map */
337 @GwtIncompatible // java.io.ObjectOutputStream
338 private void writeObject(ObjectOutputStream stream) throws IOException {
339 stream.defaultWriteObject();
340 stream.writeObject(factory);
341 stream.writeObject(backingMap());
342 }
343
344 @GwtIncompatible // java.io.ObjectInputStream
345 @SuppressWarnings("unchecked") // reading data stored by writeObject
346 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
347 stream.defaultReadObject();
348 factory = (Supplier<? extends List<V>>) stream.readObject();
349 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
350 setMap(map);
351 }
352
353 @GwtIncompatible // java serialization not supported
354 private static final long serialVersionUID = 0;
355 }
356
357 /**
358 * Creates a new {@code SetMultimap} that uses the provided map and factory. It can generate a
359 * multimap based on arbitrary {@link Map} and {@link Set} classes.
360 *
361 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
362 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
363 * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
364 * method returns instances of a different class than {@code factory.get()} does.
365 *
366 * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code
367 * factory}, and the multimap contents are all serializable.
368 *
369 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
370 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
371 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
372 * #synchronizedSetMultimap}.
373 *
374 * <p>Call this method only when the simpler methods {@link HashMultimap#create()}, {@link
375 * LinkedHashMultimap#create()}, {@link TreeMultimap#create()}, and {@link
376 * TreeMultimap#create(Comparator, Comparator)} won't suffice.
377 *
378 * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by
379 * {@code factory}. Those objects should not be manually updated and they should not use soft,
380 * weak, or phantom references.
381 *
382 * @param map place to store the mapping from each key to its corresponding values
383 * @param factory supplier of new, empty sets that will each hold all values for a given key
384 * @throws IllegalArgumentException if {@code map} is not empty
385 */
386 public static <K, V> SetMultimap<K, V> newSetMultimap(
387 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
388 return new CustomSetMultimap<>(map, factory);
389 }
390
391 private static class CustomSetMultimap<K, V> extends AbstractSetMultimap<K, V> {
392 transient Supplier<? extends Set<V>> factory;
393
394 CustomSetMultimap(Map<K, Collection<V>> map, Supplier<? extends Set<V>> factory) {
395 super(map);
396 this.factory = checkNotNull(factory);
397 }
398
399 @Override
400 Set<K> createKeySet() {
401 return createMaybeNavigableKeySet();
402 }
403
404 @Override
405 Map<K, Collection<V>> createAsMap() {
406 return createMaybeNavigableAsMap();
407 }
408
409 @Override
410 protected Set<V> createCollection() {
411 return factory.get();
412 }
413
414 @Override
415 <E> Collection<E> unmodifiableCollectionSubclass(Collection<E> collection) {
416 if (collection instanceof NavigableSet) {
417 return Sets.unmodifiableNavigableSet((NavigableSet<E>) collection);
418 } else if (collection instanceof SortedSet) {
419 return Collections.unmodifiableSortedSet((SortedSet<E>) collection);
420 } else {
421 return Collections.unmodifiableSet((Set<E>) collection);
422 }
423 }
424
425 @Override
426 Collection<V> wrapCollection(K key, Collection<V> collection) {
427 if (collection instanceof NavigableSet) {
428 return new WrappedNavigableSet(key, (NavigableSet<V>) collection, null);
429 } else if (collection instanceof SortedSet) {
430 return new WrappedSortedSet(key, (SortedSet<V>) collection, null);
431 } else {
432 return new WrappedSet(key, (Set<V>) collection);
433 }
434 }
435
436 /** @serialData the factory and the backing map */
437 @GwtIncompatible // java.io.ObjectOutputStream
438 private void writeObject(ObjectOutputStream stream) throws IOException {
439 stream.defaultWriteObject();
440 stream.writeObject(factory);
441 stream.writeObject(backingMap());
442 }
443
444 @GwtIncompatible // java.io.ObjectInputStream
445 @SuppressWarnings("unchecked") // reading data stored by writeObject
446 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
447 stream.defaultReadObject();
448 factory = (Supplier<? extends Set<V>>) stream.readObject();
449 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
450 setMap(map);
451 }
452
453 @GwtIncompatible // not needed in emulated source
454 private static final long serialVersionUID = 0;
455 }
456
457 /**
458 * Creates a new {@code SortedSetMultimap} that uses the provided map and factory. It can generate
459 * a multimap based on arbitrary {@link Map} and {@link SortedSet} classes.
460 *
461 * <p>The {@code factory}-generated and {@code map} classes determine the multimap iteration
462 * order. They also specify the behavior of the {@code equals}, {@code hashCode}, and {@code
463 * toString} methods for the multimap and its returned views. However, the multimap's {@code get}
464 * method returns instances of a different class than {@code factory.get()} does.
465 *
466 * <p>The multimap is serializable if {@code map}, {@code factory}, the sets generated by {@code
467 * factory}, and the multimap contents are all serializable.
468 *
469 * <p>The multimap is not threadsafe when any concurrent operations update the multimap, even if
470 * {@code map} and the instances generated by {@code factory} are. Concurrent read operations will
471 * work correctly. To allow concurrent update operations, wrap the multimap with a call to {@link
472 * #synchronizedSortedSetMultimap}.
473 *
474 * <p>Call this method only when the simpler methods {@link TreeMultimap#create()} and {@link
475 * TreeMultimap#create(Comparator, Comparator)} won't suffice.
476 *
477 * <p>Note: the multimap assumes complete ownership over of {@code map} and the sets returned by
478 * {@code factory}. Those objects should not be manually updated and they should not use soft,
479 * weak, or phantom references.
480 *
481 * @param map place to store the mapping from each key to its corresponding values
482 * @param factory supplier of new, empty sorted sets that will each hold all values for a given
483 * key
484 * @throws IllegalArgumentException if {@code map} is not empty
485 */
486 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
487 Map<K, Collection<V>> map, final Supplier<? extends SortedSet<V>> factory) {
488 return new CustomSortedSetMultimap<>(map, factory);
489 }
490
491 private static class CustomSortedSetMultimap<K, V> extends AbstractSortedSetMultimap<K, V> {
492 transient Supplier<? extends SortedSet<V>> factory;
493 transient Comparator<? super V> valueComparator;
494
495 CustomSortedSetMultimap(Map<K, Collection<V>> map, Supplier<? extends SortedSet<V>> factory) {
496 super(map);
497 this.factory = checkNotNull(factory);
498 valueComparator = factory.get().comparator();
499 }
500
501 @Override
502 Set<K> createKeySet() {
503 return createMaybeNavigableKeySet();
504 }
505
506 @Override
507 Map<K, Collection<V>> createAsMap() {
508 return createMaybeNavigableAsMap();
509 }
510
511 @Override
512 protected SortedSet<V> createCollection() {
513 return factory.get();
514 }
515
516 @Override
517 public Comparator<? super V> valueComparator() {
518 return valueComparator;
519 }
520
521 /** @serialData the factory and the backing map */
522 @GwtIncompatible // java.io.ObjectOutputStream
523 private void writeObject(ObjectOutputStream stream) throws IOException {
524 stream.defaultWriteObject();
525 stream.writeObject(factory);
526 stream.writeObject(backingMap());
527 }
528
529 @GwtIncompatible // java.io.ObjectInputStream
530 @SuppressWarnings("unchecked") // reading data stored by writeObject
531 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
532 stream.defaultReadObject();
533 factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
534 valueComparator = factory.get().comparator();
535 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
536 setMap(map);
537 }
538
539 @GwtIncompatible // not needed in emulated source
540 private static final long serialVersionUID = 0;
541 }
542
543 /**
544 * Copies each key-value mapping in {@code source} into {@code dest}, with its key and value
545 * reversed.
546 *
547 * <p>If {@code source} is an {@link ImmutableMultimap}, consider using {@link
548 * ImmutableMultimap#inverse} instead.
549 *
550 * @param source any multimap
551 * @param dest the multimap to copy into; usually empty
552 * @return {@code dest}
553 */
554 @CanIgnoreReturnValue
555 public static <K, V, M extends Multimap<K, V>> M invertFrom(
556 Multimap<? extends V, ? extends K> source, M dest) {
557 checkNotNull(dest);
558 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
559 dest.put(entry.getValue(), entry.getKey());
560 }
561 return dest;
562 }
563
564 /**
565 * Returns a synchronized (thread-safe) multimap backed by the specified multimap. In order to
566 * guarantee serial access, it is critical that <b>all</b> access to the backing multimap is
567 * accomplished through the returned multimap.
568 *
569 * <p>It is imperative that the user manually synchronize on the returned multimap when accessing
570 * any of its collection views:
571 *
572 * <pre>{@code
573 * Multimap<K, V> multimap = Multimaps.synchronizedMultimap(
574 * HashMultimap.<K, V>create());
575 * ...
576 * Collection<V> values = multimap.get(key); // Needn't be in synchronized block
577 * ...
578 * synchronized (multimap) { // Synchronizing on multimap, not values!
579 * Iterator<V> i = values.iterator(); // Must be in synchronized block
580 * while (i.hasNext()) {
581 * foo(i.next());
582 * }
583 * }
584 * }</pre>
585 *
586 * <p>Failure to follow this advice may result in non-deterministic behavior.
587 *
588 * <p>Note that the generated multimap's {@link Multimap#removeAll} and {@link
589 * Multimap#replaceValues} methods return collections that aren't synchronized.
590 *
591 * <p>The returned multimap will be serializable if the specified multimap is serializable.
592 *
593 * @param multimap the multimap to be wrapped in a synchronized view
594 * @return a synchronized view of the specified multimap
595 */
596 public static <K, V> Multimap<K, V> synchronizedMultimap(Multimap<K, V> multimap) {
597 return Synchronized.multimap(multimap, null);
598 }
599
600 /**
601 * Returns an unmodifiable view of the specified multimap. Query operations on the returned
602 * multimap "read through" to the specified multimap, and attempts to modify the returned
603 * multimap, either directly or through the multimap's views, result in an {@code
604 * UnsupportedOperationException}.
605 *
606 * <p>The returned multimap will be serializable if the specified multimap is serializable.
607 *
608 * @param delegate the multimap for which an unmodifiable view is to be returned
609 * @return an unmodifiable view of the specified multimap
610 */
611 public static <K, V> Multimap<K, V> unmodifiableMultimap(Multimap<K, V> delegate) {
612 if (delegate instanceof UnmodifiableMultimap || delegate instanceof ImmutableMultimap) {
613 return delegate;
614 }
615 return new UnmodifiableMultimap<>(delegate);
616 }
617
618 /**
619 * Simply returns its argument.
620 *
621 * @deprecated no need to use this
622 * @since 10.0
623 */
624 @Deprecated
625 public static <K, V> Multimap<K, V> unmodifiableMultimap(ImmutableMultimap<K, V> delegate) {
626 return checkNotNull(delegate);
627 }
628
629 private static class UnmodifiableMultimap<K, V> extends ForwardingMultimap<K, V>
630 implements Serializable {
631 final Multimap<K, V> delegate;
632 @LazyInit transient @Nullable Collection<Entry<K, V>> entries;
633 @LazyInit transient @Nullable Multiset<K> keys;
634 @LazyInit transient @Nullable Set<K> keySet;
635 @LazyInit transient @Nullable Collection<V> values;
636 @LazyInit transient @Nullable Map<K, Collection<V>> map;
637
638 UnmodifiableMultimap(final Multimap<K, V> delegate) {
639 this.delegate = checkNotNull(delegate);
640 }
641
642 @Override
643 protected Multimap<K, V> delegate() {
644 return delegate;
645 }
646
647 @Override
648 public void clear() {
649 throw new UnsupportedOperationException();
650 }
651
652 @Override
653 public Map<K, Collection<V>> asMap() {
654 Map<K, Collection<V>> result = map;
655 if (result == null) {
656 result =
657 map =
658 Collections.unmodifiableMap(
659 Maps.transformValues(
660 delegate.asMap(),
661 new Function<Collection<V>, Collection<V>>() {
662 @Override
663 public Collection<V> apply(Collection<V> collection) {
664 return unmodifiableValueCollection(collection);
665 }
666 }));
667 }
668 return result;
669 }
670
671 @Override
672 public Collection<Entry<K, V>> entries() {
673 Collection<Entry<K, V>> result = entries;
674 if (result == null) {
675 entries = result = unmodifiableEntries(delegate.entries());
676 }
677 return result;
678 }
679
680 @Override
681 public void forEach(BiConsumer<? super K, ? super V> consumer) {
682 delegate.forEach(checkNotNull(consumer));
683 }
684
685 @Override
686 public Collection<V> get(K key) {
687 return unmodifiableValueCollection(delegate.get(key));
688 }
689
690 @Override
691 public Multiset<K> keys() {
692 Multiset<K> result = keys;
693 if (result == null) {
694 keys = result = Multisets.unmodifiableMultiset(delegate.keys());
695 }
696 return result;
697 }
698
699 @Override
700 public Set<K> keySet() {
701 Set<K> result = keySet;
702 if (result == null) {
703 keySet = result = Collections.unmodifiableSet(delegate.keySet());
704 }
705 return result;
706 }
707
708 @Override
709 public boolean put(K key, V value) {
710 throw new UnsupportedOperationException();
711 }
712
713 @Override
714 public boolean putAll(K key, Iterable<? extends V> values) {
715 throw new UnsupportedOperationException();
716 }
717
718 @Override
719 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
720 throw new UnsupportedOperationException();
721 }
722
723 @Override
724 public boolean remove(Object key, Object value) {
725 throw new UnsupportedOperationException();
726 }
727
728 @Override
729 public Collection<V> removeAll(Object key) {
730 throw new UnsupportedOperationException();
731 }
732
733 @Override
734 public Collection<V> replaceValues(K key, Iterable<? extends V> values) {
735 throw new UnsupportedOperationException();
736 }
737
738 @Override
739 public Collection<V> values() {
740 Collection<V> result = values;
741 if (result == null) {
742 values = result = Collections.unmodifiableCollection(delegate.values());
743 }
744 return result;
745 }
746
747 private static final long serialVersionUID = 0;
748 }
749
750 private static class UnmodifiableListMultimap<K, V> extends UnmodifiableMultimap<K, V>
751 implements ListMultimap<K, V> {
752 UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
753 super(delegate);
754 }
755
756 @Override
757 public ListMultimap<K, V> delegate() {
758 return (ListMultimap<K, V>) super.delegate();
759 }
760
761 @Override
762 public List<V> get(K key) {
763 return Collections.unmodifiableList(delegate().get(key));
764 }
765
766 @Override
767 public List<V> removeAll(Object key) {
768 throw new UnsupportedOperationException();
769 }
770
771 @Override
772 public List<V> replaceValues(K key, Iterable<? extends V> values) {
773 throw new UnsupportedOperationException();
774 }
775
776 private static final long serialVersionUID = 0;
777 }
778
779 private static class UnmodifiableSetMultimap<K, V> extends UnmodifiableMultimap<K, V>
780 implements SetMultimap<K, V> {
781 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
782 super(delegate);
783 }
784
785 @Override
786 public SetMultimap<K, V> delegate() {
787 return (SetMultimap<K, V>) super.delegate();
788 }
789
790 @Override
791 public Set<V> get(K key) {
792 /*
793 * Note that this doesn't return a SortedSet when delegate is a
794 * SortedSetMultiset, unlike (SortedSet<V>) super.get().
795 */
796 return Collections.unmodifiableSet(delegate().get(key));
797 }
798
799 @Override
800 public Set<Map.Entry<K, V>> entries() {
801 return Maps.unmodifiableEntrySet(delegate().entries());
802 }
803
804 @Override
805 public Set<V> removeAll(Object key) {
806 throw new UnsupportedOperationException();
807 }
808
809 @Override
810 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
811 throw new UnsupportedOperationException();
812 }
813
814 private static final long serialVersionUID = 0;
815 }
816
817 private static class UnmodifiableSortedSetMultimap<K, V> extends UnmodifiableSetMultimap<K, V>
818 implements SortedSetMultimap<K, V> {
819 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
820 super(delegate);
821 }
822
823 @Override
824 public SortedSetMultimap<K, V> delegate() {
825 return (SortedSetMultimap<K, V>) super.delegate();
826 }
827
828 @Override
829 public SortedSet<V> get(K key) {
830 return Collections.unmodifiableSortedSet(delegate().get(key));
831 }
832
833 @Override
834 public SortedSet<V> removeAll(Object key) {
835 throw new UnsupportedOperationException();
836 }
837
838 @Override
839 public SortedSet<V> replaceValues(K key, Iterable<? extends V> values) {
840 throw new UnsupportedOperationException();
841 }
842
843 @Override
844 public Comparator<? super V> valueComparator() {
845 return delegate().valueComparator();
846 }
847
848 private static final long serialVersionUID = 0;
849 }
850
851 /**
852 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the specified multimap.
853 *
854 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
855 *
856 * <p>The returned multimap will be serializable if the specified multimap is serializable.
857 *
858 * @param multimap the multimap to be wrapped
859 * @return a synchronized view of the specified multimap
860 */
861 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(SetMultimap<K, V> multimap) {
862 return Synchronized.setMultimap(multimap, null);
863 }
864
865 /**
866 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query operations on the
867 * returned multimap "read through" to the specified multimap, and attempts to modify the returned
868 * multimap, either directly or through the multimap's views, result in an {@code
869 * UnsupportedOperationException}.
870 *
871 * <p>The returned multimap will be serializable if the specified multimap is serializable.
872 *
873 * @param delegate the multimap for which an unmodifiable view is to be returned
874 * @return an unmodifiable view of the specified multimap
875 */
876 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(SetMultimap<K, V> delegate) {
877 if (delegate instanceof UnmodifiableSetMultimap || delegate instanceof ImmutableSetMultimap) {
878 return delegate;
879 }
880 return new UnmodifiableSetMultimap<>(delegate);
881 }
882
883 /**
884 * Simply returns its argument.
885 *
886 * @deprecated no need to use this
887 * @since 10.0
888 */
889 @Deprecated
890 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
891 ImmutableSetMultimap<K, V> delegate) {
892 return checkNotNull(delegate);
893 }
894
895 /**
896 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by the specified
897 * multimap.
898 *
899 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
900 *
901 * <p>The returned multimap will be serializable if the specified multimap is serializable.
902 *
903 * @param multimap the multimap to be wrapped
904 * @return a synchronized view of the specified multimap
905 */
906 public static <K, V> SortedSetMultimap<K, V> synchronizedSortedSetMultimap(
907 SortedSetMultimap<K, V> multimap) {
908 return Synchronized.sortedSetMultimap(multimap, null);
909 }
910
911 /**
912 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}. Query operations on
913 * the returned multimap "read through" to the specified multimap, and attempts to modify the
914 * returned multimap, either directly or through the multimap's views, result in an {@code
915 * UnsupportedOperationException}.
916 *
917 * <p>The returned multimap will be serializable if the specified multimap is serializable.
918 *
919 * @param delegate the multimap for which an unmodifiable view is to be returned
920 * @return an unmodifiable view of the specified multimap
921 */
922 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
923 SortedSetMultimap<K, V> delegate) {
924 if (delegate instanceof UnmodifiableSortedSetMultimap) {
925 return delegate;
926 }
927 return new UnmodifiableSortedSetMultimap<>(delegate);
928 }
929
930 /**
931 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the specified multimap.
932 *
933 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
934 *
935 * @param multimap the multimap to be wrapped
936 * @return a synchronized view of the specified multimap
937 */
938 public static <K, V> ListMultimap<K, V> synchronizedListMultimap(ListMultimap<K, V> multimap) {
939 return Synchronized.listMultimap(multimap, null);
940 }
941
942 /**
943 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query operations on the
944 * returned multimap "read through" to the specified multimap, and attempts to modify the returned
945 * multimap, either directly or through the multimap's views, result in an {@code
946 * UnsupportedOperationException}.
947 *
948 * <p>The returned multimap will be serializable if the specified multimap is serializable.
949 *
950 * @param delegate the multimap for which an unmodifiable view is to be returned
951 * @return an unmodifiable view of the specified multimap
952 */
953 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(ListMultimap<K, V> delegate) {
954 if (delegate instanceof UnmodifiableListMultimap || delegate instanceof ImmutableListMultimap) {
955 return delegate;
956 }
957 return new UnmodifiableListMultimap<>(delegate);
958 }
959
960 /**
961 * Simply returns its argument.
962 *
963 * @deprecated no need to use this
964 * @since 10.0
965 */
966 @Deprecated
967 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
968 ImmutableListMultimap<K, V> delegate) {
969 return checkNotNull(delegate);
970 }
971
972 /**
973 * Returns an unmodifiable view of the specified collection, preserving the interface for
974 * instances of {@code SortedSet}, {@code Set}, {@code List} and {@code Collection}, in that order
975 * of preference.
976 *
977 * @param collection the collection for which to return an unmodifiable view
978 * @return an unmodifiable view of the collection
979 */
980 private static <V> Collection<V> unmodifiableValueCollection(Collection<V> collection) {
981 if (collection instanceof SortedSet) {
982 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
983 } else if (collection instanceof Set) {
984 return Collections.unmodifiableSet((Set<V>) collection);
985 } else if (collection instanceof List) {
986 return Collections.unmodifiableList((List<V>) collection);
987 }
988 return Collections.unmodifiableCollection(collection);
989 }
990
991 /**
992 * Returns an unmodifiable view of the specified collection of entries. The {@link Entry#setValue}
993 * operation throws an {@link UnsupportedOperationException}. If the specified collection is a
994 * {@code Set}, the returned collection is also a {@code Set}.
995 *
996 * @param entries the entries for which to return an unmodifiable view
997 * @return an unmodifiable view of the entries
998 */
999 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
1000 Collection<Entry<K, V>> entries) {
1001 if (entries instanceof Set) {
1002 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
1003 }
1004 return new Maps.UnmodifiableEntries<>(Collections.unmodifiableCollection(entries));
1005 }
1006
1007 /**
1008 * Returns {@link ListMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K,
1009 * Collection<V>>} to {@code Map<K, List<V>>}.
1010 *
1011 * @since 15.0
1012 */
1013 @Beta
1014 @SuppressWarnings("unchecked")
1015 // safe by specification of ListMultimap.asMap()
1016 public static <K, V> Map<K, List<V>> asMap(ListMultimap<K, V> multimap) {
1017 return (Map<K, List<V>>) (Map<K, ?>) multimap.asMap();
1018 }
1019
1020 /**
1021 * Returns {@link SetMultimap#asMap multimap.asMap()}, with its type corrected from {@code Map<K,
1022 * Collection<V>>} to {@code Map<K, Set<V>>}.
1023 *
1024 * @since 15.0
1025 */
1026 @Beta
1027 @SuppressWarnings("unchecked")
1028 // safe by specification of SetMultimap.asMap()
1029 public static <K, V> Map<K, Set<V>> asMap(SetMultimap<K, V> multimap) {
1030 return (Map<K, Set<V>>) (Map<K, ?>) multimap.asMap();
1031 }
1032
1033 /**
1034 * Returns {@link SortedSetMultimap#asMap multimap.asMap()}, with its type corrected from {@code
1035 * Map<K, Collection<V>>} to {@code Map<K, SortedSet<V>>}.
1036 *
1037 * @since 15.0
1038 */
1039 @Beta
1040 @SuppressWarnings("unchecked")
1041 // safe by specification of SortedSetMultimap.asMap()
1042 public static <K, V> Map<K, SortedSet<V>> asMap(SortedSetMultimap<K, V> multimap) {
1043 return (Map<K, SortedSet<V>>) (Map<K, ?>) multimap.asMap();
1044 }
1045
1046 /**
1047 * Returns {@link Multimap#asMap multimap.asMap()}. This is provided for parity with the other
1048 * more strongly-typed {@code asMap()} implementations.
1049 *
1050 * @since 15.0
1051 */
1052 @Beta
1053 public static <K, V> Map<K, Collection<V>> asMap(Multimap<K, V> multimap) {
1054 return multimap.asMap();
1055 }
1056
1057 /**
1058 * Returns a multimap view of the specified map. The multimap is backed by the map, so changes to
1059 * the map are reflected in the multimap, and vice versa. If the map is modified while an
1060 * iteration over one of the multimap's collection views is in progress (except through the
1061 * iterator's own {@code remove} operation, or through the {@code setValue} operation on a map
1062 * entry returned by the iterator), the results of the iteration are undefined.
1063 *
1064 * <p>The multimap supports mapping removal, which removes the corresponding mapping from the map.
1065 * It does not support any operations which might add mappings, such as {@code put}, {@code
1066 * putAll} or {@code replaceValues}.
1067 *
1068 * <p>The returned multimap will be serializable if the specified map is serializable.
1069 *
1070 * @param map the backing map for the returned multimap view
1071 */
1072 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
1073 return new MapMultimap<>(map);
1074 }
1075
1076 /** @see Multimaps#forMap */
1077 private static class MapMultimap<K, V> extends AbstractMultimap<K, V>
1078 implements SetMultimap<K, V>, Serializable {
1079 final Map<K, V> map;
1080
1081 MapMultimap(Map<K, V> map) {
1082 this.map = checkNotNull(map);
1083 }
1084
1085 @Override
1086 public int size() {
1087 return map.size();
1088 }
1089
1090 @Override
1091 public boolean containsKey(Object key) {
1092 return map.containsKey(key);
1093 }
1094
1095 @Override
1096 public boolean containsValue(Object value) {
1097 return map.containsValue(value);
1098 }
1099
1100 @Override
1101 public boolean containsEntry(Object key, Object value) {
1102 return map.entrySet().contains(Maps.immutableEntry(key, value));
1103 }
1104
1105 @Override
1106 public Set<V> get(final K key) {
1107 return new Sets.ImprovedAbstractSet<V>() {
1108 @Override
1109 public Iterator<V> iterator() {
1110 return new Iterator<V>() {
1111 int i;
1112
1113 @Override
1114 public boolean hasNext() {
1115 return (i == 0) && map.containsKey(key);
1116 }
1117
1118 @Override
1119 public V next() {
1120 if (!hasNext()) {
1121 throw new NoSuchElementException();
1122 }
1123 i++;
1124 return map.get(key);
1125 }
1126
1127 @Override
1128 public void remove() {
1129 checkRemove(i == 1);
1130 i = -1;
1131 map.remove(key);
1132 }
1133 };
1134 }
1135
1136 @Override
1137 public int size() {
1138 return map.containsKey(key) ? 1 : 0;
1139 }
1140 };
1141 }
1142
1143 @Override
1144 public boolean put(K key, V value) {
1145 throw new UnsupportedOperationException();
1146 }
1147
1148 @Override
1149 public boolean putAll(K key, Iterable<? extends V> values) {
1150 throw new UnsupportedOperationException();
1151 }
1152
1153 @Override
1154 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1155 throw new UnsupportedOperationException();
1156 }
1157
1158 @Override
1159 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1160 throw new UnsupportedOperationException();
1161 }
1162
1163 @Override
1164 public boolean remove(Object key, Object value) {
1165 return map.entrySet().remove(Maps.immutableEntry(key, value));
1166 }
1167
1168 @Override
1169 public Set<V> removeAll(Object key) {
1170 Set<V> values = new HashSet<V>(2);
1171 if (!map.containsKey(key)) {
1172 return values;
1173 }
1174 values.add(map.remove(key));
1175 return values;
1176 }
1177
1178 @Override
1179 public void clear() {
1180 map.clear();
1181 }
1182
1183 @Override
1184 Set<K> createKeySet() {
1185 return map.keySet();
1186 }
1187
1188 @Override
1189 Collection<V> createValues() {
1190 return map.values();
1191 }
1192
1193 @Override
1194 public Set<Entry<K, V>> entries() {
1195 return map.entrySet();
1196 }
1197
1198 @Override
1199 Collection<Entry<K, V>> createEntries() {
1200 throw new AssertionError("unreachable");
1201 }
1202
1203 @Override
1204 Multiset<K> createKeys() {
1205 return new Multimaps.Keys<K, V>(this);
1206 }
1207
1208 @Override
1209 Iterator<Entry<K, V>> entryIterator() {
1210 return map.entrySet().iterator();
1211 }
1212
1213 @Override
1214 Map<K, Collection<V>> createAsMap() {
1215 return new AsMap<>(this);
1216 }
1217
1218 @Override
1219 public int hashCode() {
1220 return map.hashCode();
1221 }
1222
1223 private static final long serialVersionUID = 7845222491160860175L;
1224 }
1225
1226 /**
1227 * Returns a view of a multimap where each value is transformed by a function. All other
1228 * properties of the multimap, such as iteration order, are left intact. For example, the code:
1229 *
1230 * <pre>{@code
1231 * Multimap<String, Integer> multimap =
1232 * ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
1233 * Function<Integer, String> square = new Function<Integer, String>() {
1234 * public String apply(Integer in) {
1235 * return Integer.toString(in * in);
1236 * }
1237 * };
1238 * Multimap<String, String> transformed =
1239 * Multimaps.transformValues(multimap, square);
1240 * System.out.println(transformed);
1241 * }</pre>
1242 *
1243 * ... prints {@code {a=[4, 16], b=[9, 9], c=[36]}}.
1244 *
1245 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1246 * supports removal operations, and these are reflected in the underlying multimap.
1247 *
1248 * <p>It's acceptable for the underlying multimap to contain null keys, and even null values
1249 * provided that the function is capable of accepting null input. The transformed multimap might
1250 * contain null values, if the function sometimes gives a null result.
1251 *
1252 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1253 * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless,
1254 * since there is not a definition of {@code equals} or {@code hashCode} for general collections,
1255 * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a
1256 * {@code Set}.
1257 *
1258 * <p>The function is applied lazily, invoked when needed. This is necessary for the returned
1259 * multimap to be a view, but it means that the function will be applied many times for bulk
1260 * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1261 * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned
1262 * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your
1263 * choosing.
1264 *
1265 * @since 7.0
1266 */
1267 public static <K, V1, V2> Multimap<K, V2> transformValues(
1268 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1269 checkNotNull(function);
1270 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1271 return transformEntries(fromMultimap, transformer);
1272 }
1273
1274 /**
1275 * Returns a view of a {@code ListMultimap} where each value is transformed by a function. All
1276 * other properties of the multimap, such as iteration order, are left intact. For example, the
1277 * code:
1278 *
1279 * <pre>{@code
1280 * ListMultimap<String, Integer> multimap
1281 * = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
1282 * Function<Integer, Double> sqrt =
1283 * new Function<Integer, Double>() {
1284 * public Double apply(Integer in) {
1285 * return Math.sqrt((int) in);
1286 * }
1287 * };
1288 * ListMultimap<String, Double> transformed = Multimaps.transformValues(map,
1289 * sqrt);
1290 * System.out.println(transformed);
1291 * }</pre>
1292 *
1293 * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}.
1294 *
1295 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1296 * supports removal operations, and these are reflected in the underlying multimap.
1297 *
1298 * <p>It's acceptable for the underlying multimap to contain null keys, and even null values
1299 * provided that the function is capable of accepting null input. The transformed multimap might
1300 * contain null values, if the function sometimes gives a null result.
1301 *
1302 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1303 * is.
1304 *
1305 * <p>The function is applied lazily, invoked when needed. This is necessary for the returned
1306 * multimap to be a view, but it means that the function will be applied many times for bulk
1307 * operations like {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1308 * perform well, {@code function} should be fast. To avoid lazy evaluation when the returned
1309 * multimap doesn't need to be a view, copy the returned multimap into a new multimap of your
1310 * choosing.
1311 *
1312 * @since 7.0
1313 */
1314 public static <K, V1, V2> ListMultimap<K, V2> transformValues(
1315 ListMultimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1316 checkNotNull(function);
1317 EntryTransformer<K, V1, V2> transformer = Maps.asEntryTransformer(function);
1318 return transformEntries(fromMultimap, transformer);
1319 }
1320
1321 /**
1322 * Returns a view of a multimap whose values are derived from the original multimap's entries. In
1323 * contrast to {@link #transformValues}, this method's entry-transformation logic may depend on
1324 * the key as well as the value.
1325 *
1326 * <p>All other properties of the transformed multimap, such as iteration order, are left intact.
1327 * For example, the code:
1328 *
1329 * <pre>{@code
1330 * SetMultimap<String, Integer> multimap =
1331 * ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
1332 * EntryTransformer<String, Integer, String> transformer =
1333 * new EntryTransformer<String, Integer, String>() {
1334 * public String transformEntry(String key, Integer value) {
1335 * return (value >= 0) ? key : "no" + key;
1336 * }
1337 * };
1338 * Multimap<String, String> transformed =
1339 * Multimaps.transformEntries(multimap, transformer);
1340 * System.out.println(transformed);
1341 * }</pre>
1342 *
1343 * ... prints {@code {a=[a, a], b=[nob]}}.
1344 *
1345 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1346 * supports removal operations, and these are reflected in the underlying multimap.
1347 *
1348 * <p>It's acceptable for the underlying multimap to contain null keys and null values provided
1349 * that the transformer is capable of accepting null inputs. The transformed multimap might
1350 * contain null values if the transformer sometimes gives a null result.
1351 *
1352 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1353 * is. The {@code equals} and {@code hashCode} methods of the returned multimap are meaningless,
1354 * since there is not a definition of {@code equals} or {@code hashCode} for general collections,
1355 * and {@code get()} will return a general {@code Collection} as opposed to a {@code List} or a
1356 * {@code Set}.
1357 *
1358 * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1359 * multimap to be a view, but it means that the transformer will be applied many times for bulk
1360 * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform
1361 * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap
1362 * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing.
1363 *
1364 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1365 * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1366 * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1367 * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1368 * transformed multimap.
1369 *
1370 * @since 7.0
1371 */
1372 public static <K, V1, V2> Multimap<K, V2> transformEntries(
1373 Multimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1374 return new TransformedEntriesMultimap<>(fromMap, transformer);
1375 }
1376
1377 /**
1378 * Returns a view of a {@code ListMultimap} whose values are derived from the original multimap's
1379 * entries. In contrast to {@link #transformValues(ListMultimap, Function)}, this method's
1380 * entry-transformation logic may depend on the key as well as the value.
1381 *
1382 * <p>All other properties of the transformed multimap, such as iteration order, are left intact.
1383 * For example, the code:
1384 *
1385 * <pre>{@code
1386 * Multimap<String, Integer> multimap =
1387 * ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
1388 * EntryTransformer<String, Integer, String> transformer =
1389 * new EntryTransformer<String, Integer, String>() {
1390 * public String transformEntry(String key, Integer value) {
1391 * return key + value;
1392 * }
1393 * };
1394 * Multimap<String, String> transformed =
1395 * Multimaps.transformEntries(multimap, transformer);
1396 * System.out.println(transformed);
1397 * }</pre>
1398 *
1399 * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}.
1400 *
1401 * <p>Changes in the underlying multimap are reflected in this view. Conversely, this view
1402 * supports removal operations, and these are reflected in the underlying multimap.
1403 *
1404 * <p>It's acceptable for the underlying multimap to contain null keys and null values provided
1405 * that the transformer is capable of accepting null inputs. The transformed multimap might
1406 * contain null values if the transformer sometimes gives a null result.
1407 *
1408 * <p>The returned multimap is not thread-safe or serializable, even if the underlying multimap
1409 * is.
1410 *
1411 * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1412 * multimap to be a view, but it means that the transformer will be applied many times for bulk
1413 * operations like {@link Multimap#containsValue} and {@link Object#toString}. For this to perform
1414 * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned multimap
1415 * doesn't need to be a view, copy the returned multimap into a new multimap of your choosing.
1416 *
1417 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1418 * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1419 * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1420 * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1421 * transformed multimap.
1422 *
1423 * @since 7.0
1424 */
1425 public static <K, V1, V2> ListMultimap<K, V2> transformEntries(
1426 ListMultimap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1427 return new TransformedEntriesListMultimap<>(fromMap, transformer);
1428 }
1429
1430 private static class TransformedEntriesMultimap<K, V1, V2> extends AbstractMultimap<K, V2> {
1431 final Multimap<K, V1> fromMultimap;
1432 final EntryTransformer<? super K, ? super V1, V2> transformer;
1433
1434 TransformedEntriesMultimap(
1435 Multimap<K, V1> fromMultimap,
1436 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1437 this.fromMultimap = checkNotNull(fromMultimap);
1438 this.transformer = checkNotNull(transformer);
1439 }
1440
1441 Collection<V2> transform(K key, Collection<V1> values) {
1442 Function<? super V1, V2> function = Maps.asValueToValueFunction(transformer, key);
1443 if (values instanceof List) {
1444 return Lists.transform((List<V1>) values, function);
1445 } else {
1446 return Collections2.transform(values, function);
1447 }
1448 }
1449
1450 @Override
1451 Map<K, Collection<V2>> createAsMap() {
1452 return Maps.transformEntries(
1453 fromMultimap.asMap(),
1454 new EntryTransformer<K, Collection<V1>, Collection<V2>>() {
1455 @Override
1456 public Collection<V2> transformEntry(K key, Collection<V1> value) {
1457 return transform(key, value);
1458 }
1459 });
1460 }
1461
1462 @Override
1463 public void clear() {
1464 fromMultimap.clear();
1465 }
1466
1467 @Override
1468 public boolean containsKey(Object key) {
1469 return fromMultimap.containsKey(key);
1470 }
1471
1472 @Override
1473 Collection<Entry<K, V2>> createEntries() {
1474 return new Entries();
1475 }
1476
1477 @Override
1478 Iterator<Entry<K, V2>> entryIterator() {
1479 return Iterators.transform(
1480 fromMultimap.entries().iterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
1481 }
1482
1483 @Override
1484 public Collection<V2> get(final K key) {
1485 return transform(key, fromMultimap.get(key));
1486 }
1487
1488 @Override
1489 public boolean isEmpty() {
1490 return fromMultimap.isEmpty();
1491 }
1492
1493 @Override
1494 Set<K> createKeySet() {
1495 return fromMultimap.keySet();
1496 }
1497
1498 @Override
1499 Multiset<K> createKeys() {
1500 return fromMultimap.keys();
1501 }
1502
1503 @Override
1504 public boolean put(K key, V2 value) {
1505 throw new UnsupportedOperationException();
1506 }
1507
1508 @Override
1509 public boolean putAll(K key, Iterable<? extends V2> values) {
1510 throw new UnsupportedOperationException();
1511 }
1512
1513 @Override
1514 public boolean putAll(Multimap<? extends K, ? extends V2> multimap) {
1515 throw new UnsupportedOperationException();
1516 }
1517
1518 @SuppressWarnings("unchecked")
1519 @Override
1520 public boolean remove(Object key, Object value) {
1521 return get((K) key).remove(value);
1522 }
1523
1524 @SuppressWarnings("unchecked")
1525 @Override
1526 public Collection<V2> removeAll(Object key) {
1527 return transform((K) key, fromMultimap.removeAll(key));
1528 }
1529
1530 @Override
1531 public Collection<V2> replaceValues(K key, Iterable<? extends V2> values) {
1532 throw new UnsupportedOperationException();
1533 }
1534
1535 @Override
1536 public int size() {
1537 return fromMultimap.size();
1538 }
1539
1540 @Override
1541 Collection<V2> createValues() {
1542 return Collections2.transform(
1543 fromMultimap.entries(), Maps.<K, V1, V2>asEntryToValueFunction(transformer));
1544 }
1545 }
1546
1547 private static final class TransformedEntriesListMultimap<K, V1, V2>
1548 extends TransformedEntriesMultimap<K, V1, V2> implements ListMultimap<K, V2> {
1549
1550 TransformedEntriesListMultimap(
1551 ListMultimap<K, V1> fromMultimap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1552 super(fromMultimap, transformer);
1553 }
1554
1555 @Override
1556 List<V2> transform(K key, Collection<V1> values) {
1557 return Lists.transform((List<V1>) values, Maps.asValueToValueFunction(transformer, key));
1558 }
1559
1560 @Override
1561 public List<V2> get(K key) {
1562 return transform(key, fromMultimap.get(key));
1563 }
1564
1565 @SuppressWarnings("unchecked")
1566 @Override
1567 public List<V2> removeAll(Object key) {
1568 return transform((K) key, fromMultimap.removeAll(key));
1569 }
1570
1571 @Override
1572 public List<V2> replaceValues(K key, Iterable<? extends V2> values) {
1573 throw new UnsupportedOperationException();
1574 }
1575 }
1576
1577 /**
1578 * Creates an index {@code ImmutableListMultimap} that contains the results of applying a
1579 * specified function to each item in an {@code Iterable} of values. Each value will be stored as
1580 * a value in the resulting multimap, yielding a multimap with the same size as the input
1581 * iterable. The key used to store that value in the multimap will be the result of calling the
1582 * function on that value. The resulting multimap is created as an immutable snapshot. In the
1583 * returned multimap, keys appear in the order they are first encountered, and the values
1584 * corresponding to each key appear in the same order as they are encountered.
1585 *
1586 * <p>For example,
1587 *
1588 * <pre>{@code
1589 * List<String> badGuys =
1590 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1591 * Function<String, Integer> stringLengthFunction = ...;
1592 * Multimap<Integer, String> index =
1593 * Multimaps.index(badGuys, stringLengthFunction);
1594 * System.out.println(index);
1595 * }</pre>
1596 *
1597 * <p>prints
1598 *
1599 * <pre>{@code
1600 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}
1601 * }</pre>
1602 *
1603 * <p>The returned multimap is serializable if its keys and values are all serializable.
1604 *
1605 * @param values the values to use when constructing the {@code ImmutableListMultimap}
1606 * @param keyFunction the function used to produce the key for each value
1607 * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code
1608 * keyFunction} on each value in the input collection to that value
1609 * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1610 * keyFunction} produces {@code null} for any key
1611 */
1612 public static <K, V> ImmutableListMultimap<K, V> index(
1613 Iterable<V> values, Function<? super V, K> keyFunction) {
1614 return index(values.iterator(), keyFunction);
1615 }
1616
1617 /**
1618 * Creates an index {@code ImmutableListMultimap} that contains the results of applying a
1619 * specified function to each item in an {@code Iterator} of values. Each value will be stored as
1620 * a value in the resulting multimap, yielding a multimap with the same size as the input
1621 * iterator. The key used to store that value in the multimap will be the result of calling the
1622 * function on that value. The resulting multimap is created as an immutable snapshot. In the
1623 * returned multimap, keys appear in the order they are first encountered, and the values
1624 * corresponding to each key appear in the same order as they are encountered.
1625 *
1626 * <p>For example,
1627 *
1628 * <pre>{@code
1629 * List<String> badGuys =
1630 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1631 * Function<String, Integer> stringLengthFunction = ...;
1632 * Multimap<Integer, String> index =
1633 * Multimaps.index(badGuys.iterator(), stringLengthFunction);
1634 * System.out.println(index);
1635 * }</pre>
1636 *
1637 * <p>prints
1638 *
1639 * <pre>{@code
1640 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}
1641 * }</pre>
1642 *
1643 * <p>The returned multimap is serializable if its keys and values are all serializable.
1644 *
1645 * @param values the values to use when constructing the {@code ImmutableListMultimap}
1646 * @param keyFunction the function used to produce the key for each value
1647 * @return {@code ImmutableListMultimap} mapping the result of evaluating the function {@code
1648 * keyFunction} on each value in the input collection to that value
1649 * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1650 * keyFunction} produces {@code null} for any key
1651 * @since 10.0
1652 */
1653 public static <K, V> ImmutableListMultimap<K, V> index(
1654 Iterator<V> values, Function<? super V, K> keyFunction) {
1655 checkNotNull(keyFunction);
1656 ImmutableListMultimap.Builder<K, V> builder = ImmutableListMultimap.builder();
1657 while (values.hasNext()) {
1658 V value = values.next();
1659 checkNotNull(value, values);
1660 builder.put(keyFunction.apply(value), value);
1661 }
1662 return builder.build();
1663 }
1664
1665 static class Keys<K, V> extends AbstractMultiset<K> {
1666 @Weak final Multimap<K, V> multimap;
1667
1668 Keys(Multimap<K, V> multimap) {
1669 this.multimap = multimap;
1670 }
1671
1672 @Override
1673 Iterator<Multiset.Entry<K>> entryIterator() {
1674 return new TransformedIterator<Map.Entry<K, Collection<V>>, Multiset.Entry<K>>(
1675 multimap.asMap().entrySet().iterator()) {
1676 @Override
1677 Multiset.Entry<K> transform(final Map.Entry<K, Collection<V>> backingEntry) {
1678 return new Multisets.AbstractEntry<K>() {
1679 @Override
1680 public K getElement() {
1681 return backingEntry.getKey();
1682 }
1683
1684 @Override
1685 public int getCount() {
1686 return backingEntry.getValue().size();
1687 }
1688 };
1689 }
1690 };
1691 }
1692
1693 @Override
1694 public Spliterator<K> spliterator() {
1695 return CollectSpliterators.map(multimap.entries().spliterator(), Map.Entry::getKey);
1696 }
1697
1698 @Override
1699 public void forEach(Consumer<? super K> consumer) {
1700 checkNotNull(consumer);
1701 multimap.entries().forEach(entry -> consumer.accept(entry.getKey()));
1702 }
1703
1704 @Override
1705 int distinctElements() {
1706 return multimap.asMap().size();
1707 }
1708
1709 @Override
1710 public int size() {
1711 return multimap.size();
1712 }
1713
1714 @Override
1715 public boolean contains(@Nullable Object element) {
1716 return multimap.containsKey(element);
1717 }
1718
1719 @Override
1720 public Iterator<K> iterator() {
1721 return Maps.keyIterator(multimap.entries().iterator());
1722 }
1723
1724 @Override
1725 public int count(@Nullable Object element) {
1726 Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1727 return (values == null) ? 0 : values.size();
1728 }
1729
1730 @Override
1731 public int remove(@Nullable Object element, int occurrences) {
1732 checkNonnegative(occurrences, "occurrences");
1733 if (occurrences == 0) {
1734 return count(element);
1735 }
1736
1737 Collection<V> values = Maps.safeGet(multimap.asMap(), element);
1738
1739 if (values == null) {
1740 return 0;
1741 }
1742
1743 int oldCount = values.size();
1744 if (occurrences >= oldCount) {
1745 values.clear();
1746 } else {
1747 Iterator<V> iterator = values.iterator();
1748 for (int i = 0; i < occurrences; i++) {
1749 iterator.next();
1750 iterator.remove();
1751 }
1752 }
1753 return oldCount;
1754 }
1755
1756 @Override
1757 public void clear() {
1758 multimap.clear();
1759 }
1760
1761 @Override
1762 public Set<K> elementSet() {
1763 return multimap.keySet();
1764 }
1765
1766 @Override
1767 Iterator<K> elementIterator() {
1768 throw new AssertionError("should never be called");
1769 }
1770 }
1771
1772 /** A skeleton implementation of {@link Multimap#entries()}. */
1773 abstract static class Entries<K, V> extends AbstractCollection<Map.Entry<K, V>> {
1774 abstract Multimap<K, V> multimap();
1775
1776 @Override
1777 public int size() {
1778 return multimap().size();
1779 }
1780
1781 @Override
1782 public boolean contains(@Nullable Object o) {
1783 if (o instanceof Map.Entry) {
1784 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1785 return multimap().containsEntry(entry.getKey(), entry.getValue());
1786 }
1787 return false;
1788 }
1789
1790 @Override
1791 public boolean remove(@Nullable Object o) {
1792 if (o instanceof Map.Entry) {
1793 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1794 return multimap().remove(entry.getKey(), entry.getValue());
1795 }
1796 return false;
1797 }
1798
1799 @Override
1800 public void clear() {
1801 multimap().clear();
1802 }
1803 }
1804
1805 /** A skeleton implementation of {@link Multimap#asMap()}. */
1806 static final class AsMap<K, V> extends Maps.ViewCachingAbstractMap<K, Collection<V>> {
1807 @Weak private final Multimap<K, V> multimap;
1808
1809 AsMap(Multimap<K, V> multimap) {
1810 this.multimap = checkNotNull(multimap);
1811 }
1812
1813 @Override
1814 public int size() {
1815 return multimap.keySet().size();
1816 }
1817
1818 @Override
1819 protected Set<Entry<K, Collection<V>>> createEntrySet() {
1820 return new EntrySet();
1821 }
1822
1823 void removeValuesForKey(Object key) {
1824 multimap.keySet().remove(key);
1825 }
1826
1827 @WeakOuter
1828 class EntrySet extends Maps.EntrySet<K, Collection<V>> {
1829 @Override
1830 Map<K, Collection<V>> map() {
1831 return AsMap.this;
1832 }
1833
1834 @Override
1835 public Iterator<Entry<K, Collection<V>>> iterator() {
1836 return Maps.asMapEntryIterator(
1837 multimap.keySet(),
1838 new Function<K, Collection<V>>() {
1839 @Override
1840 public Collection<V> apply(K key) {
1841 return multimap.get(key);
1842 }
1843 });
1844 }
1845
1846 @Override
1847 public boolean remove(Object o) {
1848 if (!contains(o)) {
1849 return false;
1850 }
1851 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o;
1852 removeValuesForKey(entry.getKey());
1853 return true;
1854 }
1855 }
1856
1857 @SuppressWarnings("unchecked")
1858 @Override
1859 public Collection<V> get(Object key) {
1860 return containsKey(key) ? multimap.get((K) key) : null;
1861 }
1862
1863 @Override
1864 public Collection<V> remove(Object key) {
1865 return containsKey(key) ? multimap.removeAll(key) : null;
1866 }
1867
1868 @Override
1869 public Set<K> keySet() {
1870 return multimap.keySet();
1871 }
1872
1873 @Override
1874 public boolean isEmpty() {
1875 return multimap.isEmpty();
1876 }
1877
1878 @Override
1879 public boolean containsKey(Object key) {
1880 return multimap.containsKey(key);
1881 }
1882
1883 @Override
1884 public void clear() {
1885 multimap.clear();
1886 }
1887 }
1888
1889 /**
1890 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
1891 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
1892 * the other.
1893 *
1894 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
1895 * other methods are supported by the multimap and its views. When adding a key that doesn't
1896 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
1897 * replaceValues()} methods throw an {@link IllegalArgumentException}.
1898 *
1899 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
1900 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
1901 * underlying multimap.
1902 *
1903 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
1904 *
1905 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
1906 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
1907 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
1908 * copy.
1909 *
1910 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
1911 * {@link Predicate#apply}. Do not provide a predicate such as {@code
1912 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
1913 *
1914 * @since 11.0
1915 */
1916 public static <K, V> Multimap<K, V> filterKeys(
1917 Multimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1918 if (unfiltered instanceof SetMultimap) {
1919 return filterKeys((SetMultimap<K, V>) unfiltered, keyPredicate);
1920 } else if (unfiltered instanceof ListMultimap) {
1921 return filterKeys((ListMultimap<K, V>) unfiltered, keyPredicate);
1922 } else if (unfiltered instanceof FilteredKeyMultimap) {
1923 FilteredKeyMultimap<K, V> prev = (FilteredKeyMultimap<K, V>) unfiltered;
1924 return new FilteredKeyMultimap<>(
1925 prev.unfiltered, Predicates.<K>and(prev.keyPredicate, keyPredicate));
1926 } else if (unfiltered instanceof FilteredMultimap) {
1927 FilteredMultimap<K, V> prev = (FilteredMultimap<K, V>) unfiltered;
1928 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
1929 } else {
1930 return new FilteredKeyMultimap<>(unfiltered, keyPredicate);
1931 }
1932 }
1933
1934 /**
1935 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
1936 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
1937 * the other.
1938 *
1939 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
1940 * other methods are supported by the multimap and its views. When adding a key that doesn't
1941 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
1942 * replaceValues()} methods throw an {@link IllegalArgumentException}.
1943 *
1944 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
1945 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
1946 * underlying multimap.
1947 *
1948 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
1949 *
1950 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
1951 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
1952 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
1953 * copy.
1954 *
1955 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
1956 * {@link Predicate#apply}. Do not provide a predicate such as {@code
1957 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
1958 *
1959 * @since 14.0
1960 */
1961 public static <K, V> SetMultimap<K, V> filterKeys(
1962 SetMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
1963 if (unfiltered instanceof FilteredKeySetMultimap) {
1964 FilteredKeySetMultimap<K, V> prev = (FilteredKeySetMultimap<K, V>) unfiltered;
1965 return new FilteredKeySetMultimap<>(
1966 prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
1967 } else if (unfiltered instanceof FilteredSetMultimap) {
1968 FilteredSetMultimap<K, V> prev = (FilteredSetMultimap<K, V>) unfiltered;
1969 return filterFiltered(prev, Maps.<K>keyPredicateOnEntries(keyPredicate));
1970 } else {
1971 return new FilteredKeySetMultimap<>(unfiltered, keyPredicate);
1972 }
1973 }
1974
1975 /**
1976 * Returns a multimap containing the mappings in {@code unfiltered} whose keys satisfy a
1977 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
1978 * the other.
1979 *
1980 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
1981 * other methods are supported by the multimap and its views. When adding a key that doesn't
1982 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
1983 * replaceValues()} methods throw an {@link IllegalArgumentException}.
1984 *
1985 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
1986 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
1987 * underlying multimap.
1988 *
1989 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
1990 *
1991 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
1992 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
1993 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
1994 * copy.
1995 *
1996 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
1997 * {@link Predicate#apply}. Do not provide a predicate such as {@code
1998 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
1999 *
2000 * @since 14.0
2001 */
2002 public static <K, V> ListMultimap<K, V> filterKeys(
2003 ListMultimap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2004 if (unfiltered instanceof FilteredKeyListMultimap) {
2005 FilteredKeyListMultimap<K, V> prev = (FilteredKeyListMultimap<K, V>) unfiltered;
2006 return new FilteredKeyListMultimap<>(
2007 prev.unfiltered(), Predicates.<K>and(prev.keyPredicate, keyPredicate));
2008 } else {
2009 return new FilteredKeyListMultimap<>(unfiltered, keyPredicate);
2010 }
2011 }
2012
2013 /**
2014 * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a
2015 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
2016 * the other.
2017 *
2018 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2019 * other methods are supported by the multimap and its views. When adding a value that doesn't
2020 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
2021 * replaceValues()} methods throw an {@link IllegalArgumentException}.
2022 *
2023 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2024 * multimap or its views, only mappings whose value satisfy the filter will be removed from the
2025 * underlying multimap.
2026 *
2027 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2028 *
2029 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2030 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2031 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2032 * copy.
2033 *
2034 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2035 * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2036 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2037 *
2038 * @since 11.0
2039 */
2040 public static <K, V> Multimap<K, V> filterValues(
2041 Multimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2042 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2043 }
2044
2045 /**
2046 * Returns a multimap containing the mappings in {@code unfiltered} whose values satisfy a
2047 * predicate. The returned multimap is a live view of {@code unfiltered}; changes to one affect
2048 * the other.
2049 *
2050 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2051 * other methods are supported by the multimap and its views. When adding a value that doesn't
2052 * satisfy the predicate, the multimap's {@code put()}, {@code putAll()}, and {@code
2053 * replaceValues()} methods throw an {@link IllegalArgumentException}.
2054 *
2055 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2056 * multimap or its views, only mappings whose value satisfy the filter will be removed from the
2057 * underlying multimap.
2058 *
2059 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2060 *
2061 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2062 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2063 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2064 * copy.
2065 *
2066 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2067 * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2068 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2069 *
2070 * @since 14.0
2071 */
2072 public static <K, V> SetMultimap<K, V> filterValues(
2073 SetMultimap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2074 return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2075 }
2076
2077 /**
2078 * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2079 * returned multimap is a live view of {@code unfiltered}; changes to one affect the other.
2080 *
2081 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2082 * other methods are supported by the multimap and its views. When adding a key/value pair that
2083 * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code
2084 * replaceValues()} methods throw an {@link IllegalArgumentException}.
2085 *
2086 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2087 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
2088 * underlying multimap.
2089 *
2090 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2091 *
2092 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2093 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2094 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2095 * copy.
2096 *
2097 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2098 * at {@link Predicate#apply}.
2099 *
2100 * @since 11.0
2101 */
2102 public static <K, V> Multimap<K, V> filterEntries(
2103 Multimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2104 checkNotNull(entryPredicate);
2105 if (unfiltered instanceof SetMultimap) {
2106 return filterEntries((SetMultimap<K, V>) unfiltered, entryPredicate);
2107 }
2108 return (unfiltered instanceof FilteredMultimap)
2109 ? filterFiltered((FilteredMultimap<K, V>) unfiltered, entryPredicate)
2110 : new FilteredEntryMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2111 }
2112
2113 /**
2114 * Returns a multimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2115 * returned multimap is a live view of {@code unfiltered}; changes to one affect the other.
2116 *
2117 * <p>The resulting multimap's views have iterators that don't support {@code remove()}, but all
2118 * other methods are supported by the multimap and its views. When adding a key/value pair that
2119 * doesn't satisfy the predicate, multimap's {@code put()}, {@code putAll()}, and {@code
2120 * replaceValues()} methods throw an {@link IllegalArgumentException}.
2121 *
2122 * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2123 * multimap or its views, only mappings whose keys satisfy the filter will be removed from the
2124 * underlying multimap.
2125 *
2126 * <p>The returned multimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2127 *
2128 * <p>Many of the filtered multimap's methods, such as {@code size()}, iterate across every
2129 * key/value mapping in the underlying multimap and determine which satisfy the filter. When a
2130 * live view is <i>not</i> needed, it may be faster to copy the filtered multimap and use the
2131 * copy.
2132 *
2133 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2134 * at {@link Predicate#apply}.
2135 *
2136 * @since 14.0
2137 */
2138 public static <K, V> SetMultimap<K, V> filterEntries(
2139 SetMultimap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2140 checkNotNull(entryPredicate);
2141 return (unfiltered instanceof FilteredSetMultimap)
2142 ? filterFiltered((FilteredSetMultimap<K, V>) unfiltered, entryPredicate)
2143 : new FilteredEntrySetMultimap<K, V>(checkNotNull(unfiltered), entryPredicate);
2144 }
2145
2146 /**
2147 * Support removal operations when filtering a filtered multimap. Since a filtered multimap has
2148 * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would
2149 * lead to a multimap whose removal operations would fail. This method combines the predicates to
2150 * avoid that problem.
2151 */
2152 private static <K, V> Multimap<K, V> filterFiltered(
2153 FilteredMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) {
2154 Predicate<Entry<K, V>> predicate =
2155 Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate);
2156 return new FilteredEntryMultimap<>(multimap.unfiltered(), predicate);
2157 }
2158
2159 /**
2160 * Support removal operations when filtering a filtered multimap. Since a filtered multimap has
2161 * iterators that don't support remove, passing one to the FilteredEntryMultimap constructor would
2162 * lead to a multimap whose removal operations would fail. This method combines the predicates to
2163 * avoid that problem.
2164 */
2165 private static <K, V> SetMultimap<K, V> filterFiltered(
2166 FilteredSetMultimap<K, V> multimap, Predicate<? super Entry<K, V>> entryPredicate) {
2167 Predicate<Entry<K, V>> predicate =
2168 Predicates.<Entry<K, V>>and(multimap.entryPredicate(), entryPredicate);
2169 return new FilteredEntrySetMultimap<>(multimap.unfiltered(), predicate);
2170 }
2171
2172 static boolean equalsImpl(Multimap<?, ?> multimap, @Nullable Object object) {
2173 if (object == multimap) {
2174 return true;
2175 }
2176 if (object instanceof Multimap) {
2177 Multimap<?, ?> that = (Multimap<?, ?>) object;
2178 return multimap.asMap().equals(that.asMap());
2179 }
2180 return false;
2181 }
2182
2183 // TODO(jlevy): Create methods that filter a SortedSetMultimap.
2184 }