https://github.com/google/guava/guava: Guava is a suite of core and expanded libraries that include utility classes, google's collections, io classes, and much much more. 
/*
 * Copyright (C) 2007 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static com.google.common.collect.CollectPreconditions.checkNonnegative;
import static com.google.common.collect.CollectPreconditions.checkRemove;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Objects;
import com.google.common.base.Predicate;
import com.google.common.base.Predicates;
import com.google.common.collect.Multiset.Entry;
import com.google.common.math.IntMath;
import com.google.common.primitives.Ints;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import java.io.Serializable;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.Spliterator;
import java.util.stream.Collector;
import org.checkerframework.checker.nullness.qual.MonotonicNonNull;
import org.checkerframework.checker.nullness.qual.Nullable;


Provides static utility methods for creating and working with Multiset instances. 
See the Guava User Guide article on  
Multisets.

Author:Kevin Bourrillion, Mike Bostock, Louis Wasserman
Since:2.0
/**
 * Provides static utility methods for creating and working with {@link Multiset} instances.
 *
 * <p>See the Guava User Guide article on <a href=
 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multisets"> {@code
 * Multisets}</a>.
 *
 * @author Kevin Bourrillion
 * @author Mike Bostock
 * @author Louis Wasserman
 * @since 2.0
 */
@GwtCompatible
public final class Multisets {
  private Multisets() {}

  
Returns a Collector that accumulates elements into a multiset created via the specified Supplier, whose elements are the result of applying elementFunction to the inputs, with counts equal to the result of applying countFunction to the inputs. Elements are added in encounter order. 
If the mapped elements contain duplicates (according to Object.equals), the element will be added more than once, with the count summed over all appearances of the element. 
Note that stream.collect(toMultiset(function, e -> 1, supplier)) is equivalent to stream.map(function).collect(Collectors.toCollection(supplier)). 
Since:22.0
/**
   * Returns a {@code Collector} that accumulates elements into a multiset created via the specified
   * {@code Supplier}, whose elements are the result of applying {@code elementFunction} to the
   * inputs, with counts equal to the result of applying {@code countFunction} to the inputs.
   * Elements are added in encounter order.
   *
   * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the element
   * will be added more than once, with the count summed over all appearances of the element.
   *
   * <p>Note that {@code stream.collect(toMultiset(function, e -> 1, supplier))} is equivalent to
   * {@code stream.map(function).collect(Collectors.toCollection(supplier))}.
   *
   * @since 22.0
   */
  public static <T, E, M extends Multiset<E>> Collector<T, ?, M> toMultiset(
      java.util.function.Function<? super T, E> elementFunction,
      java.util.function.ToIntFunction<? super T> countFunction,
      java.util.function.Supplier<M> multisetSupplier) {
    checkNotNull(elementFunction);
    checkNotNull(countFunction);
    checkNotNull(multisetSupplier);
    return Collector.of(
        multisetSupplier,
        (ms, t) -> ms.add(elementFunction.apply(t), countFunction.applyAsInt(t)),
        (ms1, ms2) -> {
          ms1.addAll(ms2);
          return ms1;
        });
  }

  
Returns an unmodifiable view of the specified multiset. Query operations on the returned multiset "read through" to the specified multiset, and attempts to modify the returned multiset result in an UnsupportedOperationException. 
The returned multiset will be serializable if the specified multiset is serializable.

Params:
  • multiset – the multiset for which an unmodifiable view is to be generated
Returns:an unmodifiable view of the multiset
/**
   * Returns an unmodifiable view of the specified multiset. Query operations on the returned
   * multiset "read through" to the specified multiset, and attempts to modify the returned multiset
   * result in an {@link UnsupportedOperationException}.
   *
   * <p>The returned multiset will be serializable if the specified multiset is serializable.
   *
   * @param multiset the multiset for which an unmodifiable view is to be generated
   * @return an unmodifiable view of the multiset
   */
  public static <E> Multiset<E> unmodifiableMultiset(Multiset<? extends E> multiset) {
    if (multiset instanceof UnmodifiableMultiset || multiset instanceof ImmutableMultiset) {
      @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe
      Multiset<E> result = (Multiset<E>) multiset;
      return result;
    }
    return new UnmodifiableMultiset<E>(checkNotNull(multiset));
  }

  
Simply returns its argument.

Deprecated:no need to use this
Since:10.0
/**
   * Simply returns its argument.
   *
   * @deprecated no need to use this
   * @since 10.0
   */
  @Deprecated
  public static <E> Multiset<E> unmodifiableMultiset(ImmutableMultiset<E> multiset) {
    return checkNotNull(multiset);
  }

  static class UnmodifiableMultiset<E> extends ForwardingMultiset<E> implements Serializable {
    final Multiset<? extends E> delegate;

    UnmodifiableMultiset(Multiset<? extends E> delegate) {
      this.delegate = delegate;
    }

    @SuppressWarnings("unchecked")
    @Override
    protected Multiset<E> delegate() {
      // This is safe because all non-covariant methods are overridden
      return (Multiset<E>) delegate;
    }

    @MonotonicNonNull transient Set<E> elementSet;

    Set<E> createElementSet() {
      return Collections.<E>unmodifiableSet(delegate.elementSet());
    }

