src/com/google/common/collect/LinkedHashMultimap.java

/*
 * Copyright (C) 2007 Google Inc.
 *
 * 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 com.google.common.annotations.VisibleForTesting;
import com.google.common.base.Preconditions;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

import javax.annotation.Nullable;

/**
 * Implementation of {@code Multimap} that does not allow duplicate key-value
 * entries and that returns collections whose iterators follow the ordering in
 * which the data was added to the multimap.
 *
 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
 * asMap} iterate through the keys in the order they were first added to the
 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
 * replaceValues} return collections that iterate through the values in the
 * order they were added. The collections generated by {@code entries} and
 * {@code values} iterate across the key-value mappings in the order they were
 * added to the multimap.
 *
 * <p>The iteration ordering of the collections generated by {@code keySet},
 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
 * keys remains unchanged, adding or removing mappings does not affect the key
 * iteration order. However, if you remove all values associated with a key and
 * then add the key back to the multimap, that key will come last in the key
 * iteration order.
 *
 * <p>The multimap does not store duplicate key-value pairs. Adding a new
 * key-value pair equal to an existing key-value pair has no effect.
 *
 * <p>Keys and values may be null. All optional multimap methods are supported,
 * and all returned views are modifiable.
 *
 * <p>This class is not threadsafe when any concurrent operations update the
 * multimap. Concurrent read operations will work correctly. To allow concurrent
 * update operations, wrap your multimap with a call to {@link
 * Multimaps#synchronizedSetMultimap}.
 *
 * @author Jared Levy
 */
