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