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