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