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