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