AbstractMapBasedMultiset.java revision 7dd252788645e940eada959bdde927426e2531c9
1/* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkArgument; 20import static com.google.common.base.Preconditions.checkNotNull; 21import static com.google.common.base.Preconditions.checkState; 22import static com.google.common.collect.Multisets.checkNonnegative; 23 24import com.google.common.annotations.GwtCompatible; 25import com.google.common.annotations.GwtIncompatible; 26import com.google.common.primitives.Ints; 27 28import java.io.InvalidObjectException; 29import java.io.ObjectStreamException; 30import java.io.Serializable; 31import java.util.ConcurrentModificationException; 32import java.util.Iterator; 33import java.util.Map; 34import java.util.Set; 35 36import javax.annotation.Nullable; 37 38/** 39 * Basic implementation of {@code Multiset<E>} backed by an instance of {@code 40 * Map<E, Count>}. 41 * 42 * <p>For serialization to work, the subclass must specify explicit {@code 43 * readObject} and {@code writeObject} methods. 44 * 45 * @author Kevin Bourrillion 46 */ 47@GwtCompatible(emulated = true) 48abstract class AbstractMapBasedMultiset<E> extends AbstractMultiset<E> implements Serializable { 49 50 private transient Map<E, Count> backingMap; 51 52 /* 53 * Cache the size for efficiency. Using a long lets us avoid the need for 54 * overflow checking and ensures that size() will function correctly even if 55 * the multiset had once been larger than Integer.MAX_VALUE. 56 */ 57 private transient long size; 58 59 /** Standard constructor. */ 60 protected AbstractMapBasedMultiset(Map<E, Count> backingMap) { 61 this.backingMap = checkNotNull(backingMap); 62 this.size = super.size(); 63 } 64 65 /** Used during deserialization only. The backing map must be empty. */ 66 void setBackingMap(Map<E, Count> backingMap) { 67 this.backingMap = backingMap; 68 } 69 70 // Required Implementations 71 72 /** 73 * {@inheritDoc} 74 * 75 * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned 76 * set always returns the current count of that element in the multiset, as 77 * opposed to the count at the time the entry was retrieved. 78 */ 79 80 @Override 81 public Set<Multiset.Entry<E>> entrySet() { 82 return super.entrySet(); 83 } 84 85 @Override 86 Iterator<Entry<E>> entryIterator() { 87 final Iterator<Map.Entry<E, Count>> backingEntries = backingMap.entrySet().iterator(); 88 return new Iterator<Multiset.Entry<E>>() { 89 Map.Entry<E, Count> toRemove; 90 91 public boolean hasNext() { 92 return backingEntries.hasNext(); 93 } 94 95 public Multiset.Entry<E> next() { 96 final Map.Entry<E, Count> mapEntry = backingEntries.next(); 97 toRemove = mapEntry; 98 return new Multisets.AbstractEntry<E>() { 99 100 public E getElement() { 101 return mapEntry.getKey(); 102 } 103 104 public int getCount() { 105 int count = mapEntry.getValue().get(); 106 if (count == 0) { 107 Count frequency = backingMap.get(getElement()); 108 if (frequency != null) { 109 count = frequency.get(); 110 } 111 } 112 return count; 113 } 114 }; 115 } 116 117 public void remove() { 118 Iterators.checkRemove(toRemove != null); 119 size -= toRemove.getValue().getAndSet(0); 120 backingEntries.remove(); 121 toRemove = null; 122 } 123 }; 124 } 125 126 @Override 127 public void clear() { 128 for (Count frequency : backingMap.values()) { 129 frequency.set(0); 130 } 131 backingMap.clear(); 132 size = 0L; 133 } 134 135 @Override 136 int distinctElements() { 137 return backingMap.size(); 138 } 139 140 // Optimizations - Query Operations 141 142 @Override 143 public int size() { 144 return Ints.saturatedCast(size); 145 } 146 147 @Override 148 public Iterator<E> iterator() { 149 return new MapBasedMultisetIterator(); 150 } 151 152 /* 153 * Not subclassing AbstractMultiset$MultisetIterator because next() needs to 154 * retrieve the Map.Entry<E, Count> entry, which can then be used for 155 * a more efficient remove() call. 156 */ 157 private class MapBasedMultisetIterator implements Iterator<E> { 158 final Iterator<Map.Entry<E, Count>> entryIterator; 159 Map.Entry<E, Count> currentEntry; 160 int occurrencesLeft; 161 boolean canRemove; 162 163 MapBasedMultisetIterator() { 164 this.entryIterator = backingMap.entrySet().iterator(); 165 } 166 167 public boolean hasNext() { 168 return occurrencesLeft > 0 || entryIterator.hasNext(); 169 } 170 171 public E next() { 172 if (occurrencesLeft == 0) { 173 currentEntry = entryIterator.next(); 174 occurrencesLeft = currentEntry.getValue().get(); 175 } 176 occurrencesLeft--; 177 canRemove = true; 178 return currentEntry.getKey(); 179 } 180 181 public void remove() { 182 checkState(canRemove, "no calls to next() since the last call to remove()"); 183 int frequency = currentEntry.getValue().get(); 184 if (frequency <= 0) { 185 throw new ConcurrentModificationException(); 186 } 187 if (currentEntry.getValue().addAndGet(-1) == 0) { 188 entryIterator.remove(); 189 } 190 size--; 191 canRemove = false; 192 } 193 } 194 195 @Override public int count(@Nullable Object element) { 196 Count frequency = Maps.safeGet(backingMap, element); 197 return (frequency == null) ? 0 : frequency.get(); 198 } 199 200 // Optional Operations - Modification Operations 201 202 /** 203 * {@inheritDoc} 204 * 205 * @throws IllegalArgumentException if the call would result in more than 206 * {@link Integer#MAX_VALUE} occurrences of {@code element} in this 207 * multiset. 208 */ 209 @Override 210 public int add(@Nullable E element, int occurrences) { 211 if (occurrences == 0) { 212 return count(element); 213 } 214 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences); 215 Count frequency = backingMap.get(element); 216 int oldCount; 217 if (frequency == null) { 218 oldCount = 0; 219 backingMap.put(element, new Count(occurrences)); 220 } else { 221 oldCount = frequency.get(); 222 long newCount = (long) oldCount + (long) occurrences; 223 checkArgument(newCount <= Integer.MAX_VALUE, "too many occurrences: %s", newCount); 224 frequency.getAndAdd(occurrences); 225 } 226 size += occurrences; 227 return oldCount; 228 } 229 230 @Override 231 public int remove(@Nullable Object element, int occurrences) { 232 if (occurrences == 0) { 233 return count(element); 234 } 235 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences); 236 Count frequency = backingMap.get(element); 237 if (frequency == null) { 238 return 0; 239 } 240 241 int oldCount = frequency.get(); 242 243 int numberRemoved; 244 if (oldCount > occurrences) { 245 numberRemoved = occurrences; 246 } else { 247 numberRemoved = oldCount; 248 backingMap.remove(element); 249 } 250 251 frequency.addAndGet(-numberRemoved); 252 size -= numberRemoved; 253 return oldCount; 254 } 255 256 // Roughly a 33% performance improvement over AbstractMultiset.setCount(). 257 @Override 258 public int setCount(@Nullable E element, int count) { 259 checkNonnegative(count, "count"); 260 261 Count existingCounter; 262 int oldCount; 263 if (count == 0) { 264 existingCounter = backingMap.remove(element); 265 oldCount = getAndSet(existingCounter, count); 266 } else { 267 existingCounter = backingMap.get(element); 268 oldCount = getAndSet(existingCounter, count); 269 270 if (existingCounter == null) { 271 backingMap.put(element, new Count(count)); 272 } 273 } 274 275 size += (count - oldCount); 276 return oldCount; 277 } 278 279 private static int getAndSet(Count i, int count) { 280 if (i == null) { 281 return 0; 282 } 283 284 return i.getAndSet(count); 285 } 286 287 // Don't allow default serialization. 288 @GwtIncompatible("java.io.ObjectStreamException") 289 @SuppressWarnings("unused") 290 // actually used during deserialization 291 private void readObjectNoData() throws ObjectStreamException { 292 throw new InvalidObjectException("Stream data required"); 293 } 294 295 @GwtIncompatible("not needed in emulated source.") 296 private static final long serialVersionUID = -2250766705698539974L; 297} 298