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
017 package com.google.common.collect;
018
019 import static com.google.common.base.Preconditions.checkArgument;
020 import static com.google.common.base.Preconditions.checkState;
021 import static java.util.Collections.unmodifiableList;
022
023 import com.google.common.annotations.GwtCompatible;
024 import com.google.common.annotations.GwtIncompatible;
025 import com.google.common.base.Objects;
026 import com.google.common.base.Preconditions;
027
028 import java.io.IOException;
029 import java.io.ObjectInputStream;
030 import java.io.ObjectOutputStream;
031 import java.io.Serializable;
032 import java.util.AbstractSequentialList;
033 import java.util.Collection;
034 import java.util.Iterator;
035 import java.util.List;
036 import java.util.ListIterator;
037 import java.util.Map;
038 import java.util.Map.Entry;
039 import java.util.NoSuchElementException;
040 import java.util.Set;
041
042 import 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)
101 public 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 }