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