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