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