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