1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkNotNull;
20 import static com.google.common.base.Preconditions.checkPositionIndex;
21 import static com.google.common.base.Preconditions.checkState;
22 import static com.google.common.collect.CollectPreconditions.checkRemove;
23 import static java.util.Collections.unmodifiableList;
24
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.common.annotations.GwtIncompatible;
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import com.google.j2objc.annotations.WeakOuter;
29 import java.io.IOException;
30 import java.io.ObjectInputStream;
31 import java.io.ObjectOutputStream;
32 import java.io.Serializable;
33 import java.util.AbstractSequentialList;
34 import java.util.Collection;
35 import java.util.ConcurrentModificationException;
36 import java.util.Iterator;
37 import java.util.List;
38 import java.util.ListIterator;
39 import java.util.Map;
40 import java.util.Map.Entry;
41 import java.util.NoSuchElementException;
42 import java.util.Set;
43 import java.util.function.Consumer;
44 import org.checkerframework.checker.nullness.qual.Nullable;
45
46 /**
47 * An implementation of {@code ListMultimap} that supports deterministic iteration order for both
48 * keys and values. The iteration order is preserved across non-distinct key values. For example,
49 * for the following multimap definition:
50 *
51 * <pre>{@code
52 * Multimap<K, V> multimap = LinkedListMultimap.create();
53 * multimap.put(key1, foo);
54 * multimap.put(key2, bar);
55 * multimap.put(key1, baz);
56 * }</pre>
57 *
58 * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, and similarly for
59 * {@link #entries()}. Unlike {@link LinkedHashMultimap}, the iteration order is kept consistent
60 * between keys, entries and values. For example, calling:
61 *
62 * <pre>{@code
63 * multimap.remove(key1, foo);
64 * }</pre>
65 *
66 * <p>changes the entries iteration order to {@code [key2=bar, key1=baz]} and the key iteration
67 * order to {@code [key2, key1]}. The {@link #entries()} iterator returns mutable map entries, and
68 * {@link #replaceValues} attempts to preserve iteration order as much as possible.
69 *
70 * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate through the keys in
71 * the order they were first added to the multimap. Similarly, {@link #get}, {@link #removeAll}, and
72 * {@link #replaceValues} return collections that iterate through the values in the order they were
73 * added. The collections generated by {@link #entries()}, {@link #keys()}, and {@link #values}
74 * iterate across the key-value mappings in the order they were added to the multimap.
75 *
76 * <p>The {@link #values()} and {@link #entries()} methods both return a {@code List}, instead of
77 * the {@code Collection} specified by the {@link ListMultimap} interface.
78 *
79 * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()}, {@link #values}, {@link
80 * #entries()}, and {@link #asMap} return collections that are views of the multimap. If the
81 * multimap is modified while an iteration over any of those collections is in progress, except
82 * through the iterator's methods, the results of the iteration are undefined.
83 *
84 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
85 * views are modifiable.
86 *
87 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
88 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
89 * with a call to {@link Multimaps#synchronizedListMultimap}.
90 *
91 * <p>See the Guava User Guide article on <a href=
92 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code
93 * Multimap}</a>.
94 *
95 * @author Mike Bostock
96 * @since 2.0
97 */
98 @GwtCompatible(serializable = true, emulated = true)
99 public class LinkedListMultimap<K, V> extends AbstractMultimap<K, V>
100 implements ListMultimap<K, V>, Serializable {
101 /*
102 * Order is maintained using a linked list containing all key-value pairs. In
103 * addition, a series of disjoint linked lists of "siblings", each containing
104 * the values for a specific key, is used to implement {@link
105 * ValueForKeyIterator} in constant time.
106 */
107
108 private static final class Node<K, V> extends AbstractMapEntry<K, V> {
109 final @Nullable K key;
110 @Nullable V value;
111 @Nullable Node<K, V> next; // the next node (with any key)
112 @Nullable Node<K, V> previous; // the previous node (with any key)
113 @Nullable Node<K, V> nextSibling; // the next node with the same key
114 @Nullable Node<K, V> previousSibling; // the previous node with the same key
115
116 Node(@Nullable K key, @Nullable V value) {
117 this.key = key;
118 this.value = value;
119 }
120
121 @Override
122 public K getKey() {
123 return key;
124 }
125
126 @Override
127 public V getValue() {
128 return value;
129 }
130
131 @Override
132 public V setValue(@Nullable V newValue) {
133 V result = value;
134 this.value = newValue;
135 return result;
136 }
137 }
138
139 private static class KeyList<K, V> {
140 Node<K, V> head;
141 Node<K, V> tail;
142 int count;
143
144 KeyList(Node<K, V> firstNode) {
145 this.head = firstNode;
146 this.tail = firstNode;
147 firstNode.previousSibling = null;
148 firstNode.nextSibling = null;
149 this.count = 1;
150 }
151 }
152
153 private transient @Nullable Node<K, V> head; // the head for all keys
154 private transient @Nullable Node<K, V> tail; // the tail for all keys
155 private transient Map<K, KeyList<K, V>> keyToKeyList;
156 private transient int size;
157
158 /*
159 * Tracks modifications to keyToKeyList so that addition or removal of keys invalidates
160 * preexisting iterators. This does *not* track simple additions and removals of values
161 * that are not the first to be added or last to be removed for their key.
162 */
163 private transient int modCount;
164
165 /** Creates a new, empty {@code LinkedListMultimap} with the default initial capacity. */
166 public static <K, V> LinkedListMultimap<K, V> create() {
167 return new LinkedListMultimap<>();
168 }
169
170 /**
171 * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold the specified
172 * number of keys without rehashing.
173 *
174 * @param expectedKeys the expected number of distinct keys
175 * @throws IllegalArgumentException if {@code expectedKeys} is negative
176 */
177 public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) {
178 return new LinkedListMultimap<>(expectedKeys);
179 }
180
181 /**
182 * Constructs a {@code LinkedListMultimap} with the same mappings as the specified {@code
183 * Multimap}. The new multimap has the same {@link Multimap#entries()} iteration order as the
184 * input multimap.
185 *
186 * @param multimap the multimap whose contents are copied to this multimap
187 */
188 public static <K, V> LinkedListMultimap<K, V> create(
189 Multimap<? extends K, ? extends V> multimap) {
190 return new LinkedListMultimap<>(multimap);
191 }
192
193 LinkedListMultimap() {
194 this(12);
195 }
196
197 private LinkedListMultimap(int expectedKeys) {
198 keyToKeyList = Platform.newHashMapWithExpectedSize(expectedKeys);
199 }
200
201 private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
202 this(multimap.keySet().size());
203 putAll(multimap);
204 }
205
206 /**
207 * Adds a new node for the specified key-value pair before the specified {@code nextSibling}
208 * element, or at the end of the list if {@code nextSibling} is null. Note: if {@code nextSibling}
209 * is specified, it MUST be for an node for the same {@code key}!
210 */
211 @CanIgnoreReturnValue
212 private Node<K, V> addNode(@Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) {
213 Node<K, V> node = new Node<>(key, value);
214 if (head == null) { // empty list
215 head = tail = node;
216 keyToKeyList.put(key, new KeyList<K, V>(node));
217 modCount++;
218 } else if (nextSibling == null) { // non-empty list, add to tail
219 tail.next = node;
220 node.previous = tail;
221 tail = node;
222 KeyList<K, V> keyList = keyToKeyList.get(key);
223 if (keyList == null) {
224 keyToKeyList.put(key, keyList = new KeyList<>(node));
225 modCount++;
226 } else {
227 keyList.count++;
228 Node<K, V> keyTail = keyList.tail;
229 keyTail.nextSibling = node;
230 node.previousSibling = keyTail;
231 keyList.tail = node;
232 }
233 } else { // non-empty list, insert before nextSibling
234 KeyList<K, V> keyList = keyToKeyList.get(key);
235 keyList.count++;
236 node.previous = nextSibling.previous;
237 node.previousSibling = nextSibling.previousSibling;
238 node.next = nextSibling;
239 node.nextSibling = nextSibling;
240 if (nextSibling.previousSibling == null) { // nextSibling was key head
241 keyToKeyList.get(key).head = node;
242 } else {
243 nextSibling.previousSibling.nextSibling = node;
244 }
245 if (nextSibling.previous == null) { // nextSibling was head
246 head = node;
247 } else {
248 nextSibling.previous.next = node;
249 }
250 nextSibling.previous = node;
251 nextSibling.previousSibling = node;
252 }
253 size++;
254 return node;
255 }
256
257 /**
258 * Removes the specified node from the linked list. This method is only intended to be used from
259 * the {@code Iterator} classes. See also {@link LinkedListMultimap#removeAllNodes(Object)}.
260 */
261 private void removeNode(Node<K, V> node) {
262 if (node.previous != null) {
263 node.previous.next = node.next;
264 } else { // node was head
265 head = node.next;
266 }
267 if (node.next != null) {
268 node.next.previous = node.previous;
269 } else { // node was tail
270 tail = node.previous;
271 }
272 if (node.previousSibling == null && node.nextSibling == null) {
273 KeyList<K, V> keyList = keyToKeyList.remove(node.key);
274 keyList.count = 0;
275 modCount++;
276 } else {
277 KeyList<K, V> keyList = keyToKeyList.get(node.key);
278 keyList.count--;
279
280 if (node.previousSibling == null) {
281 keyList.head = node.nextSibling;
282 } else {
283 node.previousSibling.nextSibling = node.nextSibling;
284 }
285
286 if (node.nextSibling == null) {
287 keyList.tail = node.previousSibling;
288 } else {
289 node.nextSibling.previousSibling = node.previousSibling;
290 }
291 }
292 size--;
293 }
294
295 /** Removes all nodes for the specified key. */
296 private void removeAllNodes(@Nullable Object key) {
297 Iterators.clear(new ValueForKeyIterator(key));
298 }
299
300 /** Helper method for verifying that an iterator element is present. */
301 private static void checkElement(@Nullable Object node) {
302 if (node == null) {
303 throw new NoSuchElementException();
304 }
305 }
306
307 /** An {@code Iterator} over all nodes. */
308 private class NodeIterator implements ListIterator<Entry<K, V>> {
309 int nextIndex;
310 @Nullable Node<K, V> next;
311 @Nullable Node<K, V> current;
312 @Nullable Node<K, V> previous;
313 int expectedModCount = modCount;
314
315 NodeIterator(int index) {
316 int size = size();
317 checkPositionIndex(index, size);
318 if (index >= (size / 2)) {
319 previous = tail;
320 nextIndex = size;
321 while (index++ < size) {
322 previous();
323 }
324 } else {
325 next = head;
326 while (index-- > 0) {
327 next();
328 }
329 }
330 current = null;
331 }
332
333 private void checkForConcurrentModification() {
334 if (modCount != expectedModCount) {
335 throw new ConcurrentModificationException();
336 }
337 }
338
339 @Override
340 public boolean hasNext() {
341 checkForConcurrentModification();
342 return next != null;
343 }
344
345 @CanIgnoreReturnValue
346 @Override
347 public Node<K, V> next() {
348 checkForConcurrentModification();
349 checkElement(next);
350 previous = current = next;
351 next = next.next;
352 nextIndex++;
353 return current;
354 }
355
356 @Override
357 public void remove() {
358 checkForConcurrentModification();
359 checkRemove(current != null);
360 if (current != next) { // after call to next()
361 previous = current.previous;
362 nextIndex--;
363 } else { // after call to previous()
364 next = current.next;
365 }
366 removeNode(current);
367 current = null;
368 expectedModCount = modCount;
369 }
370
371 @Override
372 public boolean hasPrevious() {
373 checkForConcurrentModification();
374 return previous != null;
375 }
376
377 @CanIgnoreReturnValue
378 @Override
379 public Node<K, V> previous() {
380 checkForConcurrentModification();
381 checkElement(previous);
382 next = current = previous;
383 previous = previous.previous;
384 nextIndex--;
385 return current;
386 }
387
388 @Override
389 public int nextIndex() {
390 return nextIndex;
391 }
392
393 @Override
394 public int previousIndex() {
395 return nextIndex - 1;
396 }
397
398 @Override
399 public void set(Entry<K, V> e) {
400 throw new UnsupportedOperationException();
401 }
402
403 @Override
404 public void add(Entry<K, V> e) {
405 throw new UnsupportedOperationException();
406 }
407
408 void setValue(V value) {
409 checkState(current != null);
410 current.value = value;
411 }
412 }
413
414 /** An {@code Iterator} over distinct keys in key head order. */
415 private class DistinctKeyIterator implements Iterator<K> {
416 final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size());
417 Node<K, V> next = head;
418 @Nullable Node<K, V> current;
419 int expectedModCount = modCount;
420
421 private void checkForConcurrentModification() {
422 if (modCount != expectedModCount) {
423 throw new ConcurrentModificationException();
424 }
425 }
426
427 @Override
428 public boolean hasNext() {
429 checkForConcurrentModification();
430 return next != null;
431 }
432
433 @Override
434 public K next() {
435 checkForConcurrentModification();
436 checkElement(next);
437 current = next;
438 seenKeys.add(current.key);
439 do { // skip ahead to next unseen key
440 next = next.next;
441 } while ((next != null) && !seenKeys.add(next.key));
442 return current.key;
443 }
444
445 @Override
446 public void remove() {
447 checkForConcurrentModification();
448 checkRemove(current != null);
449 removeAllNodes(current.key);
450 current = null;
451 expectedModCount = modCount;
452 }
453 }
454
455 /** A {@code ListIterator} over values for a specified key. */
456 private class ValueForKeyIterator implements ListIterator<V> {
457 final @Nullable Object key;
458 int nextIndex;
459 @Nullable Node<K, V> next;
460 @Nullable Node<K, V> current;
461 @Nullable Node<K, V> previous;
462
463 /** Constructs a new iterator over all values for the specified key. */
464 ValueForKeyIterator(@Nullable Object key) {
465 this.key = key;
466 KeyList<K, V> keyList = keyToKeyList.get(key);
467 next = (keyList == null) ? null : keyList.head;
468 }
469
470 /**
471 * Constructs a new iterator over all values for the specified key starting at the specified
472 * index. This constructor is optimized so that it starts at either the head or the tail,
473 * depending on which is closer to the specified index. This allows adds to the tail to be done
474 * in constant time.
475 *
476 * @throws IndexOutOfBoundsException if index is invalid
477 */
478 public ValueForKeyIterator(@Nullable Object key, int index) {
479 KeyList<K, V> keyList = keyToKeyList.get(key);
480 int size = (keyList == null) ? 0 : keyList.count;
481 checkPositionIndex(index, size);
482 if (index >= (size / 2)) {
483 previous = (keyList == null) ? null : keyList.tail;
484 nextIndex = size;
485 while (index++ < size) {
486 previous();
487 }
488 } else {
489 next = (keyList == null) ? null : keyList.head;
490 while (index-- > 0) {
491 next();
492 }
493 }
494 this.key = key;
495 current = null;
496 }
497
498 @Override
499 public boolean hasNext() {
500 return next != null;
501 }
502
503 @CanIgnoreReturnValue
504 @Override
505 public V next() {
506 checkElement(next);
507 previous = current = next;
508 next = next.nextSibling;
509 nextIndex++;
510 return current.value;
511 }
512
513 @Override
514 public boolean hasPrevious() {
515 return previous != null;
516 }
517
518 @CanIgnoreReturnValue
519 @Override
520 public V previous() {
521 checkElement(previous);
522 next = current = previous;
523 previous = previous.previousSibling;
524 nextIndex--;
525 return current.value;
526 }
527
528 @Override
529 public int nextIndex() {
530 return nextIndex;
531 }
532
533 @Override
534 public int previousIndex() {
535 return nextIndex - 1;
536 }
537
538 @Override
539 public void remove() {
540 checkRemove(current != null);
541 if (current != next) { // after call to next()
542 previous = current.previousSibling;
543 nextIndex--;
544 } else { // after call to previous()
545 next = current.nextSibling;
546 }
547 removeNode(current);
548 current = null;
549 }
550
551 @Override
552 public void set(V value) {
553 checkState(current != null);
554 current.value = value;
555 }
556
557 @Override
558 @SuppressWarnings("unchecked")
559 public void add(V value) {
560 previous = addNode((K) key, value, next);
561 nextIndex++;
562 current = null;
563 }
564 }
565
566 // Query Operations
567
568 @Override
569 public int size() {
570 return size;
571 }
572
573 @Override
574 public boolean isEmpty() {
575 return head == null;
576 }
577
578 @Override
579 public boolean containsKey(@Nullable Object key) {
580 return keyToKeyList.containsKey(key);
581 }
582
583 @Override
584 public boolean containsValue(@Nullable Object value) {
585 return values().contains(value);
586 }
587
588 // Modification Operations
589
590 /**
591 * Stores a key-value pair in the multimap.
592 *
593 * @param key key to store in the multimap
594 * @param value value to store in the multimap
595 * @return {@code true} always
596 */
597 @CanIgnoreReturnValue
598 @Override
599 public boolean put(@Nullable K key, @Nullable V value) {
600 addNode(key, value, null);
601 return true;
602 }
603
604 // Bulk Operations
605
606 /**
607 * {@inheritDoc}
608 *
609 * <p>If any entries for the specified {@code key} already exist in the multimap, their values are
610 * changed in-place without affecting the iteration order.
611 *
612 * <p>The returned list is immutable and implements {@link java.util.RandomAccess}.
613 */
614 @CanIgnoreReturnValue
615 @Override
616 public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
617 List<V> oldValues = getCopy(key);
618 ListIterator<V> keyValues = new ValueForKeyIterator(key);
619 Iterator<? extends V> newValues = values.iterator();
620
621 // Replace existing values, if any.
622 while (keyValues.hasNext() && newValues.hasNext()) {
623 keyValues.next();
624 keyValues.set(newValues.next());
625 }
626
627 // Remove remaining old values, if any.
628 while (keyValues.hasNext()) {
629 keyValues.next();
630 keyValues.remove();
631 }
632
633 // Add remaining new values, if any.
634 while (newValues.hasNext()) {
635 keyValues.add(newValues.next());
636 }
637
638 return oldValues;
639 }
640
641 private List<V> getCopy(@Nullable Object key) {
642 return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key)));
643 }
644
645 /**
646 * {@inheritDoc}
647 *
648 * <p>The returned list is immutable and implements {@link java.util.RandomAccess}.
649 */
650 @CanIgnoreReturnValue
651 @Override
652 public List<V> removeAll(@Nullable Object key) {
653 List<V> oldValues = getCopy(key);
654 removeAllNodes(key);
655 return oldValues;
656 }
657
658 @Override
659 public void clear() {
660 head = null;
661 tail = null;
662 keyToKeyList.clear();
663 size = 0;
664 modCount++;
665 }
666
667 // Views
668
669 /**
670 * {@inheritDoc}
671 *
672 * <p>If the multimap is modified while an iteration over the list is in progress (except through
673 * the iterator's own {@code add}, {@code set} or {@code remove} operations) the results of the
674 * iteration are undefined.
675 *
676 * <p>The returned list is not serializable and does not have random access.
677 */
678 @Override
679 public List<V> get(final @Nullable K key) {
680 return new AbstractSequentialList<V>() {
681 @Override
682 public int size() {
683 KeyList<K, V> keyList = keyToKeyList.get(key);
684 return (keyList == null) ? 0 : keyList.count;
685 }
686
687 @Override
688 public ListIterator<V> listIterator(int index) {
689 return new ValueForKeyIterator(key, index);
690 }
691 };
692 }
693
694 @Override
695 Set<K> createKeySet() {
696 @WeakOuter
697 class KeySetImpl extends Sets.ImprovedAbstractSet<K> {
698 @Override
699 public int size() {
700 return keyToKeyList.size();
701 }
702
703 @Override
704 public Iterator<K> iterator() {
705 return new DistinctKeyIterator();
706 }
707
708 @Override
709 public boolean contains(Object key) { // for performance
710 return containsKey(key);
711 }
712
713 @Override
714 public boolean remove(Object o) { // for performance
715 return !LinkedListMultimap.this.removeAll(o).isEmpty();
716 }
717 }
718 return new KeySetImpl();
719 }
720
721 @Override
722 Multiset<K> createKeys() {
723 return new Multimaps.Keys<K, V>(this);
724 }
725
726 /**
727 * {@inheritDoc}
728 *
729 * <p>The iterator generated by the returned collection traverses the values in the order they
730 * were added to the multimap. Because the values may have duplicates and follow the insertion
731 * ordering, this method returns a {@link List}, instead of the {@link Collection} specified in
732 * the {@link ListMultimap} interface.
733 */
734 @Override
735 public List<V> values() {
736 return (List<V>) super.values();
737 }
738
739 @Override
740 List<V> createValues() {
741 @WeakOuter
742 class ValuesImpl extends AbstractSequentialList<V> {
743 @Override
744 public int size() {
745 return size;
746 }
747
748 @Override
749 public ListIterator<V> listIterator(int index) {
750 final NodeIterator nodeItr = new NodeIterator(index);
751 return new TransformedListIterator<Entry<K, V>, V>(nodeItr) {
752 @Override
753 V transform(Entry<K, V> entry) {
754 return entry.getValue();
755 }
756
757 @Override
758 public void set(V value) {
759 nodeItr.setValue(value);
760 }
761 };
762 }
763 }
764 return new ValuesImpl();
765 }
766
767 /**
768 * {@inheritDoc}
769 *
770 * <p>The iterator generated by the returned collection traverses the entries in the order they
771 * were added to the multimap. Because the entries may have duplicates and follow the insertion
772 * ordering, this method returns a {@link List}, instead of the {@link Collection} specified in
773 * the {@link ListMultimap} interface.
774 *
775 * <p>An entry's {@link Entry#getKey} method always returns the same key, regardless of what
776 * happens subsequently. As long as the corresponding key-value mapping is not removed from the
777 * multimap, {@link Entry#getValue} returns the value from the multimap, which may change over
778 * time, and {@link Entry#setValue} modifies that value. Removing the mapping from the multimap
779 * does not alter the value returned by {@code getValue()}, though a subsequent {@code setValue()}
780 * call won't update the multimap but will lead to a revised value being returned by {@code
781 * getValue()}.
782 */
783 @Override
784 public List<Entry<K, V>> entries() {
785 return (List<Entry<K, V>>) super.entries();
786 }
787
788 @Override
789 List<Entry<K, V>> createEntries() {
790 @WeakOuter
791 class EntriesImpl extends AbstractSequentialList<Entry<K, V>> {
792 @Override
793 public int size() {
794 return size;
795 }
796
797 @Override
798 public ListIterator<Entry<K, V>> listIterator(int index) {
799 return new NodeIterator(index);
800 }
801
802 @Override
803 public void forEach(Consumer<? super Entry<K, V>> action) {
804 checkNotNull(action);
805 for (Node<K, V> node = head; node != null; node = node.next) {
806 action.accept(node);
807 }
808 }
809 }
810 return new EntriesImpl();
811 }
812
813 @Override
814 Iterator<Entry<K, V>> entryIterator() {
815 throw new AssertionError("should never be called");
816 }
817
818 @Override
819 Map<K, Collection<V>> createAsMap() {
820 return new Multimaps.AsMap<>(this);
821 }
822
823 /**
824 * @serialData the number of distinct keys, and then for each distinct key: the first key, the
825 * number of values for that key, and the key's values, followed by successive keys and values
826 * from the entries() ordering
827 */
828 @GwtIncompatible // java.io.ObjectOutputStream
829 private void writeObject(ObjectOutputStream stream) throws IOException {
830 stream.defaultWriteObject();
831 stream.writeInt(size());
832 for (Entry<K, V> entry : entries()) {
833 stream.writeObject(entry.getKey());
834 stream.writeObject(entry.getValue());
835 }
836 }
837
838 @GwtIncompatible // java.io.ObjectInputStream
839 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
840 stream.defaultReadObject();
841 keyToKeyList = Maps.newLinkedHashMap();
842 int size = stream.readInt();
843 for (int i = 0; i < size; i++) {
844 @SuppressWarnings("unchecked") // reading data stored by writeObject
845 K key = (K) stream.readObject();
846 @SuppressWarnings("unchecked") // reading data stored by writeObject
847 V value = (V) stream.readObject();
848 put(key, value);
849 }
850 }
851
852 @GwtIncompatible // java serialization not supported
853 private static final long serialVersionUID = 0;
854 }