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