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.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 public boolean hasNext() {
281 return next != null;
282 }
283 public Node<K, V> next() {
284 checkElement(next);
285 current = next;
286 next = next.next;
287 return current;
288 }
289 public void remove() {
290 checkState(current != null);
291 removeNode(current);
292 current = null;
293 }
294 }
295
296 /** An {@code Iterator} over distinct keys in key head order. */
297 private class DistinctKeyIterator implements Iterator<K> {
298 final Set<K> seenKeys = new HashSet<K>(Maps.capacity(keySet().size()));
299 Node<K, V> next = head;
300 Node<K, V> current;
301
302 public boolean hasNext() {
303 return next != null;
304 }
305 public K next() {
306 checkElement(next);
307 current = next;
308 seenKeys.add(current.key);
309 do { // skip ahead to next unseen key
310 next = next.next;
311 } while ((next != null) && !seenKeys.add(next.key));
312 return current.key;
313 }
314 public void remove() {
315 checkState(current != null);
316 removeAllNodes(current.key);
317 current = null;
318 }
319 }
320
321 /** A {@code ListIterator} over values for a specified key. */
322 private class ValueForKeyIterator implements ListIterator<V> {
323 final Object key;
324 int nextIndex;
325 Node<K, V> next;
326 Node<K, V> current;
327 Node<K, V> previous;
328
329 /** Constructs a new iterator over all values for the specified key. */
330 ValueForKeyIterator(@Nullable Object key) {
331 this.key = key;
332 next = keyToKeyHead.get(key);
333 }
334
335 /**
336 * Constructs a new iterator over all values for the specified key starting
337 * at the specified index. This constructor is optimized so that it starts
338 * at either the head or the tail, depending on which is closer to the
339 * specified index. This allows adds to the tail to be done in constant
340 * time.
341 *
342 * @throws IndexOutOfBoundsException if index is invalid
343 */
344 public ValueForKeyIterator(@Nullable Object key, int index) {
345 int size = keyCount.count(key);
346 Preconditions.checkPositionIndex(index, size);
347 if (index >= (size / 2)) {
348 previous = keyToKeyTail.get(key);
349 nextIndex = size;
350 while (index++ < size) {
351 previous();
352 }
353 } else {
354 next = keyToKeyHead.get(key);
355 while (index-- > 0) {
356 next();
357 }
358 }
359 this.key = key;
360 current = null;
361 }
362
363 public boolean hasNext() {
364 return next != null;
365 }
366
367 public V next() {
368 checkElement(next);
369 previous = current = next;
370 next = next.nextSibling;
371 nextIndex++;
372 return current.value;
373 }
374
375 public boolean hasPrevious() {
376 return previous != null;
377 }
378
379 public V previous() {
380 checkElement(previous);
381 next = current = previous;
382 previous = previous.previousSibling;
383 nextIndex--;
384 return current.value;
385 }
386
387 public int nextIndex() {
388 return nextIndex;
389 }
390
391 public int previousIndex() {
392 return nextIndex - 1;
393 }
394
395 public void remove() {
396 checkState(current != null);
397 if (current != next) { // removing next element
398 previous = current.previousSibling;
399 nextIndex--;
400 } else {
401 next = current.nextSibling;
402 }
403 removeNode(current);
404 current = null;
405 }
406
407 public void set(V value) {
408 checkState(current != null);
409 current.value = value;
410 }
411
412 @SuppressWarnings("unchecked")
413 public void add(V value) {
414 previous = addNode((K) key, value, next);
415 nextIndex++;
416 current = null;
417 }
418 }
419
420 // Query Operations
421
422 public int size() {
423 return keyCount.size();
424 }
425
426 public boolean isEmpty() {
427 return head == null;
428 }
429
430 public boolean containsKey(@Nullable Object key) {
431 return keyToKeyHead.containsKey(key);
432 }
433
434 public boolean containsValue(@Nullable Object value) {
435 for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) {
436 if (Objects.equal(i.next().value, value)) {
437 return true;
438 }
439 }
440 return false;
441 }
442
443 public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
444 for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) {
445 if (Objects.equal(i.next(), value)) {
446 return true;
447 }
448 }
449 return false;
450 }
451
452 // Modification Operations
453
454 /**
455 * Stores a key-value pair in the multimap.
456 *
457 * @param key key to store in the multimap
458 * @param value value to store in the multimap
459 * @return {@code true} always
460 */
461 public boolean put(@Nullable K key, @Nullable V value) {
462 addNode(key, value, null);
463 return true;
464 }
465
466 public boolean remove(@Nullable Object key, @Nullable Object value) {
467 Iterator<V> values = new ValueForKeyIterator(key);
468 while (values.hasNext()) {
469 if (Objects.equal(values.next(), value)) {
470 values.remove();
471 return true;
472 }
473 }
474 return false;
475 }
476
477 // Bulk Operations
478
479 public boolean putAll(@Nullable K key, Iterable<? extends V> values) {
480 boolean changed = false;
481 for (V value : values) {
482 changed |= put(key, value);
483 }
484 return changed;
485 }
486
487 public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
488 boolean changed = false;
489 for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
490 changed |= put(entry.getKey(), entry.getValue());
491 }
492 return changed;
493 }
494
495 /**
496 * {@inheritDoc}
497 *
498 * <p>If any entries for the specified {@code key} already exist in the
499 * multimap, their values are changed in-place without affecting the iteration
500 * order.
501 *
502 * <p>The returned list is immutable and implements
503 * {@link java.util.RandomAccess}.
504 */
505 public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
506 List<V> oldValues = getCopy(key);
507 ListIterator<V> keyValues = new ValueForKeyIterator(key);
508 Iterator<? extends V> newValues = values.iterator();
509
510 // Replace existing values, if any.
511 while (keyValues.hasNext() && newValues.hasNext()) {
512 keyValues.next();
513 keyValues.set(newValues.next());
514 }
515
516 // Remove remaining old values, if any.
517 while (keyValues.hasNext()) {
518 keyValues.next();
519 keyValues.remove();
520 }
521
522 // Add remaining new values, if any.
523 while (newValues.hasNext()) {
524 keyValues.add(newValues.next());
525 }
526
527 return oldValues;
528 }
529
530 private List<V> getCopy(@Nullable Object key) {
531 return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key)));
532 }
533
534 /**
535 * {@inheritDoc}
536 *
537 * <p>The returned list is immutable and implements
538 * {@link java.util.RandomAccess}.
539 */
540 public List<V> removeAll(@Nullable Object key) {
541 List<V> oldValues = getCopy(key);
542 removeAllNodes(key);
543 return oldValues;
544 }
545
546 public void clear() {
547 head = null;
548 tail = null;
549 keyCount.clear();
550 keyToKeyHead.clear();
551 keyToKeyTail.clear();
552 }
553
554 // Views
555
556 /**
557 * {@inheritDoc}
558 *
559 * <p>If the multimap is modified while an iteration over the list is in
560 * progress (except through the iterator's own {@code add}, {@code set} or
561 * {@code remove} operations) the results of the iteration are undefined.
562 *
563 * <p>The returned list is not serializable and does not have random access.
564 */
565 public List<V> get(final @Nullable K key) {
566 return new AbstractSequentialList<V>() {
567 @Override public int size() {
568 return keyCount.count(key);
569 }
570 @Override public ListIterator<V> listIterator(int index) {
571 return new ValueForKeyIterator(key, index);
572 }
573 @Override public boolean removeAll(Collection<?> c) {
574 return Iterators.removeAll(iterator(), c);
575 }
576 @Override public boolean retainAll(Collection<?> c) {
577 return Iterators.retainAll(iterator(), c);
578 }
579 };
580 }
581
582 private transient Set<K> keySet;
583
584 public Set<K> keySet() {
585 Set<K> result = keySet;
586 if (result == null) {
587 keySet = result = new AbstractSet<K>() {
588 @Override public int size() {
589 return keyCount.elementSet().size();
590 }
591 @Override public Iterator<K> iterator() {
592 return new DistinctKeyIterator();
593 }
594 @Override public boolean contains(Object key) { // for performance
595 return keyCount.contains(key);
596 }
597 @Override public boolean removeAll(Collection<?> c) {
598 checkNotNull(c); // eager for GWT
599 return super.removeAll(c);
600 }
601 };
602 }
603 return result;
604 }
605
606 private transient Multiset<K> keys;
607
608 public Multiset<K> keys() {
609 Multiset<K> result = keys;
610 if (result == null) {
611 keys = result = new MultisetView();
612 }
613 return result;
614 }
615
616 private class MultisetView extends AbstractCollection<K>
617 implements Multiset<K> {
618
619 @Override public int size() {
620 return keyCount.size();
621 }
622
623 @Override public Iterator<K> iterator() {
624 final Iterator<Node<K, V>> nodes = new NodeIterator();
625 return new Iterator<K>() {
626 public boolean hasNext() {
627 return nodes.hasNext();
628 }
629 public K next() {
630 return nodes.next().key;
631 }
632 public void remove() {
633 nodes.remove();
634 }
635 };
636 }
637
638 public int count(@Nullable Object key) {
639 return keyCount.count(key);
640 }
641
642 public int add(@Nullable K key, int occurrences) {
643 throw new UnsupportedOperationException();
644 }
645
646 public int remove(@Nullable Object key, int occurrences) {
647 checkArgument(occurrences >= 0);
648 int oldCount = count(key);
649 Iterator<V> values = new ValueForKeyIterator(key);
650 while ((occurrences-- > 0) && values.hasNext()) {
651 values.next();
652 values.remove();
653 }
654 return oldCount;
655 }
656
657 public int setCount(K element, int count) {
658 return setCountImpl(this, element, count);
659 }
660
661 public boolean setCount(K element, int oldCount, int newCount) {
662 return setCountImpl(this, element, oldCount, newCount);
663 }
664
665 @Override public boolean removeAll(Collection<?> c) {
666 return Iterators.removeAll(iterator(), c);
667 }
668
669 @Override public boolean retainAll(Collection<?> c) {
670 return Iterators.retainAll(iterator(), c);
671 }
672
673 public Set<K> elementSet() {
674 return keySet();
675 }
676
677 public Set<Entry<K>> entrySet() {
678 // TODO(jlevy): lazy init?
679 return new AbstractSet<Entry<K>>() {
680 @Override public int size() {
681 return keyCount.elementSet().size();
682 }
683
684 @Override public Iterator<Entry<K>> iterator() {
685 final Iterator<K> keyIterator = new DistinctKeyIterator();
686 return new Iterator<Entry<K>>() {
687 public boolean hasNext() {
688 return keyIterator.hasNext();
689 }
690 public Entry<K> next() {
691 final K key = keyIterator.next();
692 return new Multisets.AbstractEntry<K>() {
693 public K getElement() {
694 return key;
695 }
696 public int getCount() {
697 return keyCount.count(key);
698 }
699 };
700 }
701 public void remove() {
702 keyIterator.remove();
703 }
704 };
705 }
706 };
707 }
708
709 @Override public boolean equals(@Nullable Object object) {
710 return keyCount.equals(object);
711 }
712
713 @Override public int hashCode() {
714 return keyCount.hashCode();
715 }
716
717 @Override public String toString() {
718 return keyCount.toString(); // XXX observe order?
719 }
720 }
721
722 private transient Collection<V> valuesCollection;
723
724 /**
725 * {@inheritDoc}
726 *
727 * <p>The iterator generated by the returned collection traverses the values
728 * in the order they were added to the multimap.
729 */
730 public Collection<V> values() {
731 Collection<V> result = valuesCollection;
732 if (result == null) {
733 valuesCollection = result = new AbstractCollection<V>() {
734 @Override public int size() {
735 return keyCount.size();
736 }
737 @Override public Iterator<V> iterator() {
738 final Iterator<Node<K, V>> nodes = new NodeIterator();
739 return new Iterator<V>() {
740 public boolean hasNext() {
741 return nodes.hasNext();
742 }
743 public V next() {
744 return nodes.next().value;
745 }
746 public void remove() {
747 nodes.remove();
748 }
749 };
750 }
751 };
752 }
753 return result;
754 }
755
756 private transient Collection<Entry<K, V>> entries;
757
758 /**
759 * {@inheritDoc}
760 *
761 * <p>The iterator generated by the returned collection traverses the entries
762 * in the order they were added to the multimap.
763 *
764 * <p>An entry's {@link Entry#getKey} method always returns the same key,
765 * regardless of what happens subsequently. As long as the corresponding
766 * key-value mapping is not removed from the multimap, {@link Entry#getValue}
767 * returns the value from the multimap, which may change over time, and {@link
768 * Entry#setValue} modifies that value. Removing the mapping from the
769 * multimap does not alter the value returned by {@code getValue()}, though a
770 * subsequent {@code setValue()} call won't update the multimap but will lead
771 * to a revised value being returned by {@code getValue()}.
772 */
773 public Collection<Entry<K, V>> entries() {
774 Collection<Entry<K, V>> result = entries;
775 if (result == null) {
776 entries = result = new AbstractCollection<Entry<K, V>>() {
777 @Override public int size() {
778 return keyCount.size();
779 }
780
781 @Override public Iterator<Entry<K, V>> iterator() {
782 final Iterator<Node<K, V>> nodes = new NodeIterator();
783 return new Iterator<Entry<K, V>>() {
784 public boolean hasNext() {
785 return nodes.hasNext();
786 }
787
788 public Entry<K, V> next() {
789 final Node<K, V> node = nodes.next();
790 return new AbstractMapEntry<K, V>() {
791 @Override public K getKey() {
792 return node.key;
793 }
794 @Override public V getValue() {
795 return node.value;
796 }
797 @Override public V setValue(V value) {
798 V oldValue = node.value;
799 node.value = value;
800 return oldValue;
801 }
802 };
803 }
804
805 public void remove() {
806 nodes.remove();
807 }
808 };
809 }
810 };
811 }
812 return result;
813 }
814
815 private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
816 @Override public int size() {
817 return keyCount.elementSet().size();
818 }
819
820 @Override public Iterator<Entry<K, Collection<V>>> iterator() {
821 final Iterator<K> keyIterator = new DistinctKeyIterator();
822 return new Iterator<Entry<K, Collection<V>>>() {
823 public boolean hasNext() {
824 return keyIterator.hasNext();
825 }
826
827 public Entry<K, Collection<V>> next() {
828 final K key = keyIterator.next();
829 return new AbstractMapEntry<K, Collection<V>>() {
830 @Override public K getKey() {
831 return key;
832 }
833
834 @Override public Collection<V> getValue() {
835 return LinkedListMultimap.this.get(key);
836 }
837 };
838 }
839
840 public void remove() {
841 keyIterator.remove();
842 }
843 };
844 }
845
846 // TODO(jlevy): Override contains() and remove() for better performance.
847 }
848
849 private transient Map<K, Collection<V>> map;
850
851 public Map<K, Collection<V>> asMap() {
852 Map<K, Collection<V>> result = map;
853 if (result == null) {
854 map = result = new AbstractMap<K, Collection<V>>() {
855 Set<Entry<K, Collection<V>>> entrySet;
856
857 @Override public Set<Entry<K, Collection<V>>> entrySet() {
858 Set<Entry<K, Collection<V>>> result = entrySet;
859 if (result == null) {
860 entrySet = result = new AsMapEntries();
861 }
862 return result;
863 }
864
865 // The following methods are included for performance.
866
867 @Override public boolean containsKey(@Nullable Object key) {
868 return LinkedListMultimap.this.containsKey(key);
869 }
870
871 @SuppressWarnings("unchecked")
872 @Override public Collection<V> get(@Nullable Object key) {
873 Collection<V> collection = LinkedListMultimap.this.get((K) key);
874 return collection.isEmpty() ? null : collection;
875 }
876
877 @Override public Collection<V> remove(@Nullable Object key) {
878 Collection<V> collection = removeAll(key);
879 return collection.isEmpty() ? null : collection;
880 }
881 };
882 }
883
884 return result;
885 }
886
887 // Comparison and hashing
888
889 /**
890 * Compares the specified object to this multimap for equality.
891 *
892 * <p>Two {@code ListMultimap} instances are equal if, for each key, they
893 * contain the same values in the same order. If the value orderings disagree,
894 * the multimaps will not be considered equal.
895 */
896 @Override public boolean equals(@Nullable Object other) {
897 if (other == this) {
898 return true;
899 }
900 if (other instanceof Multimap) {
901 Multimap<?, ?> that = (Multimap<?, ?>) other;
902 return this.asMap().equals(that.asMap());
903 }
904 return false;
905 }
906
907 /**
908 * Returns the hash code for this multimap.
909 *
910 * <p>The hash code of a multimap is defined as the hash code of the map view,
911 * as returned by {@link Multimap#asMap}.
912 */
913 @Override public int hashCode() {
914 return asMap().hashCode();
915 }
916
917 /**
918 * Returns a string representation of the multimap, generated by calling
919 * {@code toString} on the map returned by {@link Multimap#asMap}.
920 *
921 * @return a string representation of the multimap
922 */
923 @Override public String toString() {
924 return asMap().toString();
925 }
926
927 /**
928 * @serialData the number of distinct keys, and then for each distinct key:
929 * the first key, the number of values for that key, and the key's values,
930 * followed by successive keys and values from the entries() ordering
931 */
932 @GwtIncompatible("java.io.ObjectOutputStream")
933 private void writeObject(ObjectOutputStream stream) throws IOException {
934 stream.defaultWriteObject();
935 stream.writeInt(size());
936 for (Entry<K, V> entry : entries()) {
937 stream.writeObject(entry.getKey());
938 stream.writeObject(entry.getValue());
939 }
940 }
941
942 @GwtIncompatible("java.io.ObjectInputStream")
943 private void readObject(ObjectInputStream stream)
944 throws IOException, ClassNotFoundException {
945 stream.defaultReadObject();
946 keyCount = LinkedHashMultiset.create();
947 keyToKeyHead = Maps.newHashMap();
948 keyToKeyTail = Maps.newHashMap();
949 int size = stream.readInt();
950 for (int i = 0; i < size; i++) {
951 @SuppressWarnings("unchecked") // reading data stored by writeObject
952 K key = (K) stream.readObject();
953 @SuppressWarnings("unchecked") // reading data stored by writeObject
954 V value = (V) stream.readObject();
955 put(key, value);
956 }
957 }
958
959 @GwtIncompatible("java serialization not supported")
960 private static final long serialVersionUID = 0;
961 }