1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkArgument; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkState; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.collect.Multisets.checkNonnegative; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.InvalidObjectException; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectStreamException; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ConcurrentModificationException; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Basic implementation of {@code Multiset<E>} backed by an instance of {@code 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Map<E, AtomicInteger>}. 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>For serialization to work, the subclass must specify explicit {@code 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * readObject} and {@code writeObject} methods. 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonabstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E> 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Serializable { 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient Map<E, Count> backingMap; 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Cache the size for efficiency. Using a long lets us avoid the need for 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * overflow checking and ensures that size() will function correctly even if 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multiset had once been larger than Integer.MAX_VALUE. 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient long size; 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Standard constructor. */ 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected AbstractMapBasedMultiset(Map<E, Count> backingMap) { 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.backingMap = checkNotNull(backingMap); 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.size = super.size(); 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<E, Count> backingMap() { 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return backingMap; 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Used during deserialization only. The backing map must be empty. */ 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void setBackingMap(Map<E, Count> backingMap) { 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.backingMap = backingMap; 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Required Implementations 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set always returns the current count of that element in the multiset, as 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * opposed to the count at the time the entry was retrieved. 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Set<Multiset.Entry<E>> entrySet() { 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.entrySet(); 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator() { 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> backingEntries = 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.entrySet().iterator(); 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterator<Multiset.Entry<E>>() { 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> toRemove; 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingEntries.hasNext(); 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Multiset.Entry<E> next() { 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Map.Entry<E, Count> mapEntry = backingEntries.next(); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = mapEntry; 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Multisets.AbstractEntry<E>() { 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E getElement() { 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mapEntry.getKey(); 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int getCount() { 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = mapEntry.getValue().get(); 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count == 0) { 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(getElement()); 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (frequency != null) { 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert count = frequency.get(); 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count; 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkState(toRemove != null, 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "no calls to next() since the last call to remove()"); 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size -= toRemove.getValue().getAndSet(0); 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingEntries.remove(); 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = null; 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void clear() { 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Count frequency : backingMap.values()) { 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert frequency.set(0); 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.clear(); 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size = 0L; 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int distinctElements() { 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingMap.size(); 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Optimizations - Query Operations 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.saturatedCast(size); 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new MapBasedMultisetIterator(); 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Not subclassing AbstractMultiset$MultisetIterator because next() needs to 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * retrieve the Map.Entry<E, AtomicInteger> entry, which can then be used for 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a more efficient remove() call. 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class MapBasedMultisetIterator implements Iterator<E> { 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> entryIterator; 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> currentEntry; 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int occurrencesLeft; 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean canRemove; 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson MapBasedMultisetIterator() { 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.entryIterator = backingMap.entrySet().iterator(); 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return occurrencesLeft > 0 || entryIterator.hasNext(); 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E next() { 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrencesLeft == 0) { 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson currentEntry = entryIterator.next(); 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrencesLeft = currentEntry.getValue().get(); 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrencesLeft--; 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson canRemove = true; 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return currentEntry.getKey(); 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(canRemove, 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "no calls to next() since the last call to remove()"); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int frequency = currentEntry.getValue().get(); 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency <= 0) { 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new ConcurrentModificationException(); 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (currentEntry.getValue().addAndGet(-1) == 0) { 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entryIterator.remove(); 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size--; 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson canRemove = false; 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int count(@Nullable Object element) { 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (frequency == null) ? 0 : frequency.get(); 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Optional Operations - Modification Operations 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if the call would result in more than 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Integer#MAX_VALUE} occurrences of {@code element} in this 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset. 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int add(@Nullable E element, int occurrences) { 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrences == 0) { 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count(element); 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument( 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrences > 0, "occurrences cannot be negative: %s", occurrences); 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount; 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = 0; 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.put(element, new Count(occurrences)); 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = frequency.get(); 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson long newCount = (long) oldCount + (long) occurrences; 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(newCount <= Integer.MAX_VALUE, 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "too many occurrences: %s", newCount); 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson frequency.getAndAdd(occurrences); 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size += occurrences; 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int remove(@Nullable Object element, int occurrences) { 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrences == 0) { 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count(element); 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument( 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrences > 0, "occurrences cannot be negative: %s", occurrences); 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount = frequency.get(); 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int numberRemoved; 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (oldCount > occurrences) { 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson numberRemoved = occurrences; 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson numberRemoved = oldCount; 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson backingMap.remove(element); 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson frequency.addAndGet(-numberRemoved); 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= numberRemoved; 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Roughly a 33% performance improvement over AbstractMultiset.setCount(). 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int setCount(E element, int count) { 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNonnegative(count, "count"); 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count existingCounter; 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount; 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (count == 0) { 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson existingCounter = backingMap.remove(element); 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = getAndSet(existingCounter, count); 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson existingCounter = backingMap.get(element); 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = getAndSet(existingCounter, count); 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (existingCounter == null) { 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.put(element, new Count(count)); 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size += (count - oldCount); 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int getAndSet(Count i, int count) { 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (i == null) { 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i.getAndSet(count); 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private int removeAllOccurrences(@Nullable Object element, 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<E, Count> map) { 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = map.remove(element); 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int numberRemoved = frequency.getAndSet(0); 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= numberRemoved; 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return numberRemoved; 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Set<E> createElementSet() { 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new MapBasedElementSet(backingMap); 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): once TreeMultiset is replaced with a SortedMultiset 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // implementation, replace this with a subclass of Multisets.ElementSet. 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson class MapBasedElementSet extends ForwardingSet<E> { 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This mapping is the usually the same as 'backingMap', but can be a 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // submap in some implementations. 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final Map<E, Count> map; 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Set<E> delegate; 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapBasedElementSet(Map<E, Count> map) { 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate = map.keySet(); 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override protected Set<E> delegate() { 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate; 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> entries 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = map.entrySet().iterator(); 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<E>() { 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> toRemove; 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entries.hasNext(); 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E next() { 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson toRemove = entries.next(); 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return toRemove.getKey(); 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(toRemove != null, 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "no calls to next() since the last call to remove()"); 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= toRemove.getValue().getAndSet(0); 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries.remove(); 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson toRemove = null; 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object element) { 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return removeAllOccurrences(element, map) != 0; 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> elementsToRemove) { 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), elementsToRemove); 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> elementsToRetain) { 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), elementsToRetain); 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (map == backingMap) { 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson AbstractMapBasedMultiset.this.clear(); 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<E> i = iterator(); 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (i.hasNext()) { 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.next(); 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.remove(); 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Map<E, Count> getMap() { 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map; 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Don't allow default serialization. 3981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectStreamException") 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unused") // actually used during deserialization 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObjectNoData() throws ObjectStreamException { 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new InvalidObjectException("Stream data required"); 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("not needed in emulated source.") 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = -2250766705698539974L; 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 407