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