001 /*
002 * Copyright (C) 2007 Google Inc.
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.GwtCompatible;
023 import com.google.common.annotations.GwtIncompatible;
024 import com.google.common.base.Function;
025 import com.google.common.base.Joiner;
026 import com.google.common.base.Joiner.MapJoiner;
027 import com.google.common.base.Preconditions;
028 import com.google.common.base.Supplier;
029
030 import java.io.IOException;
031 import java.io.ObjectInputStream;
032 import java.io.ObjectOutputStream;
033 import java.io.Serializable;
034 import java.util.AbstractSet;
035 import java.util.Collection;
036 import java.util.Collections;
037 import java.util.Comparator;
038 import java.util.HashSet;
039 import java.util.Iterator;
040 import java.util.List;
041 import java.util.Map;
042 import java.util.Map.Entry;
043 import java.util.NoSuchElementException;
044 import java.util.Set;
045 import java.util.SortedSet;
046
047 import javax.annotation.Nullable;
048
049 /**
050 * Provides static methods acting on or generating a {@code Multimap}.
051 *
052 * @author Jared Levy
053 * @author Robert Konigsberg
054 * @author Mike Bostock
055 * @since 2 (imported from Google Collections Library)
056 */
057 @GwtCompatible(emulated = true)
058 public final class Multimaps {
059 private Multimaps() {}
060
061 /**
062 * Creates a new {@code Multimap} that uses the provided map and factory. It
063 * can generate a multimap based on arbitrary {@link Map} and
064 * {@link Collection} classes.
065 *
066 * <p>The {@code factory}-generated and {@code map} classes determine the
067 * multimap iteration order. They also specify the behavior of the
068 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
069 * multimap and its returned views. However, the multimap's {@code get}
070 * method returns instances of a different class than {@code factory.get()}
071 * does.
072 *
073 * <p>The multimap is serializable if {@code map}, {@code factory}, the
074 * collections generated by {@code factory}, and the multimap contents are all
075 * serializable.
076 *
077 * <p>The multimap is not threadsafe when any concurrent operations update the
078 * multimap, even if {@code map} and the instances generated by
079 * {@code factory} are. Concurrent read operations will work correctly. To
080 * allow concurrent update operations, wrap the multimap with a call to
081 * {@link #synchronizedMultimap}.
082 *
083 * <p>Call this method only when the simpler methods
084 * {@link ArrayListMultimap#create()}, {@link HashMultimap#create()},
085 * {@link LinkedHashMultimap#create()}, {@link LinkedListMultimap#create()},
086 * {@link TreeMultimap#create()}, and
087 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
088 *
089 * <p>Note: the multimap assumes complete ownership over of {@code map} and
090 * the collections returned by {@code factory}. Those objects should not be
091 * manually updated and they should not use soft, weak, or phantom references.
092 *
093 * @param map place to store the mapping from each key to its corresponding
094 * values
095 * @param factory supplier of new, empty collections that will each hold all
096 * values for a given key
097 * @throws IllegalArgumentException if {@code map} is not empty
098 */
099 public static <K, V> Multimap<K, V> newMultimap(Map<K, Collection<V>> map,
100 final Supplier<? extends Collection<V>> factory) {
101 return new CustomMultimap<K, V>(map, factory);
102 }
103
104 private static class CustomMultimap<K, V> extends AbstractMultimap<K, V> {
105 transient Supplier<? extends Collection<V>> factory;
106
107 CustomMultimap(Map<K, Collection<V>> map,
108 Supplier<? extends Collection<V>> factory) {
109 super(map);
110 this.factory = checkNotNull(factory);
111 }
112
113 @Override protected Collection<V> createCollection() {
114 return factory.get();
115 }
116
117 // can't use Serialization writeMultimap and populateMultimap methods since
118 // there's no way to generate the empty backing map.
119
120 /** @serialData the factory and the backing map */
121 @GwtIncompatible("java.io.ObjectOutputStream")
122 private void writeObject(ObjectOutputStream stream) throws IOException {
123 stream.defaultWriteObject();
124 stream.writeObject(factory);
125 stream.writeObject(backingMap());
126 }
127
128 @GwtIncompatible("java.io.ObjectInputStream")
129 @SuppressWarnings("unchecked") // reading data stored by writeObject
130 private void readObject(ObjectInputStream stream)
131 throws IOException, ClassNotFoundException {
132 stream.defaultReadObject();
133 factory = (Supplier<? extends Collection<V>>) stream.readObject();
134 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
135 setMap(map);
136 }
137
138 @GwtIncompatible("java serialization not supported")
139 private static final long serialVersionUID = 0;
140 }
141
142 /**
143 * Creates a new {@code ListMultimap} that uses the provided map and factory.
144 * It can generate a multimap based on arbitrary {@link Map} and {@link List}
145 * classes.
146 *
147 * <p>The {@code factory}-generated and {@code map} classes determine the
148 * multimap iteration order. They also specify the behavior of the
149 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
150 * multimap and its returned views. The multimap's {@code get}, {@code
151 * removeAll}, and {@code replaceValues} methods return {@code RandomAccess}
152 * lists if the factory does. However, the multimap's {@code get} method
153 * returns instances of a different class than does {@code factory.get()}.
154 *
155 * <p>The multimap is serializable if {@code map}, {@code factory}, the
156 * lists generated by {@code factory}, and the multimap contents are all
157 * serializable.
158 *
159 * <p>The multimap is not threadsafe when any concurrent operations update the
160 * multimap, even if {@code map} and the instances generated by
161 * {@code factory} are. Concurrent read operations will work correctly. To
162 * allow concurrent update operations, wrap the multimap with a call to
163 * {@link #synchronizedListMultimap}.
164 *
165 * <p>Call this method only when the simpler methods
166 * {@link ArrayListMultimap#create()} and {@link LinkedListMultimap#create()}
167 * won't suffice.
168 *
169 * <p>Note: the multimap assumes complete ownership over of {@code map} and
170 * the lists returned by {@code factory}. Those objects should not be manually
171 * updated and they should not use soft, weak, or phantom references.
172 *
173 * @param map place to store the mapping from each key to its corresponding
174 * values
175 * @param factory supplier of new, empty lists that will each hold all values
176 * for a given key
177 * @throws IllegalArgumentException if {@code map} is not empty
178 */
179 public static <K, V> ListMultimap<K, V> newListMultimap(
180 Map<K, Collection<V>> map, final Supplier<? extends List<V>> factory) {
181 return new CustomListMultimap<K, V>(map, factory);
182 }
183
184 private static class CustomListMultimap<K, V>
185 extends AbstractListMultimap<K, V> {
186 transient Supplier<? extends List<V>> factory;
187
188 CustomListMultimap(Map<K, Collection<V>> map,
189 Supplier<? extends List<V>> factory) {
190 super(map);
191 this.factory = checkNotNull(factory);
192 }
193
194 @Override protected List<V> createCollection() {
195 return factory.get();
196 }
197
198 /** @serialData the factory and the backing map */
199 @GwtIncompatible("java.io.ObjectOutputStream")
200 private void writeObject(ObjectOutputStream stream) throws IOException {
201 stream.defaultWriteObject();
202 stream.writeObject(factory);
203 stream.writeObject(backingMap());
204 }
205
206 @GwtIncompatible("java.io.ObjectInputStream")
207 @SuppressWarnings("unchecked") // reading data stored by writeObject
208 private void readObject(ObjectInputStream stream)
209 throws IOException, ClassNotFoundException {
210 stream.defaultReadObject();
211 factory = (Supplier<? extends List<V>>) stream.readObject();
212 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
213 setMap(map);
214 }
215
216 @GwtIncompatible("java serialization not supported")
217 private static final long serialVersionUID = 0;
218 }
219
220 /**
221 * Creates a new {@code SetMultimap} that uses the provided map and factory.
222 * It can generate a multimap based on arbitrary {@link Map} and {@link Set}
223 * classes.
224 *
225 * <p>The {@code factory}-generated and {@code map} classes determine the
226 * multimap iteration order. They also specify the behavior of the
227 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
228 * multimap and its returned views. However, the multimap's {@code get}
229 * method returns instances of a different class than {@code factory.get()}
230 * does.
231 *
232 * <p>The multimap is serializable if {@code map}, {@code factory}, the
233 * sets generated by {@code factory}, and the multimap contents are all
234 * serializable.
235 *
236 * <p>The multimap is not threadsafe when any concurrent operations update the
237 * multimap, even if {@code map} and the instances generated by
238 * {@code factory} are. Concurrent read operations will work correctly. To
239 * allow concurrent update operations, wrap the multimap with a call to
240 * {@link #synchronizedSetMultimap}.
241 *
242 * <p>Call this method only when the simpler methods
243 * {@link HashMultimap#create()}, {@link LinkedHashMultimap#create()},
244 * {@link TreeMultimap#create()}, and
245 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
246 *
247 * <p>Note: the multimap assumes complete ownership over of {@code map} and
248 * the sets returned by {@code factory}. Those objects should not be manually
249 * updated and they should not use soft, weak, or phantom references.
250 *
251 * @param map place to store the mapping from each key to its corresponding
252 * values
253 * @param factory supplier of new, empty sets that will each hold all values
254 * for a given key
255 * @throws IllegalArgumentException if {@code map} is not empty
256 */
257 public static <K, V> SetMultimap<K, V> newSetMultimap(
258 Map<K, Collection<V>> map, final Supplier<? extends Set<V>> factory) {
259 return new CustomSetMultimap<K, V>(map, factory);
260 }
261
262 private static class CustomSetMultimap<K, V>
263 extends AbstractSetMultimap<K, V> {
264 transient Supplier<? extends Set<V>> factory;
265
266 CustomSetMultimap(Map<K, Collection<V>> map,
267 Supplier<? extends Set<V>> factory) {
268 super(map);
269 this.factory = checkNotNull(factory);
270 }
271
272 @Override protected Set<V> createCollection() {
273 return factory.get();
274 }
275
276 /** @serialData the factory and the backing map */
277 @GwtIncompatible("java.io.ObjectOutputStream")
278 private void writeObject(ObjectOutputStream stream) throws IOException {
279 stream.defaultWriteObject();
280 stream.writeObject(factory);
281 stream.writeObject(backingMap());
282 }
283
284 @GwtIncompatible("java.io.ObjectInputStream")
285 @SuppressWarnings("unchecked") // reading data stored by writeObject
286 private void readObject(ObjectInputStream stream)
287 throws IOException, ClassNotFoundException {
288 stream.defaultReadObject();
289 factory = (Supplier<? extends Set<V>>) stream.readObject();
290 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
291 setMap(map);
292 }
293
294 @GwtIncompatible("not needed in emulated source")
295 private static final long serialVersionUID = 0;
296 }
297
298 /**
299 * Creates a new {@code SortedSetMultimap} that uses the provided map and
300 * factory. It can generate a multimap based on arbitrary {@link Map} and
301 * {@link SortedSet} classes.
302 *
303 * <p>The {@code factory}-generated and {@code map} classes determine the
304 * multimap iteration order. They also specify the behavior of the
305 * {@code equals}, {@code hashCode}, and {@code toString} methods for the
306 * multimap and its returned views. However, the multimap's {@code get}
307 * method returns instances of a different class than {@code factory.get()}
308 * does.
309 *
310 * <p>The multimap is serializable if {@code map}, {@code factory}, the
311 * sets generated by {@code factory}, and the multimap contents are all
312 * serializable.
313 *
314 * <p>The multimap is not threadsafe when any concurrent operations update the
315 * multimap, even if {@code map} and the instances generated by
316 * {@code factory} are. Concurrent read operations will work correctly. To
317 * allow concurrent update operations, wrap the multimap with a call to
318 * {@link #synchronizedSortedSetMultimap}.
319 *
320 * <p>Call this method only when the simpler methods
321 * {@link TreeMultimap#create()} and
322 * {@link TreeMultimap#create(Comparator, Comparator)} won't suffice.
323 *
324 * <p>Note: the multimap assumes complete ownership over of {@code map} and
325 * the sets returned by {@code factory}. Those objects should not be manually
326 * updated and they should not use soft, weak, or phantom references.
327 *
328 * @param map place to store the mapping from each key to its corresponding
329 * values
330 * @param factory supplier of new, empty sorted sets that will each hold
331 * all values for a given key
332 * @throws IllegalArgumentException if {@code map} is not empty
333 */
334 public static <K, V> SortedSetMultimap<K, V> newSortedSetMultimap(
335 Map<K, Collection<V>> map,
336 final Supplier<? extends SortedSet<V>> factory) {
337 return new CustomSortedSetMultimap<K, V>(map, factory);
338 }
339
340 private static class CustomSortedSetMultimap<K, V>
341 extends AbstractSortedSetMultimap<K, V> {
342 transient Supplier<? extends SortedSet<V>> factory;
343 transient Comparator<? super V> valueComparator;
344
345 CustomSortedSetMultimap(Map<K, Collection<V>> map,
346 Supplier<? extends SortedSet<V>> factory) {
347 super(map);
348 this.factory = checkNotNull(factory);
349 valueComparator = factory.get().comparator();
350 }
351
352 @Override protected SortedSet<V> createCollection() {
353 return factory.get();
354 }
355
356 @Override public Comparator<? super V> valueComparator() {
357 return valueComparator;
358 }
359
360 /** @serialData the factory and the backing map */
361 @GwtIncompatible("java.io.ObjectOutputStream")
362 private void writeObject(ObjectOutputStream stream) throws IOException {
363 stream.defaultWriteObject();
364 stream.writeObject(factory);
365 stream.writeObject(backingMap());
366 }
367
368 @GwtIncompatible("java.io.ObjectInputStream")
369 @SuppressWarnings("unchecked") // reading data stored by writeObject
370 private void readObject(ObjectInputStream stream)
371 throws IOException, ClassNotFoundException {
372 stream.defaultReadObject();
373 factory = (Supplier<? extends SortedSet<V>>) stream.readObject();
374 valueComparator = factory.get().comparator();
375 Map<K, Collection<V>> map = (Map<K, Collection<V>>) stream.readObject();
376 setMap(map);
377 }
378
379 @GwtIncompatible("not needed in emulated source")
380 private static final long serialVersionUID = 0;
381 }
382
383 /**
384 * Copies each key-value mapping in {@code source} into {@code dest}, with
385 * its key and value reversed.
386 *
387 * @param source any multimap
388 * @param dest the multimap to copy into; usually empty
389 * @return {@code dest}
390 */
391 public static <K, V, M extends Multimap<K, V>> M invertFrom(
392 Multimap<? extends V, ? extends K> source, M dest) {
393 checkNotNull(dest);
394 for (Map.Entry<? extends V, ? extends K> entry : source.entries()) {
395 dest.put(entry.getValue(), entry.getKey());
396 }
397 return dest;
398 }
399
400 /**
401 * Returns a synchronized (thread-safe) multimap backed by the specified
402 * multimap. In order to guarantee serial access, it is critical that
403 * <b>all</b> access to the backing multimap is accomplished through the
404 * returned multimap.
405 *
406 * <p>It is imperative that the user manually synchronize on the returned
407 * multimap when accessing any of its collection views: <pre> {@code
408 *
409 * Multimap<K, V> m = Multimaps.synchronizedMultimap(
410 * HashMultimap.<K, V>create());
411 * ...
412 * Set<K> s = m.keySet(); // Needn't be in synchronized block
413 * ...
414 * synchronized (m) { // Synchronizing on m, not s!
415 * Iterator<K> i = s.iterator(); // Must be in synchronized block
416 * while (i.hasNext()) {
417 * foo(i.next());
418 * }
419 * }}</pre>
420 *
421 * Failure to follow this advice may result in non-deterministic behavior.
422 *
423 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
424 * {@link Multimap#replaceValues} methods return collections that aren't
425 * synchronized.
426 *
427 * <p>The returned multimap will be serializable if the specified multimap is
428 * serializable.
429 *
430 * @param multimap the multimap to be wrapped in a synchronized view
431 * @return a synchronized view of the specified multimap
432 */
433 public static <K, V> Multimap<K, V> synchronizedMultimap(
434 Multimap<K, V> multimap) {
435 return Synchronized.multimap(multimap, null);
436 }
437
438 /**
439 * Returns an unmodifiable view of the specified multimap. Query operations on
440 * the returned multimap "read through" to the specified multimap, and
441 * attempts to modify the returned multimap, either directly or through the
442 * multimap's views, result in an {@code UnsupportedOperationException}.
443 *
444 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
445 * {@link Multimap#replaceValues} methods return collections that are
446 * modifiable.
447 *
448 * <p>The returned multimap will be serializable if the specified multimap is
449 * serializable.
450 *
451 * @param delegate the multimap for which an unmodifiable view is to be
452 * returned
453 * @return an unmodifiable view of the specified multimap
454 */
455 public static <K, V> Multimap<K, V> unmodifiableMultimap(
456 Multimap<K, V> delegate) {
457 return new UnmodifiableMultimap<K, V>(delegate);
458 }
459
460 private static class UnmodifiableMultimap<K, V>
461 extends ForwardingMultimap<K, V> implements Serializable {
462 final Multimap<K, V> delegate;
463 transient Collection<Entry<K, V>> entries;
464 transient Multiset<K> keys;
465 transient Set<K> keySet;
466 transient Collection<V> values;
467 transient Map<K, Collection<V>> map;
468
469 UnmodifiableMultimap(final Multimap<K, V> delegate) {
470 this.delegate = checkNotNull(delegate);
471 }
472
473 @Override protected Multimap<K, V> delegate() {
474 return delegate;
475 }
476
477 @Override public void clear() {
478 throw new UnsupportedOperationException();
479 }
480
481 @Override public Map<K, Collection<V>> asMap() {
482 Map<K, Collection<V>> result = map;
483 if (result == null) {
484 final Map<K, Collection<V>> unmodifiableMap
485 = Collections.unmodifiableMap(delegate.asMap());
486 map = result = new ForwardingMap<K, Collection<V>>() {
487 @Override protected Map<K, Collection<V>> delegate() {
488 return unmodifiableMap;
489 }
490
491 Set<Entry<K, Collection<V>>> entrySet;
492
493 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() {
494 Set<Entry<K, Collection<V>>> result = entrySet;
495 return (result == null)
496 ? entrySet
497 = unmodifiableAsMapEntries(unmodifiableMap.entrySet())
498 : result;
499 }
500
501 @Override public Collection<V> get(Object key) {
502 Collection<V> collection = unmodifiableMap.get(key);
503 return (collection == null)
504 ? null : unmodifiableValueCollection(collection);
505 }
506
507 Collection<Collection<V>> asMapValues;
508
509 @Override public Collection<Collection<V>> values() {
510 Collection<Collection<V>> result = asMapValues;
511 return (result == null)
512 ? asMapValues
513 = new UnmodifiableAsMapValues<V>(unmodifiableMap.values())
514 : result;
515 }
516
517 @Override public boolean containsValue(Object o) {
518 return values().contains(o);
519 }
520 };
521 }
522 return result;
523 }
524
525 @Override public Collection<Entry<K, V>> entries() {
526 Collection<Entry<K, V>> result = entries;
527 if (result == null) {
528 entries = result = unmodifiableEntries(delegate.entries());
529 }
530 return result;
531 }
532
533 @Override public Collection<V> get(K key) {
534 return unmodifiableValueCollection(delegate.get(key));
535 }
536
537 @Override public Multiset<K> keys() {
538 Multiset<K> result = keys;
539 if (result == null) {
540 keys = result = Multisets.unmodifiableMultiset(delegate.keys());
541 }
542 return result;
543 }
544
545 @Override public Set<K> keySet() {
546 Set<K> result = keySet;
547 if (result == null) {
548 keySet = result = Collections.unmodifiableSet(delegate.keySet());
549 }
550 return result;
551 }
552
553 @Override public boolean put(K key, V value) {
554 throw new UnsupportedOperationException();
555 }
556
557 @Override public boolean putAll(K key,
558 @SuppressWarnings("hiding") Iterable<? extends V> values) {
559 throw new UnsupportedOperationException();
560 }
561
562 @Override
563 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
564 throw new UnsupportedOperationException();
565 }
566
567 @Override public boolean remove(Object key, Object value) {
568 throw new UnsupportedOperationException();
569 }
570
571 @Override public Collection<V> removeAll(Object key) {
572 throw new UnsupportedOperationException();
573 }
574
575 @Override public Collection<V> replaceValues(K key,
576 @SuppressWarnings("hiding") Iterable<? extends V> values) {
577 throw new UnsupportedOperationException();
578 }
579
580 @Override public Collection<V> values() {
581 Collection<V> result = values;
582 if (result == null) {
583 values = result = Collections.unmodifiableCollection(delegate.values());
584 }
585 return result;
586 }
587
588 private static final long serialVersionUID = 0;
589 }
590
591 private static class UnmodifiableAsMapValues<V>
592 extends ForwardingCollection<Collection<V>> {
593 final Collection<Collection<V>> delegate;
594 UnmodifiableAsMapValues(Collection<Collection<V>> delegate) {
595 this.delegate = Collections.unmodifiableCollection(delegate);
596 }
597 @Override protected Collection<Collection<V>> delegate() {
598 return delegate;
599 }
600 @Override public Iterator<Collection<V>> iterator() {
601 final Iterator<Collection<V>> iterator = delegate.iterator();
602 return new Iterator<Collection<V>>() {
603 public boolean hasNext() {
604 return iterator.hasNext();
605 }
606 public Collection<V> next() {
607 return unmodifiableValueCollection(iterator.next());
608 }
609 public void remove() {
610 throw new UnsupportedOperationException();
611 }
612 };
613 }
614 @Override public Object[] toArray() {
615 return ObjectArrays.toArrayImpl(this);
616 }
617 @Override public <T> T[] toArray(T[] array) {
618 return ObjectArrays.toArrayImpl(this, array);
619 }
620 @Override public boolean contains(Object o) {
621 return Iterators.contains(iterator(), o);
622 }
623 @Override public boolean containsAll(Collection<?> c) {
624 return Collections2.containsAll(this, c);
625 }
626 }
627
628 private static class UnmodifiableListMultimap<K, V>
629 extends UnmodifiableMultimap<K, V> implements ListMultimap<K, V> {
630 UnmodifiableListMultimap(ListMultimap<K, V> delegate) {
631 super(delegate);
632 }
633 @Override public ListMultimap<K, V> delegate() {
634 return (ListMultimap<K, V>) super.delegate();
635 }
636 @Override public List<V> get(K key) {
637 return Collections.unmodifiableList(delegate().get(key));
638 }
639 @Override public List<V> removeAll(Object key) {
640 throw new UnsupportedOperationException();
641 }
642 @Override public List<V> replaceValues(
643 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
644 throw new UnsupportedOperationException();
645 }
646 private static final long serialVersionUID = 0;
647 }
648
649 private static class UnmodifiableSetMultimap<K, V>
650 extends UnmodifiableMultimap<K, V> implements SetMultimap<K, V> {
651 UnmodifiableSetMultimap(SetMultimap<K, V> delegate) {
652 super(delegate);
653 }
654 @Override public SetMultimap<K, V> delegate() {
655 return (SetMultimap<K, V>) super.delegate();
656 }
657 @Override public Set<V> get(K key) {
658 /*
659 * Note that this doesn't return a SortedSet when delegate is a
660 * SortedSetMultiset, unlike (SortedSet<V>) super.get().
661 */
662 return Collections.unmodifiableSet(delegate().get(key));
663 }
664 @Override public Set<Map.Entry<K, V>> entries() {
665 return Maps.unmodifiableEntrySet(delegate().entries());
666 }
667 @Override public Set<V> removeAll(Object key) {
668 throw new UnsupportedOperationException();
669 }
670 @Override public Set<V> replaceValues(
671 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
672 throw new UnsupportedOperationException();
673 }
674 private static final long serialVersionUID = 0;
675 }
676
677 private static class UnmodifiableSortedSetMultimap<K, V>
678 extends UnmodifiableSetMultimap<K, V> implements SortedSetMultimap<K, V> {
679 UnmodifiableSortedSetMultimap(SortedSetMultimap<K, V> delegate) {
680 super(delegate);
681 }
682 @Override public SortedSetMultimap<K, V> delegate() {
683 return (SortedSetMultimap<K, V>) super.delegate();
684 }
685 @Override public SortedSet<V> get(K key) {
686 return Collections.unmodifiableSortedSet(delegate().get(key));
687 }
688 @Override public SortedSet<V> removeAll(Object key) {
689 throw new UnsupportedOperationException();
690 }
691 @Override public SortedSet<V> replaceValues(
692 K key, @SuppressWarnings("hiding") Iterable<? extends V> values) {
693 throw new UnsupportedOperationException();
694 }
695 public Comparator<? super V> valueComparator() {
696 return delegate().valueComparator();
697 }
698 private static final long serialVersionUID = 0;
699 }
700
701 /**
702 * Returns a synchronized (thread-safe) {@code SetMultimap} backed by the
703 * specified multimap.
704 *
705 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
706 *
707 * <p>The returned multimap will be serializable if the specified multimap is
708 * serializable.
709 *
710 * @param multimap the multimap to be wrapped
711 * @return a synchronized view of the specified multimap
712 */
713 public static <K, V> SetMultimap<K, V> synchronizedSetMultimap(
714 SetMultimap<K, V> multimap) {
715 return Synchronized.setMultimap(multimap, null);
716 }
717
718 /**
719 * Returns an unmodifiable view of the specified {@code SetMultimap}. Query
720 * operations on the returned multimap "read through" to the specified
721 * multimap, and attempts to modify the returned multimap, either directly or
722 * through the multimap's views, result in an
723 * {@code UnsupportedOperationException}.
724 *
725 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
726 * {@link Multimap#replaceValues} methods return collections that are
727 * modifiable.
728 *
729 * <p>The returned multimap will be serializable if the specified multimap is
730 * serializable.
731 *
732 * @param delegate the multimap for which an unmodifiable view is to be
733 * returned
734 * @return an unmodifiable view of the specified multimap
735 */
736 public static <K, V> SetMultimap<K, V> unmodifiableSetMultimap(
737 SetMultimap<K, V> delegate) {
738 return new UnmodifiableSetMultimap<K, V>(delegate);
739 }
740
741 /**
742 * Returns a synchronized (thread-safe) {@code SortedSetMultimap} backed by
743 * the specified multimap.
744 *
745 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
746 *
747 * <p>The returned multimap will be serializable if the specified multimap is
748 * serializable.
749 *
750 * @param multimap the multimap to be wrapped
751 * @return a synchronized view of the specified multimap
752 */
753 public static <K, V> SortedSetMultimap<K, V>
754 synchronizedSortedSetMultimap(SortedSetMultimap<K, V> multimap) {
755 return Synchronized.sortedSetMultimap(multimap, null);
756 }
757
758 /**
759 * Returns an unmodifiable view of the specified {@code SortedSetMultimap}.
760 * Query operations on the returned multimap "read through" to the specified
761 * multimap, and attempts to modify the returned multimap, either directly or
762 * through the multimap's views, result in an
763 * {@code UnsupportedOperationException}.
764 *
765 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
766 * {@link Multimap#replaceValues} methods return collections that are
767 * modifiable.
768 *
769 * <p>The returned multimap will be serializable if the specified multimap is
770 * serializable.
771 *
772 * @param delegate the multimap for which an unmodifiable view is to be
773 * returned
774 * @return an unmodifiable view of the specified multimap
775 */
776 public static <K, V> SortedSetMultimap<K, V> unmodifiableSortedSetMultimap(
777 SortedSetMultimap<K, V> delegate) {
778 return new UnmodifiableSortedSetMultimap<K, V>(delegate);
779 }
780
781 /**
782 * Returns a synchronized (thread-safe) {@code ListMultimap} backed by the
783 * specified multimap.
784 *
785 * <p>You must follow the warnings described in {@link #synchronizedMultimap}.
786 *
787 * @param multimap the multimap to be wrapped
788 * @return a synchronized view of the specified multimap
789 */
790 public static <K, V> ListMultimap<K, V> synchronizedListMultimap(
791 ListMultimap<K, V> multimap) {
792 return Synchronized.listMultimap(multimap, null);
793 }
794
795 /**
796 * Returns an unmodifiable view of the specified {@code ListMultimap}. Query
797 * operations on the returned multimap "read through" to the specified
798 * multimap, and attempts to modify the returned multimap, either directly or
799 * through the multimap's views, result in an
800 * {@code UnsupportedOperationException}.
801 *
802 * <p>Note that the generated multimap's {@link Multimap#removeAll} and
803 * {@link Multimap#replaceValues} methods return collections that are
804 * modifiable.
805 *
806 * <p>The returned multimap will be serializable if the specified multimap is
807 * serializable.
808 *
809 * @param delegate the multimap for which an unmodifiable view is to be
810 * returned
811 * @return an unmodifiable view of the specified multimap
812 */
813 public static <K, V> ListMultimap<K, V> unmodifiableListMultimap(
814 ListMultimap<K, V> delegate) {
815 return new UnmodifiableListMultimap<K, V>(delegate);
816 }
817
818 /**
819 * Returns an unmodifiable view of the specified collection, preserving the
820 * interface for instances of {@code SortedSet}, {@code Set}, {@code List} and
821 * {@code Collection}, in that order of preference.
822 *
823 * @param collection the collection for which to return an unmodifiable view
824 * @return an unmodifiable view of the collection
825 */
826 private static <V> Collection<V> unmodifiableValueCollection(
827 Collection<V> collection) {
828 if (collection instanceof SortedSet) {
829 return Collections.unmodifiableSortedSet((SortedSet<V>) collection);
830 } else if (collection instanceof Set) {
831 return Collections.unmodifiableSet((Set<V>) collection);
832 } else if (collection instanceof List) {
833 return Collections.unmodifiableList((List<V>) collection);
834 }
835 return Collections.unmodifiableCollection(collection);
836 }
837
838 /**
839 * Returns an unmodifiable view of the specified multimap {@code asMap} entry.
840 * The {@link Entry#setValue} operation throws an {@link
841 * UnsupportedOperationException}, and the collection returned by {@code
842 * getValue} is also an unmodifiable (type-preserving) view. This also has the
843 * side-effect of redefining equals to comply with the Map.Entry contract, and
844 * to avoid a possible nefarious implementation of equals.
845 *
846 * @param entry the entry for which to return an unmodifiable view
847 * @return an unmodifiable view of the entry
848 */
849 private static <K, V> Map.Entry<K, Collection<V>> unmodifiableAsMapEntry(
850 final Map.Entry<K, Collection<V>> entry) {
851 checkNotNull(entry);
852 return new AbstractMapEntry<K, Collection<V>>() {
853 @Override public K getKey() {
854 return entry.getKey();
855 }
856
857 @Override public Collection<V> getValue() {
858 return unmodifiableValueCollection(entry.getValue());
859 }
860 };
861 }
862
863 /**
864 * Returns an unmodifiable view of the specified collection of entries. The
865 * {@link Entry#setValue} operation throws an {@link
866 * UnsupportedOperationException}. If the specified collection is a {@code
867 * Set}, the returned collection is also a {@code Set}.
868 *
869 * @param entries the entries for which to return an unmodifiable view
870 * @return an unmodifiable view of the entries
871 */
872 private static <K, V> Collection<Entry<K, V>> unmodifiableEntries(
873 Collection<Entry<K, V>> entries) {
874 if (entries instanceof Set) {
875 return Maps.unmodifiableEntrySet((Set<Entry<K, V>>) entries);
876 }
877 return new Maps.UnmodifiableEntries<K, V>(
878 Collections.unmodifiableCollection(entries));
879 }
880
881 /**
882 * Returns an unmodifiable view of the specified set of {@code asMap} entries.
883 * The {@link Entry#setValue} operation throws an {@link
884 * UnsupportedOperationException}, as do any operations that attempt to modify
885 * the returned collection.
886 *
887 * @param asMapEntries the {@code asMap} entries for which to return an
888 * unmodifiable view
889 * @return an unmodifiable view of the collection entries
890 */
891 private static <K, V> Set<Entry<K, Collection<V>>> unmodifiableAsMapEntries(
892 Set<Entry<K, Collection<V>>> asMapEntries) {
893 return new UnmodifiableAsMapEntries<K, V>(
894 Collections.unmodifiableSet(asMapEntries));
895 }
896
897 /** @see Multimaps#unmodifiableAsMapEntries */
898 static class UnmodifiableAsMapEntries<K, V>
899 extends ForwardingSet<Entry<K, Collection<V>>> {
900 private final Set<Entry<K, Collection<V>>> delegate;
901 UnmodifiableAsMapEntries(Set<Entry<K, Collection<V>>> delegate) {
902 this.delegate = delegate;
903 }
904
905 @Override protected Set<Entry<K, Collection<V>>> delegate() {
906 return delegate;
907 }
908
909 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
910 final Iterator<Entry<K, Collection<V>>> iterator = delegate.iterator();
911 return new ForwardingIterator<Entry<K, Collection<V>>>() {
912 @Override protected Iterator<Entry<K, Collection<V>>> delegate() {
913 return iterator;
914 }
915 @Override public Entry<K, Collection<V>> next() {
916 return unmodifiableAsMapEntry(iterator.next());
917 }
918 };
919 }
920
921 @Override public Object[] toArray() {
922 return ObjectArrays.toArrayImpl(this);
923 }
924
925 @Override public <T> T[] toArray(T[] array) {
926 return ObjectArrays.toArrayImpl(this, array);
927 }
928
929 @Override public boolean contains(Object o) {
930 return Maps.containsEntryImpl(delegate(), o);
931 }
932
933 @Override public boolean containsAll(Collection<?> c) {
934 return Collections2.containsAll(this, c);
935 }
936
937 @Override public boolean equals(@Nullable Object object) {
938 return Collections2.setEquals(this, object);
939 }
940 }
941
942 /**
943 * Returns a multimap view of the specified map. The multimap is backed by the
944 * map, so changes to the map are reflected in the multimap, and vice versa.
945 * If the map is modified while an iteration over one of the multimap's
946 * collection views is in progress (except through the iterator's own {@code
947 * remove} operation, or through the {@code setValue} operation on a map entry
948 * returned by the iterator), the results of the iteration are undefined.
949 *
950 * <p>The multimap supports mapping removal, which removes the corresponding
951 * mapping from the map. It does not support any operations which might add
952 * mappings, such as {@code put}, {@code putAll} or {@code replaceValues}.
953 *
954 * <p>The returned multimap will be serializable if the specified map is
955 * serializable.
956 *
957 * @param map the backing map for the returned multimap view
958 */
959 public static <K, V> SetMultimap<K, V> forMap(Map<K, V> map) {
960 return new MapMultimap<K, V>(map);
961 }
962
963 /** @see Multimaps#forMap */
964 private static class MapMultimap<K, V>
965 implements SetMultimap<K, V>, Serializable {
966 final Map<K, V> map;
967 transient Map<K, Collection<V>> asMap;
968
969 MapMultimap(Map<K, V> map) {
970 this.map = checkNotNull(map);
971 }
972
973 public int size() {
974 return map.size();
975 }
976
977 public boolean isEmpty() {
978 return map.isEmpty();
979 }
980
981 public boolean containsKey(Object key) {
982 return map.containsKey(key);
983 }
984
985 public boolean containsValue(Object value) {
986 return map.containsValue(value);
987 }
988
989 public boolean containsEntry(Object key, Object value) {
990 return map.entrySet().contains(Maps.immutableEntry(key, value));
991 }
992
993 public Set<V> get(final K key) {
994 return new AbstractSet<V>() {
995 @Override public Iterator<V> iterator() {
996 return new Iterator<V>() {
997 int i;
998
999 public boolean hasNext() {
1000 return (i == 0) && map.containsKey(key);
1001 }
1002
1003 public V next() {
1004 if (!hasNext()) {
1005 throw new NoSuchElementException();
1006 }
1007 i++;
1008 return map.get(key);
1009 }
1010
1011 public void remove() {
1012 checkState(i == 1);
1013 i = -1;
1014 map.remove(key);
1015 }
1016 };
1017 }
1018
1019 @Override public int size() {
1020 return map.containsKey(key) ? 1 : 0;
1021 }
1022 };
1023 }
1024
1025 public boolean put(K key, V value) {
1026 throw new UnsupportedOperationException();
1027 }
1028
1029 public boolean putAll(K key, Iterable<? extends V> values) {
1030 throw new UnsupportedOperationException();
1031 }
1032
1033 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
1034 throw new UnsupportedOperationException();
1035 }
1036
1037 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
1038 throw new UnsupportedOperationException();
1039 }
1040
1041 public boolean remove(Object key, Object value) {
1042 return map.entrySet().remove(Maps.immutableEntry(key, value));
1043 }
1044
1045 public Set<V> removeAll(Object key) {
1046 Set<V> values = new HashSet<V>(2);
1047 if (!map.containsKey(key)) {
1048 return values;
1049 }
1050 values.add(map.remove(key));
1051 return values;
1052 }
1053
1054 public void clear() {
1055 map.clear();
1056 }
1057
1058 public Set<K> keySet() {
1059 return map.keySet();
1060 }
1061
1062 public Multiset<K> keys() {
1063 return Multisets.forSet(map.keySet());
1064 }
1065
1066 public Collection<V> values() {
1067 return map.values();
1068 }
1069
1070 public Set<Entry<K, V>> entries() {
1071 return map.entrySet();
1072 }
1073
1074 public Map<K, Collection<V>> asMap() {
1075 Map<K, Collection<V>> result = asMap;
1076 if (result == null) {
1077 asMap = result = new AsMap();
1078 }
1079 return result;
1080 }
1081
1082 @Override public boolean equals(@Nullable Object object) {
1083 if (object == this) {
1084 return true;
1085 }
1086 if (object instanceof Multimap) {
1087 Multimap<?, ?> that = (Multimap<?, ?>) object;
1088 return this.size() == that.size() && asMap().equals(that.asMap());
1089 }
1090 return false;
1091 }
1092
1093 @Override public int hashCode() {
1094 return map.hashCode();
1095 }
1096
1097 private static final MapJoiner joiner
1098 = Joiner.on("], ").withKeyValueSeparator("=[").useForNull("null");
1099
1100 @Override public String toString() {
1101 if (map.isEmpty()) {
1102 return "{}";
1103 }
1104 StringBuilder builder = new StringBuilder(map.size() * 16).append('{');
1105 joiner.appendTo(builder, map);
1106 return builder.append("]}").toString();
1107 }
1108
1109 /** @see MapMultimap#asMap */
1110 class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
1111 @Override public int size() {
1112 return map.size();
1113 }
1114
1115 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
1116 return new Iterator<Entry<K, Collection<V>>>() {
1117 final Iterator<K> keys = map.keySet().iterator();
1118
1119 public boolean hasNext() {
1120 return keys.hasNext();
1121 }
1122 public Entry<K, Collection<V>> next() {
1123 final K key = keys.next();
1124 return new AbstractMapEntry<K, Collection<V>>() {
1125 @Override public K getKey() {
1126 return key;
1127 }
1128 @Override public Collection<V> getValue() {
1129 return get(key);
1130 }
1131 };
1132 }
1133 public void remove() {
1134 keys.remove();
1135 }
1136 };
1137 }
1138
1139 @Override public boolean contains(Object o) {
1140 if (!(o instanceof Entry)) {
1141 return false;
1142 }
1143 Entry<?, ?> entry = (Entry<?, ?>) o;
1144 if (!(entry.getValue() instanceof Set)) {
1145 return false;
1146 }
1147 Set<?> set = (Set<?>) entry.getValue();
1148 return (set.size() == 1)
1149 && containsEntry(entry.getKey(), set.iterator().next());
1150 }
1151
1152 @Override public boolean remove(Object o) {
1153 if (!(o instanceof Entry)) {
1154 return false;
1155 }
1156 Entry<?, ?> entry = (Entry<?, ?>) o;
1157 if (!(entry.getValue() instanceof Set)) {
1158 return false;
1159 }
1160 Set<?> set = (Set<?>) entry.getValue();
1161 return (set.size() == 1)
1162 && map.entrySet().remove(
1163 Maps.immutableEntry(entry.getKey(), set.iterator().next()));
1164 }
1165 }
1166
1167 /** @see MapMultimap#asMap */
1168 class AsMap extends Maps.ImprovedAbstractMap<K, Collection<V>> {
1169 @Override protected Set<Entry<K, Collection<V>>> createEntrySet() {
1170 return new AsMapEntries();
1171 }
1172
1173 // The following methods are included for performance.
1174
1175 @Override public boolean containsKey(Object key) {
1176 return map.containsKey(key);
1177 }
1178
1179 @SuppressWarnings("unchecked")
1180 @Override public Collection<V> get(Object key) {
1181 Collection<V> collection = MapMultimap.this.get((K) key);
1182 return collection.isEmpty() ? null : collection;
1183 }
1184
1185 @Override public Collection<V> remove(Object key) {
1186 Collection<V> collection = removeAll(key);
1187 return collection.isEmpty() ? null : collection;
1188 }
1189 }
1190 private static final long serialVersionUID = 7845222491160860175L;
1191 }
1192
1193 /**
1194 * Creates an index {@code ImmutableMultimap} that contains the results of
1195 * applying a specified function to each item in an {@code Iterable} of
1196 * values. Each value will be stored as a value in the resulting multimap,
1197 * yielding a multimap with the same size as the input iterable. The key used
1198 * to store that value in the multimap will be the result of calling the
1199 * function on that value. The resulting multimap is created as an immutable
1200 * snapshot, it does <em>not</em> reflect subsequent changes on the input
1201 * iterable.
1202 *
1203 * <p>For example, <pre class="code"> {@code
1204 *
1205 * List<String> badGuys
1206 * = Arrays.asList("Inky", "Blinky", "Pinky", "Pinky", "Clyde");
1207 * Function<String, Integer> stringLengthFunction = ...;
1208 * Multimap<Integer, String> index
1209 * = Multimaps.index(badGuys, stringLengthFunction);
1210 * System.out.println(index);}</pre>
1211 *
1212 * prints <pre class="code"> {@code
1213 *
1214 * {4=[Inky], 5=[Pinky, Pinky, Clyde], 6=[Blinky]}}</pre>
1215 *
1216 * <p>The returned multimap is serializable if its keys and values are all
1217 * serializable.
1218 *
1219 * @param values the values to use when constructing the {@code
1220 * ImmutableMultimap}
1221 * @param keyFunction the function used to produce the key for each value
1222 * @return {@code ImmutableMultimap} mapping the result of evaluating the
1223 * function {@code keyFunction} on each value in the input collection to
1224 * that value
1225 * @throws NullPointerException if any of the following cases is true: <ul>
1226 * <li> {@code values} is null
1227 * <li> {@code keyFunction} is null
1228 * <li> An element in {@code values} is null
1229 * <li> {@code keyFunction} returns null for any element of {@code values}
1230 * </ul>
1231 */
1232 public static <K, V> ImmutableListMultimap<K, V> index(
1233 Iterable<V> values, Function<? super V, K> keyFunction) {
1234 checkNotNull(keyFunction);
1235 ImmutableListMultimap.Builder<K, V> builder
1236 = ImmutableListMultimap.builder();
1237 for (V value : values) {
1238 Preconditions.checkNotNull(value, values);
1239 builder.put(keyFunction.apply(value), value);
1240 }
1241 return builder.build();
1242 }
1243 }