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