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