1 /*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.base.Preconditions.checkState;
21 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
22 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
23
24 import com.google.common.annotations.Beta;
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.annotations.VisibleForTesting;
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import com.google.errorprone.annotations.DoNotCall;
29 import com.google.errorprone.annotations.DoNotMock;
30 import com.google.errorprone.annotations.concurrent.LazyInit;
31 import com.google.j2objc.annotations.RetainedWith;
32 import com.google.j2objc.annotations.WeakOuter;
33 import java.io.Serializable;
34 import java.util.AbstractMap;
35 import java.util.Arrays;
36 import java.util.Collection;
37 import java.util.Collections;
38 import java.util.Comparator;
39 import java.util.EnumMap;
40 import java.util.Iterator;
41 import java.util.Map;
42 import java.util.SortedMap;
43 import java.util.Spliterator;
44 import java.util.Spliterators;
45 import java.util.function.BiFunction;
46 import java.util.function.BinaryOperator;
47 import java.util.function.Function;
48 import java.util.stream.Collector;
49 import java.util.stream.Collectors;
50 import org.checkerframework.checker.nullness.qual.Nullable;
51
52 /**
53 * A {@link Map} whose contents will never change, with many other important properties detailed at
54 * {@link ImmutableCollection}.
55 *
56 * <p>See the Guava User Guide article on <a href=
57 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
58 *
59 * @author Jesse Wilson
60 * @author Kevin Bourrillion
61 * @since 2.0
62 */
63 @DoNotMock("Use ImmutableMap.of or another implementation")
64 @GwtCompatible(serializable = true, emulated = true)
65 @SuppressWarnings("serial") // we're overriding default serialization
66 public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable {
67
68 /**
69 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
70 * and values are the result of applying the provided mapping functions to the input elements.
71 * Entries appear in the result {@code ImmutableMap} in encounter order.
72 *
73 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}, an {@code
74 * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
75 * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
76 * throws an {@code IllegalStateException}.)
77 *
78 * @since 21.0
79 */
80 public static <T, K, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
81 Function<? super T, ? extends K> keyFunction,
82 Function<? super T, ? extends V> valueFunction) {
83 return CollectCollectors.toImmutableMap(keyFunction, valueFunction);
84 }
85
86 /**
87 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys
88 * and values are the result of applying the provided mapping functions to the input elements.
89 *
90 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}), the
91 * values are merged using the specified merging function. Entries will appear in the encounter
92 * order of the first occurrence of the key.
93 *
94 * @since 21.0
95 */
96 public static <T, K, V> Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
97 Function<? super T, ? extends K> keyFunction,
98 Function<? super T, ? extends V> valueFunction,
99 BinaryOperator<V> mergeFunction) {
100 return CollectCollectors.toImmutableMap(keyFunction, valueFunction, mergeFunction);
101 }
102
103 /**
104 * Returns the empty map. This map behaves and performs comparably to {@link
105 * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your
106 * code.
107 *
108 * <p><b>Performance note:</b> the instance returned is a singleton.
109 */
110 @SuppressWarnings("unchecked")
111 public static <K, V> ImmutableMap<K, V> of() {
112 return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY;
113 }
114
115 /**
116 * Returns an immutable map containing a single entry. This map behaves and performs comparably to
117 * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable
118 * mainly for consistency and maintainability of your code.
119 */
120 public static <K, V> ImmutableMap<K, V> of(K k1, V v1) {
121 return ImmutableBiMap.of(k1, v1);
122 }
123
124 /**
125 * Returns an immutable map containing the given entries, in order.
126 *
127 * @throws IllegalArgumentException if duplicate keys are provided
128 */
129 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2) {
130 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2));
131 }
132
133 /**
134 * Returns an immutable map containing the given entries, in order.
135 *
136 * @throws IllegalArgumentException if duplicate keys are provided
137 */
138 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
139 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
140 }
141
142 /**
143 * Returns an immutable map containing the given entries, in order.
144 *
145 * @throws IllegalArgumentException if duplicate keys are provided
146 */
147 public static <K, V> ImmutableMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
148 return RegularImmutableMap.fromEntries(
149 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
150 }
151
152 /**
153 * Returns an immutable map containing the given entries, in order.
154 *
155 * @throws IllegalArgumentException if duplicate keys are provided
156 */
157 public static <K, V> ImmutableMap<K, V> of(
158 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
159 return RegularImmutableMap.fromEntries(
160 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
161 }
162
163 // looking for of() with > 5 entries? Use the builder instead.
164
165 /**
166 * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry
167 * with those values.
168 *
169 * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link
170 * UnsupportedOperationException}.
171 */
172 static <K, V> Entry<K, V> entryOf(K key, V value) {
173 checkEntryNotNull(key, value);
174 return new AbstractMap.SimpleImmutableEntry<>(key, value);
175 }
176
177 /**
178 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
179 * Builder} constructor.
180 */
181 public static <K, V> Builder<K, V> builder() {
182 return new Builder<>();
183 }
184
185 /**
186 * Returns a new builder, expecting the specified number of entries to be added.
187 *
188 * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link
189 * Builder#build} is called, the builder is likely to perform better than an unsized {@link
190 * #builder()} would have.
191 *
192 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
193 * but not exactly, the number of entries added to the builder.
194 *
195 * @since 23.1
196 */
197 @Beta
198 public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) {
199 checkNonnegative(expectedSize, "expectedSize");
200 return new Builder<>(expectedSize);
201 }
202
203 static void checkNoConflict(
204 boolean safe, String conflictDescription, Entry<?, ?> entry1, Entry<?, ?> entry2) {
205 if (!safe) {
206 throw conflictException(conflictDescription, entry1, entry2);
207 }
208 }
209
210 static IllegalArgumentException conflictException(
211 String conflictDescription, Object entry1, Object entry2) {
212 return new IllegalArgumentException(
213 "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2);
214 }
215
216 /**
217 * A builder for creating immutable map instances, especially {@code public static final} maps
218 * ("constant maps"). Example:
219 *
220 * <pre>{@code
221 * static final ImmutableMap<String, Integer> WORD_TO_INT =
222 * new ImmutableMap.Builder<String, Integer>()
223 * .put("one", 1)
224 * .put("two", 2)
225 * .put("three", 3)
226 * .build();
227 * }</pre>
228 *
229 * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more
230 * convenient.
231 *
232 * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they
233 * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the
234 * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the
235 * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect
236 * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to
237 * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to
238 * sort entries by value.
239 *
240 * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build
241 * multiple maps in series. Each map is a superset of the maps created before it.
242 *
243 * @since 2.0
244 */
245 @DoNotMock
246 public static class Builder<K, V> {
247 @Nullable Comparator<? super V> valueComparator;
248 Entry<K, V>[] entries;
249 int size;
250 boolean entriesUsed;
251
252 /**
253 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
254 * ImmutableMap#builder}.
255 */
256 public Builder() {
257 this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY);
258 }
259
260 @SuppressWarnings("unchecked")
261 Builder(int initialCapacity) {
262 this.entries = new Entry[initialCapacity];
263 this.size = 0;
264 this.entriesUsed = false;
265 }
266
267 private void ensureCapacity(int minCapacity) {
268 if (minCapacity > entries.length) {
269 entries =
270 Arrays.copyOf(
271 entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity));
272 entriesUsed = false;
273 }
274 }
275
276 /**
277 * Associates {@code key} with {@code value} in the built map. Duplicate keys are not allowed,
278 * and will cause {@link #build} to fail.
279 */
280 @CanIgnoreReturnValue
281 public Builder<K, V> put(K key, V value) {
282 ensureCapacity(size + 1);
283 Entry<K, V> entry = entryOf(key, value);
284 // don't inline this: we want to fail atomically if key or value is null
285 entries[size++] = entry;
286 return this;
287 }
288
289 /**
290 * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys are
291 * not allowed, and will cause {@link #build} to fail.
292 *
293 * @since 11.0
294 */
295 @CanIgnoreReturnValue
296 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
297 return put(entry.getKey(), entry.getValue());
298 }
299
300 /**
301 * Associates all of the given map's keys and values in the built map. Duplicate keys are not
302 * allowed, and will cause {@link #build} to fail.
303 *
304 * @throws NullPointerException if any key or value in {@code map} is null
305 */
306 @CanIgnoreReturnValue
307 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
308 return putAll(map.entrySet());
309 }
310
311 /**
312 * Adds all of the given entries to the built map. Duplicate keys are not allowed, and will
313 * cause {@link #build} to fail.
314 *
315 * @throws NullPointerException if any key, value, or entry is null
316 * @since 19.0
317 */
318 @CanIgnoreReturnValue
319 @Beta
320 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
321 if (entries instanceof Collection) {
322 ensureCapacity(size + ((Collection<?>) entries).size());
323 }
324 for (Entry<? extends K, ? extends V> entry : entries) {
325 put(entry);
326 }
327 return this;
328 }
329
330 /**
331 * Configures this {@code Builder} to order entries by value according to the specified
332 * comparator.
333 *
334 * <p>The sort order is stable, that is, if two entries have values that compare as equivalent,
335 * the entry that was inserted first will be first in the built map's iteration order.
336 *
337 * @throws IllegalStateException if this method was already called
338 * @since 19.0
339 */
340 @CanIgnoreReturnValue
341 @Beta
342 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
343 checkState(this.valueComparator == null, "valueComparator was already set");
344 this.valueComparator = checkNotNull(valueComparator, "valueComparator");
345 return this;
346 }
347
348 @CanIgnoreReturnValue
349 Builder<K, V> combine(Builder<K, V> other) {
350 checkNotNull(other);
351 ensureCapacity(this.size + other.size);
352 System.arraycopy(other.entries, 0, this.entries, this.size, other.size);
353 this.size += other.size;
354 return this;
355 }
356
357 /*
358 * TODO(kevinb): Should build() and the ImmutableBiMap & ImmutableSortedMap
359 * versions throw an IllegalStateException instead?
360 */
361
362 /**
363 * Returns a newly-created immutable map. The iteration order of the returned map is the order
364 * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was
365 * called, in which case entries are sorted by value.
366 *
367 * @throws IllegalArgumentException if duplicate keys were added
368 */
369 public ImmutableMap<K, V> build() {
370 /*
371 * If entries is full, or if hash flooding is detected, then this implementation may end up
372 * using the entries array directly and writing over the entry objects with non-terminal
373 * entries, but this is safe; if this Builder is used further, it will grow the entries array
374 * (so it can't affect the original array), and future build() calls will always copy any
375 * entry objects that cannot be safely reused.
376 */
377 if (valueComparator != null) {
378 if (entriesUsed) {
379 entries = Arrays.copyOf(entries, size);
380 }
381 Arrays.sort(
382 entries, 0, size, Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
383 }
384 switch (size) {
385 case 0:
386 return of();
387 case 1:
388 return of(entries[0].getKey(), entries[0].getValue());
389 default:
390 entriesUsed = true;
391 return RegularImmutableMap.fromEntryArray(size, entries);
392 }
393 }
394
395 @VisibleForTesting // only for testing JDK backed implementation
396 ImmutableMap<K, V> buildJdkBacked() {
397 checkState(
398 valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator");
399 switch (size) {
400 case 0:
401 return of();
402 case 1:
403 return of(entries[0].getKey(), entries[0].getValue());
404 default:
405 entriesUsed = true;
406 return JdkBackedImmutableMap.create(size, entries);
407 }
408 }
409 }
410
411 /**
412 * Returns an immutable map containing the same entries as {@code map}. The returned map iterates
413 * over entries in the same order as the {@code entrySet} of the original map. If {@code map}
414 * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
415 * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
416 *
417 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
418 * safe to do so. The exact circumstances under which a copy will or will not be performed are
419 * undocumented and subject to change.
420 *
421 * @throws NullPointerException if any key or value in {@code map} is null
422 */
423 public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
424 if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) {
425 @SuppressWarnings("unchecked") // safe since map is not writable
426 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map;
427 if (!kvMap.isPartialView()) {
428 return kvMap;
429 }
430 } else if (map instanceof EnumMap) {
431 @SuppressWarnings("unchecked") // safe since map is not writable
432 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) copyOfEnumMap((EnumMap<?, ?>) map);
433 return kvMap;
434 }
435 return copyOf(map.entrySet());
436 }
437
438 /**
439 * Returns an immutable map containing the specified entries. The returned map iterates over
440 * entries in the same order as the original iterable.
441 *
442 * @throws NullPointerException if any key, value, or entry is null
443 * @throws IllegalArgumentException if two entries have the same key
444 * @since 19.0
445 */
446 @Beta
447 public static <K, V> ImmutableMap<K, V> copyOf(
448 Iterable<? extends Entry<? extends K, ? extends V>> entries) {
449 @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
450 Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
451 switch (entryArray.length) {
452 case 0:
453 return of();
454 case 1:
455 Entry<K, V> onlyEntry = entryArray[0];
456 return of(onlyEntry.getKey(), onlyEntry.getValue());
457 default:
458 /*
459 * The current implementation will end up using entryArray directly, though it will write
460 * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
461 */
462 return RegularImmutableMap.fromEntries(entryArray);
463 }
464 }
465
466 private static <K extends Enum<K>, V> ImmutableMap<K, V> copyOfEnumMap(
467 EnumMap<K, ? extends V> original) {
468 EnumMap<K, V> copy = new EnumMap<>(original);
469 for (Entry<?, ?> entry : copy.entrySet()) {
470 checkEntryNotNull(entry.getKey(), entry.getValue());
471 }
472 return ImmutableEnumMap.asImmutable(copy);
473 }
474
475 static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0];
476
477 abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> {
478 abstract UnmodifiableIterator<Entry<K, V>> entryIterator();
479
480 Spliterator<Entry<K, V>> entrySpliterator() {
481 return Spliterators.spliterator(
482 entryIterator(),
483 size(),
484 Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED);
485 }
486
487 @Override
488 ImmutableSet<K> createKeySet() {
489 return new ImmutableMapKeySet<>(this);
490 }
491
492 @Override
493 ImmutableSet<Entry<K, V>> createEntrySet() {
494 class EntrySetImpl extends ImmutableMapEntrySet<K, V> {
495 @Override
496 ImmutableMap<K, V> map() {
497 return IteratorBasedImmutableMap.this;
498 }
499
500 @Override
501 public UnmodifiableIterator<Entry<K, V>> iterator() {
502 return entryIterator();
503 }
504 }
505 return new EntrySetImpl();
506 }
507
508 @Override
509 ImmutableCollection<V> createValues() {
510 return new ImmutableMapValues<>(this);
511 }
512 }
513
514 ImmutableMap() {}
515
516 /**
517 * Guaranteed to throw an exception and leave the map unmodified.
518 *
519 * @throws UnsupportedOperationException always
520 * @deprecated Unsupported operation.
521 */
522 @CanIgnoreReturnValue
523 @Deprecated
524 @Override
525 @DoNotCall("Always throws UnsupportedOperationException")
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 @DoNotCall("Always throws UnsupportedOperationException")
540 public final V putIfAbsent(K key, V value) {
541 throw new UnsupportedOperationException();
542 }
543
544 /**
545 * Guaranteed to throw an exception and leave the map unmodified.
546 *
547 * @throws UnsupportedOperationException always
548 * @deprecated Unsupported operation.
549 */
550 @Deprecated
551 @Override
552 @DoNotCall("Always throws UnsupportedOperationException")
553 public final boolean replace(K key, V oldValue, V newValue) {
554 throw new UnsupportedOperationException();
555 }
556
557 /**
558 * Guaranteed to throw an exception and leave the map unmodified.
559 *
560 * @throws UnsupportedOperationException always
561 * @deprecated Unsupported operation.
562 */
563 @Deprecated
564 @Override
565 @DoNotCall("Always throws UnsupportedOperationException")
566 public final V replace(K key, V value) {
567 throw new UnsupportedOperationException();
568 }
569
570 /**
571 * Guaranteed to throw an exception and leave the map unmodified.
572 *
573 * @throws UnsupportedOperationException always
574 * @deprecated Unsupported operation.
575 */
576 @Deprecated
577 @Override
578 @DoNotCall("Always throws UnsupportedOperationException")
579 public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
580 throw new UnsupportedOperationException();
581 }
582
583 /**
584 * Guaranteed to throw an exception and leave the map unmodified.
585 *
586 * @throws UnsupportedOperationException always
587 * @deprecated Unsupported operation.
588 */
589 @Deprecated
590 @Override
591 @DoNotCall("Always throws UnsupportedOperationException")
592 public final V computeIfPresent(
593 K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
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 @DoNotCall("Always throws UnsupportedOperationException")
606 public final V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
607 throw new UnsupportedOperationException();
608 }
609
610 /**
611 * Guaranteed to throw an exception and leave the map unmodified.
612 *
613 * @throws UnsupportedOperationException always
614 * @deprecated Unsupported operation.
615 */
616 @Deprecated
617 @Override
618 @DoNotCall("Always throws UnsupportedOperationException")
619 public final V merge(
620 K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
621 throw new UnsupportedOperationException();
622 }
623
624 /**
625 * Guaranteed to throw an exception and leave the map unmodified.
626 *
627 * @throws UnsupportedOperationException always
628 * @deprecated Unsupported operation.
629 */
630 @Deprecated
631 @Override
632 @DoNotCall("Always throws UnsupportedOperationException")
633 public final void putAll(Map<? extends K, ? extends V> map) {
634 throw new UnsupportedOperationException();
635 }
636
637 /**
638 * Guaranteed to throw an exception and leave the map unmodified.
639 *
640 * @throws UnsupportedOperationException always
641 * @deprecated Unsupported operation.
642 */
643 @Deprecated
644 @Override
645 @DoNotCall("Always throws UnsupportedOperationException")
646 public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
647 throw new UnsupportedOperationException();
648 }
649
650 /**
651 * Guaranteed to throw an exception and leave the map unmodified.
652 *
653 * @throws UnsupportedOperationException always
654 * @deprecated Unsupported operation.
655 */
656 @Deprecated
657 @Override
658 @DoNotCall("Always throws UnsupportedOperationException")
659 public final V remove(Object o) {
660 throw new UnsupportedOperationException();
661 }
662
663 /**
664 * Guaranteed to throw an exception and leave the map unmodified.
665 *
666 * @throws UnsupportedOperationException always
667 * @deprecated Unsupported operation.
668 */
669 @Deprecated
670 @Override
671 @DoNotCall("Always throws UnsupportedOperationException")
672 public final boolean remove(Object key, Object value) {
673 throw new UnsupportedOperationException();
674 }
675
676 /**
677 * Guaranteed to throw an exception and leave the map unmodified.
678 *
679 * @throws UnsupportedOperationException always
680 * @deprecated Unsupported operation.
681 */
682 @Deprecated
683 @Override
684 @DoNotCall("Always throws UnsupportedOperationException")
685 public final void clear() {
686 throw new UnsupportedOperationException();
687 }
688
689 @Override
690 public boolean isEmpty() {
691 return size() == 0;
692 }
693
694 @Override
695 public boolean containsKey(@Nullable Object key) {
696 return get(key) != null;
697 }
698
699 @Override
700 public boolean containsValue(@Nullable Object value) {
701 return values().contains(value);
702 }
703
704 // Overriding to mark it Nullable
705 @Override
706 public abstract V get(@Nullable Object key);
707
708 /**
709 * @since 21.0 (but only since 23.5 in the Android <a
710 * href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>).
711 * Note, however, that Java 8 users can call this method with any version and flavor of Guava.
712 */
713 @Override
714 public final V getOrDefault(@Nullable Object key, @Nullable V defaultValue) {
715 V result = get(key);
716 return (result != null) ? result : defaultValue;
717 }
718
719 @LazyInit @RetainedWith private transient ImmutableSet<Entry<K, V>> entrySet;
720
721 /**
722 * Returns an immutable set of the mappings in this map. The iteration order is specified by the
723 * method used to create this map. Typically, this is insertion order.
724 */
725 @Override
726 public ImmutableSet<Entry<K, V>> entrySet() {
727 ImmutableSet<Entry<K, V>> result = entrySet;
728 return (result == null) ? entrySet = createEntrySet() : result;
729 }
730
731 abstract ImmutableSet<Entry<K, V>> createEntrySet();
732
733 @LazyInit @RetainedWith private transient ImmutableSet<K> keySet;
734
735 /**
736 * Returns an immutable set of the keys in this map, in the same order that they appear in {@link
737 * #entrySet}.
738 */
739 @Override
740 public ImmutableSet<K> keySet() {
741 ImmutableSet<K> result = keySet;
742 return (result == null) ? keySet = createKeySet() : result;
743 }
744
745 /*
746 * This could have a good default implementation of return new ImmutableKeySet<K, V>(this),
747 * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap
748 * overrides it.
749 */
750 abstract ImmutableSet<K> createKeySet();
751
752 UnmodifiableIterator<K> keyIterator() {
753 final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator();
754 return new UnmodifiableIterator<K>() {
755 @Override
756 public boolean hasNext() {
757 return entryIterator.hasNext();
758 }
759
760 @Override
761 public K next() {
762 return entryIterator.next().getKey();
763 }
764 };
765 }
766
767 Spliterator<K> keySpliterator() {
768 return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey);
769 }
770
771 @LazyInit @RetainedWith private transient ImmutableCollection<V> values;
772
773 /**
774 * Returns an immutable collection of the values in this map, in the same order that they appear
775 * in {@link #entrySet}.
776 */
777 @Override
778 public ImmutableCollection<V> values() {
779 ImmutableCollection<V> result = values;
780 return (result == null) ? values = createValues() : result;
781 }
782
783 /*
784 * This could have a good default implementation of {@code return new
785 * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default
786 * when RegularImmutableMap overrides it.
787 */
788 abstract ImmutableCollection<V> createValues();
789
790 // cached so that this.multimapView().inverse() only computes inverse once
791 @LazyInit private transient ImmutableSetMultimap<K, V> multimapView;
792
793 /**
794 * Returns a multimap view of the map.
795 *
796 * @since 14.0
797 */
798 public ImmutableSetMultimap<K, V> asMultimap() {
799 if (isEmpty()) {
800 return ImmutableSetMultimap.of();
801 }
802 ImmutableSetMultimap<K, V> result = multimapView;
803 return (result == null)
804 ? (multimapView =
805 new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null))
806 : result;
807 }
808
809 @WeakOuter
810 private final class MapViewOfValuesAsSingletonSets
811 extends IteratorBasedImmutableMap<K, ImmutableSet<V>> {
812
813 @Override
814 public int size() {
815 return ImmutableMap.this.size();
816 }
817
818 @Override
819 ImmutableSet<K> createKeySet() {
820 return ImmutableMap.this.keySet();
821 }
822
823 @Override
824 public boolean containsKey(@Nullable Object key) {
825 return ImmutableMap.this.containsKey(key);
826 }
827
828 @Override
829 public ImmutableSet<V> get(@Nullable Object key) {
830 V outerValue = ImmutableMap.this.get(key);
831 return (outerValue == null) ? null : ImmutableSet.of(outerValue);
832 }
833
834 @Override
835 boolean isPartialView() {
836 return ImmutableMap.this.isPartialView();
837 }
838
839 @Override
840 public int hashCode() {
841 // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same
842 return ImmutableMap.this.hashCode();
843 }
844
845 @Override
846 boolean isHashCodeFast() {
847 return ImmutableMap.this.isHashCodeFast();
848 }
849
850 @Override
851 UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() {
852 final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator();
853 return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() {
854 @Override
855 public boolean hasNext() {
856 return backingIterator.hasNext();
857 }
858
859 @Override
860 public Entry<K, ImmutableSet<V>> next() {
861 final Entry<K, V> backingEntry = backingIterator.next();
862 return new AbstractMapEntry<K, ImmutableSet<V>>() {
863 @Override
864 public K getKey() {
865 return backingEntry.getKey();
866 }
867
868 @Override
869 public ImmutableSet<V> getValue() {
870 return ImmutableSet.of(backingEntry.getValue());
871 }
872 };
873 }
874 };
875 }
876 }
877
878 @Override
879 public boolean equals(@Nullable Object object) {
880 return Maps.equalsImpl(this, object);
881 }
882
883 abstract boolean isPartialView();
884
885 @Override
886 public int hashCode() {
887 return Sets.hashCodeImpl(entrySet());
888 }
889
890 boolean isHashCodeFast() {
891 return false;
892 }
893
894 @Override
895 public String toString() {
896 return Maps.toStringImpl(this);
897 }
898
899 /**
900 * Serialized type for all ImmutableMap instances. It captures the logical contents and they are
901 * reconstructed using public factory methods. This ensures that the implementation types remain
902 * as implementation details.
903 */
904 static class SerializedForm<K, V> implements Serializable {
905 // This object retains references to collections returned by keySet() and value(). This saves
906 // bytes when the both the map and its keySet or value collection are written to the same
907 // instance of ObjectOutputStream.
908
909 // TODO(b/160980469): remove support for the old serialization format after some time
910 private static final boolean USE_LEGACY_SERIALIZATION = true;
911
912 private final Object keys;
913 private final Object values;
914
915 SerializedForm(ImmutableMap<K, V> map) {
916 if (USE_LEGACY_SERIALIZATION) {
917 Object[] keys = new Object[map.size()];
918 Object[] values = new Object[map.size()];
919 int i = 0;
920 for (Entry<?, ?> entry : map.entrySet()) {
921 keys[i] = entry.getKey();
922 values[i] = entry.getValue();
923 i++;
924 }
925 this.keys = keys;
926 this.values = values;
927 return;
928 }
929 this.keys = map.keySet();
930 this.values = map.values();
931 }
932
933 @SuppressWarnings("unchecked")
934 final Object readResolve() {
935 if (!(this.keys instanceof ImmutableSet)) {
936 return legacyReadResolve();
937 }
938
939 ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys;
940 ImmutableCollection<V> values = (ImmutableCollection<V>) this.values;
941
942 Builder<K, V> builder = makeBuilder(keySet.size());
943
944 UnmodifiableIterator<K> keyIter = keySet.iterator();
945 UnmodifiableIterator<V> valueIter = values.iterator();
946
947 while (keyIter.hasNext()) {
948 builder.put(keyIter.next(), valueIter.next());
949 }
950
951 return builder.build();
952 }
953
954 @SuppressWarnings("unchecked")
955 final Object legacyReadResolve() {
956 K[] keys = (K[]) this.keys;
957 V[] values = (V[]) this.values;
958
959 Builder<K, V> builder = makeBuilder(keys.length);
960
961 for (int i = 0; i < keys.length; i++) {
962 builder.put(keys[i], values[i]);
963 }
964 return builder.build();
965 }
966
967 /**
968 * Returns a builder that builds the unserialized type. Subclasses should override this method.
969 */
970 Builder<K, V> makeBuilder(int size) {
971 return new Builder<>(size);
972 }
973
974 private static final long serialVersionUID = 0;
975 }
976
977 /**
978 * Returns a serializable form of this object. Non-public subclasses should not override this
979 * method. Publicly-accessible subclasses must override this method and should return a subclass
980 * of SerializedForm whose readResolve() method returns objects of the subclass type.
981 */
982 Object writeReplace() {
983 return new SerializedForm<>(this);
984 }
985 }