    @Override
    public Set<E> elementSet() {
      Set<E> es = elementSet;
      return (es == null) ? elementSet = createElementSet() : es;
    }

    @MonotonicNonNull transient Set<Multiset.Entry<E>> entrySet;

    @SuppressWarnings("unchecked")
    @Override
    public Set<Multiset.Entry<E>> entrySet() {
      Set<Multiset.Entry<E>> es = entrySet;
      return (es == null)
          // Safe because the returned set is made unmodifiable and Entry
          // itself is readonly
          ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
          : es;
    }

    @Override
    public Iterator<E> iterator() {
      return Iterators.<E>unmodifiableIterator(delegate.iterator());
    }

    @Override
    public boolean add(E element) {
      throw new UnsupportedOperationException();
    }

    @Override
    public int add(E element, int occurences) {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean addAll(Collection<? extends E> elementsToAdd) {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean remove(Object element) {
      throw new UnsupportedOperationException();
    }

    @Override
    public int remove(Object element, int occurrences) {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> elementsToRemove) {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> elementsToRetain) {
      throw new UnsupportedOperationException();
    }

    @Override
    public void clear() {
      throw new UnsupportedOperationException();
    }

    @Override
    public int setCount(E element, int count) {
      throw new UnsupportedOperationException();
    }

    @Override
    public boolean setCount(E element, int oldCount, int newCount) {
      throw new UnsupportedOperationException();
    }

    private static final long serialVersionUID = 0;
  }

  
Returns an unmodifiable view of the specified sorted multiset. Query operations on the returned multiset "read through" to the specified multiset, and attempts to modify the returned multiset result in an UnsupportedOperationException. 
The returned multiset will be serializable if the specified multiset is serializable.

Params:
  • sortedMultiset – the sorted multiset for which an unmodifiable view is to be generated
Returns:an unmodifiable view of the multiset
Since:11.0
/**
   * Returns an unmodifiable view of the specified sorted multiset. Query operations on the returned
   * multiset "read through" to the specified multiset, and attempts to modify the returned multiset
   * result in an {@link UnsupportedOperationException}.
   *
   * <p>The returned multiset will be serializable if the specified multiset is serializable.
   *
   * @param sortedMultiset the sorted multiset for which an unmodifiable view is to be generated
   * @return an unmodifiable view of the multiset
   * @since 11.0
   */
  @Beta
  public static <E> SortedMultiset<E> unmodifiableSortedMultiset(SortedMultiset<E> sortedMultiset) {
    // it's in its own file so it can be emulated for GWT
    return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset));
  }

  
Returns an immutable multiset entry with the specified element and count. The entry will be serializable if e is. 
Params:
  • e – the element to be associated with the returned entry
  • n – the count to be associated with the returned entry
Throws:
/**
   * Returns an immutable multiset entry with the specified element and count. The entry will be
   * serializable if {@code e} is.
   *
   * @param e the element to be associated with the returned entry
   * @param n the count to be associated with the returned entry
   * @throws IllegalArgumentException if {@code n} is negative
   */
  public static <E> Multiset.Entry<E> immutableEntry(@Nullable E e, int n) {
    return new ImmutableEntry<E>(e, n);
  }

  static class ImmutableEntry<E> extends AbstractEntry<E> implements Serializable {
    private final @Nullable E element;
    private final int count;

    ImmutableEntry(@Nullable E element, int count) {
      this.element = element;
      this.count = count;
      checkNonnegative(count, "count");
    }

    @Override
    public final @Nullable E getElement() {
      return element;
    }

    @Override
    public final int getCount() {
      return count;
    }

    public ImmutableEntry<E> nextInBucket() {
      return null;
    }

    private static final long serialVersionUID = 0;
  }

  
Returns a view of the elements of unfiltered that satisfy a predicate. The returned multiset is a live view of unfiltered; changes to one affect the other. 
The resulting multiset's iterators, and those of its entrySet() and 
elementSet(), do not support remove(). However, all other multiset methods supported by unfiltered are supported by the returned multiset. When given an element that doesn't satisfy the predicate, the multiset's add() and addAll() methods throw an IllegalArgumentException. When methods such as removeAll() and 
clear() are called on the filtered multiset, only elements that satisfy the filter will be removed from the underlying multiset. 
The returned multiset isn't threadsafe or serializable, even if unfiltered is. 
Many of the filtered multiset's methods, such as size(), iterate across every element in the underlying multiset and determine which elements satisfy the filter. When a live view is not needed, it may be faster to copy the returned multiset and use the copy.

Warning: predicate must be consistent with equals, as documented at Predicate.apply. Do not provide a predicate such as 
Predicates.instanceOf(ArrayList.class), which is inconsistent with equals. (See Iterables.filter(Iterable<?>, Class<Object>) for related functionality.) 
Since:14.0
/**
   * Returns a view of the elements of {@code unfiltered} that satisfy a predicate. The returned
   * multiset is a live view of {@code unfiltered}; changes to one affect the other.
   *
   * <p>The resulting multiset's iterators, and those of its {@code entrySet()} and {@code
   * elementSet()}, do not support {@code remove()}. However, all other multiset methods supported
   * by {@code unfiltered} are supported by the returned multiset. When given an element that
   * doesn't satisfy the predicate, the multiset's {@code add()} and {@code addAll()} methods throw
   * an {@link IllegalArgumentException}. When methods such as {@code removeAll()} and {@code
   * clear()} are called on the filtered multiset, only elements that satisfy the filter will be
   * removed from the underlying multiset.
   *
   * <p>The returned multiset isn't threadsafe or serializable, even if {@code unfiltered} is.
   *
   * <p>Many of the filtered multiset's methods, such as {@code size()}, iterate across every
   * element in the underlying multiset and determine which elements satisfy the filter. When a live
   * view is <i>not</i> needed, it may be faster to copy the returned multiset and use the copy.
   *
   * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
   * {@link Predicate#apply}. Do not provide a predicate such as {@code
   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See {@link
   * Iterables#filter(Iterable, Class)} for related functionality.)
   *
   * @since 14.0
   */
  @Beta
  public static <E> Multiset<E> filter(Multiset<E> unfiltered, Predicate<? super E> predicate) {
    if (unfiltered instanceof FilteredMultiset) {
      // Support clear(), removeAll(), and retainAll() when filtering a filtered
      // collection.
      FilteredMultiset<E> filtered = (FilteredMultiset<E>) unfiltered;
      Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
      return new FilteredMultiset<E>(filtered.unfiltered, combinedPredicate);
    }
    return new FilteredMultiset<E>(unfiltered, predicate);
  }

