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