1/*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkArgument;
18import static com.google.common.collect.CollectPreconditions.checkNonnegative;
19import static com.google.common.collect.CollectPreconditions.checkRemove;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.annotations.GwtIncompatible;
23import com.google.common.base.Objects;
24
25import java.io.IOException;
26import java.io.ObjectInputStream;
27import java.io.ObjectOutputStream;
28import java.io.Serializable;
29import java.util.AbstractMap;
30import java.util.Arrays;
31import java.util.ConcurrentModificationException;
32import java.util.Iterator;
33import java.util.Map;
34import java.util.NoSuchElementException;
35import java.util.Set;
36
37import javax.annotation.Nullable;
38
39/**
40 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
41 * {@code HashBiMap} and its inverse are both serializable.
42 *
43 * <p>See the Guava User Guide article on <a href=
44 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#BiMap"> {@code BiMap}
45 * </a>.
46 *
47 * @author Louis Wasserman
48 * @author Mike Bostock
49 * @since 2.0 (imported from Google Collections Library)
50 */
51@GwtCompatible(emulated = true)
52public final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K, V>, Serializable {
53
54  /**
55   * Returns a new, empty {@code HashBiMap} with the default initial capacity (16).
56   */
57  public static <K, V> HashBiMap<K, V> create() {
58    return create(16);
59  }
60
61  /**
62   * Constructs a new, empty bimap with the specified expected size.
63   *
64   * @param expectedSize the expected number of entries
65   * @throws IllegalArgumentException if the specified expected size is negative
66   */
67  public static <K, V> HashBiMap<K, V> create(int expectedSize) {
68    return new HashBiMap<K, V>(expectedSize);
69  }
70
71  /**
72   * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
73   * initial capacity sufficient to hold the mappings in the specified map.
74   */
75  public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
76    HashBiMap<K, V> bimap = create(map.size());
77    bimap.putAll(map);
78    return bimap;
79  }
80
81  private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
82    final int keyHash;
83    final int valueHash;
84
85    @Nullable
86    BiEntry<K, V> nextInKToVBucket;
87
88    @Nullable
89    BiEntry<K, V> nextInVToKBucket;
90
91    BiEntry(K key, int keyHash, V value, int valueHash) {
92      super(key, value);
93      this.keyHash = keyHash;
94      this.valueHash = valueHash;
95    }
96  }
97
98  private static final double LOAD_FACTOR = 1.0;
99
100  private transient BiEntry<K, V>[] hashTableKToV;
101  private transient BiEntry<K, V>[] hashTableVToK;
102  private transient int size;
103  private transient int mask;
104  private transient int modCount;
105
106  private HashBiMap(int expectedSize) {
107    init(expectedSize);
108  }
109
110  private void init(int expectedSize) {
111    checkNonnegative(expectedSize, "expectedSize");
112    int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR);
113    this.hashTableKToV = createTable(tableSize);
114    this.hashTableVToK = createTable(tableSize);
115    this.mask = tableSize - 1;
116    this.modCount = 0;
117    this.size = 0;
118  }
119
120  /**
121   * Finds and removes {@code entry} from the bucket linked lists in both the
122   * key-to-value direction and the value-to-key direction.
123   */
124  private void delete(BiEntry<K, V> entry) {
125    int keyBucket = entry.keyHash & mask;
126    BiEntry<K, V> prevBucketEntry = null;
127    for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket]; true;
128        bucketEntry = bucketEntry.nextInKToVBucket) {
129      if (bucketEntry == entry) {
130        if (prevBucketEntry == null) {
131          hashTableKToV[keyBucket] = entry.nextInKToVBucket;
132        } else {
133          prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
134        }
135        break;
136      }
137      prevBucketEntry = bucketEntry;
138    }
139
140    int valueBucket = entry.valueHash & mask;
141    prevBucketEntry = null;
142    for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];;
143        bucketEntry = bucketEntry.nextInVToKBucket) {
144      if (bucketEntry == entry) {
145        if (prevBucketEntry == null) {
146          hashTableVToK[valueBucket] = entry.nextInVToKBucket;
147        } else {
148          prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
149        }
150        break;
151      }
152      prevBucketEntry = bucketEntry;
153    }
154
155    size--;
156    modCount++;
157  }
158
159  private void insert(BiEntry<K, V> entry) {
160    int keyBucket = entry.keyHash & mask;
161    entry.nextInKToVBucket = hashTableKToV[keyBucket];
162    hashTableKToV[keyBucket] = entry;
163
164    int valueBucket = entry.valueHash & mask;
165    entry.nextInVToKBucket = hashTableVToK[valueBucket];
166    hashTableVToK[valueBucket] = entry;
167
168    size++;
169    modCount++;
170  }
171
172  private static int hash(@Nullable Object o) {
173    return Hashing.smear((o == null) ? 0 : o.hashCode());
174  }
175
176  private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
177    for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask]; entry != null;
178        entry = entry.nextInKToVBucket) {
179      if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
180        return entry;
181      }
182    }
183    return null;
184  }
185
186  private BiEntry<K, V> seekByValue(@Nullable Object value, int valueHash) {
187    for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask]; entry != null;
188        entry = entry.nextInVToKBucket) {
189      if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) {
190        return entry;
191      }
192    }
193    return null;
194  }
195
196  @Override
197  public boolean containsKey(@Nullable Object key) {
198    return seekByKey(key, hash(key)) != null;
199  }
200
201  @Override
202  public boolean containsValue(@Nullable Object value) {
203    return seekByValue(value, hash(value)) != null;
204  }
205
206  @Nullable
207  @Override
208  public V get(@Nullable Object key) {
209    BiEntry<K, V> entry = seekByKey(key, hash(key));
210    return (entry == null) ? null : entry.value;
211  }
212
213  @Override
214  public V put(@Nullable K key, @Nullable V value) {
215    return put(key, value, false);
216  }
217
218  @Override
219  public V forcePut(@Nullable K key, @Nullable V value) {
220    return put(key, value, true);
221  }
222
223  private V put(@Nullable K key, @Nullable V value, boolean force) {
224    int keyHash = hash(key);
225    int valueHash = hash(value);
226
227    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
228    if (oldEntryForKey != null && valueHash == oldEntryForKey.valueHash
229        && Objects.equal(value, oldEntryForKey.value)) {
230      return value;
231    }
232
233    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
234    if (oldEntryForValue != null) {
235      if (force) {
236        delete(oldEntryForValue);
237      } else {
238        throw new IllegalArgumentException("value already present: " + value);
239      }
240    }
241
242    if (oldEntryForKey != null) {
243      delete(oldEntryForKey);
244    }
245    BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
246    insert(newEntry);
247    rehashIfNecessary();
248    return (oldEntryForKey == null) ? null : oldEntryForKey.value;
249  }
250
251  @Nullable
252  private K putInverse(@Nullable V value, @Nullable K key, boolean force) {
253    int valueHash = hash(value);
254    int keyHash = hash(key);
255
256    BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
257    if (oldEntryForValue != null && keyHash == oldEntryForValue.keyHash
258        && Objects.equal(key, oldEntryForValue.key)) {
259      return key;
260    }
261
262    BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
263    if (oldEntryForKey != null) {
264      if (force) {
265        delete(oldEntryForKey);
266      } else {
267        throw new IllegalArgumentException("value already present: " + key);
268      }
269    }
270
271    if (oldEntryForValue != null) {
272      delete(oldEntryForValue);
273    }
274    BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
275    insert(newEntry);
276    rehashIfNecessary();
277    return (oldEntryForValue == null) ? null : oldEntryForValue.key;
278  }
279
280  private void rehashIfNecessary() {
281    BiEntry<K, V>[] oldKToV = hashTableKToV;
282    if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
283      int newTableSize = oldKToV.length * 2;
284
285      this.hashTableKToV = createTable(newTableSize);
286      this.hashTableVToK = createTable(newTableSize);
287      this.mask = newTableSize - 1;
288      this.size = 0;
289
290      for (int bucket = 0; bucket < oldKToV.length; bucket++) {
291        BiEntry<K, V> entry = oldKToV[bucket];
292        while (entry != null) {
293          BiEntry<K, V> nextEntry = entry.nextInKToVBucket;
294          insert(entry);
295          entry = nextEntry;
296        }
297      }
298      this.modCount++;
299    }
300  }
301
302  @SuppressWarnings("unchecked")
303  private BiEntry<K, V>[] createTable(int length) {
304    return new BiEntry[length];
305  }
306
307  @Override
308  public V remove(@Nullable Object key) {
309    BiEntry<K, V> entry = seekByKey(key, hash(key));
310    if (entry == null) {
311      return null;
312    } else {
313      delete(entry);
314      return entry.value;
315    }
316  }
317
318  @Override
319  public void clear() {
320    size = 0;
321    Arrays.fill(hashTableKToV, null);
322    Arrays.fill(hashTableVToK, null);
323    modCount++;
324  }
325
326  @Override
327  public int size() {
328    return size;
329  }
330
331  abstract class Itr<T> implements Iterator<T> {
332    int nextBucket = 0;
333    BiEntry<K, V> next = null;
334    BiEntry<K, V> toRemove = null;
335    int expectedModCount = modCount;
336
337    private void checkForConcurrentModification() {
338      if (modCount != expectedModCount) {
339        throw new ConcurrentModificationException();
340      }
341    }
342
343    @Override
344    public boolean hasNext() {
345      checkForConcurrentModification();
346      if (next != null) {
347        return true;
348      }
349      while (nextBucket < hashTableKToV.length) {
350        if (hashTableKToV[nextBucket] != null) {
351          next = hashTableKToV[nextBucket++];
352          return true;
353        }
354        nextBucket++;
355      }
356      return false;
357    }
358
359    @Override
360    public T next() {
361      checkForConcurrentModification();
362      if (!hasNext()) {
363        throw new NoSuchElementException();
364      }
365
366      BiEntry<K, V> entry = next;
367      next = entry.nextInKToVBucket;
368      toRemove = entry;
369      return output(entry);
370    }
371
372    @Override
373    public void remove() {
374      checkForConcurrentModification();
375      checkRemove(toRemove != null);
376      delete(toRemove);
377      expectedModCount = modCount;
378      toRemove = null;
379    }
380
381    abstract T output(BiEntry<K, V> entry);
382  }
383
384  @Override
385  public Set<K> keySet() {
386    return new KeySet();
387  }
388
389  private final class KeySet extends Maps.KeySet<K, V> {
390    KeySet() {
391      super(HashBiMap.this);
392    }
393
394    @Override
395    public Iterator<K> iterator() {
396      return new Itr<K>() {
397        @Override
398        K output(BiEntry<K, V> entry) {
399          return entry.key;
400        }
401      };
402    }
403
404    @Override
405    public boolean remove(@Nullable Object o) {
406      BiEntry<K, V> entry = seekByKey(o, hash(o));
407      if (entry == null) {
408        return false;
409      } else {
410        delete(entry);
411        return true;
412      }
413    }
414  }
415
416  @Override
417  public Set<V> values() {
418    return inverse().keySet();
419  }
420
421  @Override
422  public Set<Entry<K, V>> entrySet() {
423    return new EntrySet();
424  }
425
426  private final class EntrySet extends Maps.EntrySet<K, V> {
427    @Override
428    Map<K, V> map() {
429      return HashBiMap.this;
430    }
431
432    @Override
433    public Iterator<Entry<K, V>> iterator() {
434      return new Itr<Entry<K, V>>() {
435        @Override
436        Entry<K, V> output(BiEntry<K, V> entry) {
437          return new MapEntry(entry);
438        }
439
440        class MapEntry extends AbstractMapEntry<K, V> {
441          BiEntry<K, V> delegate;
442
443          MapEntry(BiEntry<K, V> entry) {
444            this.delegate = entry;
445          }
446
447          @Override public K getKey() {
448            return delegate.key;
449          }
450
451          @Override public V getValue() {
452            return delegate.value;
453          }
454
455          @Override public V setValue(V value) {
456            V oldValue = delegate.value;
457            int valueHash = hash(value);
458            if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) {
459              return value;
460            }
461            checkArgument(
462                seekByValue(value, valueHash) == null, "value already present: %s", value);
463            delete(delegate);
464            BiEntry<K, V> newEntry =
465                new BiEntry<K, V>(delegate.key, delegate.keyHash, value, valueHash);
466            insert(newEntry);
467            expectedModCount = modCount;
468            if (toRemove == delegate) {
469              toRemove = newEntry;
470            }
471            delegate = newEntry;
472            return oldValue;
473          }
474        }
475      };
476    }
477  }
478
479  private transient BiMap<V, K> inverse;
480
481  @Override
482  public BiMap<V, K> inverse() {
483    return (inverse == null) ? inverse = new Inverse() : inverse;
484  }
485
486  private final class Inverse extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
487    BiMap<K, V> forward() {
488      return HashBiMap.this;
489    }
490
491    @Override
492    public int size() {
493      return size;
494    }
495
496    @Override
497    public void clear() {
498      forward().clear();
499    }
500
501    @Override
502    public boolean containsKey(@Nullable Object value) {
503      return forward().containsValue(value);
504    }
505
506    @Override
507    public K get(@Nullable Object value) {
508      BiEntry<K, V> entry = seekByValue(value, hash(value));
509      return (entry == null) ? null : entry.key;
510    }
511
512    @Override
513    public K put(@Nullable V value, @Nullable K key) {
514      return putInverse(value, key, false);
515    }
516
517    @Override
518    public K forcePut(@Nullable V value, @Nullable K key) {
519      return putInverse(value, key, true);
520    }
521
522    @Override
523    public K remove(@Nullable Object value) {
524      BiEntry<K, V> entry = seekByValue(value, hash(value));
525      if (entry == null) {
526        return null;
527      } else {
528        delete(entry);
529        return entry.key;
530      }
531    }
532
533    @Override
534    public BiMap<K, V> inverse() {
535      return forward();
536    }
537
538    @Override
539    public Set<V> keySet() {
540      return new InverseKeySet();
541    }
542
543    private final class InverseKeySet extends Maps.KeySet<V, K> {
544      InverseKeySet() {
545        super(Inverse.this);
546      }
547
548      @Override
549      public boolean remove(@Nullable Object o) {
550        BiEntry<K, V> entry = seekByValue(o, hash(o));
551        if (entry == null) {
552          return false;
553        } else {
554          delete(entry);
555          return true;
556        }
557      }
558
559      @Override
560      public Iterator<V> iterator() {
561        return new Itr<V>() {
562          @Override V output(BiEntry<K, V> entry) {
563            return entry.value;
564          }
565        };
566      }
567    }
568
569    @Override
570    public Set<K> values() {
571      return forward().keySet();
572    }
573
574    @Override
575    public Set<Entry<V, K>> entrySet() {
576      return new Maps.EntrySet<V, K>() {
577
578        @Override
579        Map<V, K> map() {
580          return Inverse.this;
581        }
582
583        @Override
584        public Iterator<Entry<V, K>> iterator() {
585          return new Itr<Entry<V, K>>() {
586            @Override
587            Entry<V, K> output(BiEntry<K, V> entry) {
588              return new InverseEntry(entry);
589            }
590
591            class InverseEntry extends AbstractMapEntry<V, K> {
592              BiEntry<K, V> delegate;
593
594              InverseEntry(BiEntry<K, V> entry) {
595                this.delegate = entry;
596              }
597
598              @Override
599              public V getKey() {
600                return delegate.value;
601              }
602
603              @Override
604              public K getValue() {
605                return delegate.key;
606              }
607
608              @Override
609              public K setValue(K key) {
610                K oldKey = delegate.key;
611                int keyHash = hash(key);
612                if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) {
613                  return key;
614                }
615                checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key);
616                delete(delegate);
617                BiEntry<K, V> newEntry =
618                    new BiEntry<K, V>(key, keyHash, delegate.value, delegate.valueHash);
619                insert(newEntry);
620                expectedModCount = modCount;
621                // This is safe because entries can only get bumped up to earlier in the iteration,
622                // so they can't get revisited.
623                return oldKey;
624              }
625            }
626          };
627        }
628      };
629    }
630
631    Object writeReplace() {
632      return new InverseSerializedForm<K, V>(HashBiMap.this);
633    }
634  }
635
636  private static final class InverseSerializedForm<K, V> implements Serializable {
637    private final HashBiMap<K, V> bimap;
638
639    InverseSerializedForm(HashBiMap<K, V> bimap) {
640      this.bimap = bimap;
641    }
642
643    Object readResolve() {
644      return bimap.inverse();
645    }
646  }
647
648  /**
649   * @serialData the number of entries, first key, first value, second key, second value, and so on.
650   */
651  @GwtIncompatible("java.io.ObjectOutputStream")
652  private void writeObject(ObjectOutputStream stream) throws IOException {
653    stream.defaultWriteObject();
654    Serialization.writeMap(this, stream);
655  }
656
657  @GwtIncompatible("java.io.ObjectInputStream")
658  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
659    stream.defaultReadObject();
660    int size = Serialization.readCount(stream);
661    init(size);
662    Serialization.populateMap(this, stream, size);
663  }
664
665  @GwtIncompatible("Not needed in emulated source")
666  private static final long serialVersionUID = 0;
667}
668