  private static final class FilteredMultiset<E> extends ViewMultiset<E> {
    final Multiset<E> unfiltered;
    final Predicate<? super E> predicate;

    FilteredMultiset(Multiset<E> unfiltered, Predicate<? super E> predicate) {
      this.unfiltered = checkNotNull(unfiltered);
      this.predicate = checkNotNull(predicate);
    }

    @Override
    public UnmodifiableIterator<E> iterator() {
      return Iterators.filter(unfiltered.iterator(), predicate);
    }

    @Override
    Set<E> createElementSet() {
      return Sets.filter(unfiltered.elementSet(), predicate);
    }

    @Override
    Iterator<E> elementIterator() {
      throw new AssertionError("should never be called");
    }

    @Override
    Set<Entry<E>> createEntrySet() {
      return Sets.filter(
          unfiltered.entrySet(),
          new Predicate<Entry<E>>() {
            @Override
            public boolean apply(Entry<E> entry) {
              return predicate.apply(entry.getElement());
            }
          });
    }

    @Override
    Iterator<Entry<E>> entryIterator() {
      throw new AssertionError("should never be called");
    }

    @Override
    public int count(@Nullable Object element) {
      int count = unfiltered.count(element);
      if (count > 0) {
        @SuppressWarnings("unchecked") // element is equal to an E
        E e = (E) element;
        return predicate.apply(e) ? count : 0;
      }
      return 0;
    }

    @Override
    public int add(@Nullable E element, int occurrences) {
      checkArgument(
          predicate.apply(element), "Element %s does not match predicate %s", element, predicate);
      return unfiltered.add(element, occurrences);
    }

