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