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 }