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