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.base.Preconditions.checkState;
021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
022import static com.google.common.collect.CollectPreconditions.checkNonnegative;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.VisibleForTesting;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.errorprone.annotations.DoNotMock;
029import com.google.errorprone.annotations.concurrent.LazyInit;
030import com.google.j2objc.annotations.RetainedWith;
031import com.google.j2objc.annotations.WeakOuter;
032import java.io.Serializable;
033import java.util.AbstractMap;
034import java.util.Arrays;
035import java.util.Collection;
036import java.util.Collections;
037import java.util.Comparator;
038import java.util.EnumMap;
039import java.util.Iterator;
040import java.util.Map;
041import java.util.SortedMap;
042import java.util.Spliterator;
043import java.util.Spliterators;
044import java.util.function.BiFunction;
045import java.util.function.BinaryOperator;
046import java.util.function.Function;
047import java.util.stream.Collector;
048import java.util.stream.Collectors;
049import org.checkerframework.checker.nullness.qual.Nullable;
050
051/**
052 * A {@link Map} whose contents will never change, with many other important properties detailed at
053 * {@link ImmutableCollection}.
054 *
055 * <p>See the Guava User Guide article on <a href=
056 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
057 *
058 * @author Jesse Wilson
059 * @author Kevin Bourrillion
060 * @since 2.0
061 */
062@DoNotMock("Use ImmutableMap.of or another implementation")
063@GwtCompatible(serializable = true, emulated = true)
064@SuppressWarnings("serial") // we're overriding default serialization
065public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
066
067  /**
068   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
069   * and values are the result of applying the provided mapping functions to the input elements.
070   * Entries appear in the result {@code ImmutableMap} in encounter order.
071   *
072   * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}, an {@code
073   * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
074   * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
075   * throws an {@code IllegalStateException}.)
076   *
077   *
078   * @since 21.0
079   */
080  public static <T, K, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
081      Function<? super T, ? extends K> keyFunction,
082      Function<? super T, ? extends V> valueFunction) {
083    return CollectCollectors.toImmutableMap(keyFunction, valueFunction);
084  }
085
086  /**
087   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
088   * and values are the result of applying the provided mapping functions to the input elements.
089   *
090   * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}), the
091   * values are merged using the specified merging function. Entries will appear in the encounter
092   * order of the first occurrence of the key.
093   *
094   *
095   * @since 21.0
096   */
097  public static <T, K, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
098      Function<? super T, ? extends K> keyFunction,
099      Function<? super T, ? extends V> valueFunction,
100      BinaryOperator<V> mergeFunction) {
101    return CollectCollectors.toImmutableMap(keyFunction, valueFunction, mergeFunction);
102  }
103
104  /**
105   * Returns the empty map. This map behaves and performs comparably to {@link
106   * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your
107   * code.
108   */
109  @SuppressWarnings("unchecked")
110  public static <K, V> ImmutableMap<K, V> of() {
111    return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY;
112  }
113
114  /**
115   * Returns an immutable map containing a single entry. This map behaves and performs comparably to
116   * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable
117   * mainly for consistency and maintainability of your code.
118   */
119  public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
120    return ImmutableBiMap.of(k1, v1);
121  }
122
123  /**
124   * Returns an immutable map containing the given entries, in order.
125   *
126   * @throws IllegalArgumentException if duplicate keys are provided
127   */
128  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
129    return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2));
130  }
131
132  /**
133   * Returns an immutable map containing the given entries, in order.
134   *
135   * @throws IllegalArgumentException if duplicate keys are provided
136   */
137  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
138    return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
139  }
140
141  /**
142   * Returns an immutable map containing the given entries, in order.
143   *
144   * @throws IllegalArgumentException if duplicate keys are provided
145   */
146  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
147    return RegularImmutableMap.fromEntries(
148        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
149  }
150
151  /**
152   * Returns an immutable map containing the given entries, in order.
153   *
154   * @throws IllegalArgumentException if duplicate keys are provided
155   */
156  public static <K, V> ImmutableMap<K, V> of(
157      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
158    return RegularImmutableMap.fromEntries(
159        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
160  }
161
162  // looking for of() with > 5 entries? Use the builder instead.
163
164  /**
165   * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry
166   * with those values.
167   *
168   * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link
169   * UnsupportedOperationException}.
170   */
171  static <K, V> Entry<K, V> entryOf(K key, V value) {
172    checkEntryNotNull(key, value);
173    return new AbstractMap.SimpleImmutableEntry<>(key, value);
174  }
175
176  /**
177   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
178   * Builder} constructor.
179   */
180  public static <K, V> Builder<K, V> builder() {
181    return new Builder<>();
182  }
183
184  /**
185   * Returns a new builder, expecting the specified number of entries to be added.
186   *
187   * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link
188   * Builder#build} is called, the builder is likely to perform better than an unsized {@link
189   * #builder()} would have.
190   *
191   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
192   * but not exactly, the number of entries added to the builder.
193   *
194   * @since 23.1
195   */
196  @Beta
197  public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) {
198    checkNonnegative(expectedSize, "expectedSize");
199    return new Builder<>(expectedSize);
200  }
201
202  static void checkNoConflict(
203      boolean safe, String conflictDescription, Entry<?, ?> entry1, Entry<?, ?> entry2) {
204    if (!safe) {
205      throw conflictException(conflictDescription, entry1, entry2);
206    }
207  }
208
209  static IllegalArgumentException conflictException(
210      String conflictDescription, Object entry1, Object entry2) {
211    return new IllegalArgumentException(
212        "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2);
213  }
214
215  /**
216   * A builder for creating immutable map instances, especially {@code public static final} maps
217   * ("constant maps"). Example:
218   *
219   * <pre>{@code
220   * static final ImmutableMap<String, Integer> WORD_TO_INT =
221   *     new ImmutableMap.Builder<String, Integer>()
222   *         .put("one", 1)
223   *         .put("two", 2)
224   *         .put("three", 3)
225   *         .build();
226   * }</pre>
227   *
228   * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more
229   * convenient.
230   *
231   * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they
232   * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the
233   * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the
234   * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect
235   * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to
236   * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to
237   * sort entries by value.
238   *
239   * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build
240   * multiple maps in series. Each map is a superset of the maps created before it.
241   *
242   * @since 2.0
243   */
244  @DoNotMock
245  public static class Builder<K, V> {
246    @Nullable Comparator<? super V> valueComparator;
247    Entry<K, V>[] entries;
248    int size;
249    boolean entriesUsed;
250
251    /**
252     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
253     * ImmutableMap#builder}.
254     */
255    public Builder() {
256      this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
257    }
258
259    @SuppressWarnings("unchecked")
260    Builder(int initialCapacity) {
261      this.entries = new Entry[initialCapacity];
262      this.size = 0;
263      this.entriesUsed = false;
264    }
265
266    private void ensureCapacity(int minCapacity) {
267      if (minCapacity > entries.length) {
268        entries =
269            Arrays.copyOf(
270                entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity));
271        entriesUsed = false;
272      }
273    }
274
275    /**
276     * Associates {@code key} with {@code value} in the built map. Duplicate keys are not allowed,
277     * and will cause {@link #build} to fail.
278     */
279    @CanIgnoreReturnValue
280    public Builder<K, V> put(K key, V value) {
281      ensureCapacity(size + 1);
282      Entry<K, V> entry = entryOf(key, value);
283      // don't inline this: we want to fail atomically if key or value is null
284      entries[size++] = entry;
285      return this;
286    }
287
288    /**
289     * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys are
290     * not allowed, and will cause {@link #build} to fail.
291     *
292     * @since 11.0
293     */
294    @CanIgnoreReturnValue
295    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
296      return put(entry.getKey(), entry.getValue());
297    }
298
299    /**
300     * Associates all of the given map's keys and values in the built map. Duplicate keys are not
301     * allowed, and will cause {@link #build} to fail.
302     *
303     * @throws NullPointerException if any key or value in {@code map} is null
304     */
305    @CanIgnoreReturnValue
306    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
307      return putAll(map.entrySet());
308    }
309
310    /**
311     * Adds all of the given entries to the built map. Duplicate keys are not allowed, and will
312     * cause {@link #build} to fail.
313     *
314     * @throws NullPointerException if any key, value, or entry is null
315     * @since 19.0
316     */
317    @CanIgnoreReturnValue
318    @Beta
319    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
320      if (entries instanceof Collection) {
321        ensureCapacity(size + ((Collection<?>) entries).size());
322      }
323      for (Entry<? extends K, ? extends V> entry : entries) {
324        put(entry);
325      }
326      return this;
327    }
328
329    /**
330     * Configures this {@code Builder} to order entries by value according to the specified
331     * comparator.
332     *
333     * <p>The sort order is stable, that is, if two entries have values that compare as equivalent,
334     * the entry that was inserted first will be first in the built map's iteration order.
335     *
336     * @throws IllegalStateException if this method was already called
337     * @since 19.0
338     */
339    @CanIgnoreReturnValue
340    @Beta
341    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
342      checkState(this.valueComparator == null, "valueComparator was already set");
343      this.valueComparator = checkNotNull(valueComparator, "valueComparator");
344      return this;
345    }
346
347    @CanIgnoreReturnValue
348    Builder<K, V> combine(Builder<K, V> other) {
349      checkNotNull(other);
350      ensureCapacity(this.size + other.size);
351      System.arraycopy(other.entries, 0, this.entries, this.size, other.size);
352      this.size += other.size;
353      return this;
354    }
355
356    /*
357     * TODO(kevinb): Should build() and the ImmutableBiMap & ImmutableSortedMap
358     * versions throw an IllegalStateException instead?
359     */
360
361    /**
362     * Returns a newly-created immutable map. The iteration order of the returned map is the order
363     * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was
364     * called, in which case entries are sorted by value.
365     *
366     * @throws IllegalArgumentException if duplicate keys were added
367     */
368    public ImmutableMap<K, V> build() {
369      /*
370       * If entries is full, or if hash flooding is detected, then this implementation may end up
371       * using the entries array directly and writing over the entry objects with non-terminal
372       * entries, but this is safe; if this Builder is used further, it will grow the entries array
373       * (so it can't affect the original array), and future build() calls will always copy any
374       * entry objects that cannot be safely reused.
375       */
376      if (valueComparator != null) {
377        if (entriesUsed) {
378          entries = Arrays.copyOf(entries, size);
379        }
380        Arrays.sort(
381            entries, 0, size, Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
382      }
383      switch (size) {
384        case 0:
385          return of();
386        case 1:
387          return of(entries[0].getKey(), entries[0].getValue());
388        default:
389          entriesUsed = true;
390          return RegularImmutableMap.fromEntryArray(size, entries);
391      }
392    }
393
394    @VisibleForTesting // only for testing JDK backed implementation
395    ImmutableMap<K, V> buildJdkBacked() {
396      checkState(
397          valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator");
398      switch (size) {
399        case 0:
400          return of();
401        case 1:
402          return of(entries[0].getKey(), entries[0].getValue());
403        default:
404          entriesUsed = true;
405          return JdkBackedImmutableMap.create(size, entries);
406      }
407    }
408  }
409
410  /**
411   * Returns an immutable map containing the same entries as {@code map}. The returned map iterates
412   * over entries in the same order as the {@code entrySet} of the original map. If {@code map}
413   * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
414   * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
415   *
416   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
417   * safe to do so. The exact circumstances under which a copy will or will not be performed are
418   * undocumented and subject to change.
419   *
420   * @throws NullPointerException if any key or value in {@code map} is null
421   */
422  public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
423    if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) {
424      @SuppressWarnings("unchecked") // safe since map is not writable
425      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
426      if (!kvMap.isPartialView()) {
427        return kvMap;
428      }
429    } else if (map instanceof EnumMap) {
430      @SuppressWarnings("unchecked") // safe since map is not writable
431      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) copyOfEnumMap((EnumMap<?, ?>) map);
432      return kvMap;
433    }
434    return copyOf(map.entrySet());
435  }
436
437  /**
438   * Returns an immutable map containing the specified entries. The returned map iterates over
439   * entries in the same order as the original iterable.
440   *
441   * @throws NullPointerException if any key, value, or entry is null
442   * @throws IllegalArgumentException if two entries have the same key
443   * @since 19.0
444   */
445  @Beta
446  public static <K, V> ImmutableMap<K, V> copyOf(
447      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
448    @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
449    Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
450    switch (entryArray.length) {
451      case 0:
452        return of();
453      case 1:
454        Entry<K, V> onlyEntry = entryArray[0];
455        return of(onlyEntry.getKey(), onlyEntry.getValue());
456      default:
457        /*
458         * The current implementation will end up using entryArray directly, though it will write
459         * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
460         */
461        return RegularImmutableMap.fromEntries(entryArray);
462    }
463  }
464
465  private static <K extends Enum<K>, V> ImmutableMap<K, V> copyOfEnumMap(
466      EnumMap<K, ? extends V> original) {
467    EnumMap<K, V> copy = new EnumMap<>(original);
468    for (Entry<?, ?> entry : copy.entrySet()) {
469      checkEntryNotNull(entry.getKey(), entry.getValue());
470    }
471    return ImmutableEnumMap.asImmutable(copy);
472  }
473
474  static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0];
475
476  abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> {
477    abstract UnmodifiableIterator<Entry<K, V>> entryIterator();
478
479    Spliterator<Entry<K, V>> entrySpliterator() {
480      return Spliterators.spliterator(
481          entryIterator(),
482          size(),
483          Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED);
484    }
485
486    @Override
487    ImmutableSet<K> createKeySet() {
488      return new ImmutableMapKeySet<>(this);
489    }
490
491    @Override
492    ImmutableSet<Entry<K, V>> createEntrySet() {
493      class EntrySetImpl extends ImmutableMapEntrySet<K, V> {
494        @Override
495        ImmutableMap<K, V> map() {
496          return IteratorBasedImmutableMap.this;
497        }
498
499        @Override
500        public UnmodifiableIterator<Entry<K, V>> iterator() {
501          return entryIterator();
502        }
503      }
504      return new EntrySetImpl();
505    }
506
507    @Override
508    ImmutableCollection<V> createValues() {
509      return new ImmutableMapValues<>(this);
510    }
511  }
512
513  ImmutableMap() {}
514
515  /**
516   * Guaranteed to throw an exception and leave the map unmodified.
517   *
518   * @throws UnsupportedOperationException always
519   * @deprecated Unsupported operation.
520   */
521  @CanIgnoreReturnValue
522  @Deprecated
523  @Override
524  public final V put(K k, V v) {
525    throw new UnsupportedOperationException();
526  }
527
528  /**
529   * Guaranteed to throw an exception and leave the map unmodified.
530   *
531   * @throws UnsupportedOperationException always
532   * @deprecated Unsupported operation.
533   */
534  @CanIgnoreReturnValue
535  @Deprecated
536  @Override
537  public final V putIfAbsent(K key, V value) {
538    throw new UnsupportedOperationException();
539  }
540
541  /**
542   * Guaranteed to throw an exception and leave the map unmodified.
543   *
544   * @throws UnsupportedOperationException always
545   * @deprecated Unsupported operation.
546   */
547  @Deprecated
548  @Override
549  public final boolean replace(K key, V oldValue, V newValue) {
550    throw new UnsupportedOperationException();
551  }
552
553  /**
554   * Guaranteed to throw an exception and leave the map unmodified.
555   *
556   * @throws UnsupportedOperationException always
557   * @deprecated Unsupported operation.
558   */
559  @Deprecated
560  @Override
561  public final V replace(K key, V value) {
562    throw new UnsupportedOperationException();
563  }
564
565  /**
566   * Guaranteed to throw an exception and leave the map unmodified.
567   *
568   * @throws UnsupportedOperationException always
569   * @deprecated Unsupported operation.
570   */
571  @Deprecated
572  @Override
573  public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
574    throw new UnsupportedOperationException();
575  }
576
577  /**
578   * Guaranteed to throw an exception and leave the map unmodified.
579   *
580   * @throws UnsupportedOperationException always
581   * @deprecated Unsupported operation.
582   */
583  @Deprecated
584  @Override
585  public final V computeIfPresent(
586      K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
587    throw new UnsupportedOperationException();
588  }
589
590  /**
591   * Guaranteed to throw an exception and leave the map unmodified.
592   *
593   * @throws UnsupportedOperationException always
594   * @deprecated Unsupported operation.
595   */
596  @Deprecated
597  @Override
598  public final V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
599    throw new UnsupportedOperationException();
600  }
601
602  /**
603   * Guaranteed to throw an exception and leave the map unmodified.
604   *
605   * @throws UnsupportedOperationException always
606   * @deprecated Unsupported operation.
607   */
608  @Deprecated
609  @Override
610  public final V merge(
611      K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
612    throw new UnsupportedOperationException();
613  }
614
615  /**
616   * Guaranteed to throw an exception and leave the map unmodified.
617   *
618   * @throws UnsupportedOperationException always
619   * @deprecated Unsupported operation.
620   */
621  @Deprecated
622  @Override
623  public final void putAll(Map<? extends K, ? extends V> map) {
624    throw new UnsupportedOperationException();
625  }
626
627  /**
628   * Guaranteed to throw an exception and leave the map unmodified.
629   *
630   * @throws UnsupportedOperationException always
631   * @deprecated Unsupported operation.
632   */
633  @Deprecated
634  @Override
635  public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
636    throw new UnsupportedOperationException();
637  }
638
639  /**
640   * Guaranteed to throw an exception and leave the map unmodified.
641   *
642   * @throws UnsupportedOperationException always
643   * @deprecated Unsupported operation.
644   */
645  @Deprecated
646  @Override
647  public final V remove(Object o) {
648    throw new UnsupportedOperationException();
649  }
650
651  /**
652   * Guaranteed to throw an exception and leave the map unmodified.
653   *
654   * @throws UnsupportedOperationException always
655   * @deprecated Unsupported operation.
656   */
657  @Deprecated
658  @Override
659  public final boolean remove(Object key, Object value) {
660    throw new UnsupportedOperationException();
661  }
662
663  /**
664   * Guaranteed to throw an exception and leave the map unmodified.
665   *
666   * @throws UnsupportedOperationException always
667   * @deprecated Unsupported operation.
668   */
669  @Deprecated
670  @Override
671  public final void clear() {
672    throw new UnsupportedOperationException();
673  }
674
675  @Override
676  public boolean isEmpty() {
677    return size() == 0;
678  }
679
680  @Override
681  public boolean containsKey(@Nullable Object key) {
682    return get(key) != null;
683  }
684
685  @Override
686  public boolean containsValue(@Nullable Object value) {
687    return values().contains(value);
688  }
689
690  // Overriding to mark it Nullable
691  @Override
692  public abstract V get(@Nullable Object key);
693
694  /**
695   * @since 21.0 (but only since 23.5 in the Android <a
696   *     href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>).
697   *     Note, however, that Java 8 users can call this method with any version and flavor of Guava.
698   */
699  @Override
700  public final V getOrDefault(@Nullable Object key, @Nullable V defaultValue) {
701    V result = get(key);
702    return (result != null) ? result : defaultValue;
703  }
704
705  @LazyInit @RetainedWith private transient ImmutableSet<Entry<K, V>> entrySet;
706
707  /**
708   * Returns an immutable set of the mappings in this map. The iteration order is specified by the
709   * method used to create this map. Typically, this is insertion order.
710   */
711  @Override
712  public ImmutableSet<Entry<K, V>> entrySet() {
713    ImmutableSet<Entry<K, V>> result = entrySet;
714    return (result == null) ? entrySet = createEntrySet() : result;
715  }
716
717  abstract ImmutableSet<Entry<K, V>> createEntrySet();
718
719  @LazyInit @RetainedWith private transient ImmutableSet<K> keySet;
720
721  /**
722   * Returns an immutable set of the keys in this map, in the same order that they appear in {@link
723   * #entrySet}.
724   */
725  @Override
726  public ImmutableSet<K> keySet() {
727    ImmutableSet<K> result = keySet;
728    return (result == null) ? keySet = createKeySet() : result;
729  }
730
731  /*
732   * This could have a good default implementation of return new ImmutableKeySet<K, V>(this),
733   * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap
734   * overrides it.
735   */
736  abstract ImmutableSet<K> createKeySet();
737
738  UnmodifiableIterator<K> keyIterator() {
739    final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator();
740    return new UnmodifiableIterator<K>() {
741      @Override
742      public boolean hasNext() {
743        return entryIterator.hasNext();
744      }
745
746      @Override
747      public K next() {
748        return entryIterator.next().getKey();
749      }
750    };
751  }
752
753  Spliterator<K> keySpliterator() {
754    return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey);
755  }
756
757  @LazyInit @RetainedWith private transient ImmutableCollection<V> values;
758
759  /**
760   * Returns an immutable collection of the values in this map, in the same order that they appear
761   * in {@link #entrySet}.
762   */
763  @Override
764  public ImmutableCollection<V> values() {
765    ImmutableCollection<V> result = values;
766    return (result == null) ? values = createValues() : result;
767  }
768
769  /*
770   * This could have a good default implementation of {@code return new
771   * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default
772   * when RegularImmutableMap overrides it.
773   */
774  abstract ImmutableCollection<V> createValues();
775
776  // cached so that this.multimapView().inverse() only computes inverse once
777  @LazyInit private transient ImmutableSetMultimap<K, V> multimapView;
778
779  /**
780   * Returns a multimap view of the map.
781   *
782   * @since 14.0
783   */
784  public ImmutableSetMultimap<K, V> asMultimap() {
785    if (isEmpty()) {
786      return ImmutableSetMultimap.of();
787    }
788    ImmutableSetMultimap<K, V> result = multimapView;
789    return (result == null)
790        ? (multimapView =
791            new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null))
792        : result;
793  }
794
795  @WeakOuter
796  private final class MapViewOfValuesAsSingletonSets
797      extends IteratorBasedImmutableMap<K, ImmutableSet<V>> {
798
799    @Override
800    public int size() {
801      return ImmutableMap.this.size();
802    }
803
804    @Override
805    ImmutableSet<K> createKeySet() {
806      return ImmutableMap.this.keySet();
807    }
808
809    @Override
810    public boolean containsKey(@Nullable Object key) {
811      return ImmutableMap.this.containsKey(key);
812    }
813
814    @Override
815    public ImmutableSet<V> get(@Nullable Object key) {
816      V outerValue = ImmutableMap.this.get(key);
817      return (outerValue == null) ? null : ImmutableSet.of(outerValue);
818    }
819
820    @Override
821    boolean isPartialView() {
822      return ImmutableMap.this.isPartialView();
823    }
824
825    @Override
826    public int hashCode() {
827      // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same
828      return ImmutableMap.this.hashCode();
829    }
830
831    @Override
832    boolean isHashCodeFast() {
833      return ImmutableMap.this.isHashCodeFast();
834    }
835
836    @Override
837    UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() {
838      final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator();
839      return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() {
840        @Override
841        public boolean hasNext() {
842          return backingIterator.hasNext();
843        }
844
845        @Override
846        public Entry<K, ImmutableSet<V>> next() {
847          final Entry<K, V> backingEntry = backingIterator.next();
848          return new AbstractMapEntry<K, ImmutableSet<V>>() {
849            @Override
850            public K getKey() {
851              return backingEntry.getKey();
852            }
853
854            @Override
855            public ImmutableSet<V> getValue() {
856              return ImmutableSet.of(backingEntry.getValue());
857            }
858          };
859        }
860      };
861    }
862  }
863
864  @Override
865  public boolean equals(@Nullable Object object) {
866    return Maps.equalsImpl(this, object);
867  }
868
869  abstract boolean isPartialView();
870
871  @Override
872  public int hashCode() {
873    return Sets.hashCodeImpl(entrySet());
874  }
875
876  boolean isHashCodeFast() {
877    return false;
878  }
879
880  @Override
881  public String toString() {
882    return Maps.toStringImpl(this);
883  }
884
885  /**
886   * Serialized type for all ImmutableMap instances. It captures the logical contents and they are
887   * reconstructed using public factory methods. This ensures that the implementation types remain
888   * as implementation details.
889   */
890  static class SerializedForm<K, V> implements Serializable {
891    // This object retains references to collections returned by keySet() and value(). This saves
892    // bytes when the both the map and its keySet or value collection are written to the same
893    // instance of ObjectOutputStream.
894
895    // TODO(b/160980469): remove support for the old serialization format after some time
896    private static final boolean USE_LEGACY_SERIALIZATION = true;
897
898    private final Object keys;
899    private final Object values;
900
901    SerializedForm(ImmutableMap<K, V> map) {
902      if (USE_LEGACY_SERIALIZATION) {
903        Object[] keys = new Object[map.size()];
904        Object[] values = new Object[map.size()];
905        int i = 0;
906        for (Entry<?, ?> entry : map.entrySet()) {
907          keys[i] = entry.getKey();
908          values[i] = entry.getValue();
909          i++;
910        }
911        this.keys = keys;
912        this.values = values;
913        return;
914      }
915      this.keys = map.keySet();
916      this.values = map.values();
917    }
918
919    @SuppressWarnings("unchecked")
920    final Object readResolve() {
921      if (!(this.keys instanceof ImmutableSet)) {
922        return legacyReadResolve();
923      }
924
925      ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys;
926      ImmutableCollection<V> values = (ImmutableCollection<V>) this.values;
927
928      Builder<K, V> builder = makeBuilder(keySet.size());
929
930      UnmodifiableIterator<K> keyIter = keySet.iterator();
931      UnmodifiableIterator<V> valueIter = values.iterator();
932
933      while (keyIter.hasNext()) {
934        builder.put(keyIter.next(), valueIter.next());
935      }
936
937      return builder.build();
938    }
939
940    @SuppressWarnings("unchecked")
941    final Object legacyReadResolve() {
942      K[] keys = (K[]) this.keys;
943      V[] values = (V[]) this.values;
944
945      Builder<K, V> builder = makeBuilder(keys.length);
946
947      for (int i = 0; i < keys.length; i++) {
948        builder.put(keys[i], values[i]);
949      }
950      return builder.build();
951    }
952
953    /**
954     * Returns a builder that builds the unserialized type. Subclasses should override this method.
955     */
956    Builder<K, V> makeBuilder(int size) {
957      return new Builder<>(size);
958    }
959
960    private static final long serialVersionUID = 0;
961  }
962
963  /**
964   * Returns a serializable form of this object. Non-public subclasses should not override this
965   * method. Publicly-accessible subclasses must override this method and should return a subclass
966   * of SerializedForm whose readResolve() method returns objects of the subclass type.
967   */
968  Object writeReplace() {
969    return new SerializedForm<>(this);
970  }
971}