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