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