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.checkPositionIndex;
020import static com.google.common.base.Preconditions.checkState;
021import static com.google.common.collect.CollectPreconditions.checkRemove;
022import static java.util.Collections.unmodifiableList;
023
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import com.google.j2objc.annotations.WeakOuter;
028import java.io.IOException;
029import java.io.ObjectInputStream;
030import java.io.ObjectOutputStream;
031import java.io.Serializable;
032import java.util.AbstractSequentialList;
033import java.util.Collection;
034import java.util.ConcurrentModificationException;
035import java.util.HashMap;
036import java.util.Iterator;
037import java.util.List;
038import java.util.ListIterator;
039import java.util.Map;
040import java.util.Map.Entry;
041import java.util.NoSuchElementException;
042import java.util.Set;
043import org.checkerframework.checker.nullness.compatqual.NullableDecl;
044
045/**
046 * An implementation of {@code ListMultimap} that supports deterministic iteration order for both
047 * keys and values. The iteration order is preserved across non-distinct key values. For example,
048 * for the following multimap definition:
049 *
050 * <pre>{@code
051 * Multimap<K, V> multimap = LinkedListMultimap.create();
052 * multimap.put(key1, foo);
053 * multimap.put(key2, bar);
054 * multimap.put(key1, baz);
055 * }</pre>
056 *
057 * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, and similarly for
058 * {@link #entries()}. Unlike {@link LinkedHashMultimap}, the iteration order is kept consistent
059 * between keys, entries and values. For example, calling:
060 *
061 * <pre>{@code
062 * map.remove(key1, foo);
063 * }</pre>
064 *
065 * <p>changes the entries iteration order to {@code [key2=bar, key1=baz]} and the key iteration
066 * order to {@code [key2, key1]}. The {@link #entries()} iterator returns mutable map entries, and
067 * {@link #replaceValues} attempts to preserve iteration order as much as possible.
068 *
069 * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate through the keys in
070 * the order they were first added to the multimap. Similarly, {@link #get}, {@link #removeAll}, and
071 * {@link #replaceValues} return collections that iterate through the values in the order they were
072 * added. The collections generated by {@link #entries()}, {@link #keys()}, and {@link #values}
073 * iterate across the key-value mappings in the order they were added to the multimap.
074 *
075 * <p>The {@link #values()} and {@link #entries()} methods both return a {@code List}, instead of
076 * the {@code Collection} specified by the {@link ListMultimap} interface.
077 *
078 * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()}, {@link #values}, {@link
079 * #entries()}, and {@link #asMap} return collections that are views of the multimap. If the
080 * multimap is modified while an iteration over any of those collections is in progress, except
081 * through the iterator's methods, the results of the iteration are undefined.
082 *
083 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
084 * views are modifiable.
085 *
086 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
087 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
088 * with a call to {@link Multimaps#synchronizedListMultimap}.
089 *
090 * <p>See the Guava User Guide article on <a href=
091 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap"> {@code
092 * Multimap}</a>.
093 *
094 * @author Mike Bostock
095 * @since 2.0
096 */
097@GwtCompatible(serializable = true, emulated = true)
098public class LinkedListMultimap<K, V> extends AbstractMultimap<K, V>
099    implements ListMultimap<K, V>, Serializable {
100  /*
101   * Order is maintained using a linked list containing all key-value pairs. In
102   * addition, a series of disjoint linked lists of "siblings", each containing
103   * the values for a specific key, is used to implement {@link
104   * ValueForKeyIterator} in constant time.
105   */
106
107  private static final class Node<K, V> extends AbstractMapEntry<K, V> {
108    @NullableDecl final K key;
109    @NullableDecl V value;
110    @NullableDecl Node<K, V> next; // the next node (with any key)
111    @NullableDecl Node<K, V> previous; // the previous node (with any key)
112    @NullableDecl Node<K, V> nextSibling; // the next node with the same key
113    @NullableDecl Node<K, V> previousSibling; // the previous node with the same key
114
115    Node(@NullableDecl K key, @NullableDecl V value) {
116      this.key = key;
117      this.value = value;
118    }
119
120    @Override
121    public K getKey() {
122      return key;
123    }
124
125    @Override
126    public V getValue() {
127      return value;
128    }
129
130    @Override
131    public V setValue(@NullableDecl V newValue) {
132      V result = value;
133      this.value = newValue;
134      return result;
135    }
136  }
137
138  private static class KeyList<K, V> {
139    Node<K, V> head;
140    Node<K, V> tail;
141    int count;
142
143    KeyList(Node<K, V> firstNode) {
144      this.head = firstNode;
145      this.tail = firstNode;
146      firstNode.previousSibling = null;
147      firstNode.nextSibling = null;
148      this.count = 1;
149    }
150  }
151
152  @NullableDecl private transient Node<K, V> head; // the head for all keys
153  @NullableDecl private transient Node<K, V> tail; // the tail for all keys
154  private transient Map<K, KeyList<K, V>> keyToKeyList;
155  private transient int size;
156
157  /*
158   * Tracks modifications to keyToKeyList so that addition or removal of keys invalidates
159   * preexisting iterators. This does *not* track simple additions and removals of values
160   * that are not the first to be added or last to be removed for their key.
161   */
162  private transient int modCount;
163
164  /** Creates a new, empty {@code LinkedListMultimap} with the default initial capacity. */
165  public static <K, V> LinkedListMultimap<K, V> create() {
166    return new LinkedListMultimap<>();
167  }
168
169  /**
170   * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold the specified
171   * number of keys without rehashing.
172   *
173   * @param expectedKeys the expected number of distinct keys
174   * @throws IllegalArgumentException if {@code expectedKeys} is negative
175   */
176  public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) {
177    return new LinkedListMultimap<>(expectedKeys);
178  }
179
180  /**
181   * Constructs a {@code LinkedListMultimap} with the same mappings as the specified {@code
182   * Multimap}. The new multimap has the same {@link Multimap#entries()} iteration order as the
183   * input multimap.
184   *
185   * @param multimap the multimap whose contents are copied to this multimap
186   */
187  public static <K, V> LinkedListMultimap<K, V> create(
188      Multimap<? extends K, ? extends V> multimap) {
189    return new LinkedListMultimap<>(multimap);
190  }
191
192  LinkedListMultimap() {
193    this(12);
194  }
195
196  private LinkedListMultimap(int expectedKeys) {
197    keyToKeyList = Platform.newHashMapWithExpectedSize(expectedKeys);
198  }
199
200  private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
201    this(multimap.keySet().size());
202    putAll(multimap);
203  }
204
205  /**
206   * Adds a new node for the specified key-value pair before the specified {@code nextSibling}
207   * element, or at the end of the list if {@code nextSibling} is null. Note: if {@code nextSibling}
208   * is specified, it MUST be for an node for the same {@code key}!
209   */
210  @CanIgnoreReturnValue
211  private Node<K, V> addNode(
212      @NullableDecl K key, @NullableDecl V value, @NullableDecl 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(@NullableDecl 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(@NullableDecl 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    @NullableDecl Node<K, V> next;
311    @NullableDecl Node<K, V> current;
312    @NullableDecl 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    @NullableDecl 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    @NullableDecl final Object key;
458    int nextIndex;
459    @NullableDecl Node<K, V> next;
460    @NullableDecl Node<K, V> current;
461    @NullableDecl Node<K, V> previous;
462
463    /** Constructs a new iterator over all values for the specified key. */
464    ValueForKeyIterator(@NullableDecl 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(@NullableDecl 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(@NullableDecl Object key) {
580    return keyToKeyList.containsKey(key);
581  }
582
583  @Override
584  public boolean containsValue(@NullableDecl 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(@NullableDecl K key, @NullableDecl 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(@NullableDecl 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(@NullableDecl 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(@NullableDecl 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 @NullableDecl 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    return new EntriesImpl();
803  }
804
805  @Override
806  Iterator<Entry<K, V>> entryIterator() {
807    throw new AssertionError("should never be called");
808  }
809
810  @Override
811  Map<K, Collection<V>> createAsMap() {
812    return new Multimaps.AsMap<>(this);
813  }
814
815  /**
816   * @serialData the number of distinct keys, and then for each distinct key: the first key, the
817   *     number of values for that key, and the key's values, followed by successive keys and values
818   *     from the entries() ordering
819   */
820  @GwtIncompatible // java.io.ObjectOutputStream
821  private void writeObject(ObjectOutputStream stream) throws IOException {
822    stream.defaultWriteObject();
823    stream.writeInt(size());
824    for (Entry<K, V> entry : entries()) {
825      stream.writeObject(entry.getKey());
826      stream.writeObject(entry.getValue());
827    }
828  }
829
830  @GwtIncompatible // java.io.ObjectInputStream
831  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
832    stream.defaultReadObject();
833    keyToKeyList = CompactLinkedHashMap.create();
834    int size = stream.readInt();
835    for (int i = 0; i < size; i++) {
836      @SuppressWarnings("unchecked") // reading data stored by writeObject
837      K key = (K) stream.readObject();
838      @SuppressWarnings("unchecked") // reading data stored by writeObject
839      V value = (V) stream.readObject();
840      put(key, value);
841    }
842  }
843
844  @GwtIncompatible // java serialization not supported
845  private static final long serialVersionUID = 0;
846}