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 com.google.common.annotations.Beta;
020import com.google.common.annotations.GwtCompatible;
021import com.google.errorprone.annotations.CanIgnoreReturnValue;
022import java.util.Arrays;
023import java.util.Comparator;
024import java.util.Map;
025import java.util.function.Function;
026import java.util.stream.Collector;
027import java.util.stream.Collectors;
028
029/**
030 * A {@link BiMap} whose contents will never change, with many other important properties detailed
031 * at {@link ImmutableCollection}.
032 *
033 * @author Jared Levy
034 * @since 2.0
035 */
036@GwtCompatible(serializable = true, emulated = true)
037public abstract class ImmutableBiMap<K, V> extends ImmutableBiMapFauxverideShim<K, V>
038    implements BiMap<K, V> {
039
040  /**
041   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableBiMap} whose
042   * keys and values are the result of applying the provided mapping functions to the input
043   * elements. Entries appear in the result {@code ImmutableBiMap} in encounter order.
044   *
045   * <p>If the mapped keys or values contain duplicates
046   * (according to {@link Object#equals(Object)}, an {@code IllegalArgumentException} is thrown
047   * when the collection operation is performed. (This differs from the {@code Collector} returned
048   * by {@link Collectors#toMap(Function, Function)}, which throws an
049   * {@code IllegalStateException}.)
050   *
051   * @since 21.0
052   */
053  @Beta
054  public static <T, K, V> Collector<T, ?, ImmutableBiMap<K, V>> toImmutableBiMap(
055      Function<? super T, ? extends K> keyFunction,
056      Function<? super T, ? extends V> valueFunction) {
057    return CollectCollectors.toImmutableBiMap(keyFunction, valueFunction);
058  }
059
060  /**
061   * Returns the empty bimap.
062   */
063  // Casting to any type is safe because the set will never hold any elements.
064  @SuppressWarnings("unchecked")
065  public static <K, V> ImmutableBiMap<K, V> of() {
066    return (ImmutableBiMap<K, V>) RegularImmutableBiMap.EMPTY;
067  }
068
069  /**
070   * Returns an immutable bimap containing a single entry.
071   */
072  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1) {
073    return new SingletonImmutableBiMap<K, V>(k1, v1);
074  }
075
076  /**
077   * Returns an immutable map containing the given entries, in order.
078   *
079   * @throws IllegalArgumentException if duplicate keys or values are added
080   */
081  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2) {
082    return RegularImmutableBiMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2));
083  }
084
085  /**
086   * Returns an immutable map containing the given entries, in order.
087   *
088   * @throws IllegalArgumentException if duplicate keys or values are added
089   */
090  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
091    return RegularImmutableBiMap.fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
092  }
093
094  /**
095   * Returns an immutable map containing the given entries, in order.
096   *
097   * @throws IllegalArgumentException if duplicate keys or values are added
098   */
099  public static <K, V> ImmutableBiMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
100    return RegularImmutableBiMap.fromEntries(
101        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
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(
110      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
111    return RegularImmutableBiMap.fromEntries(
112        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
113  }
114
115  // looking for of() with > 5 entries? Use the builder instead.
116
117  /**
118   * Returns a new builder. The generated builder is equivalent to the builder
119   * created by the {@link Builder} constructor.
120   */
121  public static <K, V> Builder<K, V> builder() {
122    return new Builder<K, V>();
123  }
124
125  /**
126   * A builder for creating immutable bimap instances, especially {@code public
127   * static final} bimaps ("constant bimaps"). Example: <pre>   {@code
128   *
129   *   static final ImmutableBiMap<String, Integer> WORD_TO_INT =
130   *       new ImmutableBiMap.Builder<String, Integer>()
131   *           .put("one", 1)
132   *           .put("two", 2)
133   *           .put("three", 3)
134   *           .build();}</pre>
135   *
136   * <p>For <i>small</i> immutable bimaps, the {@code ImmutableBiMap.of()} methods
137   * are even more convenient.
138   *
139   * <p>Builder instances can be reused - it is safe to call {@link #build}
140   * multiple times to build multiple bimaps in series. Each bimap is a superset
141   * of the bimaps created before it.
142   *
143   * @since 2.0
144   */
145  public static final class Builder<K, V> extends ImmutableMap.Builder<K, V> {
146
147    /**
148     * Creates a new builder. The returned builder is equivalent to the builder
149     * generated by {@link ImmutableBiMap#builder}.
150     */
151    public Builder() {}
152
153    Builder(int size) {
154      super(size);
155    }
156
157    /**
158     * Associates {@code key} with {@code value} in the built bimap. Duplicate
159     * keys or values are not allowed, and will cause {@link #build} to fail.
160     */
161    @CanIgnoreReturnValue
162    @Override
163    public Builder<K, V> put(K key, V value) {
164      super.put(key, value);
165      return this;
166    }
167
168    /**
169     * Adds the given {@code entry} to the bimap.  Duplicate keys or values
170     * are not allowed, and will cause {@link #build} to fail.
171     *
172     * @since 19.0
173     */
174    @CanIgnoreReturnValue
175    @Override
176    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
177      super.put(entry);
178      return this;
179    }
180
181    /**
182     * Associates all of the given map's keys and values in the built bimap.
183     * Duplicate keys or values are not allowed, and will cause {@link #build}
184     * to fail.
185     *
186     * @throws NullPointerException if any key or value in {@code map} is null
187     */
188    @CanIgnoreReturnValue
189    @Override
190    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
191      super.putAll(map);
192      return this;
193    }
194
195    /**
196     * Adds all of the given entries to the built bimap.  Duplicate keys or
197     * values are not allowed, and will cause {@link #build} to fail.
198     *
199     * @throws NullPointerException if any key, value, or entry is null
200     * @since 19.0
201     */
202    @CanIgnoreReturnValue
203    @Beta
204    @Override
205    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
206      super.putAll(entries);
207      return this;
208    }
209
210    /**
211     * Configures this {@code Builder} to order entries by value according to the specified
212     * comparator.
213     *
214     * <p>The sort order is stable, that is, if two entries have values that compare
215     * as equivalent, the entry that was inserted first will be first in the built map's
216     * iteration order.
217     *
218     * @throws IllegalStateException if this method was already called
219     * @since 19.0
220     */
221    @CanIgnoreReturnValue
222    @Beta
223    @Override
224    public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
225      super.orderEntriesByValue(valueComparator);
226      return this;
227    }
228
229    @CanIgnoreReturnValue
230    Builder<K, V> combine(ImmutableMap.Builder<K, V> builder) {
231      super.combine(builder);
232      return this;
233    }
234
235    /**
236     * Returns a newly-created immutable bimap.
237     *
238     * @throws IllegalArgumentException if duplicate keys or values were added
239     */
240    @Override
241    public ImmutableBiMap<K, V> build() {
242      switch (size) {
243        case 0:
244          return of();
245        case 1:
246          return of(entries[0].getKey(), entries[0].getValue());
247        default:
248          /*
249           * If entries is full, then this implementation may end up using the entries array
250           * directly and writing over the entry objects with non-terminal entries, but this is
251           * safe; if this Builder is used further, it will grow the entries array (so it can't
252           * affect the original array), and future build() calls will always copy any entry
253           * objects that cannot be safely reused.
254           */
255          if (valueComparator != null) {
256            if (entriesUsed) {
257              entries = Arrays.copyOf(entries, size);
258            }
259            Arrays.sort(
260                entries,
261                0,
262                size,
263                Ordering.from(valueComparator).onResultOf(Maps.<V>valueFunction()));
264          }
265          entriesUsed = size == entries.length;
266          return RegularImmutableBiMap.fromEntryArray(size, entries);
267      }
268    }
269  }
270
271  /**
272   * Returns an immutable bimap containing the same entries as {@code map}. If
273   * {@code map} somehow contains entries with duplicate keys (for example, if
274   * it is a {@code SortedMap} whose comparator is not <i>consistent with
275   * equals</i>), the results of this method are undefined.
276   *
277   * <p>Despite the method name, this method attempts to avoid actually copying
278   * the data when it is safe to do so. The exact circumstances under which a
279   * copy will or will not be performed are undocumented and subject to change.
280   *
281   * @throws IllegalArgumentException if two keys have the same value
282   * @throws NullPointerException if any key or value in {@code map} is null
283   */
284  public static <K, V> ImmutableBiMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
285    if (map instanceof ImmutableBiMap) {
286      @SuppressWarnings("unchecked") // safe since map is not writable
287      ImmutableBiMap<K, V> bimap = (ImmutableBiMap<K, V>) map;
288      // TODO(lowasser): if we need to make a copy of a BiMap because the
289      // forward map is a view, don't make a copy of the non-view delegate map
290      if (!bimap.isPartialView()) {
291        return bimap;
292      }
293    }
294    return copyOf(map.entrySet());
295  }
296
297  /**
298   * Returns an immutable bimap containing the given entries.
299   *
300   * @throws IllegalArgumentException if two keys have the same value or two
301   *         values have the same key
302   * @throws NullPointerException if any key, value, or entry is null
303   * @since 19.0
304   */
305  @Beta
306  public static <K, V> ImmutableBiMap<K, V> copyOf(
307      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
308    @SuppressWarnings("unchecked") // we'll only be using getKey and getValue, which are covariant
309    Entry<K, V>[] entryArray = (Entry<K, V>[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
310    switch (entryArray.length) {
311      case 0:
312        return of();
313      case 1:
314        Entry<K, V> entry = entryArray[0];
315        return of(entry.getKey(), entry.getValue());
316      default:
317        /*
318         * The current implementation will end up using entryArray directly, though it will write
319         * over the (arbitrary, potentially mutable) Entry objects actually stored in entryArray.
320         */
321        return RegularImmutableBiMap.fromEntries(entryArray);
322    }
323  }
324
325  ImmutableBiMap() {}
326
327  /**
328   * {@inheritDoc}
329   *
330   * <p>The inverse of an {@code ImmutableBiMap} is another
331   * {@code ImmutableBiMap}.
332   */
333  @Override
334  public abstract ImmutableBiMap<V, K> inverse();
335
336  /**
337   * Returns an immutable set of the values in this map. The values are in the
338   * same order as the parameters used to build this map.
339   */
340  @Override
341  public ImmutableSet<V> values() {
342    return inverse().keySet();
343  }
344
345  /**
346   * Guaranteed to throw an exception and leave the bimap unmodified.
347   *
348   * @throws UnsupportedOperationException always
349   * @deprecated Unsupported operation.
350   */
351  @CanIgnoreReturnValue
352  @Deprecated
353  @Override
354  public V forcePut(K key, V value) {
355    throw new UnsupportedOperationException();
356  }
357
358  /**
359   * Serialized type for all ImmutableBiMap instances. It captures the logical
360   * contents and they are reconstructed using public factory methods. This
361   * ensures that the implementation types remain as implementation details.
362   *
363   * Since the bimap is immutable, ImmutableBiMap doesn't require special logic
364   * for keeping the bimap and its inverse in sync during serialization, the way
365   * AbstractBiMap does.
366   */
367  private static class SerializedForm extends ImmutableMap.SerializedForm {
368    SerializedForm(ImmutableBiMap<?, ?> bimap) {
369      super(bimap);
370    }
371
372    @Override
373    Object readResolve() {
374      Builder<Object, Object> builder = new Builder<Object, Object>();
375      return createMap(builder);
376    }
377
378    private static final long serialVersionUID = 0;
379  }
380
381  @Override
382  Object writeReplace() {
383    return new SerializedForm(this);
384  }
385}