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