001 /*
002 * Copyright (C) 2007 Google Inc.
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 public boolean hasNext() {
224 return delegateIterator.hasNext();
225 }
226 public V next() {
227 value = delegateIterator.next();
228 return value;
229 }
230 public void remove() {
231 delegateIterator.remove();
232 linkedEntries.remove(createEntry(value));
233 }
234 };
235 }
236
237 @Override public boolean remove(@Nullable Object value) {
238 boolean changed = delegate.remove(value);
239 if (changed) {
240 /*
241 * linkedEntries.remove() will return false when this method is called
242 * by entries().iterator().remove()
243 */
244 linkedEntries.remove(createEntry(value));
245 }
246 return changed;
247 }
248
249 @Override public boolean removeAll(Collection<?> values) {
250 boolean changed = delegate.removeAll(values);
251 if (changed) {
252 linkedEntries.removeAll(createEntries(values));
253 }
254 return changed;
255 }
256
257 @Override public boolean retainAll(Collection<?> values) {
258 /*
259 * Calling linkedEntries.retainAll() would incorrectly remove values
260 * with other keys.
261 */
262 boolean changed = false;
263 Iterator<V> iterator = delegate.iterator();
264 while (iterator.hasNext()) {
265 V value = iterator.next();
266 if (!values.contains(value)) {
267 iterator.remove();
268 linkedEntries.remove(Maps.immutableEntry(key, value));
269 changed = true;
270 }
271 }
272 return changed;
273 }
274 }
275
276 /**
277 * {@inheritDoc}
278 *
279 * <p>Generates an iterator across map entries that follows the ordering in
280 * which the key-value pairs were added to the multimap.
281 *
282 * @return a key-value iterator with the correct ordering
283 */
284 @Override Iterator<Map.Entry<K, V>> createEntryIterator() {
285 final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator();
286
287 return new Iterator<Map.Entry<K, V>>() {
288 Map.Entry<K, V> entry;
289
290 public boolean hasNext() {
291 return delegateIterator.hasNext();
292 }
293
294 public Map.Entry<K, V> next() {
295 entry = delegateIterator.next();
296 return entry;
297 }
298
299 public void remove() {
300 // Remove from iterator first to keep iterator valid.
301 delegateIterator.remove();
302 LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue());
303 }
304 };
305 }
306
307 /**
308 * {@inheritDoc}
309 *
310 * <p>If {@code values} is not empty and the multimap already contains a
311 * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
312 * However, the provided values always come last in the {@link #entries()} and
313 * {@link #values()} iteration orderings.
314 */
315 @Override public Set<V> replaceValues(
316 @Nullable K key, Iterable<? extends V> values) {
317 return super.replaceValues(key, values);
318 }
319
320 /**
321 * Returns a set of all key-value pairs. Changes to the returned set will
322 * update the underlying multimap, and vice versa. The entries set does not
323 * support the {@code add} or {@code addAll} operations.
324 *
325 * <p>The iterator generated by the returned set traverses the entries in the
326 * order they were added to the multimap.
327 *
328 * <p>Each entry is an immutable snapshot of a key-value mapping in the
329 * multimap, taken at the time the entry is returned by a method call to the
330 * collection or its iterator.
331 */
332 @Override public Set<Map.Entry<K, V>> entries() {
333 return super.entries();
334 }
335
336 /**
337 * Returns a collection of all values in the multimap. Changes to the returned
338 * collection will update the underlying multimap, and vice versa.
339 *
340 * <p>The iterator generated by the returned collection traverses the values
341 * in the order they were added to the multimap.
342 */
343 @Override public Collection<V> values() {
344 return super.values();
345 }
346
347 // Unfortunately, the entries() ordering does not determine the key ordering;
348 // see the example in the LinkedListMultimap class Javadoc.
349
350 /**
351 * @serialData the number of distinct keys, and then for each distinct key:
352 * the first key, the number of values for that key, and the key's values,
353 * followed by successive keys and values from the entries() ordering
354 */
355 @GwtIncompatible("java.io.ObjectOutputStream")
356 private void writeObject(ObjectOutputStream stream) throws IOException {
357 stream.defaultWriteObject();
358 stream.writeInt(expectedValuesPerKey);
359 Serialization.writeMultimap(this, stream);
360 for (Map.Entry<K, V> entry : linkedEntries) {
361 stream.writeObject(entry.getKey());
362 stream.writeObject(entry.getValue());
363 }
364 }
365
366 @GwtIncompatible("java.io.ObjectInputStream")
367 private void readObject(ObjectInputStream stream)
368 throws IOException, ClassNotFoundException {
369 stream.defaultReadObject();
370 expectedValuesPerKey = stream.readInt();
371 int distinctKeys = Serialization.readCount(stream);
372 setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys)));
373 linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
374 distinctKeys * expectedValuesPerKey);
375 Serialization.populateMultimap(this, stream, distinctKeys);
376 linkedEntries.clear(); // will clear and repopulate entries
377 for (int i = 0; i < size(); i++) {
378 @SuppressWarnings("unchecked") // reading data stored by writeObject
379 K key = (K) stream.readObject();
380 @SuppressWarnings("unchecked") // reading data stored by writeObject
381 V value = (V) stream.readObject();
382 linkedEntries.add(Maps.immutableEntry(key, value));
383 }
384 }
385
386 @GwtIncompatible("java serialization not supported")
387 private static final long serialVersionUID = 0;
388 }