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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.base.Preconditions.checkState;
021
022import com.google.common.annotations.Beta;
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.base.Function;
026import com.google.common.base.Joiner;
027import com.google.common.base.Joiner.MapJoiner;
028import com.google.common.base.Supplier;
029import com.google.common.collect.Collections2.TransformedCollection;
030import com.google.common.collect.Maps.EntryTransformer;
031
032import java.io.IOException;
033import java.io.ObjectInputStream;
034import java.io.ObjectOutputStream;
035import java.io.Serializable;
036import java.util.AbstractSet;
037import java.util.Collection;
038import java.util.Collections;
039import java.util.Comparator;
040import java.util.HashSet;
041import java.util.Iterator;
042import java.util.List;
043import java.util.Map;
044import java.util.Map.Entry;
045import java.util.NoSuchElementException;
046import java.util.Set;
047import java.util.SortedSet;
048
049import 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)
061public 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}