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