Guava BiMap AbstractBiMap
46165 ワード
BiMap
BiMapは構造であり、このMapのkeyとvalueが一意であることを表すMap構造を定義し、相互に関連する逆ビューを生成することができ、逆ビューのデータは本体BiMapの変更に伴って変更される
AbstractBiMap
AbstractBiMapはBiMapインタフェースを実現し、BiMapの方法を一度実現した.その中で最も主要な原理はforwardとbackwardを用いて2つのkvが互いに変調したMapを表してAbstractBiMapを構築し,その後AbstractBiMap内部で
delegateは正のMapを表し、inverseは逆のMapを表し、彼らの関係は互いに死の循環のようで、コード分析は以下の通りである.
BiMapは構造であり、このMapのkeyとvalueが一意であることを表すMap構造を定義し、相互に関連する逆ビューを生成することができ、逆ビューのデータは本体BiMapの変更に伴って変更される
/*
* Copyright (C) 2007 The Guava Authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.collect;
import com.google.common.annotations.GwtCompatible;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
/**
* A bimap (or "bidirectional map") is a map that preserves the uniqueness of
* its values as well as that of its keys. This constraint enables bimaps to
* support an "inverse view", which is another bimap containing the same entries
* as this bimap but with reversed keys and values.
*
* bimap ( "bidirectional map") map values keys .
* bimap , bimap entry, entry value key
*
* <p>See the Guava User Guide article on <a href=
* "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#BiMap">
* {@code BiMap}</a>.
*
* @author Kevin Bourrillion
* @since 2.0 (imported from Google Collections Library)
*/
@GwtCompatible
public interface BiMap<K, V> extends Map<K, V> {
// Modification Operations
/**
* {@inheritDoc}
*
* @throws IllegalArgumentException if the given value is already bound to a
* different key in this bimap. The bimap will remain unmodified in this
* event. To avoid this exception, call {@link #forcePut} instead.
*
* value key IllegalArgumentException.
* bimap forcePut exception
*/
@Override
V put(@Nullable K key, @Nullable V value);
/**
* An alternate form of {@code put} that silently removes any existing entry
* with the value {@code value} before proceeding with the {@link #put}
* operation. If the bimap previously contained the provided key-value
* mapping, this method has no effect.
*
* put , put value entry. bimap
* key-value , .
*
* <p>Note that a successful call to this method could cause the size of the
* bimap to increase by one, stay the same, or even decrease by one.
*
* bimap size +1, , -1 ( bimap (k1, v1)
* (k2, v2)) forcePut(k1, v2), (k1, v1) (k2, v2)
*
* <p><b>Warning:</b> If an existing entry with this value is removed, the key
* for that entry is discarded and not returned.
*
* : value entry , entry key
*
* @param key the key with which the specified value is to be associated
* @param value the value to be associated with the specified key
* @return the value which was previously associated with the key, which may
* be {@code null}, or {@code null} if there was no previous entry
*
* key value, key entry null
*/
V forcePut(@Nullable K key, @Nullable V value);
// Bulk Operations
//
/**
* {@inheritDoc}
*
* <p><b>Warning:</b> the results of calling this method may vary depending on
* the iteration order of {@code map}.
*
* : map
*
* @throws IllegalArgumentException if an attempt to {@code put} any
* entry fails. Note that some map entries may have been added to the
* bimap before the exception was thrown.
* put IllegalArgumentException. map entry
* bimap
*/
@Override
void putAll(Map<? extends K, ? extends V> map);
// Views
/**
* {@inheritDoc}
*
* <p>Because a bimap has unique values, this method returns a {@link Set},
* instead of the {@link java.util.Collection} specified in the {@link Map}
* interface.
*
* bimap value , set map collection
*/
@Override
Set<V> values();
/**
* Returns the inverse view of this bimap, which maps each of this bimap's
* values to its associated key. The two bimaps are backed by the same data;
* any changes to one will appear in the other.
*
* bimap -- bimap value key map, bimaps
* .
*
* <p><b>Note:</b>There is no guaranteed correspondence between the iteration
* order of a bimap and that of its inverse.
*
* : bimap
*
* @return the inverse view of this bimap
* bimap
*/
BiMap<V, K> inverse();
}AbstractBiMap
AbstractBiMapはBiMapインタフェースを実現し、BiMapの方法を一度実現した.その中で最も主要な原理はforwardとbackwardを用いて2つのkvが互いに変調したMapを表してAbstractBiMapを構築し,その後AbstractBiMap内部で
private transient Map<K, V> delegate;
transient AbstractBiMap<V, K> inverse;delegateは正のMapを表し、inverseは逆のMapを表し、彼らの関係は互いに死の循環のようで、コード分析は以下の通りである.
/*
* Copyright (C) 2007 The Guava Authors
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package com.google.common.collect;
import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkState;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.base.Objects;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import javax.annotation.Nullable;
/**
* A general-purpose bimap implementation using any two backing {@code Map}
* instances.
*
* Map bimap
*
* <p>Note that this class contains {@code equals()} calls that keep it from
* supporting {@code IdentityHashMap} backing maps.
*
* @author Kevin Bourrillion
* @author Mike Bostock
*/
@GwtCompatible(emulated = true)
abstract class AbstractBiMap<K, V> extends ForwardingMap<K, V>
implements BiMap<K, V>, Serializable {
private transient Map<K, V> delegate;
transient AbstractBiMap<V, K> inverse;
/** Package-private constructor for creating a map-backed bimap. */
/** map-backed bimap */
AbstractBiMap(Map<K, V> forward, Map<V, K> backward) {
setDelegates(forward, backward);
}
/** Private constructor for inverse bimap. */
/** bimap */
private AbstractBiMap(Map<K, V> backward, AbstractBiMap<V, K> forward) {
delegate = backward;
inverse = forward;
}
@Override protected Map<K, V> delegate() {
return delegate;
}
/**
* Returns its input, or throws an exception if this is not a valid key.
* , key
*/
K checkKey(@Nullable K key) {
return key;
}
/**
* Returns its input, or throws an exception if this is not a valid value.
* , value
*/
V checkValue(@Nullable V value) {
return value;
}
/**
* Specifies the delegate maps going in each direction. Called by the
* constructor and by subclasses during deserialization.
*
* map.
*/
void setDelegates(Map<K, V> forward, Map<V, K> backward) {
checkState(delegate == null);
checkState(inverse == null);
checkArgument(forward.isEmpty());
checkArgument(backward.isEmpty());
checkArgument(forward != backward);
delegate = forward;
inverse = new Inverse<V, K>(backward, this);
}
void setInverse(AbstractBiMap<V, K> inverse) {
this.inverse = inverse;
}
// Query Operations (optimizations)
// ( )
@Override public boolean containsValue(Object value) {
return inverse.containsKey(value);
}
// Modification Operations
//
@Override public V put(K key, V value) {
return putInBothMaps(key, value, false);
}
@Override
public V forcePut(K key, V value) {
return putInBothMaps(key, value, true);
}
/**
* delegate inverse key value
*
* @param key
* @param value
* @param force
* @return
*/
private V putInBothMaps(@Nullable K key, @Nullable V value, boolean force) {
checkKey(key);
checkValue(value);
boolean containedKey = containsKey(key);
// entry , value
if (containedKey && Objects.equal(value, get(key))) {
return value;
}
if (force) {
// put key & value
inverse().remove(value);
} else {
// value ,
checkArgument(!containsValue(value), "value already present: %s", value);
}
V oldValue = delegate.put(key, value);
//
updateInverseMap(key, containedKey, oldValue, value);
return oldValue;
}
/**
*
*/
private void updateInverseMap(
K key, boolean containedKey, V oldValue, V newValue) {
// key ( inverse value ), entry
if (containedKey) {
removeFromInverseMap(oldValue);
}
inverse.delegate.put(newValue, key);
}
@Override public V remove(Object key) {
return containsKey(key) ? removeFromBothMaps(key) : null;
}
private V removeFromBothMaps(Object key) {
V oldValue = delegate.remove(key);
removeFromInverseMap(oldValue);
return oldValue;
}
private void removeFromInverseMap(V oldValue) {
inverse.delegate.remove(oldValue);
}
// Bulk Operations
//
@Override public void putAll(Map<? extends K, ? extends V> map) {
for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
put(entry.getKey(), entry.getValue());
}
}
@Override public void clear() {
delegate.clear();
inverse.delegate.clear();
}
// Views
//
@Override
public BiMap<V, K> inverse() {
return inverse;
}
private transient Set<K> keySet;
@Override public Set<K> keySet() {
Set<K> result = keySet;
return (result == null) ? keySet = new KeySet() : result;
}
private class KeySet extends ForwardingSet<K> {
@Override protected Set<K> delegate() {
return delegate.keySet();
}
@Override public void clear() {
AbstractBiMap.this.clear();
}
@Override public boolean remove(Object key) {
if (!contains(key)) {
return false;
}
removeFromBothMaps(key);
return true;
}
@Override public boolean removeAll(Collection<?> keysToRemove) {
return standardRemoveAll(keysToRemove);
}
@Override public boolean retainAll(Collection<?> keysToRetain) {
return standardRetainAll(keysToRetain);
}
@Override public Iterator<K> iterator() {
return Maps.keyIterator(entrySet().iterator());
}
}
private transient Set<V> valueSet;
@Override public Set<V> values() {
/*
* We can almost reuse the inverse's keySet, except we have to fix the
* iteration order so that it is consistent with the forward map.
*
* inverse keyset forward valueset, ,
* forward map
*/
Set<V> result = valueSet;
return (result == null) ? valueSet = new ValueSet() : result;
}
private class ValueSet extends ForwardingSet<V> {
/** inverse keySet valueSet */
final Set<V> valuesDelegate = inverse.keySet();
@Override protected Set<V> delegate() {
return valuesDelegate;
}
@Override public Iterator<V> iterator() {
return Maps.valueIterator(entrySet().iterator());
}
@Override public Object[] toArray() {
return standardToArray();
}
@Override public <T> T[] toArray(T[] array) {
return standardToArray(array);
}
@Override public String toString() {
return standardToString();
}
}
private transient Set<Entry<K, V>> entrySet;
@Override public Set<Entry<K, V>> entrySet() {
Set<Entry<K, V>> result = entrySet;
return (result == null) ? entrySet = new EntrySet() : result;
}
private class EntrySet extends ForwardingSet<Entry<K, V>> {
final Set<Entry<K, V>> esDelegate = delegate.entrySet();
@Override protected Set<Entry<K, V>> delegate() {
return esDelegate;
}
@Override public void clear() {
AbstractBiMap.this.clear();
}
@Override public boolean remove(Object object) {
if (!esDelegate.contains(object)) {
return false;
}
// safe because esDelgate.contains(object).
Entry<?, ?> entry = (Entry<?, ?>) object;
inverse.delegate.remove(entry.getValue());
/*
* Remove the mapping in inverse before removing from esDelegate because
* if entry is part of esDelegate, entry might be invalidated after the
* mapping is removed from esDelegate.
*
* forward entry inverse entry , entry forward ,
* entry forward
*/
esDelegate.remove(entry);
return true;
}
@Override public Iterator<Entry<K, V>> iterator() {
final Iterator<Entry<K, V>> iterator = esDelegate.iterator();
return new Iterator<Entry<K, V>>() {
Entry<K, V> entry;
@Override public boolean hasNext() {
return iterator.hasNext();
}
@Override public Entry<K, V> next() {
entry = iterator.next();
final Entry<K, V> finalEntry = entry;
return new ForwardingMapEntry<K, V>() {
@Override protected Entry<K, V> delegate() {
return finalEntry;
}
@Override public V setValue(V value) {
// Preconditions keep the map and inverse consistent.
checkState(contains(this), "entry no longer in map");
// similar to putInBothMaps, but set via entry
if (Objects.equal(value, getValue())) {
return value;
}
checkArgument(!containsValue(value),
"value already present: %s", value);
V oldValue = finalEntry.setValue(value);
checkState(Objects.equal(value, get(getKey())),
"entry no longer in map");
updateInverseMap(getKey(), true, oldValue, value);
return oldValue;
}
};
}
@Override public void remove() {
checkState(entry != null);
V value = entry.getValue();
iterator.remove();
removeFromInverseMap(value);
}
};
}
// See java.util.Collections.CheckedEntrySet for details on attacks.
@Override public Object[] toArray() {
return standardToArray();
}
@Override public <T> T[] toArray(T[] array) {
return standardToArray(array);
}
@Override public boolean contains(Object o) {
return Maps.containsEntryImpl(delegate(), o);
}
@Override public boolean containsAll(Collection<?> c) {
return standardContainsAll(c);
}
@Override public boolean removeAll(Collection<?> c) {
return standardRemoveAll(c);
}
@Override public boolean retainAll(Collection<?> c) {
return standardRetainAll(c);
}
}
/** The inverse of any other {@code AbstractBiMap} subclass. */
/** inverse , , AbstractBiMap forward inverse */
private static class Inverse<K, V> extends AbstractBiMap<K, V> {
private Inverse(Map<K, V> backward, AbstractBiMap<V, K> forward) {
super(backward, forward);
}
/*
* Serialization stores the forward bimap, the inverse of this inverse.
* Deserialization calls inverse() on the forward bimap and returns that
* inverse.
*
* forward bimap, inverse .
* forward inverse() inverse
*
* If a bimap and its inverse are serialized together, the deserialized
* instances have inverse() methods that return the other.
*/
@Override
K checkKey(K key) {
return inverse.checkValue(key);
}
@Override
V checkValue(V value) {
return inverse.checkKey(value);
}
/**
* @serialData the forward bimap
*
* delegate inverse transient
* inverse()
*/
@GwtIncompatible("java.io.ObjectOuputStream")
private void writeObject(ObjectOutputStream stream) throws IOException {
stream.defaultWriteObject();
stream.writeObject(inverse());
}
/**
* inverse
*/
@GwtIncompatible("java.io.ObjectInputStream")
@SuppressWarnings("unchecked") // reading data stored by writeObject
private void readObject(ObjectInputStream stream)
throws IOException, ClassNotFoundException {
stream.defaultReadObject();
setInverse((AbstractBiMap<V, K>) stream.readObject());
}
/**
* inverse().inverse(), forward .
*/
@GwtIncompatible("Not needed in the emulated source.")
Object readResolve() {
return inverse().inverse();
}
@GwtIncompatible("Not needed in emulated source.")
private static final long serialVersionUID = 0;
}
@GwtIncompatible("Not needed in emulated source.")
private static final long serialVersionUID = 0;
}