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