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; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.VisibleForTesting; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Preconditions; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashMap; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashSet; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Implementation of {@code Multimap} that does not allow duplicate key-value 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * entries and that returns collections whose iterators follow the ordering in 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which the data was added to the multimap. 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The collections returned by {@code keySet}, {@code keys}, and {@code 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * asMap} iterate through the keys in the order they were first added to the 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Similarly, {@code get}, {@code removeAll}, and {@code 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * replaceValues} return collections that iterate through the values in the 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order they were added. The collections generated by {@code entries} and 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code values} iterate across the key-value mappings in the order they were 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * added to the multimap. 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration ordering of the collections generated by {@code keySet}, 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * keys remains unchanged, adding or removing mappings does not affect the key 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order. However, if you remove all values associated with a key and 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * then add the key back to the multimap, that key will come last in the key 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order. 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The multimap does not store duplicate key-value pairs. Adding a new 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value pair equal to an existing key-value pair has no effect. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Keys and values may be null. All optional multimap methods are supported, 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and all returned views are modifiable. 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Concurrent read operations will work correctly. To allow concurrent 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update operations, wrap your multimap with a call to {@link 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedSetMultimap}. 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> { 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final int DEFAULT_VALUES_PER_KEY = 8; 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @VisibleForTesting 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY; 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Map entries with an iteration order corresponding to the order in which the 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value pairs were added to the multimap. 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // package-private for GWT deserialization 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson transient Collection<Map.Entry<K, V>> linkedEntries; 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new, empty {@code LinkedHashMultimap} with the default initial 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * capacities. 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create() { 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(); 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified numbers of keys and values without rehashing. 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedKeys the expected number of distinct keys 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedValuesPerKey the expected average number of values per key 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedKeys} or {@code 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * expectedValuesPerKey} is negative 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create( 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int expectedKeys, int expectedValuesPerKey) { 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey); 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a {@code LinkedHashMultimap} with the same mappings as the 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified multimap. If a key-value mapping appears multiple times in the 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * input multimap, it only appears once in the constructed multimap. The new 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap has the same {@link Multimap#entries()} iteration order as the 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * input multimap, except for excluding duplicate mappings. 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param multimap the multimap whose contents are copied to this multimap 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedHashMultimap<K, V> create( 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<? extends K, ? extends V> multimap) { 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashMultimap<K, V>(multimap); 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap() { 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>()); 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries = Sets.newLinkedHashSet(); 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) { 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>(expectedKeys)); 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkArgument(expectedValuesPerKey >= 0); 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.expectedValuesPerKey = expectedValuesPerKey; 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries = new LinkedHashSet<Map.Entry<K, V>>( 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert (int) Math.min(Ints.MAX_POWER_OF_TWO, 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ((long) expectedKeys) * expectedValuesPerKey)); 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) { 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(new LinkedHashMap<K, Collection<V>>( 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Maps.capacity(multimap.keySet().size()))); 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size())); 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson putAll(multimap); 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Creates an empty {@code LinkedHashSet} for a collection of values for 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * one key. 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code LinkedHashSet} containing a collection of values for 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * one key 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Set<V> createCollection() { 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey)); 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order in which key-value pairs are added to the multimap. 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key key to associate with values in the collection 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new decorated {@code LinkedHashSet} containing a collection of 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values for one key 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Collection<V> createCollection(@Nullable K key) { 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetDecorator(key, createCollection()); 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class SetDecorator extends ForwardingSet<V> { 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<V> delegate; 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key; 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SetDecorator(@Nullable K key, Set<V> delegate) { 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.delegate = delegate; 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override protected Set<V> delegate() { 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate; 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson <E> Map.Entry<K, E> createEntry(@Nullable E value) { 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Maps.immutableEntry(key, value); 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) { 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // converts a collection of values into a list of key/value map entries 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<Map.Entry<K, E>> entries 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = Lists.newArrayListWithExpectedSize(values.size()); 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E value : values) { 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries.add(createEntry(value)); 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entries; 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean add(@Nullable V value) { 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.add(value); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.add(createEntry(value)); 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean addAll(Collection<? extends V> values) { 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.addAll(values); 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.addAll(createEntries(delegate())); 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (V value : delegate) { 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert linkedEntries.remove(createEntry(value)); 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate.clear(); 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<V> iterator() { 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<V> delegateIterator = delegate.iterator(); 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<V>() { 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value; 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson value = delegateIterator.next(); 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return value; 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(createEntry(value)); 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(@Nullable Object value) { 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.remove(value); 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * linkedEntries.remove() will return false when this method is called 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * by entries().iterator().remove() 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(createEntry(value)); 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> values) { 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.removeAll(values); 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.removeAll(createEntries(values)); 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> values) { 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Calling linkedEntries.retainAll() would incorrectly remove values 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * with other keys. 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> iterator = delegate.iterator(); 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = iterator.next(); 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!values.contains(value)) { 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson iterator.remove(); 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson linkedEntries.remove(Maps.immutableEntry(key, value)); 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed = true; 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Generates an iterator across map entries that follows the ordering in 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * which the key-value pairs were added to the multimap. 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a key-value iterator with the correct ordering 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Iterator<Map.Entry<K, V>> createEntryIterator() { 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator(); 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Map.Entry<K, V>>() { 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<K, V> entry; 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map.Entry<K, V> next() { 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entry = delegateIterator.next(); 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entry; 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Remove from iterator first to keep iterator valid. 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue()); 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If {@code values} is not empty and the multimap already contains a 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * mapping for {@code key}, the {@code keySet()} ordering is unchanged. 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * However, the provided values always come last in the {@link #entries()} and 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #values()} iteration orderings. 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<V> replaceValues( 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, Iterable<? extends V> values) { 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.replaceValues(key, values); 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a set of all key-value pairs. Changes to the returned set will 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update the underlying multimap, and vice versa. The entries set does not 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * support the {@code add} or {@code addAll} operations. 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned set traverses the entries in the 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order they were added to the multimap. 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Each entry is an immutable snapshot of a key-value mapping in the 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, taken at the time the entry is returned by a method call to the 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection or its iterator. 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<Map.Entry<K, V>> entries() { 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.entries(); 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a collection of all values in the multimap. Changes to the returned 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection will update the underlying multimap, and vice versa. 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the order they were added to the multimap. 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> values() { 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.values(); 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Unfortunately, the entries() ordering does not determine the key ordering; 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // see the example in the LinkedListMultimap class Javadoc. 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 355