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