@GwtCompatible(serializable = true)
public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
  private static final int DEFAULT_VALUES_PER_KEY = 8;

  @VisibleForTesting
  transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;

  /**
   * Map entries with an iteration order corresponding to the order in which the
   * key-value pairs were added to the multimap.
   */
  // package-private for GWT deserialization
  transient Collection<Map.Entry<K, V>> linkedEntries;

  /**
   * Creates a new, empty {@code LinkedHashMultimap} with the default initial
   * capacities.
   */
  public static <K, V> LinkedHashMultimap<K, V> create() {
    return new LinkedHashMultimap<K, V>();
  }

  /**
   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold
   * the specified numbers of keys and values without rehashing.
   *
   * @param expectedKeys the expected number of distinct keys
   * @param expectedValuesPerKey the expected average number of values per key
   * @throws IllegalArgumentException if {@code expectedKeys} or {@code
   *      expectedValuesPerKey} is negative
   */
  public static <K, V> LinkedHashMultimap<K, V> create(
      int expectedKeys, int expectedValuesPerKey) {
    return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey);
  }

  /**
   * Constructs a {@code LinkedHashMultimap} with the same mappings as the
   * specified multimap. If a key-value mapping appears multiple times in the
   * input multimap, it only appears once in the constructed multimap. The new
   * multimap has the same {@link Multimap#entries()} iteration order as the
   * input multimap, except for excluding duplicate mappings.
   *
   * @param multimap the multimap whose contents are copied to this multimap
   */
  public static <K, V> LinkedHashMultimap<K, V> create(
      Multimap<? extends K, ? extends V> multimap) {
    return new LinkedHashMultimap<K, V>(multimap);
  }

  private LinkedHashMultimap() {
    super(new LinkedHashMap<K, Collection<V>>());
    linkedEntries = Sets.newLinkedHashSet();
  }

  private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) {
    super(new LinkedHashMap<K, Collection<V>>(expectedKeys));
    Preconditions.checkArgument(expectedValuesPerKey >= 0);
    this.expectedValuesPerKey = expectedValuesPerKey;
    linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
        expectedKeys * expectedValuesPerKey);
  }

  private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) {
    super(new LinkedHashMap<K, Collection<V>>(
        Maps.capacity(multimap.keySet().size())));
    linkedEntries
        = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size()));
    putAll(multimap);
  }

  /**
   * {@inheritDoc}
   *
   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
   * one key.
   *
   * @return a new {@code LinkedHashSet} containing a collection of values for
   *     one key
   */
  @Override Set<V> createCollection() {
    return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey));
  }

  /**
   * {@inheritDoc}
   *
   * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the
   * order in which key-value pairs are added to the multimap.
   *
   * @param key key to associate with values in the collection
   * @return a new decorated {@code LinkedHashSet} containing a collection of
   *     values for one key
   */
  @Override Collection<V> createCollection(@Nullable K key) {
    return new SetDecorator(key, createCollection());
  }

  private class SetDecorator extends ForwardingSet<V> {
    final Set<V> delegate;
    final K key;

    SetDecorator(@Nullable K key, Set<V> delegate) {
      this.delegate = delegate;
      this.key = key;
    }

    @Override protected Set<V> delegate() {
      return delegate;
    }

    <E> Map.Entry<K, E> createEntry(@Nullable E value) {
      return Maps.immutableEntry(key, value);
    }

    <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) {
      // converts a collection of values into a list of key/value map entries
      Collection<Map.Entry<K, E>> entries
          = Lists.newArrayListWithExpectedSize(values.size());
      for (E value : values) {
        entries.add(createEntry(value));
      }
      return entries;
    }

    @Override public boolean add(@Nullable V value) {
      boolean changed = delegate.add(value);
      if (changed) {
        linkedEntries.add(createEntry(value));
      }
      return changed;
    }

    @Override public boolean addAll(Collection<? extends V> values) {
      boolean changed = delegate.addAll(values);
      if (changed) {
        linkedEntries.addAll(createEntries(delegate()));
      }
      return changed;
    }

    @Override public void clear() {
      linkedEntries.removeAll(createEntries(delegate()));
      delegate.clear();
    }

    @Override public Iterator<V> iterator() {
      final Iterator<V> delegateIterator = delegate.iterator();
      return new Iterator<V>() {
        V value;

        public boolean hasNext() {
          return delegateIterator.hasNext();
        }
        public V next() {
          value = delegateIterator.next();
          return value;
        }
        public void remove() {
          delegateIterator.remove();
          linkedEntries.remove(createEntry(value));
        }
      };
    }

    @Override public boolean remove(@Nullable Object value) {
      boolean changed = delegate.remove(value);
      if (changed) {
        /*
         * linkedEntries.remove() will return false when this method is called
         * by entries().iterator().remove()
         */
        linkedEntries.remove(createEntry(value));
      }
      return changed;
    }

    @Override public boolean removeAll(Collection<?> values) {
      boolean changed = delegate.removeAll(values);
      if (changed) {
        linkedEntries.removeAll(createEntries(values));
      }
      return changed;
    }

    @Override public boolean retainAll(Collection<?> values) {
      /*
       * Calling linkedEntries.retainAll() would incorrectly remove values
       * with other keys.
       */
      boolean changed = false;
      Iterator<V> iterator = delegate.iterator();
      while (iterator.hasNext()) {
        V value = iterator.next();
        if (!values.contains(value)) {
          iterator.remove();
          linkedEntries.remove(Maps.immutableEntry(key, value));
          changed = true;
        }
      }
      return changed;
    }
  }

  /**
   * {@inheritDoc}
   *
   * <p>Generates an iterator across map entries that follows the ordering in
   * which the key-value pairs were added to the multimap.
   *
   * @return a key-value iterator with the correct ordering
   */
  @Override Iterator<Map.Entry<K, V>> createEntryIterator() {
    final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator();

    return new Iterator<Map.Entry<K, V>>() {
      Map.Entry<K, V> entry;

      public boolean hasNext() {
        return delegateIterator.hasNext();
      }

      public Map.Entry<K, V> next() {
        entry = delegateIterator.next();
        return entry;
      }

      public void remove() {
        // Remove from iterator first to keep iterator valid.
        delegateIterator.remove();
        LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue());
      }
    };
  }

  /**
   * {@inheritDoc}
   *
   * <p>If {@code values} is not empty and the multimap already contains a
   * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
   * However, the provided values always come last in the {@link #entries()} and
   * {@link #values()} iteration orderings.
   */
  @Override public Set<V> replaceValues(
      @Nullable K key, Iterable<? extends V> values) {
    return super.replaceValues(key, values);
  }

  /**
   * Returns a set of all key-value pairs. Changes to the returned set will
   * update the underlying multimap, and vice versa. The entries set does not
   * support the {@code add} or {@code addAll} operations.
   *
   * <p>The iterator generated by the returned set traverses the entries in the
   * order they were added to the multimap.
   *
   * <p>Each entry is an immutable snapshot of a key-value mapping in the
   * multimap, taken at the time the entry is returned by a method call to the
   * collection or its iterator.
   */
  @Override public Set<Map.Entry<K, V>> entries() {
    return super.entries();
  }

  /**
   * Returns a collection of all values in the multimap. Changes to the returned
   * collection will update the underlying multimap, and vice versa.
   *
   * <p>The iterator generated by the returned collection traverses the values
   * in the order they were added to the multimap.
   */
  @Override public Collection<V> values() {
    return super.values();
  }

  // Unfortunately, the entries() ordering does not determine the key ordering;
  // see the example in the LinkedListMultimap class Javadoc.

  /**
   * @serialData the number of distinct keys, and then for each distinct key:
   *     the first key, the number of values for that key, and the key's values,
   *     followed by successive keys and values from the entries() ordering
   */
  private void writeObject(ObjectOutputStream stream) throws IOException {
    stream.defaultWriteObject();
    stream.writeInt(expectedValuesPerKey);
    Serialization.writeMultimap(this, stream);
    for (Map.Entry<K, V> entry : linkedEntries) {
      stream.writeObject(entry.getKey());
      stream.writeObject(entry.getValue());
    }
  }

  private void readObject(ObjectInputStream stream)
      throws IOException, ClassNotFoundException {
    stream.defaultReadObject();
    expectedValuesPerKey = stream.readInt();
    int distinctKeys = Serialization.readCount(stream);
    setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys)));
    linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
        distinctKeys * expectedValuesPerKey);
    Serialization.populateMultimap(this, stream, distinctKeys);
    linkedEntries.clear(); // will clear and repopulate entries
    for (int i = 0; i < size(); i++) {
      @SuppressWarnings("unchecked") // reading data stored by writeObject
      K key = (K) stream.readObject();
      @SuppressWarnings("unchecked") // reading data stored by writeObject
      V value = (V) stream.readObject();
      linkedEntries.add(Maps.immutableEntry(key, value));
    }
  }

  private static final long serialVersionUID = 0;
}