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