11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 210888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkNonnegative; 220888a09821a98ac0680fad765217302858e70fa4Paul Duffinimport static com.google.common.collect.CollectPreconditions.checkRemove; 237dd252788645e940eada959bdde927426e2531c9Paul Duffin 247dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.Beta; 257dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.annotations.GwtCompatible; 267dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Objects; 277dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Predicate; 287dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.base.Predicates; 297dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.collect.Multiset.Entry; 307dd252788645e940eada959bdde927426e2531c9Paul Duffinimport com.google.common.primitives.Ints; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.io.Serializable; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collection; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Collections; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Iterator; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.List; 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.NoSuchElementException; 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Set; 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Provides static utility methods for creating and working with {@link 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Multiset} instances. 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 467dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 477dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Multisets"> 487dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Multisets}</a>. 497dd252788645e940eada959bdde927426e2531c9Paul Duffin * 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Kevin Bourrillion 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Mike Bostock 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class Multisets { 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Multisets() {} 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an unmodifiable view of the specified multiset. Query operations on 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the returned multiset "read through" to the specified multiset, and 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * attempts to modify the returned multiset result in an 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link UnsupportedOperationException}. 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will be serializable if the specified multiset is 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * serializable. 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param multiset the multiset for which an unmodifiable view is to be 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * generated 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return an unmodifiable view of the multiset 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 720888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Multiset<E> unmodifiableMultiset( 730888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<? extends E> multiset) { 740888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (multiset instanceof UnmodifiableMultiset || 750888a09821a98ac0680fad765217302858e70fa4Paul Duffin multiset instanceof ImmutableMultiset) { 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Since it's unmodifiable, the covariant cast is safe 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset<E> result = (Multiset<E>) multiset; 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new UnmodifiableMultiset<E>(checkNotNull(multiset)); 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Simply returns its argument. 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @deprecated no need to use this 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 10.0 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 900888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Deprecated public static <E> Multiset<E> unmodifiableMultiset( 910888a09821a98ac0680fad765217302858e70fa4Paul Duffin ImmutableMultiset<E> multiset) { 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return checkNotNull(multiset); 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 950888a09821a98ac0680fad765217302858e70fa4Paul Duffin static class UnmodifiableMultiset<E> 960888a09821a98ac0680fad765217302858e70fa4Paul Duffin extends ForwardingMultiset<E> implements Serializable { 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Multiset<? extends E> delegate; 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert UnmodifiableMultiset(Multiset<? extends E> delegate) { 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.delegate = delegate; 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1040888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override protected Multiset<E> delegate() { 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This is safe because all non-covariant methods are overriden 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Multiset<E>) delegate; 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert transient Set<E> elementSet; 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<E> createElementSet() { 1120888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Collections.<E>unmodifiableSet(delegate.elementSet()); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Set<E> elementSet() { 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<E> es = elementSet; 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (es == null) ? elementSet = createElementSet() : es; 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert transient Set<Multiset.Entry<E>> entrySet; 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1240888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Set<Multiset.Entry<E>> entrySet() { 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<Multiset.Entry<E>> es = entrySet; 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (es == null) 1270888a09821a98ac0680fad765217302858e70fa4Paul Duffin // Safe because the returned set is made unmodifiable and Entry 1280888a09821a98ac0680fad765217302858e70fa4Paul Duffin // itself is readonly 1290888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? entrySet = (Set) Collections.unmodifiableSet(delegate.entrySet()) 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : es; 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1340888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<E> iterator() { 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Safe because the returned Iterator is made unmodifiable 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Iterator<E>) Iterators.unmodifiableIterator(delegate.iterator()); 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1390888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean add(E element) { 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1430888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int add(E element, int occurences) { 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1470888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean addAll(Collection<? extends E> elementsToAdd) { 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1510888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean remove(Object element) { 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1550888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int remove(Object element, int occurrences) { 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1590888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean removeAll(Collection<?> elementsToRemove) { 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1630888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean retainAll(Collection<?> elementsToRetain) { 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1710888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int setCount(E element, int count) { 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1750888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean setCount(E element, int oldCount, int newCount) { 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an unmodifiable view of the specified sorted multiset. Query 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * operations on the returned multiset "read through" to the specified 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multiset, and attempts to modify the returned multiset result in an {@link 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * UnsupportedOperationException}. 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned multiset will be serializable if the specified multiset is 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * serializable. 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param sortedMultiset the sorted multiset for which an unmodifiable view is 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to be generated 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return an unmodifiable view of the multiset 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 1970888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> SortedMultiset<E> unmodifiableSortedMultiset( 1980888a09821a98ac0680fad765217302858e70fa4Paul Duffin SortedMultiset<E> sortedMultiset) { 1997dd252788645e940eada959bdde927426e2531c9Paul Duffin // it's in its own file so it can be emulated for GWT 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new UnmodifiableSortedMultiset<E>(checkNotNull(sortedMultiset)); 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable multiset entry with the specified element and count. 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The entry will be serializable if {@code e} is. 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param e the element to be associated with the returned entry 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param n the count to be associated with the returned entry 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code n} is negative 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Multiset.Entry<E> immutableEntry(@Nullable E e, int n) { 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ImmutableEntry<E>(e, n); 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2150888a09821a98ac0680fad765217302858e70fa4Paul Duffin static final class ImmutableEntry<E> extends AbstractEntry<E> implements 2160888a09821a98ac0680fad765217302858e70fa4Paul Duffin Serializable { 2170888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable final E element; 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final int count; 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableEntry(@Nullable E element, int count) { 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.element = element; 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.count = count; 2230888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(count, "count"); 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2260888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2270888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Nullable public E getElement() { 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return element; 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2310888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int getCount() { 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count; 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final long serialVersionUID = 0; 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2407dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns a view of the elements of {@code unfiltered} that satisfy a predicate. The returned 2417dd252788645e940eada959bdde927426e2531c9Paul Duffin * multiset is a live view of {@code unfiltered}; changes to one affect the other. 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2437dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>The resulting multiset's iterators, and those of its {@code entrySet()} and 2447dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code elementSet()}, do not support {@code remove()}. However, all other multiset methods 2457dd252788645e940eada959bdde927426e2531c9Paul Duffin * supported by {@code unfiltered} are supported by the returned multiset. When given an element 2467dd252788645e940eada959bdde927426e2531c9Paul Duffin * that doesn't satisfy the predicate, the multiset's {@code add()} and {@code addAll()} methods 2477dd252788645e940eada959bdde927426e2531c9Paul Duffin * throw an {@link IllegalArgumentException}. When methods such as {@code removeAll()} and 2487dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code clear()} are called on the filtered multiset, only elements that satisfy the filter 2497dd252788645e940eada959bdde927426e2531c9Paul Duffin * will be removed from the underlying multiset. 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2517dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>The returned multiset isn't threadsafe or serializable, even if {@code unfiltered} is. 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2537dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Many of the filtered multiset's methods, such as {@code size()}, iterate across every 2547dd252788645e940eada959bdde927426e2531c9Paul Duffin * element in the underlying multiset and determine which elements satisfy the filter. When a 2557dd252788645e940eada959bdde927426e2531c9Paul Duffin * live view is <i>not</i> needed, it may be faster to copy the returned multiset and use the 2567dd252788645e940eada959bdde927426e2531c9Paul Duffin * copy. 2577dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2587dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, as documented at 2597dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link Predicate#apply}. Do not provide a predicate such as 2607dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals. (See 2617dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@link Iterables#filter(Iterable, Class)} for related functionality.) 2627dd252788645e940eada959bdde927426e2531c9Paul Duffin * 2637dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 14.0 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2657dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 2667dd252788645e940eada959bdde927426e2531c9Paul Duffin public static <E> Multiset<E> filter(Multiset<E> unfiltered, Predicate<? super E> predicate) { 2677dd252788645e940eada959bdde927426e2531c9Paul Duffin if (unfiltered instanceof FilteredMultiset) { 2687dd252788645e940eada959bdde927426e2531c9Paul Duffin // Support clear(), removeAll(), and retainAll() when filtering a filtered 2697dd252788645e940eada959bdde927426e2531c9Paul Duffin // collection. 2707dd252788645e940eada959bdde927426e2531c9Paul Duffin FilteredMultiset<E> filtered = (FilteredMultiset<E>) unfiltered; 2710888a09821a98ac0680fad765217302858e70fa4Paul Duffin Predicate<E> combinedPredicate 2720888a09821a98ac0680fad765217302858e70fa4Paul Duffin = Predicates.<E>and(filtered.predicate, predicate); 2737dd252788645e940eada959bdde927426e2531c9Paul Duffin return new FilteredMultiset<E>(filtered.unfiltered, combinedPredicate); 2747dd252788645e940eada959bdde927426e2531c9Paul Duffin } 2757dd252788645e940eada959bdde927426e2531c9Paul Duffin return new FilteredMultiset<E>(unfiltered, predicate); 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2787dd252788645e940eada959bdde927426e2531c9Paul Duffin private static final class FilteredMultiset<E> extends AbstractMultiset<E> { 2797dd252788645e940eada959bdde927426e2531c9Paul Duffin final Multiset<E> unfiltered; 2807dd252788645e940eada959bdde927426e2531c9Paul Duffin final Predicate<? super E> predicate; 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2827dd252788645e940eada959bdde927426e2531c9Paul Duffin FilteredMultiset(Multiset<E> unfiltered, Predicate<? super E> predicate) { 2837dd252788645e940eada959bdde927426e2531c9Paul Duffin this.unfiltered = checkNotNull(unfiltered); 2847dd252788645e940eada959bdde927426e2531c9Paul Duffin this.predicate = checkNotNull(predicate); 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2877dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 2880888a09821a98ac0680fad765217302858e70fa4Paul Duffin public UnmodifiableIterator<E> iterator() { 2890888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Iterators.filter(unfiltered.iterator(), predicate); 2900888a09821a98ac0680fad765217302858e70fa4Paul Duffin } 2910888a09821a98ac0680fad765217302858e70fa4Paul Duffin 2920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2937dd252788645e940eada959bdde927426e2531c9Paul Duffin Set<E> createElementSet() { 2947dd252788645e940eada959bdde927426e2531c9Paul Duffin return Sets.filter(unfiltered.elementSet(), predicate); 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2987dd252788645e940eada959bdde927426e2531c9Paul Duffin Set<Entry<E>> createEntrySet() { 2997dd252788645e940eada959bdde927426e2531c9Paul Duffin return Sets.filter(unfiltered.entrySet(), new Predicate<Entry<E>>() { 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3017dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean apply(Entry<E> entry) { 3027dd252788645e940eada959bdde927426e2531c9Paul Duffin return predicate.apply(entry.getElement()); 3037dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3047dd252788645e940eada959bdde927426e2531c9Paul Duffin }); 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3087dd252788645e940eada959bdde927426e2531c9Paul Duffin Iterator<Entry<E>> entryIterator() { 3097dd252788645e940eada959bdde927426e2531c9Paul Duffin throw new AssertionError("should never be called"); 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3137dd252788645e940eada959bdde927426e2531c9Paul Duffin int distinctElements() { 3147dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet().size(); 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3187dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(@Nullable Object element) { 3197dd252788645e940eada959bdde927426e2531c9Paul Duffin int count = unfiltered.count(element); 3207dd252788645e940eada959bdde927426e2531c9Paul Duffin if (count > 0) { 3210888a09821a98ac0680fad765217302858e70fa4Paul Duffin @SuppressWarnings("unchecked") // element is equal to an E 3227dd252788645e940eada959bdde927426e2531c9Paul Duffin E e = (E) element; 3237dd252788645e940eada959bdde927426e2531c9Paul Duffin return predicate.apply(e) ? count : 0; 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3257dd252788645e940eada959bdde927426e2531c9Paul Duffin return 0; 326dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin } 327dbd967a6e5c96cc1a97c5521f88dc1564ba2f81bPaul Duffin 3287dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3297dd252788645e940eada959bdde927426e2531c9Paul Duffin public int add(@Nullable E element, int occurrences) { 3300888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkArgument(predicate.apply(element), 3310888a09821a98ac0680fad765217302858e70fa4Paul Duffin "Element %s does not match predicate %s", element, predicate); 3327dd252788645e940eada959bdde927426e2531c9Paul Duffin return unfiltered.add(element, occurrences); 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3367dd252788645e940eada959bdde927426e2531c9Paul Duffin public int remove(@Nullable Object element, int occurrences) { 3370888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkNonnegative(occurrences, "occurrences"); 3387dd252788645e940eada959bdde927426e2531c9Paul Duffin if (occurrences == 0) { 3397dd252788645e940eada959bdde927426e2531c9Paul Duffin return count(element); 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 3417dd252788645e940eada959bdde927426e2531c9Paul Duffin return contains(element) ? unfiltered.remove(element, occurrences) : 0; 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3467dd252788645e940eada959bdde927426e2531c9Paul Duffin public void clear() { 3477dd252788645e940eada959bdde927426e2531c9Paul Duffin elementSet().clear(); 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the expected number of distinct elements given the specified 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements. The number of distinct elements is only computed if {@code 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements} is an instance of {@code Multiset}; otherwise the default value 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of 11 is returned. 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static int inferDistinctElements(Iterable<?> elements) { 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Multiset) { 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((Multiset<?>) elements).elementSet().size(); 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 11; // initial capacity will be rounded up to 16 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3657dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns an unmodifiable view of the union of two multisets. 3667dd252788645e940eada959bdde927426e2531c9Paul Duffin * In the returned multiset, the count of each element is the <i>maximum</i> 3677dd252788645e940eada959bdde927426e2531c9Paul Duffin * of its counts in the two backing multisets. The iteration order of the 3687dd252788645e940eada959bdde927426e2531c9Paul Duffin * returned multiset matches that of the element set of {@code multiset1} 3697dd252788645e940eada959bdde927426e2531c9Paul Duffin * followed by the members of the element set of {@code multiset2} that are 3707dd252788645e940eada959bdde927426e2531c9Paul Duffin * not contained in {@code multiset1}, with repeated occurrences of the same 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * element appearing consecutively. 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Results are undefined if {@code multiset1} and {@code multiset2} are 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * based on different equivalence relations (as {@code HashMultiset} and 3751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code TreeMultiset} are). 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3777dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 14.0 3787dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 3797dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 3800888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Multiset<E> union( 3810888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) { 3827dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset1); 3837dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset2); 3847dd252788645e940eada959bdde927426e2531c9Paul Duffin 3857dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractMultiset<E>() { 3867dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3877dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean contains(@Nullable Object element) { 3887dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.contains(element) || multiset2.contains(element); 3897dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3907dd252788645e940eada959bdde927426e2531c9Paul Duffin 3917dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3927dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean isEmpty() { 3937dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.isEmpty() && multiset2.isEmpty(); 3947dd252788645e940eada959bdde927426e2531c9Paul Duffin } 3957dd252788645e940eada959bdde927426e2531c9Paul Duffin 3967dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 3977dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(Object element) { 3987dd252788645e940eada959bdde927426e2531c9Paul Duffin return Math.max(multiset1.count(element), multiset2.count(element)); 3997dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4007dd252788645e940eada959bdde927426e2531c9Paul Duffin 4017dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4027dd252788645e940eada959bdde927426e2531c9Paul Duffin Set<E> createElementSet() { 4037dd252788645e940eada959bdde927426e2531c9Paul Duffin return Sets.union(multiset1.elementSet(), multiset2.elementSet()); 4047dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4057dd252788645e940eada959bdde927426e2531c9Paul Duffin 4067dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4077dd252788645e940eada959bdde927426e2531c9Paul Duffin Iterator<Entry<E>> entryIterator() { 4080888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<? extends Entry<? extends E>> iterator1 4090888a09821a98ac0680fad765217302858e70fa4Paul Duffin = multiset1.entrySet().iterator(); 4100888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<? extends Entry<? extends E>> iterator2 4110888a09821a98ac0680fad765217302858e70fa4Paul Duffin = multiset2.entrySet().iterator(); 4120888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): consider making the entries live views 4137dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractIterator<Entry<E>>() { 4147dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4157dd252788645e940eada959bdde927426e2531c9Paul Duffin protected Entry<E> computeNext() { 4167dd252788645e940eada959bdde927426e2531c9Paul Duffin if (iterator1.hasNext()) { 4177dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<? extends E> entry1 = iterator1.next(); 4187dd252788645e940eada959bdde927426e2531c9Paul Duffin E element = entry1.getElement(); 4197dd252788645e940eada959bdde927426e2531c9Paul Duffin int count = Math.max(entry1.getCount(), multiset2.count(element)); 4207dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, count); 4217dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4227dd252788645e940eada959bdde927426e2531c9Paul Duffin while (iterator2.hasNext()) { 4237dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<? extends E> entry2 = iterator2.next(); 4247dd252788645e940eada959bdde927426e2531c9Paul Duffin E element = entry2.getElement(); 4257dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!multiset1.contains(element)) { 4267dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, entry2.getCount()); 4277dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4287dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4297dd252788645e940eada959bdde927426e2531c9Paul Duffin return endOfData(); 4307dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4317dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 4327dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4337dd252788645e940eada959bdde927426e2531c9Paul Duffin 4347dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 4357dd252788645e940eada959bdde927426e2531c9Paul Duffin int distinctElements() { 4367dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet().size(); 4377dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4387dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 4397dd252788645e940eada959bdde927426e2531c9Paul Duffin } 4407dd252788645e940eada959bdde927426e2531c9Paul Duffin 4417dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 4427dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns an unmodifiable view of the intersection of two multisets. 4437dd252788645e940eada959bdde927426e2531c9Paul Duffin * In the returned multiset, the count of each element is the <i>minimum</i> 4447dd252788645e940eada959bdde927426e2531c9Paul Duffin * of its counts in the two backing multisets, with elements that would have 4457dd252788645e940eada959bdde927426e2531c9Paul Duffin * a count of 0 not included. The iteration order of the returned multiset 4467dd252788645e940eada959bdde927426e2531c9Paul Duffin * matches that of the element set of {@code multiset1}, with repeated 4477dd252788645e940eada959bdde927426e2531c9Paul Duffin * occurrences of the same element appearing consecutively. 4487dd252788645e940eada959bdde927426e2531c9Paul Duffin * 4497dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Results are undefined if {@code multiset1} and {@code multiset2} are 4507dd252788645e940eada959bdde927426e2531c9Paul Duffin * based on different equivalence relations (as {@code HashMultiset} and 4517dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code TreeMultiset} are). 4527dd252788645e940eada959bdde927426e2531c9Paul Duffin * 4531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 4541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 4550888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Multiset<E> intersection( 4560888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Multiset<E> multiset1, final Multiset<?> multiset2) { 4571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(multiset1); 4581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(multiset2); 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractMultiset<E>() { 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int count(Object element) { 4631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count1 = multiset1.count(element); 4641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (count1 == 0) ? 0 : Math.min(count1, multiset2.count(element)); 4651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<E> createElementSet() { 4690888a09821a98ac0680fad765217302858e70fa4Paul Duffin return Sets.intersection( 4700888a09821a98ac0680fad765217302858e70fa4Paul Duffin multiset1.elementSet(), multiset2.elementSet()); 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator() { 4751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator(); 4760888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): consider making the entries live views 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractIterator<Entry<E>>() { 4781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected Entry<E> computeNext() { 4801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (iterator1.hasNext()) { 4811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> entry1 = iterator1.next(); 4821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E element = entry1.getElement(); 4831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = Math.min(entry1.getCount(), multiset2.count(element)); 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count > 0) { 4857dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, count); 4861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return endOfData(); 4891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 4931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 4941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int distinctElements() { 4951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return elementSet().size(); 4961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 4981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 5001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 5017dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns an unmodifiable view of the sum of two multisets. 5027dd252788645e940eada959bdde927426e2531c9Paul Duffin * In the returned multiset, the count of each element is the <i>sum</i> of 5037dd252788645e940eada959bdde927426e2531c9Paul Duffin * its counts in the two backing multisets. The iteration order of the 5047dd252788645e940eada959bdde927426e2531c9Paul Duffin * returned multiset matches that of the element set of {@code multiset1} 5050888a09821a98ac0680fad765217302858e70fa4Paul Duffin * followed by the members of the element set of {@code multiset2} that 5067dd252788645e940eada959bdde927426e2531c9Paul Duffin * are not contained in {@code multiset1}, with repeated occurrences of the 5077dd252788645e940eada959bdde927426e2531c9Paul Duffin * same element appearing consecutively. 5087dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5097dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Results are undefined if {@code multiset1} and {@code multiset2} are 5107dd252788645e940eada959bdde927426e2531c9Paul Duffin * based on different equivalence relations (as {@code HashMultiset} and 5117dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code TreeMultiset} are). 5127dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5137dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 14.0 5147dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 5157dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 5160888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Multiset<E> sum( 5170888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Multiset<? extends E> multiset1, final Multiset<? extends E> multiset2) { 5187dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset1); 5197dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset2); 5207dd252788645e940eada959bdde927426e2531c9Paul Duffin 5210888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): consider making the entries live views 5227dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractMultiset<E>() { 5237dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5247dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean contains(@Nullable Object element) { 5257dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.contains(element) || multiset2.contains(element); 5267dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5277dd252788645e940eada959bdde927426e2531c9Paul Duffin 5287dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5297dd252788645e940eada959bdde927426e2531c9Paul Duffin public boolean isEmpty() { 5307dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.isEmpty() && multiset2.isEmpty(); 5317dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5327dd252788645e940eada959bdde927426e2531c9Paul Duffin 5337dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5347dd252788645e940eada959bdde927426e2531c9Paul Duffin public int size() { 5357dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.size() + multiset2.size(); 5367dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5377dd252788645e940eada959bdde927426e2531c9Paul Duffin 5387dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5397dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(Object element) { 5407dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset1.count(element) + multiset2.count(element); 5417dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5427dd252788645e940eada959bdde927426e2531c9Paul Duffin 5437dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5447dd252788645e940eada959bdde927426e2531c9Paul Duffin Set<E> createElementSet() { 5457dd252788645e940eada959bdde927426e2531c9Paul Duffin return Sets.union(multiset1.elementSet(), multiset2.elementSet()); 5467dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5477dd252788645e940eada959bdde927426e2531c9Paul Duffin 5487dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5497dd252788645e940eada959bdde927426e2531c9Paul Duffin Iterator<Entry<E>> entryIterator() { 5500888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<? extends Entry<? extends E>> iterator1 5510888a09821a98ac0680fad765217302858e70fa4Paul Duffin = multiset1.entrySet().iterator(); 5520888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Iterator<? extends Entry<? extends E>> iterator2 5530888a09821a98ac0680fad765217302858e70fa4Paul Duffin = multiset2.entrySet().iterator(); 5547dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractIterator<Entry<E>>() { 5557dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5567dd252788645e940eada959bdde927426e2531c9Paul Duffin protected Entry<E> computeNext() { 5577dd252788645e940eada959bdde927426e2531c9Paul Duffin if (iterator1.hasNext()) { 5587dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<? extends E> entry1 = iterator1.next(); 5597dd252788645e940eada959bdde927426e2531c9Paul Duffin E element = entry1.getElement(); 5607dd252788645e940eada959bdde927426e2531c9Paul Duffin int count = entry1.getCount() + multiset2.count(element); 5617dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, count); 5627dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5637dd252788645e940eada959bdde927426e2531c9Paul Duffin while (iterator2.hasNext()) { 5647dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<? extends E> entry2 = iterator2.next(); 5657dd252788645e940eada959bdde927426e2531c9Paul Duffin E element = entry2.getElement(); 5667dd252788645e940eada959bdde927426e2531c9Paul Duffin if (!multiset1.contains(element)) { 5677dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, entry2.getCount()); 5687dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5697dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5707dd252788645e940eada959bdde927426e2531c9Paul Duffin return endOfData(); 5717dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5727dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 5737dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5747dd252788645e940eada959bdde927426e2531c9Paul Duffin 5757dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 5767dd252788645e940eada959bdde927426e2531c9Paul Duffin int distinctElements() { 5777dd252788645e940eada959bdde927426e2531c9Paul Duffin return elementSet().size(); 5787dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5797dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 5807dd252788645e940eada959bdde927426e2531c9Paul Duffin } 5817dd252788645e940eada959bdde927426e2531c9Paul Duffin 5827dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 5837dd252788645e940eada959bdde927426e2531c9Paul Duffin * Returns an unmodifiable view of the difference of two multisets. 5847dd252788645e940eada959bdde927426e2531c9Paul Duffin * In the returned multiset, the count of each element is the result of the 5857dd252788645e940eada959bdde927426e2531c9Paul Duffin * <i>zero-truncated subtraction</i> of its count in the second multiset from 5867dd252788645e940eada959bdde927426e2531c9Paul Duffin * its count in the first multiset, with elements that would have a count of 5877dd252788645e940eada959bdde927426e2531c9Paul Duffin * 0 not included. The iteration order of the returned multiset matches that 5887dd252788645e940eada959bdde927426e2531c9Paul Duffin * of the element set of {@code multiset1}, with repeated occurrences of the 5897dd252788645e940eada959bdde927426e2531c9Paul Duffin * same element appearing consecutively. 5907dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5917dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Results are undefined if {@code multiset1} and {@code multiset2} are 5927dd252788645e940eada959bdde927426e2531c9Paul Duffin * based on different equivalence relations (as {@code HashMultiset} and 5937dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code TreeMultiset} are). 5947dd252788645e940eada959bdde927426e2531c9Paul Duffin * 5957dd252788645e940eada959bdde927426e2531c9Paul Duffin * @since 14.0 5967dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 5977dd252788645e940eada959bdde927426e2531c9Paul Duffin @Beta 5980888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static <E> Multiset<E> difference( 5990888a09821a98ac0680fad765217302858e70fa4Paul Duffin final Multiset<E> multiset1, final Multiset<?> multiset2) { 6007dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset1); 6017dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(multiset2); 6027dd252788645e940eada959bdde927426e2531c9Paul Duffin 6030888a09821a98ac0680fad765217302858e70fa4Paul Duffin // TODO(user): consider making the entries live views 6047dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractMultiset<E>() { 6057dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6067dd252788645e940eada959bdde927426e2531c9Paul Duffin public int count(@Nullable Object element) { 6077dd252788645e940eada959bdde927426e2531c9Paul Duffin int count1 = multiset1.count(element); 6080888a09821a98ac0680fad765217302858e70fa4Paul Duffin return (count1 == 0) ? 0 : 6090888a09821a98ac0680fad765217302858e70fa4Paul Duffin Math.max(0, count1 - multiset2.count(element)); 6107dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6117dd252788645e940eada959bdde927426e2531c9Paul Duffin 6127dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6137dd252788645e940eada959bdde927426e2531c9Paul Duffin Iterator<Entry<E>> entryIterator() { 6147dd252788645e940eada959bdde927426e2531c9Paul Duffin final Iterator<Entry<E>> iterator1 = multiset1.entrySet().iterator(); 6157dd252788645e940eada959bdde927426e2531c9Paul Duffin return new AbstractIterator<Entry<E>>() { 6167dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6177dd252788645e940eada959bdde927426e2531c9Paul Duffin protected Entry<E> computeNext() { 6187dd252788645e940eada959bdde927426e2531c9Paul Duffin while (iterator1.hasNext()) { 6197dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<E> entry1 = iterator1.next(); 6207dd252788645e940eada959bdde927426e2531c9Paul Duffin E element = entry1.getElement(); 6217dd252788645e940eada959bdde927426e2531c9Paul Duffin int count = entry1.getCount() - multiset2.count(element); 6227dd252788645e940eada959bdde927426e2531c9Paul Duffin if (count > 0) { 6237dd252788645e940eada959bdde927426e2531c9Paul Duffin return immutableEntry(element, count); 6247dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6257dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6267dd252788645e940eada959bdde927426e2531c9Paul Duffin return endOfData(); 6277dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6287dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 6297dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6307dd252788645e940eada959bdde927426e2531c9Paul Duffin 6317dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 6327dd252788645e940eada959bdde927426e2531c9Paul Duffin int distinctElements() { 6337dd252788645e940eada959bdde927426e2531c9Paul Duffin return Iterators.size(entryIterator()); 6347dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6357dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 6367dd252788645e940eada959bdde927426e2531c9Paul Duffin } 6377dd252788645e940eada959bdde927426e2531c9Paul Duffin 6387dd252788645e940eada959bdde927426e2531c9Paul Duffin /** 6391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns {@code true} if {@code subMultiset.count(o) <= 6401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * superMultiset.count(o)} for all {@code o}. 6411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 10.0 6431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6440888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean containsOccurrences( 6450888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> superMultiset, Multiset<?> subMultiset) { 6461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(superMultiset); 6471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(subMultiset); 6481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Entry<?> entry : subMultiset.entrySet()) { 6491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int superCount = superMultiset.count(entry.getElement()); 6501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (superCount < entry.getCount()) { 6511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 6521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 6551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 6581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Modifies {@code multisetToModify} so that its count for an element 6591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code e} is at most {@code multisetToRetain.count(e)}. 6601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>To be precise, {@code multisetToModify.count(e)} is set to 6621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Math.min(multisetToModify.count(e), 6631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multisetToRetain.count(e))}. This is similar to 6641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link #intersection(Multiset, Multiset) intersection} 6651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code (multisetToModify, multisetToRetain)}, but mutates 6661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code multisetToModify} instead of returning a view. 6671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>In contrast, {@code multisetToModify.retainAll(multisetToRetain)} keeps 6691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * all occurrences of elements that appear at all in {@code 6701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multisetToRetain}, and deletes all occurrences of all other elements. 6711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 6721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code true} if {@code multisetToModify} was changed as a result 6731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of this operation 6741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 10.0 6751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6760888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean retainOccurrences(Multiset<?> multisetToModify, 6770888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> multisetToRetain) { 6781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return retainOccurrencesImpl(multisetToModify, multisetToRetain); 6791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 6801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 6811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 6821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Delegate implementation which cares about the element type. 6831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 6840888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <E> boolean retainOccurrencesImpl( 6850888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<E> multisetToModify, Multiset<?> occurrencesToRetain) { 6861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(multisetToModify); 6871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(occurrencesToRetain); 6881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Avoiding ConcurrentModificationExceptions is tricky. 6891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator(); 6901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean changed = false; 6911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (entryIterator.hasNext()) { 6921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> entry = entryIterator.next(); 6931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int retainCount = occurrencesToRetain.count(entry.getElement()); 6941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (retainCount == 0) { 6951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entryIterator.remove(); 6961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert changed = true; 6971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (retainCount < entry.getCount()) { 6981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multisetToModify.setCount(entry.getElement(), retainCount); 6991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert changed = true; 7001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return changed; 7031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * For each occurrence of an element {@code e} in {@code occurrencesToRemove}, 7071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * removes one occurrence of {@code e} in {@code multisetToModify}. 7081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Equivalently, this method modifies {@code multisetToModify} so that 7101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code multisetToModify.count(e)} is set to 7111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Math.max(0, multisetToModify.count(e) - 7121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * occurrencesToRemove.count(e))}. 7131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This is <i>not</i> the same as {@code multisetToModify.} 7151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Multiset#removeAll removeAll}{@code (occurrencesToRemove)}, which 7161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * removes all occurrences of elements that appear in 7171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code occurrencesToRemove}. However, this operation <i>is</i> equivalent 7181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to, albeit more efficient than, the following: <pre> {@code 7191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * for (E e : occurrencesToRemove) { 7211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * multisetToModify.remove(e); 7221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * }}</pre> 7231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return {@code true} if {@code multisetToModify} was changed as a result of 7251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this operation 7261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 10.0 7271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7280888a09821a98ac0680fad765217302858e70fa4Paul Duffin public static boolean removeOccurrences( 7290888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> multisetToModify, Multiset<?> occurrencesToRemove) { 7301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return removeOccurrencesImpl(multisetToModify, occurrencesToRemove); 7311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Delegate that cares about the element types in occurrencesToRemove. 7351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7360888a09821a98ac0680fad765217302858e70fa4Paul Duffin private static <E> boolean removeOccurrencesImpl( 7370888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<E> multisetToModify, Multiset<?> occurrencesToRemove) { 7381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): generalize to removing an Iterable, perhaps 7391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(multisetToModify); 7401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(occurrencesToRemove); 7411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean changed = false; 7431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator = multisetToModify.entrySet().iterator(); 7441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (entryIterator.hasNext()) { 7451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<E> entry = entryIterator.next(); 7461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int removeCount = occurrencesToRemove.count(entry.getElement()); 7471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (removeCount >= entry.getCount()) { 7481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entryIterator.remove(); 7491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert changed = true; 7501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (removeCount > 0) { 7511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multisetToModify.remove(entry.getElement(), removeCount); 7521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert changed = true; 7531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return changed; 7561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Implementation of the {@code equals}, {@code hashCode}, and 7601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code toString} methods of {@link Multiset.Entry}. 7611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract static class AbstractEntry<E> implements Multiset.Entry<E> { 7631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Indicates whether an object equals this entry, following the behavior 7651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * specified in {@link Multiset.Entry#equals}. 7661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean equals(@Nullable Object object) { 7681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object instanceof Multiset.Entry) { 7691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset.Entry<?> that = (Multiset.Entry<?>) object; 7701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return this.getCount() == that.getCount() 7711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert && Objects.equal(this.getElement(), that.getElement()); 7721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 7741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Return this entry's hash code, following the behavior specified in 7781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link Multiset.Entry#hashCode}. 7791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7800888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int hashCode() { 7811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E e = getElement(); 7821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((e == null) ? 0 : e.hashCode()) ^ getCount(); 7831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a string representation of this multiset entry. The string 7871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * representation consists of the associated element if the associated count 7881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is one, and otherwise the associated element followed by the characters 7891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * " x " (space, x and space) followed by the count. Elements and counts are 7901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * converted to strings as by {@code String.valueOf}. 7911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public String toString() { 7931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert String text = String.valueOf(getElement()); 7941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int n = getCount(); 7951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (n == 1) ? text : (text + " x " + n); 7961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#equals}. 8011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean equalsImpl(Multiset<?> multiset, @Nullable Object object) { 8031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object == multiset) { 8041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 8051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object instanceof Multiset) { 8071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset<?> that = (Multiset<?>) object; 8081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 8091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * We can't simply check whether the entry sets are equal, since that 8101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * approach fails when a TreeMultiset has a comparator that returns 0 8111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * when passed unequal elements. 8121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8140888a09821a98ac0680fad765217302858e70fa4Paul Duffin if (multiset.size() != that.size() 8150888a09821a98ac0680fad765217302858e70fa4Paul Duffin || multiset.entrySet().size() != that.entrySet().size()) { 8161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 8171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Entry<?> entry : that.entrySet()) { 8191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (multiset.count(entry.getElement()) != entry.getCount()) { 8201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 8211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 8241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 8261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#addAll}. 8301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8310888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> boolean addAllImpl( 8320888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<E> self, Collection<? extends E> elements) { 8331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements.isEmpty()) { 8341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 8351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof Multiset) { 8371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Multiset<? extends E> that = cast(elements); 8381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Entry<? extends E> entry : that.entrySet()) { 8391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert self.add(entry.getElement(), entry.getCount()); 8401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 8421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterators.addAll(self, elements.iterator()); 8431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 8451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#removeAll}. 8491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8500888a09821a98ac0680fad765217302858e70fa4Paul Duffin static boolean removeAllImpl( 8510888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> self, Collection<?> elementsToRemove) { 8520888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<?> collection = (elementsToRemove instanceof Multiset) 8530888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? ((Multiset<?>) elementsToRemove).elementSet() : elementsToRemove; 8541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return self.elementSet().removeAll(collection); 8561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#retainAll}. 8601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8610888a09821a98ac0680fad765217302858e70fa4Paul Duffin static boolean retainAllImpl( 8620888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<?> self, Collection<?> elementsToRetain) { 8637dd252788645e940eada959bdde927426e2531c9Paul Duffin checkNotNull(elementsToRetain); 8640888a09821a98ac0680fad765217302858e70fa4Paul Duffin Collection<?> collection = (elementsToRetain instanceof Multiset) 8650888a09821a98ac0680fad765217302858e70fa4Paul Duffin ? ((Multiset<?>) elementsToRetain).elementSet() : elementsToRetain; 8661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return self.elementSet().retainAll(collection); 8681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#setCount(Object, int)}. 8721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <E> int setCountImpl(Multiset<E> self, E element, int count) { 8741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(count, "count"); 8751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int oldCount = self.count(element); 8771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int delta = count - oldCount; 8791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (delta > 0) { 8801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert self.add(element, delta); 8811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (delta < 0) { 8821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert self.remove(element, -delta); 8831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldCount; 8861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 8891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#setCount(Object, int, int)}. 8901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8910888a09821a98ac0680fad765217302858e70fa4Paul Duffin static <E> boolean setCountImpl( 8920888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<E> self, E element, int oldCount, int newCount) { 8931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(oldCount, "oldCount"); 8941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNonnegative(newCount, "newCount"); 8951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (self.count(element) == oldCount) { 8971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert self.setCount(element, newCount); 8981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 8991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 9001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 9011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9047dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract static class ElementSet<E> extends Sets.ImprovedAbstractSet<E> { 9051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract Multiset<E> multiset(); 9061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9070888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 9081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multiset().clear(); 9091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9110888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(Object o) { 9121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset().contains(o); 9131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9150888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean containsAll(Collection<?> c) { 9161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset().containsAll(c); 9171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9190888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean isEmpty() { 9201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset().isEmpty(); 9211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9230888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public Iterator<E> iterator() { 9247dd252788645e940eada959bdde927426e2531c9Paul Duffin return new TransformedIterator<Entry<E>, E>(multiset().entrySet().iterator()) { 9257dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override 9267dd252788645e940eada959bdde927426e2531c9Paul Duffin E transform(Entry<E> entry) { 9277dd252788645e940eada959bdde927426e2531c9Paul Duffin return entry.getElement(); 9287dd252788645e940eada959bdde927426e2531c9Paul Duffin } 9297dd252788645e940eada959bdde927426e2531c9Paul Duffin }; 9301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean remove(Object o) { 9341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = multiset().count(o); 9351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count > 0) { 9361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multiset().remove(o, count); 9371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 9381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 9401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9420888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public int size() { 9431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset().entrySet().size(); 9441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9477dd252788645e940eada959bdde927426e2531c9Paul Duffin abstract static class EntrySet<E> extends Sets.ImprovedAbstractSet<Entry<E>> { 9481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract Multiset<E> multiset(); 9491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9500888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public boolean contains(@Nullable Object o) { 9511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (o instanceof Entry) { 9527dd252788645e940eada959bdde927426e2531c9Paul Duffin /* 9537dd252788645e940eada959bdde927426e2531c9Paul Duffin * The GWT compiler wrongly issues a warning here. 9547dd252788645e940eada959bdde927426e2531c9Paul Duffin */ 9551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("cast") 9561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Entry<?> entry = (Entry<?>) o; 9571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (entry.getCount() <= 0) { 9581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 9591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = multiset().count(entry.getElement()); 9611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count == entry.getCount(); 9621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 9651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9677dd252788645e940eada959bdde927426e2531c9Paul Duffin // GWT compiler warning; see contains(). 9681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("cast") 9697dd252788645e940eada959bdde927426e2531c9Paul Duffin @Override public boolean remove(Object object) { 9707dd252788645e940eada959bdde927426e2531c9Paul Duffin if (object instanceof Multiset.Entry) { 9717dd252788645e940eada959bdde927426e2531c9Paul Duffin Entry<?> entry = (Entry<?>) object; 9727dd252788645e940eada959bdde927426e2531c9Paul Duffin Object element = entry.getElement(); 9737dd252788645e940eada959bdde927426e2531c9Paul Duffin int entryCount = entry.getCount(); 9747dd252788645e940eada959bdde927426e2531c9Paul Duffin if (entryCount != 0) { 9757dd252788645e940eada959bdde927426e2531c9Paul Duffin // Safe as long as we never add a new entry, which we won't. 9767dd252788645e940eada959bdde927426e2531c9Paul Duffin @SuppressWarnings("unchecked") 9777dd252788645e940eada959bdde927426e2531c9Paul Duffin Multiset<Object> multiset = (Multiset) multiset(); 9787dd252788645e940eada959bdde927426e2531c9Paul Duffin return multiset.setCount(element, entryCount, 0); 9797dd252788645e940eada959bdde927426e2531c9Paul Duffin } 9807dd252788645e940eada959bdde927426e2531c9Paul Duffin } 9817dd252788645e940eada959bdde927426e2531c9Paul Duffin return false; 9821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9840888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override public void clear() { 9851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multiset().clear(); 9861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 9901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#iterator}. 9911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 9921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <E> Iterator<E> iteratorImpl(Multiset<E> multiset) { 9930888a09821a98ac0680fad765217302858e70fa4Paul Duffin return new MultisetIteratorImpl<E>( 9940888a09821a98ac0680fad765217302858e70fa4Paul Duffin multiset, multiset.entrySet().iterator()); 9951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final class MultisetIteratorImpl<E> implements Iterator<E> { 9981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final Multiset<E> multiset; 9991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final Iterator<Entry<E>> entryIterator; 10001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private Entry<E> currentEntry; 10011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** Count of subsequent elements equal to current element */ 10021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int laterCount; 10031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** Count of all elements equal to current element */ 10041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private int totalCount; 10051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private boolean canRemove; 10061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10070888a09821a98ac0680fad765217302858e70fa4Paul Duffin MultisetIteratorImpl( 10080888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multiset<E> multiset, Iterator<Entry<E>> entryIterator) { 10091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.multiset = multiset; 10101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.entryIterator = entryIterator; 10111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10130888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 10151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return laterCount > 0 || entryIterator.hasNext(); 10161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10180888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E next() { 10201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!hasNext()) { 10211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new NoSuchElementException(); 10221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (laterCount == 0) { 10241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert currentEntry = entryIterator.next(); 10251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert totalCount = laterCount = currentEntry.getCount(); 10261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert laterCount--; 10281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert canRemove = true; 10291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return currentEntry.getElement(); 10301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10320888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 10331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 10340888a09821a98ac0680fad765217302858e70fa4Paul Duffin checkRemove(canRemove); 10351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (totalCount == 1) { 10361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entryIterator.remove(); 10371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 10381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert multiset.remove(currentEntry.getElement()); 10391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert totalCount--; 10411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert canRemove = false; 10421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 10461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation of {@link Multiset#size}. 10471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 10481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static int sizeImpl(Multiset<?> multiset) { 10491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert long size = 0; 10501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Entry<?> entry : multiset.entrySet()) { 10511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size += entry.getCount(); 10521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.saturatedCast(size); 10541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 10571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Used to avoid http://bugs.sun.com/view_bug.do?bug_id=6558557 10581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 10591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <T> Multiset<T> cast(Iterable<T> iterable) { 10601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Multiset<T>) iterable; 10611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final Ordering<Entry<?>> DECREASING_COUNT_ORDERING = new Ordering<Entry<?>>() { 10641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 10651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int compare(Entry<?> entry1, Entry<?> entry2) { 10661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.compare(entry2.getCount(), entry1.getCount()); 10671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 10691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 10711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a copy of {@code multiset} as an {@link ImmutableMultiset} whose iteration order is 10721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * highest count first, with ties broken by the iteration order of the original multiset. 10731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 10741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 10751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 10761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 10771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableMultiset<E> copyHighestCountFirst(Multiset<E> multiset) { 10780888a09821a98ac0680fad765217302858e70fa4Paul Duffin List<Entry<E>> sortedEntries = 10790888a09821a98ac0680fad765217302858e70fa4Paul Duffin Multisets.DECREASING_COUNT_ORDERING.immutableSortedCopy(multiset.entrySet()); 10801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ImmutableMultiset.copyFromEntries(sortedEntries); 10811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 1083