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
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.base.Preconditions.checkPositionIndex;
021import static com.google.common.base.Preconditions.checkState;
022import static com.google.common.collect.CollectPreconditions.checkRemove;
023import static java.util.Collections.unmodifiableList;
024
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.errorprone.annotations.CanIgnoreReturnValue;
028import com.google.j2objc.annotations.WeakOuter;
029import java.io.IOException;
030import java.io.ObjectInputStream;
031import java.io.ObjectOutputStream;
032import java.io.Serializable;
033import java.util.AbstractSequentialList;
034import java.util.Collection;
035import java.util.ConcurrentModificationException;
036import java.util.HashMap;
037import java.util.Iterator;
038import java.util.List;
039import java.util.ListIterator;
040import java.util.Map;
041import java.util.Map.Entry;
042import java.util.NoSuchElementException;
043import java.util.Set;
044import java.util.function.Consumer;
045import javax.annotation.Nullable;
046
047/**
048 * An implementation of {@code ListMultimap} that supports deterministic
049 * iteration order for both keys and values. The iteration order is preserved
050 * across non-distinct key values. For example, for the following multimap
051 * definition: <pre>   {@code
052 *
053 *   Multimap<K, V> multimap = LinkedListMultimap.create();
054 *   multimap.put(key1, foo);
055 *   multimap.put(key2, bar);
056 *   multimap.put(key1, baz);}</pre>
057 *
058 * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]},
059 * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the
060 * iteration order is kept consistent between keys, entries and values. For
061 * example, calling: <pre>   {@code
062 *
063 *   map.remove(key1, foo);}</pre>
064 *
065 * <p>changes the entries iteration order to {@code [key2=bar, key1=baz]} and the
066 * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator
067 * returns mutable map entries, and {@link #replaceValues} attempts to preserve
068 * iteration order as much as possible.
069 *
070 * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate
071 * through the keys in the order they were first added to the multimap.
072 * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues}
073 * return collections that iterate through the values in the order they were
074 * added. The collections generated by {@link #entries()}, {@link #keys()}, and
075 * {@link #values} iterate across the key-value mappings in the order they were
076 * added to the multimap.
077 *
078 * <p>The {@link #values()} and {@link #entries()} methods both return a
079 * {@code List}, instead of the {@code Collection} specified by the {@link
080 * ListMultimap} interface.
081 *
082 * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()},
083 * {@link #values}, {@link #entries()}, and {@link #asMap} return collections
084 * that are views of the multimap. If the multimap is modified while an
085 * iteration over any of those collections is in progress, except through the
086 * iterator's methods, the results of the iteration are undefined.
087 *
088 * <p>Keys and values may be null. All optional multimap methods are supported,
089 * and all returned views are modifiable.
090 *
091 * <p>This class is not threadsafe when any concurrent operations update the
092 * multimap. Concurrent read operations will work correctly. To allow concurrent
093 * update operations, wrap your multimap with a call to {@link
094 * Multimaps#synchronizedListMultimap}.
095 *
096 * <p>See the Guava User Guide article on <a href=
097 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">
098 * {@code Multimap}</a>.
099 *
100 * @author Mike Bostock
101 * @since 2.0
102 */
103@GwtCompatible(serializable = true, emulated = true)
104public 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<K, V>();
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<K, V>(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<K, V>(multimap);
199  }
200
201  LinkedListMultimap() {
202    keyToKeyList = Maps.newHashMap();
203  }
204
205  private LinkedListMultimap(int expectedKeys) {
206    keyToKeyList = new HashMap<K, KeyList<K, V>>(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<K, V>(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<K, V>(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<K, V>(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}