1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21import static com.google.common.collect.CollectPreconditions.checkRemove; 22 23import com.google.common.annotations.GwtCompatible; 24import com.google.common.collect.Maps.ImprovedAbstractMap; 25 26import java.io.Serializable; 27import java.util.AbstractCollection; 28import java.util.Collection; 29import java.util.Collections; 30import java.util.Comparator; 31import java.util.ConcurrentModificationException; 32import java.util.Iterator; 33import java.util.List; 34import java.util.ListIterator; 35import java.util.Map; 36import java.util.Map.Entry; 37import java.util.RandomAccess; 38import java.util.Set; 39import java.util.SortedMap; 40import java.util.SortedSet; 41 42import javax.annotation.Nullable; 43 44/** 45 * Basic implementation of the {@link Multimap} interface. This class represents 46 * a multimap as a map that associates each key with a collection of values. All 47 * methods of {@link Multimap} are supported, including those specified as 48 * optional in the interface. 49 * 50 * <p>To implement a multimap, a subclass must define the method {@link 51 * #createCollection()}, which creates an empty collection of values for a key. 52 * 53 * <p>The multimap constructor takes a map that has a single entry for each 54 * distinct key. When you insert a key-value pair with a key that isn't already 55 * in the multimap, {@code AbstractMapBasedMultimap} calls {@link #createCollection()} 56 * to create the collection of values for that key. The subclass should not call 57 * {@link #createCollection()} directly, and a new instance should be created 58 * every time the method is called. 59 * 60 * <p>For example, the subclass could pass a {@link java.util.TreeMap} during 61 * construction, and {@link #createCollection()} could return a {@link 62 * java.util.TreeSet}, in which case the multimap's iterators would propagate 63 * through the keys and values in sorted order. 64 * 65 * <p>Keys and values may be null, as long as the underlying collection classes 66 * support null elements. 67 * 68 * <p>The collections created by {@link #createCollection()} may or may not 69 * allow duplicates. If the collection, such as a {@link Set}, does not support 70 * duplicates, an added key-value pair will replace an existing pair with the 71 * same key and value, if such a pair is present. With collections like {@link 72 * List} that allow duplicates, the collection will keep the existing key-value 73 * pairs while adding a new pair. 74 * 75 * <p>This class is not threadsafe when any concurrent operations update the 76 * multimap, even if the underlying map and {@link #createCollection()} method 77 * return threadsafe classes. Concurrent read operations will work correctly. To 78 * allow concurrent update operations, wrap your multimap with a call to {@link 79 * Multimaps#synchronizedMultimap}. 80 * 81 * <p>For serialization to work, the subclass must specify explicit 82 * {@code readObject} and {@code writeObject} methods. 83 * 84 * @author Jared Levy 85 * @author Louis Wasserman 86 */ 87@GwtCompatible(emulated = true) 88abstract class AbstractMapBasedMultimap<K, V> extends AbstractMultimap<K, V> 89 implements Serializable { 90 /* 91 * Here's an outline of the overall design. 92 * 93 * The map variable contains the collection of values associated with each 94 * key. When a key-value pair is added to a multimap that didn't previously 95 * contain any values for that key, a new collection generated by 96 * createCollection is added to the map. That same collection instance 97 * remains in the map as long as the multimap has any values for the key. If 98 * all values for the key are removed, the key and collection are removed 99 * from the map. 100 * 101 * The get method returns a WrappedCollection, which decorates the collection 102 * in the map (if the key is present) or an empty collection (if the key is 103 * not present). When the collection delegate in the WrappedCollection is 104 * empty, the multimap may contain subsequently added values for that key. To 105 * handle that situation, the WrappedCollection checks whether map contains 106 * an entry for the provided key, and if so replaces the delegate. 107 */ 108 109 private transient Map<K, Collection<V>> map; 110 private transient int totalSize; 111 112 /** 113 * Creates a new multimap that uses the provided map. 114 * 115 * @param map place to store the mapping from each key to its corresponding 116 * values 117 * @throws IllegalArgumentException if {@code map} is not empty 118 */ 119 protected AbstractMapBasedMultimap(Map<K, Collection<V>> map) { 120 checkArgument(map.isEmpty()); 121 this.map = map; 122 } 123 124 /** Used during deserialization only. */ 125 final void setMap(Map<K, Collection<V>> map) { 126 this.map = map; 127 totalSize = 0; 128 for (Collection<V> values : map.values()) { 129 checkArgument(!values.isEmpty()); 130 totalSize += values.size(); 131 } 132 } 133 134 /** 135 * Creates an unmodifiable, empty collection of values. 136 * 137 * <p>This is used in {@link #removeAll} on an empty key. 138 */ 139 Collection<V> createUnmodifiableEmptyCollection() { 140 return unmodifiableCollectionSubclass(createCollection()); 141 } 142 143 /** 144 * Creates the collection of values for a single key. 145 * 146 * <p>Collections with weak, soft, or phantom references are not supported. 147 * Each call to {@code createCollection} should create a new instance. 148 * 149 * <p>The returned collection class determines whether duplicate key-value 150 * pairs are allowed. 151 * 152 * @return an empty collection of values 153 */ 154 abstract Collection<V> createCollection(); 155 156 /** 157 * Creates the collection of values for an explicitly provided key. By 158 * default, it simply calls {@link #createCollection()}, which is the correct 159 * behavior for most implementations. The {@link LinkedHashMultimap} class 160 * overrides it. 161 * 162 * @param key key to associate with values in the collection 163 * @return an empty collection of values 164 */ 165 Collection<V> createCollection(@Nullable K key) { 166 return createCollection(); 167 } 168 169 Map<K, Collection<V>> backingMap() { 170 return map; 171 } 172 173 // Query Operations 174 175 @Override 176 public int size() { 177 return totalSize; 178 } 179 180 @Override 181 public boolean containsKey(@Nullable Object key) { 182 return map.containsKey(key); 183 } 184 185 // Modification Operations 186 187 @Override 188 public boolean put(@Nullable K key, @Nullable V value) { 189 Collection<V> collection = map.get(key); 190 if (collection == null) { 191 collection = createCollection(key); 192 if (collection.add(value)) { 193 totalSize++; 194 map.put(key, collection); 195 return true; 196 } else { 197 throw new AssertionError("New Collection violated the Collection spec"); 198 } 199 } else if (collection.add(value)) { 200 totalSize++; 201 return true; 202 } else { 203 return false; 204 } 205 } 206 207 private Collection<V> getOrCreateCollection(@Nullable K key) { 208 Collection<V> collection = map.get(key); 209 if (collection == null) { 210 collection = createCollection(key); 211 map.put(key, collection); 212 } 213 return collection; 214 } 215 216 // Bulk Operations 217 218 /** 219 * {@inheritDoc} 220 * 221 * <p>The returned collection is immutable. 222 */ 223 @Override 224 public Collection<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 225 Iterator<? extends V> iterator = values.iterator(); 226 if (!iterator.hasNext()) { 227 return removeAll(key); 228 } 229 230 // TODO(user): investigate atomic failure? 231 Collection<V> collection = getOrCreateCollection(key); 232 Collection<V> oldValues = createCollection(); 233 oldValues.addAll(collection); 234 235 totalSize -= collection.size(); 236 collection.clear(); 237 238 while (iterator.hasNext()) { 239 if (collection.add(iterator.next())) { 240 totalSize++; 241 } 242 } 243 244 return unmodifiableCollectionSubclass(oldValues); 245 } 246 247 /** 248 * {@inheritDoc} 249 * 250 * <p>The returned collection is immutable. 251 */ 252 @Override 253 public Collection<V> removeAll(@Nullable Object key) { 254 Collection<V> collection = map.remove(key); 255 256 if (collection == null) { 257 return createUnmodifiableEmptyCollection(); 258 } 259 260 Collection<V> output = createCollection(); 261 output.addAll(collection); 262 totalSize -= collection.size(); 263 collection.clear(); 264 265 return unmodifiableCollectionSubclass(output); 266 } 267 268 Collection<V> unmodifiableCollectionSubclass(Collection<V> collection) { 269 // We don't deal with NavigableSet here yet for GWT reasons -- instead, 270 // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet. 271 if (collection instanceof SortedSet) { 272 return Collections.unmodifiableSortedSet((SortedSet<V>) collection); 273 } else if (collection instanceof Set) { 274 return Collections.unmodifiableSet((Set<V>) collection); 275 } else if (collection instanceof List) { 276 return Collections.unmodifiableList((List<V>) collection); 277 } else { 278 return Collections.unmodifiableCollection(collection); 279 } 280 } 281 282 @Override 283 public void clear() { 284 // Clear each collection, to make previously returned collections empty. 285 for (Collection<V> collection : map.values()) { 286 collection.clear(); 287 } 288 map.clear(); 289 totalSize = 0; 290 } 291 292 // Views 293 294 /** 295 * {@inheritDoc} 296 * 297 * <p>The returned collection is not serializable. 298 */ 299 @Override 300 public Collection<V> get(@Nullable K key) { 301 Collection<V> collection = map.get(key); 302 if (collection == null) { 303 collection = createCollection(key); 304 } 305 return wrapCollection(key, collection); 306 } 307 308 /** 309 * Generates a decorated collection that remains consistent with the values in 310 * the multimap for the provided key. Changes to the multimap may alter the 311 * returned collection, and vice versa. 312 */ 313 Collection<V> wrapCollection(@Nullable K key, Collection<V> collection) { 314 // We don't deal with NavigableSet here yet for GWT reasons -- instead, 315 // non-GWT TreeMultimap explicitly overrides this and uses NavigableSet. 316 if (collection instanceof SortedSet) { 317 return new WrappedSortedSet(key, (SortedSet<V>) collection, null); 318 } else if (collection instanceof Set) { 319 return new WrappedSet(key, (Set<V>) collection); 320 } else if (collection instanceof List) { 321 return wrapList(key, (List<V>) collection, null); 322 } else { 323 return new WrappedCollection(key, collection, null); 324 } 325 } 326 327 private List<V> wrapList( 328 @Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) { 329 return (list instanceof RandomAccess) 330 ? new RandomAccessWrappedList(key, list, ancestor) 331 : new WrappedList(key, list, ancestor); 332 } 333 334 /** 335 * Collection decorator that stays in sync with the multimap values for a key. 336 * There are two kinds of wrapped collections: full and subcollections. Both 337 * have a delegate pointing to the underlying collection class. 338 * 339 * <p>Full collections, identified by a null ancestor field, contain all 340 * multimap values for a given key. Its delegate is a value in {@link 341 * AbstractMapBasedMultimap#map} whenever the delegate is non-empty. The {@code 342 * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure 343 * that the {@code WrappedCollection} and map remain consistent. 344 * 345 * <p>A subcollection, such as a sublist, contains some of the values for a 346 * given key. Its ancestor field points to the full wrapped collection with 347 * all values for the key. The subcollection {@code refreshIfEmpty}, {@code 348 * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods 349 * of the full wrapped collection. 350 */ 351 private class WrappedCollection extends AbstractCollection<V> { 352 final K key; 353 Collection<V> delegate; 354 final WrappedCollection ancestor; 355 final Collection<V> ancestorDelegate; 356 357 WrappedCollection(@Nullable K key, Collection<V> delegate, 358 @Nullable WrappedCollection ancestor) { 359 this.key = key; 360 this.delegate = delegate; 361 this.ancestor = ancestor; 362 this.ancestorDelegate 363 = (ancestor == null) ? null : ancestor.getDelegate(); 364 } 365 366 /** 367 * If the delegate collection is empty, but the multimap has values for the 368 * key, replace the delegate with the new collection for the key. 369 * 370 * <p>For a subcollection, refresh its ancestor and validate that the 371 * ancestor delegate hasn't changed. 372 */ 373 void refreshIfEmpty() { 374 if (ancestor != null) { 375 ancestor.refreshIfEmpty(); 376 if (ancestor.getDelegate() != ancestorDelegate) { 377 throw new ConcurrentModificationException(); 378 } 379 } else if (delegate.isEmpty()) { 380 Collection<V> newDelegate = map.get(key); 381 if (newDelegate != null) { 382 delegate = newDelegate; 383 } 384 } 385 } 386 387 /** 388 * If collection is empty, remove it from {@code AbstractMapBasedMultimap.this.map}. 389 * For subcollections, check whether the ancestor collection is empty. 390 */ 391 void removeIfEmpty() { 392 if (ancestor != null) { 393 ancestor.removeIfEmpty(); 394 } else if (delegate.isEmpty()) { 395 map.remove(key); 396 } 397 } 398 399 K getKey() { 400 return key; 401 } 402 403 /** 404 * Add the delegate to the map. Other {@code WrappedCollection} methods 405 * should call this method after adding elements to a previously empty 406 * collection. 407 * 408 * <p>Subcollection add the ancestor's delegate instead. 409 */ 410 void addToMap() { 411 if (ancestor != null) { 412 ancestor.addToMap(); 413 } else { 414 map.put(key, delegate); 415 } 416 } 417 418 @Override public int size() { 419 refreshIfEmpty(); 420 return delegate.size(); 421 } 422 423 @Override public boolean equals(@Nullable Object object) { 424 if (object == this) { 425 return true; 426 } 427 refreshIfEmpty(); 428 return delegate.equals(object); 429 } 430 431 @Override public int hashCode() { 432 refreshIfEmpty(); 433 return delegate.hashCode(); 434 } 435 436 @Override public String toString() { 437 refreshIfEmpty(); 438 return delegate.toString(); 439 } 440 441 Collection<V> getDelegate() { 442 return delegate; 443 } 444 445 @Override public Iterator<V> iterator() { 446 refreshIfEmpty(); 447 return new WrappedIterator(); 448 } 449 450 /** Collection iterator for {@code WrappedCollection}. */ 451 class WrappedIterator implements Iterator<V> { 452 final Iterator<V> delegateIterator; 453 final Collection<V> originalDelegate = delegate; 454 455 WrappedIterator() { 456 delegateIterator = iteratorOrListIterator(delegate); 457 } 458 459 WrappedIterator(Iterator<V> delegateIterator) { 460 this.delegateIterator = delegateIterator; 461 } 462 463 /** 464 * If the delegate changed since the iterator was created, the iterator is 465 * no longer valid. 466 */ 467 void validateIterator() { 468 refreshIfEmpty(); 469 if (delegate != originalDelegate) { 470 throw new ConcurrentModificationException(); 471 } 472 } 473 474 @Override 475 public boolean hasNext() { 476 validateIterator(); 477 return delegateIterator.hasNext(); 478 } 479 480 @Override 481 public V next() { 482 validateIterator(); 483 return delegateIterator.next(); 484 } 485 486 @Override 487 public void remove() { 488 delegateIterator.remove(); 489 totalSize--; 490 removeIfEmpty(); 491 } 492 493 Iterator<V> getDelegateIterator() { 494 validateIterator(); 495 return delegateIterator; 496 } 497 } 498 499 @Override public boolean add(V value) { 500 refreshIfEmpty(); 501 boolean wasEmpty = delegate.isEmpty(); 502 boolean changed = delegate.add(value); 503 if (changed) { 504 totalSize++; 505 if (wasEmpty) { 506 addToMap(); 507 } 508 } 509 return changed; 510 } 511 512 WrappedCollection getAncestor() { 513 return ancestor; 514 } 515 516 // The following methods are provided for better performance. 517 518 @Override public boolean addAll(Collection<? extends V> collection) { 519 if (collection.isEmpty()) { 520 return false; 521 } 522 int oldSize = size(); // calls refreshIfEmpty 523 boolean changed = delegate.addAll(collection); 524 if (changed) { 525 int newSize = delegate.size(); 526 totalSize += (newSize - oldSize); 527 if (oldSize == 0) { 528 addToMap(); 529 } 530 } 531 return changed; 532 } 533 534 @Override public boolean contains(Object o) { 535 refreshIfEmpty(); 536 return delegate.contains(o); 537 } 538 539 @Override public boolean containsAll(Collection<?> c) { 540 refreshIfEmpty(); 541 return delegate.containsAll(c); 542 } 543 544 @Override public void clear() { 545 int oldSize = size(); // calls refreshIfEmpty 546 if (oldSize == 0) { 547 return; 548 } 549 delegate.clear(); 550 totalSize -= oldSize; 551 removeIfEmpty(); // maybe shouldn't be removed if this is a sublist 552 } 553 554 @Override public boolean remove(Object o) { 555 refreshIfEmpty(); 556 boolean changed = delegate.remove(o); 557 if (changed) { 558 totalSize--; 559 removeIfEmpty(); 560 } 561 return changed; 562 } 563 564 @Override public boolean removeAll(Collection<?> c) { 565 if (c.isEmpty()) { 566 return false; 567 } 568 int oldSize = size(); // calls refreshIfEmpty 569 boolean changed = delegate.removeAll(c); 570 if (changed) { 571 int newSize = delegate.size(); 572 totalSize += (newSize - oldSize); 573 removeIfEmpty(); 574 } 575 return changed; 576 } 577 578 @Override public boolean retainAll(Collection<?> c) { 579 checkNotNull(c); 580 int oldSize = size(); // calls refreshIfEmpty 581 boolean changed = delegate.retainAll(c); 582 if (changed) { 583 int newSize = delegate.size(); 584 totalSize += (newSize - oldSize); 585 removeIfEmpty(); 586 } 587 return changed; 588 } 589 } 590 591 private Iterator<V> iteratorOrListIterator(Collection<V> collection) { 592 return (collection instanceof List) 593 ? ((List<V>) collection).listIterator() 594 : collection.iterator(); 595 } 596 597 /** Set decorator that stays in sync with the multimap values for a key. */ 598 private class WrappedSet extends WrappedCollection implements Set<V> { 599 WrappedSet(@Nullable K key, Set<V> delegate) { 600 super(key, delegate, null); 601 } 602 603 @Override 604 public boolean removeAll(Collection<?> c) { 605 if (c.isEmpty()) { 606 return false; 607 } 608 int oldSize = size(); // calls refreshIfEmpty 609 610 // Guava issue 1013: AbstractSet and most JDK set implementations are 611 // susceptible to quadratic removeAll performance on lists; 612 // use a slightly smarter implementation here 613 boolean changed = Sets.removeAllImpl((Set<V>) delegate, c); 614 if (changed) { 615 int newSize = delegate.size(); 616 totalSize += (newSize - oldSize); 617 removeIfEmpty(); 618 } 619 return changed; 620 } 621 } 622 623 /** 624 * SortedSet decorator that stays in sync with the multimap values for a key. 625 */ 626 private class WrappedSortedSet extends WrappedCollection 627 implements SortedSet<V> { 628 WrappedSortedSet(@Nullable K key, SortedSet<V> delegate, 629 @Nullable WrappedCollection ancestor) { 630 super(key, delegate, ancestor); 631 } 632 633 SortedSet<V> getSortedSetDelegate() { 634 return (SortedSet<V>) getDelegate(); 635 } 636 637 @Override 638 public Comparator<? super V> comparator() { 639 return getSortedSetDelegate().comparator(); 640 } 641 642 @Override 643 public V first() { 644 refreshIfEmpty(); 645 return getSortedSetDelegate().first(); 646 } 647 648 @Override 649 public V last() { 650 refreshIfEmpty(); 651 return getSortedSetDelegate().last(); 652 } 653 654 @Override 655 public SortedSet<V> headSet(V toElement) { 656 refreshIfEmpty(); 657 return new WrappedSortedSet( 658 getKey(), getSortedSetDelegate().headSet(toElement), 659 (getAncestor() == null) ? this : getAncestor()); 660 } 661 662 @Override 663 public SortedSet<V> subSet(V fromElement, V toElement) { 664 refreshIfEmpty(); 665 return new WrappedSortedSet( 666 getKey(), getSortedSetDelegate().subSet(fromElement, toElement), 667 (getAncestor() == null) ? this : getAncestor()); 668 } 669 670 @Override 671 public SortedSet<V> tailSet(V fromElement) { 672 refreshIfEmpty(); 673 return new WrappedSortedSet( 674 getKey(), getSortedSetDelegate().tailSet(fromElement), 675 (getAncestor() == null) ? this : getAncestor()); 676 } 677 } 678 679 /** List decorator that stays in sync with the multimap values for a key. */ 680 private class WrappedList extends WrappedCollection implements List<V> { 681 WrappedList(@Nullable K key, List<V> delegate, 682 @Nullable WrappedCollection ancestor) { 683 super(key, delegate, ancestor); 684 } 685 686 List<V> getListDelegate() { 687 return (List<V>) getDelegate(); 688 } 689 690 @Override 691 public boolean addAll(int index, Collection<? extends V> c) { 692 if (c.isEmpty()) { 693 return false; 694 } 695 int oldSize = size(); // calls refreshIfEmpty 696 boolean changed = getListDelegate().addAll(index, c); 697 if (changed) { 698 int newSize = getDelegate().size(); 699 totalSize += (newSize - oldSize); 700 if (oldSize == 0) { 701 addToMap(); 702 } 703 } 704 return changed; 705 } 706 707 @Override 708 public V get(int index) { 709 refreshIfEmpty(); 710 return getListDelegate().get(index); 711 } 712 713 @Override 714 public V set(int index, V element) { 715 refreshIfEmpty(); 716 return getListDelegate().set(index, element); 717 } 718 719 @Override 720 public void add(int index, V element) { 721 refreshIfEmpty(); 722 boolean wasEmpty = getDelegate().isEmpty(); 723 getListDelegate().add(index, element); 724 totalSize++; 725 if (wasEmpty) { 726 addToMap(); 727 } 728 } 729 730 @Override 731 public V remove(int index) { 732 refreshIfEmpty(); 733 V value = getListDelegate().remove(index); 734 totalSize--; 735 removeIfEmpty(); 736 return value; 737 } 738 739 @Override 740 public int indexOf(Object o) { 741 refreshIfEmpty(); 742 return getListDelegate().indexOf(o); 743 } 744 745 @Override 746 public int lastIndexOf(Object o) { 747 refreshIfEmpty(); 748 return getListDelegate().lastIndexOf(o); 749 } 750 751 @Override 752 public ListIterator<V> listIterator() { 753 refreshIfEmpty(); 754 return new WrappedListIterator(); 755 } 756 757 @Override 758 public ListIterator<V> listIterator(int index) { 759 refreshIfEmpty(); 760 return new WrappedListIterator(index); 761 } 762 763 @Override 764 public List<V> subList(int fromIndex, int toIndex) { 765 refreshIfEmpty(); 766 return wrapList(getKey(), 767 getListDelegate().subList(fromIndex, toIndex), 768 (getAncestor() == null) ? this : getAncestor()); 769 } 770 771 /** ListIterator decorator. */ 772 private class WrappedListIterator extends WrappedIterator 773 implements ListIterator<V> { 774 WrappedListIterator() {} 775 776 public WrappedListIterator(int index) { 777 super(getListDelegate().listIterator(index)); 778 } 779 780 private ListIterator<V> getDelegateListIterator() { 781 return (ListIterator<V>) getDelegateIterator(); 782 } 783 784 @Override 785 public boolean hasPrevious() { 786 return getDelegateListIterator().hasPrevious(); 787 } 788 789 @Override 790 public V previous() { 791 return getDelegateListIterator().previous(); 792 } 793 794 @Override 795 public int nextIndex() { 796 return getDelegateListIterator().nextIndex(); 797 } 798 799 @Override 800 public int previousIndex() { 801 return getDelegateListIterator().previousIndex(); 802 } 803 804 @Override 805 public void set(V value) { 806 getDelegateListIterator().set(value); 807 } 808 809 @Override 810 public void add(V value) { 811 boolean wasEmpty = isEmpty(); 812 getDelegateListIterator().add(value); 813 totalSize++; 814 if (wasEmpty) { 815 addToMap(); 816 } 817 } 818 } 819 } 820 821 /** 822 * List decorator that stays in sync with the multimap values for a key and 823 * supports rapid random access. 824 */ 825 private class RandomAccessWrappedList extends WrappedList 826 implements RandomAccess { 827 RandomAccessWrappedList(@Nullable K key, List<V> delegate, 828 @Nullable WrappedCollection ancestor) { 829 super(key, delegate, ancestor); 830 } 831 } 832 833 @Override 834 Set<K> createKeySet() { 835 // TreeMultimap uses NavigableKeySet explicitly, but we don't handle that here for GWT 836 // compatibility reasons 837 return (map instanceof SortedMap) 838 ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map); 839 } 840 841 private class KeySet extends Maps.KeySet<K, Collection<V>> { 842 KeySet(final Map<K, Collection<V>> subMap) { 843 super(subMap); 844 } 845 846 @Override public Iterator<K> iterator() { 847 final Iterator<Map.Entry<K, Collection<V>>> entryIterator 848 = map().entrySet().iterator(); 849 return new Iterator<K>() { 850 Map.Entry<K, Collection<V>> entry; 851 852 @Override 853 public boolean hasNext() { 854 return entryIterator.hasNext(); 855 } 856 @Override 857 public K next() { 858 entry = entryIterator.next(); 859 return entry.getKey(); 860 } 861 @Override 862 public void remove() { 863 checkRemove(entry != null); 864 Collection<V> collection = entry.getValue(); 865 entryIterator.remove(); 866 totalSize -= collection.size(); 867 collection.clear(); 868 } 869 }; 870 } 871 872 // The following methods are included for better performance. 873 874 @Override public boolean remove(Object key) { 875 int count = 0; 876 Collection<V> collection = map().remove(key); 877 if (collection != null) { 878 count = collection.size(); 879 collection.clear(); 880 totalSize -= count; 881 } 882 return count > 0; 883 } 884 885 @Override 886 public void clear() { 887 Iterators.clear(iterator()); 888 } 889 890 @Override public boolean containsAll(Collection<?> c) { 891 return map().keySet().containsAll(c); 892 } 893 894 @Override public boolean equals(@Nullable Object object) { 895 return this == object || this.map().keySet().equals(object); 896 } 897 898 @Override public int hashCode() { 899 return map().keySet().hashCode(); 900 } 901 } 902 903 private class SortedKeySet extends KeySet implements SortedSet<K> { 904 905 SortedKeySet(SortedMap<K, Collection<V>> subMap) { 906 super(subMap); 907 } 908 909 SortedMap<K, Collection<V>> sortedMap() { 910 return (SortedMap<K, Collection<V>>) super.map(); 911 } 912 913 @Override 914 public Comparator<? super K> comparator() { 915 return sortedMap().comparator(); 916 } 917 918 @Override 919 public K first() { 920 return sortedMap().firstKey(); 921 } 922 923 @Override 924 public SortedSet<K> headSet(K toElement) { 925 return new SortedKeySet(sortedMap().headMap(toElement)); 926 } 927 928 @Override 929 public K last() { 930 return sortedMap().lastKey(); 931 } 932 933 @Override 934 public SortedSet<K> subSet(K fromElement, K toElement) { 935 return new SortedKeySet(sortedMap().subMap(fromElement, toElement)); 936 } 937 938 @Override 939 public SortedSet<K> tailSet(K fromElement) { 940 return new SortedKeySet(sortedMap().tailMap(fromElement)); 941 } 942 } 943 944 /** 945 * Removes all values for the provided key. Unlike {@link #removeAll}, it 946 * returns the number of removed mappings. 947 */ 948 private int removeValuesForKey(Object key) { 949 Collection<V> collection = Maps.safeRemove(map, key); 950 951 int count = 0; 952 if (collection != null) { 953 count = collection.size(); 954 collection.clear(); 955 totalSize -= count; 956 } 957 return count; 958 } 959 960 private abstract class Itr<T> implements Iterator<T> { 961 final Iterator<Map.Entry<K, Collection<V>>> keyIterator; 962 K key; 963 Collection<V> collection; 964 Iterator<V> valueIterator; 965 966 Itr() { 967 keyIterator = map.entrySet().iterator(); 968 key = null; 969 collection = null; 970 valueIterator = Iterators.emptyModifiableIterator(); 971 } 972 973 abstract T output(K key, V value); 974 975 @Override 976 public boolean hasNext() { 977 return keyIterator.hasNext() || valueIterator.hasNext(); 978 } 979 980 @Override 981 public T next() { 982 if (!valueIterator.hasNext()) { 983 Map.Entry<K, Collection<V>> mapEntry = keyIterator.next(); 984 key = mapEntry.getKey(); 985 collection = mapEntry.getValue(); 986 valueIterator = collection.iterator(); 987 } 988 return output(key, valueIterator.next()); 989 } 990 991 @Override 992 public void remove() { 993 valueIterator.remove(); 994 if (collection.isEmpty()) { 995 keyIterator.remove(); 996 } 997 totalSize--; 998 } 999 } 1000 1001 /** 1002 * {@inheritDoc} 1003 * 1004 * <p>The iterator generated by the returned collection traverses the values 1005 * for one key, followed by the values of a second key, and so on. 1006 */ 1007 @Override public Collection<V> values() { 1008 return super.values(); 1009 } 1010 1011 @Override 1012 Iterator<V> valueIterator() { 1013 return new Itr<V>() { 1014 @Override 1015 V output(K key, V value) { 1016 return value; 1017 } 1018 }; 1019 } 1020 1021 /* 1022 * TODO(kevinb): should we copy this javadoc to each concrete class, so that 1023 * classes like LinkedHashMultimap that need to say something different are 1024 * still able to {@inheritDoc} all the way from Multimap? 1025 */ 1026 1027 /** 1028 * {@inheritDoc} 1029 * 1030 * <p>The iterator generated by the returned collection traverses the values 1031 * for one key, followed by the values of a second key, and so on. 1032 * 1033 * <p>Each entry is an immutable snapshot of a key-value mapping in the 1034 * multimap, taken at the time the entry is returned by a method call to the 1035 * collection or its iterator. 1036 */ 1037 @Override 1038 public Collection<Map.Entry<K, V>> entries() { 1039 return super.entries(); 1040 } 1041 1042 /** 1043 * Returns an iterator across all key-value map entries, used by {@code 1044 * entries().iterator()} and {@code values().iterator()}. The default 1045 * behavior, which traverses the values for one key, the values for a second 1046 * key, and so on, suffices for most {@code AbstractMapBasedMultimap} implementations. 1047 * 1048 * @return an iterator across map entries 1049 */ 1050 @Override 1051 Iterator<Map.Entry<K, V>> entryIterator() { 1052 return new Itr<Map.Entry<K, V>>() { 1053 @Override 1054 Entry<K, V> output(K key, V value) { 1055 return Maps.immutableEntry(key, value); 1056 } 1057 }; 1058 } 1059 1060 @Override 1061 Map<K, Collection<V>> createAsMap() { 1062 // TreeMultimap uses NavigableAsMap explicitly, but we don't handle that here for GWT 1063 // compatibility reasons 1064 return (map instanceof SortedMap) 1065 ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map); 1066 } 1067 1068 private class AsMap extends ImprovedAbstractMap<K, Collection<V>> { 1069 /** 1070 * Usually the same as map, but smaller for the headMap(), tailMap(), or 1071 * subMap() of a SortedAsMap. 1072 */ 1073 final transient Map<K, Collection<V>> submap; 1074 1075 AsMap(Map<K, Collection<V>> submap) { 1076 this.submap = submap; 1077 } 1078 1079 @Override 1080 protected Set<Entry<K, Collection<V>>> createEntrySet() { 1081 return new AsMapEntries(); 1082 } 1083 1084 // The following methods are included for performance. 1085 1086 @Override public boolean containsKey(Object key) { 1087 return Maps.safeContainsKey(submap, key); 1088 } 1089 1090 @Override public Collection<V> get(Object key) { 1091 Collection<V> collection = Maps.safeGet(submap, key); 1092 if (collection == null) { 1093 return null; 1094 } 1095 @SuppressWarnings("unchecked") 1096 K k = (K) key; 1097 return wrapCollection(k, collection); 1098 } 1099 1100 @Override public Set<K> keySet() { 1101 return AbstractMapBasedMultimap.this.keySet(); 1102 } 1103 1104 @Override 1105 public int size() { 1106 return submap.size(); 1107 } 1108 1109 @Override public Collection<V> remove(Object key) { 1110 Collection<V> collection = submap.remove(key); 1111 if (collection == null) { 1112 return null; 1113 } 1114 1115 Collection<V> output = createCollection(); 1116 output.addAll(collection); 1117 totalSize -= collection.size(); 1118 collection.clear(); 1119 return output; 1120 } 1121 1122 @Override public boolean equals(@Nullable Object object) { 1123 return this == object || submap.equals(object); 1124 } 1125 1126 @Override public int hashCode() { 1127 return submap.hashCode(); 1128 } 1129 1130 @Override public String toString() { 1131 return submap.toString(); 1132 } 1133 1134 @Override 1135 public void clear() { 1136 if (submap == map) { 1137 AbstractMapBasedMultimap.this.clear(); 1138 } else { 1139 Iterators.clear(new AsMapIterator()); 1140 } 1141 } 1142 1143 Entry<K, Collection<V>> wrapEntry(Entry<K, Collection<V>> entry) { 1144 K key = entry.getKey(); 1145 return Maps.immutableEntry(key, wrapCollection(key, entry.getValue())); 1146 } 1147 1148 class AsMapEntries extends Maps.EntrySet<K, Collection<V>> { 1149 @Override 1150 Map<K, Collection<V>> map() { 1151 return AsMap.this; 1152 } 1153 1154 @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { 1155 return new AsMapIterator(); 1156 } 1157 1158 // The following methods are included for performance. 1159 1160 @Override public boolean contains(Object o) { 1161 return Collections2.safeContains(submap.entrySet(), o); 1162 } 1163 1164 @Override public boolean remove(Object o) { 1165 if (!contains(o)) { 1166 return false; 1167 } 1168 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1169 removeValuesForKey(entry.getKey()); 1170 return true; 1171 } 1172 } 1173 1174 /** Iterator across all keys and value collections. */ 1175 class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> { 1176 final Iterator<Map.Entry<K, Collection<V>>> delegateIterator 1177 = submap.entrySet().iterator(); 1178 Collection<V> collection; 1179 1180 @Override 1181 public boolean hasNext() { 1182 return delegateIterator.hasNext(); 1183 } 1184 1185 @Override 1186 public Map.Entry<K, Collection<V>> next() { 1187 Map.Entry<K, Collection<V>> entry = delegateIterator.next(); 1188 collection = entry.getValue(); 1189 return wrapEntry(entry); 1190 } 1191 1192 @Override 1193 public void remove() { 1194 delegateIterator.remove(); 1195 totalSize -= collection.size(); 1196 collection.clear(); 1197 } 1198 } 1199 } 1200 1201 private class SortedAsMap extends AsMap 1202 implements SortedMap<K, Collection<V>> { 1203 SortedAsMap(SortedMap<K, Collection<V>> submap) { 1204 super(submap); 1205 } 1206 1207 SortedMap<K, Collection<V>> sortedMap() { 1208 return (SortedMap<K, Collection<V>>) submap; 1209 } 1210 1211 @Override 1212 public Comparator<? super K> comparator() { 1213 return sortedMap().comparator(); 1214 } 1215 1216 @Override 1217 public K firstKey() { 1218 return sortedMap().firstKey(); 1219 } 1220 1221 @Override 1222 public K lastKey() { 1223 return sortedMap().lastKey(); 1224 } 1225 1226 @Override 1227 public SortedMap<K, Collection<V>> headMap(K toKey) { 1228 return new SortedAsMap(sortedMap().headMap(toKey)); 1229 } 1230 1231 @Override 1232 public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) { 1233 return new SortedAsMap(sortedMap().subMap(fromKey, toKey)); 1234 } 1235 1236 @Override 1237 public SortedMap<K, Collection<V>> tailMap(K fromKey) { 1238 return new SortedAsMap(sortedMap().tailMap(fromKey)); 1239 } 1240 1241 SortedSet<K> sortedKeySet; 1242 1243 // returns a SortedSet, even though returning a Set would be sufficient to 1244 // satisfy the SortedMap.keySet() interface 1245 @Override public SortedSet<K> keySet() { 1246 SortedSet<K> result = sortedKeySet; 1247 return (result == null) ? sortedKeySet = createKeySet() : result; 1248 } 1249 1250 @Override 1251 SortedSet<K> createKeySet() { 1252 return new SortedKeySet(sortedMap()); 1253 } 1254 } 1255 1256 private static final long serialVersionUID = 2447537837011683357L; 1257} 1258