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