1/*
2 * Copyright (C) 2008 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
20
21import com.google.common.annotations.GwtCompatible;
22import com.google.common.collect.ImmutableMapEntry.TerminalEntry;
23
24import java.io.Serializable;
25
26import javax.annotation.Nullable;
27
28/**
29 * Bimap with two or more mappings.
30 *
31 * @author Louis Wasserman
32 */
33@GwtCompatible(serializable = true, emulated = true)
34@SuppressWarnings("serial") // uses writeReplace(), not default serialization
35class RegularImmutableBiMap<K, V> extends ImmutableBiMap<K, V> {
36
37  static final double MAX_LOAD_FACTOR = 1.2;
38
39  private final transient ImmutableMapEntry<K, V>[] keyTable;
40  private final transient ImmutableMapEntry<K, V>[] valueTable;
41  private final transient ImmutableMapEntry<K, V>[] entries;
42  private final transient int mask;
43  private final transient int hashCode;
44
45  RegularImmutableBiMap(TerminalEntry<?, ?>... entriesToAdd) {
46    this(entriesToAdd.length, entriesToAdd);
47  }
48
49  /**
50   * Constructor for RegularImmutableBiMap that takes as input an array of {@code TerminalEntry}
51   * entries.  Assumes that these entries have already been checked for null.
52   *
53   * <p>This allows reuse of the entry objects from the array in the actual implementation.
54   */
55  RegularImmutableBiMap(int n, TerminalEntry<?, ?>[] entriesToAdd) {
56    int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
57    this.mask = tableSize - 1;
58    ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
59    ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
60    ImmutableMapEntry<K, V>[] entries = createEntryArray(n);
61    int hashCode = 0;
62
63    for (int i = 0; i < n; i++) {
64      @SuppressWarnings("unchecked")
65      TerminalEntry<K, V> entry = (TerminalEntry<K, V>) entriesToAdd[i];
66      K key = entry.getKey();
67      V value = entry.getValue();
68
69      int keyHash = key.hashCode();
70      int valueHash = value.hashCode();
71      int keyBucket = Hashing.smear(keyHash) & mask;
72      int valueBucket = Hashing.smear(valueHash) & mask;
73
74      ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
75      for (ImmutableMapEntry<K, V> keyEntry = nextInKeyBucket; keyEntry != null;
76           keyEntry = keyEntry.getNextInKeyBucket()) {
77        checkNoConflict(!key.equals(keyEntry.getKey()), "key", entry, keyEntry);
78      }
79      ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
80      for (ImmutableMapEntry<K, V> valueEntry = nextInValueBucket; valueEntry != null;
81           valueEntry = valueEntry.getNextInValueBucket()) {
82        checkNoConflict(!value.equals(valueEntry.getValue()), "value", entry, valueEntry);
83      }
84      ImmutableMapEntry<K, V> newEntry =
85          (nextInKeyBucket == null && nextInValueBucket == null)
86          ? entry
87          : new NonTerminalBiMapEntry<K, V>(entry, nextInKeyBucket, nextInValueBucket);
88      keyTable[keyBucket] = newEntry;
89      valueTable[valueBucket] = newEntry;
90      entries[i] = newEntry;
91      hashCode += keyHash ^ valueHash;
92    }
93
94    this.keyTable = keyTable;
95    this.valueTable = valueTable;
96    this.entries = entries;
97    this.hashCode = hashCode;
98  }
99
100  /**
101   * Constructor for RegularImmutableBiMap that makes no assumptions about the input entries.
102   */
103  RegularImmutableBiMap(Entry<?, ?>[] entriesToAdd) {
104    int n = entriesToAdd.length;
105    int tableSize = Hashing.closedTableSize(n, MAX_LOAD_FACTOR);
106    this.mask = tableSize - 1;
107    ImmutableMapEntry<K, V>[] keyTable = createEntryArray(tableSize);
108    ImmutableMapEntry<K, V>[] valueTable = createEntryArray(tableSize);
109    ImmutableMapEntry<K, V>[] entries = createEntryArray(n);
110    int hashCode = 0;
111
112    for (int i = 0; i < n; i++) {
113      @SuppressWarnings("unchecked")
114      Entry<K, V> entry = (Entry<K, V>) entriesToAdd[i];
115      K key = entry.getKey();
116      V value = entry.getValue();
117      checkEntryNotNull(key, value);
118      int keyHash = key.hashCode();
119      int valueHash = value.hashCode();
120      int keyBucket = Hashing.smear(keyHash) & mask;
121      int valueBucket = Hashing.smear(valueHash) & mask;
122
123      ImmutableMapEntry<K, V> nextInKeyBucket = keyTable[keyBucket];
124      for (ImmutableMapEntry<K, V> keyEntry = nextInKeyBucket; keyEntry != null;
125           keyEntry = keyEntry.getNextInKeyBucket()) {
126        checkNoConflict(!key.equals(keyEntry.getKey()), "key", entry, keyEntry);
127      }
128      ImmutableMapEntry<K, V> nextInValueBucket = valueTable[valueBucket];
129      for (ImmutableMapEntry<K, V> valueEntry = nextInValueBucket; valueEntry != null;
130           valueEntry = valueEntry.getNextInValueBucket()) {
131        checkNoConflict(!value.equals(valueEntry.getValue()), "value", entry, valueEntry);
132      }
133      ImmutableMapEntry<K, V> newEntry =
134          (nextInKeyBucket == null && nextInValueBucket == null)
135          ? new TerminalEntry<K, V>(key, value)
136          : new NonTerminalBiMapEntry<K, V>(key, value, nextInKeyBucket, nextInValueBucket);
137      keyTable[keyBucket] = newEntry;
138      valueTable[valueBucket] = newEntry;
139      entries[i] = newEntry;
140      hashCode += keyHash ^ valueHash;
141    }
142
143    this.keyTable = keyTable;
144    this.valueTable = valueTable;
145    this.entries = entries;
146    this.hashCode = hashCode;
147  }
148
149  private static final class NonTerminalBiMapEntry<K, V> extends ImmutableMapEntry<K, V> {
150    @Nullable private final ImmutableMapEntry<K, V> nextInKeyBucket;
151    @Nullable private final ImmutableMapEntry<K, V> nextInValueBucket;
152
153    NonTerminalBiMapEntry(K key, V value, @Nullable ImmutableMapEntry<K, V> nextInKeyBucket,
154        @Nullable ImmutableMapEntry<K, V> nextInValueBucket) {
155      super(key, value);
156      this.nextInKeyBucket = nextInKeyBucket;
157      this.nextInValueBucket = nextInValueBucket;
158    }
159
160    NonTerminalBiMapEntry(ImmutableMapEntry<K, V> contents,
161        @Nullable ImmutableMapEntry<K, V> nextInKeyBucket,
162        @Nullable ImmutableMapEntry<K, V> nextInValueBucket) {
163      super(contents);
164      this.nextInKeyBucket = nextInKeyBucket;
165      this.nextInValueBucket = nextInValueBucket;
166    }
167
168    @Override
169    @Nullable
170    ImmutableMapEntry<K, V> getNextInKeyBucket() {
171      return nextInKeyBucket;
172    }
173
174    @Override
175    @Nullable
176    ImmutableMapEntry<K, V> getNextInValueBucket() {
177      return nextInValueBucket;
178    }
179  }
180
181  @SuppressWarnings("unchecked")
182  private static <K, V> ImmutableMapEntry<K, V>[] createEntryArray(int length) {
183    return new ImmutableMapEntry[length];
184  }
185
186  @Override
187  @Nullable
188  public V get(@Nullable Object key) {
189    if (key == null) {
190      return null;
191    }
192    int bucket = Hashing.smear(key.hashCode()) & mask;
193    for (ImmutableMapEntry<K, V> entry = keyTable[bucket]; entry != null;
194         entry = entry.getNextInKeyBucket()) {
195      if (key.equals(entry.getKey())) {
196        return entry.getValue();
197      }
198    }
199    return null;
200  }
201
202  @Override
203  ImmutableSet<Entry<K, V>> createEntrySet() {
204    return new ImmutableMapEntrySet<K, V>() {
205      @Override
206      ImmutableMap<K, V> map() {
207        return RegularImmutableBiMap.this;
208      }
209
210      @Override
211      public UnmodifiableIterator<Entry<K, V>> iterator() {
212        return asList().iterator();
213      }
214
215      @Override
216      ImmutableList<Entry<K, V>> createAsList() {
217        return new RegularImmutableAsList<Entry<K, V>>(this, entries);
218      }
219
220      @Override
221      boolean isHashCodeFast() {
222        return true;
223      }
224
225      @Override
226      public int hashCode() {
227        return hashCode;
228      }
229    };
230  }
231
232  @Override
233  boolean isPartialView() {
234    return false;
235  }
236
237  @Override
238  public int size() {
239    return entries.length;
240  }
241
242  private transient ImmutableBiMap<V, K> inverse;
243
244  @Override
245  public ImmutableBiMap<V, K> inverse() {
246    ImmutableBiMap<V, K> result = inverse;
247    return (result == null) ? inverse = new Inverse() : result;
248  }
249
250  private final class Inverse extends ImmutableBiMap<V, K> {
251
252    @Override
253    public int size() {
254      return inverse().size();
255    }
256
257    @Override
258    public ImmutableBiMap<K, V> inverse() {
259      return RegularImmutableBiMap.this;
260    }
261
262    @Override
263    public K get(@Nullable Object value) {
264      if (value == null) {
265        return null;
266      }
267      int bucket = Hashing.smear(value.hashCode()) & mask;
268      for (ImmutableMapEntry<K, V> entry = valueTable[bucket]; entry != null;
269           entry = entry.getNextInValueBucket()) {
270        if (value.equals(entry.getValue())) {
271          return entry.getKey();
272        }
273      }
274      return null;
275    }
276
277    @Override
278    ImmutableSet<Entry<V, K>> createEntrySet() {
279      return new InverseEntrySet();
280    }
281
282    final class InverseEntrySet extends ImmutableMapEntrySet<V, K> {
283      @Override
284      ImmutableMap<V, K> map() {
285        return Inverse.this;
286      }
287
288      @Override
289      boolean isHashCodeFast() {
290        return true;
291      }
292
293      @Override
294      public int hashCode() {
295        return hashCode;
296      }
297
298      @Override
299      public UnmodifiableIterator<Entry<V, K>> iterator() {
300        return asList().iterator();
301      }
302
303      @Override
304      ImmutableList<Entry<V, K>> createAsList() {
305        return new ImmutableAsList<Entry<V, K>>() {
306          @Override
307          public Entry<V, K> get(int index) {
308            Entry<K, V> entry = entries[index];
309            return Maps.immutableEntry(entry.getValue(), entry.getKey());
310          }
311
312          @Override
313          ImmutableCollection<Entry<V, K>> delegateCollection() {
314            return InverseEntrySet.this;
315          }
316        };
317      }
318    }
319
320    @Override
321    boolean isPartialView() {
322      return false;
323    }
324
325    @Override
326    Object writeReplace() {
327      return new InverseSerializedForm<K, V>(RegularImmutableBiMap.this);
328    }
329  }
330
331  private static class InverseSerializedForm<K, V> implements Serializable {
332    private final ImmutableBiMap<K, V> forward;
333
334    InverseSerializedForm(ImmutableBiMap<K, V> forward) {
335      this.forward = forward;
336    }
337
338    Object readResolve() {
339      return forward.inverse();
340    }
341
342    private static final long serialVersionUID = 1;
343  }
344}
345