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