    @Override
    public int remove(@Nullable Object element, int occurrences) {
      checkNonnegative(occurrences, "occurrences");
      if (occurrences == 0) {
        return count(element);
      } else {
        return contains(element) ? unfiltered.remove(element, occurrences) : 0;
      }
    }
  }

  
Returns the expected number of distinct elements given the specified elements. The number of distinct elements is only computed if elements is an instance of Multiset; otherwise the default value of 11 is returned. 
/**
   * Returns the expected number of distinct elements given the specified elements. The number of
   * distinct elements is only computed if {@code elements} is an instance of {@code Multiset};
   * otherwise the default value of 11 is returned.
   */
  static int inferDistinctElements(Iterable<?> elements) {
    if (elements instanceof Multiset) {
      return ((Multiset<?>) elements).elementSet().size();
    }
    return 11; // initial capacity will be rounded up to 16
  }

  
Returns an unmodifiable view of the union of two multisets. In the returned multiset, the count
of each element is the maximum of its counts in the two backing multisets. The iteration order of the returned multiset matches that of the element set of multiset1 followed by the members of the element set of multiset2 that are not contained in 
multiset1, with repeated occurrences of the same element appearing consecutively. 
Results are undefined if multiset1 and multiset2 are based on different equivalence relations (as HashMultiset and TreeMultiset are). 
Since:14.0
/**
   * Returns an unmodifiable view of the union of two multisets. In the returned multiset, the count
   * of each element is the <i>maximum</i> of its counts in the two backing multisets. The iteration
   * order of the returned multiset matches that of the element set of {@code multiset1} followed by
   * the members of the element set of {@code multiset2} that are not contained in {@code
   * multiset1}, with repeated occurrences of the same element appearing consecutively.
   *
   * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
   * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
   *
   * @since 14.0
   */
  @Beta
  public static <E> Multiset<E> union(
      final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
    checkNotNull(multiset1);
    checkNotNull(multiset2);

    return new ViewMultiset<E>() {
      @Override
      public boolean contains(@Nullable Object element) {
        return multiset1.contains(element) || multiset2.contains(element);
      }

      @Override
      public boolean isEmpty() {
        return multiset1.isEmpty() && multiset2.isEmpty();
      }

      @Override
      public int count(Object element) {
        return Math.max(multiset1.count(element), multiset2.count(element));
      }

      @Override
      Set<E> createElementSet() {
        return Sets.union(multiset1.elementSet(), multiset2.elementSet());
      }

      @Override
      Iterator<E> elementIterator() {
        throw new AssertionError("should never be called");
      }

      @Override
      Iterator<Entry<E>> entryIterator() {
        final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
        final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
        // TODO(lowasser): consider making the entries live views
        return new AbstractIterator<Entry<E>>() {
          @Override
          protected Entry<E> computeNext() {
            if (iterator1.hasNext()) {
              Entry<? extends E> entry1 = iterator1.next();
              E element = entry1.getElement();
              int count = Math.max(entry1.getCount(), multiset2.count(element));
              return immutableEntry(element, count);
            }
            while (iterator2.hasNext()) {
              Entry<? extends E> entry2 = iterator2.next();
              E element = entry2.getElement();
              if (!multiset1.contains(element)) {
                return immutableEntry(element, entry2.getCount());
              }
            }
            return endOfData();
          }
        };
      }
    };
  }

  
Returns an unmodifiable view of the intersection of two multisets. In the returned multiset,
the count of each element is the minimum of its counts in the two backing multisets, with elements that would have a count of 0 not included. The iteration order of the returned multiset matches that of the element set of multiset1, with repeated occurrences of the same element appearing consecutively. 
Results are undefined if multiset1 and multiset2 are based on different equivalence relations (as HashMultiset and TreeMultiset are). 
Since:2.0
/**
   * Returns an unmodifiable view of the intersection of two multisets. In the returned multiset,
   * the count of each element is the <i>minimum</i> of its counts in the two backing multisets,
   * with elements that would have a count of 0 not included. The iteration order of the returned
   * multiset matches that of the element set of {@code multiset1}, with repeated occurrences of the
   * same element appearing consecutively.
   *
   * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
   * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
   *
   * @since 2.0
   */
  public static <E> Multiset<E> intersection(
      final Multiset<E> multiset1, final Multiset<?> multiset2) {
    checkNotNull(multiset1);
    checkNotNull(multiset2);

    return new ViewMultiset<E>() {
      @Override
      public int count(Object element) {
        int count1 = multiset1.count(element);
        return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
      }

      @Override
      Set<E> createElementSet() {
        return Sets.intersection(multiset1.elementSet(), multiset2.elementSet());
      }

      @Override
      Iterator<E> elementIterator() {
        throw new AssertionError("should never be called");
      }

      @Override
      Iterator<Entry<E>> entryIterator() {
        final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
        // TODO(lowasser): consider making the entries live views
        return new AbstractIterator<Entry<E>>() {
          @Override
          protected Entry<E> computeNext() {
            while (iterator1.hasNext()) {
              Entry<E> entry1 = iterator1.next();
              E element = entry1.getElement();
              int count = Math.min(entry1.getCount(), multiset2.count(element));
              if (count > 0) {
                return immutableEntry(element, count);
              }
            }
            return endOfData();
          }
        };
      }
    };
  }

  
Returns an unmodifiable view of the sum of two multisets. In the returned multiset, the count
of each element is the sum of its counts in the two backing multisets. The iteration order of the returned multiset matches that of the element set of multiset1 followed by the members of the element set of multiset2 that are not contained in 
multiset1, with repeated occurrences of the same element appearing consecutively. 
Results are undefined if multiset1 and multiset2 are based on different equivalence relations (as HashMultiset and TreeMultiset are). 
Since:14.0
/**
   * Returns an unmodifiable view of the sum of two multisets. In the returned multiset, the count
   * of each element is the <i>sum</i> of its counts in the two backing multisets. The iteration
   * order of the returned multiset matches that of the element set of {@code multiset1} followed by
   * the members of the element set of {@code multiset2} that are not contained in {@code
   * multiset1}, with repeated occurrences of the same element appearing consecutively.
   *
   * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
   * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
   *
   * @since 14.0
   */
  @Beta
  public static <E> Multiset<E> sum(
      final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
    checkNotNull(multiset1);
    checkNotNull(multiset2);

    // TODO(lowasser): consider making the entries live views
    return new ViewMultiset<E>() {
      @Override
      public boolean contains(@Nullable Object element) {
        return multiset1.contains(element) || multiset2.contains(element);
      }

      @Override
      public boolean isEmpty() {
        return multiset1.isEmpty() && multiset2.isEmpty();
      }

      @Override
      public int size() {
        return IntMath.saturatedAdd(multiset1.size(), multiset2.size());
      }

      @Override
      public int count(Object element) {
        return multiset1.count(element) + multiset2.count(element);
      }

      @Override
      Set<E> createElementSet() {
        return Sets.union(multiset1.elementSet(), multiset2.elementSet());
      }

      @Override
      Iterator<E> elementIterator() {
        throw new AssertionError("should never be called");
      }

      @Override
      Iterator<Entry<E>> entryIterator() {
        final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
        final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
        return new AbstractIterator<Entry<E>>() {
          @Override
          protected Entry<E> computeNext() {
            if (iterator1.hasNext()) {
              Entry<? extends E> entry1 = iterator1.next();
              E element = entry1.getElement();
              int count = entry1.getCount() + multiset2.count(element);
              return immutableEntry(element, count);
            }
            while (iterator2.hasNext()) {
              Entry<? extends E> entry2 = iterator2.next();
              E element = entry2.getElement();
              if (!multiset1.contains(element)) {
                return immutableEntry(element, entry2.getCount());
              }
            }
            return endOfData();
          }
        };
      }
    };
  }

  
Returns an unmodifiable view of the difference of two multisets. In the returned multiset, the
count of each element is the result of the zero-truncated subtraction of its count in the second multiset from its count in the first multiset, with elements that would have a count of 0 not included. The iteration order of the returned multiset matches that of the element set of multiset1, with repeated occurrences of the same element appearing consecutively. 
Results are undefined if multiset1 and multiset2 are based on different equivalence relations (as HashMultiset and TreeMultiset are). 
Since:14.0
/**
   * Returns an unmodifiable view of the difference of two multisets. In the returned multiset, the
   * count of each element is the result of the <i>zero-truncated subtraction</i> of its count in
   * the second multiset from its count in the first multiset, with elements that would have a count
   * of 0 not included. The iteration order of the returned multiset matches that of the element set
   * of {@code multiset1}, with repeated occurrences of the same element appearing consecutively.
   *
   * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different
   * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are).
   *
   * @since 14.0
   */
  @Beta
  public static <E> Multiset<E> difference(
      final Multiset<E> multiset1, final Multiset<?> multiset2) {
    checkNotNull(multiset1);
    checkNotNull(multiset2);

    // TODO(lowasser): consider making the entries live views
    return new ViewMultiset<E>() {
      @Override
      public int count(@Nullable Object element) {
        int count1 = multiset1.count(element);
        return (count1 == 0) ? 0 : Math.max(0, count1 - multiset2.count(element));
      }

      @Override
      public void clear() {
        throw new UnsupportedOperationException();
      }

      @Override
      Iterator<E> elementIterator() {
        final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
        return new AbstractIterator<E>() {
          @Override
          protected E computeNext() {
            while (iterator1.hasNext()) {
              Entry<E> entry1 = iterator1.next();
              E element = entry1.getElement();
              if (entry1.getCount() > multiset2.count(element)) {
                return element;
              }
            }
            return endOfData();
          }
        };
      }

      @Override
      Iterator<Entry<E>> entryIterator() {
        final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
        return new AbstractIterator<Entry<E>>() {
          @Override
          protected Entry<E> computeNext() {
            while (iterator1.hasNext()) {
              Entry<E> entry1 = iterator1.next();
              E element = entry1.getElement();
              int count = entry1.getCount() - multiset2.count(element);
              if (count > 0) {
                return immutableEntry(element, count);
              }
            }
            return endOfData();
          }
        };
      }

      @Override
      int distinctElements() {
        return Iterators.size(entryIterator());
      }
    };
  }

  
Returns true if subMultiset.count(o) <= superMultiset.count(o) for all 
o. 
Since:10.0
/**
   * Returns {@code true} if {@code subMultiset.count(o) <= superMultiset.count(o)} for all {@code
   * o}.
   *
   * @since 10.0
   */
  @CanIgnoreReturnValue
  public static boolean containsOccurrences(Multiset<?> superMultiset, Multiset<?> subMultiset) {
    checkNotNull(superMultiset);
    checkNotNull(subMultiset);
    for (Entry<?> entry : subMultiset.entrySet()) {
      int superCount = superMultiset.count(entry.getElement());
      if (superCount < entry.getCount()) {
        return false;
      }
    }
    return true;
  }

  
Modifies multisetToModify so that its count for an element e is at most 
multisetToRetain.count(e). 
To be precise, multisetToModify.count(e) is set to 
Math.min(multisetToModify.count(e), multisetToRetain.count(e)). This is similar to intersection (multisetToModify, multisetToRetain), but mutates multisetToModify instead of returning a view. 
In contrast, multisetToModify.retainAll(multisetToRetain) keeps all occurrences of elements that appear at all in multisetToRetain, and deletes all occurrences of all other elements. 
Returns:true if multisetToModify was changed as a result of this operation
Since:10.0
/**
   * Modifies {@code multisetToModify} so that its count for an element {@code e} is at most {@code
   * multisetToRetain.count(e)}.
   *
   * <p>To be precise, {@code multisetToModify.count(e)} is set to {@code
   * Math.min(multisetToModify.count(e), multisetToRetain.count(e))}. This is similar to {@link
   * #intersection(Multiset, Multiset) intersection} {@code (multisetToModify, multisetToRetain)},
   * but mutates {@code multisetToModify} instead of returning a view.
   *
   * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps all occurrences of
   * elements that appear at all in {@code multisetToRetain}, and deletes all occurrences of all
   * other elements.
   *
   * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
   * @since 10.0
   */
  @CanIgnoreReturnValue
  public static boolean retainOccurrences(
      Multiset<?> multisetToModify, Multiset<?> multisetToRetain) {
    return retainOccurrencesImpl(multisetToModify, multisetToRetain);
  }

  
Delegate implementation which cares about the element type. 
/** Delegate implementation which cares about the element type. */
  private static <E> boolean retainOccurrencesImpl(
      Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) {
    checkNotNull(multisetToModify);
    checkNotNull(occurrencesToRetain);
    // Avoiding ConcurrentModificationExceptions is tricky.
    Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
    boolean changed = false;
    while (entryIterator.hasNext()) {
      Entry<E> entry = entryIterator.next();
      int retainCount = occurrencesToRetain.count(entry.getElement());
      if (retainCount == 0) {
        entryIterator.remove();
        changed = true;
      } else if (retainCount < entry.getCount()) {
        multisetToModify.setCount(entry.getElement(), retainCount);
        changed = true;
      }
    }
    return changed;
  }

  
For each occurrence of an element e in occurrencesToRemove, removes one occurrence of e in multisetToModify. 
Equivalently, this method modifies multisetToModify so that 
multisetToModify.count(e) is set to Math.max(0, multisetToModify.count(e) -
Iterables.frequency(occurrencesToRemove, e)). 
This is not the same as multisetToModify. 
removeAll(occurrencesToRemove), which removes all occurrences of elements that appear in occurrencesToRemove. However, this operation is equivalent to, albeit
sometimes more efficient than, the following:


for (E e : occurrencesToRemove) {
  multisetToModify.remove(e);
 }



Returns:true if multisetToModify was changed as a result of this operation
Since:18.0 (present in 10.0 with a requirement that the second parameter be a 
    Multiset)
/**
   * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one
   * occurrence of {@code e} in {@code multisetToModify}.
   *
   * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code
   * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) -
   * Iterables.frequency(occurrencesToRemove, e))}.
   *
   * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll
   * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear
   * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit
   * sometimes more efficient than, the following:
   *
   * <pre>{@code
   * for (E e : occurrencesToRemove) {
   *   multisetToModify.remove(e);
   * }
   * }</pre>
   *
   * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
   * @since 18.0 (present in 10.0 with a requirement that the second parameter be a {@code
   *     Multiset})
   */
  @CanIgnoreReturnValue
  public static boolean removeOccurrences(
      Multiset<?> multisetToModify, Iterable<?> occurrencesToRemove) {
    if (occurrencesToRemove instanceof Multiset) {
      return removeOccurrences(multisetToModify, (Multiset<?>) occurrencesToRemove);
    } else {
      checkNotNull(multisetToModify);
      checkNotNull(occurrencesToRemove);
      boolean changed = false;
      for (Object o : occurrencesToRemove) {
        changed |= multisetToModify.remove(o);
      }
      return changed;
    }
  }

  
For each occurrence of an element e in occurrencesToRemove, removes one occurrence of e in multisetToModify. 
Equivalently, this method modifies multisetToModify so that 
multisetToModify.count(e) is set to Math.max(0, multisetToModify.count(e) -
occurrencesToRemove.count(e)). 
This is not the same as multisetToModify. 
removeAll(occurrencesToRemove), which removes all occurrences of elements that appear in occurrencesToRemove. However, this operation is equivalent to, albeit
sometimes more efficient than, the following:


for (E e : occurrencesToRemove) {
  multisetToModify.remove(e);
 }



Returns:true if multisetToModify was changed as a result of this operation
Since:10.0 (missing in 18.0 when only the overload taking an Iterable was present)
/**
   * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one
   * occurrence of {@code e} in {@code multisetToModify}.
   *
   * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code
   * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) -
   * occurrencesToRemove.count(e))}.
   *
   * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll
   * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear
   * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit
   * sometimes more efficient than, the following:
   *
   * <pre>{@code
   * for (E e : occurrencesToRemove) {
   *   multisetToModify.remove(e);
   * }
   * }</pre>
   *
   * @return {@code true} if {@code multisetToModify} was changed as a result of this operation
   * @since 10.0 (missing in 18.0 when only the overload taking an {@code Iterable} was present)
   */
  @CanIgnoreReturnValue
  public static boolean removeOccurrences(
      Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) {
    checkNotNull(multisetToModify);
    checkNotNull(occurrencesToRemove);

    boolean changed = false;
    Iterator<? extends Entry<?>> entryIterator = multisetToModify.entrySet().iterator();
    while (entryIterator.hasNext()) {
      Entry<?> entry = entryIterator.next();
      int removeCount = occurrencesToRemove.count(entry.getElement());
      if (removeCount >= entry.getCount()) {
        entryIterator.remove();
        changed = true;
      } else if (removeCount > 0) {
        multisetToModify.remove(entry.getElement(), removeCount);
        changed = true;
      }
    }
    return changed;
  }

  
Implementation of the equals, hashCode, and toString methods of Entry. 
/**
   * Implementation of the {@code equals}, {@code hashCode}, and {@code toString} methods of {@link
   * Multiset.Entry}.
   */
  abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
    
Indicates whether an object equals this entry, following the behavior specified in Entry.equals. 
/**
     * Indicates whether an object equals this entry, following the behavior specified in {@link
     * Multiset.Entry#equals}.
     */
    @Override
    public boolean equals(@Nullable Object object) {
      if (object instanceof Multiset.Entry) {
        Multiset.Entry<?> that = (Multiset.Entry<?>) object;
        return this.getCount() == that.getCount()
            && Objects.equal(this.getElement(), that.getElement());
      }
      return false;
    }

    
Return this entry's hash code, following the behavior specified in Entry.hashCode. 
/**
     * Return this entry's hash code, following the behavior specified in {@link
     * Multiset.Entry#hashCode}.
     */
    @Override
    public int hashCode() {
      E e = getElement();
      return ((e == null) ? 0 : e.hashCode()) ^ getCount();
    }

    
Returns a string representation of this multiset entry. The string representation consists of the associated element if the associated count is one, and otherwise the associated element followed by the characters " x " (space, x and space) followed by the count. Elements and counts are converted to strings as by String.valueOf. 
/**
     * Returns a string representation of this multiset entry. The string representation consists of
     * the associated element if the associated count is one, and otherwise the associated element
     * followed by the characters " x " (space, x and space) followed by the count. Elements and
     * counts are converted to strings as by {@code String.valueOf}.
     */
    @Override
    public String toString() {
      String text = String.valueOf(getElement());
      int n = getCount();
      return (n == 1) ? text : (text + " x " + n);
    }
  }

  
