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.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 Object#equals(Object)},
057   * an {@code IllegalArgumentException} is thrown when the collection operation is performed. (This
058   * differs from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)},
059   * 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  @Beta
306  public static <K, V> Builder<K, V> builderWithExpectedSize(int expectedSize) {
307    checkNonnegative(expectedSize, "expectedSize");
308    return new Builder<>(expectedSize);
309  }
310
311  /**
312   * A builder for creating immutable bimap instances, especially {@code public static final} bimaps
313   * ("constant bimaps"). Example:
314   *
315   * <pre>{@code
316   * static final ImmutableBiMap<String, Integer> WORD_TO_INT =
317   *     new ImmutableBiMap.Builder<String, Integer>()
318   *         .put("one", 1)
319   *         .put("two", 2)
320   *         .put("three", 3)
321   *         .buildOrThrow();
322   * }</pre>
323   *
324   * <p>For <i>small</i> immutable bimaps, the {@code ImmutableBiMap.of()} methods are even more
325   * convenient.
326   *
327   * <p>By default, a {@code Builder} will generate bimaps that iterate over entries in the order
328   * they were inserted into the builder. For example, in the above example, {@code
329   * WORD_TO_INT.entrySet()} is guaranteed to iterate over the entries in the order {@code "one"=1,
330   * "two"=2, "three"=3}, and {@code keySet()} and {@code values()} respect the same order. If you
331   * want a different order, consider using {@link #orderEntriesByValue(Comparator)}, which changes
332   * this builder to sort entries by value.
333   *
334   * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to
335   * build multiple bimaps in series. Each bimap is a superset of the bimaps created before it.
336   *
337   * @since 2.0
338   */
339  public static final class Builder<K, V> extends ImmutableMap.Builder<K, V> {
340
341    /**
342     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
343     * ImmutableBiMap#builder}.
344     */
345    public Builder() {}
346
347    Builder(int size) {
348      super(size);
349    }
350
351    /**
352     * Associates {@code key} with {@code value} in the built bimap. Duplicate keys or values are
353     * not allowed, and will cause {@link #build} to fail.
354     */
355    @CanIgnoreReturnValue
356    @Override
357    public Builder<K, V> put(K key, V value) {
358      super.put(key, value);
359      return this;
360    }
361
362    /**
363     * Adds the given {@code entry} to the bimap. Duplicate keys or values are not allowed, and will
364     * cause {@link #build} to fail.
365     *
366     * @since 19.0
367     */
368    @CanIgnoreReturnValue
369    @Override
370    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
371      super.put(entry);
372      return this;
373    }
374
375    /**
376     * Associates all of the given map's keys and values in the built bimap. Duplicate keys or
377     * values are not allowed, and will cause {@link #build} to fail.
378     *
379     * @throws NullPointerException if any key or value in {@code map} is null
380     */
381    @CanIgnoreReturnValue
382    @Override
383    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
384      super.putAll(map);
385      return this;
386    }
387
388    /**
389     * Adds all of the given entries to the built bimap. Duplicate keys or values are not allowed,
390     * and will cause {@link #build} to fail.
391     *
392     * @throws NullPointerException if any key, value, or entry is null
393     * @since 19.0
394     */
395    @CanIgnoreReturnValue
396    @Beta
397    @Override
398    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
399      super.putAll(entries);
400      return this;
401    }
402
403    /**
404     * Configures this {@code Builder} to order entries by value according to the specified
405     * comparator.
406     *
407     * <p>The sort order is stable, that is, if two entries have values that compare as equivalent,
408     * the entry that was inserted first will be first in the built map's iteration order.
409     *
410     * @throws IllegalStateException if this method was already called
411     * @since 19.0
412     */
413    @CanIgnoreReturnValue
414    @Beta
415    @Override
416    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
417      super.orderEntriesByValue(valueComparator);
418      return this;
419    }
420
421    @Override
422    @CanIgnoreReturnValue
423    Builder<K, V> combine(ImmutableMap.Builder<K, V> builder) {
424      super.combine(builder);
425      return this;
426    }
427
428    /**
429     * Returns a newly-created immutable bimap. The iteration order of the returned bimap is the
430     * order in which entries were inserted into the builder, unless {@link #orderEntriesByValue}
431     * was called, in which case entries are sorted by value.
432     *
433     * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method
434     * will throw an exception if there are duplicate keys or values. The {@code build()} method
435     * will soon be deprecated.
436     *
437     * @throws IllegalArgumentException if duplicate keys or values were added
438     */
439    @Override
440    public ImmutableBiMap<K, V> build() {
441      return buildOrThrow();
442    }
443
444    /**
445     * Returns a newly-created immutable bimap, or throws an exception if any key or value was added
446     * more than once. The iteration order of the returned bimap is the order in which entries were
447     * inserted into the builder, unless {@link #orderEntriesByValue} was called, in which case
448     * entries are sorted by value.
449     *
450     * @throws IllegalArgumentException if duplicate keys or values were added
451     * @since 31.0
452     */
453    @Override
454    public ImmutableBiMap<K, V> buildOrThrow() {
455      switch (size) {
456        case 0:
457          return of();
458        case 1:
459          // requireNonNull is safe because the first `size` elements have been filled in.
460          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
461          return of(onlyEntry.getKey(), onlyEntry.getValue());
462        default:
463          /*
464           * If entries is full, or if hash flooding is detected, then this implementation may end
465           * up using the entries array directly and writing over the entry objects with
466           * non-terminal entries, but this is safe; if this Builder is used further, it will grow
467           * the entries array (so it can't affect the original array), and future build() calls
468           * will always copy any entry objects that cannot be safely reused.
469           */
470          if (valueComparator != null) {
471            if (entriesUsed) {
472              entries = Arrays.copyOf(entries, size);
473            }
474            Arrays.sort(
475                entries,
476                0,
477                size,
478                Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
479          }
480          entriesUsed = true;
481          return RegularImmutableBiMap.fromEntryArray(size, entries);
482      }
483    }
484
485    /**
486     * Throws {@link UnsupportedOperationException}. This method is inherited from {@link
487     * ImmutableMap.Builder}, but it does not make sense for bimaps.
488     *
489     * @throws UnsupportedOperationException always
490     * @deprecated This method does not make sense for bimaps and should not be called.
491     * @since 31.1
492     */
493    @DoNotCall
494    @Deprecated
495    @Override
496    public ImmutableBiMap<K, V> buildKeepingLast() {
497      throw new UnsupportedOperationException("Not supported for bimaps");
498    }
499
500    @Override
501    @VisibleForTesting
502    ImmutableBiMap<K, V> buildJdkBacked() {
503      checkState(
504          valueComparator == null,
505          "buildJdkBacked is for tests only, doesn't support orderEntriesByValue");
506      switch (size) {
507        case 0:
508          return of();
509        case 1:
510          // requireNonNull is safe because the first `size` elements have been filled in.
511          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
512          return of(onlyEntry.getKey(), onlyEntry.getValue());
513        default:
514          entriesUsed = true;
515          return RegularImmutableBiMap.fromEntryArray(size, entries);
516      }
517    }
518  }
519
520  /**
521   * Returns an immutable bimap containing the same entries as {@code map}. If {@code map} somehow
522   * contains entries with duplicate keys (for example, if it is a {@code SortedMap} whose
523   * comparator is not <i>consistent with equals</i>), the results of this method are undefined.
524   *
525   * <p>The returned {@code BiMap} iterates over entries in the same order as the {@code entrySet}
526   * of the original map.
527   *
528   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
529   * safe to do so. The exact circumstances under which a copy will or will not be performed are
530   * undocumented and subject to change.
531   *
532   * @throws IllegalArgumentException if two keys have the same value or two values have the same
533   *     key
534   * @throws NullPointerException if any key or value in {@code map} is null
535   */
536  public static <K, V> ImmutableBiMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
537    if (map instanceof ImmutableBiMap) {
538      @SuppressWarnings("unchecked") // safe since map is not writable
539      ImmutableBiMap<K, V> bimap = (ImmutableBiMap<K, V>) map;
540      // TODO(lowasser): if we need to make a copy of a BiMap because the
541      // forward map is a view, don't make a copy of the non-view delegate map
542      if (!bimap.isPartialView()) {
543        return bimap;
544      }
545    }
546    return copyOf(map.entrySet());
547  }
548
549  /**
550   * Returns an immutable bimap containing the given entries. The returned bimap iterates over
551   * entries in the same order as the original iterable.
552   *
553   * @throws IllegalArgumentException if two keys have the same value or two values have the same
554   *     key
555   * @throws NullPointerException if any key, value, or entry is null
556   * @since 19.0
557   */
558  @Beta
559  public static <K, V> ImmutableBiMap<K, V> copyOf(
560      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
561    @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
562    Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
563    switch (entryArray.length) {
564      case 0:
565        return of();
566      case 1:
567        Entry<K, V> entry = entryArray[0];
568        return of(entry.getKey(), entry.getValue());
569      default:
570        /*
571         * The current implementation will end up using entryArray directly, though it will write
572         * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
573         */
574        return RegularImmutableBiMap.fromEntries(entryArray);
575    }
576  }
577
578  ImmutableBiMap() {}
579
580  /**
581   * {@inheritDoc}
582   *
583   * <p>The inverse of an {@code ImmutableBiMap} is another {@code ImmutableBiMap}.
584   */
585  @Override
586  public abstract ImmutableBiMap<V, K> inverse();
587
588  /**
589   * Returns an immutable set of the values in this map, in the same order they appear in {@link
590   * #entrySet}.
591   */
592  @Override
593  public ImmutableSet<V> values() {
594    return inverse().keySet();
595  }
596
597  @Override
598  final ImmutableSet<V> createValues() {
599    throw new AssertionError("should never be called");
600  }
601
602  /**
603   * Guaranteed to throw an exception and leave the bimap unmodified.
604   *
605   * @throws UnsupportedOperationException always
606   * @deprecated Unsupported operation.
607   */
608  @CanIgnoreReturnValue
609  @Deprecated
610  @Override
611  @DoNotCall("Always throws UnsupportedOperationException")
612  @CheckForNull
613  public final V forcePut(K key, V value) {
614    throw new UnsupportedOperationException();
615  }
616
617  /**
618   * Serialized type for all ImmutableBiMap instances. It captures the logical contents and they are
619   * reconstructed using public factory methods. This ensures that the implementation types remain
620   * as implementation details.
621   *
622   * <p>Since the bimap is immutable, ImmutableBiMap doesn't require special logic for keeping the
623   * bimap and its inverse in sync during serialization, the way AbstractBiMap does.
624   */
625  private static class SerializedForm<K, V> extends ImmutableMap.SerializedForm<K, V> {
626    SerializedForm(ImmutableBiMap<K, V> bimap) {
627      super(bimap);
628    }
629
630    @Override
631    Builder<K, V> makeBuilder(int size) {
632      return new Builder<>(size);
633    }
634
635    private static final long serialVersionUID = 0;
636  }
637
638  @Override
639  Object writeReplace() {
640    return new SerializedForm<>(this);
641  }
642
643  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
644    throw new InvalidObjectException("Use SerializedForm");
645  }
646}