001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005 * in compliance with the License. You may obtain a copy of the License at
006 *
007 * http://www.apache.org/licenses/LICENSE-2.0
008 *
009 * Unless required by applicable law or agreed to in writing, software distributed under the License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.collect;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkNotNull;
019import static com.google.common.collect.CollectPreconditions.checkNonnegative;
020import static com.google.common.collect.CollectPreconditions.checkRemove;
021import static com.google.common.collect.Hashing.smearedHash;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.base.Objects;
026import com.google.common.collect.Maps.IteratorBasedAbstractMap;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.j2objc.annotations.RetainedWith;
029import com.google.j2objc.annotations.WeakOuter;
030import java.io.IOException;
031import java.io.ObjectInputStream;
032import java.io.ObjectOutputStream;
033import java.io.Serializable;
034import java.util.Arrays;
035import java.util.ConcurrentModificationException;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.NoSuchElementException;
039import java.util.Set;
040import java.util.function.BiConsumer;
041import java.util.function.BiFunction;
042import org.checkerframework.checker.nullness.compatqual.MonotonicNonNullDecl;
043import org.checkerframework.checker.nullness.compatqual.NullableDecl;
044
045/**
046 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
047 * {@code HashBiMap} and its inverse are both serializable.
048 *
049 * <p>This implementation guarantees insertion-based iteration order of its keys.
050 *
051 * <p>See the Guava User Guide article on <a href=
052 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap"> {@code BiMap} </a>.
053 *
054 * @author Louis Wasserman
055 * @author Mike Bostock
056 * @since 2.0
057 */
058@GwtCompatible(emulated = true)
059public final class HashBiMap<K, V> extends IteratorBasedAbstractMap<K, V>
060    implements BiMap<K, V>, Serializable {
061
062  /** Returns a new, empty {@code HashBiMap} with the default initial capacity (16). */
063  public static <K, V> HashBiMap<K, V> create() {
064    return create(16);
065  }
066
067  /**
068   * Constructs a new, empty bimap with the specified expected size.
069   *
070   * @param expectedSize the expected number of entries
071   * @throws IllegalArgumentException if the specified expected size is negative
072   */
073  public static <K, V> HashBiMap<K, V> create(int expectedSize) {
074    return new HashBiMap<>(expectedSize);
075  }
076
077  /**
078   * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
079   * initial capacity sufficient to hold the mappings in the specified map.
080   */
081  public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
082    HashBiMap<K, V> bimap = create(map.size());
083    bimap.putAll(map);
084    return bimap;
085  }
086
087  private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
088    final int keyHash;
089    final int valueHash;
090
091    @NullableDecl BiEntry<K, V> nextInKToVBucket;
092    @NullableDecl BiEntry<K, V> nextInVToKBucket;
093
094    @NullableDecl BiEntry<K, V> nextInKeyInsertionOrder;
095    @NullableDecl BiEntry<K, V> prevInKeyInsertionOrder;
096
097    BiEntry(K key, int keyHash, V value, int valueHash) {
098      super(key, value);
099      this.keyHash = keyHash;
100      this.valueHash = valueHash;
101    }
102  }
103
104  private static final double LOAD_FACTOR = 1.0;
105
106  private transient BiEntry<K, V>[] hashTableKToV;
107  private transient BiEntry<K, V>[] hashTableVToK;
108  @NullableDecl private transient BiEntry<K, V> firstInKeyInsertionOrder;
109  @NullableDecl private transient BiEntry<K, V> lastInKeyInsertionOrder;
110  private transient int size;
111  private transient int mask;
112  private transient int modCount;
113
114  private HashBiMap(int expectedSize) {
115    init(expectedSize);
116  }
117
118  private void init(int expectedSize) {
119    checkNonnegative(expectedSize, "expectedSize");
120    int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR);
121    this.hashTableKToV = createTable(tableSize);
122    this.hashTableVToK = createTable(tableSize);
123    this.firstInKeyInsertionOrder = null;
124    this.lastInKeyInsertionOrder = null;
125    this.size = 0;
126    this.mask = tableSize - 1;
127    this.modCount = 0;
128  }
129
130  /**
131   * Finds and removes {@code entry} from the bucket linked lists in both the key-to-value direction
132   * and the value-to-key direction.
133   */
134  private void delete(BiEntry<K, V> entry) {
135    int keyBucket = entry.keyHash & mask;
136    BiEntry<K, V> prevBucketEntry = null;
137    for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket];
138        true;
139        bucketEntry = bucketEntry.nextInKToVBucket) {
140      if (bucketEntry == entry) {
141        if (prevBucketEntry == null) {
142          hashTableKToV[keyBucket] = entry.nextInKToVBucket;
143        } else {
144          prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
145        }
146        break;
147      }
148      prevBucketEntry = bucketEntry;
149    }
150
151    int valueBucket = entry.valueHash & mask;
152    prevBucketEntry = null;
153    for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];
154        true;
155        bucketEntry = bucketEntry.nextInVToKBucket) {
156      if (bucketEntry == entry) {
157        if (prevBucketEntry == null) {
158          hashTableVToK[valueBucket] = entry.nextInVToKBucket;
159        } else {
160          prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
161        }
162        break;
163      }
164      prevBucketEntry = bucketEntry;
165    }
166
167    if (entry.prevInKeyInsertionOrder == null) {
168      firstInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
169    } else {
170      entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry.nextInKeyInsertionOrder;
171    }
172
173    if (entry.nextInKeyInsertionOrder == null) {
174      lastInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
175    } else {
176      entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry.prevInKeyInsertionOrder;
177    }
178
179    size--;
180    modCount++;
181  }
182
183  private void insert(BiEntry<K, V> entry, @NullableDecl BiEntry<K, V> oldEntryForKey) {
184    int keyBucket = entry.keyHash & mask;
185    entry.nextInKToVBucket = hashTableKToV[keyBucket];
186    hashTableKToV[keyBucket] = entry;
187
188    int valueBucket = entry.valueHash & mask;
189    entry.nextInVToKBucket = hashTableVToK[valueBucket];
190    hashTableVToK[valueBucket] = entry;
191
192    if (oldEntryForKey == null) {
193      entry.prevInKeyInsertionOrder = lastInKeyInsertionOrder;
194      entry.nextInKeyInsertionOrder = null;
195      if (lastInKeyInsertionOrder == null) {
196        firstInKeyInsertionOrder = entry;
197      } else {
198        lastInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
199      }
200      lastInKeyInsertionOrder = entry;
201    } else {
202      entry.prevInKeyInsertionOrder = oldEntryForKey.prevInKeyInsertionOrder;
203      if (entry.prevInKeyInsertionOrder == null) {
204        firstInKeyInsertionOrder = entry;
205      } else {
206        entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry;
207      }
208      entry.nextInKeyInsertionOrder = oldEntryForKey.nextInKeyInsertionOrder;
209      if (entry.nextInKeyInsertionOrder == null) {
210        lastInKeyInsertionOrder = entry;
211      } else {
212        entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry;
213      }
214    }
215
216    size++;
217    modCount++;
218  }
219
220  private BiEntry<K, V> seekByKey(@NullableDecl Object key, int keyHash) {
221    for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask];
222        entry != null;
223        entry = entry.nextInKToVBucket) {
224      if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
225        return entry;
226      }
227    }
228    return null;
229  }
230
231  private BiEntry<K, V> seekByValue(@NullableDecl Object value, int valueHash) {
232    for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask];
233        entry != null;
234        entry = entry.nextInVToKBucket) {
235      if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) {
236        return entry;
237      }
238    }
239    return null;
240  }
241
242  @Override
243  public boolean containsKey(@NullableDecl Object key) {
244    return seekByKey(key, smearedHash(key)) != null;
245  }
246
247  @Override
248  public boolean containsValue(@NullableDecl Object value) {
249    return seekByValue(value, smearedHash(value)) != null;
250  }
251
252  @NullableDecl
253  @Override
254  public V get(@NullableDecl Object key) {
255    return Maps.valueOrNull(seekByKey(key, smearedHash(key)));
256  }
257
258  @CanIgnoreReturnValue
259  @Override
260  public V put(@NullableDecl K key, @NullableDecl V value) {
261    return put(key, value, false);
262  }
263
264  @CanIgnoreReturnValue
265  @Override
266  public V forcePut(@NullableDecl K key, @NullableDecl V value) {
267    return put(key, value, true);
268  }
269
270  private V put(@NullableDecl K key, @NullableDecl V value, boolean force) {
271    int keyHash = smearedHash(key);
272    int valueHash = smearedHash(value);
273
274    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
275    if (oldEntryForKey != null
276        && valueHash == oldEntryForKey.valueHash
277        && Objects.equal(value, oldEntryForKey.value)) {
278      return value;
279    }
280
281    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
282    if (oldEntryForValue != null) {
283      if (force) {
284        delete(oldEntryForValue);
285      } else {
286        throw new IllegalArgumentException("value already present: " + value);
287      }
288    }
289
290    BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash);
291    if (oldEntryForKey != null) {
292      delete(oldEntryForKey);
293      insert(newEntry, oldEntryForKey);
294      oldEntryForKey.prevInKeyInsertionOrder = null;
295      oldEntryForKey.nextInKeyInsertionOrder = null;
296      rehashIfNecessary();
297      return oldEntryForKey.value;
298    } else {
299      insert(newEntry, null);
300      rehashIfNecessary();
301      return null;
302    }
303  }
304
305  @NullableDecl
306  private K putInverse(@NullableDecl V value, @NullableDecl K key, boolean force) {
307    int valueHash = smearedHash(value);
308    int keyHash = smearedHash(key);
309
310    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
311    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
312    if (oldEntryForValue != null
313        && keyHash == oldEntryForValue.keyHash
314        && Objects.equal(key, oldEntryForValue.key)) {
315      return key;
316    } else if (oldEntryForKey != null && !force) {
317      throw new IllegalArgumentException("key already present: " + key);
318    }
319
320    /*
321     * The ordering here is important: if we deleted the key entry and then the value entry,
322     * the key entry's prev or next pointer might point to the dead value entry, and when we
323     * put the new entry in the key entry's position in iteration order, it might invalidate
324     * the linked list.
325     */
326
327    if (oldEntryForValue != null) {
328      delete(oldEntryForValue);
329    }
330
331    if (oldEntryForKey != null) {
332      delete(oldEntryForKey);
333    }
334
335    BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash);
336    insert(newEntry, oldEntryForKey);
337
338    if (oldEntryForKey != null) {
339      oldEntryForKey.prevInKeyInsertionOrder = null;
340      oldEntryForKey.nextInKeyInsertionOrder = null;
341    }
342    if (oldEntryForValue != null) {
343      oldEntryForValue.prevInKeyInsertionOrder = null;
344      oldEntryForValue.nextInKeyInsertionOrder = null;
345    }
346    rehashIfNecessary();
347    return Maps.keyOrNull(oldEntryForValue);
348  }
349
350  private void rehashIfNecessary() {
351    BiEntry<K, V>[] oldKToV = hashTableKToV;
352    if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
353      int newTableSize = oldKToV.length * 2;
354
355      this.hashTableKToV = createTable(newTableSize);
356      this.hashTableVToK = createTable(newTableSize);
357      this.mask = newTableSize - 1;
358      this.size = 0;
359
360      for (BiEntry<K, V> entry = firstInKeyInsertionOrder;
361          entry != null;
362          entry = entry.nextInKeyInsertionOrder) {
363        insert(entry, entry);
364      }
365      this.modCount++;
366    }
367  }
368
369  @SuppressWarnings("unchecked")
370  private BiEntry<K, V>[] createTable(int length) {
371    return new BiEntry[length];
372  }
373
374  @CanIgnoreReturnValue
375  @Override
376  public V remove(@NullableDecl Object key) {
377    BiEntry<K, V> entry = seekByKey(key, smearedHash(key));
378    if (entry == null) {
379      return null;
380    } else {
381      delete(entry);
382      entry.prevInKeyInsertionOrder = null;
383      entry.nextInKeyInsertionOrder = null;
384      return entry.value;
385    }
386  }
387
388  @Override
389  public void clear() {
390    size = 0;
391    Arrays.fill(hashTableKToV, null);
392    Arrays.fill(hashTableVToK, null);
393    firstInKeyInsertionOrder = null;
394    lastInKeyInsertionOrder = null;
395    modCount++;
396  }
397
398  @Override
399  public int size() {
400    return size;
401  }
402
403  abstract class Itr<T> implements Iterator<T> {
404    BiEntry<K, V> next = firstInKeyInsertionOrder;
405    BiEntry<K, V> toRemove = null;
406    int expectedModCount = modCount;
407    int remaining = size();
408
409    @Override
410    public boolean hasNext() {
411      if (modCount != expectedModCount) {
412        throw new ConcurrentModificationException();
413      }
414      return next != null && remaining > 0;
415    }
416
417    @Override
418    public T next() {
419      if (!hasNext()) {
420        throw new NoSuchElementException();
421      }
422
423      BiEntry<K, V> entry = next;
424      next = entry.nextInKeyInsertionOrder;
425      toRemove = entry;
426      remaining--;
427      return output(entry);
428    }
429
430    @Override
431    public void remove() {
432      if (modCount != expectedModCount) {
433        throw new ConcurrentModificationException();
434      }
435      checkRemove(toRemove != null);
436      delete(toRemove);
437      expectedModCount = modCount;
438      toRemove = null;
439    }
440
441    abstract T output(BiEntry<K, V> entry);
442  }
443
444  @Override
445  public Set<K> keySet() {
446    return new KeySet();
447  }
448
449  @WeakOuter
450  private final class KeySet extends Maps.KeySet<K, V> {
451    KeySet() {
452      super(HashBiMap.this);
453    }
454
455    @Override
456    public Iterator<K> iterator() {
457      return new Itr<K>() {
458        @Override
459        K output(BiEntry<K, V> entry) {
460          return entry.key;
461        }
462      };
463    }
464
465    @Override
466    public boolean remove(@NullableDecl Object o) {
467      BiEntry<K, V> entry = seekByKey(o, smearedHash(o));
468      if (entry == null) {
469        return false;
470      } else {
471        delete(entry);
472        entry.prevInKeyInsertionOrder = null;
473        entry.nextInKeyInsertionOrder = null;
474        return true;
475      }
476    }
477  }
478
479  @Override
480  public Set<V> values() {
481    return inverse().keySet();
482  }
483
484  @Override
485  Iterator<Entry<K, V>> entryIterator() {
486    return new Itr<Entry<K, V>>() {
487      @Override
488      Entry<K, V> output(BiEntry<K, V> entry) {
489        return new MapEntry(entry);
490      }
491
492      class MapEntry extends AbstractMapEntry<K, V> {
493        BiEntry<K, V> delegate;
494
495        MapEntry(BiEntry<K, V> entry) {
496          this.delegate = entry;
497        }
498
499        @Override
500        public K getKey() {
501          return delegate.key;
502        }
503
504        @Override
505        public V getValue() {
506          return delegate.value;
507        }
508
509        @Override
510        public V setValue(V value) {
511          V oldValue = delegate.value;
512          int valueHash = smearedHash(value);
513          if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) {
514            return value;
515          }
516          checkArgument(seekByValue(value, valueHash) == null, "value already present: %s", value);
517          delete(delegate);
518          BiEntry<K, V> newEntry = new BiEntry<>(delegate.key, delegate.keyHash, value, valueHash);
519          insert(newEntry, delegate);
520          delegate.prevInKeyInsertionOrder = null;
521          delegate.nextInKeyInsertionOrder = null;
522          expectedModCount = modCount;
523          if (toRemove == delegate) {
524            toRemove = newEntry;
525          }
526          delegate = newEntry;
527          return oldValue;
528        }
529      }
530    };
531  }
532
533  @Override
534  public void forEach(BiConsumer<? super K, ? super V> action) {
535    checkNotNull(action);
536    for (BiEntry<K, V> entry = firstInKeyInsertionOrder;
537        entry != null;
538        entry = entry.nextInKeyInsertionOrder) {
539      action.accept(entry.key, entry.value);
540    }
541  }
542
543  @Override
544  public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
545    checkNotNull(function);
546    BiEntry<K, V> oldFirst = firstInKeyInsertionOrder;
547    clear();
548    for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) {
549      put(entry.key, function.apply(entry.key, entry.value));
550    }
551  }
552
553  @MonotonicNonNullDecl @RetainedWith private transient BiMap<V, K> inverse;
554
555  @Override
556  public BiMap<V, K> inverse() {
557    BiMap<V, K> result = inverse;
558    return (result == null) ? inverse = new Inverse() : result;
559  }
560
561  private final class Inverse extends IteratorBasedAbstractMap<V, K>
562      implements BiMap<V, K>, Serializable {
563    BiMap<K, V> forward() {
564      return HashBiMap.this;
565    }
566
567    @Override
568    public int size() {
569      return size;
570    }
571
572    @Override
573    public void clear() {
574      forward().clear();
575    }
576
577    @Override
578    public boolean containsKey(@NullableDecl Object value) {
579      return forward().containsValue(value);
580    }
581
582    @Override
583    public K get(@NullableDecl Object value) {
584      return Maps.keyOrNull(seekByValue(value, smearedHash(value)));
585    }
586
587    @CanIgnoreReturnValue
588    @Override
589    public K put(@NullableDecl V value, @NullableDecl K key) {
590      return putInverse(value, key, false);
591    }
592
593    @Override
594    public K forcePut(@NullableDecl V value, @NullableDecl K key) {
595      return putInverse(value, key, true);
596    }
597
598    @Override
599    public K remove(@NullableDecl Object value) {
600      BiEntry<K, V> entry = seekByValue(value, smearedHash(value));
601      if (entry == null) {
602        return null;
603      } else {
604        delete(entry);
605        entry.prevInKeyInsertionOrder = null;
606        entry.nextInKeyInsertionOrder = null;
607        return entry.key;
608      }
609    }
610
611    @Override
612    public BiMap<K, V> inverse() {
613      return forward();
614    }
615
616    @Override
617    public Set<V> keySet() {
618      return new InverseKeySet();
619    }
620
621    @WeakOuter
622    private final class InverseKeySet extends Maps.KeySet<V, K> {
623      InverseKeySet() {
624        super(Inverse.this);
625      }
626
627      @Override
628      public boolean remove(@NullableDecl Object o) {
629        BiEntry<K, V> entry = seekByValue(o, smearedHash(o));
630        if (entry == null) {
631          return false;
632        } else {
633          delete(entry);
634          return true;
635        }
636      }
637
638      @Override
639      public Iterator<V> iterator() {
640        return new Itr<V>() {
641          @Override
642          V output(BiEntry<K, V> entry) {
643            return entry.value;
644          }
645        };
646      }
647    }
648
649    @Override
650    public Set<K> values() {
651      return forward().keySet();
652    }
653
654    @Override
655    Iterator<Entry<V, K>> entryIterator() {
656      return new Itr<Entry<V, K>>() {
657        @Override
658        Entry<V, K> output(BiEntry<K, V> entry) {
659          return new InverseEntry(entry);
660        }
661
662        class InverseEntry extends AbstractMapEntry<V, K> {
663          BiEntry<K, V> delegate;
664
665          InverseEntry(BiEntry<K, V> entry) {
666            this.delegate = entry;
667          }
668
669          @Override
670          public V getKey() {
671            return delegate.value;
672          }
673
674          @Override
675          public K getValue() {
676            return delegate.key;
677          }
678
679          @Override
680          public K setValue(K key) {
681            K oldKey = delegate.key;
682            int keyHash = smearedHash(key);
683            if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) {
684              return key;
685            }
686            checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key);
687            delete(delegate);
688            BiEntry<K, V> newEntry =
689                new BiEntry<>(key, keyHash, delegate.value, delegate.valueHash);
690            delegate = newEntry;
691            insert(newEntry, null);
692            expectedModCount = modCount;
693            return oldKey;
694          }
695        }
696      };
697    }
698
699    @Override
700    public void forEach(BiConsumer<? super V, ? super K> action) {
701      checkNotNull(action);
702      HashBiMap.this.forEach((k, v) -> action.accept(v, k));
703    }
704
705    @Override
706    public void replaceAll(BiFunction<? super V, ? super K, ? extends K> function) {
707      checkNotNull(function);
708      BiEntry<K, V> oldFirst = firstInKeyInsertionOrder;
709      clear();
710      for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) {
711        put(entry.value, function.apply(entry.value, entry.key));
712      }
713    }
714
715    Object writeReplace() {
716      return new InverseSerializedForm<>(HashBiMap.this);
717    }
718  }
719
720  private static final class InverseSerializedForm<K, V> implements Serializable {
721    private final HashBiMap<K, V> bimap;
722
723    InverseSerializedForm(HashBiMap<K, V> bimap) {
724      this.bimap = bimap;
725    }
726
727    Object readResolve() {
728      return bimap.inverse();
729    }
730  }
731
732  /**
733   * @serialData the number of entries, first key, first value, second key, second value, and so on.
734   */
735  @GwtIncompatible // java.io.ObjectOutputStream
736  private void writeObject(ObjectOutputStream stream) throws IOException {
737    stream.defaultWriteObject();
738    Serialization.writeMap(this, stream);
739  }
740
741  @GwtIncompatible // java.io.ObjectInputStream
742  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
743    stream.defaultReadObject();
744    int size = Serialization.readCount(stream);
745    init(16); // resist hostile attempts to allocate gratuitous heap
746    Serialization.populateMap(this, stream, size);
747  }
748
749  @GwtIncompatible // Not needed in emulated source
750  private static final long serialVersionUID = 0;
751}