1/* 2 * Copyright (C) 2008 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 17package com.google.common.collect; 18 19import static com.google.common.base.Preconditions.checkNotNull; 20 21import com.google.common.annotations.GwtCompatible; 22import com.google.common.collect.Multiset.Entry; 23import com.google.common.primitives.Ints; 24 25import java.io.Serializable; 26import java.util.Arrays; 27import java.util.Collection; 28import java.util.Iterator; 29 30import javax.annotation.Nullable; 31 32/** 33 * An immutable hash-based multiset. Does not permit null elements. 34 * 35 * <p>Its iterator orders elements according to the first appearance of the 36 * element among the items passed to the factory method or builder. When the 37 * multiset contains multiple instances of an element, those instances are 38 * consecutive in the iteration order. 39 * 40 * <p>See the Guava User Guide article on <a href= 41 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained"> 42 * immutable collections</a>. 43 * 44 * @author Jared Levy 45 * @author Louis Wasserman 46 * @since 2.0 (imported from Google Collections Library) 47 */ 48@GwtCompatible(serializable = true, emulated = true) 49@SuppressWarnings("serial") // we're overriding default serialization 50// TODO(user): write an efficient asList() implementation 51public abstract class ImmutableMultiset<E> extends ImmutableCollection<E> 52 implements Multiset<E> { 53 54 private static final ImmutableMultiset<Object> EMPTY = 55 new RegularImmutableMultiset<Object>(ImmutableMap.<Object, Integer>of(), 0); 56 57 /** 58 * Returns the empty immutable multiset. 59 */ 60 @SuppressWarnings("unchecked") // all supported methods are covariant 61 public static <E> ImmutableMultiset<E> of() { 62 return (ImmutableMultiset<E>) EMPTY; 63 } 64 65 /** 66 * Returns an immutable multiset containing a single element. 67 * 68 * @throws NullPointerException if {@code element} is null 69 * @since 6.0 (source-compatible since 2.0) 70 */ 71 @SuppressWarnings("unchecked") // generic array created but never written 72 public static <E> ImmutableMultiset<E> of(E element) { 73 return copyOfInternal(element); 74 } 75 76 /** 77 * Returns an immutable multiset containing the given elements, in order. 78 * 79 * @throws NullPointerException if any element is null 80 * @since 6.0 (source-compatible since 2.0) 81 */ 82 @SuppressWarnings("unchecked") // 83 public static <E> ImmutableMultiset<E> of(E e1, E e2) { 84 return copyOfInternal(e1, e2); 85 } 86 87 /** 88 * Returns an immutable multiset containing the given elements, in order. 89 * 90 * @throws NullPointerException if any element is null 91 * @since 6.0 (source-compatible since 2.0) 92 */ 93 @SuppressWarnings("unchecked") // 94 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3) { 95 return copyOfInternal(e1, e2, e3); 96 } 97 98 /** 99 * Returns an immutable multiset containing the given elements, in order. 100 * 101 * @throws NullPointerException if any element is null 102 * @since 6.0 (source-compatible since 2.0) 103 */ 104 @SuppressWarnings("unchecked") // 105 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4) { 106 return copyOfInternal(e1, e2, e3, e4); 107 } 108 109 /** 110 * Returns an immutable multiset containing the given elements, in order. 111 * 112 * @throws NullPointerException if any element is null 113 * @since 6.0 (source-compatible since 2.0) 114 */ 115 @SuppressWarnings("unchecked") // 116 public static <E> ImmutableMultiset<E> of(E e1, E e2, E e3, E e4, E e5) { 117 return copyOfInternal(e1, e2, e3, e4, e5); 118 } 119 120 /** 121 * Returns an immutable multiset containing the given elements, in order. 122 * 123 * @throws NullPointerException if any element is null 124 * @since 6.0 (source-compatible since 2.0) 125 */ 126 @SuppressWarnings("unchecked") // 127 public static <E> ImmutableMultiset<E> of( 128 E e1, E e2, E e3, E e4, E e5, E e6, E... others) { 129 return new Builder<E>() 130 .add(e1) 131 .add(e2) 132 .add(e3) 133 .add(e4) 134 .add(e5) 135 .add(e6) 136 .add(others) 137 .build(); 138 } 139 140 /** 141 * Returns an immutable multiset containing the given elements. 142 * 143 * <p>The multiset is ordered by the first occurrence of each element. For 144 * example, {@code ImmutableMultiset.copyOf([2, 3, 1, 3])} yields a multiset 145 * with elements in the order {@code 2, 3, 3, 1}. 146 * 147 * @throws NullPointerException if any of {@code elements} is null 148 * @since 6.0 149 */ 150 public static <E> ImmutableMultiset<E> copyOf(E[] elements) { 151 return copyOf(Arrays.asList(elements)); 152 } 153 154 /** 155 * Returns an immutable multiset containing the given elements. 156 * 157 * <p>The multiset is ordered by the first occurrence of each element. For 158 * example, {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3))} yields 159 * a multiset with elements in the order {@code 2, 3, 3, 1}. 160 * 161 * <p>Despite the method name, this method attempts to avoid actually copying 162 * the data when it is safe to do so. The exact circumstances under which a 163 * copy will or will not be performed are undocumented and subject to change. 164 * 165 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements} 166 * is an {@code ImmutableMultiset}, no copy will actually be performed, and 167 * the given multiset itself will be returned. 168 * 169 * @throws NullPointerException if any of {@code elements} is null 170 */ 171 public static <E> ImmutableMultiset<E> copyOf( 172 Iterable<? extends E> elements) { 173 if (elements instanceof ImmutableMultiset) { 174 @SuppressWarnings("unchecked") // all supported methods are covariant 175 ImmutableMultiset<E> result = (ImmutableMultiset<E>) elements; 176 if (!result.isPartialView()) { 177 return result; 178 } 179 } 180 181 Multiset<? extends E> multiset = (elements instanceof Multiset) 182 ? Multisets.cast(elements) 183 : LinkedHashMultiset.create(elements); 184 185 return copyOfInternal(multiset); 186 } 187 188 private static <E> ImmutableMultiset<E> copyOfInternal(E... elements) { 189 return copyOf(Arrays.asList(elements)); 190 } 191 192 private static <E> ImmutableMultiset<E> copyOfInternal( 193 Multiset<? extends E> multiset) { 194 return copyFromEntries(multiset.entrySet()); 195 } 196 197 static <E> ImmutableMultiset<E> copyFromEntries( 198 Collection<? extends Entry<? extends E>> entries) { 199 long size = 0; 200 ImmutableMap.Builder<E, Integer> builder = ImmutableMap.builder(); 201 for (Entry<? extends E> entry : entries) { 202 int count = entry.getCount(); 203 if (count > 0) { 204 // Since ImmutableMap.Builder throws an NPE if an element is null, no 205 // other null checks are needed. 206 builder.put(entry.getElement(), count); 207 size += count; 208 } 209 } 210 211 if (size == 0) { 212 return of(); 213 } 214 return new RegularImmutableMultiset<E>( 215 builder.build(), Ints.saturatedCast(size)); 216 } 217 218 /** 219 * Returns an immutable multiset containing the given elements. 220 * 221 * <p>The multiset is ordered by the first occurrence of each element. For 222 * example, 223 * {@code ImmutableMultiset.copyOf(Arrays.asList(2, 3, 1, 3).iterator())} 224 * yields a multiset with elements in the order {@code 2, 3, 3, 1}. 225 * 226 * @throws NullPointerException if any of {@code elements} is null 227 */ 228 public static <E> ImmutableMultiset<E> copyOf( 229 Iterator<? extends E> elements) { 230 Multiset<E> multiset = LinkedHashMultiset.create(); 231 Iterators.addAll(multiset, elements); 232 return copyOfInternal(multiset); 233 } 234 235 ImmutableMultiset() {} 236 237 @Override public UnmodifiableIterator<E> iterator() { 238 final Iterator<Entry<E>> entryIterator = entrySet().iterator(); 239 return new UnmodifiableIterator<E>() { 240 int remaining; 241 E element; 242 243 @Override 244 public boolean hasNext() { 245 return (remaining > 0) || entryIterator.hasNext(); 246 } 247 248 @Override 249 public E next() { 250 if (remaining <= 0) { 251 Entry<E> entry = entryIterator.next(); 252 element = entry.getElement(); 253 remaining = entry.getCount(); 254 } 255 remaining--; 256 return element; 257 } 258 }; 259 } 260 261 @Override 262 public boolean contains(@Nullable Object object) { 263 return count(object) > 0; 264 } 265 266 @Override 267 public boolean containsAll(Collection<?> targets) { 268 return elementSet().containsAll(targets); 269 } 270 271 /** 272 * Guaranteed to throw an exception and leave the collection unmodified. 273 * 274 * @throws UnsupportedOperationException always 275 * @deprecated Unsupported operation. 276 */ 277 @Deprecated 278 @Override 279 public final int add(E element, int occurrences) { 280 throw new UnsupportedOperationException(); 281 } 282 283 /** 284 * Guaranteed to throw an exception and leave the collection unmodified. 285 * 286 * @throws UnsupportedOperationException always 287 * @deprecated Unsupported operation. 288 */ 289 @Deprecated 290 @Override 291 public final int remove(Object element, int occurrences) { 292 throw new UnsupportedOperationException(); 293 } 294 295 /** 296 * Guaranteed to throw an exception and leave the collection unmodified. 297 * 298 * @throws UnsupportedOperationException always 299 * @deprecated Unsupported operation. 300 */ 301 @Deprecated 302 @Override 303 public final int setCount(E element, int count) { 304 throw new UnsupportedOperationException(); 305 } 306 307 /** 308 * Guaranteed to throw an exception and leave the collection unmodified. 309 * 310 * @throws UnsupportedOperationException always 311 * @deprecated Unsupported operation. 312 */ 313 @Deprecated 314 @Override 315 public final boolean setCount(E element, int oldCount, int newCount) { 316 throw new UnsupportedOperationException(); 317 } 318 319 @Override public boolean equals(@Nullable Object object) { 320 return Multisets.equalsImpl(this, object); 321 } 322 323 @Override public int hashCode() { 324 return Sets.hashCodeImpl(entrySet()); 325 } 326 327 @Override public String toString() { 328 return entrySet().toString(); 329 } 330 331 private transient ImmutableSet<Entry<E>> entrySet; 332 333 @Override 334 public ImmutableSet<Entry<E>> entrySet() { 335 ImmutableSet<Entry<E>> es = entrySet; 336 return (es == null) ? (entrySet = createEntrySet()) : es; 337 } 338 339 private final ImmutableSet<Entry<E>> createEntrySet() { 340 return isEmpty() ? ImmutableSet.<Entry<E>>of() : new EntrySet(); 341 } 342 343 abstract Entry<E> getEntry(int index); 344 345 private final class EntrySet extends ImmutableSet<Entry<E>> { 346 @Override 347 boolean isPartialView() { 348 return ImmutableMultiset.this.isPartialView(); 349 } 350 351 @Override 352 public UnmodifiableIterator<Entry<E>> iterator() { 353 return asList().iterator(); 354 } 355 356 @Override 357 ImmutableList<Entry<E>> createAsList() { 358 return new ImmutableAsList<Entry<E>>() { 359 @Override 360 public Entry<E> get(int index) { 361 return getEntry(index); 362 } 363 364 @Override 365 ImmutableCollection<Entry<E>> delegateCollection() { 366 return EntrySet.this; 367 } 368 }; 369 } 370 371 @Override 372 public int size() { 373 return elementSet().size(); 374 } 375 376 @Override 377 public boolean contains(Object o) { 378 if (o instanceof Entry) { 379 Entry<?> entry = (Entry<?>) o; 380 if (entry.getCount() <= 0) { 381 return false; 382 } 383 int count = count(entry.getElement()); 384 return count == entry.getCount(); 385 } 386 return false; 387 } 388 389 @Override 390 public int hashCode() { 391 return ImmutableMultiset.this.hashCode(); 392 } 393 394 // We can't label this with @Override, because it doesn't override anything 395 // in the GWT emulated version. 396 // TODO(cpovirk): try making all copies of this method @GwtIncompatible instead 397 Object writeReplace() { 398 return new EntrySetSerializedForm<E>(ImmutableMultiset.this); 399 } 400 401 private static final long serialVersionUID = 0; 402 } 403 404 static class EntrySetSerializedForm<E> implements Serializable { 405 final ImmutableMultiset<E> multiset; 406 407 EntrySetSerializedForm(ImmutableMultiset<E> multiset) { 408 this.multiset = multiset; 409 } 410 411 Object readResolve() { 412 return multiset.entrySet(); 413 } 414 } 415 416 private static class SerializedForm implements Serializable { 417 final Object[] elements; 418 final int[] counts; 419 420 SerializedForm(Multiset<?> multiset) { 421 int distinct = multiset.entrySet().size(); 422 elements = new Object[distinct]; 423 counts = new int[distinct]; 424 int i = 0; 425 for (Entry<?> entry : multiset.entrySet()) { 426 elements[i] = entry.getElement(); 427 counts[i] = entry.getCount(); 428 i++; 429 } 430 } 431 432 Object readResolve() { 433 LinkedHashMultiset<Object> multiset = 434 LinkedHashMultiset.create(elements.length); 435 for (int i = 0; i < elements.length; i++) { 436 multiset.add(elements[i], counts[i]); 437 } 438 return ImmutableMultiset.copyOf(multiset); 439 } 440 441 private static final long serialVersionUID = 0; 442 } 443 444 // We can't label this with @Override, because it doesn't override anything 445 // in the GWT emulated version. 446 Object writeReplace() { 447 return new SerializedForm(this); 448 } 449 450 /** 451 * Returns a new builder. The generated builder is equivalent to the builder 452 * created by the {@link Builder} constructor. 453 */ 454 public static <E> Builder<E> builder() { 455 return new Builder<E>(); 456 } 457 458 /** 459 * A builder for creating immutable multiset instances, especially {@code 460 * public static final} multisets ("constant multisets"). Example: 461 * <pre> {@code 462 * 463 * public static final ImmutableMultiset<Bean> BEANS = 464 * new ImmutableMultiset.Builder<Bean>() 465 * .addCopies(Bean.COCOA, 4) 466 * .addCopies(Bean.GARDEN, 6) 467 * .addCopies(Bean.RED, 8) 468 * .addCopies(Bean.BLACK_EYED, 10) 469 * .build();}</pre> 470 * 471 * <p>Builder instances can be reused; it is safe to call {@link #build} multiple 472 * times to build multiple multisets in series. 473 * 474 * @since 2.0 (imported from Google Collections Library) 475 */ 476 public static class Builder<E> extends ImmutableCollection.Builder<E> { 477 final Multiset<E> contents; 478 479 /** 480 * Creates a new builder. The returned builder is equivalent to the builder 481 * generated by {@link ImmutableMultiset#builder}. 482 */ 483 public Builder() { 484 this(LinkedHashMultiset.<E>create()); 485 } 486 487 Builder(Multiset<E> contents) { 488 this.contents = contents; 489 } 490 491 /** 492 * Adds {@code element} to the {@code ImmutableMultiset}. 493 * 494 * @param element the element to add 495 * @return this {@code Builder} object 496 * @throws NullPointerException if {@code element} is null 497 */ 498 @Override public Builder<E> add(E element) { 499 contents.add(checkNotNull(element)); 500 return this; 501 } 502 503 /** 504 * Adds a number of occurrences of an element to this {@code 505 * ImmutableMultiset}. 506 * 507 * @param element the element to add 508 * @param occurrences the number of occurrences of the element to add. May 509 * be zero, in which case no change will be made. 510 * @return this {@code Builder} object 511 * @throws NullPointerException if {@code element} is null 512 * @throws IllegalArgumentException if {@code occurrences} is negative, or 513 * if this operation would result in more than {@link Integer#MAX_VALUE} 514 * occurrences of the element 515 */ 516 public Builder<E> addCopies(E element, int occurrences) { 517 contents.add(checkNotNull(element), occurrences); 518 return this; 519 } 520 521 /** 522 * Adds or removes the necessary occurrences of an element such that the 523 * element attains the desired count. 524 * 525 * @param element the element to add or remove occurrences of 526 * @param count the desired count of the element in this multiset 527 * @return this {@code Builder} object 528 * @throws NullPointerException if {@code element} is null 529 * @throws IllegalArgumentException if {@code count} is negative 530 */ 531 public Builder<E> setCount(E element, int count) { 532 contents.setCount(checkNotNull(element), count); 533 return this; 534 } 535 536 /** 537 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 538 * 539 * @param elements the elements to add 540 * @return this {@code Builder} object 541 * @throws NullPointerException if {@code elements} is null or contains a 542 * null element 543 */ 544 @Override public Builder<E> add(E... elements) { 545 super.add(elements); 546 return this; 547 } 548 549 /** 550 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 551 * 552 * @param elements the {@code Iterable} to add to the {@code 553 * ImmutableMultiset} 554 * @return this {@code Builder} object 555 * @throws NullPointerException if {@code elements} is null or contains a 556 * null element 557 */ 558 @Override public Builder<E> addAll(Iterable<? extends E> elements) { 559 if (elements instanceof Multiset) { 560 Multiset<? extends E> multiset = Multisets.cast(elements); 561 for (Entry<? extends E> entry : multiset.entrySet()) { 562 addCopies(entry.getElement(), entry.getCount()); 563 } 564 } else { 565 super.addAll(elements); 566 } 567 return this; 568 } 569 570 /** 571 * Adds each element of {@code elements} to the {@code ImmutableMultiset}. 572 * 573 * @param elements the elements to add to the {@code ImmutableMultiset} 574 * @return this {@code Builder} object 575 * @throws NullPointerException if {@code elements} is null or contains a 576 * null element 577 */ 578 @Override public Builder<E> addAll(Iterator<? extends E> elements) { 579 super.addAll(elements); 580 return this; 581 } 582 583 /** 584 * Returns a newly-created {@code ImmutableMultiset} based on the contents 585 * of the {@code Builder}. 586 */ 587 @Override public ImmutableMultiset<E> build() { 588 return copyOf(contents); 589 } 590 } 591} 592