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.Collection;
030 import java.util.Collections;
031 import java.util.Comparator;
032 import java.util.Iterator;
033 import java.util.List;
034 import java.util.NoSuchElementException;
035 import java.util.Set;
036 import java.util.SortedSet;
037
038 import 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
054 public 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 }