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.checkNotNull;
020 import static com.google.common.base.Preconditions.checkState;
021
022 import com.google.common.annotations.Beta;
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Function;
026 import com.google.common.base.Joiner;
027 import com.google.common.base.Joiner.MapJoiner;
028 import com.google.common.base.Supplier;
029 import com.google.common.collect.Collections2.TransformedCollection;
030 import com.google.common.collect.Maps.EntryTransformer;
031
032 import java.io.IOException;
033 import java.io.ObjectInputStream;
034 import java.io.ObjectOutputStream;
035 import java.io.Serializable;
036 import java.util.AbstractSet;
037 import java.util.Collection;
038 import java.util.Collections;
039 import java.util.Comparator;
040 import java.util.HashSet;
041 import java.util.Iterator;
042 import java.util.List;
043 import java.util.Map;
044 import java.util.Map.Entry;
045 import java.util.NoSuchElementException;
046 import java.util.Set;
047 import java.util.SortedSet;
048
049 import javax.annotation.Nullable;
050
051 /**
052 * Provides static methods acting on or generating a {@code Multimap}.
053 *
054 * @author Jared Levy
055 * @author Robert Konigsberg
056 * @author Mike Bostock
057 * @author Louis Wasserman
058 * @since 2 (imported from Google Collections Library)
059 */
060 @GwtCompatible(emulated = true)
061 public final class Multimaps {
062 private Multimaps() {}
063
064 /**
065 * Creates a new {@code Multimap} that uses the provided map and factory. It
066 * can generate a multimap based on arbitrary {@link Map} and
067 * {@link Collection} classes.
068 *
069 * <p>The {@code factory}-generated and {@code map} classes determine the
070 * multimap iteration order. They also specify the behavior of the
071 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
072 * multimap and its returned views. However, the multimap's {@code get}
073 * method returns instances of a different class than {@code factory.get()}
074 * does.
075 *
076 * <p>The multimap is serializable if {@code map}, {@code factory}, the
077 * collections generated by {@code factory}, and the multimap contents are all
078 * serializable.
079 *
080 * <p>The multimap is not threadsafe when any concurrent operations update the
081 * multimap, even if {@code map} and the instances generated by
082 * {@code factory} are. Concurrent read operations will work correctly. To
083 * allow concurrent update operations, wrap the multimap with a call to
084 * {@link #synchronizedMultimap}.
085 *
086 * <p>Call this method only when the simpler methods
087 * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()},
088 * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()},
089 * {@link TreeMultimap#create()}, and
090 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
091 *
092 * <p>Note: the multimap assumes complete ownership over of {@code map} and
093 * the collections returned by {@code factory}. Those objects should not be
094 * manually updated and they should not use soft, weak, or phantom references.
095 *
096 * @param map place to store the mapping from each key to its corresponding
097 * values
098 * @param factory supplier of new, empty collections that will each hold all
099 * values for a given key
100 * @throws IllegalArgumentException if {@code map} is not empty
101 */
102 public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
103 final Supplier<? extends Collection<V>> factory) {
104 return new CustomMultimap<K, V>(map, factory);
105 }
106
107 private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> {
108 transient Supplier<? extends Collection<V>> factory;
109
110 CustomMultimap(Map<K, Collection<V>> map,
111 Supplier<? extends Collection<V>> factory) {
112 super(map);
113 this.factory = checkNotNull(factory);
114 }
115
116 @Override protected Collection<V> createCollection() {
117 return factory.get();
118 }
119
120 // can't use Serialization writeMultimap and populateMultimap methods since
121 // there's no way to generate the empty backing map.
122
123 /** @serialData the factory and the backing map */
124 @GwtIncompatible("java.io.ObjectOutputStream")
125 private void writeObject(ObjectOutputStream stream) throws IOException {
126 stream.defaultWriteObject();
127 stream.writeObject(factory);
128 stream.writeObject(backingMap());
129 }
130
131 @GwtIncompatible("java.io.ObjectInputStream")
132 @SuppressWarnings("unchecked") // reading data stored by writeObject
133 private void readObject(ObjectInputStream stream)
134 throws IOException, ClassNotFoundException {
135 stream.defaultReadObject();
136 factory = (Supplier<? extends Collection<V>>) stream.readObject();
137 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
138 setMap(map);
139 }
140
141 @GwtIncompatible("java serialization not supported")
142 private static final long serialVersionUID = 0;
143 }
144
145 /**
146 * Creates a new {@code ListMultimap} that uses the provided map and factory.
147 * It can generate a multimap based on arbitrary {@link Map} and {@link List}
148 * classes.
149 *
150 * <p>The {@code factory}-generated and {@code map} classes determine the
151 * multimap iteration order. They also specify the behavior of the
152 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
153 * multimap and its returned views. The multimap's {@code get}, {@code
154 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess}
155 * lists if the factory does. However, the multimap's {@code get} method
156 * returns instances of a different class than does {@code factory.get()}.
157 *
158 * <p>The multimap is serializable if {@code map}, {@code factory}, the
159 * lists generated by {@code factory}, and the multimap contents are all
160 * serializable.
161 *
162 * <p>The multimap is not threadsafe when any concurrent operations update the
163 * multimap, even if {@code map} and the instances generated by
164 * {@code factory} are. Concurrent read operations will work correctly. To
165 * allow concurrent update operations, wrap the multimap with a call to
166 * {@link #synchronizedListMultimap}.
167 *
168 * <p>Call this method only when the simpler methods
169 * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()}
170 * won't suffice.
171 *
172 * <p>Note: the multimap assumes complete ownership over of {@code map} and
173 * the lists returned by {@code factory}. Those objects should not be manually
174 * updated and they should not use soft, weak, or phantom references.
175 *
176 * @param map place to store the mapping from each key to its corresponding
177 * values
178 * @param factory supplier of new, empty lists that will each hold all values
179 * for a given key
180 * @throws IllegalArgumentException if {@code map} is not empty
181 */
182 public static <K, V> ListMultimap<K, V> newListMultimap(
183 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
184 return new CustomListMultimap<K, V>(map, factory);
185 }
186
187 private static class CustomListMultimap<K, V>
188 extends AbstractListMultimap<K, V> {
189 transient Supplier<? extends List<V>> factory;
190
191 CustomListMultimap(Map<K, Collection<V>> map,
192 Supplier<? extends List<V>> factory) {
193 super(map);
194 this.factory = checkNotNull(factory);
195 }
196
197 @Override protected List<V> createCollection() {
198 return factory.get();
199 }
200
201 /** @serialData the factory and the backing map */
202 @GwtIncompatible("java.io.ObjectOutputStream")
203 private void writeObject(ObjectOutputStream stream) throws IOException {
204 stream.defaultWriteObject();
205 stream.writeObject(factory);
206 stream.writeObject(backingMap());
207 }
208
209 @GwtIncompatible("java.io.ObjectInputStream")
210 @SuppressWarnings("unchecked") // reading data stored by writeObject
211 private void readObject(ObjectInputStream stream)
212 throws IOException, ClassNotFoundException {
213 stream.defaultReadObject();
214 factory = (Supplier<? extends List<V>>) stream.readObject();
215 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
216 setMap(map);
217 }
218
219 @GwtIncompatible("java serialization not supported")
220 private static final long serialVersionUID = 0;
221 }
222
223 /**
224 * Creates a new {@code SetMultimap} that uses the provided map and factory.
225 * It can generate a multimap based on arbitrary {@link Map} and {@link Set}
226 * classes.
227 *
228 * <p>The {@code factory}-generated and {@code map} classes determine the
229 * multimap iteration order. They also specify the behavior of the
230 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
231 * multimap and its returned views. However, the multimap's {@code get}
232 * method returns instances of a different class than {@code factory.get()}
233 * does.
234 *
235 * <p>The multimap is serializable if {@code map}, {@code factory}, the
236 * sets generated by {@code factory}, and the multimap contents are all
237 * serializable.
238 *
239 * <p>The multimap is not threadsafe when any concurrent operations update the
240 * multimap, even if {@code map} and the instances generated by
241 * {@code factory} are. Concurrent read operations will work correctly. To
242 * allow concurrent update operations, wrap the multimap with a call to
243 * {@link #synchronizedSetMultimap}.
244 *
245 * <p>Call this method only when the simpler methods
246 * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()},
247 * {@link TreeMultimap#create()}, and
248 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
249 *
250 * <p>Note: the multimap assumes complete ownership over of {@code map} and
251 * the sets returned by {@code factory}. Those objects should not be manually
252 * updated and they should not use soft, weak, or phantom references.
253 *
254 * @param map place to store the mapping from each key to its corresponding
255 * values
256 * @param factory supplier of new, empty sets that will each hold all values
257 * for a given key
258 * @throws IllegalArgumentException if {@code map} is not empty
259 */
260 public static <K, V> SetMultimap<K, V> newSetMultimap(
261 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
262 return new CustomSetMultimap<K, V>(map, factory);
263 }
264
265 private static class CustomSetMultimap<K, V>
266 extends AbstractSetMultimap<K, V> {
267 transient Supplier<? extends Set<V>> factory;
268
269 CustomSetMultimap(Map<K, Collection<V>> map,
270 Supplier<? extends Set<V>> factory) {
271 super(map);
272 this.factory = checkNotNull(factory);
273 }
274
275 @Override protected Set<V> createCollection() {
276 return factory.get();
277 }
278
279 /** @serialData the factory and the backing map */
280 @GwtIncompatible("java.io.ObjectOutputStream")
281 private void writeObject(ObjectOutputStream stream) throws IOException {
282 stream.defaultWriteObject();
283 stream.writeObject(factory);
284 stream.writeObject(backingMap());
285 }
286
287 @GwtIncompatible("java.io.ObjectInputStream")
288 @SuppressWarnings("unchecked") // reading data stored by writeObject
289 private void readObject(ObjectInputStream stream)
290 throws IOException, ClassNotFoundException {
291 stream.defaultReadObject();
292 factory = (Supplier<? extends Set<V>>) stream.readObject();
293 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
294 setMap(map);
295 }
296
297 @GwtIncompatible("not needed in emulated source")
298 private static final long serialVersionUID = 0;
299 }
300
301 /**
302 * Creates a new {@code SortedSetMultimap} that uses the provided map and
303 * factory. It can generate a multimap based on arbitrary {@link Map} and
304 * {@link SortedSet} classes.
305 *
306 * <p>The {@code factory}-generated and {@code map} classes determine the
307 * multimap iteration order. They also specify the behavior of the
308 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
309 * multimap and its returned views. However, the multimap's {@code get}
310 * method returns instances of a different class than {@code factory.get()}
311 * does.
312 *
313 * <p>The multimap is serializable if {@code map}, {@code factory}, the
314 * sets generated by {@code factory}, and the multimap contents are all
315 * serializable.
316 *
317 * <p>The multimap is not threadsafe when any concurrent operations update the
318 * multimap, even if {@code map} and the instances generated by
319 * {@code factory} are. Concurrent read operations will work correctly. To
320 * allow concurrent update operations, wrap the multimap with a call to
321 * {@link #synchronizedSortedSetMultimap}.
322 *
323 * <p>Call this method only when the simpler methods
324 * {@link TreeMultimap#create()} and
325 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
326 *
327 * <p>Note: the multimap assumes complete ownership over of {@code map} and
328 * the sets returned by {@code factory}. Those objects should not be manually
329 * updated and they should not use soft, weak, or phantom references.
330 *
331 * @param map place to store the mapping from each key to its corresponding
332 * values
333 * @param factory supplier of new, empty sorted sets that will each hold
334 * all values for a given key
335 * @throws IllegalArgumentException if {@code map} is not empty
336 */
337 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
338 Map<K, Collection<V>> map,
339 final Supplier<? extends SortedSet<V>> factory) {
340 return new CustomSortedSetMultimap<K, V>(map, factory);
341 }
342
343 private static class CustomSortedSetMultimap<K, V>
344 extends AbstractSortedSetMultimap<K, V> {
345 transient Supplier<? extends SortedSet<V>> factory;
346 transient Comparator<? super V> valueComparator;
347
348 CustomSortedSetMultimap(Map<K, Collection<V>> map,
349 Supplier<? extends SortedSet<V>> factory) {
350 super(map);
351 this.factory = checkNotNull(factory);
352 valueComparator = factory.get().comparator();
353 }
354
355 @Override protected SortedSet<V> createCollection() {
356 return factory.get();
357 }
358
359 @Override public Comparator<? super V> valueComparator() {
360 return valueComparator;
361 }
362
363 /** @serialData the factory and the backing map */
364 @GwtIncompatible("java.io.ObjectOutputStream")
365 private void writeObject(ObjectOutputStream stream) throws IOException {
366 stream.defaultWriteObject();
367 stream.writeObject(factory);
368 stream.writeObject(backingMap());
369 }
370
371 @GwtIncompatible("java.io.ObjectInputStream")
372 @SuppressWarnings("unchecked") // reading data stored by writeObject
373 private void readObject(ObjectInputStream stream)
374 throws IOException, ClassNotFoundException {
375 stream.defaultReadObject();
376 factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
377 valueComparator = factory.get().comparator();
378 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
379 setMap(map);
380 }
381
382 @GwtIncompatible("not needed in emulated source")
383 private static final long serialVersionUID = 0;
384 }
385
386 /**
387 * Copies each key-value mapping in {@code source} into {@code dest}, with
388 * its key and value reversed.
389 *
390 * @param source any multimap
391 * @param dest the multimap to copy into; usually empty
392 * @return {@code dest}
393 */
394 public static <K, V, M extends Multimap<K, V>> M invertFrom(
395 Multimap<? extends V, ? extends K> source, M dest) {
396 checkNotNull(dest);
397 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
398 dest.put(entry.getValue(), entry.getKey());
399 }
400 return dest;
401 }
402
403 /**
404 * Returns a synchronized (thread-safe) multimap backed by the specified
405 * multimap. In order to guarantee serial access, it is critical that
406 * <b>all</b> access to the backing multimap is accomplished through the
407 * returned multimap.
408 *
409 * <p>It is imperative that the user manually synchronize on the returned
410 * multimap when accessing any of its collection views: <pre> {@code
411 *
412 * Multimap<K, V> m = Multimaps.synchronizedMultimap(
413 * HashMultimap.<K, V>create());
414 * ...
415 * Set<K> s = m.keySet(); // Needn't be in synchronized block
416 * ...
417 * synchronized (m) { // Synchronizing on m, not s!
418 * Iterator<K> i = s.iterator(); // Must be in synchronized block
419 * while (i.hasNext()) {
420 * foo(i.next());
421 * }
422 * }}</pre>
423 *
424 * Failure to follow this advice may result in non-deterministic behavior.
425 *
426 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
427 * {@link Multimap#replaceValues} methods return collections that aren't
428 * synchronized.
429 *
430 * <p>The returned multimap will be serializable if the specified multimap is
431 * serializable.
432 *
433 * @param multimap the multimap to be wrapped in a synchronized view
434 * @return a synchronized view of the specified multimap
435 */
436 public static <K, V> Multimap<K, V> synchronizedMultimap(
437 Multimap<K, V> multimap) {
438 return Synchronized.multimap(multimap, null);
439 }
440
441 /**
442 * Returns an unmodifiable view of the specified multimap. Query operations on
443 * the returned multimap "read through" to the specified multimap, and
444 * attempts to modify the returned multimap, either directly or through the
445 * multimap's views, result in an {@code UnsupportedOperationException}.
446 *
447 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
448 * {@link Multimap#replaceValues} methods return collections that are
449 * modifiable.
450 *
451 * <p>The returned multimap will be serializable if the specified multimap is
452 * serializable.
453 *
454 * @param delegate the multimap for which an unmodifiable view is to be
455 * returned
456 * @return an unmodifiable view of the specified multimap
457 */
458 public static <K, V> Multimap<K, V> unmodifiableMultimap(
459 Multimap<K, V> delegate) {
460 return new UnmodifiableMultimap<K, V>(delegate);
461 }
462
463 private static class UnmodifiableMultimap<K, V>
464 extends ForwardingMultimap<K, V> implements Serializable {
465 final Multimap<K, V> delegate;
466 transient Collection<Entry<K, V>> entries;
467 transient Multiset<K> keys;
468 transient Set<K> keySet;
469 transient Collection<V> values;
470 transient Map<K, Collection<V>> map;
471
472 UnmodifiableMultimap(final Multimap<K, V> delegate) {
473 this.delegate = checkNotNull(delegate);
474 }
475
476 @Override protected Multimap<K, V> delegate() {
477 return delegate;
478 }
479
480 @Override public void clear() {
481 throw new UnsupportedOperationException();
482 }
483
484 @Override public Map<K, Collection<V>> asMap() {
485 Map<K, Collection<V>> result = map;
486 if (result == null) {
487 final Map<K, Collection<V>> unmodifiableMap
488 = Collections.unmodifiableMap(delegate.asMap());
489 map = result = new ForwardingMap<K, Collection<V>>() {
490 @Override protected Map<K, Collection<V>> delegate() {
491 return unmodifiableMap;
492 }
493
494 Set<Entry<K, Collection<V>>> entrySet;
495
496 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
497 Set<Entry<K, Collection<V>>> result = entrySet;
498 return (result == null)
499 ? entrySet
500 = unmodifiableAsMapEntries(unmodifiableMap.entrySet())
501 : result;
502 }
503
504 @Override public Collection<V> get(Object key) {
505 Collection<V> collection = unmodifiableMap.get(key);
506 return (collection == null)
507 ? null : unmodifiableValueCollection(collection);
508 }
509
510 Collection<Collection<V>> asMapValues;
511
512 @Override public Collection<Collection<V>> values() {
513 Collection<Collection<V>> result = asMapValues;
514 return (result == null)
515 ? asMapValues
516 = new UnmodifiableAsMapValues<V>(unmodifiableMap.values())
517 : result;
518 }
519
520 @Override public boolean containsValue(Object o) {
521 return values().contains(o);
522 }
523 };
524 }
525 return result;
526 }
527
528 @Override public Collection<Entry<K, V>> entries() {
529 Collection<Entry<K, V>> result = entries;
530 if (result == null) {
531 entries = result = unmodifiableEntries(delegate.entries());
532 }
533 return result;
534 }
535
536 @Override public Collection<V> get(K key) {
537 return unmodifiableValueCollection(delegate.get(key));
538 }
539
540 @Override public Multiset<K> keys() {
541 Multiset<K> result = keys;
542 if (result == null) {
543 keys = result = Multisets.unmodifiableMultiset(delegate.keys());
544 }
545 return result;
546 }
547
548 @Override public Set<K> keySet() {
549 Set<K> result = keySet;
550 if (result == null) {
551 keySet = result = Collections.unmodifiableSet(delegate.keySet());
552 }
553 return result;
554 }
555
556 @Override public boolean put(K key, V value) {
557 throw new UnsupportedOperationException();
558 }
559
560 @Override public boolean putAll(K key,
561 @SuppressWarnings("hiding") Iterable<? extends V> values) {
562 throw new UnsupportedOperationException();
563 }
564
565 @Override
566 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
567 throw new UnsupportedOperationException();
568 }
569
570 @Override public boolean remove(Object key, Object value) {
571 throw new UnsupportedOperationException();
572 }
573
574 @Override public Collection<V> removeAll(Object key) {
575 throw new UnsupportedOperationException();
576 }
577
578 @Override public Collection<V> replaceValues(K key,
579 @SuppressWarnings("hiding") Iterable<? extends V> values) {
580 throw new UnsupportedOperationException();
581 }
582
583 @Override public Collection<V> values() {
584 Collection<V> result = values;
585 if (result == null) {
586 values = result = Collections.unmodifiableCollection(delegate.values());
587 }
588 return result;
589 }
590
591 private static final long serialVersionUID = 0;
592 }
593
594 private static class UnmodifiableAsMapValues<V>
595 extends ForwardingCollection<Collection<V>> {
596 final Collection<Collection<V>> delegate;
597 UnmodifiableAsMapValues(Collection<Collection<V>> delegate) {
598 this.delegate = Collections.unmodifiableCollection(delegate);
599 }
600 @Override protected Collection<Collection<V>> delegate() {
601 return delegate;
602 }
603 @Override public Iterator<Collection<V>> iterator() {
604 final Iterator<Collection<V>> iterator = delegate.iterator();
605 return new Iterator<Collection<V>>() {
606 @Override
607 public boolean hasNext() {
608 return iterator.hasNext();
609 }
610 @Override
611 public Collection<V> next() {
612 return unmodifiableValueCollection(iterator.next());
613 }
614 @Override
615 public void remove() {
616 throw new UnsupportedOperationException();
617 }
618 };
619 }
620 @Override public Object[] toArray() {
621 return standardToArray();
622 }
623 @Override public <T> T[] toArray(T[] array) {
624 return standardToArray(array);
625 }
626 @Override public boolean contains(Object o) {
627 return standardContains(o);
628 }
629 @Override public boolean containsAll(Collection<?> c) {
630 return standardContainsAll(c);
631 }
632 }
633
634 private static class UnmodifiableListMultimap<K, V>
635 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
636 UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
637 super(delegate);
638 }
639 @Override public ListMultimap<K, V> delegate() {
640 return (ListMultimap<K, V>) super.delegate();
641 }
642 @Override public List<V> get(K key) {
643 return Collections.unmodifiableList(delegate().get(key));
644 }
645 @Override public List<V> removeAll(Object key) {
646 throw new UnsupportedOperationException();
647 }
648 @Override public List<V> replaceValues(
649 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
650 throw new UnsupportedOperationException();
651 }
652 private static final long serialVersionUID = 0;
653 }
654
655 private static class UnmodifiableSetMultimap<K, V>
656 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
657 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
658 super(delegate);
659 }
660 @Override public SetMultimap<K, V> delegate() {
661 return (SetMultimap<K, V>) super.delegate();
662 }
663 @Override public Set<V> get(K key) {
664 /*
665 * Note that this doesn't return a SortedSet when delegate is a
666 * SortedSetMultiset, unlike (SortedSet<V>) super.get().
667 */
668 return Collections.unmodifiableSet(delegate().get(key));
669 }
670 @Override public Set<Map.Entry<K, V>> entries() {
671 return Maps.unmodifiableEntrySet(delegate().entries());
672 }
673 @Override public Set<V> removeAll(Object key) {
674 throw new UnsupportedOperationException();
675 }
676 @Override public Set<V> replaceValues(
677 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
678 throw new UnsupportedOperationException();
679 }
680 private static final long serialVersionUID = 0;
681 }
682
683 private static class UnmodifiableSortedSetMultimap<K, V>
684 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
685 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
686 super(delegate);
687 }
688 @Override public SortedSetMultimap<K, V> delegate() {
689 return (SortedSetMultimap<K, V>) super.delegate();
690 }
691 @Override public SortedSet<V> get(K key) {
692 return Collections.unmodifiableSortedSet(delegate().get(key));
693 }
694 @Override public SortedSet<V> removeAll(Object key) {
695 throw new UnsupportedOperationException();
696 }
697 @Override public SortedSet<V> replaceValues(
698 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
699 throw new UnsupportedOperationException();
700 }
701 @Override
702 public Comparator<? super V> valueComparator() {
703 return delegate().valueComparator();
704 }
705 private static final long serialVersionUID = 0;
706 }
707
708 /**
709 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the
710 * specified multimap.
711 *
712 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
713 *
714 * <p>The returned multimap will be serializable if the specified multimap is
715 * serializable.
716 *
717 * @param multimap the multimap to be wrapped
718 * @return a synchronized view of the specified multimap
719 */
720 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
721 SetMultimap<K, V> multimap) {
722 return Synchronized.setMultimap(multimap, null);
723 }
724
725 /**
726 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query
727 * operations on the returned multimap "read through" to the specified
728 * multimap, and attempts to modify the returned multimap, either directly or
729 * through the multimap's views, result in an
730 * {@code UnsupportedOperationException}.
731 *
732 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
733 * {@link Multimap#replaceValues} methods return collections that are
734 * modifiable.
735 *
736 * <p>The returned multimap will be serializable if the specified multimap is
737 * serializable.
738 *
739 * @param delegate the multimap for which an unmodifiable view is to be
740 * returned
741 * @return an unmodifiable view of the specified multimap
742 */
743 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
744 SetMultimap<K, V> delegate) {
745 return new UnmodifiableSetMultimap<K, V>(delegate);
746 }
747
748 /**
749 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by
750 * the specified multimap.
751 *
752 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
753 *
754 * <p>The returned multimap will be serializable if the specified multimap is
755 * serializable.
756 *
757 * @param multimap the multimap to be wrapped
758 * @return a synchronized view of the specified multimap
759 */
760 public static <K, V> SortedSetMultimap<K, V>
761 synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
762 return Synchronized.sortedSetMultimap(multimap, null);
763 }
764
765 /**
766 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}.
767 * Query operations on the returned multimap "read through" to the specified
768 * multimap, and attempts to modify the returned multimap, either directly or
769 * through the multimap's views, result in an
770 * {@code UnsupportedOperationException}.
771 *
772 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
773 * {@link Multimap#replaceValues} methods return collections that are
774 * modifiable.
775 *
776 * <p>The returned multimap will be serializable if the specified multimap is
777 * serializable.
778 *
779 * @param delegate the multimap for which an unmodifiable view is to be
780 * returned
781 * @return an unmodifiable view of the specified multimap
782 */
783 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
784 SortedSetMultimap<K, V> delegate) {
785 return new UnmodifiableSortedSetMultimap<K, V>(delegate);
786 }
787
788 /**
789 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the
790 * specified multimap.
791 *
792 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
793 *
794 * @param multimap the multimap to be wrapped
795 * @return a synchronized view of the specified multimap
796 */
797 public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
798 ListMultimap<K, V> multimap) {
799 return Synchronized.listMultimap(multimap, null);
800 }
801
802 /**
803 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query
804 * operations on the returned multimap "read through" to the specified
805 * multimap, and attempts to modify the returned multimap, either directly or
806 * through the multimap's views, result in an
807 * {@code UnsupportedOperationException}.
808 *
809 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
810 * {@link Multimap#replaceValues} methods return collections that are
811 * modifiable.
812 *
813 * <p>The returned multimap will be serializable if the specified multimap is
814 * serializable.
815 *
816 * @param delegate the multimap for which an unmodifiable view is to be
817 * returned
818 * @return an unmodifiable view of the specified multimap
819 */
820 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
821 ListMultimap<K, V> delegate) {
822 return new UnmodifiableListMultimap<K, V>(delegate);
823 }
824
825 /**
826 * Returns an unmodifiable view of the specified collection, preserving the
827 * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and
828 * {@code Collection}, in that order of preference.
829 *
830 * @param collection the collection for which to return an unmodifiable view
831 * @return an unmodifiable view of the collection
832 */
833 private static <V> Collection<V> unmodifiableValueCollection(
834 Collection<V> collection) {
835 if (collection instanceof SortedSet) {
836 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
837 } else if (collection instanceof Set) {
838 return Collections.unmodifiableSet((Set<V>) collection);
839 } else if (collection instanceof List) {
840 return Collections.unmodifiableList((List<V>) collection);
841 }
842 return Collections.unmodifiableCollection(collection);
843 }
844
845 /**
846 * Returns an unmodifiable view of the specified multimap {@code asMap} entry.
847 * The {@link Entry#setValue} operation throws an {@link
848 * UnsupportedOperationException}, and the collection returned by {@code
849 * getValue} is also an unmodifiable (type-preserving) view. This also has the
850 * side-effect of redefining equals to comply with the Map.Entry contract, and
851 * to avoid a possible nefarious implementation of equals.
852 *
853 * @param entry the entry for which to return an unmodifiable view
854 * @return an unmodifiable view of the entry
855 */
856 private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry(
857 final Map.Entry<K, Collection<V>> entry) {
858 checkNotNull(entry);
859 return new AbstractMapEntry<K, Collection<V>>() {
860 @Override public K getKey() {
861 return entry.getKey();
862 }
863
864 @Override public Collection<V> getValue() {
865 return unmodifiableValueCollection(entry.getValue());
866 }
867 };
868 }
869
870 /**
871 * Returns an unmodifiable view of the specified collection of entries. The
872 * {@link Entry#setValue} operation throws an {@link
873 * UnsupportedOperationException}. If the specified collection is a {@code
874 * Set}, the returned collection is also a {@code Set}.
875 *
876 * @param entries the entries for which to return an unmodifiable view
877 * @return an unmodifiable view of the entries
878 */
879 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
880 Collection<Entry<K, V>> entries) {
881 if (entries instanceof Set) {
882 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
883 }
884 return new Maps.UnmodifiableEntries<K, V>(
885 Collections.unmodifiableCollection(entries));
886 }
887
888 /**
889 * Returns an unmodifiable view of the specified set of {@code asMap} entries.
890 * The {@link Entry#setValue} operation throws an {@link
891 * UnsupportedOperationException}, as do any operations that attempt to modify
892 * the returned collection.
893 *
894 * @param asMapEntries the {@code asMap} entries for which to return an
895 * unmodifiable view
896 * @return an unmodifiable view of the collection entries
897 */
898 private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries(
899 Set<Entry<K, Collection<V>>> asMapEntries) {
900 return new UnmodifiableAsMapEntries<K, V>(
901 Collections.unmodifiableSet(asMapEntries));
902 }
903
904 /** @see Multimaps#unmodifiableAsMapEntries */
905 static class UnmodifiableAsMapEntries<K, V>
906 extends ForwardingSet<Entry<K, Collection<V>>> {
907 private final Set<Entry<K, Collection<V>>> delegate;
908 UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) {
909 this.delegate = delegate;
910 }
911
912 @Override protected Set<Entry<K, Collection<V>>> delegate() {
913 return delegate;
914 }
915
916 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
917 final Iterator<Entry<K, Collection<V>>> iterator = delegate.iterator();
918 return new ForwardingIterator<Entry<K, Collection<V>>>() {
919 @Override protected Iterator<Entry<K, Collection<V>>> delegate() {
920 return iterator;
921 }
922 @Override public Entry<K, Collection<V>> next() {
923 return unmodifiableAsMapEntry(iterator.next());
924 }
925 };
926 }
927
928 @Override public Object[] toArray() {
929 return standardToArray();
930 }
931
932 @Override public <T> T[] toArray(T[] array) {
933 return standardToArray(array);
934 }
935
936 @Override public boolean contains(Object o) {
937 return Maps.containsEntryImpl(delegate(), o);
938 }
939
940 @Override public boolean containsAll(Collection<?> c) {
941 return standardContainsAll(c);
942 }
943
944 @Override public boolean equals(@Nullable Object object) {
945 return standardEquals(object);
946 }
947 }
948
949 /**
950 * Returns a multimap view of the specified map. The multimap is backed by the
951 * map, so changes to the map are reflected in the multimap, and vice versa.
952 * If the map is modified while an iteration over one of the multimap's
953 * collection views is in progress (except through the iterator's own {@code
954 * remove} operation, or through the {@code setValue} operation on a map entry
955 * returned by the iterator), the results of the iteration are undefined.
956 *
957 * <p>The multimap supports mapping removal, which removes the corresponding
958 * mapping from the map. It does not support any operations which might add
959 * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}.
960 *
961 * <p>The returned multimap will be serializable if the specified map is
962 * serializable.
963 *
964 * @param map the backing map for the returned multimap view
965 */
966 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
967 return new MapMultimap<K, V>(map);
968 }
969
970 /** @see Multimaps#forMap */
971 private static class MapMultimap<K, V>
972 implements SetMultimap<K, V>, Serializable {
973 final Map<K, V> map;
974 transient Map<K, Collection<V>> asMap;
975
976 MapMultimap(Map<K, V> map) {
977 this.map = checkNotNull(map);
978 }
979
980 @Override
981 public int size() {
982 return map.size();
983 }
984
985 @Override
986 public boolean isEmpty() {
987 return map.isEmpty();
988 }
989
990 @Override
991 public boolean containsKey(Object key) {
992 return map.containsKey(key);
993 }
994
995 @Override
996 public boolean containsValue(Object value) {
997 return map.containsValue(value);
998 }
999
1000 @Override
1001 public boolean containsEntry(Object key, Object value) {
1002 return map.entrySet().contains(Maps.immutableEntry(key, value));
1003 }
1004
1005 @Override
1006 public Set<V> get(final K key) {
1007 return new AbstractSet<V>() {
1008 @Override public Iterator<V> iterator() {
1009 return new Iterator<V>() {
1010 int i;
1011
1012 @Override
1013 public boolean hasNext() {
1014 return (i == 0) && map.containsKey(key);
1015 }
1016
1017 @Override
1018 public V next() {
1019 if (!hasNext()) {
1020 throw new NoSuchElementException();
1021 }
1022 i++;
1023 return map.get(key);
1024 }
1025
1026 @Override
1027 public void remove() {
1028 checkState(i == 1);
1029 i = -1;
1030 map.remove(key);
1031 }
1032 };
1033 }
1034
1035 @Override public int size() {
1036 return map.containsKey(key) ? 1 : 0;
1037 }
1038 };
1039 }
1040
1041 @Override
1042 public boolean put(K key, V value) {
1043 throw new UnsupportedOperationException();
1044 }
1045
1046 @Override
1047 public boolean putAll(K key, Iterable<? extends V> values) {
1048 throw new UnsupportedOperationException();
1049 }
1050
1051 @Override
1052 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1053 throw new UnsupportedOperationException();
1054 }
1055
1056 @Override
1057 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1058 throw new UnsupportedOperationException();
1059 }
1060
1061 @Override
1062 public boolean remove(Object key, Object value) {
1063 return map.entrySet().remove(Maps.immutableEntry(key, value));
1064 }
1065
1066 @Override
1067 public Set<V> removeAll(Object key) {
1068 Set<V> values = new HashSet<V>(2);
1069 if (!map.containsKey(key)) {
1070 return values;
1071 }
1072 values.add(map.remove(key));
1073 return values;
1074 }
1075
1076 @Override
1077 public void clear() {
1078 map.clear();
1079 }
1080
1081 @Override
1082 public Set<K> keySet() {
1083 return map.keySet();
1084 }
1085
1086 @Override
1087 public Multiset<K> keys() {
1088 return Multisets.forSet(map.keySet());
1089 }
1090
1091 @Override
1092 public Collection<V> values() {
1093 return map.values();
1094 }
1095
1096 @Override
1097 public Set<Entry<K, V>> entries() {
1098 return map.entrySet();
1099 }
1100
1101 @Override
1102 public Map<K, Collection<V>> asMap() {
1103 Map<K, Collection<V>> result = asMap;
1104 if (result == null) {
1105 asMap = result = new AsMap();
1106 }
1107 return result;
1108 }
1109
1110 @Override public boolean equals(@Nullable Object object) {
1111 if (object == this) {
1112 return true;
1113 }
1114 if (object instanceof Multimap) {
1115 Multimap<?, ?> that = (Multimap<?, ?>) object;
1116 return this.size() == that.size() && asMap().equals(that.asMap());
1117 }
1118 return false;
1119 }
1120
1121 @Override public int hashCode() {
1122 return map.hashCode();
1123 }
1124
1125 private static final MapJoiner JOINER
1126 = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null");
1127
1128 @Override public String toString() {
1129 if (map.isEmpty()) {
1130 return "{}";
1131 }
1132 StringBuilder builder
1133 = Collections2.newStringBuilderForCollection(map.size()).append('{');
1134 JOINER.appendTo(builder, map);
1135 return builder.append("]}").toString();
1136 }
1137
1138 /** @see MapMultimap#asMap */
1139 class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
1140 @Override public int size() {
1141 return map.size();
1142 }
1143
1144 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
1145 return new Iterator<Entry<K, Collection<V>>>() {
1146 final Iterator<K> keys = map.keySet().iterator();
1147
1148 @Override
1149 public boolean hasNext() {
1150 return keys.hasNext();
1151 }
1152 @Override
1153 public Entry<K, Collection<V>> next() {
1154 final K key = keys.next();
1155 return new AbstractMapEntry<K, Collection<V>>() {
1156 @Override public K getKey() {
1157 return key;
1158 }
1159 @Override public Collection<V> getValue() {
1160 return get(key);
1161 }
1162 };
1163 }
1164 @Override
1165 public void remove() {
1166 keys.remove();
1167 }
1168 };
1169 }
1170
1171 @Override public boolean contains(Object o) {
1172 if (!(o instanceof Entry)) {
1173 return false;
1174 }
1175 Entry<?, ?> entry = (Entry<?, ?>) o;
1176 if (!(entry.getValue() instanceof Set)) {
1177 return false;
1178 }
1179 Set<?> set = (Set<?>) entry.getValue();
1180 return (set.size() == 1)
1181 && containsEntry(entry.getKey(), set.iterator().next());
1182 }
1183
1184 @Override public boolean remove(Object o) {
1185 if (!(o instanceof Entry)) {
1186 return false;
1187 }
1188 Entry<?, ?> entry = (Entry<?, ?>) o;
1189 if (!(entry.getValue() instanceof Set)) {
1190 return false;
1191 }
1192 Set<?> set = (Set<?>) entry.getValue();
1193 return (set.size() == 1)
1194 && map.entrySet().remove(
1195 Maps.immutableEntry(entry.getKey(), set.iterator().next()));
1196 }
1197 }
1198
1199 /** @see MapMultimap#asMap */
1200 class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> {
1201 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
1202 return new AsMapEntries();
1203 }
1204
1205 // The following methods are included for performance.
1206
1207 @Override public boolean containsKey(Object key) {
1208 return map.containsKey(key);
1209 }
1210
1211 @SuppressWarnings("unchecked")
1212 @Override public Collection<V> get(Object key) {
1213 Collection<V> collection = MapMultimap.this.get((K) key);
1214 return collection.isEmpty() ? null : collection;
1215 }
1216
1217 @Override public Collection<V> remove(Object key) {
1218 Collection<V> collection = removeAll(key);
1219 return collection.isEmpty() ? null : collection;
1220 }
1221 }
1222 private static final long serialVersionUID = 7845222491160860175L;
1223 }
1224
1225 /**
1226 * Returns a view of a multimap where each value is transformed by a function.
1227 * All other properties of the multimap, such as iteration order, are left
1228 * intact. For example, the code: <pre> {@code
1229 *
1230 * Multimap<String, Integer> multimap =
1231 * ImmutableSetMultimap.of("a", 2, "b", -3, "b", -3, "a", 4, "c", 6);
1232 * Function<Integer, String> square = new Function<Integer, String>() {
1233 * public String apply(Integer in) {
1234 * return Integer.toString(in * in);
1235 * }
1236 * };
1237 * Multimap<String, String> transformed =
1238 * Multimaps.transformValues(multimap, square);
1239 * System.out.println(transformed);}</pre>
1240 *
1241 * ... prints {@code {a=[4, 16], b=[9, 9], c=[6]}}.
1242 *
1243 * <p>Changes in the underlying multimap are reflected in this view.
1244 * Conversely, this view supports removal operations, and these are reflected
1245 * in the underlying multimap.
1246 *
1247 * <p>It's acceptable for the underlying multimap to contain null keys, and
1248 * even null values provided that the function is capable of accepting null
1249 * input. The transformed multimap might contain null values, if the function
1250 * sometimes gives a null result.
1251 *
1252 * <p>The returned multimap is not thread-safe or serializable, even if the
1253 * underlying multimap is. The {@code equals} and {@code hashCode} methods
1254 * of the returned multimap are meaningless, since there is not a definition
1255 * of {@code equals} or {@code hashCode} for general collections, and
1256 * {@code get()} will return a general {@code Collection} as opposed to a
1257 * {@code List} or a {@code Set}.
1258 *
1259 * <p>The function is applied lazily, invoked when needed. This is necessary
1260 * for the returned multimap to be a view, but it means that the function will
1261 * be applied many times for bulk operations like
1262 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1263 * perform well, {@code function} should be fast. To avoid lazy evaluation
1264 * when the returned multimap doesn't need to be a view, copy the returned
1265 * multimap into a new multimap of your choosing.
1266 *
1267 * @since 7
1268 */
1269 @Beta
1270 @GwtIncompatible(value = "untested")
1271 public static <K, V1, V2> Multimap<K, V2> transformValues(
1272 Multimap<K, V1> fromMultimap, final Function<? super V1, V2> function) {
1273 checkNotNull(function);
1274 EntryTransformer<K, V1, V2> transformer =
1275 new EntryTransformer<K, V1, V2>() {
1276 @Override
1277 public V2 transformEntry(K key, V1 value) {
1278 return function.apply(value);
1279 }
1280 };
1281 return transformEntries(fromMultimap, transformer);
1282 }
1283
1284 /**
1285 * Returns a view of a multimap whose values are derived from the original
1286 * multimap's entries. In contrast to {@link #transformValues}, this method's
1287 * entry-transformation logic may depend on the key as well as the value.
1288 *
1289 * <p>All other properties of the transformed multimap, such as iteration
1290 * order, are left intact. For example, the code: <pre> {@code
1291 *
1292 * SetMultimap<String, Integer> multimap =
1293 * ImmutableSetMultimap.of("a", 1, "a", 4, "b", -6);
1294 * EntryTransformer<String, Integer, String> transformer =
1295 * new EntryTransformer<String, Integer, String>() {
1296 * public String transformEntry(String key, Integer value) {
1297 * return (value >= 0) ? key : "no" + key;
1298 * }
1299 * };
1300 * Multimap<String, String> transformed =
1301 * Multimaps.transformEntries(multimap, transformer);
1302 * System.out.println(transformed);}</pre>
1303 *
1304 * ... prints {@code {a=[a, a], b=[nob]}}.
1305 *
1306 * <p>Changes in the underlying multimap are reflected in this view.
1307 * Conversely, this view supports removal operations, and these are reflected
1308 * in the underlying multimap.
1309 *
1310 * <p>It's acceptable for the underlying multimap to contain null keys and
1311 * null values provided that the transformer is capable of accepting null
1312 * inputs. The transformed multimap might contain null values if the
1313 * transformer sometimes gives a null result.
1314 *
1315 * <p>The returned multimap is not thread-safe or serializable, even if the
1316 * underlying multimap is. The {@code equals} and {@code hashCode} methods
1317 * of the returned multimap are meaningless, since there is not a definition
1318 * of {@code equals} or {@code hashCode} for general collections, and
1319 * {@code get()} will return a general {@code Collection} as opposed to a
1320 * {@code List} or a {@code Set}.
1321 *
1322 * <p>The transformer is applied lazily, invoked when needed. This is
1323 * necessary for the returned multimap to be a view, but it means that the
1324 * transformer will be applied many times for bulk operations like {@link
1325 * Multimap#containsValue} and {@link Object#toString}. For this to perform
1326 * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1327 * returned multimap doesn't need to be a view, copy the returned multimap
1328 * into a new multimap of your choosing.
1329 *
1330 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1331 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1332 * that {@code k2} is also of type {@code K}. Using an {@code
1333 * EntryTransformer} key type for which this may not hold, such as {@code
1334 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1335 * the transformed multimap.
1336 *
1337 * @since 7
1338 */
1339 @Beta
1340 @GwtIncompatible(value = "untested")
1341 public static <K, V1, V2> Multimap<K, V2> transformEntries(
1342 Multimap<K, V1> fromMap,
1343 EntryTransformer<? super K, ? super V1, V2> transformer) {
1344 return new TransformedEntriesMultimap<K, V1, V2>(fromMap, transformer);
1345 }
1346
1347 @GwtIncompatible(value = "untested")
1348 private static class TransformedEntriesMultimap<K, V1, V2>
1349 implements Multimap<K, V2> {
1350 final Multimap<K, V1> fromMultimap;
1351 final EntryTransformer<? super K, ? super V1, V2> transformer;
1352
1353 TransformedEntriesMultimap(Multimap<K, V1> fromMultimap,
1354 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1355 this.fromMultimap = checkNotNull(fromMultimap);
1356 this.transformer = checkNotNull(transformer);
1357 }
1358
1359 Collection<V2> transform(final K key, Collection<V1> values) {
1360 return Collections2.transform(values, new Function<V1, V2>() {
1361 @Override public V2 apply(V1 value) {
1362 return transformer.transformEntry(key, value);
1363 }
1364 });
1365 }
1366
1367 private transient Map<K, Collection<V2>> asMap;
1368
1369 @Override public Map<K, Collection<V2>> asMap() {
1370 if (asMap == null) {
1371 Map<K, Collection<V2>> aM = Maps.transformEntries(fromMultimap.asMap(),
1372 new EntryTransformer<K, Collection<V1>, Collection<V2>>() {
1373
1374 @Override public Collection<V2> transformEntry(
1375 K key, Collection<V1> value) {
1376 return transform(key, value);
1377 }
1378 });
1379 asMap = aM;
1380 return aM;
1381 }
1382 return asMap;
1383 }
1384
1385 @Override public void clear() {
1386 fromMultimap.clear();
1387 }
1388
1389 @SuppressWarnings("unchecked")
1390 @Override public boolean containsEntry(Object key, Object value) {
1391 Collection<V2> values = get((K) key);
1392 return values.contains(value);
1393 }
1394
1395 @Override public boolean containsKey(Object key) {
1396 return fromMultimap.containsKey(key);
1397 }
1398
1399 @Override public boolean containsValue(Object value) {
1400 return values().contains(value);
1401 }
1402
1403 private transient Collection<Entry<K, V2>> entries;
1404
1405 @Override public Collection<Entry<K, V2>> entries() {
1406 if (entries == null) {
1407 Collection<Entry<K, V2>> es = new TransformedEntries(transformer);
1408 entries = es;
1409 return es;
1410 }
1411 return entries;
1412 }
1413
1414 private class TransformedEntries
1415 extends TransformedCollection<Entry<K, V1>, Entry<K, V2>> {
1416
1417 TransformedEntries(
1418 final EntryTransformer<? super K, ? super V1, V2> transformer) {
1419 super(fromMultimap.entries(),
1420 new Function<Entry<K, V1>, Entry<K, V2>>() {
1421 @Override public Entry<K, V2> apply(final Entry<K, V1> entry) {
1422 return new AbstractMapEntry<K, V2>() {
1423
1424 @Override public K getKey() {
1425 return entry.getKey();
1426 }
1427
1428 @Override public V2 getValue() {
1429 return transformer.transformEntry(
1430 entry.getKey(), entry.getValue());
1431 }
1432 };
1433 }
1434 });
1435 }
1436
1437 @SuppressWarnings("unchecked")
1438 @Override public boolean contains(Object o) {
1439 if (o instanceof Entry) {
1440 Entry<?, ?> entry = (Entry<?, ?>) o;
1441 return containsEntry(entry.getKey(), entry.getValue());
1442 }
1443 return false;
1444 }
1445
1446 @SuppressWarnings("unchecked")
1447 @Override public boolean remove(Object o) {
1448 if (o instanceof Entry) {
1449 Entry<?, ?> entry = (Entry<?, ?>) o;
1450 Collection<V2> values = get((K) entry.getKey());
1451 return values.remove(entry.getValue());
1452 }
1453 return false;
1454 }
1455
1456 }
1457
1458 @Override public Collection<V2> get(final K key) {
1459 return transform(key, fromMultimap.get(key));
1460 }
1461
1462 @Override public boolean isEmpty() {
1463 return fromMultimap.isEmpty();
1464 }
1465
1466 @Override public Set<K> keySet() {
1467 return fromMultimap.keySet();
1468 }
1469
1470 @Override public Multiset<K> keys() {
1471 return fromMultimap.keys();
1472 }
1473
1474 @Override public boolean put(K key, V2 value) {
1475 throw new UnsupportedOperationException();
1476 }
1477
1478 @Override public boolean putAll(K key, Iterable<? extends V2> values) {
1479 throw new UnsupportedOperationException();
1480 }
1481
1482 @Override public boolean putAll(
1483 Multimap<? extends K, ? extends V2> multimap) {
1484 throw new UnsupportedOperationException();
1485 }
1486
1487 @SuppressWarnings("unchecked")
1488 @Override public boolean remove(Object key, Object value) {
1489 return get((K) key).remove(value);
1490 }
1491
1492 @SuppressWarnings("unchecked")
1493 @Override public Collection<V2> removeAll(Object key) {
1494 return transform((K) key, fromMultimap.removeAll(key));
1495 }
1496
1497 @Override public Collection<V2> replaceValues(
1498 K key, Iterable<? extends V2> values) {
1499 throw new UnsupportedOperationException();
1500 }
1501
1502 @Override public int size() {
1503 return fromMultimap.size();
1504 }
1505
1506 private transient Collection<V2> values;
1507
1508 @Override public Collection<V2> values() {
1509 if (values == null) {
1510 Collection<V2> vs = Collections2.transform(
1511 fromMultimap.entries(), new Function<Entry<K, V1>, V2>() {
1512
1513 @Override public V2 apply(Entry<K, V1> entry) {
1514 return transformer.transformEntry(
1515 entry.getKey(), entry.getValue());
1516 }
1517 });
1518 values = vs;
1519 return vs;
1520 }
1521 return values;
1522 }
1523
1524 @Override public boolean equals(Object obj) {
1525 if (obj instanceof Multimap) {
1526 Multimap<?, ?> other = (Multimap<?, ?>) obj;
1527 return asMap().equals(other.asMap());
1528 }
1529 return false;
1530 }
1531
1532 @Override public int hashCode() {
1533 return asMap().hashCode();
1534 }
1535
1536 @Override public String toString() {
1537 return asMap().toString();
1538 }
1539 }
1540
1541 /**
1542 * Returns a view of a {@code ListMultimap} where each value is transformed by
1543 * a function. All other properties of the multimap, such as iteration order,
1544 * are left intact. For example, the code: <pre> {@code
1545 *
1546 * ListMultimap<String, Integer> multimap
1547 * = ImmutableListMultimap.of("a", 4, "a", 16, "b", 9);
1548 * Function<Integer, Double> sqrt =
1549 * new Function<Integer, Double>() {
1550 * public Double apply(Integer in) {
1551 * return Math.sqrt((int) in);
1552 * }
1553 * };
1554 * ListMultimap<String, Double> transformed = Multimaps.transformValues(map,
1555 * sqrt);
1556 * System.out.println(transformed);}</pre>
1557 *
1558 * ... prints {@code {a=[2.0, 4.0], b=[3.0]}}.
1559 *
1560 * <p>Changes in the underlying multimap are reflected in this view.
1561 * Conversely, this view supports removal operations, and these are reflected
1562 * in the underlying multimap.
1563 *
1564 * <p>It's acceptable for the underlying multimap to contain null keys, and
1565 * even null values provided that the function is capable of accepting null
1566 * input. The transformed multimap might contain null values, if the function
1567 * sometimes gives a null result.
1568 *
1569 * <p>The returned multimap is not thread-safe or serializable, even if the
1570 * underlying multimap is.
1571 *
1572 * <p>The function is applied lazily, invoked when needed. This is necessary
1573 * for the returned multimap to be a view, but it means that the function will
1574 * be applied many times for bulk operations like
1575 * {@link Multimap#containsValue} and {@code Multimap.toString()}. For this to
1576 * perform well, {@code function} should be fast. To avoid lazy evaluation
1577 * when the returned multimap doesn't need to be a view, copy the returned
1578 * multimap into a new multimap of your choosing.
1579 *
1580 * @since 7
1581 */
1582 @Beta
1583 @GwtIncompatible(value = "untested")
1584 public static <K, V1, V2> ListMultimap<K, V2> transformValues(
1585 ListMultimap<K, V1> fromMultimap,
1586 final Function<? super V1, V2> function) {
1587 checkNotNull(function);
1588 EntryTransformer<K, V1, V2> transformer =
1589 new EntryTransformer<K, V1, V2>() {
1590 @Override
1591 public V2 transformEntry(K key, V1 value) {
1592 return function.apply(value);
1593 }
1594 };
1595 return transformEntries(fromMultimap, transformer);
1596 }
1597
1598 /**
1599 * Returns a view of a {@code ListMultimap} whose values are derived from the
1600 * original multimap's entries. In contrast to
1601 * {@link #transformValues(ListMultimap, Function)}, this method's
1602 * entry-transformation logic may depend on the key as well as the value.
1603 *
1604 * <p>All other properties of the transformed multimap, such as iteration
1605 * order, are left intact. For example, the code: <pre> {@code
1606 *
1607 * Multimap<String, Integer> multimap =
1608 * ImmutableMultimap.of("a", 1, "a", 4, "b", 6);
1609 * EntryTransformer<String, Integer, String> transformer =
1610 * new EntryTransformer<String, Integer, String>() {
1611 * public String transformEntry(String key, Integer value) {
1612 * return key + value;
1613 * }
1614 * };
1615 * Multimap<String, String> transformed =
1616 * Multimaps.transformEntries(multimap, transformer);
1617 * System.out.println(transformed);}</pre>
1618 *
1619 * ... prints {@code {"a"=["a1", "a4"], "b"=["b6"]}}.
1620 *
1621 * <p>Changes in the underlying multimap are reflected in this view.
1622 * Conversely, this view supports removal operations, and these are reflected
1623 * in the underlying multimap.
1624 *
1625 * <p>It's acceptable for the underlying multimap to contain null keys and
1626 * null values provided that the transformer is capable of accepting null
1627 * inputs. The transformed multimap might contain null values if the
1628 * transformer sometimes gives a null result.
1629 *
1630 * <p>The returned multimap is not thread-safe or serializable, even if the
1631 * underlying multimap is.
1632 *
1633 * <p>The transformer is applied lazily, invoked when needed. This is
1634 * necessary for the returned multimap to be a view, but it means that the
1635 * transformer will be applied many times for bulk operations like {@link
1636 * Multimap#containsValue} and {@link Object#toString}. For this to perform
1637 * well, {@code transformer} should be fast. To avoid lazy evaluation when the
1638 * returned multimap doesn't need to be a view, copy the returned multimap
1639 * into a new multimap of your choosing.
1640 *
1641 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
1642 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
1643 * that {@code k2} is also of type {@code K}. Using an {@code
1644 * EntryTransformer} key type for which this may not hold, such as {@code
1645 * ArrayList}, may risk a {@code ClassCastException} when calling methods on
1646 * the transformed multimap.
1647 *
1648 * @since 7
1649 */
1650 @Beta
1651 @GwtIncompatible(value = "untested")
1652 public static <K, V1, V2> ListMultimap<K, V2> transformEntries(
1653 ListMultimap<K, V1> fromMap,
1654 EntryTransformer<? super K, ? super V1, V2> transformer) {
1655 return new TransformedEntriesListMultimap<K, V1, V2>(fromMap, transformer);
1656 }
1657
1658 @GwtIncompatible(value = "untested")
1659 private static final class TransformedEntriesListMultimap<K, V1, V2>
1660 extends TransformedEntriesMultimap<K, V1, V2>
1661 implements ListMultimap<K, V2> {
1662
1663 TransformedEntriesListMultimap(ListMultimap<K, V1> fromMultimap,
1664 EntryTransformer<? super K, ? super V1, V2> transformer) {
1665 super(fromMultimap, transformer);
1666 }
1667
1668 @Override List<V2> transform(final K key, Collection<V1> values) {
1669 return Lists.transform((List<V1>) values, new Function<V1, V2>() {
1670 @Override public V2 apply(V1 value) {
1671 return transformer.transformEntry(key, value);
1672 }
1673 });
1674 }
1675
1676 @Override public List<V2> get(K key) {
1677 return transform(key, fromMultimap.get(key));
1678 }
1679
1680 @SuppressWarnings("unchecked")
1681 @Override public List<V2> removeAll(Object key) {
1682 return transform((K) key, fromMultimap.removeAll(key));
1683 }
1684
1685 @Override public List<V2> replaceValues(
1686 K key, Iterable<? extends V2> values) {
1687 throw new UnsupportedOperationException();
1688 }
1689 }
1690
1691 /**
1692 * Creates an index {@code ImmutableListMultimap} that contains the results of
1693 * applying a specified function to each item in an {@code Iterable} of
1694 * values. Each value will be stored as a value in the resulting multimap,
1695 * yielding a multimap with the same size as the input iterable. The key used
1696 * to store that value in the multimap will be the result of calling the
1697 * function on that value. The resulting multimap is created as an immutable
1698 * snapshot. In the returned multimap, keys appear in the order they are first
1699 * encountered, and the values corresponding to each key appear in the same
1700 * order as they are encountered.
1701 *
1702 * <p>For example, <pre> {@code
1703 *
1704 * List<String> badGuys =
1705 * Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1706 * Function<String, Integer> stringLengthFunction = ...;
1707 * Multimap<Integer, String> index =
1708 * Multimaps.index(badGuys, stringLengthFunction);
1709 * System.out.println(index);}</pre>
1710 *
1711 * prints <pre> {@code
1712 *
1713 * {4=[Inky], 6=[Blinky], 5=[Pinky, Pinky, Clyde]}}</pre>
1714 *
1715 * The returned multimap is serializable if its keys and values are all
1716 * serializable.
1717 *
1718 * @param values the values to use when constructing the {@code
1719 * ImmutableListMultimap}
1720 * @param keyFunction the function used to produce the key for each value
1721 * @return {@code ImmutableListMultimap} mapping the result of evaluating the
1722 * function {@code keyFunction} on each value in the input collection to
1723 * that value
1724 * @throws NullPointerException if any of the following cases is true:
1725 * <ul>
1726 * <li>{@code values} is null
1727 * <li>{@code keyFunction} is null
1728 * <li>An element in {@code values} is null
1729 * <li>{@code keyFunction} returns {@code null} for any element of {@code
1730 * values}
1731 * </ul>
1732 */
1733 public static <K, V> ImmutableListMultimap<K, V> index(
1734 Iterable<V> values, Function<? super V, K> keyFunction) {
1735 checkNotNull(keyFunction);
1736 ImmutableListMultimap.Builder<K, V> builder
1737 = ImmutableListMultimap.builder();
1738 for (V value : values) {
1739 checkNotNull(value, values);
1740 builder.put(keyFunction.apply(value), value);
1741 }
1742 return builder.build();
1743 }
1744 }