1 /* 2 * Copyright (C) 2007 Google Inc. 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 17 package com.google.common.collect; 18 19 import com.google.common.annotations.GwtCompatible; 20 import com.google.common.annotations.GwtIncompatible; 21 import static com.google.common.base.Preconditions.checkArgument; 22 import static com.google.common.base.Preconditions.checkNotNull; 23 import static com.google.common.base.Preconditions.checkState; 24 25 import java.io.Serializable; 26 import java.util.AbstractCollection; 27 import java.util.AbstractMap; 28 import java.util.AbstractSet; 29 import java.util.Collection; 30 import java.util.Collections; 31 import java.util.Comparator; 32 import java.util.ConcurrentModificationException; 33 import java.util.Iterator; 34 import java.util.List; 35 import java.util.ListIterator; 36 import java.util.Map; 37 import java.util.RandomAccess; 38 import java.util.Set; 39 import java.util.SortedMap; 40 import java.util.SortedSet; 41 42 import 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 AbstractMultimap} 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 */ 86 @GwtCompatible 87 abstract class AbstractMultimap<K, V> implements Multimap<K, V>, Serializable { 88 /* 89 * Here's an outline of the overall design. 90 * 91 * The map variable contains the collection of values associated with each 92 * key. When a key-value pair is added to a multimap that didn't previously 93 * contain any values for that key, a new collection generated by 94 * createCollection is added to the map. That same collection instance 95 * remains in the map as long as the multimap has any values for the key. If 96 * all values for the key are removed, the key and collection are removed 97 * from the map. 98 * 99 * The get method returns a WrappedCollection, which decorates the collection 100 * in the map (if the key is present) or an empty collection (if the key is 101 * not present). When the collection delegate in the WrappedCollection is 102 * empty, the multimap may contain subsequently added values for that key. To 103 * handle that situation, the WrappedCollection checks whether map contains 104 * an entry for the provided key, and if so replaces the delegate. 105 */ 106 107 private transient Map<K, Collection<V>> map; 108 private transient int totalSize; 109 110 /** 111 * Creates a new multimap that uses the provided map. 112 * 113 * @param map place to store the mapping from each key to its corresponding 114 * values 115 * @throws IllegalArgumentException if {@code map} is not empty 116 */ 117 protected AbstractMultimap(Map<K, Collection<V>> map) { 118 checkArgument(map.isEmpty()); 119 this.map = map; 120 } 121 122 /** Used during deserialization only. */ 123 final void setMap(Map<K, Collection<V>> map) { 124 this.map = map; 125 totalSize = 0; 126 for (Collection<V> values : map.values()) { 127 checkArgument(!values.isEmpty()); 128 totalSize += values.size(); 129 } 130 } 131 132 /** 133 * Creates the collection of values for a single key. 134 * 135 * <p>Collections with weak, soft, or phantom references are not supported. 136 * Each call to {@code createCollection} should create a new instance. 137 * 138 * <p>The returned collection class determines whether duplicate key-value 139 * pairs are allowed. 140 * 141 * @return an empty collection of values 142 */ 143 abstract Collection<V> createCollection(); 144 145 /** 146 * Creates the collection of values for an explicitly provided key. By 147 * default, it simply calls {@link #createCollection()}, which is the correct 148 * behavior for most implementations. The {@link LinkedHashMultimap} class 149 * overrides it. 150 * 151 * @param key key to associate with values in the collection 152 * @return an empty collection of values 153 */ 154 Collection<V> createCollection(@Nullable K key) { 155 return createCollection(); 156 } 157 158 Map<K, Collection<V>> backingMap() { 159 return map; 160 } 161 162 // Query Operations 163 164 public int size() { 165 return totalSize; 166 } 167 168 public boolean isEmpty() { 169 return totalSize == 0; 170 } 171 172 public boolean containsKey(@Nullable Object key) { 173 return map.containsKey(key); 174 } 175 176 public boolean containsValue(@Nullable Object value) { 177 for (Collection<V> collection : map.values()) { 178 if (collection.contains(value)) { 179 return true; 180 } 181 } 182 183 return false; 184 } 185 186 public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 187 Collection<V> collection = map.get(key); 188 return collection != null && collection.contains(value); 189 } 190 191 // Modification Operations 192 193 public boolean put(@Nullable K key, @Nullable V value) { 194 Collection<V> collection = getOrCreateCollection(key); 195 196 if (collection.add(value)) { 197 totalSize++; 198 return true; 199 } else { 200 return false; 201 } 202 } 203 204 private Collection<V> getOrCreateCollection(@Nullable K key) { 205 Collection<V> collection = map.get(key); 206 if (collection == null) { 207 collection = createCollection(key); 208 map.put(key, collection); 209 } 210 return collection; 211 } 212 213 public boolean remove(@Nullable Object key, @Nullable Object value) { 214 Collection<V> collection = map.get(key); 215 if (collection == null) { 216 return false; 217 } 218 219 boolean changed = collection.remove(value); 220 if (changed) { 221 totalSize--; 222 if (collection.isEmpty()) { 223 map.remove(key); 224 } 225 } 226 return changed; 227 } 228 229 // Bulk Operations 230 231 public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 232 if (!values.iterator().hasNext()) { 233 return false; 234 } 235 Collection<V> collection = getOrCreateCollection(key); 236 int oldSize = collection.size(); 237 238 boolean changed = false; 239 if (values instanceof Collection) { 240 @SuppressWarnings("unchecked") 241 Collection<? extends V> c = (Collection<? extends V>) values; 242 changed = collection.addAll(c); 243 } else { 244 for (V value : values) { 245 changed |= collection.add(value); 246 } 247 } 248 249 totalSize += (collection.size() - oldSize); 250 return changed; 251 } 252 253 public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 254 boolean changed = false; 255 for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) { 256 changed |= put(entry.getKey(), entry.getValue()); 257 } 258 return changed; 259 } 260 261 /** 262 * {@inheritDoc} 263 * 264 * <p>The returned collection is immutable. 265 */ 266 public Collection<V> replaceValues( 267 @Nullable K key, Iterable<? extends V> values) { 268 Iterator<? extends V> iterator = values.iterator(); 269 if (!iterator.hasNext()) { 270 return removeAll(key); 271 } 272 273 Collection<V> collection = getOrCreateCollection(key); 274 Collection<V> oldValues = createCollection(); 275 oldValues.addAll(collection); 276 277 totalSize -= collection.size(); 278 collection.clear(); 279 280 while (iterator.hasNext()) { 281 if (collection.add(iterator.next())) { 282 totalSize++; 283 } 284 } 285 286 return unmodifiableCollectionSubclass(oldValues); 287 } 288 289 /** 290 * {@inheritDoc} 291 * 292 * <p>The returned collection is immutable. 293 */ 294 public Collection<V> removeAll(@Nullable Object key) { 295 Collection<V> collection = map.remove(key); 296 Collection<V> output = createCollection(); 297 298 if (collection != null) { 299 output.addAll(collection); 300 totalSize -= collection.size(); 301 collection.clear(); 302 } 303 304 return unmodifiableCollectionSubclass(output); 305 } 306 307 private Collection<V> unmodifiableCollectionSubclass( 308 Collection<V> collection) { 309 if (collection instanceof SortedSet) { 310 return Collections.unmodifiableSortedSet((SortedSet<V>) collection); 311 } else if (collection instanceof Set) { 312 return Collections.unmodifiableSet((Set<V>) collection); 313 } else if (collection instanceof List) { 314 return Collections.unmodifiableList((List<V>) collection); 315 } else { 316 return Collections.unmodifiableCollection(collection); 317 } 318 } 319 320 public void clear() { 321 // Clear each collection, to make previously returned collections empty. 322 for (Collection<V> collection : map.values()) { 323 collection.clear(); 324 } 325 map.clear(); 326 totalSize = 0; 327 } 328 329 // Views 330 331 /** 332 * {@inheritDoc} 333 * 334 * <p>The returned collection is not serializable. 335 */ 336 public Collection<V> get(@Nullable K key) { 337 Collection<V> collection = map.get(key); 338 if (collection == null) { 339 collection = createCollection(key); 340 } 341 return wrapCollection(key, collection); 342 } 343 344 /** 345 * Generates a decorated collection that remains consistent with the values in 346 * the multimap for the provided key. Changes to the multimap may alter the 347 * returned collection, and vice versa. 348 */ 349 private Collection<V> wrapCollection( 350 @Nullable K key, Collection<V> collection) { 351 if (collection instanceof SortedSet) { 352 return new WrappedSortedSet(key, (SortedSet<V>) collection, null); 353 } else if (collection instanceof Set) { 354 return new WrappedSet(key, (Set<V>) collection); 355 } else if (collection instanceof List) { 356 return wrapList(key, (List<V>) collection, null); 357 } else { 358 return new WrappedCollection(key, collection, null); 359 } 360 } 361 362 private List<V> wrapList( 363 K key, List<V> list, @Nullable WrappedCollection ancestor) { 364 return (list instanceof RandomAccess) 365 ? new RandomAccessWrappedList(key, list, ancestor) 366 : new WrappedList(key, list, ancestor); 367 } 368 369 /** 370 * Collection decorator that stays in sync with the multimap values for a key. 371 * There are two kinds of wrapped collections: full and subcollections. Both 372 * have a delegate pointing to the underlying collection class. 373 * 374 * <p>Full collections, identified by a null ancestor field, contain all 375 * multimap values for a given key. Its delegate is a value in {@link 376 * AbstractMultimap#map} whenever the delegate is non-empty. The {@code 377 * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure 378 * that the {@code WrappedCollection} and map remain consistent. 379 * 380 * <p>A subcollection, such as a sublist, contains some of the values for a 381 * given key. Its ancestor field points to the full wrapped collection with 382 * all values for the key. The subcollection {@code refreshIfEmpty}, {@code 383 * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods 384 * of the full wrapped collection. 385 */ 386 private class WrappedCollection extends AbstractCollection<V> { 387 final K key; 388 Collection<V> delegate; 389 final WrappedCollection ancestor; 390 final Collection<V> ancestorDelegate; 391 392 WrappedCollection(@Nullable K key, Collection<V> delegate, 393 @Nullable WrappedCollection ancestor) { 394 this.key = key; 395 this.delegate = delegate; 396 this.ancestor = ancestor; 397 this.ancestorDelegate 398 = (ancestor == null) ? null : ancestor.getDelegate(); 399 } 400 401 /** 402 * If the delegate collection is empty, but the multimap has values for the 403 * key, replace the delegate with the new collection for the key. 404 * 405 * <p>For a subcollection, refresh its ancestor and validate that the 406 * ancestor delegate hasn't changed. 407 */ 408 void refreshIfEmpty() { 409 if (ancestor != null) { 410 ancestor.refreshIfEmpty(); 411 if (ancestor.getDelegate() != ancestorDelegate) { 412 throw new ConcurrentModificationException(); 413 } 414 } else if (delegate.isEmpty()) { 415 Collection<V> newDelegate = map.get(key); 416 if (newDelegate != null) { 417 delegate = newDelegate; 418 } 419 } 420 } 421 422 /** 423 * If collection is empty, remove it from {@code map}. For subcollections, 424 * check whether the ancestor collection is empty. 425 */ 426 void removeIfEmpty() { 427 if (ancestor != null) { 428 ancestor.removeIfEmpty(); 429 } else if (delegate.isEmpty()) { 430 map.remove(key); 431 } 432 } 433 434 K getKey() { 435 return key; 436 } 437 438 /** 439 * Add the delegate to the map. Other {@code WrappedCollection} methods 440 * should call this method after adding elements to a previously empty 441 * collection. 442 * 443 * <p>Subcollection add the ancestor's delegate instead. 444 */ 445 void addToMap() { 446 if (ancestor != null) { 447 ancestor.addToMap(); 448 } else { 449 map.put(key, delegate); 450 } 451 } 452 453 @Override public int size() { 454 refreshIfEmpty(); 455 return delegate.size(); 456 } 457 458 @Override public boolean equals(@Nullable Object object) { 459 if (object == this) { 460 return true; 461 } 462 refreshIfEmpty(); 463 return delegate.equals(object); 464 } 465 466 @Override public int hashCode() { 467 refreshIfEmpty(); 468 return delegate.hashCode(); 469 } 470 471 @Override public String toString() { 472 refreshIfEmpty(); 473 return delegate.toString(); 474 } 475 476 Collection<V> getDelegate() { 477 return delegate; 478 } 479 480 @Override public Iterator<V> iterator() { 481 refreshIfEmpty(); 482 return new WrappedIterator(); 483 } 484 485 /** Collection iterator for {@code WrappedCollection}. */ 486 class WrappedIterator implements Iterator<V> { 487 final Iterator<V> delegateIterator; 488 final Collection<V> originalDelegate = delegate; 489 490 WrappedIterator() { 491 delegateIterator = iteratorOrListIterator(delegate); 492 } 493 494 WrappedIterator(Iterator<V> delegateIterator) { 495 this.delegateIterator = delegateIterator; 496 } 497 498 /** 499 * If the delegate changed since the iterator was created, the iterator is 500 * no longer valid. 501 */ 502 void validateIterator() { 503 refreshIfEmpty(); 504 if (delegate != originalDelegate) { 505 throw new ConcurrentModificationException(); 506 } 507 } 508 509 public boolean hasNext() { 510 validateIterator(); 511 return delegateIterator.hasNext(); 512 } 513 514 public V next() { 515 validateIterator(); 516 return delegateIterator.next(); 517 } 518 519 public void remove() { 520 delegateIterator.remove(); 521 totalSize--; 522 removeIfEmpty(); 523 } 524 525 Iterator<V> getDelegateIterator() { 526 validateIterator(); 527 return delegateIterator; 528 } 529 } 530 531 @Override public boolean add(V value) { 532 refreshIfEmpty(); 533 boolean wasEmpty = delegate.isEmpty(); 534 boolean changed = delegate.add(value); 535 if (changed) { 536 totalSize++; 537 if (wasEmpty) { 538 addToMap(); 539 } 540 } 541 return changed; 542 } 543 544 WrappedCollection getAncestor() { 545 return ancestor; 546 } 547 548 // The following methods are provided for better performance. 549 550 @Override public boolean addAll(Collection<? extends V> collection) { 551 if (collection.isEmpty()) { 552 return false; 553 } 554 int oldSize = size(); // calls refreshIfEmpty 555 boolean changed = delegate.addAll(collection); 556 if (changed) { 557 int newSize = delegate.size(); 558 totalSize += (newSize - oldSize); 559 if (oldSize == 0) { 560 addToMap(); 561 } 562 } 563 return changed; 564 } 565 566 @Override public boolean contains(Object o) { 567 refreshIfEmpty(); 568 return delegate.contains(o); 569 } 570 571 @Override public boolean containsAll(Collection<?> c) { 572 refreshIfEmpty(); 573 return delegate.containsAll(c); 574 } 575 576 @Override public void clear() { 577 int oldSize = size(); // calls refreshIfEmpty 578 if (oldSize == 0) { 579 return; 580 } 581 delegate.clear(); 582 totalSize -= oldSize; 583 removeIfEmpty(); // maybe shouldn't be removed if this is a sublist 584 } 585 586 @Override public boolean remove(Object o) { 587 refreshIfEmpty(); 588 boolean changed = delegate.remove(o); 589 if (changed) { 590 totalSize--; 591 removeIfEmpty(); 592 } 593 return changed; 594 } 595 596 @Override public boolean removeAll(Collection<?> c) { 597 if (c.isEmpty()) { 598 return false; 599 } 600 int oldSize = size(); // calls refreshIfEmpty 601 boolean changed = delegate.removeAll(c); 602 if (changed) { 603 int newSize = delegate.size(); 604 totalSize += (newSize - oldSize); 605 removeIfEmpty(); 606 } 607 return changed; 608 } 609 610 @Override public boolean retainAll(Collection<?> c) { 611 checkNotNull(c); 612 int oldSize = size(); // calls refreshIfEmpty 613 boolean changed = delegate.retainAll(c); 614 if (changed) { 615 int newSize = delegate.size(); 616 totalSize += (newSize - oldSize); 617 removeIfEmpty(); 618 } 619 return changed; 620 } 621 } 622 623 private Iterator<V> iteratorOrListIterator(Collection<V> collection) { 624 return (collection instanceof List) 625 ? ((List<V>) collection).listIterator() 626 : collection.iterator(); 627 } 628 629 /** Set decorator that stays in sync with the multimap values for a key. */ 630 private class WrappedSet extends WrappedCollection implements Set<V> { 631 WrappedSet(K key, Set<V> delegate) { 632 super(key, delegate, null); 633 } 634 } 635 636 /** 637 * SortedSet decorator that stays in sync with the multimap values for a key. 638 */ 639 private class WrappedSortedSet extends WrappedCollection 640 implements SortedSet<V> { 641 WrappedSortedSet(@Nullable K key, SortedSet<V> delegate, 642 @Nullable WrappedCollection ancestor) { 643 super(key, delegate, ancestor); 644 } 645 646 SortedSet<V> getSortedSetDelegate() { 647 return (SortedSet<V>) getDelegate(); 648 } 649 650 public Comparator<? super V> comparator() { 651 return getSortedSetDelegate().comparator(); 652 } 653 654 public V first() { 655 refreshIfEmpty(); 656 return getSortedSetDelegate().first(); 657 } 658 659 public V last() { 660 refreshIfEmpty(); 661 return getSortedSetDelegate().last(); 662 } 663 664 public SortedSet<V> headSet(V toElement) { 665 refreshIfEmpty(); 666 return new WrappedSortedSet( 667 getKey(), getSortedSetDelegate().headSet(toElement), 668 (getAncestor() == null) ? this : getAncestor()); 669 } 670 671 public SortedSet<V> subSet(V fromElement, V toElement) { 672 refreshIfEmpty(); 673 return new WrappedSortedSet( 674 getKey(), getSortedSetDelegate().subSet(fromElement, toElement), 675 (getAncestor() == null) ? this : getAncestor()); 676 } 677 678 public SortedSet<V> tailSet(V fromElement) { 679 refreshIfEmpty(); 680 return new WrappedSortedSet( 681 getKey(), getSortedSetDelegate().tailSet(fromElement), 682 (getAncestor() == null) ? this : getAncestor()); 683 } 684 } 685 686 /** List decorator that stays in sync with the multimap values for a key. */ 687 private class WrappedList extends WrappedCollection implements List<V> { 688 WrappedList(K key, List<V> delegate, @Nullable WrappedCollection ancestor) { 689 super(key, delegate, ancestor); 690 } 691 692 List<V> getListDelegate() { 693 return (List<V>) getDelegate(); 694 } 695 696 public boolean addAll(int index, Collection<? extends V> c) { 697 if (c.isEmpty()) { 698 return false; 699 } 700 int oldSize = size(); // calls refreshIfEmpty 701 boolean changed = getListDelegate().addAll(index, c); 702 if (changed) { 703 int newSize = getDelegate().size(); 704 totalSize += (newSize - oldSize); 705 if (oldSize == 0) { 706 addToMap(); 707 } 708 } 709 return changed; 710 } 711 712 public V get(int index) { 713 refreshIfEmpty(); 714 return getListDelegate().get(index); 715 } 716 717 public V set(int index, V element) { 718 refreshIfEmpty(); 719 return getListDelegate().set(index, element); 720 } 721 722 public void add(int index, V element) { 723 refreshIfEmpty(); 724 boolean wasEmpty = getDelegate().isEmpty(); 725 getListDelegate().add(index, element); 726 totalSize++; 727 if (wasEmpty) { 728 addToMap(); 729 } 730 } 731 732 public V remove(int index) { 733 refreshIfEmpty(); 734 V value = getListDelegate().remove(index); 735 totalSize--; 736 removeIfEmpty(); 737 return value; 738 } 739 740 public int indexOf(Object o) { 741 refreshIfEmpty(); 742 return getListDelegate().indexOf(o); 743 } 744 745 public int lastIndexOf(Object o) { 746 refreshIfEmpty(); 747 return getListDelegate().lastIndexOf(o); 748 } 749 750 public ListIterator<V> listIterator() { 751 refreshIfEmpty(); 752 return new WrappedListIterator(); 753 } 754 755 public ListIterator<V> listIterator(int index) { 756 refreshIfEmpty(); 757 return new WrappedListIterator(index); 758 } 759 760 @GwtIncompatible("List.subList") 761 public List<V> subList(int fromIndex, int toIndex) { 762 refreshIfEmpty(); 763 return wrapList(getKey(), 764 Platform.subList(getListDelegate(), fromIndex, toIndex), 765 (getAncestor() == null) ? this : getAncestor()); 766 } 767 768 /** ListIterator decorator. */ 769 private class WrappedListIterator extends WrappedIterator 770 implements ListIterator<V> { 771 WrappedListIterator() {} 772 773 public WrappedListIterator(int index) { 774 super(getListDelegate().listIterator(index)); 775 } 776 777 private ListIterator<V> getDelegateListIterator() { 778 return (ListIterator<V>) getDelegateIterator(); 779 } 780 781 public boolean hasPrevious() { 782 return getDelegateListIterator().hasPrevious(); 783 } 784 785 public V previous() { 786 return getDelegateListIterator().previous(); 787 } 788 789 public int nextIndex() { 790 return getDelegateListIterator().nextIndex(); 791 } 792 793 public int previousIndex() { 794 return getDelegateListIterator().previousIndex(); 795 } 796 797 public void set(V value) { 798 getDelegateListIterator().set(value); 799 } 800 801 public void add(V value) { 802 boolean wasEmpty = isEmpty(); 803 getDelegateListIterator().add(value); 804 totalSize++; 805 if (wasEmpty) { 806 addToMap(); 807 } 808 } 809 } 810 } 811 812 /** 813 * List decorator that stays in sync with the multimap values for a key and 814 * supports rapid random access. 815 */ 816 private class RandomAccessWrappedList extends WrappedList 817 implements RandomAccess { 818 RandomAccessWrappedList(K key, List<V> delegate, 819 @Nullable WrappedCollection ancestor) { 820 super(key, delegate, ancestor); 821 } 822 } 823 824 private transient Set<K> keySet; 825 826 public Set<K> keySet() { 827 Set<K> result = keySet; 828 return (result == null) ? keySet = createKeySet() : result; 829 } 830 831 private Set<K> createKeySet() { 832 return (map instanceof SortedMap) 833 ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map); 834 } 835 836 private class KeySet extends AbstractSet<K> { 837 838 /** 839 * This is usually the same as map, except when someone requests a 840 * subcollection of a {@link SortedKeySet}. 841 */ 842 final Map<K, Collection<V>> subMap; 843 844 KeySet(final Map<K, Collection<V>> subMap) { 845 this.subMap = subMap; 846 } 847 848 @Override public int size() { 849 return subMap.size(); 850 } 851 852 @Override public Iterator<K> iterator() { 853 return new Iterator<K>() { 854 final Iterator<Map.Entry<K, Collection<V>>> entryIterator 855 = subMap.entrySet().iterator(); 856 Map.Entry<K, Collection<V>> entry; 857 858 public boolean hasNext() { 859 return entryIterator.hasNext(); 860 } 861 public K next() { 862 entry = entryIterator.next(); 863 return entry.getKey(); 864 } 865 public void remove() { 866 checkState(entry != null); 867 Collection<V> collection = entry.getValue(); 868 entryIterator.remove(); 869 totalSize -= collection.size(); 870 collection.clear(); 871 } 872 }; 873 } 874 875 // The following methods are included for better performance. 876 877 @Override public boolean contains(Object key) { 878 return subMap.containsKey(key); 879 } 880 881 @Override public boolean remove(Object key) { 882 int count = 0; 883 Collection<V> collection = subMap.remove(key); 884 if (collection != null) { 885 count = collection.size(); 886 collection.clear(); 887 totalSize -= count; 888 } 889 return count > 0; 890 } 891 892 @Override public boolean containsAll(Collection<?> c) { 893 return subMap.keySet().containsAll(c); 894 } 895 896 @Override public boolean equals(@Nullable Object object) { 897 return this == object || this.subMap.keySet().equals(object); 898 } 899 900 @Override public int hashCode() { 901 return subMap.keySet().hashCode(); 902 } 903 } 904 905 private class SortedKeySet extends KeySet implements SortedSet<K> { 906 907 SortedKeySet(SortedMap<K, Collection<V>> subMap) { 908 super(subMap); 909 } 910 911 SortedMap<K, Collection<V>> sortedMap() { 912 return (SortedMap<K, Collection<V>>) subMap; 913 } 914 915 public Comparator<? super K> comparator() { 916 return sortedMap().comparator(); 917 } 918 919 public K first() { 920 return sortedMap().firstKey(); 921 } 922 923 public SortedSet<K> headSet(K toElement) { 924 return new SortedKeySet(sortedMap().headMap(toElement)); 925 } 926 927 public K last() { 928 return sortedMap().lastKey(); 929 } 930 931 public SortedSet<K> subSet(K fromElement, K toElement) { 932 return new SortedKeySet(sortedMap().subMap(fromElement, toElement)); 933 } 934 935 public SortedSet<K> tailSet(K fromElement) { 936 return new SortedKeySet(sortedMap().tailMap(fromElement)); 937 } 938 } 939 940 private transient Multiset<K> multiset; 941 942 public Multiset<K> keys() { 943 Multiset<K> result = multiset; 944 return (result == null) ? multiset = new MultisetView() : result; 945 } 946 947 /** Multiset view that stays in sync with the multimap keys. */ 948 private class MultisetView extends AbstractMultiset<K> { 949 950 @Override public int remove(Object key, int occurrences) { 951 if (occurrences == 0) { 952 return count(key); 953 } 954 checkArgument(occurrences > 0); 955 956 Collection<V> collection; 957 try { 958 collection = map.get(key); 959 } catch (NullPointerException e) { 960 return 0; 961 } catch (ClassCastException e) { 962 return 0; 963 } 964 965 if (collection == null) { 966 return 0; 967 } 968 int count = collection.size(); 969 970 if (occurrences >= count) { 971 return removeValuesForKey(key); 972 } 973 974 Iterator<V> iterator = collection.iterator(); 975 for (int i = 0; i < occurrences; i++) { 976 iterator.next(); 977 iterator.remove(); 978 } 979 totalSize -= occurrences; 980 return count; 981 } 982 983 @Override public Set<K> elementSet() { 984 return AbstractMultimap.this.keySet(); 985 } 986 987 transient Set<Multiset.Entry<K>> entrySet; 988 989 @Override public Set<Multiset.Entry<K>> entrySet() { 990 Set<Multiset.Entry<K>> result = entrySet; 991 return (result == null) ? entrySet = new EntrySet() : result; 992 } 993 994 private class EntrySet extends AbstractSet<Multiset.Entry<K>> { 995 @Override public Iterator<Multiset.Entry<K>> iterator() { 996 return new MultisetEntryIterator(); 997 } 998 @Override public int size() { 999 return map.size(); 1000 } 1001 1002 // The following methods are included for better performance. 1003 1004 @Override public boolean contains(Object o) { 1005 if (!(o instanceof Multiset.Entry)) { 1006 return false; 1007 } 1008 Multiset.Entry<?> entry = (Multiset.Entry<?>) o; 1009 Collection<V> collection = map.get(entry.getElement()); 1010 return (collection != null) && 1011 (collection.size() == entry.getCount()); 1012 } 1013 @Override public void clear() { 1014 AbstractMultimap.this.clear(); 1015 } 1016 @Override public boolean remove(Object o) { 1017 return contains(o) && 1018 (removeValuesForKey(((Multiset.Entry<?>) o).getElement()) > 0); 1019 } 1020 } 1021 1022 @Override public Iterator<K> iterator() { 1023 return new MultisetKeyIterator(); 1024 } 1025 1026 // The following methods are included for better performance. 1027 1028 @Override public int count(Object key) { 1029 try { 1030 Collection<V> collection = map.get(key); 1031 return (collection == null) ? 0 : collection.size(); 1032 } catch (NullPointerException e) { 1033 return 0; 1034 } catch (ClassCastException e) { 1035 return 0; 1036 } 1037 } 1038 1039 @Override public int size() { 1040 return totalSize; 1041 } 1042 1043 @Override public void clear() { 1044 AbstractMultimap.this.clear(); 1045 } 1046 } 1047 1048 /** 1049 * Removes all values for the provided key. Unlike {@link #removeAll}, it 1050 * returns the number of removed mappings. 1051 */ 1052 private int removeValuesForKey(Object key) { 1053 Collection<V> collection; 1054 try { 1055 collection = map.remove(key); 1056 } catch (NullPointerException e) { 1057 return 0; 1058 } catch (ClassCastException e) { 1059 return 0; 1060 } 1061 1062 int count = 0; 1063 if (collection != null) { 1064 count = collection.size(); 1065 collection.clear(); 1066 totalSize -= count; 1067 } 1068 return count; 1069 } 1070 1071 /** Iterator across each key, repeating once per value. */ 1072 private class MultisetEntryIterator implements Iterator<Multiset.Entry<K>> { 1073 final Iterator<Map.Entry<K, Collection<V>>> asMapIterator 1074 = asMap().entrySet().iterator(); 1075 1076 public boolean hasNext() { 1077 return asMapIterator.hasNext(); 1078 } 1079 public Multiset.Entry<K> next() { 1080 return new MultisetEntry(asMapIterator.next()); 1081 } 1082 public void remove() { 1083 asMapIterator.remove(); 1084 } 1085 } 1086 1087 private class MultisetEntry extends Multisets.AbstractEntry<K> { 1088 final Map.Entry<K, Collection<V>> entry; 1089 1090 public MultisetEntry(Map.Entry<K, Collection<V>> entry) { 1091 this.entry = entry; 1092 } 1093 public K getElement() { 1094 return entry.getKey(); 1095 } 1096 public int getCount() { 1097 return entry.getValue().size(); 1098 } 1099 } 1100 1101 /** Iterator across each key, repeating once per value. */ 1102 private class MultisetKeyIterator implements Iterator<K> { 1103 final Iterator<Map.Entry<K, V>> entryIterator = entries().iterator(); 1104 1105 public boolean hasNext() { 1106 return entryIterator.hasNext(); 1107 } 1108 public K next() { 1109 return entryIterator.next().getKey(); 1110 } 1111 public void remove() { 1112 entryIterator.remove(); 1113 } 1114 } 1115 1116 private transient Collection<V> valuesCollection; 1117 1118 /** 1119 * {@inheritDoc} 1120 * 1121 * <p>The iterator generated by the returned collection traverses the values 1122 * for one key, followed by the values of a second key, and so on. 1123 */ 1124 public Collection<V> values() { 1125 Collection<V> result = valuesCollection; 1126 return (result == null) ? valuesCollection = new Values() : result; 1127 } 1128 1129 private class Values extends AbstractCollection<V> { 1130 @Override public Iterator<V> iterator() { 1131 return new ValueIterator(); 1132 } 1133 @Override public int size() { 1134 return totalSize; 1135 } 1136 1137 // The following methods are included to improve performance. 1138 1139 @Override public void clear() { 1140 AbstractMultimap.this.clear(); 1141 } 1142 1143 @Override public boolean contains(Object value) { 1144 return containsValue(value); 1145 } 1146 } 1147 1148 /** Iterator across all values. */ 1149 private class ValueIterator implements Iterator<V> { 1150 final Iterator<Map.Entry<K, V>> entryIterator = createEntryIterator(); 1151 1152 public boolean hasNext() { 1153 return entryIterator.hasNext(); 1154 } 1155 public V next() { 1156 return entryIterator.next().getValue(); 1157 } 1158 public void remove() { 1159 entryIterator.remove(); 1160 } 1161 } 1162 1163 private transient Collection<Map.Entry<K, V>> entries; 1164 1165 // TODO: should we copy this javadoc to each concrete class, so that classes 1166 // like LinkedHashMultimap that need to say something different are still 1167 // able to {@inheritDoc} all the way from Multimap? 1168 1169 /** 1170 * {@inheritDoc} 1171 * 1172 * <p>The iterator generated by the returned collection traverses the values 1173 * for one key, followed by the values of a second key, and so on. 1174 * 1175 * <p>Each entry is an immutable snapshot of a key-value mapping in the 1176 * multimap, taken at the time the entry is returned by a method call to the 1177 * collection or its iterator. 1178 */ 1179 public Collection<Map.Entry<K, V>> entries() { 1180 Collection<Map.Entry<K, V>> result = entries; 1181 return (entries == null) ? entries = createEntries() : result; 1182 } 1183 1184 private Collection<Map.Entry<K, V>> createEntries() { 1185 // TODO: can we refactor so we're not doing "this instanceof"? 1186 return (this instanceof SetMultimap) ? new EntrySet() : new Entries(); 1187 } 1188 1189 /** Entries for multimap. */ 1190 private class Entries extends AbstractCollection<Map.Entry<K, V>> { 1191 @Override public Iterator<Map.Entry<K, V>> iterator() { 1192 return createEntryIterator(); 1193 } 1194 @Override public int size() { 1195 return totalSize; 1196 } 1197 1198 // The following methods are included to improve performance. 1199 1200 @Override public boolean contains(Object o) { 1201 if (!(o instanceof Map.Entry)) { 1202 return false; 1203 } 1204 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1205 return containsEntry(entry.getKey(), entry.getValue()); 1206 } 1207 1208 @Override public void clear() { 1209 AbstractMultimap.this.clear(); 1210 } 1211 1212 @Override public boolean remove(Object o) { 1213 if (!(o instanceof Map.Entry)) { 1214 return false; 1215 } 1216 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1217 return AbstractMultimap.this.remove(entry.getKey(), entry.getValue()); 1218 } 1219 } 1220 1221 /** 1222 * Returns an iterator across all key-value map entries, used by {@code 1223 * entries().iterator()} and {@code values().iterator()}. The default 1224 * behavior, which traverses the values for one key, the values for a second 1225 * key, and so on, suffices for most {@code AbstractMultimap} implementations. 1226 * 1227 * @return an iterator across map entries 1228 */ 1229 Iterator<Map.Entry<K, V>> createEntryIterator() { 1230 return new EntryIterator(); 1231 } 1232 1233 /** Iterator across all key-value pairs. */ 1234 private class EntryIterator implements Iterator<Map.Entry<K, V>> { 1235 final Iterator<Map.Entry<K, Collection<V>>> keyIterator; 1236 K key; 1237 Collection<V> collection; 1238 Iterator<V> valueIterator; 1239 1240 EntryIterator() { 1241 keyIterator = map.entrySet().iterator(); 1242 if (keyIterator.hasNext()) { 1243 findValueIteratorAndKey(); 1244 } else { 1245 valueIterator = Iterators.emptyModifiableIterator(); 1246 } 1247 } 1248 1249 void findValueIteratorAndKey() { 1250 Map.Entry<K, Collection<V>> entry = keyIterator.next(); 1251 key = entry.getKey(); 1252 collection = entry.getValue(); 1253 valueIterator = collection.iterator(); 1254 } 1255 1256 public boolean hasNext() { 1257 return keyIterator.hasNext() || valueIterator.hasNext(); 1258 } 1259 1260 public Map.Entry<K, V> next() { 1261 if (!valueIterator.hasNext()) { 1262 findValueIteratorAndKey(); 1263 } 1264 return Maps.immutableEntry(key, valueIterator.next()); 1265 } 1266 1267 public void remove() { 1268 valueIterator.remove(); 1269 if (collection.isEmpty()) { 1270 keyIterator.remove(); 1271 } 1272 totalSize--; 1273 } 1274 } 1275 1276 /** Entry set for a {@link SetMultimap}. */ 1277 private class EntrySet extends Entries implements Set<Map.Entry<K, V>> { 1278 @Override public boolean equals(@Nullable Object object) { 1279 return Collections2.setEquals(this, object); 1280 } 1281 @Override public int hashCode() { 1282 return Sets.hashCodeImpl(this); 1283 } 1284 } 1285 1286 private transient Map<K, Collection<V>> asMap; 1287 1288 public Map<K, Collection<V>> asMap() { 1289 Map<K, Collection<V>> result = asMap; 1290 return (result == null) ? asMap = createAsMap() : result; 1291 } 1292 1293 private Map<K, Collection<V>> createAsMap() { 1294 return (map instanceof SortedMap) 1295 ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map); 1296 } 1297 1298 private class AsMap extends AbstractMap<K, Collection<V>> { 1299 /** 1300 * Usually the same as map, but smaller for the headMap(), tailMap(), or 1301 * subMap() of a SortedAsMap. 1302 */ 1303 final transient Map<K, Collection<V>> submap; 1304 1305 AsMap(Map<K, Collection<V>> submap) { 1306 this.submap = submap; 1307 } 1308 1309 transient Set<Map.Entry<K, Collection<V>>> entrySet; 1310 1311 @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { 1312 Set<Map.Entry<K, Collection<V>>> result = entrySet; 1313 return (entrySet == null) ? entrySet = new AsMapEntries() : result; 1314 } 1315 1316 // The following methods are included for performance. 1317 1318 @Override public boolean containsKey(Object key) { 1319 return Maps.safeContainsKey(submap, key); 1320 } 1321 1322 @Override public Collection<V> get(Object key) { 1323 Collection<V> collection = Maps.safeGet(submap, key); 1324 if (collection == null) { 1325 return null; 1326 } 1327 @SuppressWarnings("unchecked") 1328 K k = (K) key; 1329 return wrapCollection(k, collection); 1330 } 1331 1332 @Override public Set<K> keySet() { 1333 return AbstractMultimap.this.keySet(); 1334 } 1335 1336 @Override public Collection<V> remove(Object key) { 1337 Collection<V> collection = submap.remove(key); 1338 if (collection == null) { 1339 return null; 1340 } 1341 1342 Collection<V> output = createCollection(); 1343 output.addAll(collection); 1344 totalSize -= collection.size(); 1345 collection.clear(); 1346 return output; 1347 } 1348 1349 @Override public boolean equals(@Nullable Object object) { 1350 return this == object || submap.equals(object); 1351 } 1352 1353 @Override public int hashCode() { 1354 return submap.hashCode(); 1355 } 1356 1357 @Override public String toString() { 1358 return submap.toString(); 1359 } 1360 1361 class AsMapEntries extends AbstractSet<Map.Entry<K, Collection<V>>> { 1362 @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { 1363 return new AsMapIterator(); 1364 } 1365 1366 @Override public int size() { 1367 return submap.size(); 1368 } 1369 1370 // The following methods are included for performance. 1371 1372 @Override public boolean contains(Object o) { 1373 return Collections2.safeContains(submap.entrySet(), o); 1374 } 1375 1376 @Override public boolean remove(Object o) { 1377 if (!contains(o)) { 1378 return false; 1379 } 1380 Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1381 removeValuesForKey(entry.getKey()); 1382 return true; 1383 } 1384 } 1385 1386 /** Iterator across all keys and value collections. */ 1387 class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> { 1388 final Iterator<Map.Entry<K, Collection<V>>> delegateIterator 1389 = submap.entrySet().iterator(); 1390 Collection<V> collection; 1391 1392 public boolean hasNext() { 1393 return delegateIterator.hasNext(); 1394 } 1395 1396 public Map.Entry<K, Collection<V>> next() { 1397 Map.Entry<K, Collection<V>> entry = delegateIterator.next(); 1398 K key = entry.getKey(); 1399 collection = entry.getValue(); 1400 return Maps.immutableEntry(key, wrapCollection(key, collection)); 1401 } 1402 1403 public void remove() { 1404 delegateIterator.remove(); 1405 totalSize -= collection.size(); 1406 collection.clear(); 1407 } 1408 } 1409 } 1410 1411 private class SortedAsMap extends AsMap 1412 implements SortedMap<K, Collection<V>> { 1413 SortedAsMap(SortedMap<K, Collection<V>> submap) { 1414 super(submap); 1415 } 1416 1417 SortedMap<K, Collection<V>> sortedMap() { 1418 return (SortedMap<K, Collection<V>>) submap; 1419 } 1420 1421 public Comparator<? super K> comparator() { 1422 return sortedMap().comparator(); 1423 } 1424 1425 public K firstKey() { 1426 return sortedMap().firstKey(); 1427 } 1428 1429 public K lastKey() { 1430 return sortedMap().lastKey(); 1431 } 1432 1433 public SortedMap<K, Collection<V>> headMap(K toKey) { 1434 return new SortedAsMap(sortedMap().headMap(toKey)); 1435 } 1436 1437 public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) { 1438 return new SortedAsMap(sortedMap().subMap(fromKey, toKey)); 1439 } 1440 1441 public SortedMap<K, Collection<V>> tailMap(K fromKey) { 1442 return new SortedAsMap(sortedMap().tailMap(fromKey)); 1443 } 1444 1445 SortedSet<K> sortedKeySet; 1446 1447 // returns a SortedSet, even though returning a Set would be sufficient to 1448 // satisfy the SortedMap.keySet() interface 1449 @Override public SortedSet<K> keySet() { 1450 SortedSet<K> result = sortedKeySet; 1451 return (result == null) 1452 ? sortedKeySet = new SortedKeySet(sortedMap()) : result; 1453 } 1454 } 1455 1456 // Comparison and hashing 1457 1458 @Override public boolean equals(@Nullable Object object) { 1459 if (object == this) { 1460 return true; 1461 } 1462 if (object instanceof Multimap) { 1463 Multimap<?, ?> that = (Multimap<?, ?>) object; 1464 return this.map.equals(that.asMap()); 1465 } 1466 return false; 1467 } 1468 1469 /** 1470 * Returns the hash code for this multimap. 1471 * 1472 * <p>The hash code of a multimap is defined as the hash code of the map view, 1473 * as returned by {@link Multimap#asMap}. 1474 * 1475 * @see Map#hashCode 1476 */ 1477 @Override public int hashCode() { 1478 return map.hashCode(); 1479 } 1480 1481 /** 1482 * Returns a string representation of the multimap, generated by calling 1483 * {@code toString} on the map returned by {@link Multimap#asMap}. 1484 * 1485 * @return a string representation of the multimap 1486 */ 1487 @Override public String toString() { 1488 return map.toString(); 1489 } 1490 1491 private static final long serialVersionUID = 2447537837011683357L; 1492 } 1493