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