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}