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