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