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