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    }