View Javadoc
1   /*
2    * Copyright (C) 2007 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
22  import static com.google.common.collect.CollectPreconditions.checkRemove;
23  
24  import com.google.common.annotations.Beta;
25  import com.google.common.annotations.GwtCompatible;
26  import com.google.common.base.Objects;
27  import com.google.common.base.Predicate;
28  import com.google.common.base.Predicates;
29  import com.google.common.collect.Multiset.Entry;
30  import com.google.common.math.IntMath;
31  import com.google.common.primitives.Ints;
32  import com.google.errorprone.annotations.CanIgnoreReturnValue;
33  import java.io.Serializable;
34  import java.util.Arrays;
35  import java.util.Collection;
36  import java.util.Collections;
37  import java.util.Comparator;
38  import java.util.Iterator;
39  import java.util.NoSuchElementException;
40  import java.util.Set;
41  import java.util.Spliterator;
42  import java.util.stream.Collector;
43  import javax.annotation.Nullable;
44  
45  /**
46   * Provides static utility methods for creating and working with {@link
47   * Multiset} instances.
48   *
49   * <p>See the Guava User Guide article on <a href=
50   * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multisets">
51   * {@code Multisets}</a>.
52   *
53   * @author Kevin Bourrillion
54   * @author Mike Bostock
55   * @author Louis Wasserman
56   * @since 2.0
57   */
58  @GwtCompatible
59  public final class Multisets {
60    private Multisets() {}
61  
62    /**
63     * Returns a {@code Collector} that accumulates elements into a multiset created via the specified
64     * {@code Supplier}, whose elements are the result of applying {@code elementFunction} to the
65     * inputs, with counts equal to the result of applying {@code countFunction} to the inputs.
66     * Elements are added in encounter order.
67     *
68     * <p>If the mapped elements contain duplicates (according to {@link Object#equals}), the element
69     * will be added more than once, with the count summed over all appearances of the element.
70     *
71     * <p>Note that {@code stream.collect(toMultiset(function, e -> 1, supplier))} is equivalent to
72     * {@code stream.map(function).collect(Collectors.toCollection(supplier))}.
73     *
74     * @since 22.0
75     */
76    public static <T, E, M extends Multiset<E>> Collector<T, ?, M> toMultiset(
77        java.util.function.Function<? super T, E> elementFunction,
78        java.util.function.ToIntFunction<? super T> countFunction,
79        java.util.function.Supplier<M> multisetSupplier) {
80      checkNotNull(elementFunction);
81      checkNotNull(countFunction);
82      checkNotNull(multisetSupplier);
83      return Collector.of(
84          multisetSupplier,
85          (ms, t) -> ms.add(elementFunction.apply(t), countFunction.applyAsInt(t)),
86          (ms1, ms2) -> {
87            ms1.addAll(ms2);
88            return ms1;
89          });
90    }
91  
92    /**
93     * Returns an unmodifiable view of the specified multiset. Query operations on
94     * the returned multiset "read through" to the specified multiset, and
95     * attempts to modify the returned multiset result in an
96     * {@link UnsupportedOperationException}.
97     *
98     * <p>The returned multiset will be serializable if the specified multiset is
99     * serializable.
100    *
101    * @param multiset the multiset for which an unmodifiable view is to be
102    *     generated
103    * @return an unmodifiable view of the multiset
104    */
105   public static <E> Multiset<E> unmodifiableMultiset(Multiset<? extends E> multiset) {
106     if (multiset instanceof UnmodifiableMultiset || multiset instanceof ImmutableMultiset) {
107       @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe
108       Multiset<E> result = (Multiset<E>) multiset;
109       return result;
110     }
111     return new UnmodifiableMultiset<E>(checkNotNull(multiset));
112   }
113 
114   /**
115    * Simply returns its argument.
116    *
117    * @deprecated no need to use this
118    * @since 10.0
119    */
120   @Deprecated
121   public static <E> Multiset<E> unmodifiableMultiset(ImmutableMultiset<E> multiset) {
122     return checkNotNull(multiset);
123   }
124 
125   static class UnmodifiableMultiset<E> extends ForwardingMultiset<E> implements Serializable {
126     final Multiset<? extends E> delegate;
127 
128     UnmodifiableMultiset(Multiset<? extends E> delegate) {
129       this.delegate = delegate;
130     }
131 
132     @SuppressWarnings("unchecked")
133     @Override
134     protected Multiset<E> delegate() {
135       // This is safe because all non-covariant methods are overridden
136       return (Multiset<E>) delegate;
137     }
138 
139     transient Set<E> elementSet;
140 
141     Set<E> createElementSet() {
142       return Collections.<E>unmodifiableSet(delegate.elementSet());
143     }
144 
145     @Override
146     public Set<E> elementSet() {
147       Set<E> es = elementSet;
148       return (es == null) ? elementSet = createElementSet() : es;
149     }
150 
151     transient Set<Multiset.Entry<E>> entrySet;
152 
153     @SuppressWarnings("unchecked")
154     @Override
155     public Set<Multiset.Entry<E>> entrySet() {
156       Set<Multiset.Entry<E>> es = entrySet;
157       return (es == null)
158           // Safe because the returned set is made unmodifiable and Entry
159           // itself is readonly
160           ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
161           : es;
162     }
163 
164     @Override
165     public Iterator<E> iterator() {
166       return Iterators.<E>unmodifiableIterator(delegate.iterator());
167     }
168 
169     @Override
170     public boolean add(E element) {
171       throw new UnsupportedOperationException();
172     }
173 
174     @Override
175     public int add(E element, int occurences) {
176       throw new UnsupportedOperationException();
177     }
178 
179     @Override
180     public boolean addAll(Collection<? extends E> elementsToAdd) {
181       throw new UnsupportedOperationException();
182     }
183 
184     @Override
185     public boolean remove(Object element) {
186       throw new UnsupportedOperationException();
187     }
188 
189     @Override
190     public int remove(Object element, int occurrences) {
191       throw new UnsupportedOperationException();
192     }
193 
194     @Override
195     public boolean removeAll(Collection<?> elementsToRemove) {
196       throw new UnsupportedOperationException();
197     }
198 
199     @Override
200     public boolean retainAll(Collection<?> elementsToRetain) {
201       throw new UnsupportedOperationException();
202     }
203 
204     @Override
205     public void clear() {
206       throw new UnsupportedOperationException();
207     }
208 
209     @Override
210     public int setCount(E element, int count) {
211       throw new UnsupportedOperationException();
212     }
213 
214     @Override
215     public boolean setCount(E element, int oldCount, int newCount) {
216       throw new UnsupportedOperationException();
217     }
218 
219     private static final long serialVersionUID = 0;
220   }
221 
222   /**
223    * Returns an unmodifiable view of the specified sorted multiset. Query
224    * operations on the returned multiset "read through" to the specified
225    * multiset, and attempts to modify the returned multiset result in an {@link
226    * UnsupportedOperationException}.
227    *
228    * <p>The returned multiset will be serializable if the specified multiset is
229    * serializable.
230    *
231    * @param sortedMultiset the sorted multiset for which an unmodifiable view is
232    *     to be generated
233    * @return an unmodifiable view of the multiset
234    * @since 11.0
235    */
236   @Beta
237   public static <E> SortedMultiset<E> unmodifiableSortedMultiset(SortedMultiset<E> sortedMultiset) {
238     // it's in its own file so it can be emulated for GWT
239     return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset));
240   }
241 
242   /**
243    * Returns an immutable multiset entry with the specified element and count.
244    * The entry will be serializable if {@code e} is.
245    *
246    * @param e the element to be associated with the returned entry
247    * @param n the count to be associated with the returned entry
248    * @throws IllegalArgumentException if {@code n} is negative
249    */
250   public static <E> Multiset.Entry<E> immutableEntry(@Nullable E e, int n) {
251     return new ImmutableEntry<E>(e, n);
252   }
253 
254   static class ImmutableEntry<E> extends AbstractEntry<E> implements Serializable {
255     @Nullable private final E element;
256     private final int count;
257 
258     ImmutableEntry(@Nullable E element, int count) {
259       this.element = element;
260       this.count = count;
261       checkNonnegative(count, "count");
262     }
263 
264     @Override
265     @Nullable
266     public final E getElement() {
267       return element;
268     }
269 
270     @Override
271     public final int getCount() {
272       return count;
273     }
274 
275     public ImmutableEntry<E> nextInBucket() {
276       return null;
277     }
278 
279     private static final long serialVersionUID = 0;
280   }
281 
282   /**
283    * Returns a view of the elements of {@code unfiltered} that satisfy a predicate. The returned
284    * multiset is a live view of {@code unfiltered}; changes to one affect the other.
285    *
286    * <p>The resulting multiset's iterators, and those of its {@code entrySet()} and
287    * {@code elementSet()}, do not support {@code remove()}.  However, all other multiset methods
288    * supported by {@code unfiltered} are supported by the returned multiset. When given an element
289    * that doesn't satisfy the predicate, the multiset's {@code add()} and {@code addAll()} methods
290    * throw an {@link IllegalArgumentException}. When methods such as {@code removeAll()} and
291    * {@code clear()} are called on the filtered multiset, only elements that satisfy the filter
292    * will be removed from the underlying multiset.
293    *
294    * <p>The returned multiset isn't threadsafe or serializable, even if {@code unfiltered} is.
295    *
296    * <p>Many of the filtered multiset's methods, such as {@code size()}, iterate across every
297    * element in the underlying multiset and determine which elements satisfy the filter. When a
298    * live view is <i>not</i> needed, it may be faster to copy the returned multiset and use the
299    * copy.
300    *
301    * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at
302    * {@link Predicate#apply}. Do not provide a predicate such as
303    * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See
304    * {@link Iterables#filter(Iterable, Class)} for related functionality.)
305    *
306    * @since 14.0
307    */
308   @Beta
309   public static <E> Multiset<E> filter(Multiset<E> unfiltered, Predicate<? super E> predicate) {
310     if (unfiltered instanceof FilteredMultiset) {
311       // Support clear(), removeAll(), and retainAll() when filtering a filtered
312       // collection.
313       FilteredMultiset<E> filtered = (FilteredMultiset<E>) unfiltered;
314       Predicate<E> combinedPredicate = Predicates.<E>and(filtered.predicate, predicate);
315       return new FilteredMultiset<E>(filtered.unfiltered, combinedPredicate);
316     }
317     return new FilteredMultiset<E>(unfiltered, predicate);
318   }
319 
320   private static final class FilteredMultiset<E> extends AbstractMultiset<E> {
321     final Multiset<E> unfiltered;
322     final Predicate<? super E> predicate;
323 
324     FilteredMultiset(Multiset<E> unfiltered, Predicate<? super E> predicate) {
325       this.unfiltered = checkNotNull(unfiltered);
326       this.predicate = checkNotNull(predicate);
327     }
328 
329     @Override
330     public UnmodifiableIterator<E> iterator() {
331       return Iterators.filter(unfiltered.iterator(), predicate);
332     }
333 
334     @Override
335     Set<E> createElementSet() {
336       return Sets.filter(unfiltered.elementSet(), predicate);
337     }
338 
339     @Override
340     Set<Entry<E>> createEntrySet() {
341       return Sets.filter(
342           unfiltered.entrySet(),
343           new Predicate<Entry<E>>() {
344             @Override
345             public boolean apply(Entry<E> entry) {
346               return predicate.apply(entry.getElement());
347             }
348           });
349     }
350 
351     @Override
352     Iterator<Entry<E>> entryIterator() {
353       throw new AssertionError("should never be called");
354     }
355 
356     @Override
357     int distinctElements() {
358       return elementSet().size();
359     }
360 
361     @Override
362     public int count(@Nullable Object element) {
363       int count = unfiltered.count(element);
364       if (count > 0) {
365         @SuppressWarnings("unchecked") // element is equal to an E
366         E e = (E) element;
367         return predicate.apply(e) ? count : 0;
368       }
369       return 0;
370     }
371 
372     @Override
373     public int add(@Nullable E element, int occurrences) {
374       checkArgument(
375           predicate.apply(element), "Element %s does not match predicate %s", element, predicate);
376       return unfiltered.add(element, occurrences);
377     }
378 
379     @Override
380     public int remove(@Nullable Object element, int occurrences) {
381       checkNonnegative(occurrences, "occurrences");
382       if (occurrences == 0) {
383         return count(element);
384       } else {
385         return contains(element) ? unfiltered.remove(element, occurrences) : 0;
386       }
387     }
388 
389     @Override
390     public void clear() {
391       elementSet().clear();
392     }
393   }
394 
395   /**
396    * Returns the expected number of distinct elements given the specified
397    * elements. The number of distinct elements is only computed if {@code
398    * elements} is an instance of {@code Multiset}; otherwise the default value
399    * of 11 is returned.
400    */
401   static int inferDistinctElements(Iterable<?> elements) {
402     if (elements instanceof Multiset) {
403       return ((Multiset<?>) elements).elementSet().size();
404     }
405     return 11; // initial capacity will be rounded up to 16
406   }
407 
408   /**
409    * Returns an unmodifiable view of the union of two multisets.
410    * In the returned multiset, the count of each element is the <i>maximum</i>
411    * of its counts in the two backing multisets. The iteration order of the
412    * returned multiset matches that of the element set of {@code multiset1}
413    * followed by the members of the element set of {@code multiset2} that are
414    * not contained in {@code multiset1}, with repeated occurrences of the same
415    * element appearing consecutively.
416    *
417    * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
418    * based on different equivalence relations (as {@code HashMultiset} and
419    * {@code TreeMultiset} are).
420    *
421    * @since 14.0
422    */
423   @Beta
424   public static <E> Multiset<E> union(
425       final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
426     checkNotNull(multiset1);
427     checkNotNull(multiset2);
428 
429     return new AbstractMultiset<E>() {
430       @Override
431       public boolean contains(@Nullable Object element) {
432         return multiset1.contains(element) || multiset2.contains(element);
433       }
434 
435       @Override
436       public boolean isEmpty() {
437         return multiset1.isEmpty() && multiset2.isEmpty();
438       }
439 
440       @Override
441       public int count(Object element) {
442         return Math.max(multiset1.count(element), multiset2.count(element));
443       }
444 
445       @Override
446       Set<E> createElementSet() {
447         return Sets.union(multiset1.elementSet(), multiset2.elementSet());
448       }
449 
450       @Override
451       Iterator<Entry<E>> entryIterator() {
452         final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
453         final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
454         // TODO(lowasser): consider making the entries live views
455         return new AbstractIterator<Entry<E>>() {
456           @Override
457           protected Entry<E> computeNext() {
458             if (iterator1.hasNext()) {
459               Entry<? extends E> entry1 = iterator1.next();
460               E element = entry1.getElement();
461               int count = Math.max(entry1.getCount(), multiset2.count(element));
462               return immutableEntry(element, count);
463             }
464             while (iterator2.hasNext()) {
465               Entry<? extends E> entry2 = iterator2.next();
466               E element = entry2.getElement();
467               if (!multiset1.contains(element)) {
468                 return immutableEntry(element, entry2.getCount());
469               }
470             }
471             return endOfData();
472           }
473         };
474       }
475 
476       @Override
477       int distinctElements() {
478         return elementSet().size();
479       }
480     };
481   }
482 
483   /**
484    * Returns an unmodifiable view of the intersection of two multisets.
485    * In the returned multiset, the count of each element is the <i>minimum</i>
486    * of its counts in the two backing multisets, with elements that would have
487    * a count of 0 not included. The iteration order of the returned multiset
488    * matches that of the element set of {@code multiset1}, with repeated
489    * occurrences of the same element appearing consecutively.
490    *
491    * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
492    * based on different equivalence relations (as {@code HashMultiset} and
493    * {@code TreeMultiset} are).
494    *
495    * @since 2.0
496    */
497   public static <E> Multiset<E> intersection(
498       final Multiset<E> multiset1, final Multiset<?> multiset2) {
499     checkNotNull(multiset1);
500     checkNotNull(multiset2);
501 
502     return new AbstractMultiset<E>() {
503       @Override
504       public int count(Object element) {
505         int count1 = multiset1.count(element);
506         return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
507       }
508 
509       @Override
510       Set<E> createElementSet() {
511         return Sets.intersection(multiset1.elementSet(), multiset2.elementSet());
512       }
513 
514       @Override
515       Iterator<Entry<E>> entryIterator() {
516         final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
517         // TODO(lowasser): consider making the entries live views
518         return new AbstractIterator<Entry<E>>() {
519           @Override
520           protected Entry<E> computeNext() {
521             while (iterator1.hasNext()) {
522               Entry<E> entry1 = iterator1.next();
523               E element = entry1.getElement();
524               int count = Math.min(entry1.getCount(), multiset2.count(element));
525               if (count > 0) {
526                 return immutableEntry(element, count);
527               }
528             }
529             return endOfData();
530           }
531         };
532       }
533 
534       @Override
535       int distinctElements() {
536         return elementSet().size();
537       }
538     };
539   }
540 
541   /**
542    * Returns an unmodifiable view of the sum of two multisets.
543    * In the returned multiset, the count of each element is the <i>sum</i> of
544    * its counts in the two backing multisets. The iteration order of the
545    * returned multiset matches that of the element set of {@code multiset1}
546    * followed by the members of the element set of {@code multiset2} that
547    * are not contained in {@code multiset1}, with repeated occurrences of the
548    * same element appearing consecutively.
549    *
550    * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
551    * based on different equivalence relations (as {@code HashMultiset} and
552    * {@code TreeMultiset} are).
553    *
554    * @since 14.0
555    */
556   @Beta
557   public static <E> Multiset<E> sum(
558       final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) {
559     checkNotNull(multiset1);
560     checkNotNull(multiset2);
561 
562     // TODO(lowasser): consider making the entries live views
563     return new AbstractMultiset<E>() {
564       @Override
565       public boolean contains(@Nullable Object element) {
566         return multiset1.contains(element) || multiset2.contains(element);
567       }
568 
569       @Override
570       public boolean isEmpty() {
571         return multiset1.isEmpty() && multiset2.isEmpty();
572       }
573 
574       @Override
575       public int size() {
576         return IntMath.saturatedAdd(multiset1.size(), multiset2.size());
577       }
578 
579       @Override
580       public int count(Object element) {
581         return multiset1.count(element) + multiset2.count(element);
582       }
583 
584       @Override
585       Set<E> createElementSet() {
586         return Sets.union(multiset1.elementSet(), multiset2.elementSet());
587       }
588 
589       @Override
590       Iterator<Entry<E>> entryIterator() {
591         final Iterator<? extends Entry<? extends E>> iterator1 = multiset1.entrySet().iterator();
592         final Iterator<? extends Entry<? extends E>> iterator2 = multiset2.entrySet().iterator();
593         return new AbstractIterator<Entry<E>>() {
594           @Override
595           protected Entry<E> computeNext() {
596             if (iterator1.hasNext()) {
597               Entry<? extends E> entry1 = iterator1.next();
598               E element = entry1.getElement();
599               int count = entry1.getCount() + multiset2.count(element);
600               return immutableEntry(element, count);
601             }
602             while (iterator2.hasNext()) {
603               Entry<? extends E> entry2 = iterator2.next();
604               E element = entry2.getElement();
605               if (!multiset1.contains(element)) {
606                 return immutableEntry(element, entry2.getCount());
607               }
608             }
609             return endOfData();
610           }
611         };
612       }
613 
614       @Override
615       int distinctElements() {
616         return elementSet().size();
617       }
618     };
619   }
620 
621   /**
622    * Returns an unmodifiable view of the difference of two multisets.
623    * In the returned multiset, the count of each element is the result of the
624    * <i>zero-truncated subtraction</i> of its count in the second multiset from
625    * its count in the first multiset, with elements that would have a count of
626    * 0 not included. The iteration order of the returned multiset matches that
627    * of the element set of {@code multiset1}, with repeated occurrences of the
628    * same element appearing consecutively.
629    *
630    * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
631    * based on different equivalence relations (as {@code HashMultiset} and
632    * {@code TreeMultiset} are).
633    *
634    * @since 14.0
635    */
636   @Beta
637   public static <E> Multiset<E> difference(
638       final Multiset<E> multiset1, final Multiset<?> multiset2) {
639     checkNotNull(multiset1);
640     checkNotNull(multiset2);
641 
642     // TODO(lowasser): consider making the entries live views
643     return new AbstractMultiset<E>() {
644       @Override
645       public int count(@Nullable Object element) {
646         int count1 = multiset1.count(element);
647         return (count1 == 0) ? 0 : Math.max(0, count1 - multiset2.count(element));
648       }
649 
650       @Override
651       Iterator<Entry<E>> entryIterator() {
652         final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
653         return new AbstractIterator<Entry<E>>() {
654           @Override
655           protected Entry<E> computeNext() {
656             while (iterator1.hasNext()) {
657               Entry<E> entry1 = iterator1.next();
658               E element = entry1.getElement();
659               int count = entry1.getCount() - multiset2.count(element);
660               if (count > 0) {
661                 return immutableEntry(element, count);
662               }
663             }
664             return endOfData();
665           }
666         };
667       }
668 
669       @Override
670       int distinctElements() {
671         return Iterators.size(entryIterator());
672       }
673     };
674   }
675 
676   /**
677    * Returns {@code true} if {@code subMultiset.count(o) <=
678    * superMultiset.count(o)} for all {@code o}.
679    *
680    * @since 10.0
681    */
682   @CanIgnoreReturnValue
683   public static boolean containsOccurrences(Multiset<?> superMultiset, Multiset<?> subMultiset) {
684     checkNotNull(superMultiset);
685     checkNotNull(subMultiset);
686     for (Entry<?> entry : subMultiset.entrySet()) {
687       int superCount = superMultiset.count(entry.getElement());
688       if (superCount < entry.getCount()) {
689         return false;
690       }
691     }
692     return true;
693   }
694 
695   /**
696    * Modifies {@code multisetToModify} so that its count for an element
697    * {@code e} is at most {@code multisetToRetain.count(e)}.
698    *
699    * <p>To be precise, {@code multisetToModify.count(e)} is set to
700    * {@code Math.min(multisetToModify.count(e),
701    * multisetToRetain.count(e))}. This is similar to
702    * {@link #intersection(Multiset, Multiset) intersection}
703    * {@code (multisetToModify, multisetToRetain)}, but mutates
704    * {@code multisetToModify} instead of returning a view.
705    *
706    * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps
707    * all occurrences of elements that appear at all in {@code
708    * multisetToRetain}, and deletes all occurrences of all other elements.
709    *
710    * @return {@code true} if {@code multisetToModify} was changed as a result
711    *         of this operation
712    * @since 10.0
713    */
714   @CanIgnoreReturnValue
715   public static boolean retainOccurrences(
716       Multiset<?> multisetToModify, Multiset<?> multisetToRetain) {
717     return retainOccurrencesImpl(multisetToModify, multisetToRetain);
718   }
719 
720   /**
721    * Delegate implementation which cares about the element type.
722    */
723   private static <E> boolean retainOccurrencesImpl(
724       Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) {
725     checkNotNull(multisetToModify);
726     checkNotNull(occurrencesToRetain);
727     // Avoiding ConcurrentModificationExceptions is tricky.
728     Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator();
729     boolean changed = false;
730     while (entryIterator.hasNext()) {
731       Entry<E> entry = entryIterator.next();
732       int retainCount = occurrencesToRetain.count(entry.getElement());
733       if (retainCount == 0) {
734         entryIterator.remove();
735         changed = true;
736       } else if (retainCount < entry.getCount()) {
737         multisetToModify.setCount(entry.getElement(), retainCount);
738         changed = true;
739       }
740     }
741     return changed;
742   }
743 
744   /**
745    * For each occurrence of an element {@code e} in {@code occurrencesToRemove},
746    * removes one occurrence of {@code e} in {@code multisetToModify}.
747    *
748    * <p>Equivalently, this method modifies {@code multisetToModify} so that
749    * {@code multisetToModify.count(e)} is set to
750    * {@code Math.max(0, multisetToModify.count(e) -
751    * Iterables.frequency(occurrencesToRemove, e))}.
752    *
753    * <p>This is <i>not</i> the same as {@code multisetToModify.}
754    * {@link Multiset#removeAll removeAll}{@code (occurrencesToRemove)}, which
755    * removes all occurrences of elements that appear in
756    * {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent
757    * to, albeit sometimes more efficient than, the following: <pre>   {@code
758    *
759    *   for (E e : occurrencesToRemove) {
760    *     multisetToModify.remove(e);
761    *   }}</pre>
762    *
763    * @return {@code true} if {@code multisetToModify} was changed as a result of
764    *         this operation
765    * @since 18.0 (present in 10.0 with a requirement that the second parameter
766    *     be a {@code Multiset})
767    */
768   @CanIgnoreReturnValue
769   public static boolean removeOccurrences(
770       Multiset<?> multisetToModify, Iterable<?> occurrencesToRemove) {
771     if (occurrencesToRemove instanceof Multiset) {
772       return removeOccurrences(multisetToModify, (Multiset<?>) occurrencesToRemove);
773     } else {
774       checkNotNull(multisetToModify);
775       checkNotNull(occurrencesToRemove);
776       boolean changed = false;
777       for (Object o : occurrencesToRemove) {
778         changed |= multisetToModify.remove(o);
779       }
780       return changed;
781     }
782   }
783 
784   /**
785    * For each occurrence of an element {@code e} in {@code occurrencesToRemove},
786    * removes one occurrence of {@code e} in {@code multisetToModify}.
787    *
788    * <p>Equivalently, this method modifies {@code multisetToModify} so that
789    * {@code multisetToModify.count(e)} is set to
790    * {@code Math.max(0, multisetToModify.count(e) -
791    * occurrencesToRemove.count(e))}.
792    *
793    * <p>This is <i>not</i> the same as {@code multisetToModify.}
794    * {@link Multiset#removeAll removeAll}{@code (occurrencesToRemove)}, which
795    * removes all occurrences of elements that appear in
796    * {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent
797    * to, albeit sometimes more efficient than, the following: <pre>   {@code
798    *
799    *   for (E e : occurrencesToRemove) {
800    *     multisetToModify.remove(e);
801    *   }}</pre>
802    *
803    * @return {@code true} if {@code multisetToModify} was changed as a result of
804    *         this operation
805    * @since 10.0 (missing in 18.0 when only the overload taking an {@code Iterable} was present)
806    */
807   @CanIgnoreReturnValue
808   public static boolean removeOccurrences(
809       Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) {
810     checkNotNull(multisetToModify);
811     checkNotNull(occurrencesToRemove);
812 
813     boolean changed = false;
814     Iterator<? extends Entry<?>> entryIterator = multisetToModify.entrySet().iterator();
815     while (entryIterator.hasNext()) {
816       Entry<?> entry = entryIterator.next();
817       int removeCount = occurrencesToRemove.count(entry.getElement());
818       if (removeCount >= entry.getCount()) {
819         entryIterator.remove();
820         changed = true;
821       } else if (removeCount > 0) {
822         multisetToModify.remove(entry.getElement(), removeCount);
823         changed = true;
824       }
825     }
826     return changed;
827   }
828 
829   /**
830    * Implementation of the {@code equals}, {@code hashCode}, and
831    * {@code toString} methods of {@link Multiset.Entry}.
832    */
833   abstract static class AbstractEntry<E> implements Multiset.Entry<E> {
834     /**
835      * Indicates whether an object equals this entry, following the behavior
836      * specified in {@link Multiset.Entry#equals}.
837      */
838     @Override
839     public boolean equals(@Nullable Object object) {
840       if (object instanceof Multiset.Entry) {
841         Multiset.Entry<?> that = (Multiset.Entry<?>) object;
842         return this.getCount() == that.getCount()
843             && Objects.equal(this.getElement(), that.getElement());
844       }
845       return false;
846     }
847 
848     /**
849      * Return this entry's hash code, following the behavior specified in
850      * {@link Multiset.Entry#hashCode}.
851      */
852     @Override
853     public int hashCode() {
854       E e = getElement();
855       return ((e == null) ? 0 : e.hashCode()) ^ getCount();
856     }
857 
858     /**
859      * Returns a string representation of this multiset entry. The string
860      * representation consists of the associated element if the associated count
861      * is one, and otherwise the associated element followed by the characters
862      * " x " (space, x and space) followed by the count. Elements and counts are
863      * converted to strings as by {@code String.valueOf}.
864      */
865     @Override
866     public String toString() {
867       String text = String.valueOf(getElement());
868       int n = getCount();
869       return (n == 1) ? text : (text + " x " + n);
870     }
871   }
872 
873   /**
874    * An implementation of {@link Multiset#equals}.
875    */
876   static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) {
877     if (object == multiset) {
878       return true;
879     }
880     if (object instanceof Multiset) {
881       Multiset<?> that = (Multiset<?>) object;
882       /*
883        * We can't simply check whether the entry sets are equal, since that
884        * approach fails when a TreeMultiset has a comparator that returns 0
885        * when passed unequal elements.
886        */
887 
888       if (multiset.size() != that.size() || multiset.entrySet().size() != that.entrySet().size()) {
889         return false;
890       }
891       for (Entry<?> entry : that.entrySet()) {
892         if (multiset.count(entry.getElement()) != entry.getCount()) {
893           return false;
894         }
895       }
896       return true;
897     }
898     return false;
899   }
900 
901   /**
902    * An implementation of {@link Multiset#addAll}.
903    */
904   static <E> boolean addAllImpl(Multiset<E> self, Collection<? extends E> elements) {
905     if (elements.isEmpty()) {
906       return false;
907     }
908     if (elements instanceof Multiset) {
909       Multiset<? extends E> that = cast(elements);
910       for (Entry<? extends E> entry : that.entrySet()) {
911         self.add(entry.getElement(), entry.getCount());
912       }
913     } else {
914       Iterators.addAll(self, elements.iterator());
915     }
916     return true;
917   }
918 
919   /**
920    * An implementation of {@link Multiset#removeAll}.
921    */
922   static boolean removeAllImpl(Multiset<?> self, Collection<?> elementsToRemove) {
923     Collection<?> collection =
924         (elementsToRemove instanceof Multiset)
925             ? ((Multiset<?>) elementsToRemove).elementSet()
926             : elementsToRemove;
927 
928     return self.elementSet().removeAll(collection);
929   }
930 
931   /**
932    * An implementation of {@link Multiset#retainAll}.
933    */
934   static boolean retainAllImpl(Multiset<?> self, Collection<?> elementsToRetain) {
935     checkNotNull(elementsToRetain);
936     Collection<?> collection =
937         (elementsToRetain instanceof Multiset)
938             ? ((Multiset<?>) elementsToRetain).elementSet()
939             : elementsToRetain;
940 
941     return self.elementSet().retainAll(collection);
942   }
943 
944   /**
945    * An implementation of {@link Multiset#setCount(Object, int)}.
946    */
947   static <E> int setCountImpl(Multiset<E> self, E element, int count) {
948     checkNonnegative(count, "count");
949 
950     int oldCount = self.count(element);
951 
952     int delta = count - oldCount;
953     if (delta > 0) {
954       self.add(element, delta);
955     } else if (delta < 0) {
956       self.remove(element, -delta);
957     }
958 
959     return oldCount;
960   }
961 
962   /**
963    * An implementation of {@link Multiset#setCount(Object, int, int)}.
964    */
965   static <E> boolean setCountImpl(Multiset<E> self, E element, int oldCount, int newCount) {
966     checkNonnegative(oldCount, "oldCount");
967     checkNonnegative(newCount, "newCount");
968 
969     if (self.count(element) == oldCount) {
970       self.setCount(element, newCount);
971       return true;
972     } else {
973       return false;
974     }
975   }
976 
977   abstract static class ElementSet<E> extends Sets.ImprovedAbstractSet<E> {
978     abstract Multiset<E> multiset();
979 
980     @Override
981     public void clear() {
982       multiset().clear();
983     }
984 
985     @Override
986     public boolean contains(Object o) {
987       return multiset().contains(o);
988     }
989 
990     @Override
991     public boolean containsAll(Collection<?> c) {
992       return multiset().containsAll(c);
993     }
994 
995     @Override
996     public boolean isEmpty() {
997       return multiset().isEmpty();
998     }
999 
1000     @Override
1001     public Iterator<E> iterator() {
1002       return new TransformedIterator<Entry<E>, E>(multiset().entrySet().iterator()) {
1003         @Override
1004         E transform(Entry<E> entry) {
1005           return entry.getElement();
1006         }
1007       };
1008     }
1009 
1010     @Override
1011     public boolean remove(Object o) {
1012       return multiset().remove(o, Integer.MAX_VALUE) > 0;
1013     }
1014 
1015     @Override
1016     public int size() {
1017       return multiset().entrySet().size();
1018     }
1019   }
1020 
1021   abstract static class EntrySet<E> extends Sets.ImprovedAbstractSet<Entry<E>> {
1022     abstract Multiset<E> multiset();
1023 
1024     @Override
1025     public boolean contains(@Nullable Object o) {
1026       if (o instanceof Entry) {
1027         /*
1028          * The GWT compiler wrongly issues a warning here.
1029          */
1030         @SuppressWarnings("cast")
1031         Entry<?> entry = (Entry<?>) o;
1032         if (entry.getCount() <= 0) {
1033           return false;
1034         }
1035         int count = multiset().count(entry.getElement());
1036         return count == entry.getCount();
1037       }
1038       return false;
1039     }
1040 
1041     // GWT compiler warning; see contains().
1042     @SuppressWarnings("cast")
1043     @Override
1044     public boolean remove(Object object) {
1045       if (object instanceof Multiset.Entry) {
1046         Entry<?> entry = (Entry<?>) object;
1047         Object element = entry.getElement();
1048         int entryCount = entry.getCount();
1049         if (entryCount != 0) {
1050           // Safe as long as we never add a new entry, which we won't.
1051           @SuppressWarnings("unchecked")
1052           Multiset<Object> multiset = (Multiset) multiset();
1053           return multiset.setCount(element, entryCount, 0);
1054         }
1055       }
1056       return false;
1057     }
1058 
1059     @Override
1060     public void clear() {
1061       multiset().clear();
1062     }
1063   }
1064 
1065   /**
1066    * An implementation of {@link Multiset#iterator}.
1067    */
1068   static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
1069     return new MultisetIteratorImpl<E>(multiset, multiset.entrySet().iterator());
1070   }
1071 
1072   static final class MultisetIteratorImpl<E> implements Iterator<E> {
1073     private final Multiset<E> multiset;
1074     private final Iterator<Entry<E>> entryIterator;
1075     private Entry<E> currentEntry;
1076 
1077     /** Count of subsequent elements equal to current element */
1078     private int laterCount;
1079 
1080     /** Count of all elements equal to current element */
1081     private int totalCount;
1082 
1083     private boolean canRemove;
1084 
1085     MultisetIteratorImpl(Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
1086       this.multiset = multiset;
1087       this.entryIterator = entryIterator;
1088     }
1089 
1090     @Override
1091     public boolean hasNext() {
1092       return laterCount > 0 || entryIterator.hasNext();
1093     }
1094 
1095     @Override
1096     public E next() {
1097       if (!hasNext()) {
1098         throw new NoSuchElementException();
1099       }
1100       if (laterCount == 0) {
1101         currentEntry = entryIterator.next();
1102         totalCount = laterCount = currentEntry.getCount();
1103       }
1104       laterCount--;
1105       canRemove = true;
1106       return currentEntry.getElement();
1107     }
1108 
1109     @Override
1110     public void remove() {
1111       checkRemove(canRemove);
1112       if (totalCount == 1) {
1113         entryIterator.remove();
1114       } else {
1115         multiset.remove(currentEntry.getElement());
1116       }
1117       totalCount--;
1118       canRemove = false;
1119     }
1120   }
1121 
1122   static <E> Spliterator<E> spliteratorImpl(Multiset<E> multiset) {
1123     Spliterator<Entry<E>> entrySpliterator = multiset.entrySet().spliterator();
1124     return CollectSpliterators.flatMap(
1125         entrySpliterator,
1126         entry -> Collections.nCopies(entry.getCount(), entry.getElement()).spliterator(),
1127         Spliterator.SIZED
1128             | (entrySpliterator.characteristics()
1129                 & (Spliterator.ORDERED | Spliterator.NONNULL | Spliterator.IMMUTABLE)),
1130         multiset.size());
1131   }
1132 
1133   /**
1134    * An implementation of {@link Multiset#size}.
1135    */
1136   static int sizeImpl(Multiset<?> multiset) {
1137     long size = 0;
1138     for (Entry<?> entry : multiset.entrySet()) {
1139       size += entry.getCount();
1140     }
1141     return Ints.saturatedCast(size);
1142   }
1143 
1144   /**
1145    * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557
1146    */
1147   static <T> Multiset<T> cast(Iterable<T> iterable) {
1148     return (Multiset<T>) iterable;
1149   }
1150 
1151   /**
1152    * Returns a copy of {@code multiset} as an {@link ImmutableMultiset} whose iteration order is
1153    * highest count first, with ties broken by the iteration order of the original multiset.
1154    *
1155    * @since 11.0
1156    */
1157   @Beta
1158   public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) {
1159     Entry<E>[] entries = (Entry<E>[]) multiset.entrySet().toArray(new Entry[0]);
1160     Arrays.sort(entries, DecreasingCount.INSTANCE);
1161     return ImmutableMultiset.copyFromEntries(Arrays.asList(entries));
1162   }
1163 
1164   private static final class DecreasingCount implements Comparator<Entry<?>> {
1165     static final DecreasingCount INSTANCE = new DecreasingCount();
1166 
1167     @Override public int compare(Entry<?> entry1, Entry<?> entry2) {
1168       return entry2.getCount() - entry1.getCount(); // subtracting two nonnegative integers
1169     }
1170   }
1171 }