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