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