An implementation of Multiset.equals. 
/** An implementation of {@link Multiset#equals}. */
  static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) {
    if (object == multiset) {
      return true;
    }
    if (object instanceof Multiset) {
      Multiset<?> that = (Multiset<?>) object;
      /*
       * We can't simply check whether the entry sets are equal, since that
       * approach fails when a TreeMultiset has a comparator that returns 0
       * when passed unequal elements.
       */

      if (multiset.size() != that.size() || multiset.entrySet().size() != that.entrySet().size()) {
        return false;
      }
      for (Entry<?> entry : that.entrySet()) {
        if (multiset.count(entry.getElement()) != entry.getCount()) {
          return false;
        }
      }
      return true;
    }
    return false;
  }

  
An implementation of Collection.addAll. 
/** An implementation of {@link Multiset#addAll}. */
  static <E> boolean addAllImpl(Multiset<E> self, Collection<? extends E> elements) {
    checkNotNull(self);
    checkNotNull(elements);
    if (elements instanceof Multiset) {
      return addAllImpl(self, cast(elements));
    } else if (elements.isEmpty()) {
      return false;
    } else {
      return Iterators.addAll(self, elements.iterator());
    }
  }

  
A specialization of addAllImpl for when elements is itself a Multiset. 
/** A specialization of {@code addAllImpl} for when {@code elements} is itself a Multiset. */
  private static <E> boolean addAllImpl(Multiset<E> self, Multiset<? extends E> elements) {
    if (elements.isEmpty()) {
      return false;
    }
    elements.forEachEntry(self::add);
    return true;
  }

  
