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