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