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