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