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          nonNullEntries = lastEntryForEachKey(nonNullEntries, size);
566          localSize = nonNullEntries.length;
567        }
568        Arrays.sort(
569            nonNullEntries,
570            0,
571            localSize,
572            Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
573        localEntries = (@Nullable Entry<K, V>[]) nonNullEntries;
574      }
575      entriesUsed = true;
576      return RegularImmutableMap.fromEntryArray(localSize, localEntries, throwIfDuplicateKeys);
577    }
578
579    /**
580     * Returns a newly-created immutable map. The iteration order of the returned map is the order
581     * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was
582     * called, in which case entries are sorted by value.
583     *
584     * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method
585     * will throw an exception if there are duplicate keys. The {@code build()} method will soon be
586     * deprecated.
587     *
588     * @throws IllegalArgumentException if duplicate keys were added
589     */
590    public ImmutableMap<K, V> build() {
591      return buildOrThrow();
592    }
593
594    /**
595     * Returns a newly-created immutable map, or throws an exception if any key was added more than
596     * once. The iteration order of the returned map is the order in which entries were inserted
597     * into the builder, unless {@link #orderEntriesByValue} was called, in which case entries are
598     * sorted by value.
599     *
600     * @throws IllegalArgumentException if duplicate keys were added
601     * @since 31.0
602     */
603    public ImmutableMap<K, V> buildOrThrow() {
604      return build(true);
605    }
606
607    /**
608     * Returns a newly-created immutable map, using the last value for any key that was added more
609     * than once. The iteration order of the returned map is the order in which entries were
610     * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case
611     * entries are sorted by value. If a key was added more than once, it appears in iteration order
612     * based on the first time it was added, again unless {@link #orderEntriesByValue} was called.
613     *
614     * <p>In the current implementation, all values associated with a given key are stored in the
615     * {@code Builder} object, even though only one of them will be used in the built map. If there
616     * can be many repeated keys, it may be more space-efficient to use a {@link
617     * java.util.LinkedHashMap LinkedHashMap} and {@link ImmutableMap#copyOf(Map)} rather than
618     * {@code ImmutableMap.Builder}.
619     *
620     * @since 31.1
621     */
622    public ImmutableMap<K, V> buildKeepingLast() {
623      return build(false);
624    }
625
626    @VisibleForTesting // only for testing JDK backed implementation
627    ImmutableMap<K, V> buildJdkBacked() {
628      checkState(
629          valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator");
630      switch (size) {
631        case 0:
632          return of();
633        case 1:
634          // requireNonNull is safe because the first `size` elements have been filled in.
635          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
636          return of(onlyEntry.getKey(), onlyEntry.getValue());
637        default:
638          entriesUsed = true;
639          return JdkBackedImmutableMap.create(size, entries, /* throwIfDuplicateKeys= */ true);
640      }
641    }
642
643    private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) {
644      Set<K> seen = new HashSet<>();
645      BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key
646      for (int i = size - 1; i >= 0; i--) {
647        if (!seen.add(entries[i].getKey())) {
648          dups.set(i);
649        }
650      }
651      if (dups.isEmpty()) {
652        return entries;
653      }
654      @SuppressWarnings({"rawtypes", "unchecked"})
655      Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()];
656      for (int inI = 0, outI = 0; inI < size; inI++) {
657        if (!dups.get(inI)) {
658          newEntries[outI++] = entries[inI];
659        }
660      }
661      return newEntries;
662    }
663  }
664
665  /**
666   * Returns an immutable map containing the same entries as {@code map}. The returned map iterates
667   * over entries in the same order as the {@code entrySet} of the original map. If {@code map}
668   * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
669   * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
670   *
671   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
672   * safe to do so. The exact circumstances under which a copy will or will not be performed are
673   * undocumented and subject to change.
674   *
675   * @throws NullPointerException if any key or value in {@code map} is null
676   */
677  public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
678    if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) {
679      @SuppressWarnings("unchecked") // safe since map is not writable
680      ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
681      if (!kvMap.isPartialView()) {
682        return kvMap;
683      }
684    } else if (map instanceof EnumMap) {
685      @SuppressWarnings("unchecked") // safe since map is not writable
686      ImmutableMap<K, V> kvMap =
687          (ImmutableMap<K, V>)
688              copyOfEnumMap(
689                  (EnumMap<?, ? extends V>) map); // hide K (violates bounds) from J2KT, preserve V.
690      return kvMap;
691    }
692    return copyOf(map.entrySet());
693  }
694
695  /**
696   * Returns an immutable map containing the specified entries. The returned map iterates over
697   * entries in the same order as the original iterable.
698   *
699   * @throws NullPointerException if any key, value, or entry is null
700   * @throws IllegalArgumentException if two entries have the same key
701   * @since 19.0
702   */
703  public static <K, V> ImmutableMap<K, V> copyOf(
704      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
705    @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
706    Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
707    switch (entryArray.length) {
708      case 0:
709        return of();
710      case 1:
711        // requireNonNull is safe because the first `size` elements have been filled in.
712        Entry<K, V> onlyEntry = requireNonNull(entryArray[0]);
713        return of(onlyEntry.getKey(), onlyEntry.getValue());
714      default:
715        /*
716         * The current implementation will end up using entryArray directly, though it will write
717         * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
718         */
719        return RegularImmutableMap.fromEntries(entryArray);
720    }
721  }
722
723  private static <K extends Enum<K>, V> ImmutableMap<K, ? extends V> copyOfEnumMap(
724      EnumMap<?, ? extends V> original) {
725    @SuppressWarnings("unchecked") // the best we could do to make copyOf(Map) compile
726    EnumMap<K, V> copy = new EnumMap<>((EnumMap<K, ? extends V>) original);
727    for (Entry<K, V> entry : copy.entrySet()) {
728      checkEntryNotNull(entry.getKey(), entry.getValue());
729    }
730    return ImmutableEnumMap.asImmutable(copy);
731  }
732
733  static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0];
734
735  abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> {
736    abstract UnmodifiableIterator<Entry<K, V>> entryIterator();
737
738    Spliterator<Entry<K, V>> entrySpliterator() {
739      return Spliterators.spliterator(
740          entryIterator(),
741          size(),
742          Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED);
743    }
744
745    @Override
746    ImmutableSet<K> createKeySet() {
747      return new ImmutableMapKeySet<>(this);
748    }
749
750    @Override
751    ImmutableSet<Entry<K, V>> createEntrySet() {
752      class EntrySetImpl extends ImmutableMapEntrySet<K, V> {
753        @Override
754        ImmutableMap<K, V> map() {
755          return IteratorBasedImmutableMap.this;
756        }
757
758        @Override
759        public UnmodifiableIterator<Entry<K, V>> iterator() {
760          return entryIterator();
761        }
762
763        // redeclare to help optimizers with b/310253115
764        @SuppressWarnings("RedundantOverride")
765        @Override
766        @J2ktIncompatible // serialization
767        @GwtIncompatible // serialization
768        Object writeReplace() {
769          return super.writeReplace();
770        }
771      }
772      return new EntrySetImpl();
773    }
774
775    @Override
776    ImmutableCollection<V> createValues() {
777      return new ImmutableMapValues<>(this);
778    }
779
780    // redeclare to help optimizers with b/310253115
781    @SuppressWarnings("RedundantOverride")
782    @Override
783    @J2ktIncompatible // serialization
784    @GwtIncompatible // serialization
785    Object writeReplace() {
786      return super.writeReplace();
787    }
788  }
789
790  ImmutableMap() {}
791
792  /**
793   * Guaranteed to throw an exception and leave the map unmodified.
794   *
795   * @throws UnsupportedOperationException always
796   * @deprecated Unsupported operation.
797   */
798  @CanIgnoreReturnValue
799  @Deprecated
800  @Override
801  @DoNotCall("Always throws UnsupportedOperationException")
802  @CheckForNull
803  public final V put(K k, V v) {
804    throw new UnsupportedOperationException();
805  }
806
807  /**
808   * Guaranteed to throw an exception and leave the map unmodified.
809   *
810   * @throws UnsupportedOperationException always
811   * @deprecated Unsupported operation.
812   */
813  @CanIgnoreReturnValue
814  @Deprecated
815  @Override
816  @DoNotCall("Always throws UnsupportedOperationException")
817  @CheckForNull
818  public final V putIfAbsent(K key, V value) {
819    throw new UnsupportedOperationException();
820  }
821
822  /**
823   * Guaranteed to throw an exception and leave the map unmodified.
824   *
825   * @throws UnsupportedOperationException always
826   * @deprecated Unsupported operation.
827   */
828  @Deprecated
829  @Override
830  @DoNotCall("Always throws UnsupportedOperationException")
831  public final boolean replace(K key, V oldValue, V newValue) {
832    throw new UnsupportedOperationException();
833  }
834
835  /**
836   * Guaranteed to throw an exception and leave the map unmodified.
837   *
838   * @throws UnsupportedOperationException always
839   * @deprecated Unsupported operation.
840   */
841  @Deprecated
842  @Override
843  @CheckForNull
844  @DoNotCall("Always throws UnsupportedOperationException")
845  public final V replace(K key, V value) {
846    throw new UnsupportedOperationException();
847  }
848
849  /**
850   * Guaranteed to throw an exception and leave the map unmodified.
851   *
852   * @throws UnsupportedOperationException always
853   * @deprecated Unsupported operation.
854   */
855  @Deprecated
856  @Override
857  @DoNotCall("Always throws UnsupportedOperationException")
858  public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
859    throw new UnsupportedOperationException();
860  }
861
862  /**
863   * Guaranteed to throw an exception and leave the map unmodified.
864   *
865   * @throws UnsupportedOperationException always
866   * @deprecated Unsupported operation.
867   */
868  @Deprecated
869  @Override
870  @DoNotCall("Always throws UnsupportedOperationException")
871  @CheckForNull
872  public final V computeIfPresent(
873      K key, BiFunction<? super K, ? super V, ? extends @Nullable V> remappingFunction) {
874    throw new UnsupportedOperationException();
875  }
876
877  /**
878   * Guaranteed to throw an exception and leave the map unmodified.
879   *
880   * @throws UnsupportedOperationException always
881   * @deprecated Unsupported operation.
882   */
883  @Deprecated
884  @Override
885  @DoNotCall("Always throws UnsupportedOperationException")
886  @CheckForNull
887  public final V compute(
888      K key, BiFunction<? super K, ? super @Nullable V, ? extends @Nullable V> remappingFunction) {
889    throw new UnsupportedOperationException();
890  }
891
892  /**
893   * Guaranteed to throw an exception and leave the map unmodified.
894   *
895   * @throws UnsupportedOperationException always
896   * @deprecated Unsupported operation.
897   */
898  @Deprecated
899  @Override
900  @DoNotCall("Always throws UnsupportedOperationException")
901  @CheckForNull
902  public final V merge(
903      K key, V value, BiFunction<? super V, ? super V, ? extends @Nullable V> function) {
904    throw new UnsupportedOperationException();
905  }
906
907  /**
908   * Guaranteed to throw an exception and leave the map unmodified.
909   *
910   * @throws UnsupportedOperationException always
911   * @deprecated Unsupported operation.
912   */
913  @Deprecated
914  @Override
915  @DoNotCall("Always throws UnsupportedOperationException")
916  public final void putAll(Map<? extends K, ? extends V> map) {
917    throw new UnsupportedOperationException();
918  }
919
920  /**
921   * Guaranteed to throw an exception and leave the map unmodified.
922   *
923   * @throws UnsupportedOperationException always
924   * @deprecated Unsupported operation.
925   */
926  @Deprecated
927  @Override
928  @DoNotCall("Always throws UnsupportedOperationException")
929  public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
930    throw new UnsupportedOperationException();
931  }
932
933  /**
934   * Guaranteed to throw an exception and leave the map unmodified.
935   *
936   * @throws UnsupportedOperationException always
937   * @deprecated Unsupported operation.
938   */
939  @Deprecated
940  @Override
941  @DoNotCall("Always throws UnsupportedOperationException")
942  @CheckForNull
943  public final V remove(@CheckForNull Object o) {
944    throw new UnsupportedOperationException();
945  }
946
947  /**
948   * Guaranteed to throw an exception and leave the map unmodified.
949   *
950   * @throws UnsupportedOperationException always
951   * @deprecated Unsupported operation.
952   */
953  @Deprecated
954  @Override
955  @DoNotCall("Always throws UnsupportedOperationException")
956  public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) {
957    throw new UnsupportedOperationException();
958  }
959
960  /**
961   * Guaranteed to throw an exception and leave the map unmodified.
962   *
963   * @throws UnsupportedOperationException always
964   * @deprecated Unsupported operation.
965   */
966  @Deprecated
967  @Override
968  @DoNotCall("Always throws UnsupportedOperationException")
969  public final void clear() {
970    throw new UnsupportedOperationException();
971  }
972
973  @Override
974  public boolean isEmpty() {
975    return size() == 0;
976  }
977
978  @Override
979  public boolean containsKey(@CheckForNull Object key) {
980    return get(key) != null;
981  }
982
983  @Override
984  public boolean containsValue(@CheckForNull Object value) {
985    return values().contains(value);
986  }
987
988  // Overriding to mark it Nullable
989  @Override
990  @CheckForNull
991  public abstract V get(@CheckForNull Object key);
992
993  /**
994   * @since 21.0 (but only since 23.5 in the Android <a
995   *     href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>).
996   *     Note, however, that Java 8+ users can call this method with any version and flavor of
997   *     Guava.
998   */
999  @Override
1000  @CheckForNull
1001  public final V getOrDefault(@CheckForNull Object key, @CheckForNull V defaultValue) {
1002    /*
1003     * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who
1004     * pass a literal "null" should probably just use `get`, but I would expect other callers to
1005     * pass an expression that *might* be null. This could happen with:
1006     *
1007     * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns
1008     *   `map.getOrDefault(FOO_KEY, defaultValue)`
1009     *
1010     * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key,
1011     *   ...))`
1012     *
1013     * So it makes sense for the parameter (and thus the return type) to be @CheckForNull.
1014     *
1015     * Two other points:
1016     *
1017     * 1. We'll want to use something like @PolyNull once we can make that work for the various
1018     * platforms we target.
1019     *
1020     * 2. Kotlin's Map type has a getOrDefault method that accepts and returns a "plain V," in
1021     * contrast to the "V?" type that we're using. As a result, Kotlin sees a conflict between the
1022     * nullness annotations in ImmutableMap and those in its own Map type. In response, it considers
1023     * the parameter and return type both to be platform types. As a result, Kotlin permits calls
1024     * that can lead to NullPointerException. That's unfortunate. But hopefully most Kotlin callers
1025     * use `get(key) ?: defaultValue` instead of this method, anyway.
1026     */
1027    V result = get(key);
1028    // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker.
1029    if (result != null) {
1030      return result;
1031    } else {
1032      return defaultValue;
1033    }
1034  }
1035
1036  @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<Entry<K, V>> entrySet;
1037
1038  /**
1039   * Returns an immutable set of the mappings in this map. The iteration order is specified by the
1040   * method used to create this map. Typically, this is insertion order.
1041   */
1042  @Override
1043  public ImmutableSet<Entry<K, V>> entrySet() {
1044    ImmutableSet<Entry<K, V>> result = entrySet;
1045    return (result == null) ? entrySet = createEntrySet() : result;
1046  }
1047
1048  abstract ImmutableSet<Entry<K, V>> createEntrySet();
1049
1050  @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<K> keySet;
1051
1052  /**
1053   * Returns an immutable set of the keys in this map, in the same order that they appear in {@link
1054   * #entrySet}.
1055   */
1056  @Override
1057  public ImmutableSet<K> keySet() {
1058    ImmutableSet<K> result = keySet;
1059    return (result == null) ? keySet = createKeySet() : result;
1060  }
1061
1062  /*
1063   * This could have a good default implementation of return new ImmutableKeySet<K, V>(this),
1064   * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap
1065   * overrides it.
1066   */
1067  abstract ImmutableSet<K> createKeySet();
1068
1069  UnmodifiableIterator<K> keyIterator() {
1070    final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator();
1071    return new UnmodifiableIterator<K>() {
1072      @Override
1073      public boolean hasNext() {
1074        return entryIterator.hasNext();
1075      }
1076
1077      @Override
1078      public K next() {
1079        return entryIterator.next().getKey();
1080      }
1081    };
1082  }
1083
1084  Spliterator<K> keySpliterator() {
1085    return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey);
1086  }
1087
1088  @LazyInit @RetainedWith @CheckForNull private transient ImmutableCollection<V> values;
1089
1090  /**
1091   * Returns an immutable collection of the values in this map, in the same order that they appear
1092   * in {@link #entrySet}.
1093   */
1094  @Override
1095  public ImmutableCollection<V> values() {
1096    ImmutableCollection<V> result = values;
1097    return (result == null) ? values = createValues() : result;
1098  }
1099
1100  /*
1101   * This could have a good default implementation of {@code return new
1102   * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default
1103   * when RegularImmutableMap overrides it.
1104   */
1105  abstract ImmutableCollection<V> createValues();
1106
1107  // cached so that this.multimapView().inverse() only computes inverse once
1108  @LazyInit @CheckForNull private transient ImmutableSetMultimap<K, V> multimapView;
1109
1110  /**
1111   * Returns a multimap view of the map.
1112   *
1113   * @since 14.0
1114   */
1115  public ImmutableSetMultimap<K, V> asMultimap() {
1116    if (isEmpty()) {
1117      return ImmutableSetMultimap.of();
1118    }
1119    ImmutableSetMultimap<K, V> result = multimapView;
1120    return (result == null)
1121        ? (multimapView =
1122            new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null))
1123        : result;
1124  }
1125
1126  @WeakOuter
1127  private final class MapViewOfValuesAsSingletonSets
1128      extends IteratorBasedImmutableMap<K, ImmutableSet<V>> {
1129
1130    @Override
1131    public int size() {
1132      return ImmutableMap.this.size();
1133    }
1134
1135    @Override
1136    ImmutableSet<K> createKeySet() {
1137      return ImmutableMap.this.keySet();
1138    }
1139
1140    @Override
1141    public boolean containsKey(@CheckForNull Object key) {
1142      return ImmutableMap.this.containsKey(key);
1143    }
1144
1145    @Override
1146    @CheckForNull
1147    public ImmutableSet<V> get(@CheckForNull Object key) {
1148      V outerValue = ImmutableMap.this.get(key);
1149      return (outerValue == null) ? null : ImmutableSet.of(outerValue);
1150    }
1151
1152    @Override
1153    boolean isPartialView() {
1154      return ImmutableMap.this.isPartialView();
1155    }
1156
1157    @Override
1158    public int hashCode() {
1159      // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same
1160      return ImmutableMap.this.hashCode();
1161    }
1162
1163    @Override
1164    boolean isHashCodeFast() {
1165      return ImmutableMap.this.isHashCodeFast();
1166    }
1167
1168    @Override
1169    UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() {
1170      final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator();
1171      return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() {
1172        @Override
1173        public boolean hasNext() {
1174          return backingIterator.hasNext();
1175        }
1176
1177        @Override
1178        public Entry<K, ImmutableSet<V>> next() {
1179          final Entry<K, V> backingEntry = backingIterator.next();
1180          return new AbstractMapEntry<K, ImmutableSet<V>>() {
1181            @Override
1182            public K getKey() {
1183              return backingEntry.getKey();
1184            }
1185
1186            @Override
1187            public ImmutableSet<V> getValue() {
1188              return ImmutableSet.of(backingEntry.getValue());
1189            }
1190          };
1191        }
1192      };
1193    }
1194
1195    // redeclare to help optimizers with b/310253115
1196    @SuppressWarnings("RedundantOverride")
1197    @Override
1198    @J2ktIncompatible // serialization
1199    @GwtIncompatible // serialization
1200    Object writeReplace() {
1201      return super.writeReplace();
1202    }
1203  }
1204
1205  @Override
1206  public boolean equals(@CheckForNull Object object) {
1207    return Maps.equalsImpl(this, object);
1208  }
1209
1210  abstract boolean isPartialView();
1211
1212  @Override
1213  public int hashCode() {
1214    return Sets.hashCodeImpl(entrySet());
1215  }
1216
1217  boolean isHashCodeFast() {
1218    return false;
1219  }
1220
1221  @Override
1222  public String toString() {
1223    return Maps.toStringImpl(this);
1224  }
1225
1226  /**
1227   * Serialized type for all ImmutableMap instances. It captures the logical contents and they are
1228   * reconstructed using public factory methods. This ensures that the implementation types remain
1229   * as implementation details.
1230   */
1231  @J2ktIncompatible // serialization
1232  static class SerializedForm<K, V> implements Serializable {
1233    // This object retains references to collections returned by keySet() and value(). This saves
1234    // bytes when the both the map and its keySet or value collection are written to the same
1235    // instance of ObjectOutputStream.
1236
1237    // TODO(b/160980469): remove support for the old serialization format after some time
1238    private static final boolean USE_LEGACY_SERIALIZATION = true;
1239
1240    private final Object keys;
1241    private final Object values;
1242
1243    SerializedForm(ImmutableMap<K, V> map) {
1244      if (USE_LEGACY_SERIALIZATION) {
1245        Object[] keys = new Object[map.size()];
1246        Object[] values = new Object[map.size()];
1247        int i = 0;
1248        // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013
1249        for (Entry<? extends Object, ? extends Object> entry : map.entrySet()) {
1250          keys[i] = entry.getKey();
1251          values[i] = entry.getValue();
1252          i++;
1253        }
1254        this.keys = keys;
1255        this.values = values;
1256        return;
1257      }
1258      this.keys = map.keySet();
1259      this.values = map.values();
1260    }
1261
1262    @SuppressWarnings("unchecked")
1263    final Object readResolve() {
1264      if (!(this.keys instanceof ImmutableSet)) {
1265        return legacyReadResolve();
1266      }
1267
1268      ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys;
1269      ImmutableCollection<V> values = (ImmutableCollection<V>) this.values;
1270
1271      Builder<K, V> builder = makeBuilder(keySet.size());
1272
1273      UnmodifiableIterator<K> keyIter = keySet.iterator();
1274      UnmodifiableIterator<V> valueIter = values.iterator();
1275
1276      while (keyIter.hasNext()) {
1277        builder.put(keyIter.next(), valueIter.next());
1278      }
1279
1280      return builder.buildOrThrow();
1281    }
1282
1283    @SuppressWarnings("unchecked")
1284    final Object legacyReadResolve() {
1285      K[] keys = (K[]) this.keys;
1286      V[] values = (V[]) this.values;
1287
1288      Builder<K, V> builder = makeBuilder(keys.length);
1289
1290      for (int i = 0; i < keys.length; i++) {
1291        builder.put(keys[i], values[i]);
1292      }
1293      return builder.buildOrThrow();
1294    }
1295
1296    /**
1297     * Returns a builder that builds the unserialized type. Subclasses should override this method.
1298     */
1299    Builder<K, V> makeBuilder(int size) {
1300      return new Builder<>(size);
1301    }
1302
1303    private static final long serialVersionUID = 0;
1304  }
1305
1306  /**
1307   * Returns a serializable form of this object. Non-public subclasses should not override this
1308   * method. Publicly-accessible subclasses must override this method and should return a subclass
1309   * of SerializedForm whose readResolve() method returns objects of the subclass type.
1310   */
1311  @J2ktIncompatible // serialization
1312  Object writeReplace() {
1313    return new SerializedForm<>(this);
1314  }
1315
1316  @J2ktIncompatible // java.io.ObjectInputStream
1317  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
1318    throw new InvalidObjectException("Use SerializedForm");
1319  }
1320
1321  private static final long serialVersionUID = 0xcafebabe;
1322}