An implementation of Multiset.removeAll. 
/** An implementation of {@link Multiset#removeAll}. */
  static boolean removeAllImpl(Multiset<?> self, Collection<?> elementsToRemove) {
    Collection<?> collection =
        (elementsToRemove instanceof Multiset)
            ? ((Multiset<?>) elementsToRemove).elementSet()
            : elementsToRemove;

    return self.elementSet().removeAll(collection);
  }

  
An implementation of Multiset.retainAll. 
/** An implementation of {@link Multiset#retainAll}. */
  static boolean retainAllImpl(Multiset<?> self, Collection<?> elementsToRetain) {
    checkNotNull(elementsToRetain);
    Collection<?> collection =
        (elementsToRetain instanceof Multiset)
            ? ((Multiset<?>) elementsToRetain).elementSet()
            : elementsToRetain;

    return self.elementSet().retainAll(collection);
  }

  
An implementation of Multiset.setCount(Object, int). 
/** An implementation of {@link Multiset#setCount(Object, int)}. */
  static <E> int setCountImpl(Multiset<E> self, E element, int count) {
    checkNonnegative(count, "count");

    int oldCount = self.count(element);

    int delta = count - oldCount;
    if (delta > 0) {
      self.add(element, delta);
    } else if (delta < 0) {
      self.remove(element, -delta);
    }

    return oldCount;
  }

  /** An implementation of {@link Multiset#setCount(Object, int, int)}. */
  static <E> boolean setCountImpl(Multiset<E> self, E element, int oldCount, int newCount) {
    checkNonnegative(oldCount, "oldCount");
    checkNonnegative(newCount, "newCount");

    if (self.count(element) == oldCount) {
      self.setCount(element, newCount);
      return true;
    } else {
      return false;
    }
  }

  static <E> Iterator<E> elementIterator(Iterator<Entry<E>> entryIterator) {
    return new TransformedIterator<Entry<E>, E>(entryIterator) {
      @Override
      E transform(Entry<E> entry) {
        return entry.getElement();
      }
    };
  }

  abstract static class ElementSet<E> extends Sets.ImprovedAbstractSet<E> {
    abstract Multiset<E> multiset();

    @Override
    public void clear() {
      multiset().clear();
    }

    @Override
    public boolean contains(Object o) {
      return multiset().contains(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
      return multiset().containsAll(c);
    }

    @Override
    public boolean isEmpty() {
      return multiset().isEmpty();
    }

    @Override
    public abstract Iterator<E> iterator();

    @Override
    public boolean remove(Object o) {
      return multiset().remove(o, Integer.MAX_VALUE) > 0;
    }

    @Override
    public int size() {
      return multiset().entrySet().size();
    }
  }

  abstract static class EntrySet<E> extends Sets.ImprovedAbstractSet<Entry<E>> {
    abstract Multiset<E> multiset();

    @Override
    public boolean contains(@Nullable Object o) {
      if (o instanceof Entry) {
        /*
         * The GWT compiler wrongly issues a warning here.
         */
        @SuppressWarnings("cast")
        Entry<?> entry = (Entry<?>) o;
        if (entry.getCount() <= 0) {
          return false;
        }
        int count = multiset().count(entry.getElement());
        return count == entry.getCount();
      }
      return false;
    }

    // GWT compiler warning; see contains().
    @SuppressWarnings("cast")
    @Override
    public boolean remove(Object object) {
      if (object instanceof Multiset.Entry) {
        Entry<?> entry = (Entry<?>) object;
        Object element = entry.getElement();
        int entryCount = entry.getCount();
        if (entryCount != 0) {
          // Safe as long as we never add a new entry, which we won't.
          @SuppressWarnings("unchecked")
          Multiset<Object> multiset = (Multiset) multiset();
          return multiset.setCount(element, entryCount, 0);
        }
      }
      return false;
    }

    @Override
    public void clear() {
      multiset().clear();
    }
  }

  
An implementation of Multiset.iterator. 
/** An implementation of {@link Multiset#iterator}. */
  static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
    return new MultisetIteratorImpl<E>(multiset, multiset.entrySet().iterator());
  }

  static final class MultisetIteratorImpl<E> implements Iterator<E> {
    private final Multiset<E> multiset;
    private final Iterator<Entry<E>> entryIterator;
    @MonotonicNonNull private Entry<E> currentEntry;

    
Count of subsequent elements equal to current element 
/** Count of subsequent elements equal to current element */
    private int laterCount;

    
Count of all elements equal to current element 
/** Count of all elements equal to current element */
    private int totalCount;

    private boolean canRemove;

    MultisetIteratorImpl(Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
      this.multiset = multiset;
      this.entryIterator = entryIterator;
    }

    @Override
    public boolean hasNext() {
      return laterCount > 0 || entryIterator.hasNext();
    }

    @Override
    public E next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      if (laterCount == 0) {
        currentEntry = entryIterator.next();
        totalCount = laterCount = currentEntry.getCount();
      }
      laterCount--;
      canRemove = true;
      return currentEntry.getElement();
    }

    @Override
    public void remove() {
      checkRemove(canRemove);
      if (totalCount == 1) {
        entryIterator.remove();
      } else {
        multiset.remove(currentEntry.getElement());
      }
      totalCount--;
      canRemove = false;
    }
  }

  static <E> Spliterator<E> spliteratorImpl(Multiset<E> multiset) {
    Spliterator<Entry<E>> entrySpliterator = multiset.entrySet().spliterator();
    return CollectSpliterators.flatMap(
        entrySpliterator,
        entry -> Collections.nCopies(entry.getCount(), entry.getElement()).spliterator(),
        Spliterator.SIZED
            | (entrySpliterator.characteristics()
                & (Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE)),
        multiset.size());
  }

  
