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