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