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.j2objc.annotations.RetainedWith;
024import java.io.IOException;
025import java.io.ObjectInputStream;
026import java.io.ObjectOutputStream;
027import java.io.Serializable;
028import java.util.AbstractMap;
029import java.util.AbstractSet;
030import java.util.Arrays;
031import java.util.ConcurrentModificationException;
032import java.util.Iterator;
033import java.util.Map;
034import java.util.NoSuchElementException;
035import java.util.Set;
036import org.checkerframework.checker.nullness.compatqual.MonotonicNonNullDecl;
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  @Override
236  public boolean containsValue(@NullableDecl Object value) {
237    return findEntryByValue(value) != ABSENT;
238  }
239
240  @Override
241  @NullableDecl
242  public V get(@NullableDecl Object key) {
243    int entry = findEntryByKey(key);
244    return (entry == ABSENT) ? null : values[entry];
245  }
246
247  @NullableDecl
248  K getInverse(@NullableDecl Object value) {
249    int entry = findEntryByValue(value);
250    return (entry == ABSENT) ? null : keys[entry];
251  }
252
253  @Override
254  @CanIgnoreReturnValue
255  public V put(@NullableDecl K key, @NullableDecl V value) {
256    return put(key, value, false);
257  }
258
259  @Override
260  @NullableDecl
261  @CanIgnoreReturnValue
262  public V forcePut(@NullableDecl K key, @NullableDecl V value) {
263    return put(key, value, true);
264  }
265
266  @NullableDecl
267  V put(@NullableDecl K key, @NullableDecl V value, boolean force) {
268    int keyHash = Hashing.smearedHash(key);
269    int entryForKey = findEntryByKey(key, keyHash);
270    if (entryForKey != ABSENT) {
271      V oldValue = values[entryForKey];
272      if (Objects.equal(oldValue, value)) {
273        return value;
274      } else {
275        replaceValueInEntry(entryForKey, value, force);
276        return oldValue;
277      }
278    }
279
280    int valueHash = Hashing.smearedHash(value);
281    int valueEntry = findEntryByValue(value, valueHash);
282    if (force) {
283      if (valueEntry != ABSENT) {
284        removeEntryValueHashKnown(valueEntry, valueHash);
285      }
286    } else {
287      checkArgument(valueEntry == ABSENT, "Value already present: %s", value);
288    }
289
290    ensureCapacity(size + 1);
291    keys[size] = key;
292    values[size] = value;
293
294    insertIntoTableKToV(size, keyHash);
295    insertIntoTableVToK(size, valueHash);
296
297    setSucceeds(lastInInsertionOrder, size);
298    setSucceeds(size, ENDPOINT);
299    size++;
300    modCount++;
301    return null;
302  }
303
304  @NullableDecl
305  K putInverse(@NullableDecl V value, @NullableDecl K key, boolean force) {
306    int valueHash = Hashing.smearedHash(value);
307    int entryForValue = findEntryByValue(value, valueHash);
308    if (entryForValue != ABSENT) {
309      K oldKey = keys[entryForValue];
310      if (Objects.equal(oldKey, key)) {
311        return key;
312      } else {
313        replaceKeyInEntry(entryForValue, key, force);
314        return oldKey;
315      }
316    }
317
318    int predecessor = lastInInsertionOrder;
319    int keyHash = Hashing.smearedHash(key);
320    int keyEntry = findEntryByKey(key, keyHash);
321    if (force) {
322      if (keyEntry != ABSENT) {
323        predecessor = prevInInsertionOrder[keyEntry];
324        removeEntryKeyHashKnown(keyEntry, keyHash);
325      }
326    } else {
327      checkArgument(keyEntry == ABSENT, "Key already present: %s", key);
328    }
329
330    // insertion point for new entry is after predecessor
331    // note predecessor must still be a valid entry: either we deleted an entry that was *not*
332    // predecessor, or we didn't delete anything
333
334    ensureCapacity(size + 1);
335    keys[size] = key;
336    values[size] = value;
337
338    insertIntoTableKToV(size, keyHash);
339    insertIntoTableVToK(size, valueHash);
340
341    int successor =
342        (predecessor == ENDPOINT) ? firstInInsertionOrder : nextInInsertionOrder[predecessor];
343    setSucceeds(predecessor, size);
344    setSucceeds(size, successor);
345    size++;
346    modCount++;
347    return null;
348  }
349
350  /**
351   * Updates the pointers of the insertion order linked list so that {@code next} follows {@code
352   * prev}. {@code ENDPOINT} represents either the first or last entry in the entire map (as
353   * appropriate).
354   */
355  private void setSucceeds(int prev, int next) {
356    if (prev == ENDPOINT) {
357      firstInInsertionOrder = next;
358    } else {
359      nextInInsertionOrder[prev] = next;
360    }
361    if (next == ENDPOINT) {
362      lastInInsertionOrder = prev;
363    } else {
364      prevInInsertionOrder[next] = prev;
365    }
366  }
367
368  /**
369   * Updates the K-to-V hash table to include the entry at the specified index, which is assumed to
370   * have not yet been added.
371   */
372  private void insertIntoTableKToV(int entry, int keyHash) {
373    checkArgument(entry != ABSENT);
374    int keyBucket = bucket(keyHash);
375    nextInBucketKToV[entry] = hashTableKToV[keyBucket];
376    hashTableKToV[keyBucket] = entry;
377  }
378
379  /**
380   * Updates the V-to-K hash table to include the entry at the specified index, which is assumed to
381   * have not yet been added.
382   */
383  private void insertIntoTableVToK(int entry, int valueHash) {
384    checkArgument(entry != ABSENT);
385    int valueBucket = bucket(valueHash);
386    nextInBucketVToK[entry] = hashTableVToK[valueBucket];
387    hashTableVToK[valueBucket] = entry;
388  }
389
390  /**
391   * Updates the K-to-V hash table to remove the entry at the specified index, which is assumed to
392   * be present. Does not update any other data structures.
393   */
394  private void deleteFromTableKToV(int entry, int keyHash) {
395    checkArgument(entry != ABSENT);
396    int keyBucket = bucket(keyHash);
397
398    if (hashTableKToV[keyBucket] == entry) {
399      hashTableKToV[keyBucket] = nextInBucketKToV[entry];
400      nextInBucketKToV[entry] = ABSENT;
401      return;
402    }
403
404    int prevInBucket = hashTableKToV[keyBucket];
405    for (int entryInBucket = nextInBucketKToV[prevInBucket];
406        entryInBucket != ABSENT;
407        entryInBucket = nextInBucketKToV[entryInBucket]) {
408      if (entryInBucket == entry) {
409        nextInBucketKToV[prevInBucket] = nextInBucketKToV[entry];
410        nextInBucketKToV[entry] = ABSENT;
411        return;
412      }
413      prevInBucket = entryInBucket;
414    }
415    throw new AssertionError("Expected to find entry with key " + keys[entry]);
416  }
417
418  /**
419   * Updates the V-to-K hash table to remove the entry at the specified index, which is assumed to
420   * be present. Does not update any other data structures.
421   */
422  private void deleteFromTableVToK(int entry, int valueHash) {
423    checkArgument(entry != ABSENT);
424    int valueBucket = bucket(valueHash);
425
426    if (hashTableVToK[valueBucket] == entry) {
427      hashTableVToK[valueBucket] = nextInBucketVToK[entry];
428      nextInBucketVToK[entry] = ABSENT;
429      return;
430    }
431
432    int prevInBucket = hashTableVToK[valueBucket];
433    for (int entryInBucket = nextInBucketVToK[prevInBucket];
434        entryInBucket != ABSENT;
435        entryInBucket = nextInBucketVToK[entryInBucket]) {
436      if (entryInBucket == entry) {
437        nextInBucketVToK[prevInBucket] = nextInBucketVToK[entry];
438        nextInBucketVToK[entry] = ABSENT;
439        return;
440      }
441      prevInBucket = entryInBucket;
442    }
443    throw new AssertionError("Expected to find entry with value " + values[entry]);
444  }
445
446  /**
447   * Updates the specified entry to point to the new value: removes the old value from the V-to-K
448   * mapping and puts the new one in. The entry does not move in the insertion order of the bimap.
449   */
450  private void replaceValueInEntry(int entry, @NullableDecl V newValue, boolean force) {
451    checkArgument(entry != ABSENT);
452    int newValueHash = Hashing.smearedHash(newValue);
453    int newValueIndex = findEntryByValue(newValue, newValueHash);
454    if (newValueIndex != ABSENT) {
455      if (force) {
456        removeEntryValueHashKnown(newValueIndex, newValueHash);
457        if (entry == size) { // this entry got moved to newValueIndex
458          entry = newValueIndex;
459        }
460      } else {
461        throw new IllegalArgumentException("Value already present in map: " + newValue);
462      }
463    }
464    // we do *not* update insertion order, and it isn't a structural modification!
465    deleteFromTableVToK(entry, Hashing.smearedHash(values[entry]));
466    values[entry] = newValue;
467    insertIntoTableVToK(entry, newValueHash);
468  }
469
470  /**
471   * Updates the specified entry to point to the new value: removes the old value from the V-to-K
472   * mapping and puts the new one in. The entry is moved to the end of the insertion order, or to
473   * the position of the new key if it was previously present.
474   */
475  private void replaceKeyInEntry(int entry, @NullableDecl K newKey, boolean force) {
476    checkArgument(entry != ABSENT);
477    int newKeyHash = Hashing.smearedHash(newKey);
478    int newKeyIndex = findEntryByKey(newKey, newKeyHash);
479
480    int newPredecessor = lastInInsertionOrder;
481    int newSuccessor = ENDPOINT;
482    if (newKeyIndex != ABSENT) {
483      if (force) {
484        newPredecessor = prevInInsertionOrder[newKeyIndex];
485        newSuccessor = nextInInsertionOrder[newKeyIndex];
486        removeEntryKeyHashKnown(newKeyIndex, newKeyHash);
487        if (entry == size) { // this entry got moved to newKeyIndex
488          entry = newKeyIndex;
489        }
490      } else {
491        throw new IllegalArgumentException("Key already present in map: " + newKey);
492      }
493    }
494    if (newPredecessor == entry) {
495      newPredecessor = prevInInsertionOrder[entry];
496    } else if (newPredecessor == size) {
497      newPredecessor = newKeyIndex;
498    }
499
500    if (newSuccessor == entry) {
501      newSuccessor = nextInInsertionOrder[entry];
502    } else if (newSuccessor == size) {
503      newSuccessor = newKeyIndex;
504    }
505
506    int oldPredecessor = prevInInsertionOrder[entry];
507    int oldSuccessor = nextInInsertionOrder[entry];
508    setSucceeds(oldPredecessor, oldSuccessor); // remove from insertion order linked list
509
510    deleteFromTableKToV(entry, Hashing.smearedHash(keys[entry]));
511    keys[entry] = newKey;
512    insertIntoTableKToV(entry, Hashing.smearedHash(newKey));
513
514    // insert into insertion order linked list, usually at the end
515    setSucceeds(newPredecessor, entry);
516    setSucceeds(entry, newSuccessor);
517  }
518
519  @Override
520  @NullableDecl
521  @CanIgnoreReturnValue
522  public V remove(@NullableDecl Object key) {
523    int keyHash = Hashing.smearedHash(key);
524    int entry = findEntryByKey(key, keyHash);
525    if (entry == ABSENT) {
526      return null;
527    } else {
528      @NullableDecl V value = values[entry];
529      removeEntryKeyHashKnown(entry, keyHash);
530      return value;
531    }
532  }
533
534  @NullableDecl
535  K removeInverse(@NullableDecl Object value) {
536    int valueHash = Hashing.smearedHash(value);
537    int entry = findEntryByValue(value, valueHash);
538    if (entry == ABSENT) {
539      return null;
540    } else {
541      @NullableDecl K key = keys[entry];
542      removeEntryValueHashKnown(entry, valueHash);
543      return key;
544    }
545  }
546
547  /** Removes the entry at the specified index with no additional data. */
548  void removeEntry(int entry) {
549    removeEntryKeyHashKnown(entry, Hashing.smearedHash(keys[entry]));
550  }
551
552  /** Removes the entry at the specified index, given the hash of its key. */
553  void removeEntryKeyHashKnown(int entry, int keyHash) {
554    removeEntry(entry, keyHash, Hashing.smearedHash(values[entry]));
555  }
556
557  /** Removes the entry at the specified index, given the hash of its value. */
558  void removeEntryValueHashKnown(int entry, int valueHash) {
559    removeEntry(entry, Hashing.smearedHash(keys[entry]), valueHash);
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  /**
580   * Moves the entry previously positioned at {@code src} to {@code dest}. Assumes the entry
581   * previously at {@code src} has already been removed from the data structures.
582   */
583  private void moveEntryToIndex(int src, int dest) {
584    if (src == dest) {
585      return;
586    }
587    int predecessor = prevInInsertionOrder[src];
588    int successor = nextInInsertionOrder[src];
589    setSucceeds(predecessor, dest);
590    setSucceeds(dest, successor);
591
592    K key = keys[src];
593    V value = values[src];
594
595    keys[dest] = key;
596    values[dest] = value;
597
598    // update pointers in hashTableKToV
599    int keyHash = Hashing.smearedHash(key);
600    int keyBucket = bucket(keyHash);
601    if (hashTableKToV[keyBucket] == src) {
602      hashTableKToV[keyBucket] = dest;
603    } else {
604      int prevInBucket = hashTableKToV[keyBucket];
605      for (int entryInBucket = nextInBucketKToV[prevInBucket];
606          /* should never reach end */ ;
607          entryInBucket = nextInBucketKToV[entryInBucket]) {
608        if (entryInBucket == src) {
609          nextInBucketKToV[prevInBucket] = dest;
610          break;
611        }
612        prevInBucket = entryInBucket;
613      }
614    }
615    nextInBucketKToV[dest] = nextInBucketKToV[src];
616    nextInBucketKToV[src] = ABSENT;
617
618    // update pointers in hashTableVToK
619    int valueHash = Hashing.smearedHash(value);
620    int valueBucket = bucket(valueHash);
621    if (hashTableVToK[valueBucket] == src) {
622      hashTableVToK[valueBucket] = dest;
623    } else {
624      int prevInBucket = hashTableVToK[valueBucket];
625      for (int entryInBucket = nextInBucketVToK[prevInBucket];
626          /* should never reach end*/ ;
627          entryInBucket = nextInBucketVToK[entryInBucket]) {
628        if (entryInBucket == src) {
629          nextInBucketVToK[prevInBucket] = dest;
630          break;
631        }
632        prevInBucket = entryInBucket;
633      }
634    }
635    nextInBucketVToK[dest] = nextInBucketVToK[src];
636    nextInBucketVToK[src] = ABSENT;
637  }
638
639  @Override
640  public void clear() {
641    Arrays.fill(keys, 0, size, null);
642    Arrays.fill(values, 0, size, null);
643    Arrays.fill(hashTableKToV, ABSENT);
644    Arrays.fill(hashTableVToK, ABSENT);
645    Arrays.fill(nextInBucketKToV, 0, size, ABSENT);
646    Arrays.fill(nextInBucketVToK, 0, size, ABSENT);
647    Arrays.fill(prevInInsertionOrder, 0, size, ABSENT);
648    Arrays.fill(nextInInsertionOrder, 0, size, ABSENT);
649    size = 0;
650    firstInInsertionOrder = ENDPOINT;
651    lastInInsertionOrder = ENDPOINT;
652    modCount++;
653  }
654
655  /** Shared supertype of keySet, values, entrySet, and inverse.entrySet. */
656  abstract static class View<K, V, T> extends AbstractSet<T> {
657    final HashBiMap<K, V> biMap;
658
659    View(HashBiMap<K, V> biMap) {
660      this.biMap = biMap;
661    }
662
663    abstract T forEntry(int entry);
664
665    @Override
666    public Iterator<T> iterator() {
667      return new Iterator<T>() {
668        private int index = biMap.firstInInsertionOrder;
669        private int indexToRemove = ABSENT;
670        private int expectedModCount = biMap.modCount;
671
672        // Calls to setValue on inverse entries can move already-visited entries to the end.
673        // Make sure we don't visit those.
674        private int remaining = biMap.size;
675
676        private void checkForComodification() {
677          if (biMap.modCount != expectedModCount) {
678            throw new ConcurrentModificationException();
679          }
680        }
681
682        @Override
683        public boolean hasNext() {
684          checkForComodification();
685          return index != ENDPOINT && remaining > 0;
686        }
687
688        @Override
689        public T next() {
690          if (!hasNext()) {
691            throw new NoSuchElementException();
692          }
693          T result = forEntry(index);
694          indexToRemove = index;
695          index = biMap.nextInInsertionOrder[index];
696          remaining--;
697          return result;
698        }
699
700        @Override
701        public void remove() {
702          checkForComodification();
703          CollectPreconditions.checkRemove(indexToRemove != ABSENT);
704          biMap.removeEntry(indexToRemove);
705          if (index == biMap.size) {
706            index = indexToRemove;
707          }
708          indexToRemove = ABSENT;
709          expectedModCount = biMap.modCount;
710        }
711      };
712    }
713
714    @Override
715    public int size() {
716      return biMap.size;
717    }
718
719    @Override
720    public void clear() {
721      biMap.clear();
722    }
723  }
724
725  private transient Set<K> keySet;
726
727  @Override
728  public Set<K> keySet() {
729    Set<K> result = keySet;
730    return (result == null) ? keySet = new KeySet() : result;
731  }
732
733  final class KeySet extends View<K, V, K> {
734    KeySet() {
735      super(HashBiMap.this);
736    }
737
738    @Override
739    K forEntry(int entry) {
740      return keys[entry];
741    }
742
743    @Override
744    public boolean contains(@NullableDecl Object o) {
745      return HashBiMap.this.containsKey(o);
746    }
747
748    @Override
749    public boolean remove(@NullableDecl Object o) {
750      int oHash = Hashing.smearedHash(o);
751      int entry = findEntryByKey(o, oHash);
752      if (entry != ABSENT) {
753        removeEntryKeyHashKnown(entry, oHash);
754        return true;
755      } else {
756        return false;
757      }
758    }
759  }
760
761  private transient Set<V> valueSet;
762
763  @Override
764  public Set<V> values() {
765    Set<V> result = valueSet;
766    return (result == null) ? valueSet = new ValueSet() : result;
767  }
768
769  final class ValueSet extends View<K, V, V> {
770    ValueSet() {
771      super(HashBiMap.this);
772    }
773
774    @Override
775    V forEntry(int entry) {
776      return values[entry];
777    }
778
779    @Override
780    public boolean contains(@NullableDecl Object o) {
781      return HashBiMap.this.containsValue(o);
782    }
783
784    @Override
785    public boolean remove(@NullableDecl Object o) {
786      int oHash = Hashing.smearedHash(o);
787      int entry = findEntryByValue(o, oHash);
788      if (entry != ABSENT) {
789        removeEntryValueHashKnown(entry, oHash);
790        return true;
791      } else {
792        return false;
793      }
794    }
795  }
796
797  private transient Set<Entry<K, V>> entrySet;
798
799  @Override
800  public Set<Entry<K, V>> entrySet() {
801    Set<Entry<K, V>> result = entrySet;
802    return (result == null) ? entrySet = new EntrySet() : result;
803  }
804
805  final class EntrySet extends View<K, V, Entry<K, V>> {
806    EntrySet() {
807      super(HashBiMap.this);
808    }
809
810    @Override
811    public boolean contains(@NullableDecl Object o) {
812      if (o instanceof Entry) {
813        Entry<?, ?> e = (Entry<?, ?>) o;
814        @NullableDecl Object k = e.getKey();
815        @NullableDecl Object v = e.getValue();
816        int eIndex = findEntryByKey(k);
817        return eIndex != ABSENT && Objects.equal(v, values[eIndex]);
818      }
819      return false;
820    }
821
822    @Override
823    @CanIgnoreReturnValue
824    public boolean remove(@NullableDecl Object o) {
825      if (o instanceof Entry) {
826        Entry<?, ?> e = (Entry<?, ?>) o;
827        @NullableDecl Object k = e.getKey();
828        @NullableDecl Object v = e.getValue();
829        int kHash = Hashing.smearedHash(k);
830        int eIndex = findEntryByKey(k, kHash);
831        if (eIndex != ABSENT && Objects.equal(v, values[eIndex])) {
832          removeEntryKeyHashKnown(eIndex, kHash);
833          return true;
834        }
835      }
836      return false;
837    }
838
839    @Override
840    Entry<K, V> forEntry(int entry) {
841      return new EntryForKey(entry);
842    }
843  }
844
845  /**
846   * An {@code Entry} implementation that attempts to follow its key around the map -- that is, if
847   * the key is moved, deleted, or reinserted, it will account for that -- while not doing any extra
848   * work if the key has not moved.
849   */
850  final class EntryForKey extends AbstractMapEntry<K, V> {
851    @NullableDecl final K key;
852    int index;
853
854    EntryForKey(int index) {
855      this.key = keys[index];
856      this.index = index;
857    }
858
859    void updateIndex() {
860      if (index == ABSENT || index > size || !Objects.equal(keys[index], key)) {
861        index = findEntryByKey(key);
862      }
863    }
864
865    @Override
866    public K getKey() {
867      return key;
868    }
869
870    @Override
871    @NullableDecl
872    public V getValue() {
873      updateIndex();
874      return (index == ABSENT) ? null : values[index];
875    }
876
877    @Override
878    public V setValue(V value) {
879      updateIndex();
880      if (index == ABSENT) {
881        return HashBiMap.this.put(key, value);
882      }
883      V oldValue = values[index];
884      if (Objects.equal(oldValue, value)) {
885        return value;
886      }
887      replaceValueInEntry(index, value, false);
888      return oldValue;
889    }
890  }
891
892  @MonotonicNonNullDecl @RetainedWith private transient BiMap<V, K> inverse;
893
894  @Override
895  public BiMap<V, K> inverse() {
896    BiMap<V, K> result = inverse;
897    return (result == null) ? inverse = new Inverse<K, V>(this) : result;
898  }
899
900  static class Inverse<K, V> extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
901    private final HashBiMap<K, V> forward;
902
903    Inverse(HashBiMap<K, V> forward) {
904      this.forward = forward;
905    }
906
907    @Override
908    public int size() {
909      return forward.size;
910    }
911
912    @Override
913    public boolean containsKey(@NullableDecl Object key) {
914      return forward.containsValue(key);
915    }
916
917    @Override
918    @NullableDecl
919    public K get(@NullableDecl Object key) {
920      return forward.getInverse(key);
921    }
922
923    @Override
924    public boolean containsValue(@NullableDecl Object value) {
925      return forward.containsKey(value);
926    }
927
928    @Override
929    @NullableDecl
930    @CanIgnoreReturnValue
931    public K put(@NullableDecl V value, @NullableDecl K key) {
932      return forward.putInverse(value, key, false);
933    }
934
935    @Override
936    @NullableDecl
937    @CanIgnoreReturnValue
938    public K forcePut(@NullableDecl V value, @NullableDecl K key) {
939      return forward.putInverse(value, key, true);
940    }
941
942    @Override
943    public BiMap<K, V> inverse() {
944      return forward;
945    }
946
947    @Override
948    @NullableDecl
949    @CanIgnoreReturnValue
950    public K remove(@NullableDecl Object value) {
951      return forward.removeInverse(value);
952    }
953
954    @Override
955    public void clear() {
956      forward.clear();
957    }
958
959    @Override
960    public Set<V> keySet() {
961      return forward.values();
962    }
963
964    @Override
965    public Set<K> values() {
966      return forward.keySet();
967    }
968
969    private transient Set<Entry<V, K>> inverseEntrySet;
970
971    @Override
972    public Set<Entry<V, K>> entrySet() {
973      Set<Entry<V, K>> result = inverseEntrySet;
974      return (result == null) ? inverseEntrySet = new InverseEntrySet<K, V>(forward) : result;
975    }
976
977    @GwtIncompatible("serialization")
978    private void readObject(ObjectInputStream in) throws ClassNotFoundException, IOException {
979      in.defaultReadObject();
980      this.forward.inverse = this;
981    }
982  }
983
984  static class InverseEntrySet<K, V> extends View<K, V, Entry<V, K>> {
985    InverseEntrySet(HashBiMap<K, V> biMap) {
986      super(biMap);
987    }
988
989    @Override
990    public boolean contains(@NullableDecl Object o) {
991      if (o instanceof Entry) {
992        Entry<?, ?> e = (Entry<?, ?>) o;
993        Object v = e.getKey();
994        Object k = e.getValue();
995        int eIndex = biMap.findEntryByValue(v);
996        return eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k);
997      }
998      return false;
999    }
1000
1001    @Override
1002    public boolean remove(Object o) {
1003      if (o instanceof Entry) {
1004        Entry<?, ?> e = (Entry<?, ?>) o;
1005        Object v = e.getKey();
1006        Object k = e.getValue();
1007        int vHash = Hashing.smearedHash(v);
1008        int eIndex = biMap.findEntryByValue(v, vHash);
1009        if (eIndex != ABSENT && Objects.equal(biMap.keys[eIndex], k)) {
1010          biMap.removeEntryValueHashKnown(eIndex, vHash);
1011          return true;
1012        }
1013      }
1014      return false;
1015    }
1016
1017    @Override
1018    Entry<V, K> forEntry(int entry) {
1019      return new EntryForValue<K, V>(biMap, entry);
1020    }
1021  }
1022
1023  /**
1024   * An {@code Entry} implementation that attempts to follow its value around the map -- that is, if
1025   * the value is moved, deleted, or reinserted, it will account for that -- while not doing any
1026   * extra work if the value has not moved.
1027   */
1028  static final class EntryForValue<K, V> extends AbstractMapEntry<V, K> {
1029    final HashBiMap<K, V> biMap;
1030    final V value;
1031    int index;
1032
1033    EntryForValue(HashBiMap<K, V> biMap, int index) {
1034      this.biMap = biMap;
1035      this.value = biMap.values[index];
1036      this.index = index;
1037    }
1038
1039    private void updateIndex() {
1040      if (index == ABSENT || index > biMap.size || !Objects.equal(value, biMap.values[index])) {
1041        index = biMap.findEntryByValue(value);
1042      }
1043    }
1044
1045    @Override
1046    public V getKey() {
1047      return value;
1048    }
1049
1050    @Override
1051    public K getValue() {
1052      updateIndex();
1053      return (index == ABSENT) ? null : biMap.keys[index];
1054    }
1055
1056    @Override
1057    public K setValue(K key) {
1058      updateIndex();
1059      if (index == ABSENT) {
1060        return biMap.putInverse(value, key, false);
1061      }
1062      K oldKey = biMap.keys[index];
1063      if (Objects.equal(oldKey, key)) {
1064        return key;
1065      }
1066      biMap.replaceKeyInEntry(index, key, false);
1067      return oldKey;
1068    }
1069  }
1070
1071  /**
1072   * @serialData the number of entries, first key, first value, second key, second value, and so on.
1073   */
1074  @GwtIncompatible // java.io.ObjectOutputStream
1075  private void writeObject(ObjectOutputStream stream) throws IOException {
1076    stream.defaultWriteObject();
1077    Serialization.writeMap(this, stream);
1078  }
1079
1080  @GwtIncompatible // java.io.ObjectInputStream
1081  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
1082    stream.defaultReadObject();
1083    int size = Serialization.readCount(stream);
1084    init(16); // resist hostile attempts to allocate gratuitous heap
1085    Serialization.populateMap(this, stream, size);
1086  }
1087}