common/collect/AbstractBiMap.java

/*
 * 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 static com.google.common.collect.CollectPreconditions.checkRemove;

import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Objects;

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.
 *
 * <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. */
  AbstractBiMap(Map<K, V> forward, Map<V, K> backward) {
    setDelegates(forward, backward);
  }

  /** Private constructor for inverse 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.
   */
  K checkKey(@Nullable K key) {
    return key;
  }

  /**
   * Returns its input, or throws an exception if this is not a valid 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.
   */
  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(@Nullable Object value) {
    return inverse.containsKey(value);
  }

  // Modification Operations

  @Override public V put(@Nullable K key, @Nullable V value) {
    return putInBothMaps(key, value, false);
  }

  @Override
  public V forcePut(@Nullable K key, @Nullable V value) {
    return putInBothMaps(key, value, true);
  }

  private V putInBothMaps(@Nullable K key, @Nullable V value, boolean force) {
    checkKey(key);
    checkValue(value);
    boolean containedKey = containsKey(key);
    if (containedKey && Objects.equal(value, get(key))) {
      return value;
    }
    if (force) {
      inverse().remove(value);
    } else {
      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) {
    if (containedKey) {
      removeFromInverseMap(oldValue);
    }
    inverse.delegate.put(newValue, key);
  }

  @Override public V remove(@Nullable 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.
     */
    Set<V> result = valueSet;
    return (result == null) ? valueSet = new ValueSet() : result;
  }

  private class ValueSet extends ForwardingSet<V> {
    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.
       */
      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() {
          checkRemove(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. */
  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.
     *
     * 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);
    }
  }
}