/*

 * 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();

}

    private transient Map<K, V> delegate;

    transient AbstractBiMap<V, K> inverse;

/*

 * 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;

}