001 /*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017 package com.google.common.collect;
018
019 import com.google.common.annotations.GwtCompatible;
020 import com.google.common.annotations.GwtIncompatible;
021 import com.google.common.annotations.VisibleForTesting;
022 import com.google.common.base.Preconditions;
023 import com.google.common.primitives.Ints;
024
025 import java.io.IOException;
026 import java.io.ObjectInputStream;
027 import java.io.ObjectOutputStream;
028 import java.util.Collection;
029 import java.util.Iterator;
030 import java.util.LinkedHashMap;
031 import java.util.LinkedHashSet;
032 import java.util.Map;
033 import java.util.Set;
034
035 import javax.annotation.Nullable;
036
037 /**
038 * Implementation of {@code Multimap} that does not allow duplicate key-value
039 * entries and that returns collections whose iterators follow the ordering in
040 * which the data was added to the multimap.
041 *
042 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
043 * asMap} iterate through the keys in the order they were first added to the
044 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
045 * replaceValues} return collections that iterate through the values in the
046 * order they were added. The collections generated by {@code entries} and
047 * {@code values} iterate across the key-value mappings in the order they were
048 * added to the multimap.
049 *
050 * <p>The iteration ordering of the collections generated by {@code keySet},
051 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
052 * keys remains unchanged, adding or removing mappings does not affect the key
053 * iteration order. However, if you remove all values associated with a key and
054 * then add the key back to the multimap, that key will come last in the key
055 * iteration order.
056 *
057 * <p>The multimap does not store duplicate key-value pairs. Adding a new
058 * key-value pair equal to an existing key-value pair has no effect.
059 *
060 * <p>Keys and values may be null. All optional multimap methods are supported,
061 * and all returned views are modifiable.
062 *
063 * <p>This class is not threadsafe when any concurrent operations update the
064 * multimap. Concurrent read operations will work correctly. To allow concurrent
065 * update operations, wrap your multimap with a call to {@link
066 * Multimaps#synchronizedSetMultimap}.
067 *
068 * <p>See the Guava User Guide article on <a href=
069 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
070 * {@code Multimap}</a>.
071 *
072 * @author Jared Levy
073 * @since 2.0 (imported from Google Collections Library)
074 */
075 @GwtCompatible(serializable = true, emulated = true)
076 public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
077 private static final int DEFAULT_VALUES_PER_KEY = 8;
078
079 @VisibleForTesting
080 transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
081
082 /**
083 * Map entries with an iteration order corresponding to the order in which the
084 * key-value pairs were added to the multimap.
085 */
086 // package-private for GWT deserialization
087 transient Collection<Map.Entry<K, V>> linkedEntries;
088
089 /**
090 * Creates a new, empty {@code LinkedHashMultimap} with the default initial
091 * capacities.
092 */
093 public static <K, V> LinkedHashMultimap<K, V> create() {
094 return new LinkedHashMultimap<K, V>();
095 }
096
097 /**
098 * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold
099 * the specified numbers of keys and values without rehashing.
100 *
101 * @param expectedKeys the expected number of distinct keys
102 * @param expectedValuesPerKey the expected average number of values per key
103 * @throws IllegalArgumentException if {@code expectedKeys} or {@code
104 * expectedValuesPerKey} is negative
105 */
106 public static <K, V> LinkedHashMultimap<K, V> create(
107 int expectedKeys, int expectedValuesPerKey) {
108 return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey);
109 }
110
111 /**
112 * Constructs a {@code LinkedHashMultimap} with the same mappings as the
113 * specified multimap. If a key-value mapping appears multiple times in the
114 * input multimap, it only appears once in the constructed multimap. The new
115 * multimap has the same {@link Multimap#entries()} iteration order as the
116 * input multimap, except for excluding duplicate mappings.
117 *
118 * @param multimap the multimap whose contents are copied to this multimap
119 */
120 public static <K, V> LinkedHashMultimap<K, V> create(
121 Multimap<? extends K, ? extends V> multimap) {
122 return new LinkedHashMultimap<K, V>(multimap);
123 }
124
125 private LinkedHashMultimap() {
126 super(new LinkedHashMap<K, Collection<V>>());
127 linkedEntries = Sets.newLinkedHashSet();
128 }
129
130 private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) {
131 super(new LinkedHashMap<K, Collection<V>>(expectedKeys));
132 Preconditions.checkArgument(expectedValuesPerKey >= 0);
133 this.expectedValuesPerKey = expectedValuesPerKey;
134 linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
135 (int) Math.min(Ints.MAX_POWER_OF_TWO,
136 ((long) expectedKeys) * expectedValuesPerKey));
137 }
138
139 private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) {
140 super(new LinkedHashMap<K, Collection<V>>(
141 Maps.capacity(multimap.keySet().size())));
142 linkedEntries
143 = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size()));
144 putAll(multimap);
145 }
146
147 /**
148 * {@inheritDoc}
149 *
150 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
151 * one key.
152 *
153 * @return a new {@code LinkedHashSet} containing a collection of values for
154 * one key
155 */
156 @Override Set<V> createCollection() {
157 return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey));
158 }
159
160 /**
161 * {@inheritDoc}
162 *
163 * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the
164 * order in which key-value pairs are added to the multimap.
165 *
166 * @param key key to associate with values in the collection
167 * @return a new decorated {@code LinkedHashSet} containing a collection of
168 * values for one key
169 */
170 @Override Collection<V> createCollection(@Nullable K key) {
171 return new SetDecorator(key, createCollection());
172 }
173
174 private class SetDecorator extends ForwardingSet<V> {
175 final Set<V> delegate;
176 final K key;
177
178 SetDecorator(@Nullable K key, Set<V> delegate) {
179 this.delegate = delegate;
180 this.key = key;
181 }
182
183 @Override protected Set<V> delegate() {
184 return delegate;
185 }
186
187 <E> Map.Entry<K, E> createEntry(@Nullable E value) {
188 return Maps.immutableEntry(key, value);
189 }
190
191 <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) {
192 // converts a collection of values into a list of key/value map entries
193 Collection<Map.Entry<K, E>> entries
194 = Lists.newArrayListWithExpectedSize(values.size());
195 for (E value : values) {
196 entries.add(createEntry(value));
197 }
198 return entries;
199 }
200
201 @Override public boolean add(@Nullable V value) {
202 boolean changed = delegate.add(value);
203 if (changed) {
204 linkedEntries.add(createEntry(value));
205 }
206 return changed;
207 }
208
209 @Override public boolean addAll(Collection<? extends V> values) {
210 boolean changed = delegate.addAll(values);
211 if (changed) {
212 linkedEntries.addAll(createEntries(delegate()));
213 }
214 return changed;
215 }
216
217 @Override public void clear() {
218 for (V value : delegate) {
219 linkedEntries.remove(createEntry(value));
220 }
221 delegate.clear();
222 }
223
224 @Override public Iterator<V> iterator() {
225 final Iterator<V> delegateIterator = delegate.iterator();
226 return new Iterator<V>() {
227 V value;
228
229 @Override
230 public boolean hasNext() {
231 return delegateIterator.hasNext();
232 }
233 @Override
234 public V next() {
235 value = delegateIterator.next();
236 return value;
237 }
238 @Override
239 public void remove() {
240 delegateIterator.remove();
241 linkedEntries.remove(createEntry(value));
242 }
243 };
244 }
245
246 @Override public boolean remove(@Nullable Object value) {
247 boolean changed = delegate.remove(value);
248 if (changed) {
249 /*
250 * linkedEntries.remove() will return false when this method is called
251 * by entries().iterator().remove()
252 */
253 linkedEntries.remove(createEntry(value));
254 }
255 return changed;
256 }
257
258 @Override public boolean removeAll(Collection<?> values) {
259 boolean changed = delegate.removeAll(values);
260 if (changed) {
261 linkedEntries.removeAll(createEntries(values));
262 }
263 return changed;
264 }
265
266 @Override public boolean retainAll(Collection<?> values) {
267 /*
268 * Calling linkedEntries.retainAll() would incorrectly remove values
269 * with other keys.
270 */
271 boolean changed = false;
272 Iterator<V> iterator = delegate.iterator();
273 while (iterator.hasNext()) {
274 V value = iterator.next();
275 if (!values.contains(value)) {
276 iterator.remove();
277 linkedEntries.remove(Maps.immutableEntry(key, value));
278 changed = true;
279 }
280 }
281 return changed;
282 }
283 }
284
285 /**
286 * {@inheritDoc}
287 *
288 * <p>Generates an iterator across map entries that follows the ordering in
289 * which the key-value pairs were added to the multimap.
290 *
291 * @return a key-value iterator with the correct ordering
292 */
293 @Override Iterator<Map.Entry<K, V>> createEntryIterator() {
294 final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator();
295
296 return new Iterator<Map.Entry<K, V>>() {
297 Map.Entry<K, V> entry;
298
299 @Override
300 public boolean hasNext() {
301 return delegateIterator.hasNext();
302 }
303
304 @Override
305 public Map.Entry<K, V> next() {
306 entry = delegateIterator.next();
307 return entry;
308 }
309
310 @Override
311 public void remove() {
312 // Remove from iterator first to keep iterator valid.
313 delegateIterator.remove();
314 LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue());
315 }
316 };
317 }
318
319 /**
320 * {@inheritDoc}
321 *
322 * <p>If {@code values} is not empty and the multimap already contains a
323 * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
324 * However, the provided values always come last in the {@link #entries()} and
325 * {@link #values()} iteration orderings.
326 */
327 @Override public Set<V> replaceValues(
328 @Nullable K key, Iterable<? extends V> values) {
329 return super.replaceValues(key, values);
330 }
331
332 /**
333 * Returns a set of all key-value pairs. Changes to the returned set will
334 * update the underlying multimap, and vice versa. The entries set does not
335 * support the {@code add} or {@code addAll} operations.
336 *
337 * <p>The iterator generated by the returned set traverses the entries in the
338 * order they were added to the multimap.
339 *
340 * <p>Each entry is an immutable snapshot of a key-value mapping in the
341 * multimap, taken at the time the entry is returned by a method call to the
342 * collection or its iterator.
343 */
344 @Override public Set<Map.Entry<K, V>> entries() {
345 return super.entries();
346 }
347
348 /**
349 * Returns a collection of all values in the multimap. Changes to the returned
350 * collection will update the underlying multimap, and vice versa.
351 *
352 * <p>The iterator generated by the returned collection traverses the values
353 * in the order they were added to the multimap.
354 */
355 @Override public Collection<V> values() {
356 return super.values();
357 }
358
359 // Unfortunately, the entries() ordering does not determine the key ordering;
360 // see the example in the LinkedListMultimap class Javadoc.
361
362 /**
363 * @serialData the number of distinct keys, and then for each distinct key:
364 * the first key, the number of values for that key, and the key's values,
365 * followed by successive keys and values from the entries() ordering
366 */
367 @GwtIncompatible("java.io.ObjectOutputStream")
368 private void writeObject(ObjectOutputStream stream) throws IOException {
369 stream.defaultWriteObject();
370 stream.writeInt(expectedValuesPerKey);
371 Serialization.writeMultimap(this, stream);
372 for (Map.Entry<K, V> entry : linkedEntries) {
373 stream.writeObject(entry.getKey());
374 stream.writeObject(entry.getValue());
375 }
376 }
377
378 @GwtIncompatible("java.io.ObjectInputStream")
379 private void readObject(ObjectInputStream stream)
380 throws IOException, ClassNotFoundException {
381 stream.defaultReadObject();
382 expectedValuesPerKey = stream.readInt();
383 int distinctKeys = Serialization.readCount(stream);
384 setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys)));
385 linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
386 distinctKeys * expectedValuesPerKey);
387 Serialization.populateMultimap(this, stream, distinctKeys);
388 linkedEntries.clear(); // will clear and repopulate entries
389 for (int i = 0; i < size(); i++) {
390 @SuppressWarnings("unchecked") // reading data stored by writeObject
391 K key = (K) stream.readObject();
392 @SuppressWarnings("unchecked") // reading data stored by writeObject
393 V value = (V) stream.readObject();
394 linkedEntries.add(Maps.immutableEntry(key, value));
395 }
396 }
397
398 @GwtIncompatible("java serialization not supported")
399 private static final long serialVersionUID = 0;
400 }