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