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