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