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    
017    package com.google.common.collect;
018    
019    import com.google.common.annotations.GwtCompatible;
020    
021    import java.util.Collection;
022    import java.util.Collections;
023    import java.util.Iterator;
024    import java.util.List;
025    import java.util.Set;
026    
027    import 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.0 (imported from Google Collections Library)
075     */
076    @GwtCompatible
077    public 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 null only if
106       *     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.0 (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><b>Note:</b> This method ignores how often any element might appear in
401       * {@code c}, and only cares whether or not an element appears at all.
402       * If you wish to remove one occurrence in this multiset for every occurrence
403       * in {@code c}, see {@link Multisets#removeOccurrences(Multiset, Multiset)}.
404       * 
405       * <p>This method refines {@link Collection#removeAll} to further specify that
406       * it <b>may not</b> throw an exception in response to any of {@code elements}
407       * being null or of the wrong type. 
408       */
409      @Override
410      boolean removeAll(Collection<?> c);
411    
412      /**
413       * {@inheritDoc}
414       *
415       * <p><b>Note:</b> This method ignores how often any element might appear in
416       * {@code c}, and only cares whether or not an element appears at all.
417       * If you wish to remove one occurrence in this multiset for every occurrence
418       * in {@code c}, see {@link Multisets#retainOccurrences(Multiset, Multiset)}.
419       * 
420       * <p>This method refines {@link Collection#retainAll} to further specify that
421       * it <b>may not</b> throw an exception in response to any of {@code elements}
422       * being null or of the wrong type.
423       * 
424       * @see Multisets#retainOccurrences(Multiset, Multiset)
425       */
426      @Override
427      boolean retainAll(Collection<?> c);
428    }