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