1 /*
2 * Copyright (C) 2007 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
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkState;
21 import static com.google.common.collect.CollectPreconditions.checkRemove;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.base.Objects;
26 import com.google.errorprone.annotations.CanIgnoreReturnValue;
27 import com.google.j2objc.annotations.RetainedWith;
28 import com.google.j2objc.annotations.WeakOuter;
29 import java.io.IOException;
30 import java.io.ObjectInputStream;
31 import java.io.ObjectOutputStream;
32 import java.io.Serializable;
33 import java.util.Collection;
34 import java.util.Iterator;
35 import java.util.Map;
36 import java.util.Set;
37 import java.util.function.BiFunction;
38 import org.checkerframework.checker.nullness.qual.Nullable;
39
40 /**
41 * A general-purpose bimap implementation using any two backing {@code Map} instances.
42 *
43 * <p>Note that this class contains {@code equals()} calls that keep it from supporting {@code
44 * IdentityHashMap} backing maps.
45 *
46 * @author Kevin Bourrillion
47 * @author Mike Bostock
48 */
49 @GwtCompatible(emulated = true)
50 abstract class AbstractBiMap<K, V> extends ForwardingMap<K, V>
51 implements BiMap<K, V>, Serializable {
52
53 private transient @Nullable Map<K, V> delegate;
54 @RetainedWith transient @Nullable AbstractBiMap<V, K> inverse;
55
56 /** Package-private constructor for creating a map-backed bimap. */
57 AbstractBiMap(Map<K, V> forward, Map<V, K> backward) {
58 setDelegates(forward, backward);
59 }
60
61 /** Private constructor for inverse bimap. */
62 private AbstractBiMap(Map<K, V> backward, AbstractBiMap<V, K> forward) {
63 delegate = backward;
64 inverse = forward;
65 }
66
67 @Override
68 protected Map<K, V> delegate() {
69 return delegate;
70 }
71
72 /** Returns its input, or throws an exception if this is not a valid key. */
73 @CanIgnoreReturnValue
74 K checkKey(@Nullable K key) {
75 return key;
76 }
77
78 /** Returns its input, or throws an exception if this is not a valid value. */
79 @CanIgnoreReturnValue
80 V checkValue(@Nullable V value) {
81 return value;
82 }
83
84 /**
85 * Specifies the delegate maps going in each direction. Called by the constructor and by
86 * subclasses during deserialization.
87 */
88 void setDelegates(Map<K, V> forward, Map<V, K> backward) {
89 checkState(delegate == null);
90 checkState(inverse == null);
91 checkArgument(forward.isEmpty());
92 checkArgument(backward.isEmpty());
93 checkArgument(forward != backward);
94 delegate = forward;
95 inverse = makeInverse(backward);
96 }
97
98 AbstractBiMap<V, K> makeInverse(Map<V, K> backward) {
99 return new Inverse<>(backward, this);
100 }
101
102 void setInverse(AbstractBiMap<V, K> inverse) {
103 this.inverse = inverse;
104 }
105
106 // Query Operations (optimizations)
107
108 @Override
109 public boolean containsValue(@Nullable Object value) {
110 return inverse.containsKey(value);
111 }
112
113 // Modification Operations
114
115 @CanIgnoreReturnValue
116 @Override
117 public V put(@Nullable K key, @Nullable V value) {
118 return putInBothMaps(key, value, false);
119 }
120
121 @CanIgnoreReturnValue
122 @Override
123 public V forcePut(@Nullable K key, @Nullable V value) {
124 return putInBothMaps(key, value, true);
125 }
126
127 private V putInBothMaps(@Nullable K key, @Nullable V value, boolean force) {
128 checkKey(key);
129 checkValue(value);
130 boolean containedKey = containsKey(key);
131 if (containedKey && Objects.equal(value, get(key))) {
132 return value;
133 }
134 if (force) {
135 inverse().remove(value);
136 } else {
137 checkArgument(!containsValue(value), "value already present: %s", value);
138 }
139 V oldValue = delegate.put(key, value);
140 updateInverseMap(key, containedKey, oldValue, value);
141 return oldValue;
142 }
143
144 private void updateInverseMap(K key, boolean containedKey, V oldValue, V newValue) {
145 if (containedKey) {
146 removeFromInverseMap(oldValue);
147 }
148 inverse.delegate.put(newValue, key);
149 }
150
151 @CanIgnoreReturnValue
152 @Override
153 public V remove(@Nullable Object key) {
154 return containsKey(key) ? removeFromBothMaps(key) : null;
155 }
156
157 @CanIgnoreReturnValue
158 private V removeFromBothMaps(Object key) {
159 V oldValue = delegate.remove(key);
160 removeFromInverseMap(oldValue);
161 return oldValue;
162 }
163
164 private void removeFromInverseMap(V oldValue) {
165 inverse.delegate.remove(oldValue);
166 }
167
168 // Bulk Operations
169
170 @Override
171 public void putAll(Map<? extends K, ? extends V> map) {
172 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
173 put(entry.getKey(), entry.getValue());
174 }
175 }
176
177 @Override
178 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
179 this.delegate.replaceAll(function);
180 inverse.delegate.clear();
181 Entry<K, V> broken = null;
182 Iterator<Entry<K, V>> itr = this.delegate.entrySet().iterator();
183 while (itr.hasNext()) {
184 Entry<K, V> entry = itr.next();
185 K k = entry.getKey();
186 V v = entry.getValue();
187 K conflict = inverse.delegate.putIfAbsent(v, k);
188 if (conflict != null) {
189 broken = entry;
190 // We're definitely going to throw, but we'll try to keep the BiMap in an internally
191 // consistent state by removing the bad entry.
192 itr.remove();
193 }
194 }
195 if (broken != null) {
196 throw new IllegalArgumentException("value already present: " + broken.getValue());
197 }
198 }
199
200 @Override
201 public void clear() {
202 delegate.clear();
203 inverse.delegate.clear();
204 }
205
206 // Views
207
208 @Override
209 public BiMap<V, K> inverse() {
210 return inverse;
211 }
212
213 private transient @Nullable Set<K> keySet;
214
215 @Override
216 public Set<K> keySet() {
217 Set<K> result = keySet;
218 return (result == null) ? keySet = new KeySet() : result;
219 }
220
221 @WeakOuter
222 private class KeySet extends ForwardingSet<K> {
223 @Override
224 protected Set<K> delegate() {
225 return delegate.keySet();
226 }
227
228 @Override
229 public void clear() {
230 AbstractBiMap.this.clear();
231 }
232
233 @Override
234 public boolean remove(Object key) {
235 if (!contains(key)) {
236 return false;
237 }
238 removeFromBothMaps(key);
239 return true;
240 }
241
242 @Override
243 public boolean removeAll(Collection<?> keysToRemove) {
244 return standardRemoveAll(keysToRemove);
245 }
246
247 @Override
248 public boolean retainAll(Collection<?> keysToRetain) {
249 return standardRetainAll(keysToRetain);
250 }
251
252 @Override
253 public Iterator<K> iterator() {
254 return Maps.keyIterator(entrySet().iterator());
255 }
256 }
257
258 private transient @Nullable Set<V> valueSet;
259
260 @Override
261 public Set<V> values() {
262 /*
263 * We can almost reuse the inverse's keySet, except we have to fix the
264 * iteration order so that it is consistent with the forward map.
265 */
266 Set<V> result = valueSet;
267 return (result == null) ? valueSet = new ValueSet() : result;
268 }
269
270 @WeakOuter
271 private class ValueSet extends ForwardingSet<V> {
272 final Set<V> valuesDelegate = inverse.keySet();
273
274 @Override
275 protected Set<V> delegate() {
276 return valuesDelegate;
277 }
278
279 @Override
280 public Iterator<V> iterator() {
281 return Maps.valueIterator(entrySet().iterator());
282 }
283
284 @Override
285 public Object[] toArray() {
286 return standardToArray();
287 }
288
289 @Override
290 public <T> T[] toArray(T[] array) {
291 return standardToArray(array);
292 }
293
294 @Override
295 public String toString() {
296 return standardToString();
297 }
298 }
299
300 private transient @Nullable Set<Entry<K, V>> entrySet;
301
302 @Override
303 public Set<Entry<K, V>> entrySet() {
304 Set<Entry<K, V>> result = entrySet;
305 return (result == null) ? entrySet = new EntrySet() : result;
306 }
307
308 class BiMapEntry extends ForwardingMapEntry<K, V> {
309 private final Entry<K, V> delegate;
310
311 BiMapEntry(Entry<K, V> delegate) {
312 this.delegate = delegate;
313 }
314
315 @Override
316 protected Entry<K, V> delegate() {
317 return delegate;
318 }
319
320 @Override
321 public V setValue(V value) {
322 checkValue(value);
323 // Preconditions keep the map and inverse consistent.
324 checkState(entrySet().contains(this), "entry no longer in map");
325 // similar to putInBothMaps, but set via entry
326 if (Objects.equal(value, getValue())) {
327 return value;
328 }
329 checkArgument(!containsValue(value), "value already present: %s", value);
330 V oldValue = delegate.setValue(value);
331 checkState(Objects.equal(value, get(getKey())), "entry no longer in map");
332 updateInverseMap(getKey(), true, oldValue, value);
333 return oldValue;
334 }
335 }
336
337 Iterator<Entry<K, V>> entrySetIterator() {
338 final Iterator<Entry<K, V>> iterator = delegate.entrySet().iterator();
339 return new Iterator<Entry<K, V>>() {
340 @Nullable Entry<K, V> entry;
341
342 @Override
343 public boolean hasNext() {
344 return iterator.hasNext();
345 }
346
347 @Override
348 public Entry<K, V> next() {
349 entry = iterator.next();
350 return new BiMapEntry(entry);
351 }
352
353 @Override
354 public void remove() {
355 checkRemove(entry != null);
356 V value = entry.getValue();
357 iterator.remove();
358 removeFromInverseMap(value);
359 entry = null;
360 }
361 };
362 }
363
364 @WeakOuter
365 private class EntrySet extends ForwardingSet<Entry<K, V>> {
366 final Set<Entry<K, V>> esDelegate = delegate.entrySet();
367
368 @Override
369 protected Set<Entry<K, V>> delegate() {
370 return esDelegate;
371 }
372
373 @Override
374 public void clear() {
375 AbstractBiMap.this.clear();
376 }
377
378 @Override
379 public boolean remove(Object object) {
380 if (!esDelegate.contains(object)) {
381 return false;
382 }
383
384 // safe because esDelegate.contains(object).
385 Entry<?, ?> entry = (Entry<?, ?>) object;
386 inverse.delegate.remove(entry.getValue());
387 /*
388 * Remove the mapping in inverse before removing from esDelegate because
389 * if entry is part of esDelegate, entry might be invalidated after the
390 * mapping is removed from esDelegate.
391 */
392 esDelegate.remove(entry);
393 return true;
394 }
395
396 @Override
397 public Iterator<Entry<K, V>> iterator() {
398 return entrySetIterator();
399 }
400
401 // See java.util.Collections.CheckedEntrySet for details on attacks.
402
403 @Override
404 public Object[] toArray() {
405 return standardToArray();
406 }
407
408 @Override
409 public <T> T[] toArray(T[] array) {
410 return standardToArray(array);
411 }
412
413 @Override
414 public boolean contains(Object o) {
415 return Maps.containsEntryImpl(delegate(), o);
416 }
417
418 @Override
419 public boolean containsAll(Collection<?> c) {
420 return standardContainsAll(c);
421 }
422
423 @Override
424 public boolean removeAll(Collection<?> c) {
425 return standardRemoveAll(c);
426 }
427
428 @Override
429 public boolean retainAll(Collection<?> c) {
430 return standardRetainAll(c);
431 }
432 }
433
434 /** The inverse of any other {@code AbstractBiMap} subclass. */
435 static class Inverse<K, V> extends AbstractBiMap<K, V> {
436 Inverse(Map<K, V> backward, AbstractBiMap<V, K> forward) {
437 super(backward, forward);
438 }
439
440 /*
441 * Serialization stores the forward bimap, the inverse of this inverse.
442 * Deserialization calls inverse() on the forward bimap and returns that
443 * inverse.
444 *
445 * If a bimap and its inverse are serialized together, the deserialized
446 * instances have inverse() methods that return the other.
447 */
448
449 @Override
450 K checkKey(K key) {
451 return inverse.checkValue(key);
452 }
453
454 @Override
455 V checkValue(V value) {
456 return inverse.checkKey(value);
457 }
458
459 /** @serialData the forward bimap */
460 @GwtIncompatible // java.io.ObjectOutputStream
461 private void writeObject(ObjectOutputStream stream) throws IOException {
462 stream.defaultWriteObject();
463 stream.writeObject(inverse());
464 }
465
466 @GwtIncompatible // java.io.ObjectInputStream
467 @SuppressWarnings("unchecked") // reading data stored by writeObject
468 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
469 stream.defaultReadObject();
470 setInverse((AbstractBiMap<V, K>) stream.readObject());
471 }
472
473 @GwtIncompatible // Not needed in the emulated source.
474 Object readResolve() {
475 return inverse().inverse();
476 }
477
478 @GwtIncompatible // Not needed in emulated source.
479 private static final long serialVersionUID = 0;
480 }
481
482 @GwtIncompatible // Not needed in emulated source.
483 private static final long serialVersionUID = 0;
484 }