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