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