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