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