001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020
021import com.google.common.annotations.Beta;
022import com.google.common.annotations.GwtCompatible;
023import com.google.errorprone.annotations.CanIgnoreReturnValue;
024import com.google.errorprone.annotations.CompatibleWith;
025import java.util.Collection;
026import java.util.Collections;
027import java.util.Iterator;
028import java.util.List;
029import java.util.Set;
030import java.util.Spliterator;
031import java.util.function.Consumer;
032import java.util.function.ObjIntConsumer;
033import org.checkerframework.checker.nullness.qual.Nullable;
034
035/**
036 * A collection that supports order-independent equality, like {@link Set}, but may have duplicate
037 * elements. A multiset is also sometimes called a <i>bag</i>.
038 *
039 * <p>Elements of a multiset that are equal to one another are referred to as <i>occurrences</i> of
040 * the same single element. The total number of occurrences of an element in a multiset is called
041 * the <i>count</i> of that element (the terms "frequency" and "multiplicity" are equivalent, but
042 * not used in this API). Since the count of an element is represented as an {@code int}, a multiset
043 * may never contain more than {@link Integer#MAX_VALUE} occurrences of any one element.
044 *
045 * <p>{@code Multiset} refines the specifications of several methods from {@code Collection}. It
046 * also defines an additional query operation, {@link #count}, which returns the count of an
047 * element. There are five new bulk-modification operations, for example {@link #add(Object, int)},
048 * to add or remove multiple occurrences of an element at once, or to set the count of an element to
049 * a specific value. These modification operations are optional, but implementations which support
050 * the standard collection operations {@link #add(Object)} or {@link #remove(Object)} are encouraged
051 * to implement the related methods as well. Finally, two collection views are provided: {@link
052 * #elementSet} contains the distinct elements of the multiset "with duplicates collapsed", and
053 * {@link #entrySet} is similar but contains {@link Entry Multiset.Entry} instances, each providing
054 * both a distinct element and the count of that element.
055 *
056 * <p>In addition to these required methods, implementations of {@code Multiset} are expected to
057 * provide two {@code static} creation methods: {@code create()}, returning an empty multiset, and
058 * {@code create(Iterable<? extends E>)}, returning a multiset containing the given initial
059 * elements. This is simply a refinement of {@code Collection}'s constructor recommendations,
060 * reflecting the new developments of Java 5.
061 *
062 * <p>As with other collection types, the modification operations are optional, and should throw
063 * {@link UnsupportedOperationException} when they are not implemented. Most implementations should
064 * support either all add operations or none of them, all removal operations or none of them, and if
065 * and only if all of these are supported, the {@code setCount} methods as well.
066 *
067 * <p>A multiset uses {@link Object#equals} to determine whether two instances should be considered
068 * "the same," <i>unless specified otherwise</i> by the implementation.
069 *
070 * <p>Common implementations include {@link ImmutableMultiset}, {@link HashMultiset}, and {@link
071 * ConcurrentHashMultiset}.
072 *
073 * <p>If your values may be zero, negative, or outside the range of an int, you may wish to use
074 * {@link com.google.common.util.concurrent.AtomicLongMap} instead. Note, however, that unlike
075 * {@code Multiset}, {@code AtomicLongMap} does not automatically remove zeros.
076 *
077 * <p>See the Guava User Guide article on <a href=
078 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multiset"> {@code
079 * Multiset}</a>.
080 *
081 * @author Kevin Bourrillion
082 * @since 2.0
083 */
084@GwtCompatible
085public interface Multiset<E> extends Collection<E> {
086  // Query Operations
087
088  /**
089   * Returns the total number of all occurrences of all elements in this multiset.
090   *
091   * <p><b>Note:</b> this method does not return the number of <i>distinct elements</i> in the
092   * multiset, which is given by {@code entrySet().size()}.
093   */
094  @Override
095  int size();
096
097  /**
098   * Returns the number of occurrences of an element in this multiset (the <i>count</i> of the
099   * element). Note that for an {@link Object#equals}-based multiset, this gives the same result as
100   * {@link Collections#frequency} (which would presumably perform more poorly).
101   *
102   * <p><b>Note:</b> the utility method {@link Iterables#frequency} generalizes this operation; it
103   * correctly delegates to this method when dealing with a multiset, but it can also accept any
104   * other iterable type.
105   *
106   * @param element the element to count occurrences of
107   * @return the number of occurrences of the element in this multiset; possibly zero but never
108   *     negative
109   */
110  int count(@Nullable @CompatibleWith("E") Object element);
111
112  // Bulk Operations
113
114  /**
115   * Adds a number of occurrences of an element to this multiset. Note that if {@code occurrences ==
116   * 1}, this method has the identical effect to {@link #add(Object)}. This method is functionally
117   * equivalent (except in the case of overflow) to the call {@code
118   * addAll(Collections.nCopies(element, occurrences))}, which would presumably perform much more
119   * poorly.
120   *
121   * @param element the element to add occurrences of; may be null only if explicitly allowed by the
122   *     implementation
123   * @param occurrences the number of occurrences of the element to add. May be zero, in which case
124   *     no change will be made.
125   * @return the count of the element before the operation; possibly zero
126   * @throws IllegalArgumentException if {@code occurrences} is negative, or if this operation would
127   *     result in more than {@link Integer#MAX_VALUE} occurrences of the element
128   * @throws NullPointerException if {@code element} is null and this implementation does not permit
129   *     null elements. Note that if {@code occurrences} is zero, the implementation may opt to
130   *     return normally.
131   */
132  @CanIgnoreReturnValue
133  int add(@Nullable E element, int occurrences);
134
135  /**
136   * Adds a single occurrence of the specified element to this multiset.
137   *
138   * <p>This method refines {@link Collection#add}, which only <i>ensures</i> the presence of the
139   * element, to further specify that a successful call must always increment the count of the
140   * element, and the overall size of the collection, by one.
141   *
142   * <p>To both add the element and obtain the previous count of that element, use {@link
143   * #add(Object, int) add}{@code (element, 1)} instead.
144   *
145   * @param element the element to add one occurrence of; may be null only if explicitly allowed by
146   *     the implementation
147   * @return {@code true} always, since this call is required to modify the multiset, unlike other
148   *     {@link Collection} types
149   * @throws NullPointerException if {@code element} is null and this implementation does not permit
150   *     null elements
151   * @throws IllegalArgumentException if {@link Integer#MAX_VALUE} occurrences of {@code element}
152   *     are already contained in this multiset
153   */
154  @CanIgnoreReturnValue
155  @Override
156  boolean add(E element);
157
158  /**
159   * Removes a number of occurrences of the specified element from this multiset. If the multiset
160   * contains fewer than this number of occurrences to begin with, all occurrences will be removed.
161   * Note that if {@code occurrences == 1}, this is functionally equivalent to the call {@code
162   * remove(element)}.
163   *
164   * @param element the element to conditionally remove occurrences of
165   * @param occurrences the number of occurrences of the element to remove. May be zero, in which
166   *     case no change will be made.
167   * @return the count of the element before the operation; possibly zero
168   * @throws IllegalArgumentException if {@code occurrences} is negative
169   */
170  @CanIgnoreReturnValue
171  int remove(@Nullable @CompatibleWith("E") Object element, int occurrences);
172
173  /**
174   * Removes a <i>single</i> occurrence of the specified element from this multiset, if present.
175   *
176   * <p>This method refines {@link Collection#remove} to further specify that it <b>may not</b>
177   * throw an exception in response to {@code element} being null or of the wrong type.
178   *
179   * <p>To both remove the element and obtain the previous count of that element, use {@link
180   * #remove(Object, int) remove}{@code (element, 1)} instead.
181   *
182   * @param element the element to remove one occurrence of
183   * @return {@code true} if an occurrence was found and removed
184   */
185  @CanIgnoreReturnValue
186  @Override
187  boolean remove(@Nullable Object element);
188
189  /**
190   * Adds or removes the necessary occurrences of an element such that the element attains the
191   * desired count.
192   *
193   * @param element the element to add or remove occurrences of; may be null only if explicitly
194   *     allowed by the implementation
195   * @param count the desired count of the element in this multiset
196   * @return the count of the element before the operation; possibly zero
197   * @throws IllegalArgumentException if {@code count} is negative
198   * @throws NullPointerException if {@code element} is null and this implementation does not permit
199   *     null elements. Note that if {@code count} is zero, the implementor may optionally return
200   *     zero instead.
201   */
202  @CanIgnoreReturnValue
203  int setCount(E element, int count);
204
205  /**
206   * Conditionally sets the count of an element to a new value, as described in {@link
207   * #setCount(Object, int)}, provided that the element has the expected current count. If the
208   * current count is not {@code oldCount}, no change is made.
209   *
210   * @param element the element to conditionally set the count of; may be null only if explicitly
211   *     allowed by the implementation
212   * @param oldCount the expected present count of the element in this multiset
213   * @param newCount the desired count of the element in this multiset
214   * @return {@code true} if the condition for modification was met. This implies that the multiset
215   *     was indeed modified, unless {@code oldCount == newCount}.
216   * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is negative
217   * @throws NullPointerException if {@code element} is null and the implementation does not permit
218   *     null elements. Note that if {@code oldCount} and {@code newCount} are both zero, the
219   *     implementor may optionally return {@code true} instead.
220   */
221  @CanIgnoreReturnValue
222  boolean setCount(E element, int oldCount, int newCount);
223
224  // Views
225
226  /**
227   * Returns the set of distinct elements contained in this multiset. The element set is backed by
228   * the same data as the multiset, so any change to either is immediately reflected in the other.
229   * The order of the elements in the element set is unspecified.
230   *
231   * <p>If the element set supports any removal operations, these necessarily cause <b>all</b>
232   * occurrences of the removed element(s) to be removed from the multiset. Implementations are not
233   * expected to support the add operations, although this is possible.
234   *
235   * <p>A common use for the element set is to find the number of distinct elements in the multiset:
236   * {@code elementSet().size()}.
237   *
238   * @return a view of the set of distinct elements in this multiset
239   */
240  Set<E> elementSet();
241
242  /**
243   * Returns a view of the contents of this multiset, grouped into {@code Multiset.Entry} instances,
244   * each providing an element of the multiset and the count of that element. This set contains
245   * exactly one entry for each distinct element in the multiset (thus it always has the same size
246   * as the {@link #elementSet}). The order of the elements in the element set is unspecified.
247   *
248   * <p>The entry set is backed by the same data as the multiset, so any change to either is
249   * immediately reflected in the other. However, multiset changes may or may not be reflected in
250   * any {@code Entry} instances already retrieved from the entry set (this is
251   * implementation-dependent). Furthermore, implementations are not required to support
252   * modifications to the entry set at all, and the {@code Entry} instances themselves don't even
253   * have methods for modification. See the specific implementation class for more details on how
254   * its entry set handles modifications.
255   *
256   * @return a set of entries representing the data of this multiset
257   */
258  Set<Entry<E>> entrySet();
259
260  /**
261   * An unmodifiable element-count pair for a multiset. The {@link Multiset#entrySet} method returns
262   * a view of the multiset whose elements are of this class. A multiset implementation may return
263   * Entry instances that are either live "read-through" views to the Multiset, or immutable
264   * snapshots. Note that this type is unrelated to the similarly-named type {@code Map.Entry}.
265   *
266   * @since 2.0
267   */
268  interface Entry<E> {
269
270    /**
271     * Returns the multiset element corresponding to this entry. Multiple calls to this method
272     * always return the same instance.
273     *
274     * @return the element corresponding to this entry
275     */
276    E getElement();
277
278    /**
279     * Returns the count of the associated element in the underlying multiset. This count may either
280     * be an unchanging snapshot of the count at the time the entry was retrieved, or a live view of
281     * the current count of the element in the multiset, depending on the implementation. Note that
282     * in the former case, this method can never return zero, while in the latter, it will return
283     * zero if all occurrences of the element were since removed from the multiset.
284     *
285     * @return the count of the element; never negative
286     */
287    int getCount();
288
289    /**
290     * {@inheritDoc}
291     *
292     * <p>Returns {@code true} if the given object is also a multiset entry and the two entries
293     * represent the same element and count. That is, two entries {@code a} and {@code b} are equal
294     * if:
295     *
296     * <pre>{@code
297     * Objects.equal(a.getElement(), b.getElement())
298     *     && a.getCount() == b.getCount()
299     * }</pre>
300     */
301    @Override
302    // TODO(kevinb): check this wrt TreeMultiset?
303    boolean equals(Object o);
304
305    /**
306     * {@inheritDoc}
307     *
308     * <p>The hash code of a multiset entry for element {@code element} and count {@code count} is
309     * defined as:
310     *
311     * <pre>{@code
312     * ((element == null) ? 0 : element.hashCode()) ^ count
313     * }</pre>
314     */
315    @Override
316    int hashCode();
317
318    /**
319     * Returns the canonical string representation of this entry, defined as follows. If the count
320     * for this entry is one, this is simply the string representation of the corresponding element.
321     * Otherwise, it is the string representation of the element, followed by the three characters
322     * {@code " x "} (space, letter x, space), followed by the count.
323     */
324    @Override
325    String toString();
326  }
327
328  /**
329   * Runs the specified action for each distinct element in this multiset, and the number of
330   * occurrences of that element. For some {@code Multiset} implementations, this may be more
331   * efficient than iterating over the {@link #entrySet()} either explicitly or with {@code
332   * entrySet().forEach(action)}.
333   *
334   * @since 21.0
335   */
336  @Beta
337  default void forEachEntry(ObjIntConsumer<? super E> action) {
338    checkNotNull(action);
339    entrySet().forEach(entry -> action.accept(entry.getElement(), entry.getCount()));
340  }
341
342  // Comparison and hashing
343
344  /**
345   * Compares the specified object with this multiset for equality. Returns {@code true} if the
346   * given object is also a multiset and contains equal elements with equal counts, regardless of
347   * order.
348   */
349  @Override
350  // TODO(kevinb): caveats about equivalence-relation?
351  boolean equals(@Nullable Object object);
352
353  /**
354   * Returns the hash code for this multiset. This is defined as the sum of
355   *
356   * <pre>{@code
357   * ((element == null) ? 0 : element.hashCode()) ^ count(element)
358   * }</pre>
359   *
360   * <p>over all distinct elements in the multiset. It follows that a multiset and its entry set
361   * always have the same hash code.
362   */
363  @Override
364  int hashCode();
365
366  /**
367   * {@inheritDoc}
368   *
369   * <p>It is recommended, though not mandatory, that this method return the result of invoking
370   * {@link #toString} on the {@link #entrySet}, yielding a result such as {@code [a x 3, c, d x 2,
371   * e]}.
372   */
373  @Override
374  String toString();
375
376  // Refined Collection Methods
377
378  /**
379   * {@inheritDoc}
380   *
381   * <p>Elements that occur multiple times in the multiset will appear multiple times in this
382   * iterator, though not necessarily sequentially.
383   */
384  @Override
385  Iterator<E> iterator();
386
387  /**
388   * Determines whether this multiset contains the specified element.
389   *
390   * <p>This method refines {@link Collection#contains} to further specify that it <b>may not</b>
391   * throw an exception in response to {@code element} being null or of the wrong type.
392   *
393   * @param element the element to check for
394   * @return {@code true} if this multiset contains at least one occurrence of the element
395   */
396  @Override
397  boolean contains(@Nullable Object element);
398
399  /**
400   * Returns {@code true} if this multiset contains at least one occurrence of each element in the
401   * specified collection.
402   *
403   * <p>This method refines {@link Collection#containsAll} to further specify that it <b>may not</b>
404   * throw an exception in response to any of {@code elements} being null or of the wrong type.
405   *
406   * <p><b>Note:</b> this method does not take into account the occurrence count of an element in
407   * the two collections; it may still return {@code true} even if {@code elements} contains several
408   * occurrences of an element and this multiset contains only one. This is no different than any
409   * other collection type like {@link List}, but it may be unexpected to the user of a multiset.
410   *
411   * @param elements the collection of elements to be checked for containment in this multiset
412   * @return {@code true} if this multiset contains at least one occurrence of each element
413   *     contained in {@code elements}
414   * @throws NullPointerException if {@code elements} is null
415   */
416  @Override
417  boolean containsAll(Collection<?> elements);
418
419  /**
420   * {@inheritDoc}
421   *
422   * <p><b>Note:</b> This method ignores how often any element might appear in {@code c}, and only
423   * cares whether or not an element appears at all. If you wish to remove one occurrence in this
424   * multiset for every occurrence in {@code c}, see {@link Multisets#removeOccurrences(Multiset,
425   * Multiset)}.
426   *
427   * <p>This method refines {@link Collection#removeAll} to further specify that it <b>may not</b>
428   * throw an exception in response to any of {@code elements} being null or of the wrong type.
429   */
430  @CanIgnoreReturnValue
431  @Override
432  boolean removeAll(Collection<?> c);
433
434  /**
435   * {@inheritDoc}
436   *
437   * <p><b>Note:</b> This method ignores how often any element might appear in {@code c}, and only
438   * cares whether or not an element appears at all. If you wish to remove one occurrence in this
439   * multiset for every occurrence in {@code c}, see {@link Multisets#retainOccurrences(Multiset,
440   * Multiset)}.
441   *
442   * <p>This method refines {@link Collection#retainAll} to further specify that it <b>may not</b>
443   * throw an exception in response to any of {@code elements} being null or of the wrong type.
444   *
445   * @see Multisets#retainOccurrences(Multiset, Multiset)
446   */
447  @CanIgnoreReturnValue
448  @Override
449  boolean retainAll(Collection<?> c);
450
451  /**
452   * {@inheritDoc}
453   *
454   * <p>Elements that occur multiple times in the multiset will be passed to the {@code Consumer}
455   * correspondingly many times, though not necessarily sequentially.
456   */
457  @Override
458  default void forEach(Consumer<? super E> action) {
459    checkNotNull(action);
460    entrySet()
461        .forEach(
462            entry -> {
463              E elem = entry.getElement();
464              int count = entry.getCount();
465              for (int i = 0; i < count; i++) {
466                action.accept(elem);
467              }
468            });
469  }
470
471  @Override
472  default Spliterator<E> spliterator() {
473    return Multisets.spliteratorImpl(this);
474  }
475}