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