An implementation of Multiset.size. 
/** An implementation of {@link Multiset#size}. */
  static int linearTimeSizeImpl(Multiset<?> multiset) {
    long size = 0;
    for (Entry<?> entry : multiset.entrySet()) {
      size += entry.getCount();
    }
    return Ints.saturatedCast(size);
  }

  
Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 
/** Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 */
  static <T> Multiset<T> cast(Iterable<T> iterable) {
    return (Multiset<T>) iterable;
  }

  
Returns a copy of multiset as an ImmutableMultiset whose iteration order is highest count first, with ties broken by the iteration order of the original multiset. 
Since:11.0
/**
   * Returns a copy of {@code multiset} as an {@link ImmutableMultiset} whose iteration order is
   * highest count first, with ties broken by the iteration order of the original multiset.
   *
   * @since 11.0
   */
  @Beta
  public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) {
    Entry<E>[] entries = (Entry<E>[]) multiset.entrySet().toArray(new Entry[0]);
    Arrays.sort(entries, DecreasingCount.INSTANCE);
    return ImmutableMultiset.copyFromEntries(Arrays.asList(entries));
  }

  private static final class DecreasingCount implements Comparator<Entry<?>> {
    static final DecreasingCount INSTANCE = new DecreasingCount();

    @Override
    public int compare(Entry<?> entry1, Entry<?> entry2) {
      return entry2.getCount() - entry1.getCount(); // subtracting two nonnegative integers
    }
  }

  
An AbstractMultiset with additional default implementations, some of them linear-time implementations in terms of elementSet and entrySet. 
/**
   * An {@link AbstractMultiset} with additional default implementations, some of them linear-time
   * implementations in terms of {@code elementSet} and {@code entrySet}.
   */
  private abstract static class ViewMultiset<E> extends AbstractMultiset<E> {
    @Override
    public int size() {
      return linearTimeSizeImpl(this);
    }

    @Override
    public void clear() {
      elementSet().clear();
    }

    @Override
    public Iterator<E> iterator() {
      return iteratorImpl(this);
    }

    @Override
    int distinctElements() {
      return elementSet().size();
    }
  }
}