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