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