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.checkNonnegative;
22 import static com.google.common.collect.CollectPreconditions.checkRemove;
23 import static java.util.Objects.requireNonNull;
24
25 import com.google.common.annotations.Beta;
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.base.Objects;
28 import com.google.common.base.Predicate;
29 import com.google.common.base.Predicates;
30 import com.google.common.collect.Multiset.Entry;
31 import com.google.common.math.IntMath;
32 import com.google.common.primitives.Ints;
33 import com.google.errorprone.annotations.CanIgnoreReturnValue;
34 import java.io.Serializable;
35 import java.util.Arrays;
36 import java.util.Collection;
37 import java.util.Collections;
38 import java.util.Comparator;
39 import java.util.Iterator;
40 import java.util.NoSuchElementException;
41 import java.util.Set;
42 import java.util.Spliterator;
43 import java.util.function.Function;
44 import java.util.function.Supplier;
45 import java.util.function.ToIntFunction;
46 import java.util.stream.Collector;
47 import javax.annotation.CheckForNull;
48 import org.checkerframework.checker.nullness.qual.Nullable;
49
50 /**
51 * Provides static utility methods for creating and working with {@link Multiset} instances.
52 *
53 * <p>See the Guava User Guide article on <a href=
54 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multisets"> {@code
55 * Multisets}</a>.
56 *
57 * @author Kevin Bourrillion
58 * @author Mike Bostock
59 * @author Louis Wasserman
60 * @since 2.0
61 */
62 @GwtCompatible
63 @ElementTypesAreNonnullByDefault
64 public final class Multisets {
65 private Multisets() {}
66
67 /**
68 * Returns a {@code Collector} that accumulates elements into a multiset created via the specified
69 * {@code Supplier}, whose elements are the result of applying {@code elementFunction} to the
70 * inputs, with counts equal to the result of applying {@code countFunction} to the inputs.
71 * Elements are added in encounter order.
72 *
73 * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the element
74 * will be added more than once, with the count summed over all appearances of the element.
75 *
76 * <p>Note that {@code stream.collect(toMultiset(function, e -> 1, supplier))} is equivalent to
77 * {@code stream.map(function).collect(Collectors.toCollection(supplier))}.
78 *
79 * <p>To collect to an {@link ImmutableMultiset}, use {@link
80 * ImmutableMultiset#toImmutableMultiset}.
81 *
82 * @since 22.0
83 */
84 public static <T extends @Nullable Object, E extends @Nullable Object, M extends Multiset<E>>
85 Collector<T, ?, M> toMultiset(
86 Function<? super T, E> elementFunction,
87 ToIntFunction<? super T> countFunction,
88 Supplier<M> multisetSupplier) {
89 return CollectCollectors.toMultiset(elementFunction, countFunction, multisetSupplier);
90 }
91
92 /**
93 * Returns an unmodifiable view of the specified multiset. Query operations on the returned
94 * multiset "read through" to the specified multiset, and attempts to modify the returned multiset
95 * result in an {@link UnsupportedOperationException}.
96 *
97 * <p>The returned multiset will be serializable if the specified multiset is serializable.
98 *
99 * @param multiset the multiset for which an unmodifiable view is to be generated
100 * @return an unmodifiable view of the multiset
101 */
102 public static <E extends @Nullable Object> Multiset<E> unmodifiableMultiset(
103 Multiset<? extends E> multiset) {
104 if (multiset instanceof UnmodifiableMultiset || multiset instanceof ImmutableMultiset) {
105 @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe
106 Multiset<E> result = (Multiset<E>) multiset;
107 return result;
108 }
109 return new UnmodifiableMultiset<E>(checkNotNull(multiset));
110 }
111
112 /**
113 * Simply returns its argument.
114 *
115 * @deprecated no need to use this
116 * @since 10.0
117 */
118 @Deprecated
119 public static <E> Multiset<E> unmodifiableMultiset(ImmutableMultiset<E> multiset) {
120 return checkNotNull(multiset);
121 }
122
123 static class UnmodifiableMultiset<E extends @Nullable Object> extends ForwardingMultiset<E>
124 implements Serializable {
125 final Multiset<? extends E> delegate;
126
127 UnmodifiableMultiset(Multiset<? extends E> delegate) {
128 this.delegate = delegate;
129 }
130
131 @SuppressWarnings("unchecked")
132 @Override
133 protected Multiset<E> delegate() {
134 // This is safe because all non-covariant methods are overridden
135 return (Multiset<E>) delegate;
136 }
137
138 @CheckForNull transient Set<E> elementSet;
139
140 Set<E> createElementSet() {
141 return Collections.<E>unmodifiableSet(delegate.elementSet());
142 }
143
144 @Override
145 public Set<E> elementSet() {
146 Set<E> es = elementSet;
147 return (es == null) ? elementSet = createElementSet() : es;
148 }
149
150 @CheckForNull transient Set<Multiset.Entry<E>> entrySet;
151
152 @SuppressWarnings("unchecked")
153 @Override
154 public Set<Multiset.Entry<E>> entrySet() {
155 Set<Multiset.Entry<E>> es = entrySet;
156 return (es == null)
157 // Safe because the returned set is made unmodifiable and Entry
158 // itself is readonly
159 ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
160 : es;
161 }
162
163 @Override
164 public Iterator<E> iterator() {
165 return Iterators.<E>unmodifiableIterator(delegate.iterator());
166 }
167
168 @Override
169 public boolean add(@ParametricNullness E element) {
170 throw new UnsupportedOperationException();
171 }
172
173 @Override
174 public int add(@ParametricNullness E element, int occurences) {
175 throw new UnsupportedOperationException();
176 }
177
178 @Override
179 public boolean addAll(Collection<? extends E> elementsToAdd) {
180 throw new UnsupportedOperationException();
181 }
182
183 @Override
184 public boolean remove(@CheckForNull Object element) {
185 throw new UnsupportedOperationException();
186 }
187
188 @Override
189 public int remove(@CheckForNull Object element, int occurrences) {
190 throw new UnsupportedOperationException();
191 }
192
193 @Override
194 public boolean removeAll(Collection<?> elementsToRemove) {
195 throw new UnsupportedOperationException();
196 }
197
198 @Override
199 public boolean retainAll(Collection<?> elementsToRetain) {
200 throw new UnsupportedOperationException();
201 }
202
203 @Override
204 public void clear() {
205 throw new UnsupportedOperationException();
206 }
207
208 @Override
209 public int setCount(@ParametricNullness E element, int count) {
210 throw new UnsupportedOperationException();
211 }
212
213 @Override
214 public boolean setCount(@ParametricNullness E element, int oldCount, int newCount) {
215 throw new UnsupportedOperationException();
216 }
217
218 private static final long serialVersionUID = 0;
219 }
220
221 /**
222 * Returns an unmodifiable view of the specified sorted multiset. Query operations on the returned
223 * multiset "read through" to the specified multiset, and attempts to modify the returned multiset
224 * result in an {@link UnsupportedOperationException}.
225 *
226 * <p>The returned multiset will be serializable if the specified multiset is serializable.
227 *
228 * @param sortedMultiset the sorted multiset for which an unmodifiable view is to be generated
229 * @return an unmodifiable view of the multiset
230 * @since 11.0
231 */
232 @Beta
233 public static <E extends @Nullable Object> SortedMultiset<E> unmodifiableSortedMultiset(
234 SortedMultiset<E> sortedMultiset) {
235 // it's in its own file so it can be emulated for GWT
236 return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset));
237 }
238
239 /**
240 * Returns an immutable multiset entry with the specified element and count. The entry will be
241 * serializable if {@code e} is.
242 *
243 * @param e the element to be associated with the returned entry
244 * @param n the count to be associated with the returned entry
245 * @throws IllegalArgumentException if {@code n} is negative
246 */
247 public static <E extends @Nullable Object> Multiset.Entry<E> immutableEntry(
248 @ParametricNullness E e, int n) {
249 return new ImmutableEntry<E>(e, n);
250 }
251
252 static class ImmutableEntry<E extends @Nullable Object> extends AbstractEntry<E>
253 implements Serializable {
254 @ParametricNullness private final E element;
255 private final int count;
256
257 ImmutableEntry(@ParametricNullness E element, int count) {
258 this.element = element;
259 this.count = count;
260 checkNonnegative(count, "count");
261 }
262
263 @Override
264 @ParametricNullness
265 public final E getElement() {
266 return element;
267 }
268
269 @Override
270 public final int getCount() {
271 return count;
272 }
273
274 @CheckForNull
275 public ImmutableEntry<E> nextInBucket() {
276 return null;
277 }
278
279 private static final long serialVersionUID = 0;
280 }
281
282 /**
283 * Returns a view of the elements of {@code unfiltered} that satisfy a predicate. The returned
284 * multiset is a live view of {@code unfiltered}; changes to one affect the other.
285 *
286 * <p>The resulting multiset's iterators, and those of its {@code entrySet()} and {@code
287 * elementSet()}, do not support {@code remove()}. However, all other multiset methods supported
288 * by {@code unfiltered} are supported by the returned multiset. When given an element that
289 * doesn't satisfy the predicate, the multiset's {@code add()} and {@code addAll()} methods throw
290 * an {@link IllegalArgumentException}. When methods such as {@code removeAll()} and {@code
291 * clear()} are called on the filtered multiset, only elements that satisfy the filter will be
292 * removed from the underlying multiset.
293 *
294 * <p>The returned multiset isn't threadsafe or serializable, even if {@code unfiltered} is.
295 *
296 * <p>Many of the filtered multiset's methods, such as {@code size()}, iterate across every
297 * element in the underlying multiset and determine which elements satisfy the filter. When a live
298 * view is <i>not</i> needed, it may be faster to copy the returned multiset and use the copy.
299 *
300 * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
301 * {@link Predicate#apply}. Do not provide a predicate such as {@code
302 * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link
303 * Iterables#filter(Iterable, Class)} for related functionality.)
304 *
305 * @since 14.0
306 */
307 @Beta
308 public static <E extends @Nullable Object> Multiset<E> filter(
309 Multiset<E> unfiltered, Predicate<? super E> predicate) {
310 if (unfiltered instanceof FilteredMultiset) {
311 // Support clear(), removeAll(), and retainAll() when filtering a filtered
312 // collection.
313 FilteredMultiset<E> filtered = (FilteredMultiset<E>) unfiltered;
314 Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
315 return new FilteredMultiset<E>(filtered.unfiltered, combinedPredicate);
316 }
317 return new FilteredMultiset<E>(unfiltered, predicate);
318 }
319
320 private static final class FilteredMultiset<E extends @Nullable Object> extends ViewMultiset<E> {
321 final Multiset<E> unfiltered;
322 final Predicate<? super E> predicate;
323
324 FilteredMultiset(Multiset<E> unfiltered, Predicate<? super E> predicate) {
325 this.unfiltered = checkNotNull(unfiltered);
326 this.predicate = checkNotNull(predicate);
327 }
328
329 @Override
330 public UnmodifiableIterator<E> iterator() {
331 return Iterators.filter(unfiltered.iterator(), predicate);
332 }
333
334 @Override
335 Set<E> createElementSet() {
336 return Sets.filter(unfiltered.elementSet(), predicate);
337 }
338
339 @Override
340 Iterator<E> elementIterator() {
341 throw new AssertionError("should never be called");
342 }
343
344 @Override
345 Set<Entry<E>> createEntrySet() {
346 return Sets.filter(
347 unfiltered.entrySet(),
348 new Predicate<Entry<E>>() {
349 @Override
350 public boolean apply(Entry<E> entry) {
351 return predicate.apply(entry.getElement());
352 }
353 });
354 }
355
356 @Override
357 Iterator<Entry<E>> entryIterator() {
358 throw new AssertionError("should never be called");
359 }
360
361 @Override
362 public int count(@CheckForNull Object element) {
363 int count = unfiltered.count(element);
364 if (count > 0) {
365 @SuppressWarnings("unchecked") // element is equal to an E
366 E e = (E) element;
367 return predicate.apply(e) ? count : 0;
368 }
369 return 0;
370 }
371
372 @Override
373 public int add(@ParametricNullness E element, int occurrences) {
374 checkArgument(
375 predicate.apply(element), "Element %s does not match predicate %s", element, predicate);
376 return unfiltered.add(element, occurrences);
377 }
378
379 @Override
380 public int remove(@CheckForNull Object element, int occurrences) {
381 checkNonnegative(occurrences, "occurrences");
382 if (occurrences == 0) {
383 return count(element);
384 } else {
385 return contains(element) ? unfiltered.remove(element, occurrences) : 0;
386 }
387 }
388 }
389
390 /**
391 * Returns the expected number of distinct elements given the specified elements. The number of
392 * distinct elements is only computed if {@code elements} is an instance of {@code Multiset};
393 * otherwise the default value of 11 is returned.
394 */
395 static int inferDistinctElements(Iterable<?> elements) {
396 if (elements instanceof Multiset) {
397 return ((Multiset<?>) elements).elementSet().size();
398 }
399 return 11; // initial capacity will be rounded up to 16
400 }
401
402 /**
403 * Returns an unmodifiable view of the union of two multisets. In the returned multiset, the count
404 * of each element is the <i>maximum</i> of its counts in the two backing multisets. The iteration
405 * order of the returned multiset matches that of the element set of {@code multiset1} followed by
406 * the members of the element set of {@code multiset2} that are not contained in {@code
407 * multiset1}, with repeated occurrences of the same element appearing consecutively.
408 *
409 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
410 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
411 *
412 * @since 14.0
413 */
414 @Beta
415 public static <E extends @Nullable Object> Multiset<E> union(
416 final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
417 checkNotNull(multiset1);
418 checkNotNull(multiset2);
419
420 return new ViewMultiset<E>() {
421 @Override
422 public boolean contains(@CheckForNull Object element) {
423 return multiset1.contains(element) || multiset2.contains(element);
424 }
425
426 @Override
427 public boolean isEmpty() {
428 return multiset1.isEmpty() && multiset2.isEmpty();
429 }
430
431 @Override
432 public int count(@CheckForNull Object element) {
433 return Math.max(multiset1.count(element), multiset2.count(element));
434 }
435
436 @Override
437 Set<E> createElementSet() {
438 return Sets.union(multiset1.elementSet(), multiset2.elementSet());
439 }
440
441 @Override
442 Iterator<E> elementIterator() {
443 throw new AssertionError("should never be called");
444 }
445
446 @Override
447 Iterator<Entry<E>> entryIterator() {
448 final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
449 final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
450 // TODO(lowasser): consider making the entries live views
451 return new AbstractIterator<Entry<E>>() {
452 @Override
453 @CheckForNull
454 protected Entry<E> computeNext() {
455 if (iterator1.hasNext()) {
456 Entry<? extends E> entry1 = iterator1.next();
457 E element = entry1.getElement();
458 int count = Math.max(entry1.getCount(), multiset2.count(element));
459 return immutableEntry(element, count);
460 }
461 while (iterator2.hasNext()) {
462 Entry<? extends E> entry2 = iterator2.next();
463 E element = entry2.getElement();
464 if (!multiset1.contains(element)) {
465 return immutableEntry(element, entry2.getCount());
466 }
467 }
468 return endOfData();
469 }
470 };
471 }
472 };
473 }
474
475 /**
476 * Returns an unmodifiable view of the intersection of two multisets. In the returned multiset,
477 * the count of each element is the <i>minimum</i> of its counts in the two backing multisets,
478 * with elements that would have a count of 0 not included. The iteration order of the returned
479 * multiset matches that of the element set of {@code multiset1}, with repeated occurrences of the
480 * same element appearing consecutively.
481 *
482 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
483 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
484 *
485 * @since 2.0
486 */
487 public static <E extends @Nullable Object> Multiset<E> intersection(
488 final Multiset<E> multiset1, final Multiset<?> multiset2) {
489 checkNotNull(multiset1);
490 checkNotNull(multiset2);
491
492 return new ViewMultiset<E>() {
493 @Override
494 public int count(@CheckForNull Object element) {
495 int count1 = multiset1.count(element);
496 return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
497 }
498
499 @Override
500 Set<E> createElementSet() {
501 return Sets.intersection(multiset1.elementSet(), multiset2.elementSet());
502 }
503
504 @Override
505 Iterator<E> elementIterator() {
506 throw new AssertionError("should never be called");
507 }
508
509 @Override
510 Iterator<Entry<E>> entryIterator() {
511 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
512 // TODO(lowasser): consider making the entries live views
513 return new AbstractIterator<Entry<E>>() {
514 @Override
515 protected Entry<E> computeNext() {
516 while (iterator1.hasNext()) {
517 Entry<E> entry1 = iterator1.next();
518 E element = entry1.getElement();
519 int count = Math.min(entry1.getCount(), multiset2.count(element));
520 if (count > 0) {
521 return immutableEntry(element, count);
522 }
523 }
524 return endOfData();
525 }
526 };
527 }
528 };
529 }
530
531 /**
532 * Returns an unmodifiable view of the sum of two multisets. In the returned multiset, the count
533 * of each element is the <i>sum</i> of its counts in the two backing multisets. The iteration
534 * order of the returned multiset matches that of the element set of {@code multiset1} followed by
535 * the members of the element set of {@code multiset2} that are not contained in {@code
536 * multiset1}, with repeated occurrences of the same element appearing consecutively.
537 *
538 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
539 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
540 *
541 * @since 14.0
542 */
543 @Beta
544 public static <E extends @Nullable Object> Multiset<E> sum(
545 final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
546 checkNotNull(multiset1);
547 checkNotNull(multiset2);
548
549 // TODO(lowasser): consider making the entries live views
550 return new ViewMultiset<E>() {
551 @Override
552 public boolean contains(@CheckForNull Object element) {
553 return multiset1.contains(element) || multiset2.contains(element);
554 }
555
556 @Override
557 public boolean isEmpty() {
558 return multiset1.isEmpty() && multiset2.isEmpty();
559 }
560
561 @Override
562 public int size() {
563 return IntMath.saturatedAdd(multiset1.size(), multiset2.size());
564 }
565
566 @Override
567 public int count(@CheckForNull Object element) {
568 return multiset1.count(element) + multiset2.count(element);
569 }
570
571 @Override
572 Set<E> createElementSet() {
573 return Sets.union(multiset1.elementSet(), multiset2.elementSet());
574 }
575
576 @Override
577 Iterator<E> elementIterator() {
578 throw new AssertionError("should never be called");
579 }
580
581 @Override
582 Iterator<Entry<E>> entryIterator() {
583 final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
584 final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
585 return new AbstractIterator<Entry<E>>() {
586 @Override
587 protected Entry<E> computeNext() {
588 if (iterator1.hasNext()) {
589 Entry<? extends E> entry1 = iterator1.next();
590 E element = entry1.getElement();
591 int count = entry1.getCount() + multiset2.count(element);
592 return immutableEntry(element, count);
593 }
594 while (iterator2.hasNext()) {
595 Entry<? extends E> entry2 = iterator2.next();
596 E element = entry2.getElement();
597 if (!multiset1.contains(element)) {
598 return immutableEntry(element, entry2.getCount());
599 }
600 }
601 return endOfData();
602 }
603 };
604 }
605 };
606 }
607
608 /**
609 * Returns an unmodifiable view of the difference of two multisets. In the returned multiset, the
610 * count of each element is the result of the <i>zero-truncated subtraction</i> of its count in
611 * the second multiset from its count in the first multiset, with elements that would have a count
612 * of 0 not included. The iteration order of the returned multiset matches that of the element set
613 * of {@code multiset1}, with repeated occurrences of the same element appearing consecutively.
614 *
615 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
616 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
617 *
618 * @since 14.0
619 */
620 @Beta
621 public static <E extends @Nullable Object> Multiset<E> difference(
622 final Multiset<E> multiset1, final Multiset<?> multiset2) {
623 checkNotNull(multiset1);
624 checkNotNull(multiset2);
625
626 // TODO(lowasser): consider making the entries live views
627 return new ViewMultiset<E>() {
628 @Override
629 public int count(@CheckForNull Object element) {
630 int count1 = multiset1.count(element);
631 return (count1 == 0) ? 0 : Math.max(0, count1 - multiset2.count(element));
632 }
633
634 @Override
635 public void clear() {
636 throw new UnsupportedOperationException();
637 }
638
639 @Override
640 Iterator<E> elementIterator() {
641 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
642 return new AbstractIterator<E>() {
643 @Override
644 @ParametricNullness
645 protected E computeNext() {
646 while (iterator1.hasNext()) {
647 Entry<E> entry1 = iterator1.next();
648 E element = entry1.getElement();
649 if (entry1.getCount() > multiset2.count(element)) {
650 return element;
651 }
652 }
653 return endOfData();
654 }
655 };
656 }
657
658 @Override
659 Iterator<Entry<E>> entryIterator() {
660 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
661 return new AbstractIterator<Entry<E>>() {
662 @Override
663 protected Entry<E> computeNext() {
664 while (iterator1.hasNext()) {
665 Entry<E> entry1 = iterator1.next();
666 E element = entry1.getElement();
667 int count = entry1.getCount() - multiset2.count(element);
668 if (count > 0) {
669 return immutableEntry(element, count);
670 }
671 }
672 return endOfData();
673 }
674 };
675 }
676
677 @Override
678 int distinctElements() {
679 return Iterators.size(entryIterator());
680 }
681 };
682 }
683
684 /**
685 * Returns {@code true} if {@code subMultiset.count(o) <= superMultiset.count(o)} for all {@code
686 * o}.
687 *
688 * @since 10.0
689 */
690 @CanIgnoreReturnValue
691 public static boolean containsOccurrences(Multiset<?> superMultiset, Multiset<?> subMultiset) {
692 checkNotNull(superMultiset);
693 checkNotNull(subMultiset);
694 for (Entry<?> entry : subMultiset.entrySet()) {
695 int superCount = superMultiset.count(entry.getElement());
696 if (superCount < entry.getCount()) {
697 return false;
698 }
699 }
700 return true;
701 }
702
703 /**
704 * Modifies {@code multisetToModify} so that its count for an element {@code e} is at most {@code
705 * multisetToRetain.count(e)}.
706 *
707 * <p>To be precise, {@code multisetToModify.count(e)} is set to {@code
708 * Math.min(multisetToModify.count(e), multisetToRetain.count(e))}. This is similar to {@link
709 * #intersection(Multiset, Multiset) intersection} {@code (multisetToModify, multisetToRetain)},
710 * but mutates {@code multisetToModify} instead of returning a view.
711 *
712 * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps all occurrences of
713 * elements that appear at all in {@code multisetToRetain}, and deletes all occurrences of all
714 * other elements.
715 *
716 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
717 * @since 10.0
718 */
719 @CanIgnoreReturnValue
720 public static boolean retainOccurrences(
721 Multiset<?> multisetToModify, Multiset<?> multisetToRetain) {
722 return retainOccurrencesImpl(multisetToModify, multisetToRetain);
723 }
724
725 /** Delegate implementation which cares about the element type. */
726 private static <E extends @Nullable Object> boolean retainOccurrencesImpl(
727 Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) {
728 checkNotNull(multisetToModify);
729 checkNotNull(occurrencesToRetain);
730 // Avoiding ConcurrentModificationExceptions is tricky.
731 Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
732 boolean changed = false;
733 while (entryIterator.hasNext()) {
734 Entry<E> entry = entryIterator.next();
735 int retainCount = occurrencesToRetain.count(entry.getElement());
736 if (retainCount == 0) {
737 entryIterator.remove();
738 changed = true;
739 } else if (retainCount < entry.getCount()) {
740 multisetToModify.setCount(entry.getElement(), retainCount);
741 changed = true;
742 }
743 }
744 return changed;
745 }
746
747 /**
748 * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one
749 * occurrence of {@code e} in {@code multisetToModify}.
750 *
751 * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code
752 * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) -
753 * Iterables.frequency(occurrencesToRemove, e))}.
754 *
755 * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll
756 * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear
757 * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit
758 * sometimes more efficient than, the following:
759 *
760 * <pre>{@code
761 * for (E e : occurrencesToRemove) {
762 * multisetToModify.remove(e);
763 * }
764 * }</pre>
765 *
766 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
767 * @since 18.0 (present in 10.0 with a requirement that the second parameter be a {@code
768 * Multiset})
769 */
770 @CanIgnoreReturnValue
771 public static boolean removeOccurrences(
772 Multiset<?> multisetToModify, Iterable<?> occurrencesToRemove) {
773 if (occurrencesToRemove instanceof Multiset) {
774 return removeOccurrences(multisetToModify, (Multiset<?>) occurrencesToRemove);
775 } else {
776 checkNotNull(multisetToModify);
777 checkNotNull(occurrencesToRemove);
778 boolean changed = false;
779 for (Object o : occurrencesToRemove) {
780 changed |= multisetToModify.remove(o);
781 }
782 return changed;
783 }
784 }
785
786 /**
787 * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one
788 * occurrence of {@code e} in {@code multisetToModify}.
789 *
790 * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code
791 * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) -
792 * occurrencesToRemove.count(e))}.
793 *
794 * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll
795 * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear
796 * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit
797 * sometimes more efficient than, the following:
798 *
799 * <pre>{@code
800 * for (E e : occurrencesToRemove) {
801 * multisetToModify.remove(e);
802 * }
803 * }</pre>
804 *
805 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
806 * @since 10.0 (missing in 18.0 when only the overload taking an {@code Iterable} was present)
807 */
808 @CanIgnoreReturnValue
809 public static boolean removeOccurrences(
810 Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) {
811 checkNotNull(multisetToModify);
812 checkNotNull(occurrencesToRemove);
813
814 boolean changed = false;
815 Iterator<? extends Entry<?>> entryIterator = multisetToModify.entrySet().iterator();
816 while (entryIterator.hasNext()) {
817 Entry<?> entry = entryIterator.next();
818 int removeCount = occurrencesToRemove.count(entry.getElement());
819 if (removeCount >= entry.getCount()) {
820 entryIterator.remove();
821 changed = true;
822 } else if (removeCount > 0) {
823 multisetToModify.remove(entry.getElement(), removeCount);
824 changed = true;
825 }
826 }
827 return changed;
828 }
829
830 /**
831 * Implementation of the {@code equals}, {@code hashCode}, and {@code toString} methods of {@link
832 * Multiset.Entry}.
833 */
834 abstract static class AbstractEntry<E extends @Nullable Object> implements Multiset.Entry<E> {
835 /**
836 * Indicates whether an object equals this entry, following the behavior specified in {@link
837 * Multiset.Entry#equals}.
838 */
839 @Override
840 public boolean equals(@CheckForNull Object object) {
841 if (object instanceof Multiset.Entry) {
842 Multiset.Entry<?> that = (Multiset.Entry<?>) object;
843 return this.getCount() == that.getCount()
844 && Objects.equal(this.getElement(), that.getElement());
845 }
846 return false;
847 }
848
849 /**
850 * Return this entry's hash code, following the behavior specified in {@link
851 * Multiset.Entry#hashCode}.
852 */
853 @Override
854 public int hashCode() {
855 E e = getElement();
856 return ((e == null) ? 0 : e.hashCode()) ^ getCount();
857 }
858
859 /**
860 * Returns a string representation of this multiset entry. The string representation consists of
861 * the associated element if the associated count is one, and otherwise the associated element
862 * followed by the characters " x " (space, x and space) followed by the count. Elements and
863 * counts are converted to strings as by {@code String.valueOf}.
864 */
865 @Override
866 public String toString() {
867 String text = String.valueOf(getElement());
868 int n = getCount();
869 return (n == 1) ? text : (text + " x " + n);
870 }
871 }
872
873 /** An implementation of {@link Multiset#equals}. */
874 static boolean equalsImpl(Multiset<?> multiset, @CheckForNull Object object) {
875 if (object == multiset) {
876 return true;
877 }
878 if (object instanceof Multiset) {
879 Multiset<?> that = (Multiset<?>) object;
880 /*
881 * We can't simply check whether the entry sets are equal, since that
882 * approach fails when a TreeMultiset has a comparator that returns 0
883 * when passed unequal elements.
884 */
885
886 if (multiset.size() != that.size() || multiset.entrySet().size() != that.entrySet().size()) {
887 return false;
888 }
889 for (Entry<?> entry : that.entrySet()) {
890 if (multiset.count(entry.getElement()) != entry.getCount()) {
891 return false;
892 }
893 }
894 return true;
895 }
896 return false;
897 }
898
899 /** An implementation of {@link Multiset#addAll}. */
900 static <E extends @Nullable Object> boolean addAllImpl(
901 Multiset<E> self, Collection<? extends E> elements) {
902 checkNotNull(self);
903 checkNotNull(elements);
904 if (elements instanceof Multiset) {
905 return addAllImpl(self, cast(elements));
906 } else if (elements.isEmpty()) {
907 return false;
908 } else {
909 return Iterators.addAll(self, elements.iterator());
910 }
911 }
912
913 /** A specialization of {@code addAllImpl} for when {@code elements} is itself a Multiset. */
914 private static <E extends @Nullable Object> boolean addAllImpl(
915 Multiset<E> self, Multiset<? extends E> elements) {
916 if (elements.isEmpty()) {
917 return false;
918 }
919 elements.forEachEntry(self::add);
920 return true;
921 }
922
923 /** An implementation of {@link Multiset#removeAll}. */
924 static boolean removeAllImpl(Multiset<?> self, Collection<?> elementsToRemove) {
925 Collection<?> collection =
926 (elementsToRemove instanceof Multiset)
927 ? ((Multiset<?>) elementsToRemove).elementSet()
928 : elementsToRemove;
929
930 return self.elementSet().removeAll(collection);
931 }
932
933 /** An implementation of {@link Multiset#retainAll}. */
934 static boolean retainAllImpl(Multiset<?> self, Collection<?> elementsToRetain) {
935 checkNotNull(elementsToRetain);
936 Collection<?> collection =
937 (elementsToRetain instanceof Multiset)
938 ? ((Multiset<?>) elementsToRetain).elementSet()
939 : elementsToRetain;
940
941 return self.elementSet().retainAll(collection);
942 }
943
944 /** An implementation of {@link Multiset#setCount(Object, int)}. */
945 static <E extends @Nullable Object> int setCountImpl(
946 Multiset<E> self, @ParametricNullness E element, int count) {
947 checkNonnegative(count, "count");
948
949 int oldCount = self.count(element);
950
951 int delta = count - oldCount;
952 if (delta > 0) {
953 self.add(element, delta);
954 } else if (delta < 0) {
955 self.remove(element, -delta);
956 }
957
958 return oldCount;
959 }
960
961 /** An implementation of {@link Multiset#setCount(Object, int, int)}. */
962 static <E extends @Nullable Object> boolean setCountImpl(
963 Multiset<E> self, @ParametricNullness E element, int oldCount, int newCount) {
964 checkNonnegative(oldCount, "oldCount");
965 checkNonnegative(newCount, "newCount");
966
967 if (self.count(element) == oldCount) {
968 self.setCount(element, newCount);
969 return true;
970 } else {
971 return false;
972 }
973 }
974
975 static <E extends @Nullable Object> Iterator<E> elementIterator(
976 Iterator<Entry<E>> entryIterator) {
977 return new TransformedIterator<Entry<E>, E>(entryIterator) {
978 @Override
979 @ParametricNullness
980 E transform(Entry<E> entry) {
981 return entry.getElement();
982 }
983 };
984 }
985
986 abstract static class ElementSet<E extends @Nullable Object> extends Sets.ImprovedAbstractSet<E> {
987 abstract Multiset<E> multiset();
988
989 @Override
990 public void clear() {
991 multiset().clear();
992 }
993
994 @Override
995 public boolean contains(@CheckForNull Object o) {
996 return multiset().contains(o);
997 }
998
999 @Override
1000 public boolean containsAll(Collection<?> c) {
1001 return multiset().containsAll(c);
1002 }
1003
1004 @Override
1005 public boolean isEmpty() {
1006 return multiset().isEmpty();
1007 }
1008
1009 @Override
1010 public abstract Iterator<E> iterator();
1011
1012 @Override
1013 public boolean remove(@CheckForNull Object o) {
1014 return multiset().remove(o, Integer.MAX_VALUE) > 0;
1015 }
1016
1017 @Override
1018 public int size() {
1019 return multiset().entrySet().size();
1020 }
1021 }
1022
1023 abstract static class EntrySet<E extends @Nullable Object>
1024 extends Sets.ImprovedAbstractSet<Entry<E>> {
1025 abstract Multiset<E> multiset();
1026
1027 @Override
1028 public boolean contains(@CheckForNull Object o) {
1029 if (o instanceof Entry) {
1030 /*
1031 * The GWT compiler wrongly issues a warning here.
1032 */
1033 @SuppressWarnings("cast")
1034 Entry<?> entry = (Entry<?>) o;
1035 if (entry.getCount() <= 0) {
1036 return false;
1037 }
1038 int count = multiset().count(entry.getElement());
1039 return count == entry.getCount();
1040 }
1041 return false;
1042 }
1043
1044 // GWT compiler warning; see contains().
1045 @SuppressWarnings("cast")
1046 @Override
1047 public boolean remove(@CheckForNull Object object) {
1048 if (object instanceof Multiset.Entry) {
1049 Entry<?> entry = (Entry<?>) object;
1050 Object element = entry.getElement();
1051 int entryCount = entry.getCount();
1052 if (entryCount != 0) {
1053 // Safe as long as we never add a new entry, which we won't.
1054 // (Presumably it can still throw CCE/NPE but only if the underlying Multiset does.)
1055 @SuppressWarnings({"unchecked", "nullness"})
1056 Multiset<@Nullable Object> multiset = (Multiset<@Nullable Object>) multiset();
1057 return multiset.setCount(element, entryCount, 0);
1058 }
1059 }
1060 return false;
1061 }
1062
1063 @Override
1064 public void clear() {
1065 multiset().clear();
1066 }
1067 }
1068
1069 /** An implementation of {@link Multiset#iterator}. */
1070 static <E extends @Nullable Object> Iterator<E> iteratorImpl(Multiset<E> multiset) {
1071 return new MultisetIteratorImpl<E>(multiset, multiset.entrySet().iterator());
1072 }
1073
1074 static final class MultisetIteratorImpl<E extends @Nullable Object> implements Iterator<E> {
1075 private final Multiset<E> multiset;
1076 private final Iterator<Entry<E>> entryIterator;
1077 @CheckForNull private Entry<E> currentEntry;
1078
1079 /** Count of subsequent elements equal to current element */
1080 private int laterCount;
1081
1082 /** Count of all elements equal to current element */
1083 private int totalCount;
1084
1085 private boolean canRemove;
1086
1087 MultisetIteratorImpl(Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
1088 this.multiset = multiset;
1089 this.entryIterator = entryIterator;
1090 }
1091
1092 @Override
1093 public boolean hasNext() {
1094 return laterCount > 0 || entryIterator.hasNext();
1095 }
1096
1097 @Override
1098 @ParametricNullness
1099 public E next() {
1100 if (!hasNext()) {
1101 throw new NoSuchElementException();
1102 }
1103 if (laterCount == 0) {
1104 currentEntry = entryIterator.next();
1105 totalCount = laterCount = currentEntry.getCount();
1106 }
1107 laterCount--;
1108 canRemove = true;
1109 /*
1110 * requireNonNull is safe because laterCount starts at 0, forcing us to initialize
1111 * currentEntry above. After that, we never clear it.
1112 */
1113 return requireNonNull(currentEntry).getElement();
1114 }
1115
1116 @Override
1117 public void remove() {
1118 checkRemove(canRemove);
1119 if (totalCount == 1) {
1120 entryIterator.remove();
1121 } else {
1122 /*
1123 * requireNonNull is safe because canRemove is set to true only after we initialize
1124 * currentEntry (which we never subsequently clear).
1125 */
1126 multiset.remove(requireNonNull(currentEntry).getElement());
1127 }
1128 totalCount--;
1129 canRemove = false;
1130 }
1131 }
1132
1133 static <E extends @Nullable Object> Spliterator<E> spliteratorImpl(Multiset<E> multiset) {
1134 Spliterator<Entry<E>> entrySpliterator = multiset.entrySet().spliterator();
1135 return CollectSpliterators.flatMap(
1136 entrySpliterator,
1137 entry -> Collections.nCopies(entry.getCount(), entry.getElement()).spliterator(),
1138 Spliterator.SIZED
1139 | (entrySpliterator.characteristics()
1140 & (Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE)),
1141 multiset.size());
1142 }
1143
1144 /** An implementation of {@link Multiset#size}. */
1145 static int linearTimeSizeImpl(Multiset<?> multiset) {
1146 long size = 0;
1147 for (Entry<?> entry : multiset.entrySet()) {
1148 size += entry.getCount();
1149 }
1150 return Ints.saturatedCast(size);
1151 }
1152
1153 /** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */
1154 static <T extends @Nullable Object> Multiset<T> cast(Iterable<T> iterable) {
1155 return (Multiset<T>) iterable;
1156 }
1157
1158 /**
1159 * Returns a copy of {@code multiset} as an {@link ImmutableMultiset} whose iteration order is
1160 * highest count first, with ties broken by the iteration order of the original multiset.
1161 *
1162 * @since 11.0
1163 */
1164 @Beta
1165 public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) {
1166 Entry<E>[] entries = (Entry<E>[]) multiset.entrySet().toArray(new Entry[0]);
1167 Arrays.sort(entries, DecreasingCount.INSTANCE);
1168 return ImmutableMultiset.copyFromEntries(Arrays.asList(entries));
1169 }
1170
1171 private static final class DecreasingCount implements Comparator<Entry<?>> {
1172 static final DecreasingCount INSTANCE = new DecreasingCount();
1173
1174 @Override
1175 public int compare(Entry<?> entry1, Entry<?> entry2) {
1176 return entry2.getCount() - entry1.getCount(); // subtracting two nonnegative integers
1177 }
1178 }
1179
1180 /**
1181 * An {@link AbstractMultiset} with additional default implementations, some of them linear-time
1182 * implementations in terms of {@code elementSet} and {@code entrySet}.
1183 */
1184 private abstract static class ViewMultiset<E extends @Nullable Object>
1185 extends AbstractMultiset<E> {
1186 @Override
1187 public int size() {
1188 return linearTimeSizeImpl(this);
1189 }
1190
1191 @Override
1192 public void clear() {
1193 elementSet().clear();
1194 }
1195
1196 @Override
1197 public Iterator<E> iterator() {
1198 return iteratorImpl(this);
1199 }
1200
1201 @Override
1202 int distinctElements() {
1203 return elementSet().size();
1204 }
1205 }
1206 }