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