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.checkArgument;
020import static com.google.common.base.Preconditions.checkState;
021import static java.util.Collections.unmodifiableList;
022
023import com.google.common.annotations.GwtCompatible;
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.base.Objects;
026import com.google.common.base.Preconditions;
027
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.Iterator;
035import java.util.List;
036import java.util.ListIterator;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.NoSuchElementException;
040import java.util.Set;
041
042import javax.annotation.Nullable;
043
044/**
045 * An implementation of {@code ListMultimap} that supports deterministic
046 * iteration order for both keys and values. The iteration order is preserved
047 * across non-distinct key values. For example, for the following multimap
048 * definition: <pre>   {@code
049 *
050 *   Multimap<K, V> multimap = LinkedListMultimap.create();
051 *   multimap.put(key1, foo);
052 *   multimap.put(key2, bar);
053 *   multimap.put(key1, baz);}</pre>
054 *
055 * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]},
056 * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the
057 * iteration order is kept consistent between keys, entries and values. For
058 * example, calling: <pre>   {@code
059 *
060 *   map.remove(key1, foo);}</pre>
061 *
062 * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the
063 * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator
064 * returns mutable map entries, and {@link #replaceValues} attempts to preserve
065 * iteration order as much as possible.
066 *
067 * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate
068 * through the keys in the order they were first added to the multimap.
069 * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues}
070 * return collections that iterate through the values in the order they were
071 * added. The collections generated by {@link #entries()}, {@link #keys()}, and
072 * {@link #values} iterate across the key-value mappings in the order they were
073 * added to the multimap.
074 *
075 * <p>The {@link #values()} and {@link #entries()} methods both return a
076 * {@code List}, instead of the {@code Collection} specified by the {@link
077 * ListMultimap} interface.
078 *
079 * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()},
080 * {@link #values}, {@link #entries()}, and {@link #asMap} return collections
081 * that are views of the multimap. If the multimap is modified while an
082 * iteration over any of those collections is in progress, except through the
083 * 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,
086 * and all returned views are modifiable.
087 *
088 * <p>This class is not threadsafe when any concurrent operations update the
089 * multimap. Concurrent read operations will work correctly. To allow concurrent
090 * update operations, wrap your multimap with a call to {@link
091 * Multimaps#synchronizedListMultimap}.
092 *
093 * <p>See the Guava User Guide article on <a href=
094 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
095 * {@code Multimap}</a>.
096 *
097 * @author Mike Bostock
098 * @since 2.0 (imported from Google Collections Library)
099 */
100@GwtCompatible(serializable = true, emulated = true)
101public class LinkedListMultimap<K, V>
102    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  private static final class Node<K, V> {
111    final K key;
112    V value;
113    Node<K, V> next; // the next node (with any key)
114    Node<K, V> previous; // the previous node (with any key)
115    Node<K, V> nextSibling; // the next node with the same key
116    Node<K, V> previousSibling; // the previous node with the same key
117
118    Node(@Nullable K key, @Nullable V value) {
119      this.key = key;
120      this.value = value;
121    }
122
123    @Override public String toString() {
124      return key + "=" + value;
125    }
126  }
127
128  private transient Node<K, V> head; // the head for all keys
129  private transient Node<K, V> tail; // the tail for all keys
130  private transient Multiset<K> keyCount; // the number of values for each key
131  private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key
132  private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key
133
134  /**
135   * Creates a new, empty {@code LinkedListMultimap} with the default initial
136   * capacity.
137   */
138  public static <K, V> LinkedListMultimap<K, V> create() {
139    return new LinkedListMultimap<K, V>();
140  }
141
142  /**
143   * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold
144   * the specified number of keys without rehashing.
145   *
146   * @param expectedKeys the expected number of distinct keys
147   * @throws IllegalArgumentException if {@code expectedKeys} is negative
148   */
149  public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) {
150    return new LinkedListMultimap<K, V>(expectedKeys);
151  }
152
153  /**
154   * Constructs a {@code LinkedListMultimap} with the same mappings as the
155   * specified {@code Multimap}. The new multimap has the same
156   * {@link Multimap#entries()} iteration order as the input multimap.
157   *
158   * @param multimap the multimap whose contents are copied to this multimap
159   */
160  public static <K, V> LinkedListMultimap<K, V> create(
161      Multimap<? extends K, ? extends V> multimap) {
162    return new LinkedListMultimap<K, V>(multimap);
163  }
164
165  LinkedListMultimap() {
166    keyCount = LinkedHashMultiset.create();
167    keyToKeyHead = Maps.newHashMap();
168    keyToKeyTail = Maps.newHashMap();
169  }
170
171  private LinkedListMultimap(int expectedKeys) {
172    keyCount = LinkedHashMultiset.create(expectedKeys);
173    keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys);
174    keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys);
175  }
176
177  private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
178    this(multimap.keySet().size());
179    putAll(multimap);
180  }
181
182  /**
183   * Adds a new node for the specified key-value pair before the specified
184   * {@code nextSibling} element, or at the end of the list if {@code
185   * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be
186   * for an node for the same {@code key}!
187   */
188  private Node<K, V> addNode(
189      @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) {
190    Node<K, V> node = new Node<K, V>(key, value);
191    if (head == null) { // empty list
192      head = tail = node;
193      keyToKeyHead.put(key, node);
194      keyToKeyTail.put(key, node);
195    } else if (nextSibling == null) { // non-empty list, add to tail
196      tail.next = node;
197      node.previous = tail;
198      Node<K, V> keyTail = keyToKeyTail.get(key);
199      if (keyTail == null) { // first for this key
200        keyToKeyHead.put(key, node);
201      } else {
202        keyTail.nextSibling = node;
203        node.previousSibling = keyTail;
204      }
205      keyToKeyTail.put(key, node);
206      tail = node;
207    } else { // non-empty list, insert before nextSibling
208      node.previous = nextSibling.previous;
209      node.previousSibling = nextSibling.previousSibling;
210      node.next = nextSibling;
211      node.nextSibling = nextSibling;
212      if (nextSibling.previousSibling == null) { // nextSibling was key head
213        keyToKeyHead.put(key, node);
214      } else {
215        nextSibling.previousSibling.nextSibling = node;
216      }
217      if (nextSibling.previous == null) { // nextSibling was head
218        head = node;
219      } else {
220        nextSibling.previous.next = node;
221      }
222      nextSibling.previous = node;
223      nextSibling.previousSibling = node;
224    }
225    keyCount.add(key);
226    return node;
227  }
228
229  /**
230   * Removes the specified node from the linked list. This method is only
231   * intended to be used from the {@code Iterator} classes. See also {@link
232   * LinkedListMultimap#removeAllNodes(Object)}.
233   */
234  private void removeNode(Node<K, V> node) {
235    if (node.previous != null) {
236      node.previous.next = node.next;
237    } else { // node was head
238      head = node.next;
239    }
240    if (node.next != null) {
241      node.next.previous = node.previous;
242    } else { // node was tail
243      tail = node.previous;
244    }
245    if (node.previousSibling != null) {
246      node.previousSibling.nextSibling = node.nextSibling;
247    } else if (node.nextSibling != null) { // node was key head
248      keyToKeyHead.put(node.key, node.nextSibling);
249    } else {
250      keyToKeyHead.remove(node.key); // don't leak a key-null entry
251    }
252    if (node.nextSibling != null) {
253      node.nextSibling.previousSibling = node.previousSibling;
254    } else if (node.previousSibling != null) { // node was key tail
255      keyToKeyTail.put(node.key, node.previousSibling);
256    } else {
257      keyToKeyTail.remove(node.key); // don't leak a key-null entry
258    }
259    keyCount.remove(node.key);
260  }
261
262  /** Removes all nodes for the specified key. */
263  private void removeAllNodes(@Nullable Object key) {
264    for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) {
265      i.next();
266      i.remove();
267    }
268  }
269
270  /** Helper method for verifying that an iterator element is present. */
271  private static void checkElement(@Nullable Object node) {
272    if (node == null) {
273      throw new NoSuchElementException();
274    }
275  }
276
277  /** An {@code Iterator} over all nodes. */
278  private class NodeIterator implements ListIterator<Node<K, V>> {
279    int nextIndex;
280    Node<K, V> next;
281    Node<K, V> current;
282    Node<K, V> previous;
283
284    NodeIterator() {
285      next = head;
286    }
287    NodeIterator(int index) {
288      int size = size();
289      Preconditions.checkPositionIndex(index, size);
290      if (index >= (size / 2)) {
291        previous = tail;
292        nextIndex = size;
293        while (index++ < size) {
294          previous();
295        }
296      } else {
297        next = head;
298        while (index-- > 0) {
299          next();
300        }
301      }
302      current = null;
303    }
304    @Override
305    public boolean hasNext() {
306      return next != null;
307    }
308    @Override
309    public Node<K, V> next() {
310      checkElement(next);
311      previous = current = next;
312      next = next.next;
313      nextIndex++;
314      return current;
315    }
316    @Override
317    public void remove() {
318      checkState(current != null);
319      if (current != next) { // after call to next()
320        previous = current.previous;
321        nextIndex--;
322      } else { // after call to previous()
323        next = current.next;
324      }
325      removeNode(current);
326      current = null;
327    }
328    @Override
329    public boolean hasPrevious() {
330      return previous != null;
331    }
332    @Override
333    public Node<K, V> previous() {
334      checkElement(previous);
335      next = current = previous;
336      previous = previous.previous;
337      nextIndex--;
338      return current;
339    }
340    @Override
341    public int nextIndex() {
342      return nextIndex;
343    }
344    @Override
345    public int previousIndex() {
346      return nextIndex - 1;
347    }
348    @Override
349    public void set(Node<K, V> e) {
350      throw new UnsupportedOperationException();
351    }
352    @Override
353    public void add(Node<K, V> e) {
354      throw new UnsupportedOperationException();
355    }
356    void setValue(V value) {
357      checkState(current != null);
358      current.value = value;
359    }
360  }
361
362  /** An {@code Iterator} over distinct keys in key head order. */
363  private class DistinctKeyIterator implements Iterator<K> {
364    final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size());
365    Node<K, V> next = head;
366    Node<K, V> current;
367
368    @Override
369    public boolean hasNext() {
370      return next != null;
371    }
372    @Override
373    public K next() {
374      checkElement(next);
375      current = next;
376      seenKeys.add(current.key);
377      do { // skip ahead to next unseen key
378        next = next.next;
379      } while ((next != null) && !seenKeys.add(next.key));
380      return current.key;
381    }
382    @Override
383    public void remove() {
384      checkState(current != null);
385      removeAllNodes(current.key);
386      current = null;
387    }
388  }
389
390  /** A {@code ListIterator} over values for a specified key. */
391  private class ValueForKeyIterator implements ListIterator<V> {
392    final Object key;
393    int nextIndex;
394    Node<K, V> next;
395    Node<K, V> current;
396    Node<K, V> previous;
397
398    /** Constructs a new iterator over all values for the specified key. */
399    ValueForKeyIterator(@Nullable Object key) {
400      this.key = key;
401      next = keyToKeyHead.get(key);
402    }
403
404    /**
405     * Constructs a new iterator over all values for the specified key starting
406     * at the specified index. This constructor is optimized so that it starts
407     * at either the head or the tail, depending on which is closer to the
408     * specified index. This allows adds to the tail to be done in constant
409     * time.
410     *
411     * @throws IndexOutOfBoundsException if index is invalid
412     */
413    public ValueForKeyIterator(@Nullable Object key, int index) {
414      int size = keyCount.count(key);
415      Preconditions.checkPositionIndex(index, size);
416      if (index >= (size / 2)) {
417        previous = keyToKeyTail.get(key);
418        nextIndex = size;
419        while (index++ < size) {
420          previous();
421        }
422      } else {
423        next = keyToKeyHead.get(key);
424        while (index-- > 0) {
425          next();
426        }
427      }
428      this.key = key;
429      current = null;
430    }
431
432    @Override
433    public boolean hasNext() {
434      return next != null;
435    }
436
437    @Override
438    public V next() {
439      checkElement(next);
440      previous = current = next;
441      next = next.nextSibling;
442      nextIndex++;
443      return current.value;
444    }
445
446    @Override
447    public boolean hasPrevious() {
448      return previous != null;
449    }
450
451    @Override
452    public V previous() {
453      checkElement(previous);
454      next = current = previous;
455      previous = previous.previousSibling;
456      nextIndex--;
457      return current.value;
458    }
459
460    @Override
461    public int nextIndex() {
462      return nextIndex;
463    }
464
465    @Override
466    public int previousIndex() {
467      return nextIndex - 1;
468    }
469
470    @Override
471    public void remove() {
472      checkState(current != null);
473      if (current != next) { // after call to next()
474        previous = current.previousSibling;
475        nextIndex--;
476      } else { // after call to previous()
477        next = current.nextSibling;
478      }
479      removeNode(current);
480      current = null;
481    }
482
483    @Override
484    public void set(V value) {
485      checkState(current != null);
486      current.value = value;
487    }
488
489    @Override
490    @SuppressWarnings("unchecked")
491    public void add(V value) {
492      previous = addNode((K) key, value, next);
493      nextIndex++;
494      current = null;
495    }
496  }
497
498  // Query Operations
499
500  @Override
501  public int size() {
502    return keyCount.size();
503  }
504
505  @Override
506  public boolean isEmpty() {
507    return head == null;
508  }
509
510  @Override
511  public boolean containsKey(@Nullable Object key) {
512    return keyToKeyHead.containsKey(key);
513  }
514
515  @Override
516  public boolean containsValue(@Nullable Object value) {
517    for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) {
518      if (Objects.equal(i.next().value, value)) {
519        return true;
520      }
521    }
522    return false;
523  }
524
525  @Override
526  public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
527    for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) {
528      if (Objects.equal(i.next(), value)) {
529        return true;
530      }
531    }
532    return false;
533  }
534
535  // Modification Operations
536
537  /**
538   * Stores a key-value pair in the multimap.
539   *
540   * @param key key to store in the multimap
541   * @param value value to store in the multimap
542   * @return {@code true} always
543   */
544  @Override
545  public boolean put(@Nullable K key, @Nullable V value) {
546    addNode(key, value, null);
547    return true;
548  }
549
550  @Override
551  public boolean remove(@Nullable Object key, @Nullable Object value) {
552    Iterator<V> values = new ValueForKeyIterator(key);
553    while (values.hasNext()) {
554      if (Objects.equal(values.next(), value)) {
555        values.remove();
556        return true;
557      }
558    }
559    return false;
560  }
561
562  // Bulk Operations
563
564  @Override
565  public boolean putAll(@Nullable K key, Iterable<? extends V> values) {
566    boolean changed = false;
567    for (V value : values) {
568      changed |= put(key, value);
569    }
570    return changed;
571  }
572
573  @Override
574  public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
575    boolean changed = false;
576    for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
577      changed |= put(entry.getKey(), entry.getValue());
578    }
579    return changed;
580  }
581
582  /**
583   * {@inheritDoc}
584   *
585   * <p>If any entries for the specified {@code key} already exist in the
586   * multimap, their values are changed in-place without affecting the iteration
587   * order.
588   *
589   * <p>The returned list is immutable and implements
590   * {@link java.util.RandomAccess}.
591   */
592  @Override
593  public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
594    List<V> oldValues = getCopy(key);
595    ListIterator<V> keyValues = new ValueForKeyIterator(key);
596    Iterator<? extends V> newValues = values.iterator();
597
598    // Replace existing values, if any.
599    while (keyValues.hasNext() && newValues.hasNext()) {
600      keyValues.next();
601      keyValues.set(newValues.next());
602    }
603
604    // Remove remaining old values, if any.
605    while (keyValues.hasNext()) {
606      keyValues.next();
607      keyValues.remove();
608    }
609
610    // Add remaining new values, if any.
611    while (newValues.hasNext()) {
612      keyValues.add(newValues.next());
613    }
614
615    return oldValues;
616  }
617
618  private List<V> getCopy(@Nullable Object key) {
619    return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key)));
620  }
621
622  /**
623   * {@inheritDoc}
624   *
625   * <p>The returned list is immutable and implements
626   * {@link java.util.RandomAccess}.
627   */
628  @Override
629  public List<V> removeAll(@Nullable Object key) {
630    List<V> oldValues = getCopy(key);
631    removeAllNodes(key);
632    return oldValues;
633  }
634
635  @Override
636  public void clear() {
637    head = null;
638    tail = null;
639    keyCount.clear();
640    keyToKeyHead.clear();
641    keyToKeyTail.clear();
642  }
643
644  // Views
645
646  /**
647   * {@inheritDoc}
648   *
649   * <p>If the multimap is modified while an iteration over the list is in
650   * progress (except through the iterator's own {@code add}, {@code set} or
651   * {@code remove} operations) the results of the iteration are undefined.
652   *
653   * <p>The returned list is not serializable and does not have random access.
654   */
655  @Override
656  public List<V> get(final @Nullable K key) {
657    return new AbstractSequentialList<V>() {
658      @Override public int size() {
659        return keyCount.count(key);
660      }
661      @Override public ListIterator<V> listIterator(int index) {
662        return new ValueForKeyIterator(key, index);
663      }
664      @Override public boolean removeAll(Collection<?> c) {
665        return Iterators.removeAll(iterator(), c);
666      }
667      @Override public boolean retainAll(Collection<?> c) {
668        return Iterators.retainAll(iterator(), c);
669      }
670    };
671  }
672
673  private transient Set<K> keySet;
674
675  @Override
676  public Set<K> keySet() {
677    Set<K> result = keySet;
678    if (result == null) {
679      keySet = result = new Sets.ImprovedAbstractSet<K>() {
680        @Override public int size() {
681          return keyCount.elementSet().size();
682        }
683        @Override public Iterator<K> iterator() {
684          return new DistinctKeyIterator();
685        }
686        @Override public boolean contains(Object key) { // for performance
687          return containsKey(key);
688        }
689        @Override
690        public boolean remove(Object o) { // for performance
691          return !LinkedListMultimap.this.removeAll(o).isEmpty();
692        }
693      };
694    }
695    return result;
696  }
697
698  private transient Multiset<K> keys;
699
700  @Override
701  public Multiset<K> keys() {
702    Multiset<K> result = keys;
703    if (result == null) {
704      keys = result = new MultisetView();
705    }
706    return result;
707  }
708
709  private class MultisetView extends AbstractMultiset<K> {
710    @Override
711    public int size() {
712      return keyCount.size();
713    }
714
715    @Override
716    public int count(Object element) {
717      return keyCount.count(element);
718    }
719
720    @Override
721    Iterator<Entry<K>> entryIterator() {
722      return new TransformedIterator<K, Entry<K>>(new DistinctKeyIterator()) {
723        @Override
724        Entry<K> transform(final K key) {
725          return new Multisets.AbstractEntry<K>() {
726            @Override
727            public K getElement() {
728              return key;
729            }
730
731            @Override
732            public int getCount() {
733              return keyCount.count(key);
734            }
735          };
736        }
737      };
738    }
739
740    @Override
741    int distinctElements() {
742      return elementSet().size();
743    }
744
745    @Override public Iterator<K> iterator() {
746      return new TransformedIterator<Node<K, V>, K>(new NodeIterator()) {
747        @Override
748        K transform(Node<K, V> node) {
749          return node.key;
750        }
751      };
752    }
753
754    @Override
755    public int remove(@Nullable Object key, int occurrences) {
756      checkArgument(occurrences >= 0);
757      int oldCount = count(key);
758      Iterator<V> values = new ValueForKeyIterator(key);
759      while ((occurrences-- > 0) && values.hasNext()) {
760        values.next();
761        values.remove();
762      }
763      return oldCount;
764    }
765
766    @Override
767    public Set<K> elementSet() {
768      return keySet();
769    }
770
771    @Override public boolean equals(@Nullable Object object) {
772      return keyCount.equals(object);
773    }
774
775    @Override public int hashCode() {
776      return keyCount.hashCode();
777    }
778
779    @Override public String toString() {
780      return keyCount.toString(); // XXX observe order?
781    }
782  }
783
784  private transient List<V> valuesList;
785
786  /**
787   * {@inheritDoc}
788   *
789   * <p>The iterator generated by the returned collection traverses the values
790   * in the order they were added to the multimap. Because the values may have
791   * duplicates and follow the insertion ordering, this method returns a {@link
792   * List}, instead of the {@link Collection} specified in the {@link
793   * ListMultimap} interface.
794   */
795  @Override
796  public List<V> values() {
797    List<V> result = valuesList;
798    if (result == null) {
799      valuesList = result = new AbstractSequentialList<V>() {
800        @Override public int size() {
801          return keyCount.size();
802        }
803        @Override
804        public ListIterator<V> listIterator(int index) {
805          final NodeIterator nodes = new NodeIterator(index);
806          return new TransformedListIterator<Node<K, V>, V>(nodes) {
807            @Override
808            V transform(Node<K, V> node) {
809              return node.value;
810            }
811
812            @Override
813            public void set(V value) {
814              nodes.setValue(value);
815            }
816          };
817        }
818      };
819    }
820    return result;
821  }
822
823  private static <K, V> Entry<K, V> createEntry(final Node<K, V> node) {
824    return new AbstractMapEntry<K, V>() {
825      @Override public K getKey() {
826        return node.key;
827      }
828      @Override public V getValue() {
829        return node.value;
830      }
831      @Override public V setValue(V value) {
832        V oldValue = node.value;
833        node.value = value;
834        return oldValue;
835      }
836    };
837  }
838
839  private transient List<Entry<K, V>> entries;
840
841  /**
842   * {@inheritDoc}
843   *
844   * <p>The iterator generated by the returned collection traverses the entries
845   * in the order they were added to the multimap. Because the entries may have
846   * duplicates and follow the insertion ordering, this method returns a {@link
847   * List}, instead of the {@link Collection} specified in the {@link
848   * ListMultimap} interface.
849   *
850   * <p>An entry's {@link Entry#getKey} method always returns the same key,
851   * regardless of what happens subsequently. As long as the corresponding
852   * key-value mapping is not removed from the multimap, {@link Entry#getValue}
853   * returns the value from the multimap, which may change over time, and {@link
854   * Entry#setValue} modifies that value. Removing the mapping from the
855   * multimap does not alter the value returned by {@code getValue()}, though a
856   * subsequent {@code setValue()} call won't update the multimap but will lead
857   * to a revised value being returned by {@code getValue()}.
858   */
859  @Override
860  public List<Entry<K, V>> entries() {
861    List<Entry<K, V>> result = entries;
862    if (result == null) {
863      entries = result = new AbstractSequentialList<Entry<K, V>>() {
864        @Override public int size() {
865          return keyCount.size();
866        }
867
868        @Override public ListIterator<Entry<K, V>> listIterator(int index) {
869          return new TransformedListIterator<Node<K, V>, Entry<K, V>>(new NodeIterator(index)) {
870            @Override
871            Entry<K, V> transform(Node<K, V> node) {
872              return createEntry(node);
873            }
874          };
875        }
876      };
877    }
878    return result;
879  }
880
881  private transient Map<K, Collection<V>> map;
882
883  @Override
884  public Map<K, Collection<V>> asMap() {
885    Map<K, Collection<V>> result = map;
886    if (result == null) {
887      map = result = new Multimaps.AsMap<K, V>() {
888        @Override
889        public int size() {
890          return keyCount.elementSet().size();
891        }
892
893        @Override
894        Multimap<K, V> multimap() {
895          return LinkedListMultimap.this;
896        }
897
898        @Override
899        Iterator<Entry<K, Collection<V>>> entryIterator() {
900          return new TransformedIterator<K, Entry<K, Collection<V>>>(new DistinctKeyIterator()) {
901            @Override
902            Entry<K, Collection<V>> transform(final K key) {
903              return new AbstractMapEntry<K, Collection<V>>() {
904                @Override public K getKey() {
905                  return key;
906                }
907
908                @Override public Collection<V> getValue() {
909                  return LinkedListMultimap.this.get(key);
910                }
911              };
912            }
913          };
914        }
915      };
916    }
917
918    return result;
919  }
920
921  // Comparison and hashing
922
923  /**
924   * Compares the specified object to this multimap for equality.
925   *
926   * <p>Two {@code ListMultimap} instances are equal if, for each key, they
927   * contain the same values in the same order. If the value orderings disagree,
928   * the multimaps will not be considered equal.
929   */
930  @Override public boolean equals(@Nullable Object other) {
931    if (other == this) {
932      return true;
933    }
934    if (other instanceof Multimap) {
935      Multimap<?, ?> that = (Multimap<?, ?>) other;
936      return this.asMap().equals(that.asMap());
937    }
938    return false;
939  }
940
941  /**
942   * Returns the hash code for this multimap.
943   *
944   * <p>The hash code of a multimap is defined as the hash code of the map view,
945   * as returned by {@link Multimap#asMap}.
946   */
947  @Override public int hashCode() {
948    return asMap().hashCode();
949  }
950
951  /**
952   * Returns a string representation of the multimap, generated by calling
953   * {@code toString} on the map returned by {@link Multimap#asMap}.
954   *
955   * @return a string representation of the multimap
956   */
957  @Override public String toString() {
958    return asMap().toString();
959  }
960
961  /**
962   * @serialData the number of distinct keys, and then for each distinct key:
963   *     the first key, the number of values for that key, and the key's values,
964   *     followed by successive keys and values from the entries() ordering
965   */
966  @GwtIncompatible("java.io.ObjectOutputStream")
967  private void writeObject(ObjectOutputStream stream) throws IOException {
968    stream.defaultWriteObject();
969    stream.writeInt(size());
970    for (Entry<K, V> entry : entries()) {
971      stream.writeObject(entry.getKey());
972      stream.writeObject(entry.getValue());
973    }
974  }
975
976  @GwtIncompatible("java.io.ObjectInputStream")
977  private void readObject(ObjectInputStream stream)
978      throws IOException, ClassNotFoundException {
979    stream.defaultReadObject();
980    keyCount = LinkedHashMultiset.create();
981    keyToKeyHead = Maps.newHashMap();
982    keyToKeyTail = Maps.newHashMap();
983    int size = stream.readInt();
984    for (int i = 0; i < size; i++) {
985      @SuppressWarnings("unchecked") // reading data stored by writeObject
986      K key = (K) stream.readObject();
987      @SuppressWarnings("unchecked") // reading data stored by writeObject
988      V value = (V) stream.readObject();
989      put(key, value);
990    }
991  }
992
993  @GwtIncompatible("java serialization not supported")
994  private static final long serialVersionUID = 0;
995}