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