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