001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
021import static com.google.common.collect.Maps.immutableEntry;
022import static java.util.Objects.requireNonNull;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.errorprone.annotations.DoNotCall;
029import com.google.errorprone.annotations.DoNotMock;
030import com.google.j2objc.annotations.Weak;
031import com.google.j2objc.annotations.WeakOuter;
032import java.io.InvalidObjectException;
033import java.io.ObjectInputStream;
034import java.io.Serializable;
035import java.util.ArrayList;
036import java.util.Arrays;
037import java.util.Collection;
038import java.util.Comparator;
039import java.util.Iterator;
040import java.util.Map;
041import java.util.Map.Entry;
042import java.util.Set;
043import java.util.Spliterator;
044import java.util.function.BiConsumer;
045import javax.annotation.CheckForNull;
046import org.checkerframework.checker.nullness.qual.Nullable;
047
048/**
049 * A {@link Multimap} whose contents will never change, with many other important properties
050 * detailed at {@link ImmutableCollection}.
051 *
052 * <p><b>Warning:</b> avoid <i>direct</i> usage of {@link ImmutableMultimap} as a type (as with
053 * {@link Multimap} itself). Prefer subtypes such as {@link ImmutableSetMultimap} or {@link
054 * ImmutableListMultimap}, which have well-defined {@link #equals} semantics, thus avoiding a common
055 * source of bugs and confusion.
056 *
057 * <p><b>Note:</b> every {@link ImmutableMultimap} offers an {@link #inverse} view, so there is no
058 * need for a distinct {@code ImmutableBiMultimap} type.
059 *
060 * <p><a id="iteration"></a>
061 *
062 * <p><b>Key-grouped iteration.</b> All view collections follow the same iteration order. In all
063 * current implementations, the iteration order always keeps multiple entries with the same key
064 * together. Any creation method that would customarily respect insertion order (such as {@link
065 * #copyOf(Multimap)}) instead preserves key-grouped order by inserting entries for an existing key
066 * immediately after the last entry having that key.
067 *
068 * <p>See the Guava User Guide article on <a href=
069 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
070 *
071 * @author Jared Levy
072 * @since 2.0
073 */
074@GwtCompatible(emulated = true)
075@ElementTypesAreNonnullByDefault
076public abstract class ImmutableMultimap<K, V> extends BaseImmutableMultimap<K, V>
077    implements Serializable {
078
079  /**
080   * Returns an empty multimap.
081   *
082   * <p><b>Performance note:</b> the instance returned is a singleton.
083   */
084  public static <K, V> ImmutableMultimap<K, V> of() {
085    return ImmutableListMultimap.of();
086  }
087
088  /** Returns an immutable multimap containing a single entry. */
089  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1) {
090    return ImmutableListMultimap.of(k1, v1);
091  }
092
093  /** Returns an immutable multimap containing the given entries, in order. */
094  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2) {
095    return ImmutableListMultimap.of(k1, v1, k2, v2);
096  }
097
098  /**
099   * Returns an immutable multimap containing the given entries, in the "key-grouped" insertion
100   * order described in the <a href="#iteration">class documentation</a>.
101   */
102  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
103    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3);
104  }
105
106  /**
107   * Returns an immutable multimap containing the given entries, in the "key-grouped" insertion
108   * order described in the <a href="#iteration">class documentation</a>.
109   */
110  public static <K, V> ImmutableMultimap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
111    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4);
112  }
113
114  /**
115   * Returns an immutable multimap containing the given entries, in the "key-grouped" insertion
116   * order described in the <a href="#iteration">class documentation</a>.
117   */
118  public static <K, V> ImmutableMultimap<K, V> of(
119      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
120    return ImmutableListMultimap.of(k1, v1, k2, v2, k3, v3, k4, v4, k5, v5);
121  }
122
123  // looking for of() with > 5 entries? Use the builder instead.
124
125  /**
126   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
127   * Builder} constructor.
128   */
129  public static <K, V> Builder<K, V> builder() {
130    return new Builder<>();
131  }
132
133  /**
134   * A builder for creating immutable multimap instances, especially {@code public static final}
135   * multimaps ("constant multimaps"). Example:
136   *
137   * <pre>{@code
138   * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
139   *     new ImmutableMultimap.Builder<String, Integer>()
140   *         .put("one", 1)
141   *         .putAll("several", 1, 2, 3)
142   *         .putAll("many", 1, 2, 3, 4, 5)
143   *         .build();
144   * }</pre>
145   *
146   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
147   * multiple multimaps in series. Each multimap contains the key-value mappings in the previously
148   * created multimaps.
149   *
150   * @since 2.0
151   */
152  @DoNotMock
153  public static class Builder<K, V> {
154    final Map<K, Collection<V>> builderMap;
155    @CheckForNull Comparator<? super K> keyComparator;
156    @CheckForNull Comparator<? super V> valueComparator;
157
158    /**
159     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
160     * ImmutableMultimap#builder}.
161     */
162    public Builder() {
163      this.builderMap = Platform.preservesInsertionOrderOnPutsMap();
164    }
165
166    Collection<V> newMutableValueCollection() {
167      return new ArrayList<>();
168    }
169
170    /** Adds a key-value mapping to the built multimap. */
171    @CanIgnoreReturnValue
172    public Builder<K, V> put(K key, V value) {
173      checkEntryNotNull(key, value);
174      Collection<V> valueCollection = builderMap.get(key);
175      if (valueCollection == null) {
176        builderMap.put(key, valueCollection = newMutableValueCollection());
177      }
178      valueCollection.add(value);
179      return this;
180    }
181
182    /**
183     * Adds an entry to the built multimap.
184     *
185     * @since 11.0
186     */
187    @CanIgnoreReturnValue
188    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
189      return put(entry.getKey(), entry.getValue());
190    }
191
192    /**
193     * Adds entries to the built multimap.
194     *
195     * @since 19.0
196     */
197    @CanIgnoreReturnValue
198    @Beta
199    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
200      for (Entry<? extends K, ? extends V> entry : entries) {
201        put(entry);
202      }
203      return this;
204    }
205
206    /**
207     * Stores a collection of values with the same key in the built multimap.
208     *
209     * @throws NullPointerException if {@code key}, {@code values}, or any element in {@code values}
210     *     is null. The builder is left in an invalid state.
211     */
212    @CanIgnoreReturnValue
213    public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
214      if (key == null) {
215        throw new NullPointerException("null key in entry: null=" + Iterables.toString(values));
216      }
217      Collection<V> valueCollection = builderMap.get(key);
218      if (valueCollection != null) {
219        for (V value : values) {
220          checkEntryNotNull(key, value);
221          valueCollection.add(value);
222        }
223        return this;
224      }
225      Iterator<? extends V> valuesItr = values.iterator();
226      if (!valuesItr.hasNext()) {
227        return this;
228      }
229      valueCollection = newMutableValueCollection();
230      while (valuesItr.hasNext()) {
231        V value = valuesItr.next();
232        checkEntryNotNull(key, value);
233        valueCollection.add(value);
234      }
235      builderMap.put(key, valueCollection);
236      return this;
237    }
238
239    /**
240     * Stores an array of values with the same key in the built multimap.
241     *
242     * @throws NullPointerException if the key or any value is null. The builder is left in an
243     *     invalid state.
244     */
245    @CanIgnoreReturnValue
246    public Builder<K, V> putAll(K key, V... values) {
247      return putAll(key, Arrays.asList(values));
248    }
249
250    /**
251     * Stores another multimap's entries in the built multimap. The generated multimap's key and
252     * value orderings correspond to the iteration ordering of the {@code multimap.asMap()} view,
253     * with new keys and values following any existing keys and values.
254     *
255     * @throws NullPointerException if any key or value in {@code multimap} is null. The builder is
256     *     left in an invalid state.
257     */
258    @CanIgnoreReturnValue
259    public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
260      for (Entry<? extends K, ? extends Collection<? extends V>> entry :
261          multimap.asMap().entrySet()) {
262        putAll(entry.getKey(), entry.getValue());
263      }
264      return this;
265    }
266
267    /**
268     * Specifies the ordering of the generated multimap's keys.
269     *
270     * @since 8.0
271     */
272    @CanIgnoreReturnValue
273    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
274      this.keyComparator = checkNotNull(keyComparator);
275      return this;
276    }
277
278    /**
279     * Specifies the ordering of the generated multimap's values for each key.
280     *
281     * @since 8.0
282     */
283    @CanIgnoreReturnValue
284    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
285      this.valueComparator = checkNotNull(valueComparator);
286      return this;
287    }
288
289    @CanIgnoreReturnValue
290    Builder<K, V> combine(Builder<K, V> other) {
291      for (Map.Entry<K, Collection<V>> entry : other.builderMap.entrySet()) {
292        putAll(entry.getKey(), entry.getValue());
293      }
294      return this;
295    }
296
297    /** Returns a newly-created immutable multimap. */
298    public ImmutableMultimap<K, V> build() {
299      Collection<Map.Entry<K, Collection<V>>> mapEntries = builderMap.entrySet();
300      if (keyComparator != null) {
301        mapEntries = Ordering.from(keyComparator).<K>onKeys().immutableSortedCopy(mapEntries);
302      }
303      return ImmutableListMultimap.fromMapEntries(mapEntries, valueComparator);
304    }
305  }
306
307  /**
308   * Returns an immutable multimap containing the same mappings as {@code multimap}, in the
309   * "key-grouped" iteration order described in the class documentation.
310   *
311   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
312   * safe to do so. The exact circumstances under which a copy will or will not be performed are
313   * undocumented and subject to change.
314   *
315   * @throws NullPointerException if any key or value in {@code multimap} is null
316   */
317  public static <K, V> ImmutableMultimap<K, V> copyOf(Multimap<? extends K, ? extends V> multimap) {
318    if (multimap instanceof ImmutableMultimap) {
319      @SuppressWarnings("unchecked") // safe since multimap is not writable
320      ImmutableMultimap<K, V> kvMultimap = (ImmutableMultimap<K, V>) multimap;
321      if (!kvMultimap.isPartialView()) {
322        return kvMultimap;
323      }
324    }
325    return ImmutableListMultimap.copyOf(multimap);
326  }
327
328  /**
329   * Returns an immutable multimap containing the specified entries. The returned multimap iterates
330   * over keys in the order they were first encountered in the input, and the values for each key
331   * are iterated in the order they were encountered.
332   *
333   * @throws NullPointerException if any key, value, or entry is null
334   * @since 19.0
335   */
336  @Beta
337  public static <K, V> ImmutableMultimap<K, V> copyOf(
338      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
339    return ImmutableListMultimap.copyOf(entries);
340  }
341
342  final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
343  final transient int size;
344
345  // These constants allow the deserialization code to set final fields. This
346  // holder class makes sure they are not initialized unless an instance is
347  // deserialized.
348  @GwtIncompatible // java serialization is not supported
349  static class FieldSettersHolder {
350    static final Serialization.FieldSetter<ImmutableMultimap> MAP_FIELD_SETTER =
351        Serialization.getFieldSetter(ImmutableMultimap.class, "map");
352    static final Serialization.FieldSetter<ImmutableMultimap> SIZE_FIELD_SETTER =
353        Serialization.getFieldSetter(ImmutableMultimap.class, "size");
354  }
355
356  ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, int size) {
357    this.map = map;
358    this.size = size;
359  }
360
361  // mutators (not supported)
362
363  /**
364   * Guaranteed to throw an exception and leave the multimap unmodified.
365   *
366   * @throws UnsupportedOperationException always
367   * @deprecated Unsupported operation.
368   */
369  @CanIgnoreReturnValue
370  @Deprecated
371  @Override
372  @DoNotCall("Always throws UnsupportedOperationException")
373  // DoNotCall wants this to be final, but we want to override it to return more specific types.
374  // Inheritance is closed, and all subtypes are @DoNotCall, so this is safe to suppress.
375  @SuppressWarnings("DoNotCall")
376  public ImmutableCollection<V> removeAll(@CheckForNull Object key) {
377    throw new UnsupportedOperationException();
378  }
379
380  /**
381   * Guaranteed to throw an exception and leave the multimap unmodified.
382   *
383   * @throws UnsupportedOperationException always
384   * @deprecated Unsupported operation.
385   */
386  @CanIgnoreReturnValue
387  @Deprecated
388  @Override
389  @DoNotCall("Always throws UnsupportedOperationException")
390  // DoNotCall wants this to be final, but we want to override it to return more specific types.
391  // Inheritance is closed, and all subtypes are @DoNotCall, so this is safe to suppress.
392  @SuppressWarnings("DoNotCall")
393  public ImmutableCollection<V> replaceValues(K key, Iterable<? extends V> values) {
394    throw new UnsupportedOperationException();
395  }
396
397  /**
398   * Guaranteed to throw an exception and leave the multimap unmodified.
399   *
400   * @throws UnsupportedOperationException always
401   * @deprecated Unsupported operation.
402   */
403  @Deprecated
404  @Override
405  @DoNotCall("Always throws UnsupportedOperationException")
406  public final void clear() {
407    throw new UnsupportedOperationException();
408  }
409
410  /**
411   * Returns an immutable collection of the values for the given key. If no mappings in the multimap
412   * have the provided key, an empty immutable collection is returned. The values are in the same
413   * order as the parameters used to build this multimap.
414   */
415  @Override
416  public abstract ImmutableCollection<V> get(K key);
417
418  /**
419   * Returns an immutable multimap which is the inverse of this one. For every key-value mapping in
420   * the original, the result will have a mapping with key and value reversed.
421   *
422   * @since 11.0
423   */
424  public abstract ImmutableMultimap<V, K> inverse();
425
426  /**
427   * Guaranteed to throw an exception and leave the multimap unmodified.
428   *
429   * @throws UnsupportedOperationException always
430   * @deprecated Unsupported operation.
431   */
432  @CanIgnoreReturnValue
433  @Deprecated
434  @Override
435  @DoNotCall("Always throws UnsupportedOperationException")
436  public final boolean put(K key, V value) {
437    throw new UnsupportedOperationException();
438  }
439
440  /**
441   * Guaranteed to throw an exception and leave the multimap unmodified.
442   *
443   * @throws UnsupportedOperationException always
444   * @deprecated Unsupported operation.
445   */
446  @CanIgnoreReturnValue
447  @Deprecated
448  @Override
449  @DoNotCall("Always throws UnsupportedOperationException")
450  public final boolean putAll(K key, Iterable<? extends V> values) {
451    throw new UnsupportedOperationException();
452  }
453
454  /**
455   * Guaranteed to throw an exception and leave the multimap unmodified.
456   *
457   * @throws UnsupportedOperationException always
458   * @deprecated Unsupported operation.
459   */
460  @CanIgnoreReturnValue
461  @Deprecated
462  @Override
463  @DoNotCall("Always throws UnsupportedOperationException")
464  public final boolean putAll(Multimap<? extends K, ? extends V> multimap) {
465    throw new UnsupportedOperationException();
466  }
467
468  /**
469   * Guaranteed to throw an exception and leave the multimap unmodified.
470   *
471   * @throws UnsupportedOperationException always
472   * @deprecated Unsupported operation.
473   */
474  @CanIgnoreReturnValue
475  @Deprecated
476  @Override
477  @DoNotCall("Always throws UnsupportedOperationException")
478  public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) {
479    throw new UnsupportedOperationException();
480  }
481
482  /**
483   * Returns {@code true} if this immutable multimap's implementation contains references to
484   * user-created objects that aren't accessible via this multimap's methods. This is generally used
485   * to determine whether {@code copyOf} implementations should make an explicit copy to avoid
486   * memory leaks.
487   */
488  boolean isPartialView() {
489    return map.isPartialView();
490  }
491
492  // accessors
493
494  @Override
495  public boolean containsKey(@CheckForNull Object key) {
496    return map.containsKey(key);
497  }
498
499  @Override
500  public boolean containsValue(@CheckForNull Object value) {
501    return value != null && super.containsValue(value);
502  }
503
504  @Override
505  public int size() {
506    return size;
507  }
508
509  // views
510
511  /**
512   * Returns an immutable set of the distinct keys in this multimap, in the same order as they
513   * appear in this multimap.
514   */
515  @Override
516  public ImmutableSet<K> keySet() {
517    return map.keySet();
518  }
519
520  @Override
521  Set<K> createKeySet() {
522    throw new AssertionError("unreachable");
523  }
524
525  /**
526   * Returns an immutable map that associates each key with its corresponding values in the
527   * multimap. Keys and values appear in the same order as in this multimap.
528   */
529  @Override
530  @SuppressWarnings("unchecked") // a widening cast
531  public ImmutableMap<K, Collection<V>> asMap() {
532    return (ImmutableMap) map;
533  }
534
535  @Override
536  Map<K, Collection<V>> createAsMap() {
537    throw new AssertionError("should never be called");
538  }
539
540  /** Returns an immutable collection of all key-value pairs in the multimap. */
541  @Override
542  public ImmutableCollection<Entry<K, V>> entries() {
543    return (ImmutableCollection<Entry<K, V>>) super.entries();
544  }
545
546  @Override
547  ImmutableCollection<Entry<K, V>> createEntries() {
548    return new EntryCollection<>(this);
549  }
550
551  private static class EntryCollection<K, V> extends ImmutableCollection<Entry<K, V>> {
552    @Weak final ImmutableMultimap<K, V> multimap;
553
554    EntryCollection(ImmutableMultimap<K, V> multimap) {
555      this.multimap = multimap;
556    }
557
558    @Override
559    public UnmodifiableIterator<Entry<K, V>> iterator() {
560      return multimap.entryIterator();
561    }
562
563    @Override
564    boolean isPartialView() {
565      return multimap.isPartialView();
566    }
567
568    @Override
569    public int size() {
570      return multimap.size();
571    }
572
573    @Override
574    public boolean contains(@CheckForNull Object object) {
575      if (object instanceof Entry) {
576        Entry<?, ?> entry = (Entry<?, ?>) object;
577        return multimap.containsEntry(entry.getKey(), entry.getValue());
578      }
579      return false;
580    }
581
582    private static final long serialVersionUID = 0;
583  }
584
585  @Override
586  UnmodifiableIterator<Entry<K, V>> entryIterator() {
587    return new UnmodifiableIterator<Entry<K, V>>() {
588      final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>> asMapItr =
589          map.entrySet().iterator();
590      @CheckForNull K currentKey = null;
591      Iterator<V> valueItr = Iterators.emptyIterator();
592
593      @Override
594      public boolean hasNext() {
595        return valueItr.hasNext() || asMapItr.hasNext();
596      }
597
598      @Override
599      public Entry<K, V> next() {
600        if (!valueItr.hasNext()) {
601          Entry<K, ? extends ImmutableCollection<V>> entry = asMapItr.next();
602          currentKey = entry.getKey();
603          valueItr = entry.getValue().iterator();
604        }
605        /*
606         * requireNonNull is safe: The first call to this method always enters the !hasNext() case
607         * and populates currentKey, after which it's never cleared.
608         */
609        return immutableEntry(requireNonNull(currentKey), valueItr.next());
610      }
611    };
612  }
613
614  @Override
615  Spliterator<Entry<K, V>> entrySpliterator() {
616    return CollectSpliterators.flatMap(
617        asMap().entrySet().spliterator(),
618        keyToValueCollectionEntry -> {
619          K key = keyToValueCollectionEntry.getKey();
620          Collection<V> valueCollection = keyToValueCollectionEntry.getValue();
621          return CollectSpliterators.map(
622              valueCollection.spliterator(), (V value) -> Maps.immutableEntry(key, value));
623        },
624        Spliterator.SIZED | (this instanceof SetMultimap ? Spliterator.DISTINCT : 0),
625        size());
626  }
627
628  @Override
629  public void forEach(BiConsumer<? super K, ? super V> action) {
630    checkNotNull(action);
631    asMap()
632        .forEach(
633            (key, valueCollection) -> valueCollection.forEach(value -> action.accept(key, value)));
634  }
635
636  /**
637   * Returns an immutable multiset containing all the keys in this multimap, in the same order and
638   * with the same frequencies as they appear in this multimap; to get only a single occurrence of
639   * each key, use {@link #keySet}.
640   */
641  @Override
642  public ImmutableMultiset<K> keys() {
643    return (ImmutableMultiset<K>) super.keys();
644  }
645
646  @Override
647  ImmutableMultiset<K> createKeys() {
648    return new Keys();
649  }
650
651  @SuppressWarnings("serial") // Uses writeReplace, not default serialization
652  @WeakOuter
653  class Keys extends ImmutableMultiset<K> {
654    @Override
655    public boolean contains(@CheckForNull Object object) {
656      return containsKey(object);
657    }
658
659    @Override
660    public int count(@CheckForNull Object element) {
661      Collection<V> values = map.get(element);
662      return (values == null) ? 0 : values.size();
663    }
664
665    @Override
666    public ImmutableSet<K> elementSet() {
667      return keySet();
668    }
669
670    @Override
671    public int size() {
672      return ImmutableMultimap.this.size();
673    }
674
675    @Override
676    Multiset.Entry<K> getEntry(int index) {
677      Map.Entry<K, ? extends Collection<V>> entry = map.entrySet().asList().get(index);
678      return Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
679    }
680
681    @Override
682    boolean isPartialView() {
683      return true;
684    }
685
686    @GwtIncompatible
687    @Override
688    Object writeReplace() {
689      return new KeysSerializedForm(ImmutableMultimap.this);
690    }
691
692    @GwtIncompatible
693    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
694      throw new InvalidObjectException("Use KeysSerializedForm");
695    }
696  }
697
698  @GwtIncompatible
699  private static final class KeysSerializedForm implements Serializable {
700    final ImmutableMultimap<?, ?> multimap;
701
702    KeysSerializedForm(ImmutableMultimap<?, ?> multimap) {
703      this.multimap = multimap;
704    }
705
706    Object readResolve() {
707      return multimap.keys();
708    }
709  }
710
711  /**
712   * Returns an immutable collection of the values in this multimap. Its iterator traverses the
713   * values for the first key, the values for the second key, and so on.
714   */
715  @Override
716  public ImmutableCollection<V> values() {
717    return (ImmutableCollection<V>) super.values();
718  }
719
720  @Override
721  ImmutableCollection<V> createValues() {
722    return new Values<>(this);
723  }
724
725  @Override
726  UnmodifiableIterator<V> valueIterator() {
727    return new UnmodifiableIterator<V>() {
728      Iterator<? extends ImmutableCollection<V>> valueCollectionItr = map.values().iterator();
729      Iterator<V> valueItr = Iterators.emptyIterator();
730
731      @Override
732      public boolean hasNext() {
733        return valueItr.hasNext() || valueCollectionItr.hasNext();
734      }
735
736      @Override
737      public V next() {
738        if (!valueItr.hasNext()) {
739          valueItr = valueCollectionItr.next().iterator();
740        }
741        return valueItr.next();
742      }
743    };
744  }
745
746  private static final class Values<K, V> extends ImmutableCollection<V> {
747    @Weak private final transient ImmutableMultimap<K, V> multimap;
748
749    Values(ImmutableMultimap<K, V> multimap) {
750      this.multimap = multimap;
751    }
752
753    @Override
754    public boolean contains(@CheckForNull Object object) {
755      return multimap.containsValue(object);
756    }
757
758    @Override
759    public UnmodifiableIterator<V> iterator() {
760      return multimap.valueIterator();
761    }
762
763    @GwtIncompatible // not present in emulated superclass
764    @Override
765    int copyIntoArray(@Nullable Object[] dst, int offset) {
766      for (ImmutableCollection<V> valueCollection : multimap.map.values()) {
767        offset = valueCollection.copyIntoArray(dst, offset);
768      }
769      return offset;
770    }
771
772    @Override
773    public int size() {
774      return multimap.size();
775    }
776
777    @Override
778    boolean isPartialView() {
779      return true;
780    }
781
782    private static final long serialVersionUID = 0;
783  }
784
785  private static final long serialVersionUID = 0;
786}