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