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 javax.annotation.Nullable;
034
035/**
036 * A collection that supports order-independent equality, like {@link Set}, but
037 * may have duplicate elements. A multiset is also sometimes called a
038 * <i>bag</i>.
039 *
040 * <p>Elements of a multiset that are equal to one another are referred to as
041 * <i>occurrences</i> of the same single element. The total number of
042 * occurrences of an element in a multiset is called the <i>count</i> of that
043 * element (the terms "frequency" and "multiplicity" are equivalent, but not
044 * used in this API). Since the count of an element is represented as an {@code
045 * int}, a multiset may never contain more than {@link Integer#MAX_VALUE}
046 * occurrences of any one element.
047 *
048 * <p>{@code Multiset} refines the specifications of several methods from
049 * {@code Collection}. It also defines an additional query operation, {@link
050 * #count}, which returns the count of an element. There are five new
051 * bulk-modification operations, for example {@link #add(Object, int)}, to add
052 * or remove multiple occurrences of an element at once, or to set the count of
053 * an element to a specific value. These modification operations are optional,
054 * but implementations which support the standard collection operations {@link
055 * #add(Object)} or {@link #remove(Object)} are encouraged to implement the
056 * related methods as well. Finally, two collection views are provided: {@link
057 * #elementSet} contains the distinct elements of the multiset "with duplicates
058 * collapsed", and {@link #entrySet} is similar but contains {@link Entry
059 * Multiset.Entry} instances, each providing both a distinct element and the
060 * count of that element.
061 *
062 * <p>In addition to these required methods, implementations of {@code
063 * Multiset} are expected to provide two {@code static} creation methods:
064 * {@code create()}, returning an empty multiset, and {@code
065 * create(Iterable<? extends E>)}, returning a multiset containing the
066 * given initial elements. This is simply a refinement of {@code Collection}'s
067 * constructor recommendations, reflecting the new developments of Java 5.
068 *
069 * <p>As with other collection types, the modification operations are optional,
070 * and should throw {@link UnsupportedOperationException} when they are not
071 * implemented. Most implementations should support either all add operations
072 * or none of them, all removal operations or none of them, and if and only if
073 * all of these are supported, the {@code setCount} methods as well.
074 *
075 * <p>A multiset uses {@link Object#equals} to determine whether two instances
076 * should be considered "the same," <i>unless specified otherwise</i> by the
077 * implementation.
078 *
079 * <p>Common implementations include {@link ImmutableMultiset}, {@link
080 * HashMultiset}, and {@link ConcurrentHashMultiset}.
081 *
082 * <p>If your values may be zero, negative, or outside the range of an int, you
083 * may wish to use {@link com.google.common.util.concurrent.AtomicLongMap}
084 * instead. Note, however, that unlike {@code Multiset}, {@code AtomicLongMap}
085 * does not automatically remove zeros.
086 *
087 * <p>See the Guava User Guide article on <a href=
088 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multiset">
089 * {@code Multiset}</a>.
090 *
091 * @author Kevin Bourrillion
092 * @since 2.0
093 */
094@GwtCompatible
095public interface Multiset<E> extends Collection<E> {
096  // Query Operations
097
098  /**
099   * 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}