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