1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 47dd252788645e940eada959bdde927426e2531c9Paul Duffin * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 57dd252788645e940eada959bdde927426e2531c9Paul Duffin * in compliance with the License. You may obtain a copy of the License at 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 97dd252788645e940eada959bdde927426e2531c9Paul Duffin * Unless required by applicable law or agreed to in writing, software distributed under the License 107dd252788645e940eada959bdde927426e2531c9Paul Duffin * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 117dd252788645e940eada959bdde927426e2531c9Paul Duffin * or implied. See the License for the specific language governing permissions and limitations under 127dd252788645e940eada959bdde927426e2531c9Paul Duffin * the License. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 177dd252788645e940eada959bdde927426e2531c9Paul Duffinimport static com.google.common.base.Preconditions.checkArgument; 180888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkNonnegative; 190888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkRemove; 207dd252788645e940eada959bdde927426e2531c9Paul Duffin 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 237dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Objects; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectOutputStream; 287dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.io.Serializable; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.AbstractMap; 307dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Arrays; 317dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.ConcurrentModificationException; 327dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Iterator; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 347dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.NoSuchElementException; 357dd252788645e940eada959bdde927426e2531c9Paul Duffinimport java.util.Set; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 407dd252788645e940eada959bdde927426e2531c9Paul Duffin * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A 417dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code HashBiMap} and its inverse are both serializable. 427dd252788645e940eada959bdde927426e2531c9Paul Duffin * 437dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 447dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#BiMap"> {@code BiMap} 457dd252788645e940eada959bdde927426e2531c9Paul Duffin * </a>. 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 477dd252788645e940eada959bdde927426e2531c9Paul Duffin * @author Louis Wasserman 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Mike Bostock 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 527dd252788645e940eada959bdde927426e2531c9Paul Duffinpublic final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K, V>, Serializable { 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 557dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a new, empty {@code HashBiMap} with the default initial capacity (16). 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> HashBiMap<K, V> create() { 587dd252788645e940eada959bdde927426e2531c9Paul Duffin return create(16); 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a new, empty bimap with the specified expected size. 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedSize the expected number of entries 657dd252788645e940eada959bdde927426e2531c9Paul Duffin * @throws IllegalArgumentException if the specified expected size is negative 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> HashBiMap<K, V> create(int expectedSize) { 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashBiMap<K, V>(expectedSize); 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 727dd252788645e940eada959bdde927426e2531c9Paul Duffin * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an 737dd252788645e940eada959bdde927426e2531c9Paul Duffin * initial capacity sufficient to hold the mappings in the specified map. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 757dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) { 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson HashBiMap<K, V> bimap = create(map.size()); 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson bimap.putAll(map); 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return bimap; 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 810888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static final class BiEntry<K, V> extends ImmutableEntry<K, V> { 827dd252788645e940eada959bdde927426e2531c9Paul Duffin final int keyHash; 837dd252788645e940eada959bdde927426e2531c9Paul Duffin final int valueHash; 847dd252788645e940eada959bdde927426e2531c9Paul Duffin 857dd252788645e940eada959bdde927426e2531c9Paul Duffin @Nullable 867dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> nextInKToVBucket; 877dd252788645e940eada959bdde927426e2531c9Paul Duffin 887dd252788645e940eada959bdde927426e2531c9Paul Duffin @Nullable 897dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> nextInVToKBucket; 907dd252788645e940eada959bdde927426e2531c9Paul Duffin 917dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry(K key, int keyHash, V value, int valueHash) { 920888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(key, value); 937dd252788645e940eada959bdde927426e2531c9Paul Duffin this.keyHash = keyHash; 947dd252788645e940eada959bdde927426e2531c9Paul Duffin this.valueHash = valueHash; 957dd252788645e940eada959bdde927426e2531c9Paul Duffin } 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 987dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final double LOAD_FACTOR = 1.0; 997dd252788645e940eada959bdde927426e2531c9Paul Duffin 1007dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient BiEntry<K, V>[] hashTableKToV; 1017dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient BiEntry<K, V>[] hashTableVToK; 1027dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient int size; 1037dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient int mask; 1047dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient int modCount; 1057dd252788645e940eada959bdde927426e2531c9Paul Duffin 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private HashBiMap(int expectedSize) { 1077dd252788645e940eada959bdde927426e2531c9Paul Duffin init(expectedSize); 1087dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1097dd252788645e940eada959bdde927426e2531c9Paul Duffin 1107dd252788645e940eada959bdde927426e2531c9Paul Duffin private void init(int expectedSize) { 1110888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(expectedSize, "expectedSize"); 1127dd252788645e940eada959bdde927426e2531c9Paul Duffin int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR); 1137dd252788645e940eada959bdde927426e2531c9Paul Duffin this.hashTableKToV = createTable(tableSize); 1147dd252788645e940eada959bdde927426e2531c9Paul Duffin this.hashTableVToK = createTable(tableSize); 1157dd252788645e940eada959bdde927426e2531c9Paul Duffin this.mask = tableSize - 1; 1167dd252788645e940eada959bdde927426e2531c9Paul Duffin this.modCount = 0; 1177dd252788645e940eada959bdde927426e2531c9Paul Duffin this.size = 0; 1187dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1197dd252788645e940eada959bdde927426e2531c9Paul Duffin 1207dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 1217dd252788645e940eada959bdde927426e2531c9Paul Duffin * Finds and removes {@code entry} from the bucket linked lists in both the 1227dd252788645e940eada959bdde927426e2531c9Paul Duffin * key-to-value direction and the value-to-key direction. 1237dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 1247dd252788645e940eada959bdde927426e2531c9Paul Duffin private void delete(BiEntry<K, V> entry) { 1257dd252788645e940eada959bdde927426e2531c9Paul Duffin int keyBucket = entry.keyHash & mask; 1267dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> prevBucketEntry = null; 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket]; true; 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin bucketEntry = bucketEntry.nextInKToVBucket) { 1297dd252788645e940eada959bdde927426e2531c9Paul Duffin if (bucketEntry == entry) { 1307dd252788645e940eada959bdde927426e2531c9Paul Duffin if (prevBucketEntry == null) { 1317dd252788645e940eada959bdde927426e2531c9Paul Duffin hashTableKToV[keyBucket] = entry.nextInKToVBucket; 1327dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 1337dd252788645e940eada959bdde927426e2531c9Paul Duffin prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket; 1347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1357dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 1367dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1377dd252788645e940eada959bdde927426e2531c9Paul Duffin prevBucketEntry = bucketEntry; 1387dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1397dd252788645e940eada959bdde927426e2531c9Paul Duffin 1407dd252788645e940eada959bdde927426e2531c9Paul Duffin int valueBucket = entry.valueHash & mask; 1417dd252788645e940eada959bdde927426e2531c9Paul Duffin prevBucketEntry = null; 1420888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];; 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin bucketEntry = bucketEntry.nextInVToKBucket) { 1447dd252788645e940eada959bdde927426e2531c9Paul Duffin if (bucketEntry == entry) { 1457dd252788645e940eada959bdde927426e2531c9Paul Duffin if (prevBucketEntry == null) { 1467dd252788645e940eada959bdde927426e2531c9Paul Duffin hashTableVToK[valueBucket] = entry.nextInVToKBucket; 1477dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 1487dd252788645e940eada959bdde927426e2531c9Paul Duffin prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket; 1497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1507dd252788645e940eada959bdde927426e2531c9Paul Duffin break; 1517dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1527dd252788645e940eada959bdde927426e2531c9Paul Duffin prevBucketEntry = bucketEntry; 1537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1547dd252788645e940eada959bdde927426e2531c9Paul Duffin 1557dd252788645e940eada959bdde927426e2531c9Paul Duffin size--; 1567dd252788645e940eada959bdde927426e2531c9Paul Duffin modCount++; 1577dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1587dd252788645e940eada959bdde927426e2531c9Paul Duffin 1597dd252788645e940eada959bdde927426e2531c9Paul Duffin private void insert(BiEntry<K, V> entry) { 1607dd252788645e940eada959bdde927426e2531c9Paul Duffin int keyBucket = entry.keyHash & mask; 1617dd252788645e940eada959bdde927426e2531c9Paul Duffin entry.nextInKToVBucket = hashTableKToV[keyBucket]; 1627dd252788645e940eada959bdde927426e2531c9Paul Duffin hashTableKToV[keyBucket] = entry; 1637dd252788645e940eada959bdde927426e2531c9Paul Duffin 1647dd252788645e940eada959bdde927426e2531c9Paul Duffin int valueBucket = entry.valueHash & mask; 1657dd252788645e940eada959bdde927426e2531c9Paul Duffin entry.nextInVToKBucket = hashTableVToK[valueBucket]; 1667dd252788645e940eada959bdde927426e2531c9Paul Duffin hashTableVToK[valueBucket] = entry; 1677dd252788645e940eada959bdde927426e2531c9Paul Duffin 1687dd252788645e940eada959bdde927426e2531c9Paul Duffin size++; 1697dd252788645e940eada959bdde927426e2531c9Paul Duffin modCount++; 1707dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1717dd252788645e940eada959bdde927426e2531c9Paul Duffin 1727dd252788645e940eada959bdde927426e2531c9Paul Duffin private static int hash(@Nullable Object o) { 1737dd252788645e940eada959bdde927426e2531c9Paul Duffin return Hashing.smear((o == null) ? 0 : o.hashCode()); 1747dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1757dd252788645e940eada959bdde927426e2531c9Paul Duffin 1767dd252788645e940eada959bdde927426e2531c9Paul Duffin private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) { 1770888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask]; entry != null; 1780888a09821a98ac0680fad765217302858e70fa4Paul Duffin entry = entry.nextInKToVBucket) { 1797dd252788645e940eada959bdde927426e2531c9Paul Duffin if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) { 1807dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry; 1817dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1827dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1837dd252788645e940eada959bdde927426e2531c9Paul Duffin return null; 1847dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1857dd252788645e940eada959bdde927426e2531c9Paul Duffin 1867dd252788645e940eada959bdde927426e2531c9Paul Duffin private BiEntry<K, V> seekByValue(@Nullable Object value, int valueHash) { 1870888a09821a98ac0680fad765217302858e70fa4Paul Duffin for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask]; entry != null; 1880888a09821a98ac0680fad765217302858e70fa4Paul Duffin entry = entry.nextInVToKBucket) { 1897dd252788645e940eada959bdde927426e2531c9Paul Duffin if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) { 1907dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry; 1917dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1927dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1937dd252788645e940eada959bdde927426e2531c9Paul Duffin return null; 1947dd252788645e940eada959bdde927426e2531c9Paul Duffin } 1957dd252788645e940eada959bdde927426e2531c9Paul Duffin 1967dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 1977dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean containsKey(@Nullable Object key) { 1987dd252788645e940eada959bdde927426e2531c9Paul Duffin return seekByKey(key, hash(key)) != null; 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2007dd252788645e940eada959bdde927426e2531c9Paul Duffin 2017dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2027dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean containsValue(@Nullable Object value) { 2037dd252788645e940eada959bdde927426e2531c9Paul Duffin return seekByValue(value, hash(value)) != null; 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2067dd252788645e940eada959bdde927426e2531c9Paul Duffin @Nullable 2070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2087dd252788645e940eada959bdde927426e2531c9Paul Duffin public V get(@Nullable Object key) { 2097dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByKey(key, hash(key)); 2107dd252788645e940eada959bdde927426e2531c9Paul Duffin return (entry == null) ? null : entry.value; 2117dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2127dd252788645e940eada959bdde927426e2531c9Paul Duffin 2137dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2147dd252788645e940eada959bdde927426e2531c9Paul Duffin public V put(@Nullable K key, @Nullable V value) { 2157dd252788645e940eada959bdde927426e2531c9Paul Duffin return put(key, value, false); 2167dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2177dd252788645e940eada959bdde927426e2531c9Paul Duffin 2180888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2197dd252788645e940eada959bdde927426e2531c9Paul Duffin public V forcePut(@Nullable K key, @Nullable V value) { 2207dd252788645e940eada959bdde927426e2531c9Paul Duffin return put(key, value, true); 2217dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2227dd252788645e940eada959bdde927426e2531c9Paul Duffin 2237dd252788645e940eada959bdde927426e2531c9Paul Duffin private V put(@Nullable K key, @Nullable V value, boolean force) { 2247dd252788645e940eada959bdde927426e2531c9Paul Duffin int keyHash = hash(key); 2257dd252788645e940eada959bdde927426e2531c9Paul Duffin int valueHash = hash(value); 2267dd252788645e940eada959bdde927426e2531c9Paul Duffin 2277dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 2287dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForKey != null && valueHash == oldEntryForKey.valueHash 2297dd252788645e940eada959bdde927426e2531c9Paul Duffin && Objects.equal(value, oldEntryForKey.value)) { 2307dd252788645e940eada959bdde927426e2531c9Paul Duffin return value; 2317dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2327dd252788645e940eada959bdde927426e2531c9Paul Duffin 2337dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 2347dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForValue != null) { 2357dd252788645e940eada959bdde927426e2531c9Paul Duffin if (force) { 2367dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(oldEntryForValue); 2377dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 2387dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new IllegalArgumentException("value already present: " + value); 2397dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2407dd252788645e940eada959bdde927426e2531c9Paul Duffin } 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2427dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForKey != null) { 2437dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(oldEntryForKey); 2447dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2457dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash); 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin insert(newEntry); 2477dd252788645e940eada959bdde927426e2531c9Paul Duffin rehashIfNecessary(); 2487dd252788645e940eada959bdde927426e2531c9Paul Duffin return (oldEntryForKey == null) ? null : oldEntryForKey.value; 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2517dd252788645e940eada959bdde927426e2531c9Paul Duffin @Nullable 2527dd252788645e940eada959bdde927426e2531c9Paul Duffin private K putInverse(@Nullable V value, @Nullable K key, boolean force) { 2537dd252788645e940eada959bdde927426e2531c9Paul Duffin int valueHash = hash(value); 2547dd252788645e940eada959bdde927426e2531c9Paul Duffin int keyHash = hash(key); 2557dd252788645e940eada959bdde927426e2531c9Paul Duffin 2567dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 2577dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForValue != null && keyHash == oldEntryForValue.keyHash 2587dd252788645e940eada959bdde927426e2531c9Paul Duffin && Objects.equal(key, oldEntryForValue.key)) { 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin return key; 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2617dd252788645e940eada959bdde927426e2531c9Paul Duffin 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 2637dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForKey != null) { 2647dd252788645e940eada959bdde927426e2531c9Paul Duffin if (force) { 2657dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(oldEntryForKey); 2667dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 2677dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new IllegalArgumentException("value already present: " + key); 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2697dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2707dd252788645e940eada959bdde927426e2531c9Paul Duffin 2717dd252788645e940eada959bdde927426e2531c9Paul Duffin if (oldEntryForValue != null) { 2727dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(oldEntryForValue); 2737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2747dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash); 2757dd252788645e940eada959bdde927426e2531c9Paul Duffin insert(newEntry); 2767dd252788645e940eada959bdde927426e2531c9Paul Duffin rehashIfNecessary(); 2777dd252788645e940eada959bdde927426e2531c9Paul Duffin return (oldEntryForValue == null) ? null : oldEntryForValue.key; 2787dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2797dd252788645e940eada959bdde927426e2531c9Paul Duffin 2807dd252788645e940eada959bdde927426e2531c9Paul Duffin private void rehashIfNecessary() { 2817dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V>[] oldKToV = hashTableKToV; 2827dd252788645e940eada959bdde927426e2531c9Paul Duffin if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) { 2837dd252788645e940eada959bdde927426e2531c9Paul Duffin int newTableSize = oldKToV.length * 2; 2847dd252788645e940eada959bdde927426e2531c9Paul Duffin 2857dd252788645e940eada959bdde927426e2531c9Paul Duffin this.hashTableKToV = createTable(newTableSize); 2867dd252788645e940eada959bdde927426e2531c9Paul Duffin this.hashTableVToK = createTable(newTableSize); 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin this.mask = newTableSize - 1; 2887dd252788645e940eada959bdde927426e2531c9Paul Duffin this.size = 0; 2897dd252788645e940eada959bdde927426e2531c9Paul Duffin 2907dd252788645e940eada959bdde927426e2531c9Paul Duffin for (int bucket = 0; bucket < oldKToV.length; bucket++) { 2917dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = oldKToV[bucket]; 2927dd252788645e940eada959bdde927426e2531c9Paul Duffin while (entry != null) { 2937dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> nextEntry = entry.nextInKToVBucket; 2947dd252788645e940eada959bdde927426e2531c9Paul Duffin insert(entry); 2957dd252788645e940eada959bdde927426e2531c9Paul Duffin entry = nextEntry; 2967dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2977dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2987dd252788645e940eada959bdde927426e2531c9Paul Duffin this.modCount++; 2997dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3007dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3017dd252788645e940eada959bdde927426e2531c9Paul Duffin 3027dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unchecked") 3037dd252788645e940eada959bdde927426e2531c9Paul Duffin private BiEntry<K, V>[] createTable(int length) { 3047dd252788645e940eada959bdde927426e2531c9Paul Duffin return new BiEntry[length]; 3057dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3067dd252788645e940eada959bdde927426e2531c9Paul Duffin 3077dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3087dd252788645e940eada959bdde927426e2531c9Paul Duffin public V remove(@Nullable Object key) { 3097dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByKey(key, hash(key)); 3107dd252788645e940eada959bdde927426e2531c9Paul Duffin if (entry == null) { 3117dd252788645e940eada959bdde927426e2531c9Paul Duffin return null; 3127dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 3137dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(entry); 3147dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry.value; 3157dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3167dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3177dd252788645e940eada959bdde927426e2531c9Paul Duffin 3187dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3197dd252788645e940eada959bdde927426e2531c9Paul Duffin public void clear() { 3207dd252788645e940eada959bdde927426e2531c9Paul Duffin size = 0; 3217dd252788645e940eada959bdde927426e2531c9Paul Duffin Arrays.fill(hashTableKToV, null); 3227dd252788645e940eada959bdde927426e2531c9Paul Duffin Arrays.fill(hashTableVToK, null); 3237dd252788645e940eada959bdde927426e2531c9Paul Duffin modCount++; 3247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3257dd252788645e940eada959bdde927426e2531c9Paul Duffin 3267dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3277dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 3287dd252788645e940eada959bdde927426e2531c9Paul Duffin return size; 3297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3307dd252788645e940eada959bdde927426e2531c9Paul Duffin 3317dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract class Itr<T> implements Iterator<T> { 3327dd252788645e940eada959bdde927426e2531c9Paul Duffin int nextBucket = 0; 3337dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> next = null; 3347dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> toRemove = null; 3357dd252788645e940eada959bdde927426e2531c9Paul Duffin int expectedModCount = modCount; 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin 3377dd252788645e940eada959bdde927426e2531c9Paul Duffin private void checkForConcurrentModification() { 3387dd252788645e940eada959bdde927426e2531c9Paul Duffin if (modCount != expectedModCount) { 3397dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new ConcurrentModificationException(); 3407dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3427dd252788645e940eada959bdde927426e2531c9Paul Duffin 3430888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3447dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean hasNext() { 3457dd252788645e940eada959bdde927426e2531c9Paul Duffin checkForConcurrentModification(); 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin if (next != null) { 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin return true; 3487dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3497dd252788645e940eada959bdde927426e2531c9Paul Duffin while (nextBucket < hashTableKToV.length) { 3507dd252788645e940eada959bdde927426e2531c9Paul Duffin if (hashTableKToV[nextBucket] != null) { 3517dd252788645e940eada959bdde927426e2531c9Paul Duffin next = hashTableKToV[nextBucket++]; 3527dd252788645e940eada959bdde927426e2531c9Paul Duffin return true; 3537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3547dd252788645e940eada959bdde927426e2531c9Paul Duffin nextBucket++; 3557dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3567dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 3577dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3587dd252788645e940eada959bdde927426e2531c9Paul Duffin 3590888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3607dd252788645e940eada959bdde927426e2531c9Paul Duffin public T next() { 3617dd252788645e940eada959bdde927426e2531c9Paul Duffin checkForConcurrentModification(); 3627dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!hasNext()) { 3637dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new NoSuchElementException(); 3647dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3657dd252788645e940eada959bdde927426e2531c9Paul Duffin 3667dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = next; 3677dd252788645e940eada959bdde927426e2531c9Paul Duffin next = entry.nextInKToVBucket; 3687dd252788645e940eada959bdde927426e2531c9Paul Duffin toRemove = entry; 3697dd252788645e940eada959bdde927426e2531c9Paul Duffin return output(entry); 3707dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3717dd252788645e940eada959bdde927426e2531c9Paul Duffin 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3737dd252788645e940eada959bdde927426e2531c9Paul Duffin public void remove() { 3747dd252788645e940eada959bdde927426e2531c9Paul Duffin checkForConcurrentModification(); 3750888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(toRemove != null); 3767dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(toRemove); 3777dd252788645e940eada959bdde927426e2531c9Paul Duffin expectedModCount = modCount; 3787dd252788645e940eada959bdde927426e2531c9Paul Duffin toRemove = null; 3797dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3807dd252788645e940eada959bdde927426e2531c9Paul Duffin 3817dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract T output(BiEntry<K, V> entry); 3827dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3837dd252788645e940eada959bdde927426e2531c9Paul Duffin 3847dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3857dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<K> keySet() { 3867dd252788645e940eada959bdde927426e2531c9Paul Duffin return new KeySet(); 3877dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3887dd252788645e940eada959bdde927426e2531c9Paul Duffin 3897dd252788645e940eada959bdde927426e2531c9Paul Duffin private final class KeySet extends Maps.KeySet<K, V> { 3900888a09821a98ac0680fad765217302858e70fa4Paul Duffin KeySet() { 3910888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(HashBiMap.this); 3927dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3937dd252788645e940eada959bdde927426e2531c9Paul Duffin 3947dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3957dd252788645e940eada959bdde927426e2531c9Paul Duffin public Iterator<K> iterator() { 3967dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Itr<K>() { 3977dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3987dd252788645e940eada959bdde927426e2531c9Paul Duffin K output(BiEntry<K, V> entry) { 3997dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry.key; 4007dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 4027dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4037dd252788645e940eada959bdde927426e2531c9Paul Duffin 4047dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4057dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean remove(@Nullable Object o) { 4067dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByKey(o, hash(o)); 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin if (entry == null) { 4087dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 4097dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 4107dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(entry); 4117dd252788645e940eada959bdde927426e2531c9Paul Duffin return true; 4127dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4147dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4157dd252788645e940eada959bdde927426e2531c9Paul Duffin 4167dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4177dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<V> values() { 4187dd252788645e940eada959bdde927426e2531c9Paul Duffin return inverse().keySet(); 4197dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4207dd252788645e940eada959bdde927426e2531c9Paul Duffin 4217dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4227dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<Entry<K, V>> entrySet() { 4237dd252788645e940eada959bdde927426e2531c9Paul Duffin return new EntrySet(); 4247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4257dd252788645e940eada959bdde927426e2531c9Paul Duffin 4267dd252788645e940eada959bdde927426e2531c9Paul Duffin private final class EntrySet extends Maps.EntrySet<K, V> { 4277dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4287dd252788645e940eada959bdde927426e2531c9Paul Duffin Map<K, V> map() { 4297dd252788645e940eada959bdde927426e2531c9Paul Duffin return HashBiMap.this; 4307dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4317dd252788645e940eada959bdde927426e2531c9Paul Duffin 4327dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4337dd252788645e940eada959bdde927426e2531c9Paul Duffin public Iterator<Entry<K, V>> iterator() { 4347dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Itr<Entry<K, V>>() { 4357dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4367dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<K, V> output(BiEntry<K, V> entry) { 4377dd252788645e940eada959bdde927426e2531c9Paul Duffin return new MapEntry(entry); 4387dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4397dd252788645e940eada959bdde927426e2531c9Paul Duffin 4407dd252788645e940eada959bdde927426e2531c9Paul Duffin class MapEntry extends AbstractMapEntry<K, V> { 4417dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> delegate; 4427dd252788645e940eada959bdde927426e2531c9Paul Duffin 4437dd252788645e940eada959bdde927426e2531c9Paul Duffin MapEntry(BiEntry<K, V> entry) { 4447dd252788645e940eada959bdde927426e2531c9Paul Duffin this.delegate = entry; 4457dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4467dd252788645e940eada959bdde927426e2531c9Paul Duffin 4470888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public K getKey() { 4487dd252788645e940eada959bdde927426e2531c9Paul Duffin return delegate.key; 4497dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4507dd252788645e940eada959bdde927426e2531c9Paul Duffin 4510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public V getValue() { 4527dd252788645e940eada959bdde927426e2531c9Paul Duffin return delegate.value; 4537dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4547dd252788645e940eada959bdde927426e2531c9Paul Duffin 4550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public V setValue(V value) { 4567dd252788645e940eada959bdde927426e2531c9Paul Duffin V oldValue = delegate.value; 4577dd252788645e940eada959bdde927426e2531c9Paul Duffin int valueHash = hash(value); 4587dd252788645e940eada959bdde927426e2531c9Paul Duffin if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) { 4597dd252788645e940eada959bdde927426e2531c9Paul Duffin return value; 4607dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4610888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument( 4620888a09821a98ac0680fad765217302858e70fa4Paul Duffin seekByValue(value, valueHash) == null, "value already present: %s", value); 4637dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(delegate); 4640888a09821a98ac0680fad765217302858e70fa4Paul Duffin BiEntry<K, V> newEntry = 4650888a09821a98ac0680fad765217302858e70fa4Paul Duffin new BiEntry<K, V>(delegate.key, delegate.keyHash, value, valueHash); 4667dd252788645e940eada959bdde927426e2531c9Paul Duffin insert(newEntry); 4677dd252788645e940eada959bdde927426e2531c9Paul Duffin expectedModCount = modCount; 4687dd252788645e940eada959bdde927426e2531c9Paul Duffin if (toRemove == delegate) { 4697dd252788645e940eada959bdde927426e2531c9Paul Duffin toRemove = newEntry; 4707dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4717dd252788645e940eada959bdde927426e2531c9Paul Duffin delegate = newEntry; 4727dd252788645e940eada959bdde927426e2531c9Paul Duffin return oldValue; 4737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4747dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4757dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 4767dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4777dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4787dd252788645e940eada959bdde927426e2531c9Paul Duffin 4797dd252788645e940eada959bdde927426e2531c9Paul Duffin private transient BiMap<V, K> inverse; 4807dd252788645e940eada959bdde927426e2531c9Paul Duffin 4810888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 4827dd252788645e940eada959bdde927426e2531c9Paul Duffin public BiMap<V, K> inverse() { 4837dd252788645e940eada959bdde927426e2531c9Paul Duffin return (inverse == null) ? inverse = new Inverse() : inverse; 4847dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4857dd252788645e940eada959bdde927426e2531c9Paul Duffin 4867dd252788645e940eada959bdde927426e2531c9Paul Duffin private final class Inverse extends AbstractMap<V, K> implements BiMap<V, K>, Serializable { 4877dd252788645e940eada959bdde927426e2531c9Paul Duffin BiMap<K, V> forward() { 4887dd252788645e940eada959bdde927426e2531c9Paul Duffin return HashBiMap.this; 4897dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4907dd252788645e940eada959bdde927426e2531c9Paul Duffin 4917dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4927dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 4937dd252788645e940eada959bdde927426e2531c9Paul Duffin return size; 4947dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4957dd252788645e940eada959bdde927426e2531c9Paul Duffin 4967dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4977dd252788645e940eada959bdde927426e2531c9Paul Duffin public void clear() { 4987dd252788645e940eada959bdde927426e2531c9Paul Duffin forward().clear(); 4997dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5007dd252788645e940eada959bdde927426e2531c9Paul Duffin 5017dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5027dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean containsKey(@Nullable Object value) { 5037dd252788645e940eada959bdde927426e2531c9Paul Duffin return forward().containsValue(value); 5047dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5057dd252788645e940eada959bdde927426e2531c9Paul Duffin 5067dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5077dd252788645e940eada959bdde927426e2531c9Paul Duffin public K get(@Nullable Object value) { 5087dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByValue(value, hash(value)); 5097dd252788645e940eada959bdde927426e2531c9Paul Duffin return (entry == null) ? null : entry.key; 5107dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5117dd252788645e940eada959bdde927426e2531c9Paul Duffin 5127dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5137dd252788645e940eada959bdde927426e2531c9Paul Duffin public K put(@Nullable V value, @Nullable K key) { 5147dd252788645e940eada959bdde927426e2531c9Paul Duffin return putInverse(value, key, false); 5157dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5167dd252788645e940eada959bdde927426e2531c9Paul Duffin 5170888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5187dd252788645e940eada959bdde927426e2531c9Paul Duffin public K forcePut(@Nullable V value, @Nullable K key) { 5197dd252788645e940eada959bdde927426e2531c9Paul Duffin return putInverse(value, key, true); 5207dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5217dd252788645e940eada959bdde927426e2531c9Paul Duffin 5227dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5237dd252788645e940eada959bdde927426e2531c9Paul Duffin public K remove(@Nullable Object value) { 5247dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByValue(value, hash(value)); 5257dd252788645e940eada959bdde927426e2531c9Paul Duffin if (entry == null) { 5267dd252788645e940eada959bdde927426e2531c9Paul Duffin return null; 5277dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 5287dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(entry); 5297dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry.key; 5307dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5317dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5327dd252788645e940eada959bdde927426e2531c9Paul Duffin 5330888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 5347dd252788645e940eada959bdde927426e2531c9Paul Duffin public BiMap<K, V> inverse() { 5357dd252788645e940eada959bdde927426e2531c9Paul Duffin return forward(); 5367dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5377dd252788645e940eada959bdde927426e2531c9Paul Duffin 5387dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5397dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<V> keySet() { 5407dd252788645e940eada959bdde927426e2531c9Paul Duffin return new InverseKeySet(); 5417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5427dd252788645e940eada959bdde927426e2531c9Paul Duffin 5437dd252788645e940eada959bdde927426e2531c9Paul Duffin private final class InverseKeySet extends Maps.KeySet<V, K> { 5440888a09821a98ac0680fad765217302858e70fa4Paul Duffin InverseKeySet() { 5450888a09821a98ac0680fad765217302858e70fa4Paul Duffin super(Inverse.this); 5467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5477dd252788645e940eada959bdde927426e2531c9Paul Duffin 5487dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5497dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean remove(@Nullable Object o) { 5507dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> entry = seekByValue(o, hash(o)); 5517dd252788645e940eada959bdde927426e2531c9Paul Duffin if (entry == null) { 5527dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 5537dd252788645e940eada959bdde927426e2531c9Paul Duffin } else { 5547dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(entry); 5557dd252788645e940eada959bdde927426e2531c9Paul Duffin return true; 5567dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5577dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5587dd252788645e940eada959bdde927426e2531c9Paul Duffin 5597dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5607dd252788645e940eada959bdde927426e2531c9Paul Duffin public Iterator<V> iterator() { 5617dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Itr<V>() { 5620888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override V output(BiEntry<K, V> entry) { 5637dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry.value; 5647dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5657dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 5667dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5677dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5687dd252788645e940eada959bdde927426e2531c9Paul Duffin 5697dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5707dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<K> values() { 5717dd252788645e940eada959bdde927426e2531c9Paul Duffin return forward().keySet(); 5727dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5737dd252788645e940eada959bdde927426e2531c9Paul Duffin 5747dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5757dd252788645e940eada959bdde927426e2531c9Paul Duffin public Set<Entry<V, K>> entrySet() { 5767dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Maps.EntrySet<V, K>() { 5777dd252788645e940eada959bdde927426e2531c9Paul Duffin 5787dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5797dd252788645e940eada959bdde927426e2531c9Paul Duffin Map<V, K> map() { 5807dd252788645e940eada959bdde927426e2531c9Paul Duffin return Inverse.this; 5817dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5827dd252788645e940eada959bdde927426e2531c9Paul Duffin 5837dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5847dd252788645e940eada959bdde927426e2531c9Paul Duffin public Iterator<Entry<V, K>> iterator() { 5857dd252788645e940eada959bdde927426e2531c9Paul Duffin return new Itr<Entry<V, K>>() { 5867dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5877dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<V, K> output(BiEntry<K, V> entry) { 5887dd252788645e940eada959bdde927426e2531c9Paul Duffin return new InverseEntry(entry); 5897dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5907dd252788645e940eada959bdde927426e2531c9Paul Duffin 5917dd252788645e940eada959bdde927426e2531c9Paul Duffin class InverseEntry extends AbstractMapEntry<V, K> { 5927dd252788645e940eada959bdde927426e2531c9Paul Duffin BiEntry<K, V> delegate; 5937dd252788645e940eada959bdde927426e2531c9Paul Duffin 5947dd252788645e940eada959bdde927426e2531c9Paul Duffin InverseEntry(BiEntry<K, V> entry) { 5957dd252788645e940eada959bdde927426e2531c9Paul Duffin this.delegate = entry; 5967dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5977dd252788645e940eada959bdde927426e2531c9Paul Duffin 5987dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5997dd252788645e940eada959bdde927426e2531c9Paul Duffin public V getKey() { 6007dd252788645e940eada959bdde927426e2531c9Paul Duffin return delegate.value; 6017dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6027dd252788645e940eada959bdde927426e2531c9Paul Duffin 6037dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6047dd252788645e940eada959bdde927426e2531c9Paul Duffin public K getValue() { 6057dd252788645e940eada959bdde927426e2531c9Paul Duffin return delegate.key; 6067dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6077dd252788645e940eada959bdde927426e2531c9Paul Duffin 6087dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6097dd252788645e940eada959bdde927426e2531c9Paul Duffin public K setValue(K key) { 6107dd252788645e940eada959bdde927426e2531c9Paul Duffin K oldKey = delegate.key; 6117dd252788645e940eada959bdde927426e2531c9Paul Duffin int keyHash = hash(key); 6127dd252788645e940eada959bdde927426e2531c9Paul Duffin if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) { 6137dd252788645e940eada959bdde927426e2531c9Paul Duffin return key; 6147dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6157dd252788645e940eada959bdde927426e2531c9Paul Duffin checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key); 6167dd252788645e940eada959bdde927426e2531c9Paul Duffin delete(delegate); 6170888a09821a98ac0680fad765217302858e70fa4Paul Duffin BiEntry<K, V> newEntry = 6180888a09821a98ac0680fad765217302858e70fa4Paul Duffin new BiEntry<K, V>(key, keyHash, delegate.value, delegate.valueHash); 6197dd252788645e940eada959bdde927426e2531c9Paul Duffin insert(newEntry); 6207dd252788645e940eada959bdde927426e2531c9Paul Duffin expectedModCount = modCount; 6217dd252788645e940eada959bdde927426e2531c9Paul Duffin // This is safe because entries can only get bumped up to earlier in the iteration, 6227dd252788645e940eada959bdde927426e2531c9Paul Duffin // so they can't get revisited. 6237dd252788645e940eada959bdde927426e2531c9Paul Duffin return oldKey; 6247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6257dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6267dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 6277dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6287dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 6297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6307dd252788645e940eada959bdde927426e2531c9Paul Duffin 6317dd252788645e940eada959bdde927426e2531c9Paul Duffin Object writeReplace() { 6327dd252788645e940eada959bdde927426e2531c9Paul Duffin return new InverseSerializedForm<K, V>(HashBiMap.this); 6337dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6357dd252788645e940eada959bdde927426e2531c9Paul Duffin 6367dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final class InverseSerializedForm<K, V> implements Serializable { 6377dd252788645e940eada959bdde927426e2531c9Paul Duffin private final HashBiMap<K, V> bimap; 6387dd252788645e940eada959bdde927426e2531c9Paul Duffin 6397dd252788645e940eada959bdde927426e2531c9Paul Duffin InverseSerializedForm(HashBiMap<K, V> bimap) { 6407dd252788645e940eada959bdde927426e2531c9Paul Duffin this.bimap = bimap; 6417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6427dd252788645e940eada959bdde927426e2531c9Paul Duffin 6437dd252788645e940eada959bdde927426e2531c9Paul Duffin Object readResolve() { 6447dd252788645e940eada959bdde927426e2531c9Paul Duffin return bimap.inverse(); 6457dd252788645e940eada959bdde927426e2531c9Paul Duffin } 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 6497dd252788645e940eada959bdde927426e2531c9Paul Duffin * @serialData the number of entries, first key, first value, second key, second value, and so on. 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectOutputStream") 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultWriteObject(); 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.writeMap(this, stream); 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 6587dd252788645e940eada959bdde927426e2531c9Paul Duffin private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = Serialization.readCount(stream); 6617dd252788645e940eada959bdde927426e2531c9Paul Duffin init(size); 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.populateMap(this, stream, size); 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("Not needed in emulated source") 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 668