001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
019import static com.google.common.collect.NullnessCasts.unsafeNull;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.annotations.GwtIncompatible;
023import com.google.common.annotations.J2ktIncompatible;
024import com.google.common.base.Objects;
025import com.google.errorprone.annotations.CanIgnoreReturnValue;
026import com.google.errorprone.annotations.concurrent.LazyInit;
027import com.google.j2objc.annotations.RetainedWith;
028import java.io.IOException;
029import java.io.ObjectInputStream;
030import java.io.ObjectOutputStream;
031import java.io.Serializable;
032import java.util.AbstractMap;
033import java.util.AbstractSet;
034import java.util.Arrays;
035import java.util.ConcurrentModificationException;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.NoSuchElementException;
039import java.util.Set;
040import org.checkerframework.checker.nullness.qual.Nullable;
041
042/**
043 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
044 * {@code HashBiMap} and its inverse are both serializable.
045 *
046 * <p>This implementation guarantees insertion-based iteration order of its keys.
047 *
048 * <p>See the Guava User Guide article on <a href=
049 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap">{@code BiMap} </a>.
050 *
051 * @author Louis Wasserman
052 * @author Mike Bostock
053 * @since 2.0
054 */
055@GwtCompatible
056public final class HashBiMap<K extends @Nullable Object, V extends @Nullable Object>
057    extends AbstractMap<K, V> implements BiMap<K, V>, Serializable {
058
059  /** Returns a new, empty {@code HashBiMap} with the default initial capacity (16). */
060  public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create() {
061    return create(16);
062  }
063
064  /**
065   * Constructs a new, empty bimap with the specified expected size.
066   *
067   * @param expectedSize the expected number of entries
068   * @throws IllegalArgumentException if the specified expected size is negative
069   */
070  public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create(
071      int expectedSize) {
072    return new HashBiMap<>(expectedSize);
073  }
074
075  /**
076   * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
077   * initial capacity sufficient to hold the mappings in the specified map.
078   */
079  public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create(
080      Map<? extends K, ? extends V> map) {
081    HashBiMap<K, V> bimap = create(map.size());
082    bimap.putAll(map);
083    return bimap;
084  }
085
086  private static final int ABSENT = -1;
087  private static final int ENDPOINT = -2;
088
089  /** Maps an "entry" to the key of that entry. */
090  transient @Nullable K[] keys;
091  /** Maps an "entry" to the value of that entry. */
092  transient @Nullable V[] values;
093
094  transient int size;
095  transient int modCount;
096  /** Maps a bucket to the "entry" of its first element. */
097  private transient int[] hashTableKToV;
098  /** Maps a bucket to the "entry" of its first element. */
099  private transient int[] hashTableVToK;
100  /** Maps an "entry" to the "entry" that follows it in its bucket. */
101  private transient int[] nextInBucketKToV;
102  /** Maps an "entry" to the "entry" that follows it in its bucket. */
103  private transient int[] nextInBucketVToK;
104  /** The "entry" of the first element in insertion order. */
105  private transient int firstInInsertionOrder;
106  /** The "entry" of the last element in insertion order. */
107  private transient int lastInInsertionOrder;
108  /** Maps an "entry" to the "entry" that precedes it in insertion order. */
109  private transient int[] prevInInsertionOrder;
110  /** Maps an "entry" to the "entry" that follows it in insertion order. */
111  private transient int[] nextInInsertionOrder;
112
113  private HashBiMap(int expectedSize) {
114    init(expectedSize);
115  }
116
117  @SuppressWarnings("unchecked")
118  void init(int expectedSize) {
119    CollectPreconditions.checkNonnegative(expectedSize, "expectedSize");
120    int tableSize = Hashing.closedTableSize(expectedSize, 1.0);
121    size = 0;
122
123    keys = (K[]) new Object[expectedSize];
124    values = (V[]) new Object[expectedSize];
125
126    hashTableKToV = createFilledWithAbsent(tableSize);
127    hashTableVToK = createFilledWithAbsent(tableSize);
128    nextInBucketKToV = createFilledWithAbsent(expectedSize);
129    nextInBucketVToK = createFilledWithAbsent(expectedSize);
130
131    firstInInsertionOrder = ENDPOINT;
132    lastInInsertionOrder = ENDPOINT;
133
134    prevInInsertionOrder = createFilledWithAbsent(expectedSize);
135    nextInInsertionOrder = createFilledWithAbsent(expectedSize);
136  }
137
138  /** Returns an int array of the specified size, filled with ABSENT. */
139  private static int[] createFilledWithAbsent(int size) {
140    int[] array = new int[size];
141    Arrays.fill(array, ABSENT);
142    return array;
143  }
144
145  /** Equivalent to {@code Arrays.copyOf(array, newSize)}, save that the new elements are ABSENT. */
146  private static int[] expandAndFillWithAbsent(int[] array, int newSize) {
147    int oldSize = array.length;
148    int[] result = Arrays.copyOf(array, newSize);
149    Arrays.fill(result, oldSize, newSize, ABSENT);
150    return result;
151  }
152
153  @Override
154  public int size() {
155    return size;
156  }
157
158  /**
159   * Ensures that all of the internal structures in the HashBiMap are ready for this many elements.
160   */
161  private void ensureCapacity(int minCapacity) {
162    if (nextInBucketKToV.length < minCapacity) {
163      int oldCapacity = nextInBucketKToV.length;
164      int newCapacity = ImmutableCollection.Builder.expandedCapacity(oldCapacity, minCapacity);
165
166      keys = Arrays.copyOf(keys, newCapacity);
167      values = Arrays.copyOf(values, newCapacity);
168      nextInBucketKToV = expandAndFillWithAbsent(nextInBucketKToV, newCapacity);
169      nextInBucketVToK = expandAndFillWithAbsent(nextInBucketVToK, newCapacity);
170      prevInInsertionOrder = expandAndFillWithAbsent(prevInInsertionOrder, newCapacity);
171      nextInInsertionOrder = expandAndFillWithAbsent(nextInInsertionOrder, newCapacity);
172    }
173
174    if (hashTableKToV.length < minCapacity) {
175      int newTableSize = Hashing.closedTableSize(minCapacity, 1.0);
176      hashTableKToV = createFilledWithAbsent(newTableSize);
177      hashTableVToK = createFilledWithAbsent(newTableSize);
178
179      for (int entryToRehash = 0; entryToRehash < size; entryToRehash++) {
180        int keyHash = Hashing.smearedHash(keys[entryToRehash]);
181        int keyBucket = bucket(keyHash);
182        nextInBucketKToV[entryToRehash] = hashTableKToV[keyBucket];
183        hashTableKToV[keyBucket] = entryToRehash;
184
185        int valueHash = Hashing.smearedHash(values[entryToRehash]);
186        int valueBucket = bucket(valueHash);
187        nextInBucketVToK[entryToRehash] = hashTableVToK[valueBucket];
188        hashTableVToK[valueBucket] = entryToRehash;
189      }
190    }
191  }
192
193  /**
194   * Returns the bucket (in either the K-to-V or V-to-K tables) where elements with the specified
195   * hash could be found, if present, or could be inserted.
196   */
197  private int bucket(int hash) {
198    return hash & (hashTableKToV.length - 1);
199  }
200
201  /** Given a key, returns the index of the entry in the tables, or ABSENT if not found. */
202  int findEntryByKey(@Nullable Object key) {
203    return findEntryByKey(key, Hashing.smearedHash(key));
204  }
205
206  /**
207   * Given a key and its hash, returns the index of the entry in the tables, or ABSENT if not found.
208   */
209  int findEntryByKey(@Nullable Object key, int keyHash) {
210    return findEntry(key, keyHash, hashTableKToV, nextInBucketKToV, keys);
211  }
212
213  /** Given a value, returns the index of the entry in the tables, or ABSENT if not found. */
214  int findEntryByValue(@Nullable Object value) {
215    return findEntryByValue(value, Hashing.smearedHash(value));
216  }
217
218  /**
219   * Given a value and its hash, returns the index of the entry in the tables, or ABSENT if not
220   * found.
221   */
222  int findEntryByValue(@Nullable Object value, int valueHash) {
223    return findEntry(value, valueHash, hashTableVToK, nextInBucketVToK, values);
224  }
225
226  int findEntry(
227      @Nullable Object o,
228      int oHash,
229      int[] hashTable,
230      int[] nextInBucket,
231      @Nullable Object[] array) {
232    for (int entry = hashTable[bucket(oHash)]; entry != ABSENT; entry = nextInBucket[entry]) {
233      if (Objects.equal(array[entry], o)) {
234        return entry;
235      }
236    }
237    return ABSENT;
238  }
239
240  @Override
241  public boolean containsKey(@Nullable Object key) {
242    return findEntryByKey(key) != ABSENT;
243  }
244
245  /**
246   * Returns {@code true} if this BiMap contains an entry whose value is equal to {@code value} (or,
247   * equivalently, if this inverse view contains a key that is equal to {@code value}).
248   *
249   * <p>Due to the property that values in a BiMap are unique, this will tend to execute in
250   * faster-than-linear time.
251   *
252   * @param value the object to search for in the values of this BiMap
253   * @return true if a mapping exists from a key to the specified value
254   */
255  @Override
256  public boolean containsValue(@Nullable Object value) {
257    return findEntryByValue(value) != ABSENT;
258  }
259
260  @Override
261  public @Nullable V get(@Nullable Object key) {
262    int entry = findEntryByKey(key);
263    return (entry == ABSENT) ? null : values[entry];
264  }
265
266  @Nullable K getInverse(@Nullable Object value) {
267    int entry = findEntryByValue(value);
268    return (entry == ABSENT) ? null : keys[entry];
269  }
270
271  @Override
272  @CanIgnoreReturnValue
273  public @Nullable V put(@ParametricNullness K key, @ParametricNullness V value) {
274    return put(key, value, false);
275  }
276
277  @Nullable V put(@ParametricNullness K key, @ParametricNullness V value, boolean force) {
278    int keyHash = Hashing.smearedHash(key);
279    int entryForKey = findEntryByKey(key, keyHash);
280    if (entryForKey != ABSENT) {
281      V oldValue = values[entryForKey];
282      if (Objects.equal(oldValue, value)) {
283        return value;
284      } else {
285        replaceValueInEntry(entryForKey, value, force);
286        return oldValue;
287      }
288    }
289
290    int valueHash = Hashing.smearedHash(value);
291    int valueEntry = findEntryByValue(value, valueHash);
292    if (force) {
293      if (valueEntry != ABSENT) {
294        removeEntryValueHashKnown(valueEntry, valueHash);
295      }
296    } else {
297      checkArgument(valueEntry == ABSENT, "Value already present: %s", value);
298    }
299
300    ensureCapacity(size + 1);
301    keys[size] = key;
302    values[size] = value;
303
304    insertIntoTableKToV(size, keyHash);
305    insertIntoTableVToK(size, valueHash);
306
307    setSucceeds(lastInInsertionOrder, size);
308    setSucceeds(size, ENDPOINT);
309    size++;
310    modCount++;
311    return null;
312  }
313
314  @Override
315  @CanIgnoreReturnValue
316  public @Nullable V forcePut(@ParametricNullness K key, @ParametricNullness V value) {
317    return put(key, value, true);
318  }
319
320  @CanIgnoreReturnValue
321  @Nullable K putInverse(@ParametricNullness V value, @ParametricNullness K key, boolean force) {
322    int valueHash = Hashing.smearedHash(value);
323    int entryForValue = findEntryByValue(value, valueHash);
324    if (entryForValue != ABSENT) {
325      K oldKey = keys[entryForValue];
326      if (Objects.equal(oldKey, key)) {
327        return key;
328      } else {
329        replaceKeyInEntry(entryForValue, key, force);
330        return oldKey;
331      }
332    }
333
334    int predecessor = lastInInsertionOrder;
335    int keyHash = Hashing.smearedHash(key);
336    int keyEntry = findEntryByKey(key, keyHash);
337    if (force) {
338      if (keyEntry != ABSENT) {
339        predecessor = prevInInsertionOrder[keyEntry];
340        removeEntryKeyHashKnown(keyEntry, keyHash);
341      }
342    } else {
343      checkArgument(keyEntry == ABSENT, "Key already present: %s", key);
344    }
345
346    // insertion point for new entry is after predecessor
347    // note predecessor must still be a valid entry: either we deleted an entry that was *not*
348    // predecessor, or we didn't delete anything
349
350    ensureCapacity(size + 1);
351    keys[size] = key;
352    values[size] = value;
353
354    insertIntoTableKToV(size, keyHash);
355    insertIntoTableVToK(size, valueHash);
356
357    int successor =
358        (predecessor == ENDPOINT) ? firstInInsertionOrder : nextInInsertionOrder[predecessor];
359    setSucceeds(predecessor, size);
360    setSucceeds(size, successor);
361    size++;
362    modCount++;
363    return null;
364  }
365
366  /**
367   * Updates the pointers of the insertion order linked list so that {@code next} follows {@code
368   * prev}. {@code ENDPOINT} represents either the first or last entry in the entire map (as
369   * appropriate).
370   */
371  private void setSucceeds(int prev, int next) {
372    if (prev == ENDPOINT) {
373      firstInInsertionOrder = next;
374    } else {
375      nextInInsertionOrder[prev] = next;
376    }
377    if (next == ENDPOINT) {
378      lastInInsertionOrder = prev;
379    } else {
380      prevInInsertionOrder[next] = prev;
381    }
382  }
383
384  /**
385   * Updates the K-to-V hash table to include the entry at the specified index, which is assumed to
386   * have not yet been added.
387   */
388  private void insertIntoTableKToV(int entry, int keyHash) {
389    checkArgument(entry != ABSENT);
390    int keyBucket = bucket(keyHash);
391    nextInBucketKToV[entry] = hashTableKToV[keyBucket];
392    hashTableKToV[keyBucket] = entry;
393  }
394
395  /**
396   * Updates the V-to-K hash table to include the entry at the specified index, which is assumed to
397   * have not yet been added.
398   */
399  private void insertIntoTableVToK(int entry, int valueHash) {
400    checkArgument(entry != ABSENT);
401    int valueBucket = bucket(valueHash);
402    nextInBucketVToK[entry] = hashTableVToK[valueBucket];
403    hashTableVToK[valueBucket] = entry;
404  }
405
406  /**
407   * Updates the K-to-V hash table to remove the entry at the specified index, which is assumed to
408   * be present. Does not update any other data structures.
409   */
410  private void deleteFromTableKToV(int entry, int keyHash) {
411    checkArgument(entry != ABSENT);
412    int keyBucket = bucket(keyHash);
413
414    if (hashTableKToV[keyBucket] == entry) {
415      hashTableKToV[keyBucket] = nextInBucketKToV[entry];
416      nextInBucketKToV[entry] = ABSENT;
417      return;
418    }
419
420    int prevInBucket = hashTableKToV[keyBucket];
421    for (int entryInBucket = nextInBucketKToV[prevInBucket];
422        entryInBucket != ABSENT;
423        entryInBucket = nextInBucketKToV[entryInBucket]) {
424      if (entryInBucket == entry) {
425        nextInBucketKToV[prevInBucket] = nextInBucketKToV[entry];
426        nextInBucketKToV[entry] = ABSENT;
427        return;
428      }
429      prevInBucket = entryInBucket;
430    }
431    throw new AssertionError("Expected to find entry with key " + keys[entry]);
432  }
433
434  /**
435   * Updates the V-to-K hash table to remove the entry at the specified index, which is assumed to
436   * be present. Does not update any other data structures.
437   */
438  private void deleteFromTableVToK(int entry, int valueHash) {
439    checkArgument(entry != ABSENT);
440    int valueBucket = bucket(valueHash);
441
442    if (hashTableVToK[valueBucket] == entry) {
443      hashTableVToK[valueBucket] = nextInBucketVToK[entry];
444      nextInBucketVToK[entry] = ABSENT;
445      return;
446    }
447
448    int prevInBucket = hashTableVToK[valueBucket];
449    for (int entryInBucket = nextInBucketVToK[prevInBucket];
450        entryInBucket != ABSENT;
451        entryInBucket = nextInBucketVToK[entryInBucket]) {
452      if (entryInBucket == entry) {
453        nextInBucketVToK[prevInBucket] = nextInBucketVToK[entry];
454        nextInBucketVToK[entry] = ABSENT;
455        return;
456      }
457      prevInBucket = entryInBucket;
458    }
459    throw new AssertionError("Expected to find entry with value " + values[entry]);
460  }
461
462  /**
463   * Updates the specified entry to point to the new value: removes the old value from the V-to-K
464   * mapping and puts the new one in. The entry does not move in the insertion order of the bimap.
465   */
466  private void replaceValueInEntry(int entry, @ParametricNullness V newValue, boolean force) {
467    checkArgument(entry != ABSENT);
468    int newValueHash = Hashing.smearedHash(newValue);
469    int newValueIndex = findEntryByValue(newValue, newValueHash);
470    if (newValueIndex != ABSENT) {
471      if (force) {
472        removeEntryValueHashKnown(newValueIndex, newValueHash);
473        if (entry == size) { // this entry got moved to newValueIndex
474          entry = newValueIndex;
475        }
476      } else {
477        throw new IllegalArgumentException("Value already present in map: " + newValue);
478      }
479    }
480    // we do *not* update insertion order, and it isn't a structural modification!
481    deleteFromTableVToK(entry, Hashing.smearedHash(values[entry]));
482    values[entry] = newValue;
483    insertIntoTableVToK(entry, newValueHash);
484  }
485
486  /**
487   * Updates the specified entry to point to the new value: removes the old value from the V-to-K
488   * mapping and puts the new one in. The entry is moved to the end of the insertion order, or to
489   * the position of the new key if it was previously present.
490   */
491  private void replaceKeyInEntry(int entry, @ParametricNullness K newKey, boolean force) {
492    checkArgument(entry != ABSENT);
493    int newKeyHash = Hashing.smearedHash(newKey);
494    int newKeyIndex = findEntryByKey(newKey, newKeyHash);
495
496    int newPredecessor = lastInInsertionOrder;
497    int newSuccessor = ENDPOINT;
498    if (newKeyIndex != ABSENT) {
499      if (force) {
500        newPredecessor = prevInInsertionOrder[newKeyIndex];
501        newSuccessor = nextInInsertionOrder[newKeyIndex];
502        removeEntryKeyHashKnown(newKeyIndex, newKeyHash);
503        if (entry == size) { // this entry got moved to newKeyIndex
504          entry = newKeyIndex;
505        }
506      } else {
507        throw new IllegalArgumentException("Key already present in map: " + newKey);
508      }
509    }
510    if (newPredecessor == entry) {
511      newPredecessor = prevInInsertionOrder[entry];
512    } else if (newPredecessor == size) {
513      newPredecessor = newKeyIndex;
514    }
515
516    if (newSuccessor == entry) {
517      newSuccessor = nextInInsertionOrder[entry];
518    } else if (newSuccessor == size) {
519      newSuccessor = newKeyIndex;
520    }
521
522    int oldPredecessor = prevInInsertionOrder[entry];
523    int oldSuccessor = nextInInsertionOrder[entry];
524    setSucceeds(oldPredecessor, oldSuccessor); // remove from insertion order linked list
525
526    deleteFromTableKToV(entry, Hashing.smearedHash(keys[entry]));
527    keys[entry] = newKey;
528    insertIntoTableKToV(entry, Hashing.smearedHash(newKey));
529
530    // insert into insertion order linked list, usually at the end
531    setSucceeds(newPredecessor, entry);
532    setSucceeds(entry, newSuccessor);
533  }
534
535  @Override
536  @CanIgnoreReturnValue
537  public @Nullable V remove(@Nullable Object key) {
538    int keyHash = Hashing.smearedHash(key);
539    int entry = findEntryByKey(key, keyHash);
540    if (entry == ABSENT) {
541      return null;
542    } else {
543      V value = values[entry];
544      removeEntryKeyHashKnown(entry, keyHash);
545      return value;
546    }
547  }
548
549  @Nullable K removeInverse(@Nullable Object value) {
550    int valueHash = Hashing.smearedHash(value);
551    int entry = findEntryByValue(value, valueHash);
552    if (entry == ABSENT) {
553      return null;
554    } else {
555      K key = keys[entry];
556      removeEntryValueHashKnown(entry, valueHash);
557      return key;
558    }
559  }
560
561  /** Removes the entry at the specified index with no additional data. */
562  void removeEntry(int entry) {
563    removeEntryKeyHashKnown(entry, Hashing.smearedHash(keys[entry]));
564  }
565
566  /** Removes the entry at the specified index, given the hash of its key and value. */
567  private void removeEntry(int entry, int keyHash, int valueHash) {
568    checkArgument(entry != ABSENT);
569    deleteFromTableKToV(entry, keyHash);
570    deleteFromTableVToK(entry, valueHash);
571
572    int oldPredecessor = prevInInsertionOrder[entry];
573    int oldSuccessor = nextInInsertionOrder[entry];
574    setSucceeds(oldPredecessor, oldSuccessor);
575
576    moveEntryToIndex(size - 1, entry);
577    keys[size - 1] = null;
578    values[size - 1] = null;
579    size--;
580    modCount++;
581  }
582
583  /** Removes the entry at the specified index, given the hash of its key. */
584  void removeEntryKeyHashKnown(int entry, int keyHash) {
585    removeEntry(entry, keyHash, Hashing.smearedHash(values[entry]));
586  }
587
588  /** Removes the entry at the specified index, given the hash of its value. */
589  void removeEntryValueHashKnown(int entry, int valueHash) {
590    removeEntry(entry, Hashing.smearedHash(keys[entry]), valueHash);
591  }
592
593  /**
594   * Moves the entry previously positioned at {@code src} to {@code dest}. Assumes the entry
595   * previously at {@code src} has already been removed from the data structures.
596   */
597  private void moveEntryToIndex(int src, int dest) {
598    if (src == dest) {
599      return;
600    }
601    int predecessor = prevInInsertionOrder[src];
602    int successor = nextInInsertionOrder[src];
603    setSucceeds(predecessor, dest);
604    setSucceeds(dest, successor);
605
606    K key = keys[src];
607    V value = values[src];
608
609    keys[dest] = key;
610    values[dest] = value;
611
612    // update pointers in hashTableKToV
613    int keyHash = Hashing.smearedHash(key);
614    int keyBucket = bucket(keyHash);
615    if (hashTableKToV[keyBucket] == src) {
616      hashTableKToV[keyBucket] = dest;
617    } else {
618      int prevInBucket = hashTableKToV[keyBucket];
619      for (int entryInBucket = nextInBucketKToV[prevInBucket];
620          /* should never reach end */ ;
621          entryInBucket = nextInBucketKToV[entryInBucket]) {
622        if (entryInBucket == src) {
623          nextInBucketKToV[prevInBucket] = dest;
624          break;
625        }
626        prevInBucket = entryInBucket;
627      }
628    }
629    nextInBucketKToV[dest] = nextInBucketKToV[src];
630    nextInBucketKToV[src] = ABSENT;
631
632    // update pointers in hashTableVToK
633    int valueHash = Hashing.smearedHash(value);
634    int valueBucket = bucket(valueHash);
635    if (hashTableVToK[valueBucket] == src) {
636      hashTableVToK[valueBucket] = dest;
637    } else {
638      int prevInBucket = hashTableVToK[valueBucket];
639      for (int entryInBucket = nextInBucketVToK[prevInBucket];
640          /* should never reach end*/ ;
641          entryInBucket = nextInBucketVToK[entryInBucket]) {
642        if (entryInBucket == src) {
643          nextInBucketVToK[prevInBucket] = dest;
644          break;
645        }
646        prevInBucket = entryInBucket;
647      }
648    }
649    nextInBucketVToK[dest] = nextInBucketVToK[src];
650    nextInBucketVToK[src] = ABSENT;
651  }
652
653  @Override
654  public void clear() {
655    Arrays.fill(keys, 0, size, null);
656    Arrays.fill(values, 0, size, null);
657    Arrays.fill(hashTableKToV, ABSENT);
658    Arrays.fill(hashTableVToK, ABSENT);
659    Arrays.fill(nextInBucketKToV, 0, size, ABSENT);
660    Arrays.fill(nextInBucketVToK, 0, size, ABSENT);
661    Arrays.fill(prevInInsertionOrder, 0, size, ABSENT);
662    Arrays.fill(nextInInsertionOrder, 0, size, ABSENT);
663    size = 0;
664    firstInInsertionOrder = ENDPOINT;
665    lastInInsertionOrder = ENDPOINT;
666    modCount++;
667  }
668
669  /** Shared supertype of keySet, values, entrySet, and inverse.entrySet. */
670  abstract static class View<
671          K extends @Nullable Object, V extends @Nullable Object, T extends @Nullable Object>
672      extends AbstractSet<T> {
673    final HashBiMap<K, V> biMap;
674
675    View(HashBiMap<K, V> biMap) {
676      this.biMap = biMap;
677    }
678
679    @ParametricNullness
680    abstract T forEntry(int entry);
681
682    @Override
683    public Iterator<T> iterator() {
684      return new Iterator<T>() {
685        private int index = biMap.firstInInsertionOrder;
686        private int indexToRemove = ABSENT;
687        private int expectedModCount = biMap.modCount;
688
689        // Calls to setValue on inverse entries can move already-visited entries to the end.
690        // Make sure we don't visit those.
691        private int remaining = biMap.size;
692
693        private void checkForComodification() {
694          if (biMap.modCount != expectedModCount) {
695            throw new ConcurrentModificationException();
696          }
697        }
698
699        @Override
700        public boolean hasNext() {
701          checkForComodification();
702          return index != ENDPOINT && remaining > 0;
703        }
704
705        @Override
706        @ParametricNullness
707        public T next() {
708          if (!hasNext()) {
709            throw new NoSuchElementException();
710          }
711          T result = forEntry(index);
712          indexToRemove = index;
713          index = biMap.nextInInsertionOrder[index];
714          remaining--;
715          return result;
716        }
717
718        @Override
719        public void remove() {
720          checkForComodification();
721          CollectPreconditions.checkRemove(indexToRemove != ABSENT);
722          biMap.removeEntry(indexToRemove);
723          if (index == biMap.size) {
724            index = indexToRemove;
725          }
726          indexToRemove = ABSENT;
727          expectedModCount = biMap.modCount;
728        }
729      };
730    }
731
732    @Override
733    public int size() {
734      return biMap.size;
735    }
736
737    @Override
738    public void clear() {
739      biMap.clear();
740    }
741  }
742
743  @LazyInit private transient Set<K> keySet;
744
745  @Override
746  public Set<K> keySet() {
747    Set<K> result = keySet;
748    return (result == null) ? keySet = new KeySet() : result;
749  }
750
751  final class KeySet extends View<K, V, K> {
752    KeySet() {
753      super(HashBiMap.this);
754    }
755
756    @Override
757    @ParametricNullness
758    K forEntry(int entry) {
759      // The cast is safe because we call forEntry only for indexes that contain entries.
760      return uncheckedCastNullableTToT(keys[entry]);
761    }
762
763    @Override
764    public boolean contains(@Nullable Object o) {
765      return HashBiMap.this.containsKey(o);
766    }
767
768    @Override
769    public boolean remove(@Nullable Object o) {
770      int oHash = Hashing.smearedHash(o);
771      int entry = findEntryByKey(o, oHash);
772      if (entry != ABSENT) {
773        removeEntryKeyHashKnown(entry, oHash);
774        return true;
775      } else {
776        return false;
777      }
778    }
779  }
780
781  @LazyInit private transient Set<V> valueSet;
782
783  @Override
784  public Set<V> values() {
785    Set<V> result = valueSet;
786    return (result == null) ? valueSet = new ValueSet() : result;
787  }
788
789  final class ValueSet extends View<K, V, V> {
790    ValueSet() {
791      super(HashBiMap.this);
792    }
793
794    @Override
795    @ParametricNullness
796    V forEntry(int entry) {
797      // The cast is safe because we call forEntry only for indexes that contain entries.
798      return uncheckedCastNullableTToT(values[entry]);
799    }
800
801    @Override
802    public boolean contains(@Nullable Object o) {
803      return HashBiMap.this.containsValue(o);
804    }
805
806    @Override
807    public boolean remove(@Nullable Object o) {
808      int oHash = Hashing.smearedHash(o);
809      int entry = findEntryByValue(o, oHash);
810      if (entry != ABSENT) {
811        removeEntryValueHashKnown(entry, oHash);
812        return true;
813      } else {
814        return false;
815      }
816    }
817  }
818
819  @LazyInit private transient Set<Entry<K, V>> entrySet;
820
821  @Override
822  public Set<Entry<K, V>> entrySet() {
823    Set<Entry<K, V>> result = entrySet;
824    return (result == null) ? entrySet = new EntrySet() : result;
825  }
826
827  final class EntrySet extends View<K, V, Entry<K, V>> {
828    EntrySet() {
829      super(HashBiMap.this);
830    }
831
832    @Override
833    public boolean contains(@Nullable Object o) {
834      if (o instanceof Entry) {
835        Entry<?, ?> e = (Entry<?, ?>) o;
836        Object k = e.getKey();
837        Object v = e.getValue();
838        int eIndex = findEntryByKey(k);
839        return eIndex != ABSENT && Objects.equal(v, values[eIndex]);
840      }
841      return false;
842    }
843
844    @Override
845    @CanIgnoreReturnValue
846    public boolean remove(@Nullable Object o) {
847      if (o instanceof Entry) {
848        Entry<?, ?> e = (Entry<?, ?>) o;
849        Object k = e.getKey();
850        Object v = e.getValue();
851        int kHash = Hashing.smearedHash(k);
852        int eIndex = findEntryByKey(k, kHash);
853        if (eIndex != ABSENT && Objects.equal(v, values[eIndex])) {
854          removeEntryKeyHashKnown(eIndex, kHash);
855          return true;
856        }
857      }
858      return false;
859    }
860
861    @Override
862    Entry<K, V> forEntry(int entry) {
863      return new EntryForKey(entry);
864    }
865  }
866
867  /**
868   * An {@code Entry} implementation that attempts to follow its key around the map -- that is, if
869   * the key is moved, deleted, or reinserted, it will account for that -- while not doing any extra
870   * work if the key has not moved. One quirk: The {@link #getValue()} method can return {@code
871   * null} even for a map which supposedly does not contain null elements, if the key is not present
872   * when {@code getValue()} is called.
873   */
874  final class EntryForKey extends AbstractMapEntry<K, V> {
875    @ParametricNullness final K key;
876    int index;
877
878    EntryForKey(int index) {
879      // The cast is safe because we call forEntry only for indexes that contain entries.
880      this.key = uncheckedCastNullableTToT(keys[index]);
881      this.index = index;
882    }
883
884    void updateIndex() {
885      if (index == ABSENT || index > size || !Objects.equal(keys[index], key)) {
886        index = findEntryByKey(key);
887      }
888    }
889
890    @Override
891    @ParametricNullness
892    public K getKey() {
893      return key;
894    }
895
896    @Override
897    @ParametricNullness
898    public V getValue() {
899      updateIndex();
900      /*
901       * If the entry has been removed from the map, we return null, even though that might not be a
902       * valid value. That's the best we can do, short of holding a reference to the most recently
903       * seen value. And while we *could* do that, we aren't required to: Map.Entry explicitly says
904       * that behavior is undefined when the backing map is modified through another API. (It even
905       * permits us to throw IllegalStateException. Maybe we should have done that, but we probably
906       * shouldn't change now for fear of breaking people.)
907       *
908       * If the entry is still in the map, then updateIndex ensured that `index` points to the right
909       * element. Because that element is present, uncheckedCastNullableTToT is safe.
910       */
911      return (index == ABSENT) ? unsafeNull() : uncheckedCastNullableTToT(values[index]);
912    }
913
914    @Override
915    @ParametricNullness
916    public V setValue(@ParametricNullness V value) {
917      updateIndex();
918      if (index == ABSENT) {
919        HashBiMap.this.put(key, value);
920        return unsafeNull(); // See the discussion in getValue().
921      }
922      /*
923       * The cast is safe because updateIndex found the entry for this key. (If it hadn't, then we
924       * would have returned above.) Thus, we know that it and its corresponding value are in
925       * position `index`.
926       */
927      V oldValue = uncheckedCastNullableTToT(values[index]);
928      if (Objects.equal(oldValue, value)) {
929        return value;
930      }
931      replaceValueInEntry(index, value, false);
932      return oldValue;
933    }
934  }
935
936  @LazyInit @RetainedWith private transient @Nullable BiMap<V, K> inverse;
937
938  @Override
939  public BiMap<V, K> inverse() {
940    BiMap<V, K> result = inverse;
941    return (result == null) ? inverse = new Inverse<K, V>(this) : result;
942  }
943
944  static class Inverse<K extends @Nullable Object, V extends @Nullable Object>
945      extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
946    private final HashBiMap<K, V> forward;
947
948    Inverse(HashBiMap<K, V> forward) {
949      this.forward = forward;
950    }
951
952    @Override
953    public int size() {
954      return forward.size;
955    }
956
957    @Override
958    public boolean containsKey(@Nullable Object key) {
959      return forward.containsValue(key);
960    }
961
962    @Override
963    public @Nullable K get(@Nullable Object key) {
964      return forward.getInverse(key);
965    }
966
967    @Override
968    public boolean containsValue(@Nullable Object value) {
969      return forward.containsKey(value);
970    }
971
972    @Override
973    @CanIgnoreReturnValue
974    public @Nullable K put(@ParametricNullness V value, @ParametricNullness K key) {
975      return forward.putInverse(value, key, false);
976    }
977
978    @Override
979    @CanIgnoreReturnValue
980    public @Nullable K forcePut(@ParametricNullness V value, @ParametricNullness K key) {
981      return forward.putInverse(value, key, true);
982    }
983
984    @Override
985    public BiMap<K, V> inverse() {
986      return forward;
987    }
988
989    @Override
990    @CanIgnoreReturnValue
991    public @Nullable K remove(@Nullable Object value) {
992      return forward.removeInverse(value);
993    }
994
995    @Override
996    public void clear() {
997      forward.clear();
998    }
999
1000    @Override
1001    public Set<V> keySet() {
1002      return forward.values();
1003    }
1004
1005    @Override
1006    public Set<K> values() {
1007      return forward.keySet();
1008    }
1009
1010    private transient Set<Entry<V, K>> inverseEntrySet;
1011
1012    @Override
1013    public Set<Entry<V, K>> entrySet() {
1014      Set<Entry<V, K>> result = inverseEntrySet;
1015      return (result == null) ? inverseEntrySet = new InverseEntrySet<K, V>(forward) : result;
1016    }
1017
1018    @GwtIncompatible("serialization")
1019    private void readObject(ObjectInputStream in) throws ClassNotFoundException, IOException {
1020      in.defaultReadObject();
1021      this.forward.inverse = this;
1022    }
1023  }
1024
1025  static class InverseEntrySet<K extends @Nullable Object, V extends @Nullable Object>
1026      extends View<K, V, Entry<V, K>> {
1027    InverseEntrySet(HashBiMap<K, V> biMap) {
1028      super(biMap);
1029    }
1030
1031    @Override
1032    public boolean contains(@Nullable Object o) {
1033      if (o instanceof Entry) {
1034        Entry<?, ?> e = (Entry<?, ?>) o;
1035        Object v = e.getKey();
1036        Object k = e.getValue();
1037        int eIndex = biMap.findEntryByValue(v);
1038        return eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k);
1039      }
1040      return false;
1041    }
1042
1043    @Override
1044    public boolean remove(@Nullable Object o) {
1045      if (o instanceof Entry) {
1046        Entry<?, ?> e = (Entry<?, ?>) o;
1047        Object v = e.getKey();
1048        Object k = e.getValue();
1049        int vHash = Hashing.smearedHash(v);
1050        int eIndex = biMap.findEntryByValue(v, vHash);
1051        if (eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k)) {
1052          biMap.removeEntryValueHashKnown(eIndex, vHash);
1053          return true;
1054        }
1055      }
1056      return false;
1057    }
1058
1059    @Override
1060    Entry<V, K> forEntry(int entry) {
1061      return new EntryForValue<K, V>(biMap, entry);
1062    }
1063  }
1064
1065  /**
1066   * An {@code Entry} implementation that attempts to follow its value around the map -- that is, if
1067   * the value is moved, deleted, or reinserted, it will account for that -- while not doing any
1068   * extra work if the value has not moved.
1069   */
1070  static final class EntryForValue<K extends @Nullable Object, V extends @Nullable Object>
1071      extends AbstractMapEntry<V, K> {
1072    final HashBiMap<K, V> biMap;
1073    @ParametricNullness final V value;
1074    int index;
1075
1076    EntryForValue(HashBiMap<K, V> biMap, int index) {
1077      this.biMap = biMap;
1078      // The cast is safe because we call forEntry only for indexes that contain entries.
1079      this.value = uncheckedCastNullableTToT(biMap.values[index]);
1080      this.index = index;
1081    }
1082
1083    private void updateIndex() {
1084      if (index == ABSENT || index > biMap.size || !Objects.equal(value, biMap.values[index])) {
1085        index = biMap.findEntryByValue(value);
1086      }
1087    }
1088
1089    @Override
1090    @ParametricNullness
1091    public V getKey() {
1092      return value;
1093    }
1094
1095    @Override
1096    @ParametricNullness
1097    public K getValue() {
1098      updateIndex();
1099      // For discussion of unsafeNull() and uncheckedCastNullableTToT(), see EntryForKey.getValue().
1100      return (index == ABSENT) ? unsafeNull() : uncheckedCastNullableTToT(biMap.keys[index]);
1101    }
1102
1103    @Override
1104    @ParametricNullness
1105    public K setValue(@ParametricNullness K key) {
1106      updateIndex();
1107      if (index == ABSENT) {
1108        biMap.putInverse(value, key, false);
1109        return unsafeNull(); // see EntryForKey.setValue()
1110      }
1111      K oldKey = uncheckedCastNullableTToT(biMap.keys[index]); // see EntryForKey.setValue()
1112      if (Objects.equal(oldKey, key)) {
1113        return key;
1114      }
1115      biMap.replaceKeyInEntry(index, key, false);
1116      return oldKey;
1117    }
1118  }
1119
1120  /**
1121   * @serialData the number of entries, first key, first value, second key, second value, and so on.
1122   */
1123  @GwtIncompatible // java.io.ObjectOutputStream
1124  @J2ktIncompatible
1125  private void writeObject(ObjectOutputStream stream) throws IOException {
1126    stream.defaultWriteObject();
1127    Serialization.writeMap(this, stream);
1128  }
1129
1130  @GwtIncompatible // java.io.ObjectInputStream
1131  @J2ktIncompatible
1132  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
1133    stream.defaultReadObject();
1134    int size = Serialization.readCount(stream);
1135    init(16); // resist hostile attempts to allocate gratuitous heap
1136    Serialization.populateMap(this, stream, size);
1137  }
1138}