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.checkNotNull;
20
21 import com.google.common.annotations.Beta;
22 import com.google.common.annotations.GwtCompatible;
23 import com.google.errorprone.annotations.CanIgnoreReturnValue;
24 import com.google.errorprone.annotations.CompatibleWith;
25 import java.util.Collection;
26 import java.util.Collections;
27 import java.util.Iterator;
28 import java.util.List;
29 import java.util.Set;
30 import java.util.Spliterator;
31 import java.util.function.Consumer;
32 import java.util.function.ObjIntConsumer;
33 import javax.annotation.CheckForNull;
34 import org.checkerframework.checker.nullness.qual.Nullable;
35
36 /**
37 * A collection that supports order-independent equality, like {@link Set}, but may have duplicate
38 * elements. A multiset is also sometimes called a <i>bag</i>.
39 *
40 * <p>Elements of a multiset that are equal to one another are referred to as <i>occurrences</i> of
41 * the same single element. The total number of occurrences of an element in a multiset is called
42 * the <i>count</i> of that element (the terms "frequency" and "multiplicity" are equivalent, but
43 * not used in this API). Since the count of an element is represented as an {@code int}, a multiset
44 * may never contain more than {@link Integer#MAX_VALUE} occurrences of any one element.
45 *
46 * <p>{@code Multiset} refines the specifications of several methods from {@code Collection}. It
47 * also defines an additional query operation, {@link #count}, which returns the count of an
48 * element. There are five new bulk-modification operations, for example {@link #add(Object, int)},
49 * to add or remove multiple occurrences of an element at once, or to set the count of an element to
50 * a specific value. These modification operations are optional, but implementations which support
51 * the standard collection operations {@link #add(Object)} or {@link #remove(Object)} are encouraged
52 * to implement the related methods as well. Finally, two collection views are provided: {@link
53 * #elementSet} contains the distinct elements of the multiset "with duplicates collapsed", and
54 * {@link #entrySet} is similar but contains {@link Entry Multiset.Entry} instances, each providing
55 * both a distinct element and the count of that element.
56 *
57 * <p>In addition to these required methods, implementations of {@code Multiset} are expected to
58 * provide two {@code static} creation methods: {@code create()}, returning an empty multiset, and
59 * {@code create(Iterable<? extends E>)}, returning a multiset containing the given initial
60 * elements. This is simply a refinement of {@code Collection}'s constructor recommendations,
61 * reflecting the new developments of Java 5.
62 *
63 * <p>As with other collection types, the modification operations are optional, and should throw
64 * {@link UnsupportedOperationException} when they are not implemented. Most implementations should
65 * support either all add operations or none of them, all removal operations or none of them, and if
66 * and only if all of these are supported, the {@code setCount} methods as well.
67 *
68 * <p>A multiset uses {@link Object#equals} to determine whether two instances should be considered
69 * "the same," <i>unless specified otherwise</i> by the implementation.
70 *
71 * <p><b>Warning:</b> as with normal {@link Set}s, it is almost always a bad idea to modify an
72 * element (in a way that affects its {@link Object#equals} behavior) while it is contained in a
73 * multiset. Undefined behavior and bugs will result.
74 *
75 * <p>Common implementations include {@link ImmutableMultiset}, {@link HashMultiset}, and {@link
76 * ConcurrentHashMultiset}.
77 *
78 * <p>If your values may be zero, negative, or outside the range of an int, you may wish to use
79 * {@link com.google.common.util.concurrent.AtomicLongMap} instead. Note, however, that unlike
80 * {@code Multiset}, {@code AtomicLongMap} does not automatically remove zeros.
81 *
82 * <p>See the Guava User Guide article on <a href=
83 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multiset"> {@code
84 * Multiset}</a>.
85 *
86 * @author Kevin Bourrillion
87 * @since 2.0
88 */
89 @GwtCompatible
90 @ElementTypesAreNonnullByDefault
91 public interface Multiset<E extends @Nullable Object> extends Collection<E> {
92 // Query Operations
93
94 /**
95 * Returns the total number of all occurrences of all elements in this multiset.
96 *
97 * <p><b>Note:</b> this method does not return the number of <i>distinct elements</i> in the
98 * multiset, which is given by {@code entrySet().size()}.
99 */
100 @Override
101 int size();
102
103 /**
104 * Returns the number of occurrences of an element in this multiset (the <i>count</i> of the
105 * element). Note that for an {@link Object#equals}-based multiset, this gives the same result as
106 * {@link Collections#frequency} (which would presumably perform more poorly).
107 *
108 * <p><b>Note:</b> the utility method {@link Iterables#frequency} generalizes this operation; it
109 * correctly delegates to this method when dealing with a multiset, but it can also accept any
110 * other iterable type.
111 *
112 * @param element the element to count occurrences of
113 * @return the number of occurrences of the element in this multiset; possibly zero but never
114 * negative
115 */
116 int count(@CompatibleWith("E") @CheckForNull Object element);
117
118 // Bulk Operations
119
120 /**
121 * Adds a number of occurrences of an element to this multiset. Note that if {@code occurrences ==
122 * 1}, this method has the identical effect to {@link #add(Object)}. This method is functionally
123 * equivalent (except in the case of overflow) to the call {@code
124 * addAll(Collections.nCopies(element, occurrences))}, which would presumably perform much more
125 * poorly.
126 *
127 * @param element the element to add occurrences of; may be null only if explicitly allowed by the
128 * implementation
129 * @param occurrences the number of occurrences of the element to add. May be zero, in which case
130 * no change will be made.
131 * @return the count of the element before the operation; possibly zero
132 * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation would
133 * result in more than {@link Integer#MAX_VALUE} occurrences of the element
134 * @throws NullPointerException if {@code element} is null and this implementation does not permit
135 * null elements. Note that if {@code occurrences} is zero, the implementation may opt to
136 * return normally.
137 */
138 @CanIgnoreReturnValue
139 int add(@ParametricNullness E element, int occurrences);
140
141 /**
142 * Adds a single occurrence of the specified element to this multiset.
143 *
144 * <p>This method refines {@link Collection#add}, which only <i>ensures</i> the presence of the
145 * element, to further specify that a successful call must always increment the count of the
146 * element, and the overall size of the collection, by one.
147 *
148 * <p>To both add the element and obtain the previous count of that element, use {@link
149 * #add(Object, int) add}{@code (element, 1)} instead.
150 *
151 * @param element the element to add one occurrence of; may be null only if explicitly allowed by
152 * the implementation
153 * @return {@code true} always, since this call is required to modify the multiset, unlike other
154 * {@link Collection} types
155 * @throws NullPointerException if {@code element} is null and this implementation does not permit
156 * null elements
157 * @throws IllegalArgumentException if {@link Integer#MAX_VALUE} occurrences of {@code element}
158 * are already contained in this multiset
159 */
160 @CanIgnoreReturnValue
161 @Override
162 boolean add(@ParametricNullness E element);
163
164 /**
165 * Removes a number of occurrences of the specified element from this multiset. If the multiset
166 * contains fewer than this number of occurrences to begin with, all occurrences will be removed.
167 * Note that if {@code occurrences == 1}, this is functionally equivalent to the call {@code
168 * remove(element)}.
169 *
170 * @param element the element to conditionally remove occurrences of
171 * @param occurrences the number of occurrences of the element to remove. May be zero, in which
172 * case no change will be made.
173 * @return the count of the element before the operation; possibly zero
174 * @throws IllegalArgumentException if {@code occurrences} is negative
175 */
176 @CanIgnoreReturnValue
177 int remove(@CompatibleWith("E") @CheckForNull Object element, int occurrences);
178
179 /**
180 * Removes a <i>single</i> occurrence of the specified element from this multiset, if present.
181 *
182 * <p>This method refines {@link Collection#remove} to further specify that it <b>may not</b>
183 * throw an exception in response to {@code element} being null or of the wrong type.
184 *
185 * <p>To both remove the element and obtain the previous count of that element, use {@link
186 * #remove(Object, int) remove}{@code (element, 1)} instead.
187 *
188 * @param element the element to remove one occurrence of
189 * @return {@code true} if an occurrence was found and removed
190 */
191 @CanIgnoreReturnValue
192 @Override
193 boolean remove(@CheckForNull Object element);
194
195 /**
196 * Adds or removes the necessary occurrences of an element such that the element attains the
197 * desired count.
198 *
199 * @param element the element to add or remove occurrences of; may be null only if explicitly
200 * allowed by the implementation
201 * @param count the desired count of the element in this multiset
202 * @return the count of the element before the operation; possibly zero
203 * @throws IllegalArgumentException if {@code count} is negative
204 * @throws NullPointerException if {@code element} is null and this implementation does not permit
205 * null elements. Note that if {@code count} is zero, the implementor may optionally return
206 * zero instead.
207 */
208 @CanIgnoreReturnValue
209 int setCount(@ParametricNullness E element, int count);
210
211 /**
212 * Conditionally sets the count of an element to a new value, as described in {@link
213 * #setCount(Object, int)}, provided that the element has the expected current count. If the
214 * current count is not {@code oldCount}, no change is made.
215 *
216 * @param element the element to conditionally set the count of; may be null only if explicitly
217 * allowed by the implementation
218 * @param oldCount the expected present count of the element in this multiset
219 * @param newCount the desired count of the element in this multiset
220 * @return {@code true} if the condition for modification was met. This implies that the multiset
221 * was indeed modified, unless {@code oldCount == newCount}.
222 * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is negative
223 * @throws NullPointerException if {@code element} is null and the implementation does not permit
224 * null elements. Note that if {@code oldCount} and {@code newCount} are both zero, the
225 * implementor may optionally return {@code true} instead.
226 */
227 @CanIgnoreReturnValue
228 boolean setCount(@ParametricNullness E element, int oldCount, int newCount);
229
230 // Views
231
232 /**
233 * Returns the set of distinct elements contained in this multiset. The element set is backed by
234 * the same data as the multiset, so any change to either is immediately reflected in the other.
235 * The order of the elements in the element set is unspecified.
236 *
237 * <p>If the element set supports any removal operations, these necessarily cause <b>all</b>
238 * occurrences of the removed element(s) to be removed from the multiset. Implementations are not
239 * expected to support the add operations, although this is possible.
240 *
241 * <p>A common use for the element set is to find the number of distinct elements in the multiset:
242 * {@code elementSet().size()}.
243 *
244 * @return a view of the set of distinct elements in this multiset
245 */
246 Set<E> elementSet();
247
248 /**
249 * Returns a view of the contents of this multiset, grouped into {@code Multiset.Entry} instances,
250 * each providing an element of the multiset and the count of that element. This set contains
251 * exactly one entry for each distinct element in the multiset (thus it always has the same size
252 * as the {@link #elementSet}). The order of the elements in the element set is unspecified.
253 *
254 * <p>The entry set is backed by the same data as the multiset, so any change to either is
255 * immediately reflected in the other. However, multiset changes may or may not be reflected in
256 * any {@code Entry} instances already retrieved from the entry set (this is
257 * implementation-dependent). Furthermore, implementations are not required to support
258 * modifications to the entry set at all, and the {@code Entry} instances themselves don't even
259 * have methods for modification. See the specific implementation class for more details on how
260 * its entry set handles modifications.
261 *
262 * @return a set of entries representing the data of this multiset
263 */
264 Set<Entry<E>> entrySet();
265
266 /**
267 * An unmodifiable element-count pair for a multiset. The {@link Multiset#entrySet} method returns
268 * a view of the multiset whose elements are of this class. A multiset implementation may return
269 * Entry instances that are either live "read-through" views to the Multiset, or immutable
270 * snapshots. Note that this type is unrelated to the similarly-named type {@code Map.Entry}.
271 *
272 * @since 2.0
273 */
274 interface Entry<E extends @Nullable Object> {
275
276 /**
277 * Returns the multiset element corresponding to this entry. Multiple calls to this method
278 * always return the same instance.
279 *
280 * @return the element corresponding to this entry
281 */
282 @ParametricNullness
283 E getElement();
284
285 /**
286 * Returns the count of the associated element in the underlying multiset. This count may either
287 * be an unchanging snapshot of the count at the time the entry was retrieved, or a live view of
288 * the current count of the element in the multiset, depending on the implementation. Note that
289 * in the former case, this method can never return zero, while in the latter, it will return
290 * zero if all occurrences of the element were since removed from the multiset.
291 *
292 * @return the count of the element; never negative
293 */
294 int getCount();
295
296 /**
297 * {@inheritDoc}
298 *
299 * <p>Returns {@code true} if the given object is also a multiset entry and the two entries
300 * represent the same element and count. That is, two entries {@code a} and {@code b} are equal
301 * if:
302 *
303 * <pre>{@code
304 * Objects.equal(a.getElement(), b.getElement())
305 * && a.getCount() == b.getCount()
306 * }</pre>
307 */
308 @Override
309 // TODO(kevinb): check this wrt TreeMultiset?
310 boolean equals(@CheckForNull Object o);
311
312 /**
313 * {@inheritDoc}
314 *
315 * <p>The hash code of a multiset entry for element {@code element} and count {@code count} is
316 * defined as:
317 *
318 * <pre>{@code
319 * ((element == null) ? 0 : element.hashCode()) ^ count
320 * }</pre>
321 */
322 @Override
323 int hashCode();
324
325 /**
326 * Returns the canonical string representation of this entry, defined as follows. If the count
327 * for this entry is one, this is simply the string representation of the corresponding element.
328 * Otherwise, it is the string representation of the element, followed by the three characters
329 * {@code " x "} (space, letter x, space), followed by the count.
330 */
331 @Override
332 String toString();
333 }
334
335 /**
336 * Runs the specified action for each distinct element in this multiset, and the number of
337 * occurrences of that element. For some {@code Multiset} implementations, this may be more
338 * efficient than iterating over the {@link #entrySet()} either explicitly or with {@code
339 * entrySet().forEach(action)}.
340 *
341 * @since 21.0
342 */
343 @Beta
344 default void forEachEntry(ObjIntConsumer<? super E> action) {
345 checkNotNull(action);
346 entrySet().forEach(entry -> action.accept(entry.getElement(), entry.getCount()));
347 }
348
349 // Comparison and hashing
350
351 /**
352 * Compares the specified object with this multiset for equality. Returns {@code true} if the
353 * given object is also a multiset and contains equal elements with equal counts, regardless of
354 * order.
355 */
356 @Override
357 // TODO(kevinb): caveats about equivalence-relation?
358 boolean equals(@CheckForNull Object object);
359
360 /**
361 * Returns the hash code for this multiset. This is defined as the sum of
362 *
363 * <pre>{@code
364 * ((element == null) ? 0 : element.hashCode()) ^ count(element)
365 * }</pre>
366 *
367 * <p>over all distinct elements in the multiset. It follows that a multiset and its entry set
368 * always have the same hash code.
369 */
370 @Override
371 int hashCode();
372
373 /**
374 * {@inheritDoc}
375 *
376 * <p>It is recommended, though not mandatory, that this method return the result of invoking
377 * {@link #toString} on the {@link #entrySet}, yielding a result such as {@code [a x 3, c, d x 2,
378 * e]}.
379 */
380 @Override
381 String toString();
382
383 // Refined Collection Methods
384
385 /**
386 * {@inheritDoc}
387 *
388 * <p>Elements that occur multiple times in the multiset will appear multiple times in this
389 * iterator, though not necessarily sequentially.
390 */
391 @Override
392 Iterator<E> iterator();
393
394 /**
395 * Determines whether this multiset contains the specified element.
396 *
397 * <p>This method refines {@link Collection#contains} to further specify that it <b>may not</b>
398 * throw an exception in response to {@code element} being null or of the wrong type.
399 *
400 * @param element the element to check for
401 * @return {@code true} if this multiset contains at least one occurrence of the element
402 */
403 @Override
404 boolean contains(@CheckForNull Object element);
405
406 /**
407 * Returns {@code true} if this multiset contains at least one occurrence of each element in the
408 * specified collection.
409 *
410 * <p>This method refines {@link Collection#containsAll} to further specify that it <b>may not</b>
411 * throw an exception in response to any of {@code elements} being null or of the wrong type.
412 *
413 * <p><b>Note:</b> this method does not take into account the occurrence count of an element in
414 * the two collections; it may still return {@code true} even if {@code elements} contains several
415 * occurrences of an element and this multiset contains only one. This is no different than any
416 * other collection type like {@link List}, but it may be unexpected to the user of a multiset.
417 *
418 * @param elements the collection of elements to be checked for containment in this multiset
419 * @return {@code true} if this multiset contains at least one occurrence of each element
420 * contained in {@code elements}
421 * @throws NullPointerException if {@code elements} is null
422 */
423 @Override
424 boolean containsAll(Collection<?> elements);
425
426 /**
427 * {@inheritDoc}
428 *
429 * <p><b>Note:</b> This method ignores how often any element might appear in {@code c}, and only
430 * cares whether or not an element appears at all. If you wish to remove one occurrence in this
431 * multiset for every occurrence in {@code c}, see {@link Multisets#removeOccurrences(Multiset,
432 * Multiset)}.
433 *
434 * <p>This method refines {@link Collection#removeAll} to further specify that it <b>may not</b>
435 * throw an exception in response to any of {@code elements} being null or of the wrong type.
436 */
437 @CanIgnoreReturnValue
438 @Override
439 boolean removeAll(Collection<?> c);
440
441 /**
442 * {@inheritDoc}
443 *
444 * <p><b>Note:</b> This method ignores how often any element might appear in {@code c}, and only
445 * cares whether or not an element appears at all. If you wish to remove one occurrence in this
446 * multiset for every occurrence in {@code c}, see {@link Multisets#retainOccurrences(Multiset,
447 * Multiset)}.
448 *
449 * <p>This method refines {@link Collection#retainAll} to further specify that it <b>may not</b>
450 * throw an exception in response to any of {@code elements} being null or of the wrong type.
451 *
452 * @see Multisets#retainOccurrences(Multiset, Multiset)
453 */
454 @CanIgnoreReturnValue
455 @Override
456 boolean retainAll(Collection<?> c);
457
458 /**
459 * {@inheritDoc}
460 *
461 * <p>Elements that occur multiple times in the multiset will be passed to the {@code Consumer}
462 * correspondingly many times, though not necessarily sequentially.
463 */
464 @Override
465 default void forEach(Consumer<? super E> action) {
466 checkNotNull(action);
467 entrySet()
468 .forEach(
469 entry -> {
470 E elem = entry.getElement();
471 int count = entry.getCount();
472 for (int i = 0; i < count; i++) {
473 action.accept(elem);
474 }
475 });
476 }
477
478 @Override
479 default Spliterator<E> spliterator() {
480 return Multisets.spliteratorImpl(this);
481 }
482 }