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