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