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;
023import static java.util.Objects.requireNonNull;
024
025import com.google.common.annotations.Beta;
026import com.google.common.annotations.GwtCompatible;
027import com.google.common.annotations.VisibleForTesting;
028import com.google.errorprone.annotations.CanIgnoreReturnValue;
029import com.google.errorprone.annotations.DoNotCall;
030import com.google.errorprone.annotations.DoNotMock;
031import com.google.errorprone.annotations.concurrent.LazyInit;
032import com.google.j2objc.annotations.RetainedWith;
033import com.google.j2objc.annotations.WeakOuter;
034import java.io.InvalidObjectException;
035import java.io.ObjectInputStream;
036import java.io.Serializable;
037import java.util.Arrays;
038import java.util.BitSet;
039import java.util.Collection;
040import java.util.Collections;
041import java.util.Comparator;
042import java.util.EnumMap;
043import java.util.HashSet;
044import java.util.Iterator;
045import java.util.Map;
046import java.util.Set;
047import java.util.SortedMap;
048import java.util.Spliterator;
049import java.util.Spliterators;
050import java.util.function.BiFunction;
051import java.util.function.BinaryOperator;
052import java.util.function.Function;
053import java.util.stream.Collector;
054import java.util.stream.Collectors;
055import javax.annotation.CheckForNull;
056import org.checkerframework.checker.nullness.qual.Nullable;
057
058/**
059 * A {@link Map} whose contents will never change, with many other important properties detailed at
060 * {@link ImmutableCollection}.
061 *
062 * <p>See the Guava User Guide article on <a href=
063 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
064 *
065 * @author Jesse Wilson
066 * @author Kevin Bourrillion
067 * @since 2.0
068 */
069@DoNotMock("Use ImmutableMap.of or another implementation")
070@GwtCompatible(serializable = true, emulated = true)
071@SuppressWarnings("serial") // we're overriding default serialization
072@ElementTypesAreNonnullByDefault
073public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
074
075  /**
076   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
077   * and values are the result of applying the provided mapping functions to the input elements.
078   * Entries appear in the result {@code ImmutableMap} in encounter order.
079   *
080   * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}, an {@code
081   * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
082   * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
083   * throws an {@code IllegalStateException}.)
084   *
085   * @since 21.0
086   */
087  public static <T extends @Nullable Object, K, V>
088      Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
089          Function<? super T, ? extends K> keyFunction,
090          Function<? super T, ? extends V> valueFunction) {
091    return CollectCollectors.toImmutableMap(keyFunction, valueFunction);
092  }
093
094  /**
095   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
096   * and values are the result of applying the provided mapping functions to the input elements.
097   *
098   * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}), the
099   * values are merged using the specified merging function. Entries will appear in the encounter
100   * order of the first occurrence of the key.
101   *
102   * @since 21.0
103   */
104  public static <T extends @Nullable Object, K, V>
105      Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
106          Function<? super T, ? extends K> keyFunction,
107          Function<? super T, ? extends V> valueFunction,
108          BinaryOperator<V> mergeFunction) {
109    return CollectCollectors.toImmutableMap(keyFunction, valueFunction, mergeFunction);
110  }
111
112  /**
113   * Returns the empty map. This map behaves and performs comparably to {@link
114   * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your
115   * code.
116   *
117   * <p><b>Performance note:</b> the instance returned is a singleton.
118   */
119  @SuppressWarnings("unchecked")
120  public static <K, V> ImmutableMap<K, V> of() {
121    return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY;
122  }
123
124  /**
125   * Returns an immutable map containing a single entry. This map behaves and performs comparably to
126   * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable
127   * mainly for consistency and maintainability of your code.
128   */
129  public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
130    return ImmutableBiMap.of(k1, v1);
131  }
132
133  /**
134   * Returns an immutable map containing the given entries, in order.
135   *
136   * @throws IllegalArgumentException if duplicate keys are provided
137   */
138  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
139    return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2));
140  }
141
142  /**
143   * Returns an immutable map containing the given entries, in order.
144   *
145   * @throws IllegalArgumentException if duplicate keys are provided
146   */
147  public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
148    return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
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(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
157    return RegularImmutableMap.fromEntries(
158        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
159  }
160
161  /**
162   * Returns an immutable map containing the given entries, in order.
163   *
164   * @throws IllegalArgumentException if duplicate keys are provided
165   */
166  public static <K, V> ImmutableMap<K, V> of(
167      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
168    return RegularImmutableMap.fromEntries(
169        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
170  }
171
172  /**
173   * Returns an immutable map containing the given entries, in order.
174   *
175   * @throws IllegalArgumentException if duplicate keys are provided
176   * @since 31.0
177   */
178  public static <K, V> ImmutableMap<K, V> of(
179      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) {
180    return RegularImmutableMap.fromEntries(
181        entryOf(k1, v1),
182        entryOf(k2, v2),
183        entryOf(k3, v3),
184        entryOf(k4, v4),
185        entryOf(k5, v5),
186        entryOf(k6, v6));
187  }
188
189  /**
190   * Returns an immutable map containing the given entries, in order.
191   *
192   * @throws IllegalArgumentException if duplicate keys are provided
193   * @since 31.0
194   */
195  public static <K, V> ImmutableMap<K, V> of(
196      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7) {
197    return RegularImmutableMap.fromEntries(
198        entryOf(k1, v1),
199        entryOf(k2, v2),
200        entryOf(k3, v3),
201        entryOf(k4, v4),
202        entryOf(k5, v5),
203        entryOf(k6, v6),
204        entryOf(k7, v7));
205  }
206
207  /**
208   * Returns an immutable map containing the given entries, in order.
209   *
210   * @throws IllegalArgumentException if duplicate keys are provided
211   * @since 31.0
212   */
213  public static <K, V> ImmutableMap<K, V> of(
214      K k1,
215      V v1,
216      K k2,
217      V v2,
218      K k3,
219      V v3,
220      K k4,
221      V v4,
222      K k5,
223      V v5,
224      K k6,
225      V v6,
226      K k7,
227      V v7,
228      K k8,
229      V v8) {
230    return RegularImmutableMap.fromEntries(
231        entryOf(k1, v1),
232        entryOf(k2, v2),
233        entryOf(k3, v3),
234        entryOf(k4, v4),
235        entryOf(k5, v5),
236        entryOf(k6, v6),
237        entryOf(k7, v7),
238        entryOf(k8, v8));
239  }
240
241  /**
242   * Returns an immutable map containing the given entries, in order.
243   *
244   * @throws IllegalArgumentException if duplicate keys are provided
245   * @since 31.0
246   */
247  public static <K, V> ImmutableMap<K, V> of(
248      K k1,
249      V v1,
250      K k2,
251      V v2,
252      K k3,
253      V v3,
254      K k4,
255      V v4,
256      K k5,
257      V v5,
258      K k6,
259      V v6,
260      K k7,
261      V v7,
262      K k8,
263      V v8,
264      K k9,
265      V v9) {
266    return RegularImmutableMap.fromEntries(
267        entryOf(k1, v1),
268        entryOf(k2, v2),
269        entryOf(k3, v3),
270        entryOf(k4, v4),
271        entryOf(k5, v5),
272        entryOf(k6, v6),
273        entryOf(k7, v7),
274        entryOf(k8, v8),
275        entryOf(k9, v9));
276  }
277
278  /**
279   * Returns an immutable map containing the given entries, in order.
280   *
281   * @throws IllegalArgumentException if duplicate keys are provided
282   * @since 31.0
283   */
284  public static <K, V> ImmutableMap<K, V> of(
285      K k1,
286      V v1,
287      K k2,
288      V v2,
289      K k3,
290      V v3,
291      K k4,
292      V v4,
293      K k5,
294      V v5,
295      K k6,
296      V v6,
297      K k7,
298      V v7,
299      K k8,
300      V v8,
301      K k9,
302      V v9,
303      K k10,
304      V v10) {
305    return RegularImmutableMap.fromEntries(
306        entryOf(k1, v1),
307        entryOf(k2, v2),
308        entryOf(k3, v3),
309        entryOf(k4, v4),
310        entryOf(k5, v5),
311        entryOf(k6, v6),
312        entryOf(k7, v7),
313        entryOf(k8, v8),
314        entryOf(k9, v9),
315        entryOf(k10, v10));
316  }
317
318  // looking for of() with > 10 entries? Use the builder or ofEntries instead.
319
320  /**
321   * Returns an immutable map containing the given entries, in order.
322   *
323   * @throws IllegalArgumentException if duplicate keys are provided
324   * @since 31.0
325   */
326  @SafeVarargs
327  public static <K, V> ImmutableMap<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) {
328    @SuppressWarnings("unchecked") // we will only ever read these
329    Entry<K, V>[] entries2 = (Entry<K, V>[]) entries;
330    return RegularImmutableMap.fromEntries(entries2);
331  }
332
333  /**
334   * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry
335   * with those values.
336   *
337   * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link
338   * UnsupportedOperationException}.
339   */
340  static <K, V> Entry<K, V> entryOf(K key, V value) {
341    return new ImmutableMapEntry<>(key, value);
342  }
343
344  /**
345   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
346   * Builder} constructor.
347   */
348  public static <K, V> Builder<K, V> builder() {
349    return new Builder<>();
350  }
351
352  /**
353   * Returns a new builder, expecting the specified number of entries to be added.
354   *
355   * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link
356   * Builder#build} is called, the builder is likely to perform better than an unsized {@link
357   * #builder()} would have.
358   *
359   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
360   * but not exactly, the number of entries added to the builder.
361   *
362   * @since 23.1
363   */
364  @Beta
365  public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) {
366    checkNonnegative(expectedSize, "expectedSize");
367    return new Builder<>(expectedSize);
368  }
369
370  static void checkNoConflict(
371      boolean safe, String conflictDescription, Object entry1, Object entry2) {
372    if (!safe) {
373      throw conflictException(conflictDescription, entry1, entry2);
374    }
375  }
376
377  static IllegalArgumentException conflictException(
378      String conflictDescription, Object entry1, Object entry2) {
379    return new IllegalArgumentException(
380        "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2);
381  }
382
383  /**
384   * A builder for creating immutable map instances, especially {@code public static final} maps
385   * ("constant maps"). Example:
386   *
387   * <pre>{@code
388   * static final ImmutableMap<String, Integer> WORD_TO_INT =
389   *     new ImmutableMap.Builder<String, Integer>()
390   *         .put("one", 1)
391   *         .put("two", 2)
392   *         .put("three", 3)
393   *         .buildOrThrow();
394   * }</pre>
395   *
396   * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more
397   * convenient.
398   *
399   * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they
400   * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the
401   * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the
402   * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect
403   * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to
404   * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to
405   * sort entries by value.
406   *
407   * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to
408   * build multiple maps in series. Each map is a superset of the maps created before it.
409   *
410   * @since 2.0
411   */
412  @DoNotMock
413  public static class Builder<K, V> {
414    @CheckForNull Comparator<? super V> valueComparator;
415    @Nullable Entry<K, V>[] entries;
416    int size;
417    boolean entriesUsed;
418
419    /**
420     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
421     * ImmutableMap#builder}.
422     */
423    public Builder() {
424      this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
425    }
426
427    @SuppressWarnings({"unchecked", "rawtypes"})
428    Builder(int initialCapacity) {
429      this.entries = new @Nullable Entry[initialCapacity];
430      this.size = 0;
431      this.entriesUsed = false;
432    }
433
434    private void ensureCapacity(int minCapacity) {
435      if (minCapacity > entries.length) {
436        entries =
437            Arrays.copyOf(
438                entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity));
439        entriesUsed = false;
440      }
441    }
442
443    /**
444     * Associates {@code key} with {@code value} in the built map. If the same key is put more than
445     * once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last
446     * value put for that key.
447     */
448    @CanIgnoreReturnValue
449    public Builder<K, V> put(K key, V value) {
450      ensureCapacity(size + 1);
451      Entry<K, V> entry = entryOf(key, value);
452      // don't inline this: we want to fail atomically if key or value is null
453      entries[size++] = entry;
454      return this;
455    }
456
457    /**
458     * Adds the given {@code entry} to the map, making it immutable if necessary. If the same key is
459     * put more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will
460     * keep the last value put for that key.
461     *
462     * @since 11.0
463     */
464    @CanIgnoreReturnValue
465    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
466      return put(entry.getKey(), entry.getValue());
467    }
468
469    /**
470     * Associates all of the given map's keys and values in the built map. If the same key is put
471     * more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep
472     * the last value put for that key.
473     *
474     * @throws NullPointerException if any key or value in {@code map} is null
475     */
476    @CanIgnoreReturnValue
477    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
478      return putAll(map.entrySet());
479    }
480
481    /**
482     * Adds all of the given entries to the built map. If the same key is put more than once, {@link
483     * #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last value put for
484     * that key.
485     *
486     * @throws NullPointerException if any key, value, or entry is null
487     * @since 19.0
488     */
489    @CanIgnoreReturnValue
490    @Beta
491    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
492      if (entries instanceof Collection) {
493        ensureCapacity(size + ((Collection<?>) entries).size());
494      }
495      for (Entry<? extends K, ? extends V> entry : entries) {
496        put(entry);
497      }
498      return this;
499    }
500
501    /**
502     * Configures this {@code Builder} to order entries by value according to the specified
503     * comparator.
504     *
505     * <p>The sort order is stable, that is, if two entries have values that compare as equivalent,
506     * the entry that was inserted first will be first in the built map's iteration order.
507     *
508     * @throws IllegalStateException if this method was already called
509     * @since 19.0
510     */
511    @CanIgnoreReturnValue
512    @Beta
513    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
514      checkState(this.valueComparator == null, "valueComparator was already set");
515      this.valueComparator = checkNotNull(valueComparator, "valueComparator");
516      return this;
517    }
518
519    @CanIgnoreReturnValue
520    Builder<K, V> combine(Builder<K, V> other) {
521      checkNotNull(other);
522      ensureCapacity(this.size + other.size);
523      System.arraycopy(other.entries, 0, this.entries, this.size, other.size);
524      this.size += other.size;
525      return this;
526    }
527
528    private ImmutableMap<K, V> build(boolean throwIfDuplicateKeys) {
529      /*
530       * If entries is full, or if hash flooding is detected, then this implementation may end up
531       * using the entries array directly and writing over the entry objects with non-terminal
532       * entries, but this is safe; if this Builder is used further, it will grow the entries array
533       * (so it can't affect the original array), and future build() calls will always copy any
534       * entry objects that cannot be safely reused.
535       */
536      switch (size) {
537        case 0:
538          return of();
539        case 1:
540          // requireNonNull is safe because the first `size` elements have been filled in.
541          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
542          return of(onlyEntry.getKey(), onlyEntry.getValue());
543        default:
544          break;
545      }
546      // localEntries is an alias for the entries field, except if we end up removing duplicates in
547      // a copy of the entries array. Likewise, localSize is the same as size except in that case.
548      // It's possible to keep using this Builder after calling buildKeepingLast(), so we need to
549      // ensure that its state is not corrupted by removing duplicates that should cause a later
550      // buildOrThrow() to fail, or by changing the size.
551      @Nullable Entry<K, V>[] localEntries;
552      int localSize = size;
553      if (valueComparator == null) {
554        localEntries = entries;
555      } else {
556        if (entriesUsed) {
557          entries = Arrays.copyOf(entries, size);
558        }
559        localEntries = entries;
560        if (!throwIfDuplicateKeys) {
561          // We want to retain only the last-put value for any given key, before sorting.
562          // This could be improved, but orderEntriesByValue is rather rarely used anyway.
563          @SuppressWarnings("nullness") // entries 0..size-1 are non-null
564          Entry<K, V>[] nonNullEntries = (Entry<K, V>[]) localEntries;
565          localEntries = lastEntryForEachKey(nonNullEntries, size);
566          localSize = localEntries.length;
567        }
568        Arrays.sort(
569            localEntries,
570            0,
571            localSize,
572            Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
573      }
574      entriesUsed = true;
575      return RegularImmutableMap.fromEntryArray(localSize, localEntries, throwIfDuplicateKeys);
576    }
577
578    /**
579     * Returns a newly-created immutable map. The iteration order of the returned map is the order
580     * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was
581     * called, in which case entries are sorted by value.
582     *
583     * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method
584     * will throw an exception if there are duplicate keys. The {@code build()} method will soon be
585     * deprecated.
586     *
587     * @throws IllegalArgumentException if duplicate keys were added
588     */
589    public ImmutableMap<K, V> build() {
590      return buildOrThrow();
591    }
592
593    /**
594     * Returns a newly-created immutable map, or throws an exception if any key was added more than
595     * once. The iteration order of the returned map is the order in which entries were inserted
596     * into the builder, unless {@link #orderEntriesByValue} was called, in which case entries are
597     * sorted by value.
598     *
599     * @throws IllegalArgumentException if duplicate keys were added
600     * @since 31.0
601     */
602    public ImmutableMap<K, V> buildOrThrow() {
603      return build(true);
604    }
605
606    /**
607     * Returns a newly-created immutable map, using the last value for any key that was added more
608     * than once. The iteration order of the returned map is the order in which entries were
609     * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case
610     * entries are sorted by value. If a key was added more than once, it appears in iteration order
611     * based on the first time it was added, again unless {@link #orderEntriesByValue} was called.
612     *
613     * <p>In the current implementation, all values associated with a given key are stored in the
614     * {@code Builder} object, even though only one of them will be used in the built map. If there
615     * can be many repeated keys, it may be more space-efficient to use a {@link
616     * java.util.LinkedHashMap LinkedHashMap} and {@link ImmutableMap#copyOf(Map)} rather than
617     * {@code ImmutableMap.Builder}.
618     *
619     * @since 31.1
620     */
621    public ImmutableMap<K, V> buildKeepingLast() {
622      return build(false);
623    }
624
625    @VisibleForTesting // only for testing JDK backed implementation
626    ImmutableMap<K, V> buildJdkBacked() {
627      checkState(
628          valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator");
629      switch (size) {
630        case 0:
631          return of();
632        case 1:
633          // requireNonNull is safe because the first `size` elements have been filled in.
634          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
635          return of(onlyEntry.getKey(), onlyEntry.getValue());
636        default:
637          entriesUsed = true;
638          return JdkBackedImmutableMap.create(size, entries, /* throwIfDuplicateKeys= */ true);
639      }
640    }
641
642    private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) {
643      Set<K> seen = new HashSet<>();
644      BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key
645      for (int i = size - 1; i >= 0; i--) {
646        if (!seen.add(entries[i].getKey())) {
647          dups.set(i);
648        }
649      }
650      if (dups.isEmpty()) {
651        return entries;
652      }
653      @SuppressWarnings({"rawtypes", "unchecked"})
654      Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()];
655      for (int inI = 0, outI = 0; inI < size; inI++) {
656        if (!dups.get(inI)) {
657          newEntries[outI++] = entries[inI];
658        }
659      }
660      return newEntries;
661    }
662  }
663
664  /**
665   * Returns an immutable map containing the same entries as {@code map}. The returned map iterates
666   * over entries in the same order as the {@code entrySet} of the original map. If {@code map}
667   * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
668   * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
669   *
670   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
671   * safe to do so. The exact circumstances under which a copy will or will not be performed are
672   * undocumented and subject to change.
673   *
674   * @throws NullPointerException if any key or value in {@code map} is null
675   */
676  public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
677    if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) {
678      @SuppressWarnings("unchecked") // safe since map is not writable
679      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
680      if (!kvMap.isPartialView()) {
681        return kvMap;
682      }
683    } else if (map instanceof EnumMap) {
684      @SuppressWarnings("unchecked") // safe since map is not writable
685      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) copyOfEnumMap((EnumMap<?, ?>) map);
686      return kvMap;
687    }
688    return copyOf(map.entrySet());
689  }
690
691  /**
692   * Returns an immutable map containing the specified entries. The returned map iterates over
693   * entries in the same order as the original iterable.
694   *
695   * @throws NullPointerException if any key, value, or entry is null
696   * @throws IllegalArgumentException if two entries have the same key
697   * @since 19.0
698   */
699  @Beta
700  public static <K, V> ImmutableMap<K, V> copyOf(
701      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
702    @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
703    Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
704    switch (entryArray.length) {
705      case 0:
706        return of();
707      case 1:
708        // requireNonNull is safe because the first `size` elements have been filled in.
709        Entry<K, V> onlyEntry = requireNonNull(entryArray[0]);
710        return of(onlyEntry.getKey(), onlyEntry.getValue());
711      default:
712        /*
713         * The current implementation will end up using entryArray directly, though it will write
714         * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
715         */
716        return RegularImmutableMap.fromEntries(entryArray);
717    }
718  }
719
720  private static <K extends Enum<K>, V> ImmutableMap<K, V> copyOfEnumMap(
721      EnumMap<K, ? extends V> original) {
722    EnumMap<K, V> copy = new EnumMap<>(original);
723    for (Entry<K, V> entry : copy.entrySet()) {
724      checkEntryNotNull(entry.getKey(), entry.getValue());
725    }
726    return ImmutableEnumMap.asImmutable(copy);
727  }
728
729  static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0];
730
731  abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> {
732    abstract UnmodifiableIterator<Entry<K, V>> entryIterator();
733
734    Spliterator<Entry<K, V>> entrySpliterator() {
735      return Spliterators.spliterator(
736          entryIterator(),
737          size(),
738          Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED);
739    }
740
741    @Override
742    ImmutableSet<K> createKeySet() {
743      return new ImmutableMapKeySet<>(this);
744    }
745
746    @Override
747    ImmutableSet<Entry<K, V>> createEntrySet() {
748      class EntrySetImpl extends ImmutableMapEntrySet<K, V> {
749        @Override
750        ImmutableMap<K, V> map() {
751          return IteratorBasedImmutableMap.this;
752        }
753
754        @Override
755        public UnmodifiableIterator<Entry<K, V>> iterator() {
756          return entryIterator();
757        }
758      }
759      return new EntrySetImpl();
760    }
761
762    @Override
763    ImmutableCollection<V> createValues() {
764      return new ImmutableMapValues<>(this);
765    }
766  }
767
768  ImmutableMap() {}
769
770  /**
771   * Guaranteed to throw an exception and leave the map unmodified.
772   *
773   * @throws UnsupportedOperationException always
774   * @deprecated Unsupported operation.
775   */
776  @CanIgnoreReturnValue
777  @Deprecated
778  @Override
779  @DoNotCall("Always throws UnsupportedOperationException")
780  @CheckForNull
781  public final V put(K k, V v) {
782    throw new UnsupportedOperationException();
783  }
784
785  /**
786   * Guaranteed to throw an exception and leave the map unmodified.
787   *
788   * @throws UnsupportedOperationException always
789   * @deprecated Unsupported operation.
790   */
791  @CanIgnoreReturnValue
792  @Deprecated
793  @Override
794  @DoNotCall("Always throws UnsupportedOperationException")
795  @CheckForNull
796  public final V putIfAbsent(K key, V value) {
797    throw new UnsupportedOperationException();
798  }
799
800  /**
801   * Guaranteed to throw an exception and leave the map unmodified.
802   *
803   * @throws UnsupportedOperationException always
804   * @deprecated Unsupported operation.
805   */
806  @Deprecated
807  @Override
808  @DoNotCall("Always throws UnsupportedOperationException")
809  public final boolean replace(K key, V oldValue, V newValue) {
810    throw new UnsupportedOperationException();
811  }
812
813  /**
814   * Guaranteed to throw an exception and leave the map unmodified.
815   *
816   * @throws UnsupportedOperationException always
817   * @deprecated Unsupported operation.
818   */
819  @Deprecated
820  @Override
821  @CheckForNull
822  @DoNotCall("Always throws UnsupportedOperationException")
823  public final V replace(K key, V value) {
824    throw new UnsupportedOperationException();
825  }
826
827  /**
828   * Guaranteed to throw an exception and leave the map unmodified.
829   *
830   * @throws UnsupportedOperationException always
831   * @deprecated Unsupported operation.
832   */
833  @Deprecated
834  @Override
835  @DoNotCall("Always throws UnsupportedOperationException")
836  public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
837    throw new UnsupportedOperationException();
838  }
839
840  /**
841   * Guaranteed to throw an exception and leave the map unmodified.
842   *
843   * @throws UnsupportedOperationException always
844   * @deprecated Unsupported operation.
845   */
846  @Deprecated
847  @Override
848  @DoNotCall("Always throws UnsupportedOperationException")
849  public final V computeIfPresent(
850      K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
851    throw new UnsupportedOperationException();
852  }
853
854  /**
855   * Guaranteed to throw an exception and leave the map unmodified.
856   *
857   * @throws UnsupportedOperationException always
858   * @deprecated Unsupported operation.
859   */
860  @Deprecated
861  @Override
862  @DoNotCall("Always throws UnsupportedOperationException")
863  public final V compute(
864      K key, BiFunction<? super K, ? super @Nullable V, ? extends V> remappingFunction) {
865    throw new UnsupportedOperationException();
866  }
867
868  /**
869   * Guaranteed to throw an exception and leave the map unmodified.
870   *
871   * @throws UnsupportedOperationException always
872   * @deprecated Unsupported operation.
873   */
874  @Deprecated
875  @Override
876  @DoNotCall("Always throws UnsupportedOperationException")
877  public final V merge(
878      K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
879    throw new UnsupportedOperationException();
880  }
881
882  /**
883   * Guaranteed to throw an exception and leave the map unmodified.
884   *
885   * @throws UnsupportedOperationException always
886   * @deprecated Unsupported operation.
887   */
888  @Deprecated
889  @Override
890  @DoNotCall("Always throws UnsupportedOperationException")
891  public final void putAll(Map<? extends K, ? extends V> map) {
892    throw new UnsupportedOperationException();
893  }
894
895  /**
896   * Guaranteed to throw an exception and leave the map unmodified.
897   *
898   * @throws UnsupportedOperationException always
899   * @deprecated Unsupported operation.
900   */
901  @Deprecated
902  @Override
903  @DoNotCall("Always throws UnsupportedOperationException")
904  public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
905    throw new UnsupportedOperationException();
906  }
907
908  /**
909   * Guaranteed to throw an exception and leave the map unmodified.
910   *
911   * @throws UnsupportedOperationException always
912   * @deprecated Unsupported operation.
913   */
914  @Deprecated
915  @Override
916  @DoNotCall("Always throws UnsupportedOperationException")
917  @CheckForNull
918  public final V remove(@CheckForNull Object o) {
919    throw new UnsupportedOperationException();
920  }
921
922  /**
923   * Guaranteed to throw an exception and leave the map unmodified.
924   *
925   * @throws UnsupportedOperationException always
926   * @deprecated Unsupported operation.
927   */
928  @Deprecated
929  @Override
930  @DoNotCall("Always throws UnsupportedOperationException")
931  public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) {
932    throw new UnsupportedOperationException();
933  }
934
935  /**
936   * Guaranteed to throw an exception and leave the map unmodified.
937   *
938   * @throws UnsupportedOperationException always
939   * @deprecated Unsupported operation.
940   */
941  @Deprecated
942  @Override
943  @DoNotCall("Always throws UnsupportedOperationException")
944  public final void clear() {
945    throw new UnsupportedOperationException();
946  }
947
948  @Override
949  public boolean isEmpty() {
950    return size() == 0;
951  }
952
953  @Override
954  public boolean containsKey(@CheckForNull Object key) {
955    return get(key) != null;
956  }
957
958  @Override
959  public boolean containsValue(@CheckForNull Object value) {
960    return values().contains(value);
961  }
962
963  // Overriding to mark it Nullable
964  @Override
965  @CheckForNull
966  public abstract V get(@CheckForNull Object key);
967
968  /**
969   * @since 21.0 (but only since 23.5 in the Android <a
970   *     href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>).
971   *     Note, however, that Java 8 users can call this method with any version and flavor of Guava.
972   */
973  @Override
974  @CheckForNull
975  public final V getOrDefault(@CheckForNull Object key, @CheckForNull V defaultValue) {
976    /*
977     * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who
978     * pass a literal "null" should probably just use `get`, but I would expect other callers to
979     * pass an expression that *might* be null. This could happen with:
980     *
981     * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns
982     *   `map.getOrDefault(FOO_KEY, defaultValue)`
983     *
984     * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key,
985     *   ...))`
986     *
987     * So it makes sense for the parameter (and thus the return type) to be @CheckForNull.
988     *
989     * Two other points:
990     *
991     * 1. We'll want to use something like @PolyNull once we can make that work for the various
992     * platforms we target.
993     *
994     * 2. Kotlin's Map type has a getOrDefault method that accepts and returns a "plain V," in
995     * contrast to the "V?" type that we're using. As a result, Kotlin sees a conflict between the
996     * nullness annotations in ImmutableMap and those in its own Map type. In response, it considers
997     * the parameter and return type both to be platform types. As a result, Kotlin permits calls
998     * that can lead to NullPointerException. That's unfortunate. But hopefully most Kotlin callers
999     * use `get(key) ?: defaultValue` instead of this method, anyway.
1000     */
1001    V result = get(key);
1002    // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker.
1003    if (result != null) {
1004      return result;
1005    } else {
1006      return defaultValue;
1007    }
1008  }
1009
1010  @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<Entry<K, V>> entrySet;
1011
1012  /**
1013   * Returns an immutable set of the mappings in this map. The iteration order is specified by the
1014   * method used to create this map. Typically, this is insertion order.
1015   */
1016  @Override
1017  public ImmutableSet<Entry<K, V>> entrySet() {
1018    ImmutableSet<Entry<K, V>> result = entrySet;
1019    return (result == null) ? entrySet = createEntrySet() : result;
1020  }
1021
1022  abstract ImmutableSet<Entry<K, V>> createEntrySet();
1023
1024  @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<K> keySet;
1025
1026  /**
1027   * Returns an immutable set of the keys in this map, in the same order that they appear in {@link
1028   * #entrySet}.
1029   */
1030  @Override
1031  public ImmutableSet<K> keySet() {
1032    ImmutableSet<K> result = keySet;
1033    return (result == null) ? keySet = createKeySet() : result;
1034  }
1035
1036  /*
1037   * This could have a good default implementation of return new ImmutableKeySet<K, V>(this),
1038   * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap
1039   * overrides it.
1040   */
1041  abstract ImmutableSet<K> createKeySet();
1042
1043  UnmodifiableIterator<K> keyIterator() {
1044    final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator();
1045    return new UnmodifiableIterator<K>() {
1046      @Override
1047      public boolean hasNext() {
1048        return entryIterator.hasNext();
1049      }
1050
1051      @Override
1052      public K next() {
1053        return entryIterator.next().getKey();
1054      }
1055    };
1056  }
1057
1058  Spliterator<K> keySpliterator() {
1059    return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey);
1060  }
1061
1062  @LazyInit @RetainedWith @CheckForNull private transient ImmutableCollection<V> values;
1063
1064  /**
1065   * Returns an immutable collection of the values in this map, in the same order that they appear
1066   * in {@link #entrySet}.
1067   */
1068  @Override
1069  public ImmutableCollection<V> values() {
1070    ImmutableCollection<V> result = values;
1071    return (result == null) ? values = createValues() : result;
1072  }
1073
1074  /*
1075   * This could have a good default implementation of {@code return new
1076   * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default
1077   * when RegularImmutableMap overrides it.
1078   */
1079  abstract ImmutableCollection<V> createValues();
1080
1081  // cached so that this.multimapView().inverse() only computes inverse once
1082  @LazyInit @CheckForNull private transient ImmutableSetMultimap<K, V> multimapView;
1083
1084  /**
1085   * Returns a multimap view of the map.
1086   *
1087   * @since 14.0
1088   */
1089  public ImmutableSetMultimap<K, V> asMultimap() {
1090    if (isEmpty()) {
1091      return ImmutableSetMultimap.of();
1092    }
1093    ImmutableSetMultimap<K, V> result = multimapView;
1094    return (result == null)
1095        ? (multimapView =
1096            new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null))
1097        : result;
1098  }
1099
1100  @WeakOuter
1101  private final class MapViewOfValuesAsSingletonSets
1102      extends IteratorBasedImmutableMap<K, ImmutableSet<V>> {
1103
1104    @Override
1105    public int size() {
1106      return ImmutableMap.this.size();
1107    }
1108
1109    @Override
1110    ImmutableSet<K> createKeySet() {
1111      return ImmutableMap.this.keySet();
1112    }
1113
1114    @Override
1115    public boolean containsKey(@CheckForNull Object key) {
1116      return ImmutableMap.this.containsKey(key);
1117    }
1118
1119    @Override
1120    @CheckForNull
1121    public ImmutableSet<V> get(@CheckForNull Object key) {
1122      V outerValue = ImmutableMap.this.get(key);
1123      return (outerValue == null) ? null : ImmutableSet.of(outerValue);
1124    }
1125
1126    @Override
1127    boolean isPartialView() {
1128      return ImmutableMap.this.isPartialView();
1129    }
1130
1131    @Override
1132    public int hashCode() {
1133      // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same
1134      return ImmutableMap.this.hashCode();
1135    }
1136
1137    @Override
1138    boolean isHashCodeFast() {
1139      return ImmutableMap.this.isHashCodeFast();
1140    }
1141
1142    @Override
1143    UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() {
1144      final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator();
1145      return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() {
1146        @Override
1147        public boolean hasNext() {
1148          return backingIterator.hasNext();
1149        }
1150
1151        @Override
1152        public Entry<K, ImmutableSet<V>> next() {
1153          final Entry<K, V> backingEntry = backingIterator.next();
1154          return new AbstractMapEntry<K, ImmutableSet<V>>() {
1155            @Override
1156            public K getKey() {
1157              return backingEntry.getKey();
1158            }
1159
1160            @Override
1161            public ImmutableSet<V> getValue() {
1162              return ImmutableSet.of(backingEntry.getValue());
1163            }
1164          };
1165        }
1166      };
1167    }
1168  }
1169
1170  @Override
1171  public boolean equals(@CheckForNull Object object) {
1172    return Maps.equalsImpl(this, object);
1173  }
1174
1175  abstract boolean isPartialView();
1176
1177  @Override
1178  public int hashCode() {
1179    return Sets.hashCodeImpl(entrySet());
1180  }
1181
1182  boolean isHashCodeFast() {
1183    return false;
1184  }
1185
1186  @Override
1187  public String toString() {
1188    return Maps.toStringImpl(this);
1189  }
1190
1191  /**
1192   * Serialized type for all ImmutableMap instances. It captures the logical contents and they are
1193   * reconstructed using public factory methods. This ensures that the implementation types remain
1194   * as implementation details.
1195   */
1196  static class SerializedForm<K, V> implements Serializable {
1197    // This object retains references to collections returned by keySet() and value(). This saves
1198    // bytes when the both the map and its keySet or value collection are written to the same
1199    // instance of ObjectOutputStream.
1200
1201    // TODO(b/160980469): remove support for the old serialization format after some time
1202    private static final boolean USE_LEGACY_SERIALIZATION = true;
1203
1204    private final Object keys;
1205    private final Object values;
1206
1207    SerializedForm(ImmutableMap<K, V> map) {
1208      if (USE_LEGACY_SERIALIZATION) {
1209        Object[] keys = new Object[map.size()];
1210        Object[] values = new Object[map.size()];
1211        int i = 0;
1212        // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013
1213        for (Entry<? extends Object, ? extends Object> entry : map.entrySet()) {
1214          keys[i] = entry.getKey();
1215          values[i] = entry.getValue();
1216          i++;
1217        }
1218        this.keys = keys;
1219        this.values = values;
1220        return;
1221      }
1222      this.keys = map.keySet();
1223      this.values = map.values();
1224    }
1225
1226    @SuppressWarnings("unchecked")
1227    final Object readResolve() {
1228      if (!(this.keys instanceof ImmutableSet)) {
1229        return legacyReadResolve();
1230      }
1231
1232      ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys;
1233      ImmutableCollection<V> values = (ImmutableCollection<V>) this.values;
1234
1235      Builder<K, V> builder = makeBuilder(keySet.size());
1236
1237      UnmodifiableIterator<K> keyIter = keySet.iterator();
1238      UnmodifiableIterator<V> valueIter = values.iterator();
1239
1240      while (keyIter.hasNext()) {
1241        builder.put(keyIter.next(), valueIter.next());
1242      }
1243
1244      return builder.buildOrThrow();
1245    }
1246
1247    @SuppressWarnings("unchecked")
1248    final Object legacyReadResolve() {
1249      K[] keys = (K[]) this.keys;
1250      V[] values = (V[]) this.values;
1251
1252      Builder<K, V> builder = makeBuilder(keys.length);
1253
1254      for (int i = 0; i < keys.length; i++) {
1255        builder.put(keys[i], values[i]);
1256      }
1257      return builder.buildOrThrow();
1258    }
1259
1260    /**
1261     * Returns a builder that builds the unserialized type. Subclasses should override this method.
1262     */
1263    Builder<K, V> makeBuilder(int size) {
1264      return new Builder<>(size);
1265    }
1266
1267    private static final long serialVersionUID = 0;
1268  }
1269
1270  /**
1271   * Returns a serializable form of this object. Non-public subclasses should not override this
1272   * method. Publicly-accessible subclasses must override this method and should return a subclass
1273   * of SerializedForm whose readResolve() method returns objects of the subclass type.
1274   */
1275  Object writeReplace() {
1276    return new SerializedForm<>(this);
1277  }
1278
1279  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
1280    throw new InvalidObjectException("Use SerializedForm");
1281  }
1282}