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