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.CollectPreconditions.checkNonnegative;
022import static com.google.common.collect.Iterators.emptyIterator;
023import static com.google.common.collect.Maps.immutableEntry;
024import static java.lang.Math.max;
025import static java.util.Arrays.asList;
026import static java.util.Objects.requireNonNull;
027
028import com.google.common.annotations.GwtCompatible;
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.annotations.J2ktIncompatible;
031import com.google.errorprone.annotations.CanIgnoreReturnValue;
032import com.google.errorprone.annotations.DoNotCall;
033import com.google.errorprone.annotations.DoNotMock;
034import com.google.j2objc.annotations.Weak;
035import com.google.j2objc.annotations.WeakOuter;
036import java.io.InvalidObjectException;
037import java.io.ObjectInputStream;
038import java.io.Serializable;
039import java.util.Collection;
040import java.util.Comparator;
041import java.util.Iterator;
042import java.util.Map;
043import java.util.Map.Entry;
044import java.util.Set;
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)
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   * Returns a new builder with a hint for how many distinct keys are expected to be added. The
134   * generated builder is equivalent to that returned by {@link #builder}, but may perform better if
135   * {@code expectedKeys} is a good estimate.
136   *
137   * @throws IllegalArgumentException if {@code expectedKeys} is negative
138   * @since 33.3.0
139   */
140  public static <K, V> Builder<K, V> builderWithExpectedKeys(int expectedKeys) {
141    checkNonnegative(expectedKeys, "expectedKeys");
142    return new Builder<>(expectedKeys);
143  }
144
145  /**
146   * A builder for creating immutable multimap instances, especially {@code public static final}
147   * multimaps ("constant multimaps"). Example:
148   *
149   * <pre>{@code
150   * static final Multimap<String, Integer> STRING_TO_INTEGER_MULTIMAP =
151   *     new ImmutableMultimap.Builder<String, Integer>()
152   *         .put("one", 1)
153   *         .putAll("several", 1, 2, 3)
154   *         .putAll("many", 1, 2, 3, 4, 5)
155   *         .build();
156   * }</pre>
157   *
158   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple times to build
159   * multiple multimaps in series. Each multimap contains the key-value mappings in the previously
160   * created multimaps.
161   *
162   * @since 2.0
163   */
164  @DoNotMock
165  public static class Builder<K, V> {
166    @CheckForNull Map<K, ImmutableCollection.Builder<V>> builderMap;
167    @CheckForNull Comparator<? super K> keyComparator;
168    @CheckForNull Comparator<? super V> valueComparator;
169    int expectedValuesPerKey = ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY;
170
171    /**
172     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
173     * ImmutableMultimap#builder}.
174     */
175    public Builder() {}
176
177    /** Creates a new builder with a hint for the number of distinct keys. */
178    Builder(int expectedKeys) {
179      if (expectedKeys > 0) {
180        builderMap = Platform.preservesInsertionOrderOnPutsMapWithExpectedSize(expectedKeys);
181      }
182      // otherwise, leave it null to be constructed lazily
183    }
184
185    Map<K, ImmutableCollection.Builder<V>> ensureBuilderMapNonNull() {
186      Map<K, ImmutableCollection.Builder<V>> result = builderMap;
187      if (result == null) {
188        result = Platform.preservesInsertionOrderOnPutsMap();
189        builderMap = result;
190      }
191      return result;
192    }
193
194    ImmutableCollection.Builder<V> newValueCollectionBuilderWithExpectedSize(int expectedSize) {
195      return ImmutableList.builderWithExpectedSize(expectedSize);
196    }
197
198    /**
199     * Provides a hint for how many values will be associated with each key newly added to the
200     * builder after this call. This does not change semantics, but may improve performance if
201     * {@code expectedValuesPerKey} is a good estimate.
202     *
203     * <p>This may be called more than once; each newly added key will use the most recent call to
204     * {@link #expectedValuesPerKey} as its hint.
205     *
206     * @throws IllegalArgumentException if {@code expectedValuesPerKey} is negative
207     * @since 33.3.0
208     */
209    @CanIgnoreReturnValue
210    public Builder<K, V> expectedValuesPerKey(int expectedValuesPerKey) {
211      checkNonnegative(expectedValuesPerKey, "expectedValuesPerKey");
212
213      // Always presize to at least 1, since we only bother creating a value collection if there's
214      // at least one element.
215      this.expectedValuesPerKey = max(expectedValuesPerKey, 1);
216
217      return this;
218    }
219
220    /**
221     * By default, if we are handed a value collection bigger than expectedValuesPerKey, presize to
222     * accept that many elements.
223     *
224     * <p>This gets overridden in ImmutableSetMultimap.Builder to only trust the size of {@code
225     * values} if it is a Set and therefore probably already deduplicated.
226     */
227    int expectedValueCollectionSize(int defaultExpectedValues, Iterable<?> values) {
228      if (values instanceof Collection<?>) {
229        Collection<?> collection = (Collection<?>) values;
230        return max(defaultExpectedValues, collection.size());
231      } else {
232        return defaultExpectedValues;
233      }
234    }
235
236    /** Adds a key-value mapping to the built multimap. */
237    @CanIgnoreReturnValue
238    public Builder<K, V> put(K key, V value) {
239      checkEntryNotNull(key, value);
240      ImmutableCollection.Builder<V> valuesBuilder = ensureBuilderMapNonNull().get(key);
241      if (valuesBuilder == null) {
242        valuesBuilder = newValueCollectionBuilderWithExpectedSize(expectedValuesPerKey);
243        ensureBuilderMapNonNull().put(key, valuesBuilder);
244      }
245      valuesBuilder.add(value);
246      return this;
247    }
248
249    /**
250     * Adds an entry to the built multimap.
251     *
252     * @since 11.0
253     */
254    @CanIgnoreReturnValue
255    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
256      return put(entry.getKey(), entry.getValue());
257    }
258
259    /**
260     * Adds entries to the built multimap.
261     *
262     * @since 19.0
263     */
264    @CanIgnoreReturnValue
265    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
266      for (Entry<? extends K, ? extends V> entry : entries) {
267        put(entry);
268      }
269      return this;
270    }
271
272    /**
273     * Stores a collection of values with the same key in the built multimap.
274     *
275     * @throws NullPointerException if {@code key}, {@code values}, or any element in {@code values}
276     *     is null. The builder is left in an invalid state.
277     */
278    @CanIgnoreReturnValue
279    public Builder<K, V> putAll(K key, Iterable<? extends V> values) {
280      if (key == null) {
281        throw new NullPointerException("null key in entry: null=" + Iterables.toString(values));
282      }
283      Iterator<? extends V> valuesItr = values.iterator();
284      if (!valuesItr.hasNext()) {
285        return this;
286      }
287      ImmutableCollection.Builder<V> valuesBuilder = ensureBuilderMapNonNull().get(key);
288      if (valuesBuilder == null) {
289        valuesBuilder =
290            newValueCollectionBuilderWithExpectedSize(
291                expectedValueCollectionSize(expectedValuesPerKey, values));
292        ensureBuilderMapNonNull().put(key, valuesBuilder);
293      }
294      while (valuesItr.hasNext()) {
295        V value = valuesItr.next();
296        checkEntryNotNull(key, value);
297        valuesBuilder.add(value);
298      }
299      return this;
300    }
301
302    /**
303     * Stores an array of values with the same key in the built multimap.
304     *
305     * @throws NullPointerException if the key or any value is null. The builder is left in an
306     *     invalid state.
307     */
308    @CanIgnoreReturnValue
309    public Builder<K, V> putAll(K key, V... values) {
310      return putAll(key, asList(values));
311    }
312
313    /**
314     * Stores another multimap's entries in the built multimap. The generated multimap's key and
315     * value orderings correspond to the iteration ordering of the {@code multimap.asMap()} view,
316     * with new keys and values following any existing keys and values.
317     *
318     * @throws NullPointerException if any key or value in {@code multimap} is null. The builder is
319     *     left in an invalid state.
320     */
321    @CanIgnoreReturnValue
322    public Builder<K, V> putAll(Multimap<? extends K, ? extends V> multimap) {
323      for (Entry<? extends K, ? extends Collection<? extends V>> entry :
324          multimap.asMap().entrySet()) {
325        putAll(entry.getKey(), entry.getValue());
326      }
327      return this;
328    }
329
330    /**
331     * Specifies the ordering of the generated multimap's keys.
332     *
333     * @since 8.0
334     */
335    @CanIgnoreReturnValue
336    public Builder<K, V> orderKeysBy(Comparator<? super K> keyComparator) {
337      this.keyComparator = checkNotNull(keyComparator);
338      return this;
339    }
340
341    /**
342     * Specifies the ordering of the generated multimap's values for each key.
343     *
344     * @since 8.0
345     */
346    @CanIgnoreReturnValue
347    public Builder<K, V> orderValuesBy(Comparator<? super V> valueComparator) {
348      this.valueComparator = checkNotNull(valueComparator);
349      return this;
350    }
351
352    @CanIgnoreReturnValue
353    Builder<K, V> combine(Builder<K, V> other) {
354      if (other.builderMap != null) {
355        for (Map.Entry<K, ImmutableCollection.Builder<V>> entry : other.builderMap.entrySet()) {
356          putAll(entry.getKey(), entry.getValue().build());
357        }
358      }
359      return this;
360    }
361
362    /** Returns a newly-created immutable multimap. */
363    public ImmutableMultimap<K, V> build() {
364      if (builderMap == null) {
365        return ImmutableListMultimap.of();
366      }
367      Collection<Map.Entry<K, ImmutableCollection.Builder<V>>> mapEntries = builderMap.entrySet();
368      if (keyComparator != null) {
369        mapEntries = Ordering.from(keyComparator).<K>onKeys().immutableSortedCopy(mapEntries);
370      }
371      return ImmutableListMultimap.fromMapBuilderEntries(mapEntries, valueComparator);
372    }
373  }
374
375  /**
376   * Returns an immutable multimap containing the same mappings as {@code multimap}, in the
377   * "key-grouped" iteration order described in the class documentation.
378   *
379   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
380   * safe to do so. The exact circumstances under which a copy will or will not be performed are
381   * undocumented and subject to change.
382   *
383   * @throws NullPointerException if any key or value in {@code multimap} is null
384   */
385  public static <K, V> ImmutableMultimap<K, V> copyOf(Multimap<? extends K, ? extends V> multimap) {
386    if (multimap instanceof ImmutableMultimap) {
387      @SuppressWarnings("unchecked") // safe since multimap is not writable
388      ImmutableMultimap<K, V> kvMultimap = (ImmutableMultimap<K, V>) multimap;
389      if (!kvMultimap.isPartialView()) {
390        return kvMultimap;
391      }
392    }
393    return ImmutableListMultimap.copyOf(multimap);
394  }
395
396  /**
397   * Returns an immutable multimap containing the specified entries. The returned multimap iterates
398   * over keys in the order they were first encountered in the input, and the values for each key
399   * are iterated in the order they were encountered.
400   *
401   * @throws NullPointerException if any key, value, or entry is null
402   * @since 19.0
403   */
404  public static <K, V> ImmutableMultimap<K, V> copyOf(
405      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
406    return ImmutableListMultimap.copyOf(entries);
407  }
408
409  final transient ImmutableMap<K, ? extends ImmutableCollection<V>> map;
410  final transient int size;
411
412  // These constants allow the deserialization code to set final fields. This
413  // holder class makes sure they are not initialized unless an instance is
414  // deserialized.
415  @GwtIncompatible // java serialization is not supported
416  @J2ktIncompatible
417  static class FieldSettersHolder {
418    static final Serialization.FieldSetter<? super ImmutableMultimap<?, ?>> MAP_FIELD_SETTER =
419        Serialization.getFieldSetter(ImmutableMultimap.class, "map");
420    static final Serialization.FieldSetter<? super ImmutableMultimap<?, ?>> SIZE_FIELD_SETTER =
421        Serialization.getFieldSetter(ImmutableMultimap.class, "size");
422  }
423
424  ImmutableMultimap(ImmutableMap<K, ? extends ImmutableCollection<V>> map, int size) {
425    this.map = map;
426    this.size = size;
427  }
428
429  // mutators (not supported)
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  // DoNotCall wants this to be final, but we want to override it to return more specific types.
442  // Inheritance is closed, and all subtypes are @DoNotCall, so this is safe to suppress.
443  @SuppressWarnings("DoNotCall")
444  public ImmutableCollection<V> removeAll(@CheckForNull Object key) {
445    throw new UnsupportedOperationException();
446  }
447
448  /**
449   * Guaranteed to throw an exception and leave the multimap unmodified.
450   *
451   * @throws UnsupportedOperationException always
452   * @deprecated Unsupported operation.
453   */
454  @CanIgnoreReturnValue
455  @Deprecated
456  @Override
457  @DoNotCall("Always throws UnsupportedOperationException")
458  // DoNotCall wants this to be final, but we want to override it to return more specific types.
459  // Inheritance is closed, and all subtypes are @DoNotCall, so this is safe to suppress.
460  @SuppressWarnings("DoNotCall")
461  public ImmutableCollection<V> replaceValues(K key, Iterable<? extends V> values) {
462    throw new UnsupportedOperationException();
463  }
464
465  /**
466   * Guaranteed to throw an exception and leave the multimap unmodified.
467   *
468   * @throws UnsupportedOperationException always
469   * @deprecated Unsupported operation.
470   */
471  @Deprecated
472  @Override
473  @DoNotCall("Always throws UnsupportedOperationException")
474  public final void clear() {
475    throw new UnsupportedOperationException();
476  }
477
478  /**
479   * Returns an immutable collection of the values for the given key. If no mappings in the multimap
480   * have the provided key, an empty immutable collection is returned. The values are in the same
481   * order as the parameters used to build this multimap.
482   */
483  @Override
484  public abstract ImmutableCollection<V> get(K key);
485
486  /**
487   * Returns an immutable multimap which is the inverse of this one. For every key-value mapping in
488   * the original, the result will have a mapping with key and value reversed.
489   *
490   * @since 11.0
491   */
492  public abstract ImmutableMultimap<V, K> inverse();
493
494  /**
495   * Guaranteed to throw an exception and leave the multimap unmodified.
496   *
497   * @throws UnsupportedOperationException always
498   * @deprecated Unsupported operation.
499   */
500  @CanIgnoreReturnValue
501  @Deprecated
502  @Override
503  @DoNotCall("Always throws UnsupportedOperationException")
504  public final boolean put(K key, V value) {
505    throw new UnsupportedOperationException();
506  }
507
508  /**
509   * Guaranteed to throw an exception and leave the multimap unmodified.
510   *
511   * @throws UnsupportedOperationException always
512   * @deprecated Unsupported operation.
513   */
514  @CanIgnoreReturnValue
515  @Deprecated
516  @Override
517  @DoNotCall("Always throws UnsupportedOperationException")
518  public final boolean putAll(K key, Iterable<? extends V> values) {
519    throw new UnsupportedOperationException();
520  }
521
522  /**
523   * Guaranteed to throw an exception and leave the multimap unmodified.
524   *
525   * @throws UnsupportedOperationException always
526   * @deprecated Unsupported operation.
527   */
528  @CanIgnoreReturnValue
529  @Deprecated
530  @Override
531  @DoNotCall("Always throws UnsupportedOperationException")
532  public final boolean putAll(Multimap<? extends K, ? extends V> multimap) {
533    throw new UnsupportedOperationException();
534  }
535
536  /**
537   * Guaranteed to throw an exception and leave the multimap unmodified.
538   *
539   * @throws UnsupportedOperationException always
540   * @deprecated Unsupported operation.
541   */
542  @CanIgnoreReturnValue
543  @Deprecated
544  @Override
545  @DoNotCall("Always throws UnsupportedOperationException")
546  public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) {
547    throw new UnsupportedOperationException();
548  }
549
550  /**
551   * Returns {@code true} if this immutable multimap's implementation contains references to
552   * user-created objects that aren't accessible via this multimap's methods. This is generally used
553   * to determine whether {@code copyOf} implementations should make an explicit copy to avoid
554   * memory leaks.
555   */
556  boolean isPartialView() {
557    return map.isPartialView();
558  }
559
560  // accessors
561
562  @Override
563  public boolean containsKey(@CheckForNull Object key) {
564    return map.containsKey(key);
565  }
566
567  @Override
568  public boolean containsValue(@CheckForNull Object value) {
569    return value != null && super.containsValue(value);
570  }
571
572  @Override
573  public int size() {
574    return size;
575  }
576
577  // views
578
579  /**
580   * Returns an immutable set of the distinct keys in this multimap, in the same order as they
581   * appear in this multimap.
582   */
583  @Override
584  public ImmutableSet<K> keySet() {
585    return map.keySet();
586  }
587
588  @Override
589  Set<K> createKeySet() {
590    throw new AssertionError("unreachable");
591  }
592
593  /**
594   * Returns an immutable map that associates each key with its corresponding values in the
595   * multimap. Keys and values appear in the same order as in this multimap.
596   */
597  @Override
598  @SuppressWarnings("unchecked") // a widening cast
599  public ImmutableMap<K, Collection<V>> asMap() {
600    return (ImmutableMap) map;
601  }
602
603  @Override
604  Map<K, Collection<V>> createAsMap() {
605    throw new AssertionError("should never be called");
606  }
607
608  /** Returns an immutable collection of all key-value pairs in the multimap. */
609  @Override
610  public ImmutableCollection<Entry<K, V>> entries() {
611    return (ImmutableCollection<Entry<K, V>>) super.entries();
612  }
613
614  @Override
615  ImmutableCollection<Entry<K, V>> createEntries() {
616    return new EntryCollection<>(this);
617  }
618
619  private static class EntryCollection<K, V> extends ImmutableCollection<Entry<K, V>> {
620    @Weak final ImmutableMultimap<K, V> multimap;
621
622    EntryCollection(ImmutableMultimap<K, V> multimap) {
623      this.multimap = multimap;
624    }
625
626    @Override
627    public UnmodifiableIterator<Entry<K, V>> iterator() {
628      return multimap.entryIterator();
629    }
630
631    @Override
632    boolean isPartialView() {
633      return multimap.isPartialView();
634    }
635
636    @Override
637    public int size() {
638      return multimap.size();
639    }
640
641    @Override
642    public boolean contains(@CheckForNull Object object) {
643      if (object instanceof Entry) {
644        Entry<?, ?> entry = (Entry<?, ?>) object;
645        return multimap.containsEntry(entry.getKey(), entry.getValue());
646      }
647      return false;
648    }
649
650    // redeclare to help optimizers with b/310253115
651    @SuppressWarnings("RedundantOverride")
652    @Override
653    @J2ktIncompatible // serialization
654    @GwtIncompatible // serialization
655    Object writeReplace() {
656      return super.writeReplace();
657    }
658
659    private static final long serialVersionUID = 0;
660  }
661
662  @Override
663  UnmodifiableIterator<Entry<K, V>> entryIterator() {
664    return new UnmodifiableIterator<Entry<K, V>>() {
665      final Iterator<? extends Entry<K, ? extends ImmutableCollection<V>>> asMapItr =
666          map.entrySet().iterator();
667      @CheckForNull K currentKey = null;
668      Iterator<V> valueItr = emptyIterator();
669
670      @Override
671      public boolean hasNext() {
672        return valueItr.hasNext() || asMapItr.hasNext();
673      }
674
675      @Override
676      public Entry<K, V> next() {
677        if (!valueItr.hasNext()) {
678          Entry<K, ? extends ImmutableCollection<V>> entry = asMapItr.next();
679          currentKey = entry.getKey();
680          valueItr = entry.getValue().iterator();
681        }
682        /*
683         * requireNonNull is safe: The first call to this method always enters the !hasNext() case
684         * and populates currentKey, after which it's never cleared.
685         */
686        return immutableEntry(requireNonNull(currentKey), valueItr.next());
687      }
688    };
689  }
690
691  /**
692   * Returns an immutable multiset containing all the keys in this multimap, in the same order and
693   * with the same frequencies as they appear in this multimap; to get only a single occurrence of
694   * each key, use {@link #keySet}.
695   */
696  @Override
697  public ImmutableMultiset<K> keys() {
698    return (ImmutableMultiset<K>) super.keys();
699  }
700
701  @Override
702  ImmutableMultiset<K> createKeys() {
703    return new Keys();
704  }
705
706  @SuppressWarnings("serial") // Uses writeReplace, not default serialization
707  @WeakOuter
708  class Keys extends ImmutableMultiset<K> {
709    @Override
710    public boolean contains(@CheckForNull Object object) {
711      return containsKey(object);
712    }
713
714    @Override
715    public int count(@CheckForNull Object element) {
716      Collection<V> values = map.get(element);
717      return (values == null) ? 0 : values.size();
718    }
719
720    @Override
721    public ImmutableSet<K> elementSet() {
722      return keySet();
723    }
724
725    @Override
726    public int size() {
727      return ImmutableMultimap.this.size();
728    }
729
730    @Override
731    Multiset.Entry<K> getEntry(int index) {
732      Map.Entry<K, ? extends Collection<V>> entry = map.entrySet().asList().get(index);
733      return Multisets.immutableEntry(entry.getKey(), entry.getValue().size());
734    }
735
736    @Override
737    boolean isPartialView() {
738      return true;
739    }
740
741    @GwtIncompatible
742    @J2ktIncompatible
743    @Override
744    Object writeReplace() {
745      return new KeysSerializedForm(ImmutableMultimap.this);
746    }
747
748    @GwtIncompatible
749    @J2ktIncompatible
750    private void readObject(ObjectInputStream stream) throws InvalidObjectException {
751      throw new InvalidObjectException("Use KeysSerializedForm");
752    }
753  }
754
755  @GwtIncompatible
756  @J2ktIncompatible
757  private static final class KeysSerializedForm implements Serializable {
758    final ImmutableMultimap<?, ?> multimap;
759
760    KeysSerializedForm(ImmutableMultimap<?, ?> multimap) {
761      this.multimap = multimap;
762    }
763
764    Object readResolve() {
765      return multimap.keys();
766    }
767  }
768
769  /**
770   * Returns an immutable collection of the values in this multimap. Its iterator traverses the
771   * values for the first key, the values for the second key, and so on.
772   */
773  @Override
774  public ImmutableCollection<V> values() {
775    return (ImmutableCollection<V>) super.values();
776  }
777
778  @Override
779  ImmutableCollection<V> createValues() {
780    return new Values<>(this);
781  }
782
783  @Override
784  UnmodifiableIterator<V> valueIterator() {
785    return new UnmodifiableIterator<V>() {
786      Iterator<? extends ImmutableCollection<V>> valueCollectionItr = map.values().iterator();
787      Iterator<V> valueItr = emptyIterator();
788
789      @Override
790      public boolean hasNext() {
791        return valueItr.hasNext() || valueCollectionItr.hasNext();
792      }
793
794      @Override
795      public V next() {
796        if (!valueItr.hasNext()) {
797          valueItr = valueCollectionItr.next().iterator();
798        }
799        return valueItr.next();
800      }
801    };
802  }
803
804  private static final class Values<K, V> extends ImmutableCollection<V> {
805    @Weak private final transient ImmutableMultimap<K, V> multimap;
806
807    Values(ImmutableMultimap<K, V> multimap) {
808      this.multimap = multimap;
809    }
810
811    @Override
812    public boolean contains(@CheckForNull Object object) {
813      return multimap.containsValue(object);
814    }
815
816    @Override
817    public UnmodifiableIterator<V> iterator() {
818      return multimap.valueIterator();
819    }
820
821    @GwtIncompatible // not present in emulated superclass
822    @Override
823    int copyIntoArray(@Nullable Object[] dst, int offset) {
824      for (ImmutableCollection<V> valueCollection : multimap.map.values()) {
825        offset = valueCollection.copyIntoArray(dst, offset);
826      }
827      return offset;
828    }
829
830    @Override
831    public int size() {
832      return multimap.size();
833    }
834
835    @Override
836    boolean isPartialView() {
837      return true;
838    }
839
840    // redeclare to help optimizers with b/310253115
841    @SuppressWarnings("RedundantOverride")
842    @Override
843    @J2ktIncompatible // serialization
844    @GwtIncompatible // serialization
845    Object writeReplace() {
846      return super.writeReplace();
847    }
848
849    @J2ktIncompatible // serialization
850    private static final long serialVersionUID = 0;
851  }
852
853  @J2ktIncompatible // serialization
854  private static final long serialVersionUID = 0;
855}