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
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.base.Preconditions.checkState;
22 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
23 import static com.google.common.collect.CollectPreconditions.checkRemove;
24 import static java.util.Objects.requireNonNull;
25
26 import com.google.common.annotations.GwtCompatible;
27 import com.google.common.annotations.GwtIncompatible;
28 import com.google.common.primitives.Ints;
29 import com.google.errorprone.annotations.CanIgnoreReturnValue;
30 import java.io.InvalidObjectException;
31 import java.io.ObjectStreamException;
32 import java.io.Serializable;
33 import java.util.ConcurrentModificationException;
34 import java.util.Iterator;
35 import java.util.Map;
36 import java.util.Set;
37 import java.util.function.ObjIntConsumer;
38 import javax.annotation.CheckForNull;
39 import org.checkerframework.checker.nullness.qual.Nullable;
40
41 /**
42 * Basic implementation of {@code Multiset<E>} backed by an instance of {@code Map<E, Count>}.
43 *
44 * <p>For serialization to work, the subclass must specify explicit {@code readObject} and {@code
45 * writeObject} methods.
46 *
47 * @author Kevin Bourrillion
48 */
49 @GwtCompatible(emulated = true)
50 @ElementTypesAreNonnullByDefault
51 abstract class AbstractMapBasedMultiset<E extends @Nullable Object> extends AbstractMultiset<E>
52 implements Serializable {
53 // TODO(lowasser): consider overhauling this back to Map<E, Integer>
54 private transient Map<E, Count> backingMap;
55
56 /*
57 * Cache the size for efficiency. Using a long lets us avoid the need for
58 * overflow checking and ensures that size() will function correctly even if
59 * the multiset had once been larger than Integer.MAX_VALUE.
60 */
61 private transient long size;
62
63 /** Standard constructor. */
64 protected AbstractMapBasedMultiset(Map<E, Count> backingMap) {
65 checkArgument(backingMap.isEmpty());
66 this.backingMap = backingMap;
67 }
68
69 /** Used during deserialization only. The backing map must be empty. */
70 void setBackingMap(Map<E, Count> backingMap) {
71 this.backingMap = backingMap;
72 }
73
74 // Required Implementations
75
76 /**
77 * {@inheritDoc}
78 *
79 * <p>Invoking {@link Multiset.Entry#getCount} on an entry in the returned set always returns the
80 * current count of that element in the multiset, as opposed to the count at the time the entry
81 * was retrieved.
82 */
83 @Override
84 public Set<Multiset.Entry<E>> entrySet() {
85 return super.entrySet();
86 }
87
88 @Override
89 Iterator<E> elementIterator() {
90 final Iterator<Map.Entry<E, Count>> backingEntries = backingMap.entrySet().iterator();
91 return new Iterator<E>() {
92 @CheckForNull Map.Entry<E, Count> toRemove;
93
94 @Override
95 public boolean hasNext() {
96 return backingEntries.hasNext();
97 }
98
99 @Override
100 @ParametricNullness
101 public E next() {
102 final Map.Entry<E, Count> mapEntry = backingEntries.next();
103 toRemove = mapEntry;
104 return mapEntry.getKey();
105 }
106
107 @Override
108 public void remove() {
109 checkState(toRemove != null, "no calls to next() since the last call to remove()");
110 size -= toRemove.getValue().getAndSet(0);
111 backingEntries.remove();
112 toRemove = null;
113 }
114 };
115 }
116
117 @Override
118 Iterator<Entry<E>> entryIterator() {
119 final Iterator<Map.Entry<E, Count>> backingEntries = backingMap.entrySet().iterator();
120 return new Iterator<Multiset.Entry<E>>() {
121 @CheckForNull Map.Entry<E, Count> toRemove;
122
123 @Override
124 public boolean hasNext() {
125 return backingEntries.hasNext();
126 }
127
128 @Override
129 public Multiset.Entry<E> next() {
130 final Map.Entry<E, Count> mapEntry = backingEntries.next();
131 toRemove = mapEntry;
132 return new Multisets.AbstractEntry<E>() {
133 @Override
134 @ParametricNullness
135 public E getElement() {
136 return mapEntry.getKey();
137 }
138
139 @Override
140 public int getCount() {
141 Count count = mapEntry.getValue();
142 if (count == null || count.get() == 0) {
143 Count frequency = backingMap.get(getElement());
144 if (frequency != null) {
145 return frequency.get();
146 }
147 }
148 return (count == null) ? 0 : count.get();
149 }
150 };
151 }
152
153 @Override
154 public void remove() {
155 checkState(toRemove != null, "no calls to next() since the last call to remove()");
156 size -= toRemove.getValue().getAndSet(0);
157 backingEntries.remove();
158 toRemove = null;
159 }
160 };
161 }
162
163 @Override
164 public void forEachEntry(ObjIntConsumer<? super E> action) {
165 checkNotNull(action);
166 backingMap.forEach((element, count) -> action.accept(element, count.get()));
167 }
168
169 @Override
170 public void clear() {
171 for (Count frequency : backingMap.values()) {
172 frequency.set(0);
173 }
174 backingMap.clear();
175 size = 0L;
176 }
177
178 @Override
179 int distinctElements() {
180 return backingMap.size();
181 }
182
183 // Optimizations - Query Operations
184
185 @Override
186 public int size() {
187 return Ints.saturatedCast(size);
188 }
189
190 @Override
191 public Iterator<E> iterator() {
192 return new MapBasedMultisetIterator();
193 }
194
195 /*
196 * Not subclassing AbstractMultiset$MultisetIterator because next() needs to
197 * retrieve the Map.Entry<E, Count> entry, which can then be used for
198 * a more efficient remove() call.
199 */
200 private class MapBasedMultisetIterator implements Iterator<E> {
201 final Iterator<Map.Entry<E, Count>> entryIterator;
202 @CheckForNull Map.Entry<E, Count> currentEntry;
203 int occurrencesLeft;
204 boolean canRemove;
205
206 MapBasedMultisetIterator() {
207 this.entryIterator = backingMap.entrySet().iterator();
208 }
209
210 @Override
211 public boolean hasNext() {
212 return occurrencesLeft > 0 || entryIterator.hasNext();
213 }
214
215 @Override
216 @ParametricNullness
217 public E next() {
218 if (occurrencesLeft == 0) {
219 currentEntry = entryIterator.next();
220 occurrencesLeft = currentEntry.getValue().get();
221 }
222 occurrencesLeft--;
223 canRemove = true;
224 /*
225 * requireNonNull is safe because occurrencesLeft starts at 0, forcing us to initialize
226 * currentEntry above. After that, we never clear it.
227 */
228 return requireNonNull(currentEntry).getKey();
229 }
230
231 @Override
232 public void remove() {
233 checkRemove(canRemove);
234 /*
235 * requireNonNull is safe because canRemove is set to true only after we initialize
236 * currentEntry (which we never subsequently clear).
237 */
238 int frequency = requireNonNull(currentEntry).getValue().get();
239 if (frequency <= 0) {
240 throw new ConcurrentModificationException();
241 }
242 if (currentEntry.getValue().addAndGet(-1) == 0) {
243 entryIterator.remove();
244 }
245 size--;
246 canRemove = false;
247 }
248 }
249
250 @Override
251 public int count(@CheckForNull Object element) {
252 Count frequency = Maps.safeGet(backingMap, element);
253 return (frequency == null) ? 0 : frequency.get();
254 }
255
256 // Optional Operations - Modification Operations
257
258 /**
259 * {@inheritDoc}
260 *
261 * @throws IllegalArgumentException if the call would result in more than {@link
262 * Integer#MAX_VALUE} occurrences of {@code element} in this multiset.
263 */
264 @CanIgnoreReturnValue
265 @Override
266 public int add(@ParametricNullness E element, int occurrences) {
267 if (occurrences == 0) {
268 return count(element);
269 }
270 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences);
271 Count frequency = backingMap.get(element);
272 int oldCount;
273 if (frequency == null) {
274 oldCount = 0;
275 backingMap.put(element, new Count(occurrences));
276 } else {
277 oldCount = frequency.get();
278 long newCount = (long) oldCount + (long) occurrences;
279 checkArgument(newCount <= Integer.MAX_VALUE, "too many occurrences: %s", newCount);
280 frequency.add(occurrences);
281 }
282 size += occurrences;
283 return oldCount;
284 }
285
286 @CanIgnoreReturnValue
287 @Override
288 public int remove(@CheckForNull Object element, int occurrences) {
289 if (occurrences == 0) {
290 return count(element);
291 }
292 checkArgument(occurrences > 0, "occurrences cannot be negative: %s", occurrences);
293 Count frequency = backingMap.get(element);
294 if (frequency == null) {
295 return 0;
296 }
297
298 int oldCount = frequency.get();
299
300 int numberRemoved;
301 if (oldCount > occurrences) {
302 numberRemoved = occurrences;
303 } else {
304 numberRemoved = oldCount;
305 backingMap.remove(element);
306 }
307
308 frequency.add(-numberRemoved);
309 size -= numberRemoved;
310 return oldCount;
311 }
312
313 // Roughly a 33% performance improvement over AbstractMultiset.setCount().
314 @CanIgnoreReturnValue
315 @Override
316 public int setCount(@ParametricNullness E element, int count) {
317 checkNonnegative(count, "count");
318
319 Count existingCounter;
320 int oldCount;
321 if (count == 0) {
322 existingCounter = backingMap.remove(element);
323 oldCount = getAndSet(existingCounter, count);
324 } else {
325 existingCounter = backingMap.get(element);
326 oldCount = getAndSet(existingCounter, count);
327
328 if (existingCounter == null) {
329 backingMap.put(element, new Count(count));
330 }
331 }
332
333 size += (count - oldCount);
334 return oldCount;
335 }
336
337 private static int getAndSet(@CheckForNull Count i, int count) {
338 if (i == null) {
339 return 0;
340 }
341
342 return i.getAndSet(count);
343 }
344
345 // Don't allow default serialization.
346 @GwtIncompatible // java.io.ObjectStreamException
347 private void readObjectNoData() throws ObjectStreamException {
348 throw new InvalidObjectException("Stream data required");
349 }
350
351 @GwtIncompatible // not needed in emulated source.
352 private static final long serialVersionUID = -2250766705698539974L;
353 }