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