1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.VisibleForTesting; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Preconditions; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectOutputStream; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashMap; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashSet; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Implementation of {@code Multimap} that does not allow duplicate key-value 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * entries and that returns collections whose iterators follow the ordering in 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which the data was added to the multimap. 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The collections returned by {@code keySet}, {@code keys}, and {@code 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * asMap} iterate through the keys in the order they were first added to the 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Similarly, {@code get}, {@code removeAll}, and {@code 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * replaceValues} return collections that iterate through the values in the 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order they were added. The collections generated by {@code entries} and 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code values} iterate across the key-value mappings in the order they were 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * added to the multimap. 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration ordering of the collections generated by {@code keySet}, 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * keys remains unchanged, adding or removing mappings does not affect the key 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order. However, if you remove all values associated with a key and 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * then add the key back to the multimap, that key will come last in the key 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order. 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The multimap does not store duplicate key-value pairs. Adding a new 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value pair equal to an existing key-value pair has no effect. 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Keys and values may be null. All optional multimap methods are supported, 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and all returned views are modifiable. 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Concurrent read operations will work correctly. To allow concurrent 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update operations, wrap your multimap with a call to {@link 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedSetMultimap}. 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> { 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final int DEFAULT_VALUES_PER_KEY = 8; 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @VisibleForTesting 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Map entries with an iteration order corresponding to the order in which the 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value pairs were added to the multimap. 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // package-private for GWT deserialization 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson transient Collection<Map.Entry<K, V>> linkedEntries; 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new, empty {@code LinkedHashMultimap} with the default initial 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * capacities. 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create() { 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(); 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified numbers of keys and values without rehashing. 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedKeys the expected number of distinct keys 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedValuesPerKey the expected average number of values per key 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedKeys} or {@code 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * expectedValuesPerKey} is negative 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create( 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int expectedKeys, int expectedValuesPerKey) { 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey); 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a {@code LinkedHashMultimap} with the same mappings as the 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified multimap. If a key-value mapping appears multiple times in the 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * input multimap, it only appears once in the constructed multimap. The new 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap has the same {@link Multimap#entries()} iteration order as the 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * input multimap, except for excluding duplicate mappings. 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param multimap the multimap whose contents are copied to this multimap 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create( 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<? extends K, ? extends V> multimap) { 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(multimap); 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap() { 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>()); 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries = Sets.newLinkedHashSet(); 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) { 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>(expectedKeys)); 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkArgument(expectedValuesPerKey >= 0); 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.expectedValuesPerKey = expectedValuesPerKey; 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries = new LinkedHashSet<Map.Entry<K, V>>( 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert (int) Math.min(Ints.MAX_POWER_OF_TWO, 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ((long) expectedKeys) * expectedValuesPerKey)); 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) { 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>( 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Maps.capacity(multimap.keySet().size()))); 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size())); 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson putAll(multimap); 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Creates an empty {@code LinkedHashSet} for a collection of values for 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * one key. 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code LinkedHashSet} containing a collection of values for 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * one key 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Set<V> createCollection() { 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey)); 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order in which key-value pairs are added to the multimap. 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key key to associate with values in the collection 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new decorated {@code LinkedHashSet} containing a collection of 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values for one key 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Collection<V> createCollection(@Nullable K key) { 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetDecorator(key, createCollection()); 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class SetDecorator extends ForwardingSet<V> { 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<V> delegate; 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key; 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SetDecorator(@Nullable K key, Set<V> delegate) { 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.delegate = delegate; 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override protected Set<V> delegate() { 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate; 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson <E> Map.Entry<K, E> createEntry(@Nullable E value) { 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Maps.immutableEntry(key, value); 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) { 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // converts a collection of values into a list of key/value map entries 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<Map.Entry<K, E>> entries 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = Lists.newArrayListWithExpectedSize(values.size()); 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E value : values) { 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries.add(createEntry(value)); 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entries; 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean add(@Nullable V value) { 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.add(value); 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.add(createEntry(value)); 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean addAll(Collection<? extends V> values) { 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.addAll(values); 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.addAll(createEntries(delegate())); 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (V value : delegate) { 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert linkedEntries.remove(createEntry(value)); 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate.clear(); 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<V> iterator() { 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<V> delegateIterator = delegate.iterator(); 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<V>() { 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value; 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson value = delegateIterator.next(); 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return value; 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(createEntry(value)); 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(@Nullable Object value) { 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.remove(value); 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * linkedEntries.remove() will return false when this method is called 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * by entries().iterator().remove() 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(createEntry(value)); 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> values) { 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.removeAll(values); 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.removeAll(createEntries(values)); 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> values) { 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Calling linkedEntries.retainAll() would incorrectly remove values 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * with other keys. 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> iterator = delegate.iterator(); 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = iterator.next(); 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!values.contains(value)) { 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson iterator.remove(); 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(Maps.immutableEntry(key, value)); 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed = true; 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Generates an iterator across map entries that follows the ordering in 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which the key-value pairs were added to the multimap. 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a key-value iterator with the correct ordering 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Iterator<Map.Entry<K, V>> createEntryIterator() { 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator(); 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Map.Entry<K, V>>() { 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<K, V> entry; 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map.Entry<K, V> next() { 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entry = delegateIterator.next(); 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entry; 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Remove from iterator first to keep iterator valid. 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue()); 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If {@code values} is not empty and the multimap already contains a 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * mapping for {@code key}, the {@code keySet()} ordering is unchanged. 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * However, the provided values always come last in the {@link #entries()} and 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #values()} iteration orderings. 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<V> replaceValues( 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, Iterable<? extends V> values) { 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.replaceValues(key, values); 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a set of all key-value pairs. Changes to the returned set will 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update the underlying multimap, and vice versa. The entries set does not 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * support the {@code add} or {@code addAll} operations. 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned set traverses the entries in the 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order they were added to the multimap. 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Each entry is an immutable snapshot of a key-value mapping in the 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, taken at the time the entry is returned by a method call to the 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection or its iterator. 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<Map.Entry<K, V>> entries() { 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.entries(); 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a collection of all values in the multimap. Changes to the returned 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection will update the underlying multimap, and vice versa. 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the order they were added to the multimap. 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> values() { 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.values(); 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Unfortunately, the entries() ordering does not determine the key ordering; 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // see the example in the LinkedListMultimap class Javadoc. 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @serialData the number of distinct keys, and then for each distinct key: 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the first key, the number of values for that key, and the key's values, 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * followed by successive keys and values from the entries() ordering 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectOutputStream") 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultWriteObject(); 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeInt(expectedValuesPerKey); 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.writeMultimap(this, stream); 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Map.Entry<K, V> entry : linkedEntries) { 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getKey()); 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getValue()); 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson expectedValuesPerKey = stream.readInt(); 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int distinctKeys = Serialization.readCount(stream); 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys))); 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries = new LinkedHashSet<Map.Entry<K, V>>( 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson distinctKeys * expectedValuesPerKey); 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Serialization.populateMultimap(this, stream, distinctKeys); 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.clear(); // will clear and repopulate entries 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = 0; i < size(); i++) { 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K key = (K) stream.readObject(); 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = (V) stream.readObject(); 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.add(Maps.immutableEntry(key, value)); 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java serialization not supported") 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 397