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