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}