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