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