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.primitives.Ints; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ConcurrentModificationException; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Basic implementation of {@code Multiset<E>} backed by an instance of {@code 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Map<E, AtomicInteger>}. 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>For serialization to work, the subclass must specify explicit {@code 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * readObject} and {@code writeObject} methods. 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonabstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E> 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Serializable { 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient Map<E, Count> backingMap; 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Cache the size for efficiency. Using a long lets us avoid the need for 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * overflow checking and ensures that size() will function correctly even if 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multiset had once been larger than Integer.MAX_VALUE. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient long size; 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Standard constructor. */ 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert protected AbstractMapBasedMultiset(Map<E, Count> backingMap) { 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.backingMap = checkNotNull(backingMap); 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.size = super.size(); 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<E, Count> backingMap() { 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return backingMap; 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Used during deserialization only. The backing map must be empty. */ 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void setBackingMap(Map<E, Count> backingMap) { 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.backingMap = backingMap; 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Required Implementations 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set always returns the current count of that element in the multiset, as 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * opposed to the count at the time the entry was retrieved. 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Set<Multiset.Entry<E>> entrySet() { 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.entrySet(); 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterator<Entry<E>> entryIterator() { 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> backingEntries = 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.entrySet().iterator(); 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Iterator<Multiset.Entry<E>>() { 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> toRemove; 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasNext() { 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingEntries.hasNext(); 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Multiset.Entry<E> next() { 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Map.Entry<E, Count> mapEntry = backingEntries.next(); 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = mapEntry; 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Multisets.AbstractEntry<E>() { 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E getElement() { 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return mapEntry.getKey(); 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int getCount() { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int count = mapEntry.getValue().get(); 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (count == 0) { 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(getElement()); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (frequency != null) { 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert count = frequency.get(); 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return count; 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void remove() { 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkState(toRemove != null, 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "no calls to next() since the last call to remove()"); 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size -= toRemove.getValue().getAndSet(0); 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingEntries.remove(); 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert toRemove = null; 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void clear() { 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Count frequency : backingMap.values()) { 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert frequency.set(0); 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.clear(); 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size = 0L; 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int distinctElements() { 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return backingMap.size(); 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Optimizations - Query Operations 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Ints.saturatedCast(size); 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new MapBasedMultisetIterator(); 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Not subclassing AbstractMultiset$MultisetIterator because next() needs to 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * retrieve the Map.Entry<E, AtomicInteger> entry, which can then be used for 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a more efficient remove() call. 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class MapBasedMultisetIterator implements Iterator<E> { 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> entryIterator; 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> currentEntry; 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int occurrencesLeft; 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean canRemove; 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson MapBasedMultisetIterator() { 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.entryIterator = backingMap.entrySet().iterator(); 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return occurrencesLeft > 0 || entryIterator.hasNext(); 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E next() { 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrencesLeft == 0) { 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson currentEntry = entryIterator.next(); 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrencesLeft = currentEntry.getValue().get(); 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrencesLeft--; 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson canRemove = true; 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return currentEntry.getKey(); 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(canRemove, 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "no calls to next() since the last call to remove()"); 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int frequency = currentEntry.getValue().get(); 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency <= 0) { 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new ConcurrentModificationException(); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (currentEntry.getValue().addAndGet(-1) == 0) { 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entryIterator.remove(); 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size--; 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson canRemove = false; 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int count(@Nullable Object element) { 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (frequency == null) ? 0 : frequency.get(); 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException e) { 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException e) { 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return 0; 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Optional Operations - Modification Operations 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if the call would result in more than 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Integer#MAX_VALUE} occurrences of {@code element} in this 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset. 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int add(@Nullable E element, int occurrences) { 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrences == 0) { 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count(element); 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument( 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrences > 0, "occurrences cannot be negative: %s", occurrences); 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount; 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = 0; 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.put(element, new Count(occurrences)); 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = frequency.get(); 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson long newCount = (long) oldCount + (long) occurrences; 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(newCount <= Integer.MAX_VALUE, 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "too many occurrences: %s", newCount); 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson frequency.getAndAdd(occurrences); 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size += occurrences; 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int remove(@Nullable Object element, int occurrences) { 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (occurrences == 0) { 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count(element); 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument( 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson occurrences > 0, "occurrences cannot be negative: %s", occurrences); 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = backingMap.get(element); 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount = frequency.get(); 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int numberRemoved; 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (oldCount > occurrences) { 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson numberRemoved = occurrences; 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson numberRemoved = oldCount; 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson backingMap.remove(element); 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson frequency.addAndGet(-numberRemoved); 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= numberRemoved; 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Roughly a 33% performance improvement over AbstractMultiset.setCount(). 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int setCount(E element, int count) { 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNonnegative(count, "count"); 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count existingCounter; 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount; 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (count == 0) { 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson existingCounter = backingMap.remove(element); 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = getAndSet(existingCounter, count); 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson existingCounter = backingMap.get(element); 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldCount = getAndSet(existingCounter, count); 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (existingCounter == null) { 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert backingMap.put(element, new Count(count)); 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size += (count - oldCount); 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static int getAndSet(Count i, int count) { 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (i == null) { 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return i.getAndSet(count); 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private int removeAllOccurrences(@Nullable Object element, 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<E, Count> map) { 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Count frequency = map.remove(element); 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (frequency == null) { 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int numberRemoved = frequency.getAndSet(0); 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= numberRemoved; 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return numberRemoved; 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Set<E> createElementSet() { 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new MapBasedElementSet(backingMap); 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(user): once TreeMultiset is replaced with a SortedMultiset 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // implementation, replace this with a subclass of Multisets.ElementSet. 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson class MapBasedElementSet extends ForwardingSet<E> { 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // This mapping is the usually the same as 'backingMap', but can be a 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // submap in some implementations. 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private final Map<E, Count> map; 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Set<E> delegate; 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert MapBasedElementSet(Map<E, Count> map) { 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate = map.keySet(); 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override protected Set<E> delegate() { 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate; 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Iterator<Map.Entry<E, Count>> entries 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = map.entrySet().iterator(); 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<E>() { 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map.Entry<E, Count> toRemove; 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entries.hasNext(); 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public E next() { 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson toRemove = entries.next(); 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return toRemove.getKey(); 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(toRemove != null, 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "no calls to next() since the last call to remove()"); 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson size -= toRemove.getValue().getAndSet(0); 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries.remove(); 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson toRemove = null; 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object element) { 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return removeAllOccurrences(element, map) != 0; 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> elementsToRemove) { 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), elementsToRemove); 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> elementsToRetain) { 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), elementsToRetain); 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (map == backingMap) { 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson AbstractMapBasedMultiset.this.clear(); 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<E> i = iterator(); 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (i.hasNext()) { 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.next(); 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.remove(); 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Map<E, Count> getMap() { 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map; 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Don't allow default serialization. 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 396