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 import static com.google.common.base.Preconditions.checkState;
022
023 import java.io.Serializable;
024 import java.util.AbstractSet;
025 import java.util.Collection;
026 import java.util.Collections;
027 import java.util.Comparator;
028 import java.util.Iterator;
029 import java.util.List;
030 import java.util.NoSuchElementException;
031 import java.util.Set;
032 import java.util.SortedSet;
033
034 import javax.annotation.Nullable;
035
036 import com.google.common.annotations.Beta;
037 import com.google.common.annotations.GwtCompatible;
038 import com.google.common.base.Function;
039 import com.google.common.base.Objects;
040 import com.google.common.collect.Multiset.Entry;
041 import com.google.common.primitives.Ints;
042
043 /**
044 * Provides static utility methods for creating and working with {@link
045 * Multiset} instances.
046 *
047 * @author Kevin Bourrillion
048 * @author Mike Bostock
049 * @author Louis Wasserman
050 * @since 2.0 (imported from Google Collections Library)
051 */
052 @GwtCompatible
053 public final class Multisets {
054 private Multisets() {}
055
056 /**
057 * Returns an unmodifiable view of the specified multiset. Query operations on
058 * the returned multiset "read through" to the specified multiset, and
059 * attempts to modify the returned multiset result in an
060 * {@link UnsupportedOperationException}.
061 *
062 * <p>The returned multiset will be serializable if the specified multiset is
063 * serializable.
064 *
065 * @param multiset the multiset for which an unmodifiable view is to be
066 * generated
067 * @return an unmodifiable view of the multiset
068 */
069 public static <E> Multiset<E> unmodifiableMultiset(
070 Multiset<? extends E> multiset) {
071 if (multiset instanceof UnmodifiableMultiset ||
072 multiset instanceof ImmutableMultiset) {
073 // Since it's unmodifiable, the covariant cast is safe
074 @SuppressWarnings("unchecked")
075 Multiset<E> result = (Multiset<E>) multiset;
076 return result;
077 }
078 return new UnmodifiableMultiset<E>(checkNotNull(multiset));
079 }
080
081 /**
082 * Simply returns its argument.
083 *
084 * @deprecated no need to use this
085 * @since 10.0
086 */
087 @Deprecated public static <E> Multiset<E> unmodifiableMultiset(
088 ImmutableMultiset<E> multiset) {
089 return checkNotNull(multiset);
090 }
091
092 static class UnmodifiableMultiset<E>
093 extends ForwardingMultiset<E> implements Serializable {
094 final Multiset<? extends E> delegate;
095
096 UnmodifiableMultiset(Multiset<? extends E> delegate) {
097 this.delegate = delegate;
098 }
099
100 @SuppressWarnings("unchecked")
101 @Override protected Multiset<E> delegate() {
102 // This is safe because all non-covariant methods are overriden
103 return (Multiset<E>) delegate;
104 }
105
106 transient Set<E> elementSet;
107
108 Set<E> createElementSet() {
109 return Collections.<E>unmodifiableSet(delegate.elementSet());
110 }
111
112 @Override
113 public Set<E> elementSet() {
114 Set<E> es = elementSet;
115 return (es == null) ? elementSet = createElementSet() : es;
116 }
117
118 transient Set<Multiset.Entry<E>> entrySet;
119
120 @SuppressWarnings("unchecked")
121 @Override public Set<Multiset.Entry<E>> entrySet() {
122 Set<Multiset.Entry<E>> es = entrySet;
123 return (es == null)
124 // Safe because the returned set is made unmodifiable and Entry
125 // itself is readonly
126 ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet())
127 : es;
128 }
129
130 @SuppressWarnings("unchecked")
131 @Override public Iterator<E> iterator() {
132 // Safe because the returned Iterator is made unmodifiable
133 return (Iterator<E>) Iterators.unmodifiableIterator(delegate.iterator());
134 }
135
136 @Override public boolean add(E element) {
137 throw new UnsupportedOperationException();
138 }
139
140 @Override public int add(E element, int occurences) {
141 throw new UnsupportedOperationException();
142 }
143
144 @Override public boolean addAll(Collection<? extends E> elementsToAdd) {
145 throw new UnsupportedOperationException();
146 }
147
148 @Override public boolean remove(Object element) {
149 throw new UnsupportedOperationException();
150 }
151
152 @Override public int remove(Object element, int occurrences) {
153 throw new UnsupportedOperationException();
154 }
155
156 @Override public boolean removeAll(Collection<?> elementsToRemove) {
157 throw new UnsupportedOperationException();
158 }
159
160 @Override public boolean retainAll(Collection<?> elementsToRetain) {
161 throw new UnsupportedOperationException();
162 }
163
164 @Override public void clear() {
165 throw new UnsupportedOperationException();
166 }
167
168 @Override public int setCount(E element, int count) {
169 throw new UnsupportedOperationException();
170 }
171
172 @Override public boolean setCount(E element, int oldCount, int newCount) {
173 throw new UnsupportedOperationException();
174 }
175
176 private static final long serialVersionUID = 0;
177 }
178
179 /**
180 * Returns an unmodifiable view of the specified sorted multiset. Query
181 * operations on the returned multiset "read through" to the specified
182 * multiset, and attempts to modify the returned multiset result in an {@link
183 * UnsupportedOperationException}.
184 *
185 * <p>The returned multiset will be serializable if the specified multiset is
186 * serializable.
187 *
188 * @param sortedMultiset the sorted multiset for which an unmodifiable view is
189 * to be generated
190 * @return an unmodifiable view of the multiset
191 * @since 11.0
192 */
193 @Beta
194 public static <E> SortedMultiset<E> unmodifiableSortedMultiset(
195 SortedMultiset<E> sortedMultiset) {
196 return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset));
197 }
198
199 private static final class UnmodifiableSortedMultiset<E>
200 extends UnmodifiableMultiset<E> implements SortedMultiset<E> {
201 private UnmodifiableSortedMultiset(SortedMultiset<E> delegate) {
202 super(delegate);
203 }
204
205 @Override
206 protected SortedMultiset<E> delegate() {
207 return (SortedMultiset<E>) super.delegate();
208 }
209
210 @Override
211 public Comparator<? super E> comparator() {
212 return delegate().comparator();
213 }
214
215 @Override
216 SortedSet<E> createElementSet() {
217 return Collections.unmodifiableSortedSet(delegate().elementSet());
218 }
219
220 @Override
221 public SortedSet<E> elementSet() {
222 return (SortedSet<E>) super.elementSet();
223 }
224
225 private transient UnmodifiableSortedMultiset<E> descendingMultiset;
226
227 @Override
228 public SortedMultiset<E> descendingMultiset() {
229 UnmodifiableSortedMultiset<E> result = descendingMultiset;
230 if (result == null) {
231 result = new UnmodifiableSortedMultiset<E>(
232 delegate().descendingMultiset());
233 result.descendingMultiset = this;
234 return descendingMultiset = result;
235 }
236 return result;
237 }
238
239 @Override
240 public Entry<E> firstEntry() {
241 return delegate().firstEntry();
242 }
243
244 @Override
245 public Entry<E> lastEntry() {
246 return delegate().lastEntry();
247 }
248
249 @Override
250 public Entry<E> pollFirstEntry() {
251 throw new UnsupportedOperationException();
252 }
253
254 @Override
255 public Entry<E> pollLastEntry() {
256 throw new UnsupportedOperationException();
257 }
258
259 @Override
260 public SortedMultiset<E> headMultiset(E upperBound, BoundType boundType) {
261 return unmodifiableSortedMultiset(
262 delegate().headMultiset(upperBound, boundType));
263 }
264
265 @Override
266 public SortedMultiset<E> subMultiset(
267 E lowerBound, BoundType lowerBoundType,
268 E upperBound, BoundType upperBoundType) {
269 return unmodifiableSortedMultiset(delegate().subMultiset(
270 lowerBound, lowerBoundType, upperBound, upperBoundType));
271 }
272
273 @Override
274 public SortedMultiset<E> tailMultiset(E lowerBound, BoundType boundType) {
275 return unmodifiableSortedMultiset(
276 delegate().tailMultiset(lowerBound, boundType));
277 }
278
279 private static final long serialVersionUID = 0;
280 }
281
282 /**
283 * Returns an immutable multiset entry with the specified element and count.
284 * The entry will be serializable if {@code e} is.
285 *
286 * @param e the element to be associated with the returned entry
287 * @param n the count to be associated with the returned entry
288 * @throws IllegalArgumentException if {@code n} is negative
289 */
290 public static <E> Multiset.Entry<E> immutableEntry(@Nullable E e, int n) {
291 return new ImmutableEntry<E>(e, n);
292 }
293
294 static final class ImmutableEntry<E> extends AbstractEntry<E> implements
295 Serializable {
296 @Nullable final E element;
297 final int count;
298
299 ImmutableEntry(@Nullable E element, int count) {
300 this.element = element;
301 this.count = count;
302 checkArgument(count >= 0);
303 }
304
305 @Override
306 @Nullable public E getElement() {
307 return element;
308 }
309
310 @Override
311 public int getCount() {
312 return count;
313 }
314
315 private static final long serialVersionUID = 0;
316 }
317
318 /**
319 * Returns a multiset view of the specified set. The multiset is backed by the
320 * set, so changes to the set are reflected in the multiset, and vice versa.
321 * If the set is modified while an iteration over the multiset is in progress
322 * (except through the iterator's own {@code remove} operation) the results of
323 * the iteration are undefined.
324 *
325 * <p>The multiset supports element removal, which removes the corresponding
326 * element from the set. It does not support the {@code add} or {@code addAll}
327 * operations, nor does it support the use of {@code setCount} to add
328 * elements.
329 *
330 * <p>The returned multiset will be serializable if the specified set is
331 * serializable. The multiset is threadsafe if the set is threadsafe.
332 *
333 * @param set the backing set for the returned multiset view
334 */
335 static <E> Multiset<E> forSet(Set<E> set) {
336 return new SetMultiset<E>(set);
337 }
338
339 /** @see Multisets#forSet */
340 private static class SetMultiset<E> extends ForwardingCollection<E>
341 implements Multiset<E>, Serializable {
342 final Set<E> delegate;
343
344 SetMultiset(Set<E> set) {
345 delegate = checkNotNull(set);
346 }
347
348 @Override protected Set<E> delegate() {
349 return delegate;
350 }
351
352 @Override
353 public int count(Object element) {
354 return delegate.contains(element) ? 1 : 0;
355 }
356
357 @Override
358 public int add(E element, int occurrences) {
359 throw new UnsupportedOperationException();
360 }
361
362 @Override
363 public int remove(Object element, int occurrences) {
364 if (occurrences == 0) {
365 return count(element);
366 }
367 checkArgument(occurrences > 0);
368 return delegate.remove(element) ? 1 : 0;
369 }
370
371 transient Set<E> elementSet;
372
373 @Override
374 public Set<E> elementSet() {
375 Set<E> es = elementSet;
376 return (es == null) ? elementSet = new ElementSet() : es;
377 }
378
379 transient Set<Entry<E>> entrySet;
380
381 @Override public Set<Entry<E>> entrySet() {
382 Set<Entry<E>> es = entrySet;
383 if (es == null) {
384 es = entrySet = new EntrySet<E>() {
385 @Override Multiset<E> multiset() {
386 return SetMultiset.this;
387 }
388
389 @Override public Iterator<Entry<E>> iterator() {
390 return Iterators.transform(delegate.iterator(),
391 new Function<E, Entry<E>>() {
392 @Override public Entry<E> apply(E elem) {
393 return immutableEntry(elem, 1);
394 }
395 });
396 }
397
398 @Override public int size() {
399 return delegate.size();
400 }
401 };
402 }
403 return es;
404 }
405
406 @Override public boolean add(E o) {
407 throw new UnsupportedOperationException();
408 }
409
410 @Override public boolean addAll(Collection<? extends E> c) {
411 throw new UnsupportedOperationException();
412 }
413
414 @Override
415 public int setCount(E element, int count) {
416 checkNonnegative(count, "count");
417
418 if (count == count(element)) {
419 return count;
420 } else if (count == 0) {
421 remove(element);
422 return 1;
423 } else {
424 throw new UnsupportedOperationException();
425 }
426 }
427
428 @Override
429 public boolean setCount(E element, int oldCount, int newCount) {
430 return setCountImpl(this, element, oldCount, newCount);
431 }
432
433 @Override public boolean equals(@Nullable Object object) {
434 if (object instanceof Multiset) {
435 Multiset<?> that = (Multiset<?>) object;
436 return this.size() == that.size() && delegate.equals(that.elementSet());
437 }
438 return false;
439 }
440
441 @Override public int hashCode() {
442 int sum = 0;
443 for (E e : this) {
444 sum += ((e == null) ? 0 : e.hashCode()) ^ 1;
445 }
446 return sum;
447 }
448
449 /** @see SetMultiset#elementSet */
450 class ElementSet extends ForwardingSet<E> {
451 @Override protected Set<E> delegate() {
452 return delegate;
453 }
454
455 @Override public boolean add(E o) {
456 throw new UnsupportedOperationException();
457 }
458
459 @Override public boolean addAll(Collection<? extends E> c) {
460 throw new UnsupportedOperationException();
461 }
462 }
463
464 private static final long serialVersionUID = 0;
465 }
466
467 /**
468 * Returns the expected number of distinct elements given the specified
469 * elements. The number of distinct elements is only computed if {@code
470 * elements} is an instance of {@code Multiset}; otherwise the default value
471 * of 11 is returned.
472 */
473 static int inferDistinctElements(Iterable<?> elements) {
474 if (elements instanceof Multiset) {
475 return ((Multiset<?>) elements).elementSet().size();
476 }
477 return 11; // initial capacity will be rounded up to 16
478 }
479
480 /**
481 * Returns an unmodifiable <b>view</b> of the intersection of two multisets.
482 * An element's count in the multiset is the smaller of its counts in the two
483 * backing multisets. The iteration order of the returned multiset matches the
484 * element set of {@code multiset1}, with repeated occurrences of the same
485 * element appearing consecutively.
486 *
487 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are
488 * based on different equivalence relations (as {@code HashMultiset} and
489 * {@code TreeMultiset} are).
490 *
491 * @since 2.0
492 */
493 public static <E> Multiset<E> intersection(
494 final Multiset<E> multiset1, final Multiset<?> multiset2) {
495 checkNotNull(multiset1);
496 checkNotNull(multiset2);
497
498 return new AbstractMultiset<E>() {
499 @Override
500 public int count(Object element) {
501 int count1 = multiset1.count(element);
502 return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element));
503 }
504
505 @Override
506 Set<E> createElementSet() {
507 return Sets.intersection(
508 multiset1.elementSet(), multiset2.elementSet());
509 }
510
511 @Override
512 Iterator<Entry<E>> entryIterator() {
513 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator();
514 return new AbstractIterator<Entry<E>>() {
515 @Override
516 protected Entry<E> computeNext() {
517 while (iterator1.hasNext()) {
518 Entry<E> entry1 = iterator1.next();
519 E element = entry1.getElement();
520 int count = Math.min(entry1.getCount(), multiset2.count(element));
521 if (count > 0) {
522 return Multisets.immutableEntry(element, count);
523 }
524 }
525 return endOfData();
526 }
527 };
528 }
529
530 @Override
531 int distinctElements() {
532 return elementSet().size();
533 }
534 };
535 }
536
537 /**
538 * Returns {@code true} if {@code subMultiset.count(o) <=
539 * superMultiset.count(o)} for all {@code o}.
540 *
541 * @since 10.0
542 */
543 @Beta
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 @Beta 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 @Beta 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 Collection<?> collection = (elementsToRetain instanceof Multiset)
764 ? ((Multiset<?>) elementsToRetain).elementSet() : elementsToRetain;
765
766 return self.elementSet().retainAll(collection);
767 }
768
769 /**
770 * An implementation of {@link Multiset#setCount(Object, int)}.
771 */
772 static <E> int setCountImpl(Multiset<E> self, E element, int count) {
773 checkNonnegative(count, "count");
774
775 int oldCount = self.count(element);
776
777 int delta = count - oldCount;
778 if (delta > 0) {
779 self.add(element, delta);
780 } else if (delta < 0) {
781 self.remove(element, -delta);
782 }
783
784 return oldCount;
785 }
786
787 /**
788 * An implementation of {@link Multiset#setCount(Object, int, int)}.
789 */
790 static <E> boolean setCountImpl(
791 Multiset<E> self, E element, int oldCount, int newCount) {
792 checkNonnegative(oldCount, "oldCount");
793 checkNonnegative(newCount, "newCount");
794
795 if (self.count(element) == oldCount) {
796 self.setCount(element, newCount);
797 return true;
798 } else {
799 return false;
800 }
801 }
802
803 static abstract class ElementSet<E> extends AbstractSet<E> {
804 abstract Multiset<E> multiset();
805
806 @Override public void clear() {
807 multiset().clear();
808 }
809
810 @Override public boolean contains(Object o) {
811 return multiset().contains(o);
812 }
813
814 @Override public boolean containsAll(Collection<?> c) {
815 return multiset().containsAll(c);
816 }
817
818 @Override public boolean isEmpty() {
819 return multiset().isEmpty();
820 }
821
822 @Override public Iterator<E> iterator() {
823 return Iterators.transform(multiset().entrySet().iterator(),
824 new Function<Entry<E>, E>() {
825 @Override public E apply(Entry<E> entry) {
826 return entry.getElement();
827 }
828 });
829 }
830
831 @Override
832 public boolean remove(Object o) {
833 int count = multiset().count(o);
834 if (count > 0) {
835 multiset().remove(o, count);
836 return true;
837 }
838 return false;
839 }
840
841 @Override public int size() {
842 return multiset().entrySet().size();
843 }
844 }
845
846 static abstract class EntrySet<E> extends AbstractSet<Entry<E>>{
847 abstract Multiset<E> multiset();
848
849 @Override public boolean contains(@Nullable Object o) {
850 if (o instanceof Entry) {
851 @SuppressWarnings("cast")
852 Entry<?> entry = (Entry<?>) o;
853 if (entry.getCount() <= 0) {
854 return false;
855 }
856 int count = multiset().count(entry.getElement());
857 return count == entry.getCount();
858
859 }
860 return false;
861 }
862
863 @SuppressWarnings("cast")
864 @Override public boolean remove(Object o) {
865 return contains(o)
866 && multiset().elementSet().remove(((Entry<?>) o).getElement());
867 }
868
869 @Override public void clear() {
870 multiset().clear();
871 }
872 }
873
874 /**
875 * An implementation of {@link Multiset#iterator}.
876 */
877 static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) {
878 return new MultisetIteratorImpl<E>(
879 multiset, multiset.entrySet().iterator());
880 }
881
882 static final class MultisetIteratorImpl<E> implements Iterator<E> {
883 private final Multiset<E> multiset;
884 private final Iterator<Entry<E>> entryIterator;
885 private Entry<E> currentEntry;
886 /** Count of subsequent elements equal to current element */
887 private int laterCount;
888 /** Count of all elements equal to current element */
889 private int totalCount;
890 private boolean canRemove;
891
892 MultisetIteratorImpl(
893 Multiset<E> multiset, Iterator<Entry<E>> entryIterator) {
894 this.multiset = multiset;
895 this.entryIterator = entryIterator;
896 }
897
898 @Override
899 public boolean hasNext() {
900 return laterCount > 0 || entryIterator.hasNext();
901 }
902
903 @Override
904 public E next() {
905 if (!hasNext()) {
906 throw new NoSuchElementException();
907 }
908 if (laterCount == 0) {
909 currentEntry = entryIterator.next();
910 totalCount = laterCount = currentEntry.getCount();
911 }
912 laterCount--;
913 canRemove = true;
914 return currentEntry.getElement();
915 }
916
917 @Override
918 public void remove() {
919 checkState(
920 canRemove, "no calls to next() since the last call to remove()");
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 }