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 27 import java.io.IOException; 28 import java.io.ObjectInputStream; 29 import java.io.ObjectOutputStream; 30 import java.io.Serializable; 31 import java.util.Collection; 32 import java.util.Iterator; 33 import java.util.Map; 34 import java.util.Set; 35 36 import 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) 49 abstract 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