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