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