1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * A collection that supports order-independent equality, like {@link Set}, but 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * may have duplicate elements. A multiset is also sometimes called a 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <i>bag</i>. 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 347dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>Elements of a multiset that are equal to one another are referred to as 357dd252788645e940eada959bdde927426e2531c9Paul Duffin * <i>occurrences</i> of the same single element. The total number of 367dd252788645e940eada959bdde927426e2531c9Paul Duffin * occurrences of an element in a multiset is called the <i>count</i> of that 377dd252788645e940eada959bdde927426e2531c9Paul Duffin * element (the terms "frequency" and "multiplicity" are equivalent, but not 387dd252788645e940eada959bdde927426e2531c9Paul Duffin * used in this API). Since the count of an element is represented as an {@code 397dd252788645e940eada959bdde927426e2531c9Paul Duffin * int}, a multiset may never contain more than {@link Integer#MAX_VALUE} 407dd252788645e940eada959bdde927426e2531c9Paul Duffin * occurrences of any one element. 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>{@code Multiset} refines the specifications of several methods from 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code Collection}. It also defines an additional query operation, {@link 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #count}, which returns the count of an element. There are five new 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * bulk-modification operations, for example {@link #add(Object, int)}, to add 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * or remove multiple occurrences of an element at once, or to set the count of 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * an element to a specific value. These modification operations are optional, 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * but implementations which support the standard collection operations {@link 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #add(Object)} or {@link #remove(Object)} are encouraged to implement the 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * related methods as well. Finally, two collection views are provided: {@link 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #elementSet} contains the distinct elements of the multiset "with duplicates 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collapsed", and {@link #entrySet} is similar but contains {@link Entry 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multiset.Entry} instances, each providing both a distinct element and the 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * count of that element. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>In addition to these required methods, implementations of {@code 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multiset} are expected to provide two {@code static} creation methods: 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code create()}, returning an empty multiset, and {@code 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * create(Iterable<? extends E>)}, returning a multiset containing the 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * given initial elements. This is simply a refinement of {@code Collection}'s 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * constructor recommendations, reflecting the new developments of Java 5. 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>As with other collection types, the modification operations are optional, 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and should throw {@link UnsupportedOperationException} when they are not 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implemented. Most implementations should support either all add operations 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * or none of them, all removal operations or none of them, and if and only if 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all of these are supported, the {@code setCount} methods as well. 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>A multiset uses {@link Object#equals} to determine whether two instances 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * should be considered "the same," <i>unless specified otherwise</i> by the 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation. 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Common implementations include {@link ImmutableMultiset}, {@link 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * HashMultiset}, and {@link ConcurrentHashMultiset}. 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>If your values may be zero, negative, or outside the range of an int, you 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * may wish to use {@link com.google.common.util.concurrent.AtomicLongMap} 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * instead. Note, however, that unlike {@code Multiset}, {@code AtomicLongMap} 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * does not automatically remove zeros. 807dd252788645e940eada959bdde927426e2531c9Paul Duffin * 817dd252788645e940eada959bdde927426e2531c9Paul Duffin * <p>See the Guava User Guide article on <a href= 827dd252788645e940eada959bdde927426e2531c9Paul Duffin * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multiset"> 837dd252788645e940eada959bdde927426e2531c9Paul Duffin * {@code Multiset}</a>. 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic interface Multiset<E> extends Collection<E> { 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Query Operations 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the number of occurrences of an element in this multiset (the 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <i>count</i> of the element). Note that for an {@link Object#equals}-based 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset, this gives the same result as {@link Collections#frequency} 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * (which would presumably perform more poorly). 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> the utility method {@link Iterables#frequency} generalizes 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this operation; it correctly delegates to this method when dealing with a 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset, but it can also accept any other iterable type. 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to count occurrences of 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the number of occurrences of the element in this multiset; possibly 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * zero but never negative 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int count(@Nullable Object element); 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Bulk Operations 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds a number of occurrences of an element to this multiset. Note that if 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code occurrences == 1}, this method has the identical effect to {@link 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #add(Object)}. This method is functionally equivalent (except in the case 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of overflow) to the call {@code addAll(Collections.nCopies(element, 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences))}, which would presumably perform much more poorly. 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param element the element to add occurrences of; may be null only if 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * explicitly allowed by the implementation 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param occurrences the number of occurrences of the element to add. May be 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * zero, in which case no change will be made. 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the count of the element before the operation; possibly zero 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code occurrences} is negative, or if 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this operation would result in more than {@link Integer#MAX_VALUE} 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of the element 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null and this 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation does not permit null elements. Note that if {@code 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences} is zero, the implementation may opt to return normally. 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int add(@Nullable E element, int occurrences); 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Removes a number of occurrences of the specified element from this 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset. If the multiset contains fewer than this number of occurrences to 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * begin with, all occurrences will be removed. Note that if 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code occurrences == 1}, this is functionally equivalent to the call 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code remove(element)}. 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to conditionally remove occurrences of 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param occurrences the number of occurrences of the element to remove. May 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * be zero, in which case no change will be made. 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the count of the element before the operation; possibly zero 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code occurrences} is negative 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int remove(@Nullable Object element, int occurrences); 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds or removes the necessary occurrences of an element such that the 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * element attains the desired count. 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to add or remove occurrences of; may be null 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * only if explicitly allowed by the implementation 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param count the desired count of the element in this multiset 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the count of the element before the operation; possibly zero 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code count} is negative 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null and this 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation does not permit null elements. Note that if {@code 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * count} is zero, the implementor may optionally return zero instead. 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int setCount(E element, int count); 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Conditionally sets the count of an element to a new value, as described in 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #setCount(Object, int)}, provided that the element has the expected 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * current count. If the current count is not {@code oldCount}, no change is 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * made. 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to conditionally set the count of; may be null 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * only if explicitly allowed by the implementation 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param oldCount the expected present count of the element in this multiset 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param newCount the desired count of the element in this multiset 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} if the condition for modification was met. This 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implies that the multiset was indeed modified, unless 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code oldCount == newCount}. 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * negative 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null and the 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation does not permit null elements. Note that if {@code 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * oldCount} and {@code newCount} are both zero, the implementor may 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * optionally return {@code true} instead. 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean setCount(E element, int oldCount, int newCount); 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the set of distinct elements contained in this multiset. The 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * element set is backed by the same data as the multiset, so any change to 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * either is immediately reflected in the other. The order of the elements in 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the element set is unspecified. 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If the element set supports any removal operations, these necessarily 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * cause <b>all</b> occurrences of the removed element(s) to be removed from 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multiset. Implementations are not expected to support the add 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * operations, although this is possible. 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>A common use for the element set is to find the number of distinct 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in the multiset: {@code elementSet().size()}. 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a view of the set of distinct elements in this multiset 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<E> elementSet(); 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a view of the contents of this multiset, grouped into {@code 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multiset.Entry} instances, each providing an element of the multiset and 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the count of that element. This set contains exactly one entry for each 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distinct element in the multiset (thus it always has the same size as the 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #elementSet}). The order of the elements in the element set is 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * unspecified. 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The entry set is backed by the same data as the multiset, so any change 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to either is immediately reflected in the other. However, multiset changes 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * may or may not be reflected in any {@code Entry} instances already 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * retrieved from the entry set (this is implementation-dependent). 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Furthermore, implementations are not required to support modifications to 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the entry set at all, and the {@code Entry} instances themselves don't 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * even have methods for modification. See the specific implementation class 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for more details on how its entry set handles modifications. 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a set of entries representing the data of this multiset 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Entry<E>> entrySet(); 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An unmodifiable element-count pair for a multiset. The {@link 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multiset#entrySet} method returns a view of the multiset whose elements 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * are of this class. A multiset implementation may return Entry instances 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that are either live "read-through" views to the Multiset, or immutable 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * snapshots. Note that this type is unrelated to the similarly-named type 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code Map.Entry}. 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson interface Entry<E> { 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the multiset element corresponding to this entry. Multiple calls 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to this method always return the same instance. 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the element corresponding to this entry 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E getElement(); 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the count of the associated element in the underlying multiset. 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This count may either be an unchanging snapshot of the count at the time 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the entry was retrieved, or a live view of the current count of the 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * element in the multiset, depending on the implementation. Note that in 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the former case, this method can never return zero, while in the latter, 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it will return zero if all occurrences of the element were since removed 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * from the multiset. 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the count of the element; never negative 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int getCount(); 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Returns {@code true} if the given object is also a multiset entry and 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the two entries represent the same element and count. That is, two 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * entries {@code a} and {@code b} are equal if: <pre> {@code 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Objects.equal(a.getElement(), b.getElement()) 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * && a.getCount() == b.getCount()}</pre> 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2670888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): check this wrt TreeMultiset? 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean equals(Object o); 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The hash code of a multiset entry for element {@code element} and 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * count {@code count} is defined as: <pre> {@code 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ((element == null) ? 0 : element.hashCode()) ^ count}</pre> 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2790888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode(); 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the canonical string representation of this entry, defined as 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * follows. If the count for this entry is one, this is simply the string 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * representation of the corresponding element. Otherwise, it is the string 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * representation of the element, followed by the three characters {@code 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * " x "} (space, letter x, space), followed by the count. 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2890888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson String toString(); 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Comparison and hashing 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Compares the specified object with this multiset for equality. Returns 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code true} if the given object is also a multiset and contains equal 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements with equal counts, regardless of order. 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3000888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): caveats about equivalence-relation? 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean equals(@Nullable Object object); 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the hash code for this multiset. This is defined as the sum of 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <pre> {@code 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ((element == null) ? 0 : element.hashCode()) ^ count(element)}</pre> 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 3100888a09821a98ac0680fad765217302858e70fa4Paul Duffin * <p>over all distinct elements in the multiset. It follows that a multiset and 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * its entry set always have the same hash code. 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3130888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode(); 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>It is recommended, though not mandatory, that this method return the 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * result of invoking {@link #toString} on the {@link #entrySet}, yielding a 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * result such as {@code [a x 3, c, d x 2, e]}. 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3230888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson String toString(); 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Refined Collection Methods 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Elements that occur multiple times in the multiset will appear 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiple times in this iterator, though not necessarily sequentially. 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3340888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<E> iterator(); 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Determines whether this multiset contains the specified element. 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#contains} to further specify that 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it <b>may not</b> throw an exception in response to {@code element} being 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * null or of the wrong type. 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to check for 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} if this multiset contains at least one occurrence of 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the element 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3480888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean contains(@Nullable Object element); 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns {@code true} if this multiset contains at least one occurrence of 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * each element in the specified collection. 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#containsAll} to further specify 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that it <b>may not</b> throw an exception in response to any of {@code 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements} being null or of the wrong type. 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> this method does not take into account the occurrence 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * count of an element in the two collections; it may still return {@code 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * true} even if {@code elements} contains several occurrences of an element 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and this multiset contains only one. This is no different than any other 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection type like {@link List}, but it may be unexpected to the user of 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a multiset. 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the collection of elements to be checked for containment in 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this multiset 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} if this multiset contains at least one occurrence of 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * each element contained in {@code elements} 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} is null 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3720888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean containsAll(Collection<?> elements); 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds a single occurrence of the specified element to this multiset. 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#add}, which only <i>ensures</i> 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the presence of the element, to further specify that a successful call must 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * always increment the count of the element, and the overall size of the 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection, by one. 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to add one occurrence of; may be null only if 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * explicitly allowed by the implementation 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} always, since this call is required to modify the 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset, unlike other {@link Collection} types 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null and this 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation does not permit null elements 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@link Integer#MAX_VALUE} occurrences 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of {@code element} are already contained in this multiset 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3920888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean add(E element); 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Removes a <i>single</i> occurrence of the specified element from this 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multiset, if present. 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#remove} to further specify that it 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <b>may not</b> throw an exception in response to {@code element} being null 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * or of the wrong type. 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to remove one occurrence of 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} if an occurrence was found and removed 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4060888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean remove(@Nullable Object element); 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> This method ignores how often any element might appear in 4131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code c}, and only cares whether or not an element appears at all. 4141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * If you wish to remove one occurrence in this multiset for every occurrence 4151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in {@code c}, see {@link Multisets#removeOccurrences(Multiset, Multiset)}. 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#removeAll} to further specify that 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it <b>may not</b> throw an exception in response to any of {@code elements} 4191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * being null or of the wrong type. 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4210888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean removeAll(Collection<?> c); 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> This method ignores how often any element might appear in 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code c}, and only cares whether or not an element appears at all. 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * If you wish to remove one occurrence in this multiset for every occurrence 4301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in {@code c}, see {@link Multisets#retainOccurrences(Multiset, Multiset)}. 4311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This method refines {@link Collection#retainAll} to further specify that 433090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it <b>may not</b> throw an exception in response to any of {@code elements} 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * being null or of the wrong type. 4351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @see Multisets#retainOccurrences(Multiset, Multiset) 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 4380888a09821a98ac0680fad765217302858e70fa4Paul Duffin @Override 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean retainAll(Collection<?> c); 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 441