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 static com.google.common.base.Preconditions.checkArgument;
020
021 import com.google.common.annotations.GwtCompatible;
022 import com.google.common.annotations.GwtIncompatible;
023 import com.google.common.annotations.VisibleForTesting;
024 import com.google.common.base.Objects;
025 import com.google.common.primitives.Ints;
026
027 import java.io.IOException;
028 import java.io.ObjectInputStream;
029 import java.io.ObjectOutputStream;
030 import java.util.Arrays;
031 import java.util.Collection;
032 import java.util.ConcurrentModificationException;
033 import java.util.Iterator;
034 import java.util.LinkedHashMap;
035 import java.util.LinkedHashSet;
036 import java.util.Map;
037 import java.util.NoSuchElementException;
038 import java.util.Set;
039
040 import javax.annotation.Nullable;
041
042 /**
043 * Implementation of {@code Multimap} that does not allow duplicate key-value
044 * entries and that returns collections whose iterators follow the ordering in
045 * which the data was added to the multimap.
046 *
047 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
048 * asMap} iterate through the keys in the order they were first added to the
049 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
050 * replaceValues} return collections that iterate through the values in the
051 * order they were added. The collections generated by {@code entries} and
052 * {@code values} iterate across the key-value mappings in the order they were
053 * added to the multimap.
054 *
055 * <p>The iteration ordering of the collections generated by {@code keySet},
056 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
057 * keys remains unchanged, adding or removing mappings does not affect the key
058 * iteration order. However, if you remove all values associated with a key and
059 * then add the key back to the multimap, that key will come last in the key
060 * iteration order.
061 *
062 * <p>The multimap does not store duplicate key-value pairs. Adding a new
063 * key-value pair equal to an existing key-value pair has no effect.
064 *
065 * <p>Keys and values may be null. All optional multimap methods are supported,
066 * and all returned views are modifiable.
067 *
068 * <p>This class is not threadsafe when any concurrent operations update the
069 * multimap. Concurrent read operations will work correctly. To allow concurrent
070 * update operations, wrap your multimap with a call to {@link
071 * Multimaps#synchronizedSetMultimap}.
072 *
073 * <p>See the Guava User Guide article on <a href=
074 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
075 * {@code Multimap}</a>.
076 *
077 * @author Jared Levy
078 * @author Louis Wasserman
079 * @since 2.0 (imported from Google Collections Library)
080 */
081 @GwtCompatible(serializable = true, emulated = true)
082 public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
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>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
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>(
104 Maps.capacity(expectedKeys),
105 Maps.capacity(expectedValuesPerKey));
106 }
107
108 /**
109 * Constructs a {@code LinkedHashMultimap} with the same mappings as the
110 * specified multimap. If a key-value mapping appears multiple times in the
111 * input multimap, it only appears once in the constructed multimap. The new
112 * multimap has the same {@link Multimap#entries()} iteration order as the
113 * input multimap, except for excluding duplicate mappings.
114 *
115 * @param multimap the multimap whose contents are copied to this multimap
116 */
117 public static <K, V> LinkedHashMultimap<K, V> create(
118 Multimap<? extends K, ? extends V> multimap) {
119 LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
120 result.putAll(multimap);
121 return result;
122 }
123
124 private interface ValueSetLink<K, V> {
125 ValueSetLink<K, V> getPredecessorInValueSet();
126 ValueSetLink<K, V> getSuccessorInValueSet();
127
128 void setPredecessorInValueSet(ValueSetLink<K, V> entry);
129 void setSuccessorInValueSet(ValueSetLink<K, V> entry);
130 }
131
132 private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
133 pred.setSuccessorInValueSet(succ);
134 succ.setPredecessorInValueSet(pred);
135 }
136
137 private static <K, V> void succeedsInMultimap(
138 ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
139 pred.setSuccessorInMultimap(succ);
140 succ.setPredecessorInMultimap(pred);
141 }
142
143 private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
144 succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
145 }
146
147 private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
148 succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
149 }
150
151 /**
152 * LinkedHashMultimap entries are in no less than three coexisting linked lists:
153 * a row in the hash table for a Set<V> associated with a key, the linked list
154 * of insertion-ordered entries in that Set<V>, and the linked list of entries
155 * in the LinkedHashMultimap as a whole.
156 */
157 private static final class ValueEntry<K, V> extends AbstractMapEntry<K, V>
158 implements ValueSetLink<K, V> {
159 final K key;
160 final V value;
161 final int valueHash;
162
163 @Nullable ValueEntry<K, V> nextInValueSetHashRow;
164
165 ValueSetLink<K, V> predecessorInValueSet;
166 ValueSetLink<K, V> successorInValueSet;
167
168 ValueEntry<K, V> predecessorInMultimap;
169 ValueEntry<K, V> successorInMultimap;
170
171 ValueEntry(@Nullable K key, @Nullable V value, int valueHash,
172 @Nullable ValueEntry<K, V> nextInValueSetHashRow) {
173 this.key = key;
174 this.value = value;
175 this.valueHash = valueHash;
176 this.nextInValueSetHashRow = nextInValueSetHashRow;
177 }
178
179 @Override
180 public K getKey() {
181 return key;
182 }
183
184 @Override
185 public V getValue() {
186 return value;
187 }
188
189 @Override
190 public ValueSetLink<K, V> getPredecessorInValueSet() {
191 return predecessorInValueSet;
192 }
193
194 @Override
195 public ValueSetLink<K, V> getSuccessorInValueSet() {
196 return successorInValueSet;
197 }
198
199 @Override
200 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
201 predecessorInValueSet = entry;
202 }
203
204 @Override
205 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
206 successorInValueSet = entry;
207 }
208
209 public ValueEntry<K, V> getPredecessorInMultimap() {
210 return predecessorInMultimap;
211 }
212
213 public ValueEntry<K, V> getSuccessorInMultimap() {
214 return successorInMultimap;
215 }
216
217 public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
218 this.successorInMultimap = multimapSuccessor;
219 }
220
221 public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
222 this.predecessorInMultimap = multimapPredecessor;
223 }
224 }
225
226 private static final int DEFAULT_KEY_CAPACITY = 16;
227 private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
228
229 private static final int MAX_VALUE_SET_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
230
231 @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
232 private transient ValueEntry<K, V> multimapHeaderEntry;
233
234 private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
235 super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
236
237 checkArgument(valueSetCapacity >= 0,
238 "expectedValuesPerKey must be >= 0 but was %s", valueSetCapacity);
239
240 this.valueSetCapacity = valueSetCapacity;
241 this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
242 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
243 }
244
245 /**
246 * {@inheritDoc}
247 *
248 * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
249 * one key.
250 *
251 * @return a new {@code LinkedHashSet} containing a collection of values for
252 * one key
253 */
254 @Override
255 Set<V> createCollection() {
256 return new LinkedHashSet<V>(valueSetCapacity);
257 }
258
259 /**
260 * {@inheritDoc}
261 *
262 * <p>Creates a decorated insertion-ordered set that also keeps track of the
263 * order in which key-value pairs are added to the multimap.
264 *
265 * @param key key to associate with values in the collection
266 * @return a new decorated set containing a collection of values for one key
267 */
268 @Override
269 Collection<V> createCollection(K key) {
270 return new ValueSet(key, valueSetCapacity);
271 }
272
273 /**
274 * {@inheritDoc}
275 *
276 * <p>If {@code values} is not empty and the multimap already contains a
277 * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
278 * However, the provided values always come last in the {@link #entries()} and
279 * {@link #values()} iteration orderings.
280 */
281 @Override
282 public Set<V> replaceValues(K key, Iterable<? extends V> values) {
283 return super.replaceValues(key, values);
284 }
285
286 /**
287 * Returns a set of all key-value pairs. Changes to the returned set will
288 * update the underlying multimap, and vice versa. The entries set does not
289 * support the {@code add} or {@code addAll} operations.
290 *
291 * <p>The iterator generated by the returned set traverses the entries in the
292 * order they were added to the multimap.
293 *
294 * <p>Each entry is an immutable snapshot of a key-value mapping in the
295 * multimap, taken at the time the entry is returned by a method call to the
296 * collection or its iterator.
297 */
298 @Override public Set<Map.Entry<K, V>> entries() {
299 return super.entries();
300 }
301
302 /**
303 * Returns a collection of all values in the multimap. Changes to the returned
304 * collection will update the underlying multimap, and vice versa.
305 *
306 * <p>The iterator generated by the returned collection traverses the values
307 * in the order they were added to the multimap.
308 */
309 @Override public Collection<V> values() {
310 return super.values();
311 }
312
313 @VisibleForTesting
314 final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
315 /*
316 * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
317 * consumption.
318 */
319
320 private final K key;
321 private ValueEntry<K, V>[] hashTable;
322 private int size = 0;
323 private int modCount = 0;
324
325 // We use the set object itself as the end of the linked list, avoiding an unnecessary
326 // entry object per key.
327 private ValueSetLink<K, V> firstEntry;
328 private ValueSetLink<K, V> lastEntry;
329
330 ValueSet(K key, int expectedValues) {
331 this.key = key;
332 this.firstEntry = this;
333 this.lastEntry = this;
334 // Round expected values up to a power of 2 to get the table size.
335 int tableSize = Integer.highestOneBit(Math.max(expectedValues, 2) - 1) << 1;
336 if (tableSize < 0) {
337 tableSize = MAX_VALUE_SET_TABLE_SIZE;
338 }
339
340 @SuppressWarnings("unchecked")
341 ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
342 this.hashTable = hashTable;
343 }
344
345 @Override
346 public ValueSetLink<K, V> getPredecessorInValueSet() {
347 return lastEntry;
348 }
349
350 @Override
351 public ValueSetLink<K, V> getSuccessorInValueSet() {
352 return firstEntry;
353 }
354
355 @Override
356 public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
357 lastEntry = entry;
358 }
359
360 @Override
361 public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
362 firstEntry = entry;
363 }
364
365 @Override
366 public Iterator<V> iterator() {
367 return new Iterator<V>() {
368 ValueSetLink<K, V> nextEntry = firstEntry;
369 ValueEntry<K, V> toRemove;
370 int expectedModCount = modCount;
371
372 private void checkForComodification() {
373 if (modCount != expectedModCount) {
374 throw new ConcurrentModificationException();
375 }
376 }
377
378 @Override
379 public boolean hasNext() {
380 checkForComodification();
381 return nextEntry != ValueSet.this;
382 }
383
384 @Override
385 public V next() {
386 if (!hasNext()) {
387 throw new NoSuchElementException();
388 }
389 ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
390 V result = entry.getValue();
391 toRemove = entry;
392 nextEntry = entry.getSuccessorInValueSet();
393 return result;
394 }
395
396 @Override
397 public void remove() {
398 checkForComodification();
399 Iterators.checkRemove(toRemove != null);
400 Object o = toRemove.getValue();
401 int hash = (o == null) ? 0 : o.hashCode();
402 int row = Hashing.smear(hash) & (hashTable.length - 1);
403 ValueEntry<K, V> prev = null;
404 for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
405 prev = entry, entry = entry.nextInValueSetHashRow) {
406 if (entry == toRemove) {
407 if (prev == null) {
408 // first entry in row
409 hashTable[row] = entry.nextInValueSetHashRow;
410 } else {
411 prev.nextInValueSetHashRow = entry.nextInValueSetHashRow;
412 }
413 deleteFromValueSet(toRemove);
414 deleteFromMultimap(toRemove);
415 size--;
416 expectedModCount = ++modCount;
417 break;
418 }
419 }
420 toRemove = null;
421 }
422 };
423 }
424
425 @Override
426 public int size() {
427 return size;
428 }
429
430 @Override
431 public boolean contains(@Nullable Object o) {
432 int hash = (o == null) ? 0 : o.hashCode();
433 int row = Hashing.smear(hash) & (hashTable.length - 1);
434
435 for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
436 entry = entry.nextInValueSetHashRow) {
437 if (hash == entry.valueHash && Objects.equal(o, entry.getValue())) {
438 return true;
439 }
440 }
441 return false;
442 }
443
444 /**
445 * The threshold above which the hash table should be rebuilt.
446 */
447 @VisibleForTesting int threshold() {
448 return hashTable.length; // load factor of 1.0
449 }
450
451 @Override
452 public boolean add(@Nullable V value) {
453 int hash = (value == null) ? 0 : value.hashCode();
454 int row = Hashing.smear(hash) & (hashTable.length - 1);
455
456 ValueEntry<K, V> rowHead = hashTable[row];
457 for (ValueEntry<K, V> entry = rowHead; entry != null;
458 entry = entry.nextInValueSetHashRow) {
459 if (hash == entry.valueHash && Objects.equal(value, entry.getValue())) {
460 return false;
461 }
462 }
463
464 ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, hash, rowHead);
465 succeedsInValueSet(lastEntry, newEntry);
466 succeedsInValueSet(newEntry, this);
467 succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
468 succeedsInMultimap(newEntry, multimapHeaderEntry);
469 hashTable[row] = newEntry;
470 size++;
471 modCount++;
472 rehashIfNecessary();
473 return true;
474 }
475
476 private void rehashIfNecessary() {
477 if (size > threshold() && hashTable.length < MAX_VALUE_SET_TABLE_SIZE) {
478 @SuppressWarnings("unchecked")
479 ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
480 this.hashTable = hashTable;
481 int mask = hashTable.length - 1;
482 for (ValueSetLink<K, V> entry = firstEntry;
483 entry != this; entry = entry.getSuccessorInValueSet()) {
484 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
485 int row = Hashing.smear(valueEntry.valueHash) & mask;
486 valueEntry.nextInValueSetHashRow = hashTable[row];
487 hashTable[row] = valueEntry;
488 }
489 }
490 }
491
492 @Override
493 public boolean remove(@Nullable Object o) {
494 int hash = (o == null) ? 0 : o.hashCode();
495 int row = Hashing.smear(hash) & (hashTable.length - 1);
496
497 ValueEntry<K, V> prev = null;
498 for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
499 prev = entry, entry = entry.nextInValueSetHashRow) {
500 if (hash == entry.valueHash && Objects.equal(o, entry.getValue())) {
501 if (prev == null) {
502 // first entry in the row
503 hashTable[row] = entry.nextInValueSetHashRow;
504 } else {
505 prev.nextInValueSetHashRow = entry.nextInValueSetHashRow;
506 }
507 deleteFromValueSet(entry);
508 deleteFromMultimap(entry);
509 size--;
510 modCount++;
511 return true;
512 }
513 }
514 return false;
515 }
516
517 @Override
518 public void clear() {
519 Arrays.fill(hashTable, null);
520 size = 0;
521 for (ValueSetLink<K, V> entry = firstEntry;
522 entry != this; entry = entry.getSuccessorInValueSet()) {
523 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
524 deleteFromMultimap(valueEntry);
525 }
526 succeedsInValueSet(this, this);
527 modCount++;
528 }
529 }
530
531 @Override
532 Iterator<Map.Entry<K, V>> createEntryIterator() {
533 return new Iterator<Map.Entry<K, V>>() {
534 ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
535 ValueEntry<K, V> toRemove;
536
537 @Override
538 public boolean hasNext() {
539 return nextEntry != multimapHeaderEntry;
540 }
541
542 @Override
543 public Map.Entry<K, V> next() {
544 if (!hasNext()) {
545 throw new NoSuchElementException();
546 }
547 ValueEntry<K, V> result = nextEntry;
548 toRemove = result;
549 nextEntry = nextEntry.successorInMultimap;
550 return result;
551 }
552
553 @Override
554 public void remove() {
555 Iterators.checkRemove(toRemove != null);
556 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
557 toRemove = null;
558 }
559 };
560 }
561
562 @Override
563 public void clear() {
564 super.clear();
565 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
566 }
567
568 /**
569 * @serialData the expected values per key, the number of distinct keys,
570 * the number of entries, and the entries in order
571 */
572 @GwtIncompatible("java.io.ObjectOutputStream")
573 private void writeObject(ObjectOutputStream stream) throws IOException {
574 stream.defaultWriteObject();
575 stream.writeInt(valueSetCapacity);
576 stream.writeInt(keySet().size());
577 for (K key : keySet()) {
578 stream.writeObject(key);
579 }
580 stream.writeInt(size());
581 for (Map.Entry<K, V> entry : entries()) {
582 stream.writeObject(entry.getKey());
583 stream.writeObject(entry.getValue());
584 }
585 }
586
587 @GwtIncompatible("java.io.ObjectInputStream")
588 private void readObject(ObjectInputStream stream)
589 throws IOException, ClassNotFoundException {
590 stream.defaultReadObject();
591 multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
592 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
593 valueSetCapacity = stream.readInt();
594 int distinctKeys = stream.readInt();
595 Map<K, Collection<V>> map =
596 new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys));
597 for (int i = 0; i < distinctKeys; i++) {
598 @SuppressWarnings("unchecked")
599 K key = (K) stream.readObject();
600 map.put(key, createCollection(key));
601 }
602 int entries = stream.readInt();
603 for (int i = 0; i < entries; i++) {
604 @SuppressWarnings("unchecked")
605 K key = (K) stream.readObject();
606 @SuppressWarnings("unchecked")
607 V value = (V) stream.readObject();
608 map.get(key).add(value);
609 }
610 setMap(map);
611 }
612
613 @GwtIncompatible("java serialization not supported")
614 private static final long serialVersionUID = 1;
615 }