Source code

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