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.checkState; 020import static com.google.common.collect.CollectPreconditions.checkNonnegative; 021import static java.util.Objects.requireNonNull; 022 023import com.google.common.annotations.GwtCompatible; 024import com.google.common.annotations.J2ktIncompatible; 025import com.google.common.annotations.VisibleForTesting; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import com.google.errorprone.annotations.DoNotCall; 028import java.io.InvalidObjectException; 029import java.io.ObjectInputStream; 030import java.util.Arrays; 031import java.util.Comparator; 032import java.util.Map; 033import java.util.function.Function; 034import java.util.stream.Collector; 035import java.util.stream.Collectors; 036import javax.annotation.CheckForNull; 037import org.checkerframework.checker.nullness.qual.Nullable; 038 039/** 040 * A {@link BiMap} whose contents will never change, with many other important properties detailed 041 * at {@link ImmutableCollection}. 042 * 043 * @author Jared Levy 044 * @since 2.0 045 */ 046@GwtCompatible(serializable = true, emulated = true) 047@ElementTypesAreNonnullByDefault 048public abstract class ImmutableBiMap<K, V> extends ImmutableBiMapFauxverideShim<K, V> 049 implements BiMap<K, V> { 050 051 /** 052 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableBiMap} whose keys 053 * and values are the result of applying the provided mapping functions to the input elements. 054 * Entries appear in the result {@code ImmutableBiMap} in encounter order. 055 * 056 * <p>If the mapped keys or values contain duplicates (according to {@link 057 * Object#equals(Object)}), an {@code IllegalArgumentException} is thrown when the collection 058 * operation is performed. (This differs from the {@code Collector} returned by {@link 059 * Collectors#toMap(Function, Function)}, which throws an {@code IllegalStateException}.) 060 * 061 * @since 21.0 062 */ 063 public static <T extends @Nullable Object, K, V> 064 Collector<T, ?, ImmutableBiMap<K, V>> toImmutableBiMap( 065 Function<? super T, ? extends K> keyFunction, 066 Function<? super T, ? extends V> valueFunction) { 067 return CollectCollectors.toImmutableBiMap(keyFunction, valueFunction); 068 } 069 070 /** 071 * Returns the empty bimap. 072 * 073 * <p><b>Performance note:</b> the instance returned is a singleton. 074 */ 075 // Casting to any type is safe because the set will never hold any elements. 076 @SuppressWarnings("unchecked") 077 public static <K, V> ImmutableBiMap<K, V> of() { 078 return (ImmutableBiMap<K, V>) RegularImmutableBiMap.EMPTY; 079 } 080 081 /** Returns an immutable bimap containing a single entry. */ 082 public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1) { 083 return new SingletonImmutableBiMap<>(k1, v1); 084 } 085 086 /** 087 * Returns an immutable map containing the given entries, in order. 088 * 089 * @throws IllegalArgumentException if duplicate keys or values are added 090 */ 091 public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2) { 092 return RegularImmutableBiMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2)); 093 } 094 095 /** 096 * Returns an immutable map containing the given entries, in order. 097 * 098 * @throws IllegalArgumentException if duplicate keys or values are added 099 */ 100 public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) { 101 return RegularImmutableBiMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 102 } 103 104 /** 105 * Returns an immutable map containing the given entries, in order. 106 * 107 * @throws IllegalArgumentException if duplicate keys or values are added 108 */ 109 public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 110 return RegularImmutableBiMap.fromEntries( 111 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 112 } 113 114 /** 115 * Returns an immutable map containing the given entries, in order. 116 * 117 * @throws IllegalArgumentException if duplicate keys or values are added 118 */ 119 public static <K, V> ImmutableBiMap<K, V> of( 120 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 121 return RegularImmutableBiMap.fromEntries( 122 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 123 } 124 125 /** 126 * Returns an immutable map containing the given entries, in order. 127 * 128 * @throws IllegalArgumentException if duplicate keys or values are added 129 * @since 31.0 130 */ 131 public static <K, V> ImmutableBiMap<K, V> of( 132 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) { 133 return RegularImmutableBiMap.fromEntries( 134 entryOf(k1, v1), 135 entryOf(k2, v2), 136 entryOf(k3, v3), 137 entryOf(k4, v4), 138 entryOf(k5, v5), 139 entryOf(k6, v6)); 140 } 141 142 /** 143 * Returns an immutable map containing the given entries, in order. 144 * 145 * @throws IllegalArgumentException if duplicate keys or values are added 146 * @since 31.0 147 */ 148 public static <K, V> ImmutableBiMap<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, K k7, V v7) { 150 return RegularImmutableBiMap.fromEntries( 151 entryOf(k1, v1), 152 entryOf(k2, v2), 153 entryOf(k3, v3), 154 entryOf(k4, v4), 155 entryOf(k5, v5), 156 entryOf(k6, v6), 157 entryOf(k7, v7)); 158 } 159 160 /** 161 * Returns an immutable map containing the given entries, in order. 162 * 163 * @throws IllegalArgumentException if duplicate keys or values are added 164 * @since 31.0 165 */ 166 public static <K, V> ImmutableBiMap<K, V> of( 167 K k1, 168 V v1, 169 K k2, 170 V v2, 171 K k3, 172 V v3, 173 K k4, 174 V v4, 175 K k5, 176 V v5, 177 K k6, 178 V v6, 179 K k7, 180 V v7, 181 K k8, 182 V v8) { 183 return RegularImmutableBiMap.fromEntries( 184 entryOf(k1, v1), 185 entryOf(k2, v2), 186 entryOf(k3, v3), 187 entryOf(k4, v4), 188 entryOf(k5, v5), 189 entryOf(k6, v6), 190 entryOf(k7, v7), 191 entryOf(k8, v8)); 192 } 193 194 /** 195 * Returns an immutable map containing the given entries, in order. 196 * 197 * @throws IllegalArgumentException if duplicate keys or values are added 198 * @since 31.0 199 */ 200 public static <K, V> ImmutableBiMap<K, V> of( 201 K k1, 202 V v1, 203 K k2, 204 V v2, 205 K k3, 206 V v3, 207 K k4, 208 V v4, 209 K k5, 210 V v5, 211 K k6, 212 V v6, 213 K k7, 214 V v7, 215 K k8, 216 V v8, 217 K k9, 218 V v9) { 219 return RegularImmutableBiMap.fromEntries( 220 entryOf(k1, v1), 221 entryOf(k2, v2), 222 entryOf(k3, v3), 223 entryOf(k4, v4), 224 entryOf(k5, v5), 225 entryOf(k6, v6), 226 entryOf(k7, v7), 227 entryOf(k8, v8), 228 entryOf(k9, v9)); 229 } 230 /** 231 * Returns an immutable map containing the given entries, in order. 232 * 233 * @throws IllegalArgumentException if duplicate keys or values are added 234 * @since 31.0 235 */ 236 public static <K, V> ImmutableBiMap<K, V> of( 237 K k1, 238 V v1, 239 K k2, 240 V v2, 241 K k3, 242 V v3, 243 K k4, 244 V v4, 245 K k5, 246 V v5, 247 K k6, 248 V v6, 249 K k7, 250 V v7, 251 K k8, 252 V v8, 253 K k9, 254 V v9, 255 K k10, 256 V v10) { 257 return RegularImmutableBiMap.fromEntries( 258 entryOf(k1, v1), 259 entryOf(k2, v2), 260 entryOf(k3, v3), 261 entryOf(k4, v4), 262 entryOf(k5, v5), 263 entryOf(k6, v6), 264 entryOf(k7, v7), 265 entryOf(k8, v8), 266 entryOf(k9, v9), 267 entryOf(k10, v10)); 268 } 269 270 // looking for of() with > 10 entries? Use the builder or ofEntries instead. 271 272 /** 273 * Returns an immutable map containing the given entries, in order. 274 * 275 * @throws IllegalArgumentException if duplicate keys or values are provided 276 * @since 31.0 277 */ 278 @SafeVarargs 279 public static <K, V> ImmutableBiMap<K, V> ofEntries(Entry<? extends K, ? extends V>... entries) { 280 @SuppressWarnings("unchecked") // we will only ever read these 281 Entry<K, V>[] entries2 = (Entry<K, V>[]) entries; 282 return RegularImmutableBiMap.fromEntries(entries2); 283 } 284 285 /** 286 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 287 * Builder} constructor. 288 */ 289 public static <K, V> Builder<K, V> builder() { 290 return new Builder<>(); 291 } 292 293 /** 294 * Returns a new builder, expecting the specified number of entries to be added. 295 * 296 * <p>If {@code expectedSize} is exactly the number of entries added to the builder before {@link 297 * Builder#build} is called, the builder is likely to perform better than an unsized {@link 298 * #builder()} would have. 299 * 300 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 301 * but not exactly, the number of entries added to the builder. 302 * 303 * @since 23.1 304 */ 305 public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) { 306 checkNonnegative(expectedSize, "expectedSize"); 307 return new Builder<>(expectedSize); 308 } 309 310 /** 311 * A builder for creating immutable bimap instances, especially {@code public static final} bimaps 312 * ("constant bimaps"). Example: 313 * 314 * <pre>{@code 315 * static final ImmutableBiMap<String, Integer> WORD_TO_INT = 316 * new ImmutableBiMap.Builder<String, Integer>() 317 * .put("one", 1) 318 * .put("two", 2) 319 * .put("three", 3) 320 * .buildOrThrow(); 321 * }</pre> 322 * 323 * <p>For <i>small</i> immutable bimaps, the {@code ImmutableBiMap.of()} methods are even more 324 * convenient. 325 * 326 * <p>By default, a {@code Builder} will generate bimaps that iterate over entries in the order 327 * they were inserted into the builder. For example, in the above example, {@code 328 * WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the order {@code "one"=1, 329 * "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect the same order. If you 330 * want a different order, consider using {@link #orderEntriesByValue(Comparator)}, which changes 331 * this builder to sort entries by value. 332 * 333 * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to 334 * build multiple bimaps in series. Each bimap is a superset of the bimaps created before it. 335 * 336 * @since 2.0 337 */ 338 public static final class Builder<K, V> extends ImmutableMap.Builder<K, V> { 339 340 /** 341 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 342 * ImmutableBiMap#builder}. 343 */ 344 public Builder() {} 345 346 Builder(int size) { 347 super(size); 348 } 349 350 /** 351 * Associates {@code key} with {@code value} in the built bimap. Duplicate keys or values are 352 * not allowed, and will cause {@link #build} to fail. 353 */ 354 @CanIgnoreReturnValue 355 @Override 356 public Builder<K, V> put(K key, V value) { 357 super.put(key, value); 358 return this; 359 } 360 361 /** 362 * Adds the given {@code entry} to the bimap. Duplicate keys or values are not allowed, and will 363 * cause {@link #build} to fail. 364 * 365 * @since 19.0 366 */ 367 @CanIgnoreReturnValue 368 @Override 369 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 370 super.put(entry); 371 return this; 372 } 373 374 /** 375 * Associates all of the given map's keys and values in the built bimap. Duplicate keys or 376 * values are not allowed, and will cause {@link #build} to fail. 377 * 378 * @throws NullPointerException if any key or value in {@code map} is null 379 */ 380 @CanIgnoreReturnValue 381 @Override 382 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 383 super.putAll(map); 384 return this; 385 } 386 387 /** 388 * Adds all of the given entries to the built bimap. Duplicate keys or values are not allowed, 389 * and will cause {@link #build} to fail. 390 * 391 * @throws NullPointerException if any key, value, or entry is null 392 * @since 19.0 393 */ 394 @CanIgnoreReturnValue 395 @Override 396 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 397 super.putAll(entries); 398 return this; 399 } 400 401 /** 402 * Configures this {@code Builder} to order entries by value according to the specified 403 * comparator. 404 * 405 * <p>The sort order is stable, that is, if two entries have values that compare as equivalent, 406 * the entry that was inserted first will be first in the built map's iteration order. 407 * 408 * @throws IllegalStateException if this method was already called 409 * @since 19.0 410 */ 411 @CanIgnoreReturnValue 412 @Override 413 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 414 super.orderEntriesByValue(valueComparator); 415 return this; 416 } 417 418 @Override 419 @CanIgnoreReturnValue 420 Builder<K, V> combine(ImmutableMap.Builder<K, V> builder) { 421 super.combine(builder); 422 return this; 423 } 424 425 /** 426 * Returns a newly-created immutable bimap. The iteration order of the returned bimap is the 427 * order in which entries were inserted into the builder, unless {@link #orderEntriesByValue} 428 * was called, in which case entries are sorted by value. 429 * 430 * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method 431 * will throw an exception if there are duplicate keys or values. The {@code build()} method 432 * will soon be deprecated. 433 * 434 * @throws IllegalArgumentException if duplicate keys or values were added 435 */ 436 @Override 437 public ImmutableBiMap<K, V> build() { 438 return buildOrThrow(); 439 } 440 441 /** 442 * Returns a newly-created immutable bimap, or throws an exception if any key or value was added 443 * more than once. The iteration order of the returned bimap is the order in which entries were 444 * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case 445 * entries are sorted by value. 446 * 447 * @throws IllegalArgumentException if duplicate keys or values were added 448 * @since 31.0 449 */ 450 @Override 451 public ImmutableBiMap<K, V> buildOrThrow() { 452 switch (size) { 453 case 0: 454 return of(); 455 case 1: 456 // requireNonNull is safe because the first `size` elements have been filled in. 457 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 458 return of(onlyEntry.getKey(), onlyEntry.getValue()); 459 default: 460 /* 461 * If entries is full, or if hash flooding is detected, then this implementation may end 462 * up using the entries array directly and writing over the entry objects with 463 * non-terminal entries, but this is safe; if this Builder is used further, it will grow 464 * the entries array (so it can't affect the original array), and future build() calls 465 * will always copy any entry objects that cannot be safely reused. 466 */ 467 if (valueComparator != null) { 468 if (entriesUsed) { 469 entries = Arrays.copyOf(entries, size); 470 } 471 Arrays.sort( 472 (Entry<K, V>[]) entries, // Entries up to size are not null 473 0, 474 size, 475 Ordering.from(valueComparator).onResultOf(Maps.valueFunction())); 476 } 477 entriesUsed = true; 478 return RegularImmutableBiMap.fromEntryArray(size, entries); 479 } 480 } 481 482 /** 483 * Throws {@link UnsupportedOperationException}. This method is inherited from {@link 484 * ImmutableMap.Builder}, but it does not make sense for bimaps. 485 * 486 * @throws UnsupportedOperationException always 487 * @deprecated This method does not make sense for bimaps and should not be called. 488 * @since 31.1 489 */ 490 @DoNotCall 491 @Deprecated 492 @Override 493 public ImmutableBiMap<K, V> buildKeepingLast() { 494 throw new UnsupportedOperationException("Not supported for bimaps"); 495 } 496 497 @Override 498 @VisibleForTesting 499 ImmutableBiMap<K, V> buildJdkBacked() { 500 checkState( 501 valueComparator == null, 502 "buildJdkBacked is for tests only, doesn't support orderEntriesByValue"); 503 switch (size) { 504 case 0: 505 return of(); 506 case 1: 507 // requireNonNull is safe because the first `size` elements have been filled in. 508 Entry<K, V> onlyEntry = requireNonNull(entries[0]); 509 return of(onlyEntry.getKey(), onlyEntry.getValue()); 510 default: 511 entriesUsed = true; 512 return RegularImmutableBiMap.fromEntryArray(size, entries); 513 } 514 } 515 } 516 517 /** 518 * Returns an immutable bimap containing the same entries as {@code map}. If {@code map} somehow 519 * contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose 520 * comparator is not <i>consistent with equals</i>), the results of this method are undefined. 521 * 522 * <p>The returned {@code BiMap} iterates over entries in the same order as the {@code entrySet} 523 * of the original map. 524 * 525 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is 526 * safe to do so. The exact circumstances under which a copy will or will not be performed are 527 * undocumented and subject to change. 528 * 529 * @throws IllegalArgumentException if two keys have the same value or two values have the same 530 * key 531 * @throws NullPointerException if any key or value in {@code map} is null 532 */ 533 public static <K, V> ImmutableBiMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 534 if (map instanceof ImmutableBiMap) { 535 @SuppressWarnings("unchecked") // safe since map is not writable 536 ImmutableBiMap<K, V> bimap = (ImmutableBiMap<K, V>) map; 537 // TODO(lowasser): if we need to make a copy of a BiMap because the 538 // forward map is a view, don't make a copy of the non-view delegate map 539 if (!bimap.isPartialView()) { 540 return bimap; 541 } 542 } 543 return copyOf(map.entrySet()); 544 } 545 546 /** 547 * Returns an immutable bimap containing the given entries. The returned bimap iterates over 548 * entries in the same order as the original iterable. 549 * 550 * @throws IllegalArgumentException if two keys have the same value or two values have the same 551 * key 552 * @throws NullPointerException if any key, value, or entry is null 553 * @since 19.0 554 */ 555 public static <K, V> ImmutableBiMap<K, V> copyOf( 556 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 557 @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant 558 Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 559 switch (entryArray.length) { 560 case 0: 561 return of(); 562 case 1: 563 Entry<K, V> entry = entryArray[0]; 564 return of(entry.getKey(), entry.getValue()); 565 default: 566 /* 567 * The current implementation will end up using entryArray directly, though it will write 568 * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray. 569 */ 570 return RegularImmutableBiMap.fromEntries(entryArray); 571 } 572 } 573 574 ImmutableBiMap() {} 575 576 /** 577 * {@inheritDoc} 578 * 579 * <p>The inverse of an {@code ImmutableBiMap} is another {@code ImmutableBiMap}. 580 */ 581 @Override 582 public abstract ImmutableBiMap<V, K> inverse(); 583 584 /** 585 * Returns an immutable set of the values in this map, in the same order they appear in {@link 586 * #entrySet}. 587 */ 588 @Override 589 public ImmutableSet<V> values() { 590 return inverse().keySet(); 591 } 592 593 @Override 594 final ImmutableSet<V> createValues() { 595 throw new AssertionError("should never be called"); 596 } 597 598 /** 599 * Guaranteed to throw an exception and leave the bimap unmodified. 600 * 601 * @throws UnsupportedOperationException always 602 * @deprecated Unsupported operation. 603 */ 604 @CanIgnoreReturnValue 605 @Deprecated 606 @Override 607 @DoNotCall("Always throws UnsupportedOperationException") 608 @CheckForNull 609 public final V forcePut(K key, V value) { 610 throw new UnsupportedOperationException(); 611 } 612 613 /** 614 * Serialized type for all ImmutableBiMap instances. It captures the logical contents and they are 615 * reconstructed using public factory methods. This ensures that the implementation types remain 616 * as implementation details. 617 * 618 * <p>Since the bimap is immutable, ImmutableBiMap doesn't require special logic for keeping the 619 * bimap and its inverse in sync during serialization, the way AbstractBiMap does. 620 */ 621 @J2ktIncompatible // serialization 622 private static class SerializedForm<K, V> extends ImmutableMap.SerializedForm<K, V> { 623 SerializedForm(ImmutableBiMap<K, V> bimap) { 624 super(bimap); 625 } 626 627 @Override 628 Builder<K, V> makeBuilder(int size) { 629 return new Builder<>(size); 630 } 631 632 private static final long serialVersionUID = 0; 633 } 634 635 @Override 636 @J2ktIncompatible // serialization 637 Object writeReplace() { 638 return new SerializedForm<>(this); 639 } 640 641 @J2ktIncompatible // serialization 642 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 643 throw new InvalidObjectException("Use SerializedForm"); 644 } 645}