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