001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkNonnegative; 022import static com.google.common.collect.CollectPreconditions.checkRemove; 023import static java.lang.Math.max; 024import static java.lang.Math.min; 025import static java.util.Arrays.asList; 026import static java.util.Objects.requireNonNull; 027 028import com.google.common.annotations.GwtCompatible; 029import com.google.common.base.Objects; 030import com.google.common.base.Predicate; 031import com.google.common.base.Predicates; 032import com.google.common.collect.Multiset.Entry; 033import com.google.common.math.IntMath; 034import com.google.common.primitives.Ints; 035import com.google.errorprone.annotations.CanIgnoreReturnValue; 036import com.google.errorprone.annotations.concurrent.LazyInit; 037import java.io.Serializable; 038import java.util.Arrays; 039import java.util.Collection; 040import java.util.Collections; 041import java.util.Comparator; 042import java.util.Iterator; 043import java.util.NoSuchElementException; 044import java.util.Set; 045import java.util.function.Function; 046import java.util.function.Supplier; 047import java.util.function.ToIntFunction; 048import java.util.stream.Collector; 049import org.checkerframework.checker.nullness.qual.Nullable; 050 051/** 052 * Provides static utility methods for creating and working with {@link Multiset} instances. 053 * 054 * <p>See the Guava User Guide article on <a href= 055 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#multisets">{@code 056 * Multisets}</a>. 057 * 058 * @author Kevin Bourrillion 059 * @author Mike Bostock 060 * @author Louis Wasserman 061 * @since 2.0 062 */ 063@GwtCompatible 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 33.2.0 (available since 22.0 in guava-jre) 083 */ 084 @SuppressWarnings("Java7ApiChecker") 085 @IgnoreJRERequirement // Users will use this only if they're already using streams. 086 public static <T extends @Nullable Object, E extends @Nullable Object, M extends Multiset<E>> 087 Collector<T, ?, M> toMultiset( 088 Function<? super T, E> elementFunction, 089 ToIntFunction<? super T> countFunction, 090 Supplier<M> multisetSupplier) { 091 return CollectCollectors.toMultiset(elementFunction, countFunction, multisetSupplier); 092 } 093 094 /** 095 * Returns an unmodifiable view of the specified multiset. Query operations on the returned 096 * multiset "read through" to the specified multiset, and attempts to modify the returned multiset 097 * result in an {@link UnsupportedOperationException}. 098 * 099 * <p>The returned multiset will be serializable if the specified multiset is serializable. 100 * 101 * @param multiset the multiset for which an unmodifiable view is to be generated 102 * @return an unmodifiable view of the multiset 103 */ 104 public static <E extends @Nullable Object> Multiset<E> unmodifiableMultiset( 105 Multiset<? extends E> multiset) { 106 if (multiset instanceof UnmodifiableMultiset || multiset instanceof ImmutableMultiset) { 107 @SuppressWarnings("unchecked") // Since it's unmodifiable, the covariant cast is safe 108 Multiset<E> result = (Multiset<E>) multiset; 109 return result; 110 } 111 return new UnmodifiableMultiset<>(checkNotNull(multiset)); 112 } 113 114 /** 115 * Simply returns its argument. 116 * 117 * @deprecated no need to use this 118 * @since 10.0 119 */ 120 @Deprecated 121 public static <E> Multiset<E> unmodifiableMultiset(ImmutableMultiset<E> multiset) { 122 return checkNotNull(multiset); 123 } 124 125 static class UnmodifiableMultiset<E extends @Nullable Object> extends ForwardingMultiset<E> 126 implements Serializable { 127 final Multiset<? extends E> delegate; 128 129 UnmodifiableMultiset(Multiset<? extends E> delegate) { 130 this.delegate = delegate; 131 } 132 133 @SuppressWarnings("unchecked") 134 @Override 135 protected Multiset<E> delegate() { 136 // This is safe because all non-covariant methods are overridden 137 return (Multiset<E>) delegate; 138 } 139 140 @LazyInit transient @Nullable Set<E> elementSet; 141 142 Set<E> createElementSet() { 143 return Collections.<E>unmodifiableSet(delegate.elementSet()); 144 } 145 146 @Override 147 public Set<E> elementSet() { 148 Set<E> es = elementSet; 149 return (es == null) ? elementSet = createElementSet() : es; 150 } 151 152 @LazyInit transient @Nullable Set<Multiset.Entry<E>> entrySet; 153 154 @SuppressWarnings("unchecked") 155 @Override 156 public Set<Multiset.Entry<E>> entrySet() { 157 Set<Multiset.Entry<E>> es = entrySet; 158 return (es == null) 159 // Safe because the returned set is made unmodifiable and Entry 160 // itself is readonly 161 ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet()) 162 : es; 163 } 164 165 @Override 166 public Iterator<E> iterator() { 167 return Iterators.<E>unmodifiableIterator(delegate.iterator()); 168 } 169 170 @Override 171 public boolean add(@ParametricNullness E element) { 172 throw new UnsupportedOperationException(); 173 } 174 175 @Override 176 public int add(@ParametricNullness E element, int occurrences) { 177 throw new UnsupportedOperationException(); 178 } 179 180 @Override 181 public boolean addAll(Collection<? extends E> elementsToAdd) { 182 throw new UnsupportedOperationException(); 183 } 184 185 @Override 186 public boolean remove(@Nullable Object element) { 187 throw new UnsupportedOperationException(); 188 } 189 190 @Override 191 public int remove(@Nullable Object element, int occurrences) { 192 throw new UnsupportedOperationException(); 193 } 194 195 @Override 196 public boolean removeAll(Collection<?> elementsToRemove) { 197 throw new UnsupportedOperationException(); 198 } 199 200 @Override 201 public boolean retainAll(Collection<?> elementsToRetain) { 202 throw new UnsupportedOperationException(); 203 } 204 205 @Override 206 public void clear() { 207 throw new UnsupportedOperationException(); 208 } 209 210 @Override 211 public int setCount(@ParametricNullness E element, int count) { 212 throw new UnsupportedOperationException(); 213 } 214 215 @Override 216 public boolean setCount(@ParametricNullness E element, int oldCount, int newCount) { 217 throw new UnsupportedOperationException(); 218 } 219 220 private static final long serialVersionUID = 0; 221 } 222 223 /** 224 * Returns an unmodifiable view of the specified sorted multiset. Query operations on the returned 225 * multiset "read through" to the specified multiset, and attempts to modify the returned multiset 226 * result in an {@link UnsupportedOperationException}. 227 * 228 * <p>The returned multiset will be serializable if the specified multiset is serializable. 229 * 230 * @param sortedMultiset the sorted multiset for which an unmodifiable view is to be generated 231 * @return an unmodifiable view of the multiset 232 * @since 11.0 233 */ 234 public static <E extends @Nullable Object> SortedMultiset<E> unmodifiableSortedMultiset( 235 SortedMultiset<E> sortedMultiset) { 236 // it's in its own file so it can be emulated for GWT 237 return new UnmodifiableSortedMultiset<>(checkNotNull(sortedMultiset)); 238 } 239 240 /** 241 * Returns an immutable multiset entry with the specified element and count. The entry will be 242 * serializable if {@code e} is. 243 * 244 * @param e the element to be associated with the returned entry 245 * @param n the count to be associated with the returned entry 246 * @throws IllegalArgumentException if {@code n} is negative 247 */ 248 public static <E extends @Nullable Object> Multiset.Entry<E> immutableEntry( 249 @ParametricNullness E e, int n) { 250 return new ImmutableEntry<>(e, n); 251 } 252 253 static class ImmutableEntry<E extends @Nullable Object> extends AbstractEntry<E> 254 implements Serializable { 255 @ParametricNullness private final E element; 256 private final int count; 257 258 ImmutableEntry(@ParametricNullness E element, int count) { 259 this.element = element; 260 this.count = count; 261 checkNonnegative(count, "count"); 262 } 263 264 @Override 265 @ParametricNullness 266 public final E getElement() { 267 return element; 268 } 269 270 @Override 271 public final int getCount() { 272 return count; 273 } 274 275 public @Nullable 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(@Nullable 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(@Nullable 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(@Nullable 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(@Nullable Object element) { 431 return 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 protected @Nullable Entry<E> computeNext() { 452 if (iterator1.hasNext()) { 453 Entry<? extends E> entry1 = iterator1.next(); 454 E element = entry1.getElement(); 455 int count = max(entry1.getCount(), multiset2.count(element)); 456 return immutableEntry(element, count); 457 } 458 while (iterator2.hasNext()) { 459 Entry<? extends E> entry2 = iterator2.next(); 460 E element = entry2.getElement(); 461 if (!multiset1.contains(element)) { 462 return immutableEntry(element, entry2.getCount()); 463 } 464 } 465 return endOfData(); 466 } 467 }; 468 } 469 }; 470 } 471 472 /** 473 * Returns an unmodifiable view of the intersection of two multisets. In the returned multiset, 474 * the count of each element is the <i>minimum</i> of its counts in the two backing multisets, 475 * with elements that would have a count of 0 not included. The iteration order of the returned 476 * multiset matches that of the element set of {@code multiset1}, with repeated occurrences of the 477 * same element appearing consecutively. 478 * 479 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different 480 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are). 481 * 482 * @since 2.0 483 */ 484 public static <E extends @Nullable Object> Multiset<E> intersection( 485 final Multiset<E> multiset1, final Multiset<?> multiset2) { 486 checkNotNull(multiset1); 487 checkNotNull(multiset2); 488 489 return new ViewMultiset<E>() { 490 @Override 491 public int count(@Nullable Object element) { 492 int count1 = multiset1.count(element); 493 return (count1 == 0) ? 0 : min(count1, multiset2.count(element)); 494 } 495 496 @Override 497 Set<E> createElementSet() { 498 return Sets.intersection(multiset1.elementSet(), multiset2.elementSet()); 499 } 500 501 @Override 502 Iterator<E> elementIterator() { 503 throw new AssertionError("should never be called"); 504 } 505 506 @Override 507 Iterator<Entry<E>> entryIterator() { 508 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator(); 509 // TODO(lowasser): consider making the entries live views 510 return new AbstractIterator<Entry<E>>() { 511 @Override 512 protected @Nullable Entry<E> computeNext() { 513 while (iterator1.hasNext()) { 514 Entry<E> entry1 = iterator1.next(); 515 E element = entry1.getElement(); 516 int count = 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(@Nullable 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(@Nullable 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 protected @Nullable Entry<E> computeNext() { 584 if (iterator1.hasNext()) { 585 Entry<? extends E> entry1 = iterator1.next(); 586 E element = entry1.getElement(); 587 int count = entry1.getCount() + multiset2.count(element); 588 return immutableEntry(element, count); 589 } 590 while (iterator2.hasNext()) { 591 Entry<? extends E> entry2 = iterator2.next(); 592 E element = entry2.getElement(); 593 if (!multiset1.contains(element)) { 594 return immutableEntry(element, entry2.getCount()); 595 } 596 } 597 return endOfData(); 598 } 599 }; 600 } 601 }; 602 } 603 604 /** 605 * Returns an unmodifiable view of the difference of two multisets. In the returned multiset, the 606 * count of each element is the result of the <i>zero-truncated subtraction</i> of its count in 607 * the second multiset from its count in the first multiset, with elements that would have a count 608 * of 0 not included. The iteration order of the returned multiset matches that of the element set 609 * of {@code multiset1}, with repeated occurrences of the same element appearing consecutively. 610 * 611 * <p>Results are undefined if {@code multiset1} and {@code multiset2} are based on different 612 * equivalence relations (as {@code HashMultiset} and {@code TreeMultiset} are). 613 * 614 * @since 14.0 615 */ 616 public static <E extends @Nullable Object> Multiset<E> difference( 617 final Multiset<E> multiset1, final Multiset<?> multiset2) { 618 checkNotNull(multiset1); 619 checkNotNull(multiset2); 620 621 // TODO(lowasser): consider making the entries live views 622 return new ViewMultiset<E>() { 623 @Override 624 public int count(@Nullable Object element) { 625 int count1 = multiset1.count(element); 626 return (count1 == 0) ? 0 : max(0, count1 - multiset2.count(element)); 627 } 628 629 @Override 630 public void clear() { 631 throw new UnsupportedOperationException(); 632 } 633 634 @Override 635 Iterator<E> elementIterator() { 636 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator(); 637 return new AbstractIterator<E>() { 638 @Override 639 protected @Nullable E computeNext() { 640 while (iterator1.hasNext()) { 641 Entry<E> entry1 = iterator1.next(); 642 E element = entry1.getElement(); 643 if (entry1.getCount() > multiset2.count(element)) { 644 return element; 645 } 646 } 647 return endOfData(); 648 } 649 }; 650 } 651 652 @Override 653 Iterator<Entry<E>> entryIterator() { 654 final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator(); 655 return new AbstractIterator<Entry<E>>() { 656 @Override 657 protected @Nullable Entry<E> computeNext() { 658 while (iterator1.hasNext()) { 659 Entry<E> entry1 = iterator1.next(); 660 E element = entry1.getElement(); 661 int count = entry1.getCount() - multiset2.count(element); 662 if (count > 0) { 663 return immutableEntry(element, count); 664 } 665 } 666 return endOfData(); 667 } 668 }; 669 } 670 671 @Override 672 int distinctElements() { 673 return Iterators.size(entryIterator()); 674 } 675 }; 676 } 677 678 /** 679 * Returns {@code true} if {@code subMultiset.count(o) <= superMultiset.count(o)} for all {@code 680 * o}. 681 * 682 * @since 10.0 683 */ 684 @CanIgnoreReturnValue 685 public static boolean containsOccurrences(Multiset<?> superMultiset, Multiset<?> subMultiset) { 686 checkNotNull(superMultiset); 687 checkNotNull(subMultiset); 688 for (Entry<?> entry : subMultiset.entrySet()) { 689 int superCount = superMultiset.count(entry.getElement()); 690 if (superCount < entry.getCount()) { 691 return false; 692 } 693 } 694 return true; 695 } 696 697 /** 698 * Modifies {@code multisetToModify} so that its count for an element {@code e} is at most {@code 699 * multisetToRetain.count(e)}. 700 * 701 * <p>To be precise, {@code multisetToModify.count(e)} is set to {@code 702 * Math.min(multisetToModify.count(e), multisetToRetain.count(e))}. This is similar to {@link 703 * #intersection(Multiset, Multiset) intersection} {@code (multisetToModify, multisetToRetain)}, 704 * but mutates {@code multisetToModify} instead of returning a view. 705 * 706 * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps all occurrences of 707 * elements that appear at all in {@code multisetToRetain}, and deletes all occurrences of all 708 * other elements. 709 * 710 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation 711 * @since 10.0 712 */ 713 @CanIgnoreReturnValue 714 public static boolean retainOccurrences( 715 Multiset<?> multisetToModify, Multiset<?> multisetToRetain) { 716 return retainOccurrencesImpl(multisetToModify, multisetToRetain); 717 } 718 719 /** Delegate implementation which cares about the element type. */ 720 private static <E extends @Nullable Object> boolean retainOccurrencesImpl( 721 Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) { 722 checkNotNull(multisetToModify); 723 checkNotNull(occurrencesToRetain); 724 // Avoiding ConcurrentModificationExceptions is tricky. 725 Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator(); 726 boolean changed = false; 727 while (entryIterator.hasNext()) { 728 Entry<E> entry = entryIterator.next(); 729 int retainCount = occurrencesToRetain.count(entry.getElement()); 730 if (retainCount == 0) { 731 entryIterator.remove(); 732 changed = true; 733 } else if (retainCount < entry.getCount()) { 734 multisetToModify.setCount(entry.getElement(), retainCount); 735 changed = true; 736 } 737 } 738 return changed; 739 } 740 741 /** 742 * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one 743 * occurrence of {@code e} in {@code multisetToModify}. 744 * 745 * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code 746 * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) - 747 * Iterables.frequency(occurrencesToRemove, e))}. 748 * 749 * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll 750 * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear 751 * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit 752 * sometimes more efficient than, the following: 753 * 754 * <pre>{@code 755 * for (E e : occurrencesToRemove) { 756 * multisetToModify.remove(e); 757 * } 758 * }</pre> 759 * 760 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation 761 * @since 18.0 (present in 10.0 with a requirement that the second parameter be a {@code 762 * Multiset}) 763 */ 764 @CanIgnoreReturnValue 765 public static boolean removeOccurrences( 766 Multiset<?> multisetToModify, Iterable<?> occurrencesToRemove) { 767 if (occurrencesToRemove instanceof Multiset) { 768 return removeOccurrences(multisetToModify, (Multiset<?>) occurrencesToRemove); 769 } else { 770 checkNotNull(multisetToModify); 771 checkNotNull(occurrencesToRemove); 772 boolean changed = false; 773 for (Object o : occurrencesToRemove) { 774 changed |= multisetToModify.remove(o); 775 } 776 return changed; 777 } 778 } 779 780 /** 781 * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, removes one 782 * occurrence of {@code e} in {@code multisetToModify}. 783 * 784 * <p>Equivalently, this method modifies {@code multisetToModify} so that {@code 785 * multisetToModify.count(e)} is set to {@code Math.max(0, multisetToModify.count(e) - 786 * occurrencesToRemove.count(e))}. 787 * 788 * <p>This is <i>not</i> the same as {@code multisetToModify.} {@link Multiset#removeAll 789 * removeAll}{@code (occurrencesToRemove)}, which removes all occurrences of elements that appear 790 * in {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent to, albeit 791 * sometimes more efficient than, the following: 792 * 793 * <pre>{@code 794 * for (E e : occurrencesToRemove) { 795 * multisetToModify.remove(e); 796 * } 797 * }</pre> 798 * 799 * @return {@code true} if {@code multisetToModify} was changed as a result of this operation 800 * @since 10.0 (missing in 18.0 when only the overload taking an {@code Iterable} was present) 801 */ 802 @CanIgnoreReturnValue 803 public static boolean removeOccurrences( 804 Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) { 805 checkNotNull(multisetToModify); 806 checkNotNull(occurrencesToRemove); 807 808 boolean changed = false; 809 Iterator<? extends Entry<?>> entryIterator = multisetToModify.entrySet().iterator(); 810 while (entryIterator.hasNext()) { 811 Entry<?> entry = entryIterator.next(); 812 int removeCount = occurrencesToRemove.count(entry.getElement()); 813 if (removeCount >= entry.getCount()) { 814 entryIterator.remove(); 815 changed = true; 816 } else if (removeCount > 0) { 817 multisetToModify.remove(entry.getElement(), removeCount); 818 changed = true; 819 } 820 } 821 return changed; 822 } 823 824 /** 825 * Implementation of the {@code equals}, {@code hashCode}, and {@code toString} methods of {@link 826 * Multiset.Entry}. 827 */ 828 abstract static class AbstractEntry<E extends @Nullable Object> implements Multiset.Entry<E> { 829 /** 830 * Indicates whether an object equals this entry, following the behavior specified in {@link 831 * Multiset.Entry#equals}. 832 */ 833 @Override 834 public boolean equals(@Nullable Object object) { 835 if (object instanceof Multiset.Entry) { 836 Multiset.Entry<?> that = (Multiset.Entry<?>) object; 837 return this.getCount() == that.getCount() 838 && Objects.equal(this.getElement(), that.getElement()); 839 } 840 return false; 841 } 842 843 /** 844 * Return this entry's hash code, following the behavior specified in {@link 845 * Multiset.Entry#hashCode}. 846 */ 847 @Override 848 public int hashCode() { 849 E e = getElement(); 850 return ((e == null) ? 0 : e.hashCode()) ^ getCount(); 851 } 852 853 /** 854 * Returns a string representation of this multiset entry. The string representation consists of 855 * the associated element if the associated count is one, and otherwise the associated element 856 * followed by the characters " x " (space, x and space) followed by the count. Elements and 857 * counts are converted to strings as by {@code String.valueOf}. 858 */ 859 @Override 860 public String toString() { 861 String text = String.valueOf(getElement()); 862 int n = getCount(); 863 return (n == 1) ? text : (text + " x " + n); 864 } 865 } 866 867 /** An implementation of {@link Multiset#equals}. */ 868 static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) { 869 if (object == multiset) { 870 return true; 871 } 872 if (object instanceof Multiset) { 873 Multiset<?> that = (Multiset<?>) object; 874 /* 875 * We can't simply check whether the entry sets are equal, since that 876 * approach fails when a TreeMultiset has a comparator that returns 0 877 * when passed unequal elements. 878 */ 879 880 if (multiset.size() != that.size() || multiset.entrySet().size() != that.entrySet().size()) { 881 return false; 882 } 883 for (Entry<?> entry : that.entrySet()) { 884 if (multiset.count(entry.getElement()) != entry.getCount()) { 885 return false; 886 } 887 } 888 return true; 889 } 890 return false; 891 } 892 893 /** An implementation of {@link Multiset#addAll}. */ 894 static <E extends @Nullable Object> boolean addAllImpl( 895 Multiset<E> self, Collection<? extends E> elements) { 896 checkNotNull(self); 897 checkNotNull(elements); 898 if (elements instanceof Multiset) { 899 return addAllImpl(self, (Multiset<? extends E>) elements); 900 } else if (elements.isEmpty()) { 901 return false; 902 } else { 903 return Iterators.addAll(self, elements.iterator()); 904 } 905 } 906 907 /** A specialization of {@code addAllImpl} for when {@code elements} is itself a Multiset. */ 908 private static <E extends @Nullable Object> boolean addAllImpl( 909 Multiset<E> self, Multiset<? extends E> elements) { 910 // It'd be nice if we could specialize for ImmutableMultiset here without also retaining 911 // its code when it's not in scope... 912 if (elements instanceof AbstractMapBasedMultiset) { 913 return addAllImpl(self, (AbstractMapBasedMultiset<? extends E>) elements); 914 } else if (elements.isEmpty()) { 915 return false; 916 } else { 917 for (Multiset.Entry<? extends E> entry : elements.entrySet()) { 918 self.add(entry.getElement(), entry.getCount()); 919 } 920 return true; 921 } 922 } 923 924 /** 925 * A specialization of {@code addAllImpl} for when {@code elements} is an 926 * AbstractMapBasedMultiset. 927 */ 928 private static <E extends @Nullable Object> boolean addAllImpl( 929 Multiset<E> self, AbstractMapBasedMultiset<? extends E> elements) { 930 if (elements.isEmpty()) { 931 return false; 932 } 933 elements.addTo(self); 934 return true; 935 } 936 937 /** An implementation of {@link Multiset#removeAll}. */ 938 static boolean removeAllImpl(Multiset<?> self, Collection<?> elementsToRemove) { 939 Collection<?> collection = 940 (elementsToRemove instanceof Multiset) 941 ? ((Multiset<?>) elementsToRemove).elementSet() 942 : elementsToRemove; 943 944 return self.elementSet().removeAll(collection); 945 } 946 947 /** An implementation of {@link Multiset#retainAll}. */ 948 static boolean retainAllImpl(Multiset<?> self, Collection<?> elementsToRetain) { 949 checkNotNull(elementsToRetain); 950 Collection<?> collection = 951 (elementsToRetain instanceof Multiset) 952 ? ((Multiset<?>) elementsToRetain).elementSet() 953 : elementsToRetain; 954 955 return self.elementSet().retainAll(collection); 956 } 957 958 /** An implementation of {@link Multiset#setCount(Object, int)}. */ 959 static <E extends @Nullable Object> int setCountImpl( 960 Multiset<E> self, @ParametricNullness E element, int count) { 961 checkNonnegative(count, "count"); 962 963 int oldCount = self.count(element); 964 965 int delta = count - oldCount; 966 if (delta > 0) { 967 self.add(element, delta); 968 } else if (delta < 0) { 969 self.remove(element, -delta); 970 } 971 972 return oldCount; 973 } 974 975 /** An implementation of {@link Multiset#setCount(Object, int, int)}. */ 976 static <E extends @Nullable Object> boolean setCountImpl( 977 Multiset<E> self, @ParametricNullness E element, int oldCount, int newCount) { 978 checkNonnegative(oldCount, "oldCount"); 979 checkNonnegative(newCount, "newCount"); 980 981 if (self.count(element) == oldCount) { 982 self.setCount(element, newCount); 983 return true; 984 } else { 985 return false; 986 } 987 } 988 989 static <E extends @Nullable Object> Iterator<E> elementIterator( 990 Iterator<Entry<E>> entryIterator) { 991 return new TransformedIterator<Entry<E>, E>(entryIterator) { 992 @Override 993 @ParametricNullness 994 E transform(Entry<E> entry) { 995 return entry.getElement(); 996 } 997 }; 998 } 999 1000 abstract static class ElementSet<E extends @Nullable Object> extends Sets.ImprovedAbstractSet<E> { 1001 abstract Multiset<E> multiset(); 1002 1003 @Override 1004 public void clear() { 1005 multiset().clear(); 1006 } 1007 1008 @Override 1009 public boolean contains(@Nullable Object o) { 1010 return multiset().contains(o); 1011 } 1012 1013 @Override 1014 public boolean containsAll(Collection<?> c) { 1015 return multiset().containsAll(c); 1016 } 1017 1018 @Override 1019 public boolean isEmpty() { 1020 return multiset().isEmpty(); 1021 } 1022 1023 @Override 1024 public abstract Iterator<E> iterator(); 1025 1026 @Override 1027 public boolean remove(@Nullable Object o) { 1028 return multiset().remove(o, Integer.MAX_VALUE) > 0; 1029 } 1030 1031 @Override 1032 public int size() { 1033 return multiset().entrySet().size(); 1034 } 1035 } 1036 1037 abstract static class EntrySet<E extends @Nullable Object> 1038 extends Sets.ImprovedAbstractSet<Entry<E>> { 1039 abstract Multiset<E> multiset(); 1040 1041 @Override 1042 public boolean contains(@Nullable Object o) { 1043 if (o instanceof Entry) { 1044 Entry<?> entry = (Entry<?>) o; 1045 if (entry.getCount() <= 0) { 1046 return false; 1047 } 1048 int count = multiset().count(entry.getElement()); 1049 return count == entry.getCount(); 1050 } 1051 return false; 1052 } 1053 1054 @Override 1055 public boolean remove(@Nullable Object object) { 1056 if (object instanceof Multiset.Entry) { 1057 Entry<?> entry = (Entry<?>) object; 1058 Object element = entry.getElement(); 1059 int entryCount = entry.getCount(); 1060 if (entryCount != 0) { 1061 // Safe as long as we never add a new entry, which we won't. 1062 // (Presumably it can still throw CCE/NPE but only if the underlying Multiset does.) 1063 @SuppressWarnings({"unchecked", "nullness"}) 1064 Multiset<@Nullable Object> multiset = (Multiset<@Nullable Object>) multiset(); 1065 return multiset.setCount(element, entryCount, 0); 1066 } 1067 } 1068 return false; 1069 } 1070 1071 @Override 1072 public void clear() { 1073 multiset().clear(); 1074 } 1075 } 1076 1077 /** An implementation of {@link Multiset#iterator}. */ 1078 static <E extends @Nullable Object> Iterator<E> iteratorImpl(Multiset<E> multiset) { 1079 return new MultisetIteratorImpl<>(multiset, multiset.entrySet().iterator()); 1080 } 1081 1082 static final class MultisetIteratorImpl<E extends @Nullable Object> implements Iterator<E> { 1083 private final Multiset<E> multiset; 1084 private final Iterator<Entry<E>> entryIterator; 1085 private @Nullable Entry<E> currentEntry; 1086 1087 /** Count of subsequent elements equal to current element */ 1088 private int laterCount; 1089 1090 /** Count of all elements equal to current element */ 1091 private int totalCount; 1092 1093 private boolean canRemove; 1094 1095 MultisetIteratorImpl(Multiset<E> multiset, Iterator<Entry<E>> entryIterator) { 1096 this.multiset = multiset; 1097 this.entryIterator = entryIterator; 1098 } 1099 1100 @Override 1101 public boolean hasNext() { 1102 return laterCount > 0 || entryIterator.hasNext(); 1103 } 1104 1105 @Override 1106 @ParametricNullness 1107 public E next() { 1108 if (!hasNext()) { 1109 throw new NoSuchElementException(); 1110 } 1111 if (laterCount == 0) { 1112 currentEntry = entryIterator.next(); 1113 totalCount = laterCount = currentEntry.getCount(); 1114 } 1115 laterCount--; 1116 canRemove = true; 1117 /* 1118 * requireNonNull is safe because laterCount starts at 0, forcing us to initialize 1119 * currentEntry above. After that, we never clear it. 1120 */ 1121 return requireNonNull(currentEntry).getElement(); 1122 } 1123 1124 @Override 1125 public void remove() { 1126 checkRemove(canRemove); 1127 if (totalCount == 1) { 1128 entryIterator.remove(); 1129 } else { 1130 /* 1131 * requireNonNull is safe because canRemove is set to true only after we initialize 1132 * currentEntry (which we never subsequently clear). 1133 */ 1134 multiset.remove(requireNonNull(currentEntry).getElement()); 1135 } 1136 totalCount--; 1137 canRemove = false; 1138 } 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 /** 1151 * Returns a copy of {@code multiset} as an {@link ImmutableMultiset} whose iteration order puts 1152 * the highest count first, with ties broken by the iteration order of the original multiset. 1153 * 1154 * @since 11.0 1155 */ 1156 public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) { 1157 @SuppressWarnings("unchecked") // generics+arrays 1158 // TODO(cpovirk): Consider storing an Entry<?> instead of Entry<E>. 1159 Entry<E>[] entries = (Entry<E>[]) multiset.entrySet().toArray((Entry<E>[]) new Entry<?>[0]); 1160 Arrays.sort(entries, DecreasingCount.INSTANCE); 1161 return ImmutableMultiset.copyFromEntries(asList(entries)); 1162 } 1163 1164 private static final class DecreasingCount implements Comparator<Entry<?>> { 1165 static final Comparator<Entry<?>> INSTANCE = new DecreasingCount(); 1166 1167 @Override 1168 public int compare(Entry<?> entry1, Entry<?> entry2) { 1169 return entry2.getCount() - entry1.getCount(); // subtracting two nonnegative integers 1170 } 1171 } 1172 1173 /** 1174 * An {@link AbstractMultiset} with additional default implementations, some of them linear-time 1175 * implementations in terms of {@code elementSet} and {@code entrySet}. 1176 */ 1177 private abstract static class ViewMultiset<E extends @Nullable Object> 1178 extends AbstractMultiset<E> { 1179 @Override 1180 public int size() { 1181 return linearTimeSizeImpl(this); 1182 } 1183 1184 @Override 1185 public void clear() { 1186 elementSet().clear(); 1187 } 1188 1189 @Override 1190 public Iterator<E> iterator() { 1191 return iteratorImpl(this); 1192 } 1193 1194 @Override 1195 int distinctElements() { 1196 return elementSet().size(); 1197 } 1198 } 1199}