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