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