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