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