1 /* 2 * Copyright (C) 2007 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect; 18 19 import com.google.common.annotations.GwtCompatible; 20 21 import java.util.Collection; 22 import java.util.Collections; 23 import java.util.Iterator; 24 import java.util.List; 25 import java.util.Set; 26 27 import javax.annotation.Nullable; 28 29 /** 30 * A collection that supports order-independent equality, like {@link Set}, but 31 * may have duplicate elements. A multiset is also sometimes called a 32 * <i>bag</i>. 33 * 34 * <p>Elements of a multiset that are equal to one another are referred to as 35 * <i>occurrences</i> of the same single element. The total number of 36 * occurrences of an element in a multiset is called the <i>count</i> of that 37 * element (the terms "frequency" and "multiplicity" are equivalent, but not 38 * used in this API). Since the count of an element is represented as an {@code 39 * int}, a multiset may never contain more than {@link Integer#MAX_VALUE} 40 * occurrences of any one element. 41 * 42 * <p>{@code Multiset} refines the specifications of several methods from 43 * {@code Collection}. It also defines an additional query operation, {@link 44 * #count}, which returns the count of an element. There are five new 45 * bulk-modification operations, for example {@link #add(Object, int)}, to add 46 * or remove multiple occurrences of an element at once, or to set the count of 47 * an element to a specific value. These modification operations are optional, 48 * but implementations which support the standard collection operations {@link 49 * #add(Object)} or {@link #remove(Object)} are encouraged to implement the 50 * related methods as well. Finally, two collection views are provided: {@link 51 * #elementSet} contains the distinct elements of the multiset "with duplicates 52 * collapsed", and {@link #entrySet} is similar but contains {@link Entry 53 * Multiset.Entry} instances, each providing both a distinct element and the 54 * count of that element. 55 * 56 * <p>In addition to these required methods, implementations of {@code 57 * Multiset} are expected to provide two {@code static} creation methods: 58 * {@code create()}, returning an empty multiset, and {@code 59 * create(Iterable<? extends E>)}, returning a multiset containing the 60 * given initial elements. This is simply a refinement of {@code Collection}'s 61 * constructor recommendations, reflecting the new developments of Java 5. 62 * 63 * <p>As with other collection types, the modification operations are optional, 64 * and should throw {@link UnsupportedOperationException} when they are not 65 * implemented. Most implementations should support either all add operations 66 * or none of them, all removal operations or none of them, and if and only if 67 * all of these are supported, the {@code setCount} methods as well. 68 * 69 * <p>A multiset uses {@link Object#equals} to determine whether two instances 70 * should be considered "the same," <i>unless specified otherwise</i> by the 71 * implementation. 72 * 73 * <p>Common implementations include {@link ImmutableMultiset}, {@link 74 * HashMultiset}, and {@link ConcurrentHashMultiset}. 75 * 76 * <p>If your values may be zero, negative, or outside the range of an int, you 77 * may wish to use {@link com.google.common.util.concurrent.AtomicLongMap} 78 * instead. Note, however, that unlike {@code Multiset}, {@code AtomicLongMap} 79 * does not automatically remove zeros. 80 * 81 * <p>See the Guava User Guide article on <a href= 82 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multiset"> 83 * {@code Multiset}</a>. 84 * 85 * @author Kevin Bourrillion 86 * @since 2.0 (imported from Google Collections Library) 87 */ 88 @GwtCompatible 89 public interface Multiset<E> extends Collection<E> { 90 // Query Operations 91 92 /** 93 * Returns the number of occurrences of an element in this multiset (the 94 * <i>count</i> of the element). Note that for an {@link Object#equals}-based 95 * multiset, this gives the same result as {@link Collections#frequency} 96 * (which would presumably perform more poorly). 97 * 98 * <p><b>Note:</b> the utility method {@link Iterables#frequency} generalizes 99 * this operation; it correctly delegates to this method when dealing with a 100 * multiset, but it can also accept any other iterable type. 101 * 102 * @param element the element to count occurrences of 103 * @return the number of occurrences of the element in this multiset; possibly 104 * zero but never negative 105 */ 106 int count(@Nullable Object element); 107 108 // Bulk Operations 109 110 /** 111 * Adds a number of occurrences of an element to this multiset. Note that if 112 * {@code occurrences == 1}, this method has the identical effect to {@link 113 * #add(Object)}. This method is functionally equivalent (except in the case 114 * of overflow) to the call {@code addAll(Collections.nCopies(element, 115 * occurrences))}, which would presumably perform much more poorly. 116 * 117 * @param element the element to add occurrences of; may be null only if 118 * explicitly allowed by the implementation 119 * @param occurrences the number of occurrences of the element to add. May be 120 * zero, in which case no change will be made. 121 * @return the count of the element before the operation; possibly zero 122 * @throws IllegalArgumentException if {@code occurrences} is negative, or if 123 * this operation would result in more than {@link Integer#MAX_VALUE} 124 * occurrences of the element 125 * @throws NullPointerException if {@code element} is null and this 126 * implementation does not permit null elements. Note that if {@code 127 * occurrences} is zero, the implementation may opt to return normally. 128 */ 129 int add(@Nullable E element, int occurrences); 130 131 /** 132 * Removes a number of occurrences of the specified element from this 133 * multiset. If the multiset contains fewer than this number of occurrences to 134 * begin with, all occurrences will be removed. Note that if 135 * {@code occurrences == 1}, this is functionally equivalent to the call 136 * {@code remove(element)}. 137 * 138 * @param element the element to conditionally remove occurrences of 139 * @param occurrences the number of occurrences of the element to remove. May 140 * be zero, in which case no change will be made. 141 * @return the count of the element before the operation; possibly zero 142 * @throws IllegalArgumentException if {@code occurrences} is negative 143 */ 144 int remove(@Nullable Object element, int occurrences); 145 146 /** 147 * Adds or removes the necessary occurrences of an element such that the 148 * element attains the desired count. 149 * 150 * @param element the element to add or remove occurrences of; may be null 151 * only if explicitly allowed by the implementation 152 * @param count the desired count of the element in this multiset 153 * @return the count of the element before the operation; possibly zero 154 * @throws IllegalArgumentException if {@code count} is negative 155 * @throws NullPointerException if {@code element} is null and this 156 * implementation does not permit null elements. Note that if {@code 157 * count} is zero, the implementor may optionally return zero instead. 158 */ 159 int setCount(E element, int count); 160 161 /** 162 * Conditionally sets the count of an element to a new value, as described in 163 * {@link #setCount(Object, int)}, provided that the element has the expected 164 * current count. If the current count is not {@code oldCount}, no change is 165 * made. 166 * 167 * @param element the element to conditionally set the count of; may be null 168 * only if explicitly allowed by the implementation 169 * @param oldCount the expected present count of the element in this multiset 170 * @param newCount the desired count of the element in this multiset 171 * @return {@code true} if the condition for modification was met. This 172 * implies that the multiset was indeed modified, unless 173 * {@code oldCount == newCount}. 174 * @throws IllegalArgumentException if {@code oldCount} or {@code newCount} is 175 * negative 176 * @throws NullPointerException if {@code element} is null and the 177 * implementation does not permit null elements. Note that if {@code 178 * oldCount} and {@code newCount} are both zero, the implementor may 179 * optionally return {@code true} instead. 180 */ 181 boolean setCount(E element, int oldCount, int newCount); 182 183 // Views 184 185 /** 186 * Returns the set of distinct elements contained in this multiset. The 187 * element set is backed by the same data as the multiset, so any change to 188 * either is immediately reflected in the other. The order of the elements in 189 * the element set is unspecified. 190 * 191 * <p>If the element set supports any removal operations, these necessarily 192 * cause <b>all</b> occurrences of the removed element(s) to be removed from 193 * the multiset. Implementations are not expected to support the add 194 * operations, although this is possible. 195 * 196 * <p>A common use for the element set is to find the number of distinct 197 * elements in the multiset: {@code elementSet().size()}. 198 * 199 * @return a view of the set of distinct elements in this multiset 200 */ 201 Set<E> elementSet(); 202 203 /** 204 * Returns a view of the contents of this multiset, grouped into {@code 205 * Multiset.Entry} instances, each providing an element of the multiset and 206 * the count of that element. This set contains exactly one entry for each 207 * distinct element in the multiset (thus it always has the same size as the 208 * {@link #elementSet}). The order of the elements in the element set is 209 * unspecified. 210 * 211 * <p>The entry set is backed by the same data as the multiset, so any change 212 * to either is immediately reflected in the other. However, multiset changes 213 * may or may not be reflected in any {@code Entry} instances already 214 * retrieved from the entry set (this is implementation-dependent). 215 * Furthermore, implementations are not required to support modifications to 216 * the entry set at all, and the {@code Entry} instances themselves don't 217 * even have methods for modification. See the specific implementation class 218 * for more details on how its entry set handles modifications. 219 * 220 * @return a set of entries representing the data of this multiset 221 */ 222 Set<Entry<E>> entrySet(); 223 224 /** 225 * An unmodifiable element-count pair for a multiset. The {@link 226 * Multiset#entrySet} method returns a view of the multiset whose elements 227 * are of this class. A multiset implementation may return Entry instances 228 * that are either live "read-through" views to the Multiset, or immutable 229 * snapshots. Note that this type is unrelated to the similarly-named type 230 * {@code Map.Entry}. 231 * 232 * @since 2.0 (imported from Google Collections Library) 233 */ 234 interface Entry<E> { 235 236 /** 237 * Returns the multiset element corresponding to this entry. Multiple calls 238 * to this method always return the same instance. 239 * 240 * @return the element corresponding to this entry 241 */ 242 E getElement(); 243 244 /** 245 * Returns the count of the associated element in the underlying multiset. 246 * This count may either be an unchanging snapshot of the count at the time 247 * the entry was retrieved, or a live view of the current count of the 248 * element in the multiset, depending on the implementation. Note that in 249 * the former case, this method can never return zero, while in the latter, 250 * it will return zero if all occurrences of the element were since removed 251 * from the multiset. 252 * 253 * @return the count of the element; never negative 254 */ 255 int getCount(); 256 257 /** 258 * {@inheritDoc} 259 * 260 * <p>Returns {@code true} if the given object is also a multiset entry and 261 * the two entries represent the same element and count. That is, two 262 * entries {@code a} and {@code b} are equal if: <pre> {@code 263 * 264 * Objects.equal(a.getElement(), b.getElement()) 265 * && a.getCount() == b.getCount()}</pre> 266 */ 267 @Override 268 // TODO(kevinb): check this wrt TreeMultiset? 269 boolean equals(Object o); 270 271 /** 272 * {@inheritDoc} 273 * 274 * <p>The hash code of a multiset entry for element {@code element} and 275 * count {@code count} is defined as: <pre> {@code 276 * 277 * ((element == null) ? 0 : element.hashCode()) ^ count}</pre> 278 */ 279 @Override 280 int hashCode(); 281 282 /** 283 * Returns the canonical string representation of this entry, defined as 284 * follows. If the count for this entry is one, this is simply the string 285 * representation of the corresponding element. Otherwise, it is the string 286 * representation of the element, followed by the three characters {@code 287 * " x "} (space, letter x, space), followed by the count. 288 */ 289 @Override 290 String toString(); 291 } 292 293 // Comparison and hashing 294 295 /** 296 * Compares the specified object with this multiset for equality. Returns 297 * {@code true} if the given object is also a multiset and contains equal 298 * elements with equal counts, regardless of order. 299 */ 300 @Override 301 // TODO(kevinb): caveats about equivalence-relation? 302 boolean equals(@Nullable Object object); 303 304 /** 305 * Returns the hash code for this multiset. This is defined as the sum of 306 * <pre> {@code 307 * 308 * ((element == null) ? 0 : element.hashCode()) ^ count(element)}</pre> 309 * 310 * <p>over all distinct elements in the multiset. It follows that a multiset and 311 * its entry set always have the same hash code. 312 */ 313 @Override 314 int hashCode(); 315 316 /** 317 * {@inheritDoc} 318 * 319 * <p>It is recommended, though not mandatory, that this method return the 320 * result of invoking {@link #toString} on the {@link #entrySet}, yielding a 321 * result such as {@code [a x 3, c, d x 2, e]}. 322 */ 323 @Override 324 String toString(); 325 326 // Refined Collection Methods 327 328 /** 329 * {@inheritDoc} 330 * 331 * <p>Elements that occur multiple times in the multiset will appear 332 * multiple times in this iterator, though not necessarily sequentially. 333 */ 334 @Override 335 Iterator<E> iterator(); 336 337 /** 338 * Determines whether this multiset contains the specified element. 339 * 340 * <p>This method refines {@link Collection#contains} to further specify that 341 * it <b>may not</b> throw an exception in response to {@code element} being 342 * null or of the wrong type. 343 * 344 * @param element the element to check for 345 * @return {@code true} if this multiset contains at least one occurrence of 346 * the element 347 */ 348 @Override 349 boolean contains(@Nullable Object element); 350 351 /** 352 * Returns {@code true} if this multiset contains at least one occurrence of 353 * each element in the specified collection. 354 * 355 * <p>This method refines {@link Collection#containsAll} to further specify 356 * that it <b>may not</b> throw an exception in response to any of {@code 357 * elements} being null or of the wrong type. 358 * 359 * <p><b>Note:</b> this method does not take into account the occurrence 360 * count of an element in the two collections; it may still return {@code 361 * true} even if {@code elements} contains several occurrences of an element 362 * and this multiset contains only one. This is no different than any other 363 * collection type like {@link List}, but it may be unexpected to the user of 364 * a multiset. 365 * 366 * @param elements the collection of elements to be checked for containment in 367 * this multiset 368 * @return {@code true} if this multiset contains at least one occurrence of 369 * each element contained in {@code elements} 370 * @throws NullPointerException if {@code elements} is null 371 */ 372 @Override 373 boolean containsAll(Collection<?> elements); 374 375 /** 376 * Adds a single occurrence of the specified element to this multiset. 377 * 378 * <p>This method refines {@link Collection#add}, which only <i>ensures</i> 379 * the presence of the element, to further specify that a successful call must 380 * always increment the count of the element, and the overall size of the 381 * collection, by one. 382 * 383 * @param element the element to add one occurrence of; may be null only if 384 * explicitly allowed by the implementation 385 * @return {@code true} always, since this call is required to modify the 386 * multiset, unlike other {@link Collection} types 387 * @throws NullPointerException if {@code element} is null and this 388 * implementation does not permit null elements 389 * @throws IllegalArgumentException if {@link Integer#MAX_VALUE} occurrences 390 * of {@code element} are already contained in this multiset 391 */ 392 @Override 393 boolean add(E element); 394 395 /** 396 * Removes a <i>single</i> occurrence of the specified element from this 397 * multiset, if present. 398 * 399 * <p>This method refines {@link Collection#remove} to further specify that it 400 * <b>may not</b> throw an exception in response to {@code element} being null 401 * or of the wrong type. 402 * 403 * @param element the element to remove one occurrence of 404 * @return {@code true} if an occurrence was found and removed 405 */ 406 @Override 407 boolean remove(@Nullable Object element); 408 409 /** 410 * {@inheritDoc} 411 * 412 * <p><b>Note:</b> This method ignores how often any element might appear in 413 * {@code c}, and only cares whether or not an element appears at all. 414 * If you wish to remove one occurrence in this multiset for every occurrence 415 * in {@code c}, see {@link Multisets#removeOccurrences(Multiset, Multiset)}. 416 * 417 * <p>This method refines {@link Collection#removeAll} to further specify that 418 * it <b>may not</b> throw an exception in response to any of {@code elements} 419 * being null or of the wrong type. 420 */ 421 @Override 422 boolean removeAll(Collection<?> c); 423 424 /** 425 * {@inheritDoc} 426 * 427 * <p><b>Note:</b> This method ignores how often any element might appear in 428 * {@code c}, and only cares whether or not an element appears at all. 429 * If you wish to remove one occurrence in this multiset for every occurrence 430 * in {@code c}, see {@link Multisets#retainOccurrences(Multiset, Multiset)}. 431 * 432 * <p>This method refines {@link Collection#retainAll} to further specify that 433 * it <b>may not</b> throw an exception in response to any of {@code elements} 434 * being null or of the wrong type. 435 * 436 * @see Multisets#retainOccurrences(Multiset, Multiset) 437 */ 438 @Override 439 boolean retainAll(Collection<?> c); 440 } 441
