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