001/* 002 * Copyright (C) 2008 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.base.Preconditions.checkState; 021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 022import static com.google.common.collect.CollectPreconditions.checkNonnegative; 023import static java.util.Objects.requireNonNull; 024 025import com.google.common.annotations.Beta; 026import com.google.common.annotations.GwtCompatible; 027import com.google.common.annotations.VisibleForTesting; 028import com.google.errorprone.annotations.CanIgnoreReturnValue; 029import com.google.errorprone.annotations.DoNotCall; 030import com.google.errorprone.annotations.DoNotMock; 031import com.google.errorprone.annotations.concurrent.LazyInit; 032import com.google.j2objc.annotations.RetainedWith; 033import com.google.j2objc.annotations.WeakOuter; 034import java.io.InvalidObjectException; 035import java.io.ObjectInputStream; 036import java.io.Serializable; 037import java.util.Arrays; 038import java.util.BitSet; 039import java.util.Collection; 040import java.util.Collections; 041import java.util.Comparator; 042import java.util.EnumMap; 043import java.util.HashSet; 044import java.util.Iterator; 045import java.util.Map; 046import java.util.Set; 047import java.util.SortedMap; 048import java.util.Spliterator; 049import java.util.Spliterators; 050import java.util.function.BiFunction; 051import java.util.function.BinaryOperator; 052import java.util.function.Function; 053import java.util.stream.Collector; 054import java.util.stream.Collectors; 055import javax.annotation.CheckForNull; 056import org.checkerframework.checker.nullness.qual.Nullable; 057 058/** 059 * A {@link Map} whose contents will never change, with many other important properties detailed at 060 * {@link ImmutableCollection}. 061 * 062 * <p>See the Guava User Guide article on <a href= 063 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>. 064 * 065 * @author Jesse Wilson 066 * @author Kevin Bourrillion 067 * @since 2.0 068 */ 069@DoNotMock("Use ImmutableMap.of or another implementation") 070@GwtCompatible(serializable = true, emulated = true) 071@SuppressWarnings("serial") // we're overriding default serialization 072@ElementTypesAreNonnullByDefault 073public abstract class ImmutableMap<K, V> implements Map<K, V>, Serializable { 074 075 /** 076 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys 077 * and values are the result of applying the provided mapping functions to the input elements. 078 * Entries appear in the result {@code ImmutableMap} in encounter order. 079 * 080 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}, an {@code 081 * IllegalArgumentException} is thrown when the collection operation is performed. (This differs 082 * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which 083 * throws an {@code IllegalStateException}.) 084 * 085 * @since 21.0 086 */ 087 public static <T extends @Nullable Object, K, V> 088 Collector<T, ?, ImmutableMap<K, V>> toImmutableMap( 089 Function<? super T, ? extends K> keyFunction, 090 Function<? super T, ? extends V> valueFunction) { 091 return CollectCollectors.toImmutableMap(keyFunction, valueFunction); 092 } 093 094 /** 095 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableMap} whose keys 096 * and values are the result of applying the provided mapping functions to the input elements. 097 * 098 * <p>If the mapped keys contain duplicates (according to {@link Object#equals(Object)}), the 099 * values are merged using the specified merging function. Entries will appear in the encounter 100 * order of the first occurrence of the key. 101 * 102 * @since 21.0 103 */ 104 public static <T extends @Nullable Object, K, V> 105 Collector<T, ?, ImmutableMap<K, V>> toImmutableMap( 106 Function<? super T, ? extends K> keyFunction, 107 Function<? super T, ? extends V> valueFunction, 108 BinaryOperator<V> mergeFunction) { 109 return CollectCollectors.toImmutableMap(keyFunction, valueFunction, mergeFunction); 110 } 111 112 /** 113 * Returns the empty map. This map behaves and performs comparably to {@link 114 * Collections#emptyMap}, and is preferable mainly for consistency and maintainability of your 115 * code. 116 * 117 * <p><b>Performance note:</b> the instance returned is a singleton. 118 */ 119 @SuppressWarnings("unchecked") 120 public static <K, V> ImmutableMap<K, V> of() { 121 return (ImmutableMap<K, V>) RegularImmutableMap.EMPTY; 122 } 123 124 /** 125 * Returns an immutable map containing a single entry. This map behaves and performs comparably to 126 * {@link Collections#singletonMap} but will not accept a null key or value. It is preferable 127 * mainly for consistency and maintainability of your code. 128 */ 129 public static <K, V> ImmutableMap<K, V> of(K k1, V v1) { 130 return ImmutableBiMap.of(k1, v1); 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) { 139 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2)); 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) { 148 return RegularImmutableMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 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(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 157 return RegularImmutableMap.fromEntries( 158 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 159 } 160 161 /** 162 * Returns an immutable map containing the given entries, in order. 163 * 164 * @throws IllegalArgumentException if duplicate keys are provided 165 */ 166 public static <K, V> ImmutableMap<K, V> of( 167 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 168 return RegularImmutableMap.fromEntries( 169 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 170 } 171 172 /** 173 * Returns an immutable map containing the given entries, in order. 174 * 175 * @throws IllegalArgumentException if duplicate keys are provided 176 * @since 31.0 177 */ 178 public static <K, V> ImmutableMap<K, V> of( 179 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) { 180 return RegularImmutableMap.fromEntries( 181 entryOf(k1, v1), 182 entryOf(k2, v2), 183 entryOf(k3, v3), 184 entryOf(k4, v4), 185 entryOf(k5, v5), 186 entryOf(k6, v6)); 187 } 188 189 /** 190 * Returns an immutable map containing the given entries, in order. 191 * 192 * @throws IllegalArgumentException if duplicate keys are provided 193 * @since 31.0 194 */ 195 public static <K, V> ImmutableMap<K, V> of( 196 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6, K k7, V v7) { 197 return RegularImmutableMap.fromEntries( 198 entryOf(k1, v1), 199 entryOf(k2, v2), 200 entryOf(k3, v3), 201 entryOf(k4, v4), 202 entryOf(k5, v5), 203 entryOf(k6, v6), 204 entryOf(k7, v7)); 205 } 206 207 /** 208 * Returns an immutable map containing the given entries, in order. 209 * 210 * @throws IllegalArgumentException if duplicate keys are provided 211 * @since 31.0 212 */ 213 public static <K, V> ImmutableMap<K, V> of( 214 K k1, 215 V v1, 216 K k2, 217 V v2, 218 K k3, 219 V v3, 220 K k4, 221 V v4, 222 K k5, 223 V v5, 224 K k6, 225 V v6, 226 K k7, 227 V v7, 228 K k8, 229 V v8) { 230 return RegularImmutableMap.fromEntries( 231 entryOf(k1, v1), 232 entryOf(k2, v2), 233 entryOf(k3, v3), 234 entryOf(k4, v4), 235 entryOf(k5, v5), 236 entryOf(k6, v6), 237 entryOf(k7, v7), 238 entryOf(k8, v8)); 239 } 240 241 /** 242 * Returns an immutable map containing the given entries, in order. 243 * 244 * @throws IllegalArgumentException if duplicate keys are provided 245 * @since 31.0 246 */ 247 public static <K, V> ImmutableMap<K, V> of( 248 K k1, 249 V v1, 250 K k2, 251 V v2, 252 K k3, 253 V v3, 254 K k4, 255 V v4, 256 K k5, 257 V v5, 258 K k6, 259 V v6, 260 K k7, 261 V v7, 262 K k8, 263 V v8, 264 K k9, 265 V v9) { 266 return RegularImmutableMap.fromEntries( 267 entryOf(k1, v1), 268 entryOf(k2, v2), 269 entryOf(k3, v3), 270 entryOf(k4, v4), 271 entryOf(k5, v5), 272 entryOf(k6, v6), 273 entryOf(k7, v7), 274 entryOf(k8, v8), 275 entryOf(k9, v9)); 276 } 277 278 /** 279 * Returns an immutable map containing the given entries, in order. 280 * 281 * @throws IllegalArgumentException if duplicate keys are provided 282 * @since 31.0 283 */ 284 public static <K, V> ImmutableMap<K, V> of( 285 K k1, 286 V v1, 287 K k2, 288 V v2, 289 K k3, 290 V v3, 291 K k4, 292 V v4, 293 K k5, 294 V v5, 295 K k6, 296 V v6, 297 K k7, 298 V v7, 299 K k8, 300 V v8, 301 K k9, 302 V v9, 303 K k10, 304 V v10) { 305 return RegularImmutableMap.fromEntries( 306 entryOf(k1, v1), 307 entryOf(k2, v2), 308 entryOf(k3, v3), 309 entryOf(k4, v4), 310 entryOf(k5, v5), 311 entryOf(k6, v6), 312 entryOf(k7, v7), 313 entryOf(k8, v8), 314 entryOf(k9, v9), 315 entryOf(k10, v10)); 316 } 317 318 // looking for of() with > 10 entries? Use the builder or ofEntries instead. 319 320 /** 321 * Returns an immutable map containing the given entries, in order. 322 * 323 * @throws IllegalArgumentException if duplicate keys are provided 324 * @since 31.0 325 */ 326 @SafeVarargs 327 public static <K, V> ImmutableMap<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) { 328 @SuppressWarnings("unchecked") // we will only ever read these 329 Entry<K, V>[] entries2 = (Entry<K, V>[]) entries; 330 return RegularImmutableMap.fromEntries(entries2); 331 } 332 333 /** 334 * Verifies that {@code key} and {@code value} are non-null, and returns a new immutable entry 335 * with those values. 336 * 337 * <p>A call to {@link Entry#setValue} on the returned entry will always throw {@link 338 * UnsupportedOperationException}. 339 */ 340 static <K, V> Entry<K, V> entryOf(K key, V value) { 341 return new ImmutableMapEntry<>(key, value); 342 } 343 344 /** 345 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 346 * Builder} constructor. 347 */ 348 public static <K, V> Builder<K, V> builder() { 349 return new Builder<>(); 350 } 351 352 /** 353 * Returns a new builder, expecting the specified number of entries to be added. 354 * 355 * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link 356 * Builder#build} is called, the builder is likely to perform better than an unsized {@link 357 * #builder()} would have. 358 * 359 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 360 * but not exactly, the number of entries added to the builder. 361 * 362 * @since 23.1 363 */ 364 @Beta 365 public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) { 366 checkNonnegative(expectedSize, "expectedSize"); 367 return new Builder<>(expectedSize); 368 } 369 370 static void checkNoConflict( 371 boolean safe, String conflictDescription, Object entry1, Object entry2) { 372 if (!safe) { 373 throw conflictException(conflictDescription, entry1, entry2); 374 } 375 } 376 377 static IllegalArgumentException conflictException( 378 String conflictDescription, Object entry1, Object entry2) { 379 return new IllegalArgumentException( 380 "Multiple entries with same " + conflictDescription + ": " + entry1 + " and " + entry2); 381 } 382 383 /** 384 * A builder for creating immutable map instances, especially {@code public static final} maps 385 * ("constant maps"). Example: 386 * 387 * <pre>{@code 388 * static final ImmutableMap<String, Integer> WORD_TO_INT = 389 * new ImmutableMap.Builder<String, Integer>() 390 * .put("one", 1) 391 * .put("two", 2) 392 * .put("three", 3) 393 * .buildOrThrow(); 394 * }</pre> 395 * 396 * <p>For <i>small</i> immutable maps, the {@code ImmutableMap.of()} methods are even more 397 * convenient. 398 * 399 * <p>By default, a {@code Builder} will generate maps that iterate over entries in the order they 400 * were inserted into the builder, equivalently to {@code LinkedHashMap}. For example, in the 401 * above example, {@code WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the 402 * order {@code "one"=1, "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect 403 * the same order. If you want a different order, consider using {@link ImmutableSortedMap} to 404 * sort by keys, or call {@link #orderEntriesByValue(Comparator)}, which changes this builder to 405 * sort entries by value. 406 * 407 * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to 408 * build multiple maps in series. Each map is a superset of the maps created before it. 409 * 410 * @since 2.0 411 */ 412 @DoNotMock 413 public static class Builder<K, V> { 414 @CheckForNull Comparator<? super V> valueComparator; 415 @Nullable Entry<K, V>[] entries; 416 int size; 417 boolean entriesUsed; 418 419 /** 420 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 421 * ImmutableMap#builder}. 422 */ 423 public Builder() { 424 this(ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY); 425 } 426 427 @SuppressWarnings({"unchecked", "rawtypes"}) 428 Builder(int initialCapacity) { 429 this.entries = new @Nullable Entry[initialCapacity]; 430 this.size = 0; 431 this.entriesUsed = false; 432 } 433 434 private void ensureCapacity(int minCapacity) { 435 if (minCapacity > entries.length) { 436 entries = 437 Arrays.copyOf( 438 entries, ImmutableCollection.Builder.expandedCapacity(entries.length, minCapacity)); 439 entriesUsed = false; 440 } 441 } 442 443 /** 444 * Associates {@code key} with {@code value} in the built map. If the same key is put more than 445 * once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last 446 * value put for that key. 447 */ 448 @CanIgnoreReturnValue 449 public Builder<K, V> put(K key, V value) { 450 ensureCapacity(size + 1); 451 Entry<K, V> entry = entryOf(key, value); 452 // don't inline this: we want to fail atomically if key or value is null 453 entries[size++] = entry; 454 return this; 455 } 456 457 /** 458 * Adds the given {@code entry} to the map, making it immutable if necessary. If the same key is 459 * put more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will 460 * keep the last value put for that key. 461 * 462 * @since 11.0 463 */ 464 @CanIgnoreReturnValue 465 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 466 return put(entry.getKey(), entry.getValue()); 467 } 468 469 /** 470 * Associates all of the given map's keys and values in the built map. If the same key is put 471 * more than once, {@link #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep 472 * the last value put for that key. 473 * 474 * @throws NullPointerException if any key or value in {@code map} is null 475 */ 476 @CanIgnoreReturnValue 477 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 478 return putAll(map.entrySet()); 479 } 480 481 /** 482 * Adds all of the given entries to the built map. If the same key is put more than once, {@link 483 * #buildOrThrow} will fail, while {@link #buildKeepingLast} will keep the last value put for 484 * that key. 485 * 486 * @throws NullPointerException if any key, value, or entry is null 487 * @since 19.0 488 */ 489 @CanIgnoreReturnValue 490 @Beta 491 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 492 if (entries instanceof Collection) { 493 ensureCapacity(size + ((Collection<?>) entries).size()); 494 } 495 for (Entry<? extends K, ? extends V> entry : entries) { 496 put(entry); 497 } 498 return this; 499 } 500 501 /** 502 * Configures this {@code Builder} to order entries by value according to the specified 503 * comparator. 504 * 505 * <p>The sort order is stable, that is, if two entries have values that compare as equivalent, 506 * the entry that was inserted first will be first in the built map's iteration order. 507 * 508 * @throws IllegalStateException if this method was already called 509 * @since 19.0 510 */ 511 @CanIgnoreReturnValue 512 @Beta 513 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 514 checkState(this.valueComparator == null, "valueComparator was already set"); 515 this.valueComparator = checkNotNull(valueComparator, "valueComparator"); 516 return this; 517 } 518 519 @CanIgnoreReturnValue 520 Builder<K, V> combine(Builder<K, V> other) { 521 checkNotNull(other); 522 ensureCapacity(this.size + other.size); 523 System.arraycopy(other.entries, 0, this.entries, this.size, other.size); 524 this.size += other.size; 525 return this; 526 } 527 528 private ImmutableMap<K, V> build(boolean throwIfDuplicateKeys) { 529 /* 530 * If entries is full, or if hash flooding is detected, then this implementation may end up 531 * using the entries array directly and writing over the entry objects with non-terminal 532 * entries, but this is safe; if this Builder is used further, it will grow the entries array 533 * (so it can't affect the original array), and future build() calls will always copy any 534 * entry objects that cannot be safely reused. 535 */ 536 switch (size) { 537 case 0: 538 return of(); 539 case 1: 540 // requireNonNull is safe because the first `size` elements have been filled in. 541 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 542 return of(onlyEntry.getKey(), onlyEntry.getValue()); 543 default: 544 break; 545 } 546 // localEntries is an alias for the entries field, except if we end up removing duplicates in 547 // a copy of the entries array. Likewise, localSize is the same as size except in that case. 548 // It's possible to keep using this Builder after calling buildKeepingLast(), so we need to 549 // ensure that its state is not corrupted by removing duplicates that should cause a later 550 // buildOrThrow() to fail, or by changing the size. 551 @Nullable Entry<K, V>[] localEntries; 552 int localSize = size; 553 if (valueComparator == null) { 554 localEntries = entries; 555 } else { 556 if (entriesUsed) { 557 entries = Arrays.copyOf(entries, size); 558 } 559 localEntries = entries; 560 if (!throwIfDuplicateKeys) { 561 // We want to retain only the last-put value for any given key, before sorting. 562 // This could be improved, but orderEntriesByValue is rather rarely used anyway. 563 @SuppressWarnings("nullness") // entries 0..size-1 are non-null 564 Entry<K, V>[] nonNullEntries = (Entry<K, V>[]) localEntries; 565 localEntries = lastEntryForEachKey(nonNullEntries, size); 566 localSize = localEntries.length; 567 } 568 Arrays.sort( 569 localEntries, 570 0, 571 localSize, 572 Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction())); 573 } 574 entriesUsed = true; 575 return RegularImmutableMap.fromEntryArray(localSize, localEntries, throwIfDuplicateKeys); 576 } 577 578 /** 579 * Returns a newly-created immutable map. The iteration order of the returned map is the order 580 * in which entries were inserted into the builder, unless {@link #orderEntriesByValue} was 581 * called, in which case entries are sorted by value. 582 * 583 * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method 584 * will throw an exception if there are duplicate keys. The {@code build()} method will soon be 585 * deprecated. 586 * 587 * @throws IllegalArgumentException if duplicate keys were added 588 */ 589 public ImmutableMap<K, V> build() { 590 return buildOrThrow(); 591 } 592 593 /** 594 * Returns a newly-created immutable map, or throws an exception if any key was added more than 595 * once. The iteration order of the returned map is the order in which entries were inserted 596 * into the builder, unless {@link #orderEntriesByValue} was called, in which case entries are 597 * sorted by value. 598 * 599 * @throws IllegalArgumentException if duplicate keys were added 600 * @since 31.0 601 */ 602 public ImmutableMap<K, V> buildOrThrow() { 603 return build(true); 604 } 605 606 /** 607 * Returns a newly-created immutable map, using the last value for any key that was added more 608 * than once. The iteration order of the returned map is the order in which entries were 609 * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case 610 * entries are sorted by value. If a key was added more than once, it appears in iteration order 611 * based on the first time it was added, again unless {@link #orderEntriesByValue} was called. 612 * 613 * <p>In the current implementation, all values associated with a given key are stored in the 614 * {@code Builder} object, even though only one of them will be used in the built map. If there 615 * can be many repeated keys, it may be more space-efficient to use a {@link 616 * java.util.LinkedHashMap LinkedHashMap} and {@link ImmutableMap#copyOf(Map)} rather than 617 * {@code ImmutableMap.Builder}. 618 * 619 * @since 31.1 620 */ 621 public ImmutableMap<K, V> buildKeepingLast() { 622 return build(false); 623 } 624 625 @VisibleForTesting // only for testing JDK backed implementation 626 ImmutableMap<K, V> buildJdkBacked() { 627 checkState( 628 valueComparator == null, "buildJdkBacked is only for testing; can't use valueComparator"); 629 switch (size) { 630 case 0: 631 return of(); 632 case 1: 633 // requireNonNull is safe because the first `size` elements have been filled in. 634 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 635 return of(onlyEntry.getKey(), onlyEntry.getValue()); 636 default: 637 entriesUsed = true; 638 return JdkBackedImmutableMap.create(size, entries, /* throwIfDuplicateKeys= */ true); 639 } 640 } 641 642 private static <K, V> Entry<K, V>[] lastEntryForEachKey(Entry<K, V>[] entries, int size) { 643 Set<K> seen = new HashSet<>(); 644 BitSet dups = new BitSet(); // slots that are overridden by a later duplicate key 645 for (int i = size - 1; i >= 0; i--) { 646 if (!seen.add(entries[i].getKey())) { 647 dups.set(i); 648 } 649 } 650 if (dups.isEmpty()) { 651 return entries; 652 } 653 @SuppressWarnings({"rawtypes", "unchecked"}) 654 Entry<K, V>[] newEntries = new Entry[size - dups.cardinality()]; 655 for (int inI = 0, outI = 0; inI < size; inI++) { 656 if (!dups.get(inI)) { 657 newEntries[outI++] = entries[inI]; 658 } 659 } 660 return newEntries; 661 } 662 } 663 664 /** 665 * Returns an immutable map containing the same entries as {@code map}. The returned map iterates 666 * over entries in the same order as the {@code entrySet} of the original map. If {@code map} 667 * somehow contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose 668 * comparator is not <i>consistent with equals</i>), the results of this method are undefined. 669 * 670 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 671 * safe to do so. The exact circumstances under which a copy will or will not be performed are 672 * undocumented and subject to change. 673 * 674 * @throws NullPointerException if any key or value in {@code map} is null 675 */ 676 public static <K, V> ImmutableMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 677 if ((map instanceof ImmutableMap) && !(map instanceof SortedMap)) { 678 @SuppressWarnings("unchecked") // safe since map is not writable 679 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) map; 680 if (!kvMap.isPartialView()) { 681 return kvMap; 682 } 683 } else if (map instanceof EnumMap) { 684 @SuppressWarnings("unchecked") // safe since map is not writable 685 ImmutableMap<K, V> kvMap = (ImmutableMap<K, V>) copyOfEnumMap((EnumMap<?, ?>) map); 686 return kvMap; 687 } 688 return copyOf(map.entrySet()); 689 } 690 691 /** 692 * Returns an immutable map containing the specified entries. The returned map iterates over 693 * entries in the same order as the original iterable. 694 * 695 * @throws NullPointerException if any key, value, or entry is null 696 * @throws IllegalArgumentException if two entries have the same key 697 * @since 19.0 698 */ 699 @Beta 700 public static <K, V> ImmutableMap<K, V> copyOf( 701 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 702 @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant 703 Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 704 switch (entryArray.length) { 705 case 0: 706 return of(); 707 case 1: 708 // requireNonNull is safe because the first `size` elements have been filled in. 709 Entry<K, V> onlyEntry = requireNonNull(entryArray[0]); 710 return of(onlyEntry.getKey(), onlyEntry.getValue()); 711 default: 712 /* 713 * The current implementation will end up using entryArray directly, though it will write 714 * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray. 715 */ 716 return RegularImmutableMap.fromEntries(entryArray); 717 } 718 } 719 720 private static <K extends Enum<K>, V> ImmutableMap<K, V> copyOfEnumMap( 721 EnumMap<K, ? extends V> original) { 722 EnumMap<K, V> copy = new EnumMap<>(original); 723 for (Entry<K, V> entry : copy.entrySet()) { 724 checkEntryNotNull(entry.getKey(), entry.getValue()); 725 } 726 return ImmutableEnumMap.asImmutable(copy); 727 } 728 729 static final Entry<?, ?>[] EMPTY_ENTRY_ARRAY = new Entry<?, ?>[0]; 730 731 abstract static class IteratorBasedImmutableMap<K, V> extends ImmutableMap<K, V> { 732 abstract UnmodifiableIterator<Entry<K, V>> entryIterator(); 733 734 Spliterator<Entry<K, V>> entrySpliterator() { 735 return Spliterators.spliterator( 736 entryIterator(), 737 size(), 738 Spliterator.DISTINCT | Spliterator.NONNULL | Spliterator.IMMUTABLE | Spliterator.ORDERED); 739 } 740 741 @Override 742 ImmutableSet<K> createKeySet() { 743 return new ImmutableMapKeySet<>(this); 744 } 745 746 @Override 747 ImmutableSet<Entry<K, V>> createEntrySet() { 748 class EntrySetImpl extends ImmutableMapEntrySet<K, V> { 749 @Override 750 ImmutableMap<K, V> map() { 751 return IteratorBasedImmutableMap.this; 752 } 753 754 @Override 755 public UnmodifiableIterator<Entry<K, V>> iterator() { 756 return entryIterator(); 757 } 758 } 759 return new EntrySetImpl(); 760 } 761 762 @Override 763 ImmutableCollection<V> createValues() { 764 return new ImmutableMapValues<>(this); 765 } 766 } 767 768 ImmutableMap() {} 769 770 /** 771 * Guaranteed to throw an exception and leave the map unmodified. 772 * 773 * @throws UnsupportedOperationException always 774 * @deprecated Unsupported operation. 775 */ 776 @CanIgnoreReturnValue 777 @Deprecated 778 @Override 779 @DoNotCall("Always throws UnsupportedOperationException") 780 @CheckForNull 781 public final V put(K k, V v) { 782 throw new UnsupportedOperationException(); 783 } 784 785 /** 786 * Guaranteed to throw an exception and leave the map unmodified. 787 * 788 * @throws UnsupportedOperationException always 789 * @deprecated Unsupported operation. 790 */ 791 @CanIgnoreReturnValue 792 @Deprecated 793 @Override 794 @DoNotCall("Always throws UnsupportedOperationException") 795 @CheckForNull 796 public final V putIfAbsent(K key, V value) { 797 throw new UnsupportedOperationException(); 798 } 799 800 /** 801 * Guaranteed to throw an exception and leave the map unmodified. 802 * 803 * @throws UnsupportedOperationException always 804 * @deprecated Unsupported operation. 805 */ 806 @Deprecated 807 @Override 808 @DoNotCall("Always throws UnsupportedOperationException") 809 public final boolean replace(K key, V oldValue, V newValue) { 810 throw new UnsupportedOperationException(); 811 } 812 813 /** 814 * Guaranteed to throw an exception and leave the map unmodified. 815 * 816 * @throws UnsupportedOperationException always 817 * @deprecated Unsupported operation. 818 */ 819 @Deprecated 820 @Override 821 @CheckForNull 822 @DoNotCall("Always throws UnsupportedOperationException") 823 public final V replace(K key, V value) { 824 throw new UnsupportedOperationException(); 825 } 826 827 /** 828 * Guaranteed to throw an exception and leave the map unmodified. 829 * 830 * @throws UnsupportedOperationException always 831 * @deprecated Unsupported operation. 832 */ 833 @Deprecated 834 @Override 835 @DoNotCall("Always throws UnsupportedOperationException") 836 public final V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) { 837 throw new UnsupportedOperationException(); 838 } 839 840 /** 841 * Guaranteed to throw an exception and leave the map unmodified. 842 * 843 * @throws UnsupportedOperationException always 844 * @deprecated Unsupported operation. 845 */ 846 @Deprecated 847 @Override 848 @DoNotCall("Always throws UnsupportedOperationException") 849 public final V computeIfPresent( 850 K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) { 851 throw new UnsupportedOperationException(); 852 } 853 854 /** 855 * Guaranteed to throw an exception and leave the map unmodified. 856 * 857 * @throws UnsupportedOperationException always 858 * @deprecated Unsupported operation. 859 */ 860 @Deprecated 861 @Override 862 @DoNotCall("Always throws UnsupportedOperationException") 863 public final V compute( 864 K key, BiFunction<? super K, ? super @Nullable V, ? extends V> remappingFunction) { 865 throw new UnsupportedOperationException(); 866 } 867 868 /** 869 * Guaranteed to throw an exception and leave the map unmodified. 870 * 871 * @throws UnsupportedOperationException always 872 * @deprecated Unsupported operation. 873 */ 874 @Deprecated 875 @Override 876 @DoNotCall("Always throws UnsupportedOperationException") 877 public final V merge( 878 K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) { 879 throw new UnsupportedOperationException(); 880 } 881 882 /** 883 * Guaranteed to throw an exception and leave the map unmodified. 884 * 885 * @throws UnsupportedOperationException always 886 * @deprecated Unsupported operation. 887 */ 888 @Deprecated 889 @Override 890 @DoNotCall("Always throws UnsupportedOperationException") 891 public final void putAll(Map<? extends K, ? extends V> map) { 892 throw new UnsupportedOperationException(); 893 } 894 895 /** 896 * Guaranteed to throw an exception and leave the map unmodified. 897 * 898 * @throws UnsupportedOperationException always 899 * @deprecated Unsupported operation. 900 */ 901 @Deprecated 902 @Override 903 @DoNotCall("Always throws UnsupportedOperationException") 904 public final void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 905 throw new UnsupportedOperationException(); 906 } 907 908 /** 909 * Guaranteed to throw an exception and leave the map unmodified. 910 * 911 * @throws UnsupportedOperationException always 912 * @deprecated Unsupported operation. 913 */ 914 @Deprecated 915 @Override 916 @DoNotCall("Always throws UnsupportedOperationException") 917 @CheckForNull 918 public final V remove(@CheckForNull Object o) { 919 throw new UnsupportedOperationException(); 920 } 921 922 /** 923 * Guaranteed to throw an exception and leave the map unmodified. 924 * 925 * @throws UnsupportedOperationException always 926 * @deprecated Unsupported operation. 927 */ 928 @Deprecated 929 @Override 930 @DoNotCall("Always throws UnsupportedOperationException") 931 public final boolean remove(@CheckForNull Object key, @CheckForNull Object value) { 932 throw new UnsupportedOperationException(); 933 } 934 935 /** 936 * Guaranteed to throw an exception and leave the map unmodified. 937 * 938 * @throws UnsupportedOperationException always 939 * @deprecated Unsupported operation. 940 */ 941 @Deprecated 942 @Override 943 @DoNotCall("Always throws UnsupportedOperationException") 944 public final void clear() { 945 throw new UnsupportedOperationException(); 946 } 947 948 @Override 949 public boolean isEmpty() { 950 return size() == 0; 951 } 952 953 @Override 954 public boolean containsKey(@CheckForNull Object key) { 955 return get(key) != null; 956 } 957 958 @Override 959 public boolean containsValue(@CheckForNull Object value) { 960 return values().contains(value); 961 } 962 963 // Overriding to mark it Nullable 964 @Override 965 @CheckForNull 966 public abstract V get(@CheckForNull Object key); 967 968 /** 969 * @since 21.0 (but only since 23.5 in the Android <a 970 * href="https://github.com/google/guava#guava-google-core-libraries-for-java">flavor</a>). 971 * Note, however, that Java 8 users can call this method with any version and flavor of Guava. 972 */ 973 @Override 974 @CheckForNull 975 public final V getOrDefault(@CheckForNull Object key, @CheckForNull V defaultValue) { 976 /* 977 * Even though it's weird to pass a defaultValue that is null, some callers do so. Those who 978 * pass a literal "null" should probably just use `get`, but I would expect other callers to 979 * pass an expression that *might* be null. This could happen with: 980 * 981 * - a `getFooOrDefault(@CheckForNull Foo defaultValue)` method that returns 982 * `map.getOrDefault(FOO_KEY, defaultValue)` 983 * 984 * - a call that consults a chain of maps, as in `mapA.getOrDefault(key, mapB.getOrDefault(key, 985 * ...))` 986 * 987 * So it makes sense for the parameter (and thus the return type) to be @CheckForNull. 988 * 989 * Two other points: 990 * 991 * 1. We'll want to use something like @PolyNull once we can make that work for the various 992 * platforms we target. 993 * 994 * 2. Kotlin's Map type has a getOrDefault method that accepts and returns a "plain V," in 995 * contrast to the "V?" type that we're using. As a result, Kotlin sees a conflict between the 996 * nullness annotations in ImmutableMap and those in its own Map type. In response, it considers 997 * the parameter and return type both to be platform types. As a result, Kotlin permits calls 998 * that can lead to NullPointerException. That's unfortunate. But hopefully most Kotlin callers 999 * use `get(key) ?: defaultValue` instead of this method, anyway. 1000 */ 1001 V result = get(key); 1002 // TODO(b/192579700): Use a ternary once it no longer confuses our nullness checker. 1003 if (result != null) { 1004 return result; 1005 } else { 1006 return defaultValue; 1007 } 1008 } 1009 1010 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<Entry<K, V>> entrySet; 1011 1012 /** 1013 * Returns an immutable set of the mappings in this map. The iteration order is specified by the 1014 * method used to create this map. Typically, this is insertion order. 1015 */ 1016 @Override 1017 public ImmutableSet<Entry<K, V>> entrySet() { 1018 ImmutableSet<Entry<K, V>> result = entrySet; 1019 return (result == null) ? entrySet = createEntrySet() : result; 1020 } 1021 1022 abstract ImmutableSet<Entry<K, V>> createEntrySet(); 1023 1024 @LazyInit @RetainedWith @CheckForNull private transient ImmutableSet<K> keySet; 1025 1026 /** 1027 * Returns an immutable set of the keys in this map, in the same order that they appear in {@link 1028 * #entrySet}. 1029 */ 1030 @Override 1031 public ImmutableSet<K> keySet() { 1032 ImmutableSet<K> result = keySet; 1033 return (result == null) ? keySet = createKeySet() : result; 1034 } 1035 1036 /* 1037 * This could have a good default implementation of return new ImmutableKeySet<K, V>(this), 1038 * but ProGuard can't figure out how to eliminate that default when RegularImmutableMap 1039 * overrides it. 1040 */ 1041 abstract ImmutableSet<K> createKeySet(); 1042 1043 UnmodifiableIterator<K> keyIterator() { 1044 final UnmodifiableIterator<Entry<K, V>> entryIterator = entrySet().iterator(); 1045 return new UnmodifiableIterator<K>() { 1046 @Override 1047 public boolean hasNext() { 1048 return entryIterator.hasNext(); 1049 } 1050 1051 @Override 1052 public K next() { 1053 return entryIterator.next().getKey(); 1054 } 1055 }; 1056 } 1057 1058 Spliterator<K> keySpliterator() { 1059 return CollectSpliterators.map(entrySet().spliterator(), Entry::getKey); 1060 } 1061 1062 @LazyInit @RetainedWith @CheckForNull private transient ImmutableCollection<V> values; 1063 1064 /** 1065 * Returns an immutable collection of the values in this map, in the same order that they appear 1066 * in {@link #entrySet}. 1067 */ 1068 @Override 1069 public ImmutableCollection<V> values() { 1070 ImmutableCollection<V> result = values; 1071 return (result == null) ? values = createValues() : result; 1072 } 1073 1074 /* 1075 * This could have a good default implementation of {@code return new 1076 * ImmutableMapValues<K, V>(this)}, but ProGuard can't figure out how to eliminate that default 1077 * when RegularImmutableMap overrides it. 1078 */ 1079 abstract ImmutableCollection<V> createValues(); 1080 1081 // cached so that this.multimapView().inverse() only computes inverse once 1082 @LazyInit @CheckForNull private transient ImmutableSetMultimap<K, V> multimapView; 1083 1084 /** 1085 * Returns a multimap view of the map. 1086 * 1087 * @since 14.0 1088 */ 1089 public ImmutableSetMultimap<K, V> asMultimap() { 1090 if (isEmpty()) { 1091 return ImmutableSetMultimap.of(); 1092 } 1093 ImmutableSetMultimap<K, V> result = multimapView; 1094 return (result == null) 1095 ? (multimapView = 1096 new ImmutableSetMultimap<>(new MapViewOfValuesAsSingletonSets(), size(), null)) 1097 : result; 1098 } 1099 1100 @WeakOuter 1101 private final class MapViewOfValuesAsSingletonSets 1102 extends IteratorBasedImmutableMap<K, ImmutableSet<V>> { 1103 1104 @Override 1105 public int size() { 1106 return ImmutableMap.this.size(); 1107 } 1108 1109 @Override 1110 ImmutableSet<K> createKeySet() { 1111 return ImmutableMap.this.keySet(); 1112 } 1113 1114 @Override 1115 public boolean containsKey(@CheckForNull Object key) { 1116 return ImmutableMap.this.containsKey(key); 1117 } 1118 1119 @Override 1120 @CheckForNull 1121 public ImmutableSet<V> get(@CheckForNull Object key) { 1122 V outerValue = ImmutableMap.this.get(key); 1123 return (outerValue == null) ? null : ImmutableSet.of(outerValue); 1124 } 1125 1126 @Override 1127 boolean isPartialView() { 1128 return ImmutableMap.this.isPartialView(); 1129 } 1130 1131 @Override 1132 public int hashCode() { 1133 // ImmutableSet.of(value).hashCode() == value.hashCode(), so the hashes are the same 1134 return ImmutableMap.this.hashCode(); 1135 } 1136 1137 @Override 1138 boolean isHashCodeFast() { 1139 return ImmutableMap.this.isHashCodeFast(); 1140 } 1141 1142 @Override 1143 UnmodifiableIterator<Entry<K, ImmutableSet<V>>> entryIterator() { 1144 final Iterator<Entry<K, V>> backingIterator = ImmutableMap.this.entrySet().iterator(); 1145 return new UnmodifiableIterator<Entry<K, ImmutableSet<V>>>() { 1146 @Override 1147 public boolean hasNext() { 1148 return backingIterator.hasNext(); 1149 } 1150 1151 @Override 1152 public Entry<K, ImmutableSet<V>> next() { 1153 final Entry<K, V> backingEntry = backingIterator.next(); 1154 return new AbstractMapEntry<K, ImmutableSet<V>>() { 1155 @Override 1156 public K getKey() { 1157 return backingEntry.getKey(); 1158 } 1159 1160 @Override 1161 public ImmutableSet<V> getValue() { 1162 return ImmutableSet.of(backingEntry.getValue()); 1163 } 1164 }; 1165 } 1166 }; 1167 } 1168 } 1169 1170 @Override 1171 public boolean equals(@CheckForNull Object object) { 1172 return Maps.equalsImpl(this, object); 1173 } 1174 1175 abstract boolean isPartialView(); 1176 1177 @Override 1178 public int hashCode() { 1179 return Sets.hashCodeImpl(entrySet()); 1180 } 1181 1182 boolean isHashCodeFast() { 1183 return false; 1184 } 1185 1186 @Override 1187 public String toString() { 1188 return Maps.toStringImpl(this); 1189 } 1190 1191 /** 1192 * Serialized type for all ImmutableMap instances. It captures the logical contents and they are 1193 * reconstructed using public factory methods. This ensures that the implementation types remain 1194 * as implementation details. 1195 */ 1196 static class SerializedForm<K, V> implements Serializable { 1197 // This object retains references to collections returned by keySet() and value(). This saves 1198 // bytes when the both the map and its keySet or value collection are written to the same 1199 // instance of ObjectOutputStream. 1200 1201 // TODO(b/160980469): remove support for the old serialization format after some time 1202 private static final boolean USE_LEGACY_SERIALIZATION = true; 1203 1204 private final Object keys; 1205 private final Object values; 1206 1207 SerializedForm(ImmutableMap<K, V> map) { 1208 if (USE_LEGACY_SERIALIZATION) { 1209 Object[] keys = new Object[map.size()]; 1210 Object[] values = new Object[map.size()]; 1211 int i = 0; 1212 // "extends Object" works around https://github.com/typetools/checker-framework/issues/3013 1213 for (Entry<? extends Object, ? extends Object> entry : map.entrySet()) { 1214 keys[i] = entry.getKey(); 1215 values[i] = entry.getValue(); 1216 i++; 1217 } 1218 this.keys = keys; 1219 this.values = values; 1220 return; 1221 } 1222 this.keys = map.keySet(); 1223 this.values = map.values(); 1224 } 1225 1226 @SuppressWarnings("unchecked") 1227 final Object readResolve() { 1228 if (!(this.keys instanceof ImmutableSet)) { 1229 return legacyReadResolve(); 1230 } 1231 1232 ImmutableSet<K> keySet = (ImmutableSet<K>) this.keys; 1233 ImmutableCollection<V> values = (ImmutableCollection<V>) this.values; 1234 1235 Builder<K, V> builder = makeBuilder(keySet.size()); 1236 1237 UnmodifiableIterator<K> keyIter = keySet.iterator(); 1238 UnmodifiableIterator<V> valueIter = values.iterator(); 1239 1240 while (keyIter.hasNext()) { 1241 builder.put(keyIter.next(), valueIter.next()); 1242 } 1243 1244 return builder.buildOrThrow(); 1245 } 1246 1247 @SuppressWarnings("unchecked") 1248 final Object legacyReadResolve() { 1249 K[] keys = (K[]) this.keys; 1250 V[] values = (V[]) this.values; 1251 1252 Builder<K, V> builder = makeBuilder(keys.length); 1253 1254 for (int i = 0; i < keys.length; i++) { 1255 builder.put(keys[i], values[i]); 1256 } 1257 return builder.buildOrThrow(); 1258 } 1259 1260 /** 1261 * Returns a builder that builds the unserialized type. Subclasses should override this method. 1262 */ 1263 Builder<K, V> makeBuilder(int size) { 1264 return new Builder<>(size); 1265 } 1266 1267 private static final long serialVersionUID = 0; 1268 } 1269 1270 /** 1271 * Returns a serializable form of this object. Non-public subclasses should not override this 1272 * method. Publicly-accessible subclasses must override this method and should return a subclass 1273 * of SerializedForm whose readResolve() method returns objects of the subclass type. 1274 */ 1275 Object writeReplace() { 1276 return new SerializedForm<>(this); 1277 } 1278 1279 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 1280 throw new InvalidObjectException("Use SerializedForm"); 1281 } 1282}