    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021    import static com.google.common.base.Preconditions.checkState;
    022
    023    import com.google.common.annotations.Beta;
    024    import com.google.common.annotations.GwtCompatible;
    025    import com.google.common.base.Function;
    026    import com.google.common.base.Objects;
    027    import com.google.common.collect.Multiset.Entry;
    028    import com.google.common.primitives.Ints;
    029
    030    import java.io.Serializable;
    031    import java.util.AbstractSet;
    032    import java.util.Collection;
    033    import java.util.Collections;
    034    import java.util.Iterator;
    035    import java.util.NoSuchElementException;
    036    import java.util.Set;
    037
    038    import javax.annotation.Nullable;
    039
    040    /**
    041     * Provides static utility methods for creating and working with {@link
    042     * Multiset} instances.
    043     *
    044     * @author Kevin Bourrillion
    045     * @author Mike Bostock
    046     * @author Louis Wasserman
    047     * @since 2.0 (imported from Google Collections Library)
    048     */
    049    @GwtCompatible
    050    public final class Multisets {
    051      private Multisets() {}
    052
    053      /**
    054       * Returns an unmodifiable view of the specified multiset. Query operations on
    055       * the returned multiset "read through" to the specified multiset, and
    056       * attempts to modify the returned multiset result in an
    057       * {@link UnsupportedOperationException}.
    058       *
    059       * <p>The returned multiset will be serializable if the specified multiset is
    060       * serializable.
    061       *
    062       * @param multiset the multiset for which an unmodifiable view is to be
    063       *     generated
    064       * @return an unmodifiable view of the multiset
    065       */
    066      public static <E> Multiset<E> unmodifiableMultiset(
    067          Multiset<? extends E> multiset) {
    068        if (multiset instanceof UnmodifiableMultiset ||
    069            multiset instanceof ImmutableMultiset) {
    070          // Since it's unmodifiable, the covariant cast is safe
    071          @SuppressWarnings("unchecked")
    072          Multiset<E> result = (Multiset<E>) multiset;
    073          return result;
    074        }
    075        return new UnmodifiableMultiset<E>(checkNotNull(multiset));
    076      }
    077
    078      /**
    079       * Simply returns its argument.
    080       *
    081       * @deprecated no need to use this
    082       * @since 10.0
    083       */
    084      @Deprecated public static <E> Multiset<E> unmodifiableMultiset(
    085          ImmutableMultiset<E> multiset) {
    086        return checkNotNull(multiset);
    087      }
    088
    089      static class UnmodifiableMultiset<E>
    090          extends ForwardingMultiset<E> implements Serializable {
    091        final Multiset<? extends E> delegate;
    092
    093        UnmodifiableMultiset(Multiset<? extends E> delegate) {
    094          this.delegate = delegate;
    095        }
    096
    097        @SuppressWarnings("unchecked")
    098        @Override protected Multiset<E> delegate() {
    099          // This is safe because all non-covariant methods are overriden
    100          return (Multiset<E>) delegate;
    101        }
    102
    103        transient Set<E> elementSet;
    104
    105        Set<E> createElementSet() {
    106          return Collections.<E>unmodifiableSet(delegate.elementSet());
    107        }
    108
    109        @Override
    110        public Set<E> elementSet() {
    111          Set<E> es = elementSet;
    112          return (es == null) ? elementSet = createElementSet() : es;
    113        }
    114
    115        transient Set<Multiset.Entry<E>> entrySet;
    116
    117        @SuppressWarnings("unchecked")
    118        @Override public Set<Multiset.Entry<E>> entrySet() {
    119          Set<Multiset.Entry<E>> es = entrySet;
    120          return (es == null)
    121              // Safe because the returned set is made unmodifiable and Entry
    122              // itself is readonly
    123              ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
    124              : es;
    125        }
    126
    127        @SuppressWarnings("unchecked")
    128        @Override public Iterator<E> iterator() {
    129          // Safe because the returned Iterator is made unmodifiable
    130          return (Iterator<E>) Iterators.unmodifiableIterator(delegate.iterator());
    131        }
    132
    133        @Override public boolean add(E element) {
    134          throw new UnsupportedOperationException();
    135        }
    136
    137        @Override public int add(E element, int occurences) {
    138          throw new UnsupportedOperationException();
    139        }
    140
    141        @Override public boolean addAll(Collection<? extends E> elementsToAdd) {
    142          throw new UnsupportedOperationException();
    143        }
    144
    145        @Override public boolean remove(Object element) {
    146          throw new UnsupportedOperationException();
    147        }
    148
    149        @Override public int remove(Object element, int occurrences) {
    150          throw new UnsupportedOperationException();
    151        }
    152
    153        @Override public boolean removeAll(Collection<?> elementsToRemove) {
    154          throw new UnsupportedOperationException();
    155        }
    156
    157        @Override public boolean retainAll(Collection<?> elementsToRetain) {
    158          throw new UnsupportedOperationException();
    159        }
    160
    161        @Override public void clear() {
    162          throw new UnsupportedOperationException();
    163        }
    164
    165        @Override public int setCount(E element, int count) {
    166          throw new UnsupportedOperationException();
    167        }
    168
    169        @Override public boolean setCount(E element, int oldCount, int newCount) {
    170          throw new UnsupportedOperationException();
    171        }
    172
    173        private static final long serialVersionUID = 0;
    174      }
    175
    176      /**
    177       * Returns an immutable multiset entry with the specified element and count.
    178       * The entry will be serializable if {@code e} is.
    179       *
    180       * @param e the element to be associated with the returned entry
    181       * @param n the count to be associated with the returned entry
    182       * @throws IllegalArgumentException if {@code n} is negative
    183       */
    184      public static <E> Multiset.Entry<E> immutableEntry(@Nullable E e, int n) {
    185        return new ImmutableEntry<E>(e, n);
    186      }
    187
    188      static final class ImmutableEntry<E> extends AbstractEntry<E> implements
    189          Serializable {
    190        @Nullable final E element;
    191        final int count;
    192
    193        ImmutableEntry(@Nullable E element, int count) {
    194          this.element = element;
    195          this.count = count;
    196          checkArgument(count >= 0);
    197        }
    198
    199        @Override
    200        @Nullable public E getElement() {
    201          return element;
    202        }
    203
    204        @Override
    205        public int getCount() {
    206          return count;
    207        }
    208
    209        private static final long serialVersionUID = 0;
    210      }
    211
    212      /**
    213       * Returns a multiset view of the specified set. The multiset is backed by the
    214       * set, so changes to the set are reflected in the multiset, and vice versa.
    215       * If the set is modified while an iteration over the multiset is in progress
    216       * (except through the iterator's own {@code remove} operation) the results of
    217       * the iteration are undefined.
    218       *
    219       * <p>The multiset supports element removal, which removes the corresponding
    220       * element from the set. It does not support the {@code add} or {@code addAll}
    221       * operations, nor does it support the use of {@code setCount} to add
    222       * elements.
    223       *
    224       * <p>The returned multiset will be serializable if the specified set is
    225       * serializable. The multiset is threadsafe if the set is threadsafe.
    226       *
    227       * @param set the backing set for the returned multiset view
    228       */
    229      static <E> Multiset<E> forSet(Set<E> set) {
    230        return new SetMultiset<E>(set);
    231      }
    232
    233      /** @see Multisets#forSet */
    234      private static class SetMultiset<E> extends ForwardingCollection<E>
    235          implements Multiset<E>, Serializable {
    236        final Set<E> delegate;
    237
    238        SetMultiset(Set<E> set) {
    239          delegate = checkNotNull(set);
    240        }
    241
    242        @Override protected Set<E> delegate() {
    243          return delegate;
    244        }
    245
    246        @Override
    247        public int count(Object element) {
    248          return delegate.contains(element) ? 1 : 0;
    249        }
    250
    251        @Override
    252        public int add(E element, int occurrences) {
    253          throw new UnsupportedOperationException();
    254        }
    255
    256        @Override
    257        public int remove(Object element, int occurrences) {
    258          if (occurrences == 0) {
    259            return count(element);
    260          }
    261          checkArgument(occurrences > 0);
    262          return delegate.remove(element) ? 1 : 0;
    263        }
    264
    265        transient Set<E> elementSet;
    266
    267        @Override
    268        public Set<E> elementSet() {
    269          Set<E> es = elementSet;
    270          return (es == null) ? elementSet = new ElementSet() : es;
    271        }
    272
    273        transient Set<Entry<E>> entrySet;
    274
    275        @Override public Set<Entry<E>> entrySet() {
    276          Set<Entry<E>> es = entrySet;
    277          if (es == null) {
    278            es = entrySet = new EntrySet<E>() {
    279              @Override Multiset<E> multiset() {
    280                return SetMultiset.this;
    281              }
    282
    283              @Override public Iterator<Entry<E>> iterator() {
    284                return Iterators.transform(delegate.iterator(),
    285                    new Function<E, Entry<E>>() {
    286                      @Override public Entry<E> apply(E elem) {
    287                        return immutableEntry(elem, 1);
    288                      }
    289                    });
    290              }
    291
    292              @Override public int size() {
    293                return delegate.size();
    294              }
    295            };
    296          }
    297          return es;
    298        }
    299
    300        @Override public boolean add(E o) {
    301          throw new UnsupportedOperationException();
    302        }
    303
    304        @Override public boolean addAll(Collection<? extends E> c) {
    305          throw new UnsupportedOperationException();
    306        }
    307
    308        @Override
    309        public int setCount(E element, int count) {
    310          checkNonnegative(count, "count");
    311
    312          if (count == count(element)) {
    313            return count;
    314          } else if (count == 0) {
    315            remove(element);
    316            return 1;
    317          } else {
    318            throw new UnsupportedOperationException();
    319          }
    320        }
    321
    322        @Override
    323        public boolean setCount(E element, int oldCount, int newCount) {
    324          return setCountImpl(this, element, oldCount, newCount);
    325        }
    326
    327        @Override public boolean equals(@Nullable Object object) {
    328          if (object instanceof Multiset) {
    329            Multiset<?> that = (Multiset<?>) object;
    330            return this.size() == that.size() && delegate.equals(that.elementSet());
    331          }
    332          return false;
    333        }
    334
    335        @Override public int hashCode() {
    336          int sum = 0;
    337          for (E e : this) {
    338            sum += ((e == null) ? 0 : e.hashCode()) ^ 1;
    339          }
    340          return sum;
    341        }
    342
    343        /** @see SetMultiset#elementSet */
    344        class ElementSet extends ForwardingSet<E> {
    345          @Override protected Set<E> delegate() {
    346            return delegate;
    347          }
    348
    349          @Override public boolean add(E o) {
    350            throw new UnsupportedOperationException();
    351          }
    352
    353          @Override public boolean addAll(Collection<? extends E> c) {
    354            throw new UnsupportedOperationException();
    355          }
    356        }
    357
    358        private static final long serialVersionUID = 0;
    359      }
    360
    361      /**
    362       * Returns the expected number of distinct elements given the specified
    363       * elements. The number of distinct elements is only computed if {@code
    364       * elements} is an instance of {@code Multiset}; otherwise the default value
    365       * of 11 is returned.
    366       */
    367      static int inferDistinctElements(Iterable<?> elements) {
    368        if (elements instanceof Multiset) {
    369          return ((Multiset<?>) elements).elementSet().size();
    370        }
    371        return 11; // initial capacity will be rounded up to 16
    372      }
    373
    374      /**
    375       * Returns an unmodifiable <b>view</b> of the intersection of two multisets.
    376       * An element's count in the multiset is the smaller of its counts in the two
    377       * backing multisets. The iteration order of the returned multiset matches the
    378       * element set of {@code multiset1}, with repeated occurrences of the same
    379       * element appearing consecutively.
    380       *
    381       * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
    382       * based on different equivalence relations (as {@code HashMultiset} and
    383       * {@code TreeMultiset} are).
    384       *
    385       * @since 2.0
    386       */
    387      public static <E> Multiset<E> intersection(
    388          final Multiset<E> multiset1, final Multiset<?> multiset2) {
    389        checkNotNull(multiset1);
    390        checkNotNull(multiset2);
    391
    392        return new AbstractMultiset<E>() {
    393          @Override
    394          public int count(Object element) {
    395            int count1 = multiset1.count(element);
    396            return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
    397          }
    398
    399          @Override
    400          Set<E> createElementSet() {
    401            return Sets.intersection(
    402                multiset1.elementSet(), multiset2.elementSet());
    403          }
    404
    405          @Override
    406          Iterator<Entry<E>> entryIterator() {
    407            final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
    408            return new AbstractIterator<Entry<E>>() {
    409              @Override
    410              protected Entry<E> computeNext() {
    411                while (iterator1.hasNext()) {
    412                  Entry<E> entry1 = iterator1.next();
    413                  E element = entry1.getElement();
    414                  int count = Math.min(entry1.getCount(), multiset2.count(element));
    415                  if (count > 0) {
    416                    return Multisets.immutableEntry(element, count);
    417                  }
    418                }
    419                return endOfData();
    420              }
    421            };
    422          }
    423
    424          @Override
    425          int distinctElements() {
    426            return elementSet().size();
    427          }
    428        };
    429      }
    430
    431      /**
    432       * Returns {@code true} if {@code subMultiset.count(o) <=
    433       * superMultiset.count(o)} for all {@code o}.
    434       *
    435       * @since 10.0
    436       */
    437      @Beta
    438      public static boolean containsOccurrences(
    439          Multiset<?> superMultiset, Multiset<?> subMultiset) {
    440        checkNotNull(superMultiset);
    441        checkNotNull(subMultiset);
    442        for (Entry<?> entry : subMultiset.entrySet()) {
    443          int superCount = superMultiset.count(entry.getElement());
    444          if (superCount < entry.getCount()) {
    445            return false;
    446          }
    447        }
    448        return true;
    449      }
    450
    451      /**
    452       * Modifies {@code multisetToModify} so that its count for an element
    453       * {@code e} is at most {@code multisetToRetain.count(e)}.
    454       *
    455       * <p>To be precise, {@code multisetToModify.count(e)} is set to
    456       * {@code Math.min(multisetToModify.count(e),
    457       * multisetToRetain.count(e))}. This is similar to
    458       * {@link #intersection(Multiset, Multiset) intersection}
    459       * {@code (multisetToModify, multisetToRetain)}, but mutates
    460       * {@code multisetToModify} instead of returning a view.
    461       *
    462       * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps
    463       * all occurrences of elements that appear at all in {@code
    464       * multisetToRetain}, and deletes all occurrences of all other elements.
    465       *
    466       * @return {@code true} if {@code multisetToModify} was changed as a result
    467       *         of this operation
    468       * @since 10.0
    469       */
    470      @Beta public static boolean retainOccurrences(Multiset<?> multisetToModify,
    471          Multiset<?> multisetToRetain) {
    472        return retainOccurrencesImpl(multisetToModify, multisetToRetain);
    473      }
    474
    475      /**
    476       * Delegate implementation which cares about the element type.
    477       */
    478      private static <E> boolean retainOccurrencesImpl(
    479          Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) {
    480        checkNotNull(multisetToModify);
    481        checkNotNull(occurrencesToRetain);
    482        // Avoiding ConcurrentModificationExceptions is tricky.
    483        Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
    484        boolean changed = false;
    485        while (entryIterator.hasNext()) {
    486          Entry<E> entry = entryIterator.next();
    487          int retainCount = occurrencesToRetain.count(entry.getElement());
    488          if (retainCount == 0) {
    489            entryIterator.remove();
    490            changed = true;
    491          } else if (retainCount < entry.getCount()) {
    492            multisetToModify.setCount(entry.getElement(), retainCount);
    493            changed = true;
    494          }
    495        }
    496        return changed;
    497      }
    498
    499      /**
    500       * For each occurrence of an element {@code e} in {@code occurrencesToRemove},
    501       * removes one occurrence of {@code e} in {@code multisetToModify}.
    502       *
    503       * <p>Equivalently, this method modifies {@code multisetToModify} so that
    504       * {@code multisetToModify.count(e)} is set to
    505       * {@code Math.max(0, multisetToModify.count(e) -
    506       * occurrencesToRemove.count(e))}.
    507       *
    508       * <p>This is <i>not</i> the same as {@code multisetToModify.}
    509       * {@link Multiset#removeAll removeAll}{@code (occurrencesToRemove)}, which
    510       * removes all occurrences of elements that appear in
    511       * {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent
    512       * to, albeit more efficient than, the following: <pre>   {@code
    513       *
    514       *   for (E e : occurrencesToRemove) {
    515       *     multisetToModify.remove(e);
    516       *   }}</pre>
    517       *
    518       * @return {@code true} if {@code multisetToModify} was changed as a result of
    519       *         this operation
    520       * @since 10.0
    521       */
    522      @Beta public static boolean removeOccurrences(
    523          Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) {
    524        return removeOccurrencesImpl(multisetToModify, occurrencesToRemove);
    525      }
    526
    527      /**
    528       * Delegate that cares about the element types in occurrencesToRemove.
    529       */
    530      private static <E> boolean removeOccurrencesImpl(
    531          Multiset<E> multisetToModify, Multiset<?> occurrencesToRemove) {
    532        // TODO(user): generalize to removing an Iterable, perhaps
    533        checkNotNull(multisetToModify);
    534        checkNotNull(occurrencesToRemove);
    535
    536        boolean changed = false;
    537        Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
    538        while (entryIterator.hasNext()) {
    539          Entry<E> entry = entryIterator.next();
    540          int removeCount = occurrencesToRemove.count(entry.getElement());
    541          if (removeCount >= entry.getCount()) {
    542            entryIterator.remove();
    543            changed = true;
    544          } else if (removeCount > 0) {
    545            multisetToModify.remove(entry.getElement(), removeCount);
    546            changed = true;
    547          }
    548        }
    549        return changed;
    550      }
    551
    552      /**
    553       * Implementation of the {@code equals}, {@code hashCode}, and
    554       * {@code toString} methods of {@link Multiset.Entry}.
    555       */
    556      abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
    557        /**
    558         * Indicates whether an object equals this entry, following the behavior
    559         * specified in {@link Multiset.Entry#equals}.
    560         */
    561        @Override public boolean equals(@Nullable Object object) {
    562          if (object instanceof Multiset.Entry) {
    563            Multiset.Entry<?> that = (Multiset.Entry<?>) object;
    564            return this.getCount() == that.getCount()
    565                && Objects.equal(this.getElement(), that.getElement());
    566          }
    567          return false;
    568        }
    569
    570        /**
    571         * Return this entry's hash code, following the behavior specified in
    572         * {@link Multiset.Entry#hashCode}.
    573         */
    574        @Override public int hashCode() {
    575          E e = getElement();
    576          return ((e == null) ? 0 : e.hashCode()) ^ getCount();
    577        }
    578
    579        /**
    580         * Returns a string representation of this multiset entry. The string
    581         * representation consists of the associated element if the associated count
    582         * is one, and otherwise the associated element followed by the characters
    583         * " x " (space, x and space) followed by the count. Elements and counts are
    584         * converted to strings as by {@code String.valueOf}.
    585         */
    586        @Override public String toString() {
    587          String text = String.valueOf(getElement());
    588          int n = getCount();
    589          return (n == 1) ? text : (text + " x " + n);
    590        }
    591      }
    592
    593      /**
    594       * An implementation of {@link Multiset#equals}.
    595       */
    596      static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) {
    597        if (object == multiset) {
    598          return true;
    599        }
    600        if (object instanceof Multiset) {
    601          Multiset<?> that = (Multiset<?>) object;
    602          /*
    603           * We can't simply check whether the entry sets are equal, since that
    604           * approach fails when a TreeMultiset has a comparator that returns 0
    605           * when passed unequal elements.
    606           */
    607
    608          if (multiset.size() != that.size()
    609              || multiset.entrySet().size() != that.entrySet().size()) {
    610            return false;
    611          }
    612          for (Entry<?> entry : that.entrySet()) {
    613            if (multiset.count(entry.getElement()) != entry.getCount()) {
    614              return false;
    615            }
    616          }
    617          return true;
    618        }
    619        return false;
    620      }
    621
    622      /**
    623       * An implementation of {@link Multiset#addAll}.
    624       */
    625      static <E> boolean addAllImpl(
    626          Multiset<E> self, Collection<? extends E> elements) {
    627        if (elements.isEmpty()) {
    628          return false;
    629        }
    630        if (elements instanceof Multiset) {
    631          Multiset<? extends E> that = cast(elements);
    632          for (Entry<? extends E> entry : that.entrySet()) {
    633            self.add(entry.getElement(), entry.getCount());
    634          }
    635        } else {
    636          Iterators.addAll(self, elements.iterator());
    637        }
    638        return true;
    639      }
    640
    641      /**
    642       * An implementation of {@link Multiset#removeAll}.
    643       */
    644      static boolean removeAllImpl(
    645          Multiset<?> self, Collection<?> elementsToRemove) {
    646        Collection<?> collection = (elementsToRemove instanceof Multiset)
    647            ? ((Multiset<?>) elementsToRemove).elementSet() : elementsToRemove;
    648
    649        return self.elementSet().removeAll(collection);
    650      }
    651
    652      /**
    653       * An implementation of {@link Multiset#retainAll}.
    654       */
    655      static boolean retainAllImpl(
    656          Multiset<?> self, Collection<?> elementsToRetain) {
    657        Collection<?> collection = (elementsToRetain instanceof Multiset)
    658            ? ((Multiset<?>) elementsToRetain).elementSet() : elementsToRetain;
    659
    660        return self.elementSet().retainAll(collection);
    661      }
    662
    663      /**
    664       * An implementation of {@link Multiset#setCount(Object, int)}.
    665       */
    666      static <E> int setCountImpl(Multiset<E> self, E element, int count) {
    667        checkNonnegative(count, "count");
    668
    669        int oldCount = self.count(element);
    670
    671        int delta = count - oldCount;
    672        if (delta > 0) {
    673          self.add(element, delta);
    674        } else if (delta < 0) {
    675          self.remove(element, -delta);
    676        }
    677
    678        return oldCount;
    679      }
    680
    681      /**
    682       * An implementation of {@link Multiset#setCount(Object, int, int)}.
    683       */
    684      static <E> boolean setCountImpl(
    685          Multiset<E> self, E element, int oldCount, int newCount) {
    686        checkNonnegative(oldCount, "oldCount");
    687        checkNonnegative(newCount, "newCount");
    688
    689        if (self.count(element) == oldCount) {
    690          self.setCount(element, newCount);
    691          return true;
    692        } else {
    693          return false;
    694        }
    695      }
    696
    697      static abstract class ElementSet<E> extends AbstractSet<E> {
    698        abstract Multiset<E> multiset();
    699
    700        @Override public void clear() {
    701          multiset().clear();
    702        }
    703
    704        @Override public boolean contains(Object o) {
    705          return multiset().contains(o);
    706        }
    707
    708        @Override public boolean containsAll(Collection<?> c) {
    709          return multiset().containsAll(c);
    710        }
    711
    712        @Override public boolean isEmpty() {
    713          return multiset().isEmpty();
    714        }
    715
    716        @Override public Iterator<E> iterator() {
    717          return Iterators.transform(multiset().entrySet().iterator(),
    718              new Function<Entry<E>, E>() {
    719                @Override public E apply(Entry<E> entry) {
    720                  return entry.getElement();
    721                }
    722              });
    723        }
    724
    725        @Override
    726        public boolean remove(Object o) {
    727          int count = multiset().count(o);
    728          if (count > 0) {
    729            multiset().remove(o, count);
    730            return true;
    731          }
    732          return false;
    733        }
    734
    735        @Override public int size() {
    736          return multiset().entrySet().size();
    737        }
    738      }
    739
    740      static abstract class EntrySet<E> extends AbstractSet<Entry<E>>{
    741        abstract Multiset<E> multiset();
    742
    743        @Override public boolean contains(@Nullable Object o) {
    744          if (o instanceof Entry) {
    745            @SuppressWarnings("cast")
    746            Entry<?> entry = (Entry<?>) o;
    747            if (entry.getCount() <= 0) {
    748              return false;
    749            }
    750            int count = multiset().count(entry.getElement());
    751            return count == entry.getCount();
    752
    753          }
    754          return false;
    755        }
    756
    757        @SuppressWarnings("cast")
    758        @Override public boolean remove(Object o) {
    759          return contains(o)
    760              && multiset().elementSet().remove(((Entry<?>) o).getElement());
    761        }
    762
    763        @Override public void clear() {
    764          multiset().clear();
    765        }
    766      }
    767
    768      /**
    769       * An implementation of {@link Multiset#iterator}.
    770       */
    771      static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
    772        return new MultisetIteratorImpl<E>(
    773            multiset, multiset.entrySet().iterator());
    774      }
    775
    776      static final class MultisetIteratorImpl<E> implements Iterator<E> {
    777        private final Multiset<E> multiset;
    778        private final Iterator<Entry<E>> entryIterator;
    779        private Entry<E> currentEntry;
    780        /** Count of subsequent elements equal to current element */
    781        private int laterCount;
    782        /** Count of all elements equal to current element */
    783        private int totalCount;
    784        private boolean canRemove;
    785
    786        MultisetIteratorImpl(
    787            Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
    788          this.multiset = multiset;
    789          this.entryIterator = entryIterator;
    790        }
    791
    792        @Override
    793        public boolean hasNext() {
    794          return laterCount > 0 || entryIterator.hasNext();
    795        }
    796
    797        @Override
    798        public E next() {
    799          if (!hasNext()) {
    800            throw new NoSuchElementException();
    801          }
    802          if (laterCount == 0) {
    803            currentEntry = entryIterator.next();
    804            totalCount = laterCount = currentEntry.getCount();
    805          }
    806          laterCount--;
    807          canRemove = true;
    808          return currentEntry.getElement();
    809        }
    810
    811        @Override
    812        public void remove() {
    813          checkState(
    814              canRemove, "no calls to next() since the last call to remove()");
    815          if (totalCount == 1) {
    816            entryIterator.remove();
    817          } else {
    818            multiset.remove(currentEntry.getElement());
    819          }
    820          totalCount--;
    821          canRemove = false;
    822        }
    823      }
    824
    825      /**
    826       * An implementation of {@link Multiset#size}.
    827       */
    828      static int sizeImpl(Multiset<?> multiset) {
    829        long size = 0;
    830        for (Entry<?> entry : multiset.entrySet()) {
    831          size += entry.getCount();
    832        }
    833        return Ints.saturatedCast(size);
    834      }
    835
    836      static void checkNonnegative(int count, String name) {
    837        checkArgument(count >= 0, "%s cannot be negative: %s", name, count);
    838      }
    839
    840      /**
    841       * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
    842       */
    843      static <T> Multiset<T> cast(Iterable<T> iterable) {
    844        return (Multiset<T>) iterable;
    845      }
    846    }