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